Question

Problem 1 (20 pts) Consider the mathematical program max 3x1+x2 +3x3 s.t. 2x1 +x2 + x3 +x2 x1 + 2x2 + 3x3 +2xs 5 2x 2x2 +x3 +3x6-6 Xy X2, X3, X4, Xs, X620 Three feasible solutions ((a) through (c)) are listed below. (0.3, 0.1, 0.4, 0.9, 1.65, 1.6) (c) x Please choose one appropriate interior point from the list, and use the Karmarkar's Method at the interior point and determine the optimal solution. 25

Answer 1

MAXIMIZE: Z = 3 X1 + 1 X2 + 3 X3 + X4 + X5 + X6		MAXIMIZE: Z = 3 X1 + 1 X2 + 3 X3 + 0 X4 + 0 X5 + 0 X6 + 0 X7 + 0 X8 + 0 X9
subject to 2 X1 + 1 X2 + 1 X3 + 1 X4 + 0 X5 + 0 X6 = 2 1 X1 + 2 X2 + 3 X3 + 0 X4 + 2 X5 + 0 X6 = 5 2 X1 + 2 X2 + 1 X3 + 0 X4 + 0 X5 + 3 X6 = 6		subject to 2 X1 + 1 X2 + 1 X3 + 1 X4 + 1 X9 = 2 1 X1 + 2 X2 + 3 X3 + 2 X5 + 1 X8 = 5 2 X1 + 2 X2 + 1 X3 + 3 X6 + 1 X7 = 6
X1, X2, X3, X4, X5, X6 ≥ 0		X1, X2, X3, X4, X5, X6, X7, X8, X9 ≥ 0

Tableau 1			0	0	0	0	0	0	-1	-1	-1
Base	Cb	P0	P1	P2	P3	P4	P5	P6	P7	P8	P9
P9	-1	2	2	1	1	1	0	0	0	0	1
P8	-1	5	1	2	3	0	2	0	0	1	0
P7	-1	6	2	2	1	0	0	3	1	0	0
Z		-13	-5	-5	-5	-1	-2	-3	0	0	0

Tableau 2			0	0	0	0	0	0	-1	-1	-1
Base	Cb	P0	P1	P2	P3	P4	P5	P6	P7	P8	P9
P1	0	1	1	0.5	0.5	0.5	0	0	0	0	0.5
P8	-1	4	0	1.5	2.5	-0.5	2	0	0	1	-0.5
P7	-1	4	0	1	0	-1	0	3	1	0	-1
Z		-8	0	-2.5	-2.5	1.5	-2	-3	0	0	2.5

Tableau 3			0	0	0	0	0	0	-1	-1	-1
Base	Cb	P0	P1	P2	P3	P4	P5	P6	P7	P8	P9
P1	0	1	1	0.5	0.5	0.5	0	0	0	0	0.5
P8	-1	4	0	1.5	2.5	-0.5	2	0	0	1	-0.5
P6	0	1.33	0	0.333	0	-0.333	0	1	0.333	0	-0.333
Z		-4	0	-1.5	-2.5	0.5	-2	0	1	0	1.5

Tableau 4			0	0	0	0	0	0	-1	-1	-1
Base	Cb	P0	P1	P2	P3	P4	P5	P6	P7	P8	P9
P1	0	0.2	1	0.2	0	0.6	-0.4	0	0	-0.2	0.6
P3	0	1.6	0	0.6	1	-0.2	0.8	0	0	0.4	-0.2
P6	0	1.333	0	0.333	0	-0.333	0	1	0.333	0	-0.333
Z		0	0	0	0	0	0	0	1	1	1

Tableau 1			3	1	3	0	0	0
Base	Cb	P0	P1	P2	P3	P4	P5	P6
P1	3	0.2	1	0.2	0	0.6	-0.4	0
P3	3	1.6	0	0.6	1	-0.2	0.8	0
P6	0	1.333	0	0.333	0	-0.333	0	1
Z		5.4	0	1.4	0	1.2	1.2	0

The optimal solution value is Z = 5.4
X1 = 0.2
X2 = 0
X3 = 1.6
X4 = 0
X5 = 0
X6 = 1.3333333333333

Herein I used simplex method to derive optimal solution, I am not 100% sure whether this optimum solution is right but I did my best.