15.093 - Recitation 3
Michael Frankovich and Shubham Gupta
September 25, 2009
1 Simplex Full Tableau method
Example 1. Solve the following problem using the full tableau method:
min
−x
1
− x
2
s.t. x
1
+ x
2
≤ 2
−x
1
+ x
2
≤ 0
x
1
, x
2
≥ 0
Solution. We first rewrite the problem in standard form using slack variables:
min −x
1
− x
2
s.t. x
1
+ x
2
+ s
1
= 2
−x
1
+ x
2
+ s
2
= 0
x
1
, x
2
, s
1
, s
2
≥ 0
For the initial tableau, we choose the slack variables to be the basic variables.
0 −1 −1 0 0
s
1
= 2 1
∗
1 1 0
s
2
= 0 −1 1 0 1
The solution in this tableau is not optimal because we have negative reduced costs. Select
x
1
as the entering variable. Then we have θ
∗
= 2, and s
1
will leave the basis. The next
tableau is:
2 0 0 1 0
x
1
= 2 1 1 1 0
s
2
= 2 0 2 1 1
The solution in this tableau is optimal since all reduced costs are nonnegative. Notice
however, that there is a nonbasic variable with zero reduced cost, which indicates that
there may be another optimal solution. Let’s see what happens if we go back and choose
x
2
as the entering variable instead of x
1
.
Again, here is the initial tableau:
1
Thanks Allison Chang for previous notes.
1
0 −1 −1 0 0
s
1
= 2 1 1 1 0
s
2
= 0 −1 1
∗
0 1
If x
2
enters the basis, then θ
∗
= 0 and s
2
leaves. This is a case in which degeneracy
causes the simplex method to choose the same basic feasible solution (with different basis
of course):
0 −2 0 0 1
s
1
= 2 2
∗
0 1 −1
x
2
= 0 −1 1 0 1
The solution is not optimal, and we choose x
1
to enter the basis. Then θ
∗
= 1 and s
1
leaves the basis. The next tableau is:
2 0 0 1 0
x
1
= 1 1 0 1/2 −1/2
x
2
= 1 0 1 1/2 1/2
So we have found the other optimal solution, and we can see that ¯c
4
= 0 again indicates
that the solution may not be unique.
What if the objective function is x
1
? The initial tableau is:
0 1 0 0 0
s
1
= 2 1 1 1 0
s
2
= 0 −1 1 0 1
This solution is already optimal and we have ¯c
2
= 0. However, the θ
∗
= 0, which means
we do not have multiple optimal solutions in this case. �
Example 2. Solve the following linear programming problem by full tableau simplex.
min −15x
1
− 13x
2
s.t. 7x
1
+ 6x
2
84≤
7x
1
+ 3x
2
63≤
−x
1
+ x
2
≥ −4
x
1
2x
2
2− ≤
x
1
≥ 0, x
2
≥ 0
Solution. First put the problem in standard form:
min −15x
1
− 13x
2
s.t. 7x
1
+ 6x
2
+s
1
= 84
7x
1
+ 3x
2
+s
2
= 63
x
1
− x
2
+s
3
= 4
x
1
− 2x
2
+s
4
= 2
x
1
, x
2
, s
1
, s
2
, s
3
, s
4
≥ 0
For the initial tableau, we choose the slack variables as basic variables:
2
0 −15 −13 0 0 0 0
s
1
= 84 7 6 1 0 0 0
s
2
= 63 7 3 0 1 0 0
s
3
= 4 1 −1 0 0 1 0
s
4
= 2 1
∗
−2 0 0 0 1
Not optimal: x
1
enters the basis and s
4
leaves.
30 0 −43 0 0 0 15
s
1
= 70 0 20 1 0 0 −7
s
2
= 49 0 17 0 1 0 −7
s
3
= 2 0 1
∗
0 0 1 −1
x
1
= 2 1 −2 0 0 0 1
Still not optimal: x
2
enters and s
3
leaves.
116 0 0 0 0 43 −28
s
1
= 30 0 0 1 0 −20 13
s
2
= 15 0 0 0 1 −17 10
∗
x
2
= 2 0 1 0 0 1 −1
x
1
= 6 1 0 0 0 2 −1
Almost done: s
4
enters and s
2
leaves.
158
s
1
=
21
2
s
4
=
3
2
x
2
=
7
2
x
1
=
15
2
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
28
10
−
13
10
1
10
1
10
1
10
−
23
5
21
10
∗
−
17
10
−
7
10
3
10
0
0
1
0
0
181
s
3
= 5
s
4
= 10
x
2
= 7
x
1
= 6
0 0
46
21
−
1
21
0
0 0
10
21
−
13
21
1
0 0
17
21
−
20
21
0
0 1
1
3
−
1
3
0
1 0 −
1
7
2
7
∗
0
0
0
1
0
0
182
s
3
= 18
s
4
= 30
x
2
= 14
s
2
= 21
1
6
13
6
10
3
7
6
7
2
0
0
0
1
0
13
6
1
6
1
3
1
6
−
1
2
0
0
0
0
1
0
1
0
0
0
0
0
1
0
0
And finally...
Our final solution is (x
1
, x
2
, s
1
, s
2
, s
3
, s
4
) = (0, 14, 0, 21, 18, 30).
If we draw the feasible region of the original problem, we will find that the simplex
method traverses through every extreme point before it hits the optimal one. However,
if at the first pivot, we choose x
2
to enter, then after one pivot, we are done! �
3
�
2 Exercise
While solving a standard form problem, we arrive at the following tableau, with x
3
, x
4
and x
5
being the basic variables:
-10 δ -2 0 0 0
4 -1 η 1 0 0
1 α -4 0 1 0
β γ 3 0 0 1
The entries α, β, γ, δ, η are unknown parameters. For each one of the following state-
ments, find some parameter values that will make the statement true.
a) The current solution is optimal and there are multiple optimal bases.
b) The optimal cost is
−∞.
c) The current solution is feasible but not optimal.
Solution.
a) Let β = 0, δ = 0, γ = 0, α > 0, η ≤ 0. With these choices, if we let x
2
enter the
basis, we obtain θ
∗
= β/3 = 0, and we stay at the same feasible solution. The
resulting reduced costs turn out to be nonnegative, implying optimality.
b) Let δ < 0, α ≤ 0, γ ≤ 0. If we attempt to bring x
1
into the basis, we see that the
optimal cost is
−∞.
c) Let β > 0. Nonoptimality is seen if we bring x
2
into the basis.
4
