Min Ctx
Subject to
Ax ≤ b
x ≥ 0
where, as ever
A∈ Mmxn, rank(A)=m, b∈Rm, C∈Rn
Subject to
Ax ≤ b
x ≥ 0
where, as ever
A∈ Mmxn, rank(A)=m, b∈Rm, C∈Rn
Note at first, thar this ploblem is not written in standard form (see section , The simplex Algorithm)
If you want to see a two phase method complete example click here.
We have seen at section Simplex Pivot element how to pass from a Linear programming problem to it standard form by slack variables use.
The problem is, as we have seen, to find an identity mxm submatrix of A for starting simplex algorithm, wich can be not easy.
For this, we will apply the called two-phase method consisting of the following. Essentialy whose steps are in resume:
Two-phase method overview
Phase 1
1) We look for an identity submatrix of dimension mxn within the total matrix A, once the slack variables are added, it will be necessary as much m artificial new artificial variables to start the algorithm.
In spite of being a reduntant, we will introduce m new artificial variablesm so we add a complete matrix mxm to the matrix A. With this we do not alter the set of extreme points of the original problem, and at the most we add any new step to the first phase. What we gain is to remove the complexity of distinguishing between original, slack and artificial variables at the time of going from the first to the second phase.
Most clear: b> In theory, less than m columas should be added since the original matrix together with the slack variables usually provide enough columns of the identity sub-Matrix. What we do here is that if we have to add a single artificial variable, then we add the full m. Why? Because we think that although it adds some more dimensions to the problem, it reduces its practicle complexity.
2) Change the original objective function for one that has all zeros except for last m components having the value 1 (ie, vector C = (0, .., n-times ..., 0, 1, .., m-times ..., 1)
3) Start the algorithm with this problem until to take one of these cases:
3a) We reached the optimal solution if zero: this means that artificial variables have left of basis, in this case we can move to phase 2 of the method.
3b) If we reached the optimal solution finite non-zero: The original problem has no solution.
Phase 2
Eliminate artificial variables, and continue algorithm, by:
1) Take the original objective function C
2) Take the m-firsts columns of the A matrix
3) Continue the algorithm with these changes until reach one of the 4 possible outputs of the problem.
The idea of phase 1 is to remove the artificial variables from the basis and get the trivial solution for the exthended problem. At this case, we can to pass to phase-two by eliminating artificial vars.
We will see in this section an example of the two phase method and how to handle artificial and slack variables. An even more complete is here.