USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Two Phase Method

To overcome the drawback of Big-M method, two phase method has been framed. In the first phase an auxiliary LP Problem is formulated as follows: Minimize T = Sum of artificial variables S/t, original constraints which is solved by simplex method. Here artificial variables act as decision variables. So Big-M is not required in the objective function. If T* = 0, then go to phase two calculations, else (T* ≠0) write the problem is infeasible. In phase two, the optimal table of phase one is considered with the following modifications: Delete the artificial variable's columns and incorporate the original objective function and also update the c8 values. Calculate zj - cj values. If all zj - cj ≥0, the current solution is optimal else go to the next iteration. Note. (a) Multiple solutions, if it exists, can be detected from the optimal table of phase two. (b) In phase I, the problem is always minimization type irrespective of the type of the original given objective function. Example 9. Using two phase method solve the following LPP : Minimize z = 10x1 + 3x2 S/t, x1+ 2x2 ≥ 3, x1+ 4x2≥4; x1 x2 ≥0 Solution. Standard form of the given LPP is Min.z =-Max. (- z = - 10x1 - 3x2 + O.s1 + O.s2 - Ma1 - Ma2) Sit, x1 + 2x2 - s1 + a 1 = 3, x 1 + 4x2 - s2 + a2 = 4, x 1, x2≥s1, s2, surplus ≥ a1, a2 artificial ≥ 0 Phase I Min T = a 1 + a2 = - Max (-T = 0. x1 + O.x2 + O.s1 + O.s2 - a1 - a2) S/t., x 1 + 2x2 - s1 + a1 = 3; x 1 + 4x2 - s2 +a2 = 4, x1, x 2, s1, s2, 1,' a 2 ::::: 0 Iteration 1.

 

Iteration 2.

Iteration 3.

Since all zj - cj ≥  0, the solution is optimal a1* = 0, a2* = 0 and T* = 0. Therefore we go to phase II calculations.

 

Phase II

 

Iteration 1.

Iteration 2.

Since all zj - cj ≥ 0, the current solution is opt imal.

 

x 1* = 0, x1 * = 2, z = 2

 

Example 10. Solve the following LPP by two phase method.

Maximize z = 2x1 + x2 - 3x3

S/t,       x1 + 2x2 + 2x3 ≥  12, 3x1 - 2x2 + 4x3 10

x1 0, x2 0, x3 0.

 

Solution.                     Set x2 = - x'2, x '2 ~ 0.

The standard fom1 of the given LPP is

 

Maximize = 2x1 - x'2 - 3x3 + O.s 1 + O.s2 - Ma 1

S/t,       x1 - 2x'2 + 2x3 - s1 + a1 = 12,

3x1 + 2x'2 + 4x3 + s2 = 10,

x1 ,  x'2  , x3 ≥ 0, s1 (surplus) ≥ O,s2 (slack) ≥ 0 and a 1 (artificial) ≥ 0.

 

Phase I.

 

Minimize T = a1 = - Max. (- T = O.x1 + O.x'2 + O.x3 + O.s1 + O.s2 - a1)

S/t,       x1 - 2x'2 + 2x3 - s1 + a1 = 12

3x1 + 2x'2 + 4x3 + s2 = 10

x1, x'2, x3, s1, s2, a1 ≥ 0.

 

Iteration 1.

Iteration 2.

Iteration 2.

Since all the elements in the key column are non-positive, we can not calculate min. ratio. Hence the given LPP is said to be unbounded.