Minimize \( C^t x \)

Subject to:

\( \begin{matrix} Ax \le b \\ x\geqslant 0 \end{matrix} \)

Where as always:

\( A \in \mathbb M _{mxn}, \, rnk(A)=m ,\,\, \)\( b \in R^{m}, \, C \in R^{n}, \,\, n \geqslant m \)

Subject to:

\( \begin{matrix} Ax \le b \\ x\geqslant 0 \end{matrix} \)

Where as always:

\( A \in \mathbb M _{mxn}, \, rnk(A)=m ,\,\, \)\( b \in R^{m}, \, C \in R^{n}, \,\, n \geqslant m \)

Note first of all, that this problem 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 using slack variables.

The first problem is 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. To sum up:

### Two-phase method overview

**Phase 1**

1) We look for an identity submatrix of dimension mxm within the complete matrix A. If neccesary we add as much artificial as rows we have, this is m. So that to complete a identity mxm submatrix to start the algorithm.

With this we do not modify the extreme points set of the original problem, we have just added more dimensions to the feasible set polytope, in order to have a solution to start the algorightm at first phase.

2) Change the original objective function for other one wich have all values as zero except for those components in the new artifical variables where have 1 as (ie, vector C = (0, .., n-times ..., 0, 1, .., m-times (as much) ..., 1).

3) Start the algorithm with this problem until reach one of these cases:

3a) Reached the optimal solution = zero: this means artificial variables have left the basis: in this case we can move to phase 2 of two-phase method.

3b) If we reached the optimal solution finite non-zero: means that original problem has no solution.

**Phase 2**

Eliminate artificial variables, and continue algorithm just by:

1) Changing the original objective function C.

2) The basis is the remaining from the phase one.

3) Continue the algorithm with these changes until reach one of the 4 possible outputs known of the problem.

The idea of phase one is to remove the artificial variables from the basis and get the trivial solution (this is zero) for the extended problem. In this case, we can go on to phase two.

We will see in this section a complete example of the two phase method and how to handle artificial and slack variables. An even more complete is here.