The Simplex Method

The Simplex Method
In this chapter, you will learn how to solve linear programs. This will give you insights into
what SOLVER and other commercial linear programming software packages actually do. Such an
understanding can be useful in several ways. For example, you will be able to identify when a
problem has alternate optimal solutions (SOLVER never tells you this: it always give you only one
optimal solution). You will also learn about degeneracy in linear programming and how this could
lead to a very large number of iterations when trying to solve the problem.
7.1 Linear Programs in Standard Form
Before we start discussing the simplex method, we point out that every linear program can be
converted into \standard" form
Max c1x1 + c2x2 + : : :+ cnxn
subject to a11x1 + a12x2 + : : :+ a1nxn = b1
: : : : : : : : :
am1x1 + am2x2 + : : :+ amnxn = bm
x1 0; : : :xn 0
where the objective is maximized, the constraints are equalities and the variables are all nonnega-
tive.
This is done as follows:
If the problem is min z, convert it to max 􀀀z.
If a constraint is ai1x1+ai2x2+: : :+ainxn bi, convert it into an equality constraint by adding
a nonnegative slack variable si. The resulting constraint is ai1x1+ai2x2+: : :+ainxn+si = bi,
where si 0.
If a constraint is ai1x1 + ai2x2 + : : : + ainxn bi, convert it into an equality constraint by
subtracting a nonnegative surplus variable si. The resulting constraint is ai1x1+ai2x2+: : :+
ainxn 􀀀 si = bi, where si 0.
If some variable xj is unrestricted in sign, replace it everywhere in the formulation by x0
j 􀀀x00
j ,
where x0
j 0 and x00
j 0.
87
88 CHAPTER 7. THE SIMPLEX METHOD
Example 7.1.1 Transform the following linear program into standard form.
Min 􀀀2x1 +3x2
x1 􀀀3x2 +2x3 3
􀀀x1 +2x2 2
x1 urs; x2 0; x3 0
Let us rst turn the objective into a max and the constraints into equalities.
Max 2x1 􀀀3x2
x1 􀀀3x2 +2x3 +s1 = 3
􀀀x1 +2x2 􀀀s2 = 2
x1 urs; x2 0; x3 0 s1 0 s2 0
The last step is to convert the unrestricted variable x1 into two nonnegative variables: x1 =
x0
1 􀀀 x00
1.
Max 2x0
1 􀀀2x00
1 􀀀3x2
x0
1 􀀀x00
1 􀀀3x2 +2x3 +s1 = 3
􀀀x0
1 +x00
1 +2x2 􀀀s2 = 2
x0
1 0; x00
1 0; x2 0; x3 0 s1 0 s2 0
7.2 Solution of Linear Programs by the Simplex Method
For simplicity, in this course we solve \by hand" only the case where the constraints are of the
form and the right-hand-sides are nonnegative. We will explain the steps of the simplex method
while we progress through an example.
Example 7.2.1 Solve the linear program
max x1 +x2
2x1 +x2 4
x1 +2x2 3
x1 0; x2 0
First, we convert the problem into standard form by adding slack variables x3 0 and x4 0.
max x1 +x2
2x1 +x2 +x3 = 4
x1 +2x2 +x4 = 3
x1 0; x2 0 x3 0; x4 0
Let z denote the objective function value. Here, z = x1 + x2 or, equivalently,
z 􀀀 x1 􀀀 x2 = 0:
Putting this equation together with the constraints, we get the following system of linear equa-
tions.
z 􀀀x1 􀀀x2 = 0 Row 0
2x1 +x2 +x3 = 4 Row 1
x1 +2x2 +x4 = 3 Row 2
(7.1)
7.2. SOLUTION OF LINEAR PROGRAMS BY THE SIMPLEX METHOD 89
Our goal is to maximize z, while satisfying these equations and, in addition, x1 0, x2 0,
x3 0, x4 0.
Note that the equations are already in the form that we expect at the last step of the Gauss-
Jordan procedure. Namely, the equations are solved in terms of the nonbasic variables x1, x2.
The variables (other than the special variable z) which appear in only one equation are the basic
variables. Here the basic variables are x3 and x4. A basic solution is obtained from the system of
equations by setting the nonbasic variables to zero. Here this yields
x1 = x2 = 0 x3 = 4 x4 = 3 z = 0:
Is this an optimal solution or can we increase z? (Our goal)
By looking at Row 0 above, we see that we can increase z by increasing x1 or x2. This is
because these variables have a negative coe cient in Row 0. If all coe cients in Row 0 had been
nonnegative, we could have concluded that the current basic solution is optimum, since there would
be no way to increase z (remember that all variables xi must remain 0). We have just discovered
the rst rule of the simplex method.
Rule 1 If all variables have a nonnegative coe cient in Row 0, the current basic solution is
optimal.
Otherwise, pick a variable xj with a negative coe cient in Row 0.
The variable chosen by Rule 1 is called the entering variable. Here let us choose, say, x1 as our
entering variable. It really does not matter which variable we choose as long as it has a negative
coe cient in Row 0. The idea is to pivot in order to make the nonbasic variable x1 become a basic
variable. In the process, some basic variable will become nonbasic (the leaving variable). This
change of basis is done using the Gauss-Jordan procedure. What is needed next is to choose the
pivot element. It will be found using Rule 2 of the simplex method. In order to better understand
the rationale behing this second rule, let us try both possible pivots and see why only one is
acceptable.
First, try the pivot element in Row 1.
z 􀀀x1 􀀀x2 = 0 Row 0
2x1 +x2 +x3 = 4 Row 1
x1 +2x2 +x4 = 3 Row 2
This yields
z 􀀀1
2x2 +1
3x3 = 2 Row 0
x1 +1
2x2 +1
2x3 = 2 Row 1
3
2x2 􀀀1
2x3 +x4 = 1 Row 2
with basic solution x2 = x3 = 0 x1 = 2 x4 = 1 z = 2:
Now, try the pivot element in Row 2.
z 􀀀x1 􀀀x2 = 0 Row 0
2x1 +x2 +x3 = 4 Row 1
x1 +2x2 +x4 = 3 Row 2
This yields
90 CHAPTER 7. THE SIMPLEX METHOD
z +x2 +x4 = 3 Row 0
􀀀3x2 +x3 􀀀2x4 = 􀀀2 Row 1
x1 +2x2 +x4 = 3 Row 2
with basic solution x2 = x4 = 0 x1 = 3 x3 = 􀀀2 z = 3:
Which pivot should we choose? The rst one, of course, since the second yields an infeasible
basic solution! Indeed, remember that we must keep all variables 0. With the second pivot, we
get x3 = 􀀀2 which is infeasible. How could we have known this ahead of time, before actually
performing the pivots? The answer is, by comparing the ratios Right Hand Side
Entering Variable Coe cient in
Rows 1 and 2 of (7.1). Here we get 4
2 in Row 1 and 3
1 in Row 2. If you pivot in a row with minimum
ratio, you will end up with a feasible basic solution (i.e. you will not introduce negative entries in
the Right Hand Side), whereas if you pivot in a row with a ratio which is not minimum you will
always end up with an infeasible basic solution. Just simple algebra! A negative pivot element
would not be good either, for the same reason. We have just discovered the second rule of the
simplex method.
Rule 2 For each Row i, i 1, where there is a strictly positive \entering variable coe cient",
compute the ratio of the Right Hand Side to the \entering variable coe cient". Choose the pivot
row as being the one with MINIMUM ratio.
Once you have idendi ed the pivot element by Rule 2, you perform a Gauss-Jordan pivot. This
gives you a new basic solution. Is it an optimal solution? This question is addressed by Rule 1, so
we have closed the loop. The simplex method iterates between Rules 1, 2 and pivoting until Rule
1 guarantees that the current basic solution is optimal. That's all there is to the simplex method.
After our rst pivot, we obtained the following system of equations.
z 􀀀1
2x2 +1
3x3 = 2 Row 0
x1 +1
2x2 +1
2x3 = 2 Row 1
3
2x2 􀀀1
2x3 +x4 = 1 Row 2
with basic solution x2 = x3 = 0 x1 = 2 x4 = 1 z = 2:
Is this solution optimal? No, Rule 1 tells us to choose x2 as entering variable. Where should
we pivot? Rule 2 tells us to pivot in Row 2, since the ratios are 2
1=2 = 4 for Row 1, and 1
3=2 = 2
3 for
Row 2, and the minimum occurs in Row 2. So we pivot on 3
2x2 in the above system of equations.
This yields
z +1
3x3 +1
3x4 = 7
3 Row 0
x1 +2
3x3 􀀀1
3x4 = 5
3 Row 1
x2 􀀀1
3x3 +2
3x4 = 2
3 Row 2
with basic solution x3 = x4 = 0 x1 = 5
3 x2 = 2
3 z = 7
3:
Now Rule 1 tells us that this basic solution is optimal, since there are no more negative entries
in Row 0.
All the above computations can be represented very compactly in tableau form.