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) Add an identity submatrix to A matrix by adding m columns using artificial variables, ie, the matrix A is now m x(n + m) dimensions. This allows us after to start the algorithm.

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.