Question

Q.3. ( maybe add, and maybe subtract from the original constraint) and then implement the two phase simplex method to solve the following problem. 10 points) Use artificial variables a1, a2, and a3 ( Max 10z 15 +12zs +20z4 +10s 4z1 + +43+3 > 0 1, 2, 3, 4,s 20

Answer 1

Phase-1

After introducing artificial variables $A_1, A_2, A_3$

$Max \:\:Z = - A_1 - A_2 - A_3$

subject to

$2 x_1 + 3 x_2 + x_3 + 5 x_4 + 3 x_5 + A_1 = 33$

$4 x_1 + x_2 + 4 x_3 - x_4 + x_5 + A_2 = 3$

$x_1 + x_2 - 3 x_3 - 2 x_4 + 3 x_5 + A_3 = 8 = 3$

Iteration-1		Cj	0	0	0	0	0	-1	-1	-1
B	CB	XB	x1	x2	x3	x4	x5	A1	A2	A3	MinRatio XB/x1
A1	-1	33	2	3	1	5	3	1	0	0	33/2=16.5
A2	-1	3	(4)	1	4	-1	1	0	1	0	3/4=0.75→
A3	-1	8	1	1	-3	-2	3	0	0	1	8/1=8
Z=-44		Zj	-7	-5	-2	-2	-7	-1	-1	-1
		Zj-Cj	-7↑	-5	-2	-2	-7	0	0	0

Negative minimum Zj-Cj is -7 and its column index is 1

Minimum ratio is 0.75 and its row index is 2

The pivot element is 4.

Entering =x1, Departing =A2,

$R_2 \leftarrow R_2 * \frac{1}{4}$

$R_1 \leftarrow R_1-2R_2$

$R_3 \leftarrow R_3- R_2$

Iteration-2		Cj	0	0	0	0	0	-1	-1
B	CB	XB	x1	x2	x3	x4	x5	A1	A3	MinRatio XB/x5
A1	-1	63/2	0	5/2	-1	11/2	5/2	1	0	(63/2)/(5/2)=63/5=12.6
x1	0	3/4	1	1/4	1	-1/4	1/4	0	0	(3/4)/(1/4)=3
A3	-1	29/4	0	3/4	-4	-7/4	(11/4)	0	1	(29/4)/(11/4)=29/11=2.6364→
Z=-155/4		Zj	0	-13/4	5	-15/4	-21/4	-1	-1
		Zj-Cj	0	-13/4	5	-15/4	-21/4↑	0	0

Negative minimum Zj-Cj is -21/4 and its column index is 5.

Minimum ratio is 2.6364 and its row index is 3.

The pivot element is 11/4.

$R_3 \leftarrow R_ 3 * \frac{4}{11}$

$R_1 \leftarrow R_ 1- \frac{5}{2}R_3$

$R_2 \leftarrow R_ 2- \frac{1}{4}R_3$

Iteration-3		Cj	0	0	0	0	0	-1
B	CB	XB	x1	x2	x3	x4	x5	A1	MinRatio XB/x4
A1	-1	274/11	0	20/11	29/11	(78/11)	0	1	(274/11) / (78/11)=137/39=3.5128→
x1	0	1/11	1	2/11	15/11	-1/11	0	0	---
x5	0	29/11	0	3/11	-16/11	-7/11	1	0	---
Z=-274/11		Zj	0	-20/11	-29/11	-78/11	0	-1
		Zj-Cj	0	-20/11	-29/11	-78/11↑	0	0

Negative minimum Zj-Cj is -78/11 and its column index is 4.

Minimum ratio is 3.5128 and its row index is 1

The pivot element is 78/11.

$R_1 \leftarrow R_ 1 * \frac{11}{78}$

$R_2 \leftarrow R_ 2 +R_1* \frac{1}{11}$

$R_3 \leftarrow R_ 3+R_1* \frac{7}{11}$

Iteration-4		Cj	0	0	0	0	0
B	CB	XB	x1	x2	x3	x4	x5	MinRatio
x4	0	137/39	0	10/39	29/78	1	0
x1	0	16/39	1	8/39	109/78	0	0
x5	0	190/39	0	17/39	-95/78	0	1
Z=0		Zj	0	0	0	0	0
		Zj-Cj	0	0	0	0	0

Since all  $Zj-Cj \geq 0$

Hence, optimal solution is arrived

$x_1=\frac{16}{36},\:\:x_2=0,\:\:x_3=0,\:\:x_4=\frac{137}{39},\:\:x_5=\frac{190}{39}$

$Max\:\: Z=0$

Phase-2

we eliminate the artificial variables and change the objective function for the original,

$Max \:\:Z=10x_1+15x_2+12x_3+20x_4+10x_5$

Iteration-1		Cj	10	15	12	20	10
B	CB	XB	x1	x2	x3	x4	x5	MinRatio XB/x2
x4	20	137/39	0	10/39	29/78	1	0	(137/39 )/ (10/39)=137/10=13.7
x1	10	16/39	1	(8/39)	109/78	0	0	(16/39) / (8/39)=2→
x5	10	190/39	0	17/39	-95/78	0	1	(190/39) / (17/39)=190/17=11.1765
Z=1600/13		Zj	10	150/13	120/13	20	10
		Zj-Cj	0	-45/13↑	-36/13	0	0

Negative minimum Zj-Cj is -45/13 and its column index is 2.

Minimum ratio is 2 and its row index is 2

The pivot element is 8/39.

$R_2 \leftarrow R_ 2* \frac{39}{ 8}$

$R_1 \leftarrow R_1-R_ 2* \frac{10}{ 39}$

$R_3 \leftarrow R_3-R_ 2* \frac{17}{ 39}$

Iteration-2		Cj	10	15	12	20	10
B	CB	XB	x1	x2	x3	x4	x5	MinRatio
x4	20	3	-5/4	0	-11/8	1	0
x2	15	2	39/8	1	109/16	0	0
x5	10	4	-17/8	0	-67/16	0	1
Z=130		Zj	215/8	15	525/16	20	10
		Zj-Cj	135/8	0	333/16	0	0

Since all $Zj-Cj \geq 0$

Hence, optimal solution is arrived

${\color{Red} x_1=0,\:\:\:x_2=2,\:\:\:x_3=0,\:\:\:x_4=3,\:\:\:x_5=4}$

${\color{Red} Max \:\;Z=130}$