18-07-2013, 04:53 PM
TWO PHASE simplex METHOD
TWO PHASE.pptx (Size: 140.96 KB / Downloads: 30)
Preview
When a basic feasible solution is not readily available, the two-phase simplex method may be used as an alternative to the big M method.
In the two-phase simplex method, we add artificial variables to the same constraints as we did in big M method. Then we find a basic feasible solution to the original LPP by solving the Phase I LPP.
At the completion of Phase I, we reintroduce the original LPP’s objective function and determine the optimal solution to the original LPP.
Algorithm
Step 1
Modify the constraints so that the right-hand side of each constraint is nonnegative. This requires that each constraint with a negative right-hand side be multiplied through by -1.
Step 2
Identify each constraint that is now an = or ≥ constraint. In step 3, we will add an the artificial variable to each of these constraints.
Step 3
Express the given LPP in it’s standard form and obtain an initial basic feasible solution(IBFS).
Step 4
Assign a cost (-1) to each A.V and a cost zero to all other variables in the objective function. Thus the new objective function is
Z* = 0.x1+0.x2+ . . . . . .+0.s1+0.s2+. . . – a1 – a2 - . . . .- an
Where, ai≥ 0
Remarks
As with the Big M method, the column for any artificial variable may be dropped from future table as soon as the artificial variable leaves the basis.
The Big M method and Phase I of the two -phase method make the same sequence of pivots. The two-phase method does not cause round off errors and other computational difficulties.