Question

use the two-phase method and big.M method to solve the LPP: min z=x1-2x2 st: x1+x2>=2 -x1+x2>=1 x2<=3 x1,x2>=0 (two method!)

Answer 1

Given primal problem is :

Min z = x₁-2x₂

St : x₁+x₂ 2

-x₁+x₂ 1

x₂ 3

x₁,x₂ 0

TWO PHASE METHOD

After introducing x₃,x₄ as surplus variables and x₅ as slack variable and x₆, x₇ as artificial variables, the constraint equations become,

x₁+x₂-x₃+0x₄+0x₅+x₆+0x₇ = 2

-x₁+x₂+0x₃-x₄+0x₅+0x₆+x₇ = 1

x₂+0x₃+0x₄+x₅+0x₆+0x₇ = 3

x₁,x₂,x₃,x₄,x₅,x₆,x₇ 0

The auxiliary objective function to be minimized is given by

z' = 0x₁+0x₂+0x₃+0x₄+0x₅-x₆-x₇

Subject to the above system of equations.

Here x₁,x₂,x₃,x₄,x₅ are the legitimatevariables and x₆,x₇ are the artificial variables.

We then construct the simplex tableaux successively and obtain

Phase I :

			cj	0	0	0	0	0	-1	-1
cB	B	xB	b	a1	a2	a3	a4	a5	a6	a7
-1	a6	x6	2	1	1	-1	0	0	1	0
-1	a7	x7	1	-1	1	0	-1	0	0	1
0	a5	x5	3	0	1	0	0	1	0	0
				0	-2	1	1	0	0	0
-1	a6	x6	1	2	0	-1	1	0	1
0	a2	x2	1	-1	1	0	-1	0	0
0	a5	x5	2	1	0	0	1	1	0
				-2	0	1	-1	0	0
0	a1	x1	1/2	1	0	-1/2	1/2	0
0	a2	x2	3/2	0	1	-1/2	-1/2	0
0	a5	x5	3/2	0	-1	1/2	1/2	1
				0	0	0	0	0

Here z_j-c_j 0 in this iteration and Min z' = 0. No artificial variable appears in the final tableau of phase I. We then pass on to the phase II where the objective function to be minimized is z = x₁-2x₂+0x₃+0x₄+0x₅.

The last basis of phase I will be the starting basis for phase II and the last tableau of phase I will act as the initial tableau of phase II with a change only in the objective row containing the prices. c_B column being changed accordingly, there will be a new index row showing z_j-c_j in the initial tableau of phase II. As there is no artificial vector in the basis of the last tableau of phase I, we forget about it and delete this column.

Phase II :

			cj	1	-2	0	0	0
cB	B	xB	b	a1	a2	a3	a4	a5
1	a1	x1	1/2	1	0	-1/2	1/2	0
-2	a2	x2	3/2	0	1	-1/2	-1/2	0
0	a5	x5	3/2	0	-1	1/2	1/2	1
				0	0	1/2	3/2	0

Here z_j-c_j 0, for all j. The optimality condition has been satisfied. The optimal solution is :

x₁ = 1/2, x₂ = 3/2 and z_min = (1/2)-2*(3/2) = -5/2.