Linear programming and the two phase method

[catcherintherye]

what exactly is the point of the two phase method? I have in my notes that 'if you have a program (P)

maximise $$xc_T x >= 0 , Ax<=b,$$but b not > 0, that we use the two phase method for to find a B.F.S to start the simplex algorithm. But then the notes go on to say that we use the method to solve a minimization problem.

 

[ansrivas]

The basic idea is that if one cannot readily identify a bfs for the original LP problem then one extends the LP (by adding more variables) so that a bfs can be readily identified.

Now the extended is problem is solved as an LP. The extension is such that is the initial LP was feasible then the optimal solution of the extended LP has all the extended vaibale zero (big M value in the objective function is the reason). Now we have a bfs for the initial problem and is used to start the simplex routine for the initial problem.

 

[cyeokpeng]

To put it simply, the main advantage of the two-phase Simplex method is:
in LP problems with equality in their constraints, and >= constraints (which usually occurs in a minimization problem),
we need to use big M cost coefficient in the objective function for introduction of artificial variables.
In the computer environment, how big should this value of M be? 1000000? 9999999? largest possible real number in the OS? We don't know unless we know the relative magnitude of the numbers in the problem. How are we going to program this in the Simplex algorithm with 0% logic error?

So, the two-phase method cleverly avoid this big M problem, by first considering only the artificial variables contribution to the objective function, do the Simplex until optimality is found. Then the second phase is to introduce the contribution of the decision variables back to the objective function, and do Simplex algorithm from there to reach optimality. In this way, we avoid the big M calculations!