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:
-3x1 -5x2 + 0x3 + 0x4
subject to:
where x3 is a surplus variable for constraint 1, and x4 is a slack variable for constraint 2.
Trial and error might be fine if the linear program you are solving is small. (x1 = 50 and x3 = 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 =
| x1 |
| x2 |
| x3 |
| x4 |
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:
-3x1 -5x2 + 0x3 + 0x4 + 0x5
subject to:
x1+x2 - 1x3 + 0x4 + x5 = 25
x1+x2 + 0x3 + 1x4 + 0x5= 50
x 0
It is now easy to form an initial basis where we can easily solve for the solution vector x.
x4 = 50
x5 = 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.
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:
0x1 +0x2 + 0x3 + 0x4 + 1x5
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.