Find a Starting Point (Phase I).

At each iteration of the simplex method, the algorithm starts at one vertex of the feasible region and moves along an edge to the next vertex. Since the simplex method works from vertex to vertex, the simplex method must start at a vertex of the feasible region. The feasible region is the set of points that satisfies all of the constraints.

Vertex solutions correspond to basic solutions. Let us first describe the concept of a basis and how to find a basic solution.

**Minimize:
**-3x

**subject to:**

- x
_{1}+x_{2}- 1x_{3}+ 0x_{4}= 25 - x
_{1}+x_{2}+ 0x_{3}+ 1x_{4}= 50 - x 0

where x_{3} is a surplus variable for constraint 1, and x_{4} is a
slack variable for constraint 2.

Trial and error might be fine if the linear program you are solving is small. (x_{1}
= 50 and x_{3} = 25 works for the above problem.) However, if your linear program
has 8000 variables and 20000 constraints, it will be much harder to guess a first feasible
solution. Luckily, there are mechanical steps one can use to find the first feasible
solution.

Before we begin, there are some facts we need to consider from linear algebra. Consider
the system of equations formed by the constraints. We can write it out in *Ax = b*
form.

A =

1 | 1 | -1 | 0 |

1 | 1 | 0 | 1 |

x =

x_{1} |

x_{2} |

x_{3} |

x_{4} |

b =

25 |

50 |

Notice that in this system there are 2 equations and 4 variables, more variables than equations. As a result, there are an infinite number of solutions to this system. Actually, any point in the feasible region is a solution.

We are interested in vertices of the feasible region, and these solutions correspond to
basic solutions of the linear system. When a system *Ax
= b* has *m* equations and *n* unknowns with *m* *n*, we may select any *m
x m nonsingular submatrix* from *A.* This submatrix, *B,* is called a
basis matrix, and the solution of the system, *B x = b,* is called a basic
solution. The other *n - m* variables are set to zero. The variables that are in
the basis are basic variables. Similarly, variables
that are not in the basis are called nonbasic
variables.

To find an initial basic solution, we need to find a subset of the columns where we can
easily solve for the solution, *x.* Some columns are obvious choices for this
initial basis. Since slack variables only have one number in the column, it is easy to
solve for the corresponding value of *x.* If the right-hand side value is positive,
we include this slack variable in the basis. Similarly, we include surplus variables in
the basis whose right-hand side values are negative (then the value of *x* will be
positive). Deciding on the other columns is not as easy.

To simplify choosing the additional columns to enter the basis, we will expand the problem by adding artificial variables to the problem. Their only purpose is to help in finding the initial basis and will be discarded after the initial basis has been determined. We add an artificial variable to every constraint that did not have an acceptable slack or surplus variable. If the right-hand side value is positive, the artificial variable is added to the constraint. If negative, it is subtracted from the constraint.

**Minimize:
**-3x

**subject to:**

x_{1}+x_{2} - 1x_{3} + 0x_{4} + x_{5} = 25

x_{1}+x_{2} + 0x_{3} + 1x_{4} + 0x_{5}= 50

x 0

It is now easy to form an initial basis where we can easily solve for the solution
vector *x.*

x_{4} = 50

x_{5} = 25

Even though we have an initial basis for the linear program, it is in terms of artificial variables. In order for the initial basis to be useful, it needs to be in terms of the original variables.

We divide the simplex method into two phases.

- Phase 1 finds an initial feasible basic solution.
- Phase 2 finds an optimal feasible basic solution.

The steps of phase 1 and 2 are identical. They differ in the objective function and the variables included in the problem. The steps of phase 1 are performed until a basic solution is obtained without any artificial variables. Starting from the solution of phase 1, the artificial variables are removed from the problem and the objective value is restored and phase 2 continues to find an optimal solution.

The goal of Phase I is to remove the infeasibilities from the problem. Due to the way that we have formulated the problem, the artificial variables represent the infeasibilities. Hence, we want to drive the artificial variables to zero. We can accomplish this by changing the objective function. We set the coefficients of the artificial variables to 1 and the other variables to 0.

**Minimize:
**0x

If we obtain a minimum objective value of 0, the original problem is feasible and we have identified a starting basis. If it is not 0, the original problem is infeasible.

Continue to the next step.