Linear Programming: Chapter 2
The Simplex Method

Operations Research and Financial Engineering

Simplex Method

An Example. maximize subject to

−x1 + 3x2 − 3x3
3x1 − x2 − 2x3 ≤ 7
−2x1 − 4x2 + 4x3 ≤ 3 x1 − 2x3 ≤ 4
−2x1 + 2x2 + x3 ≤ 8
3x1
≤ 5 x1, x2, x3 ≥ 0.

Rewrite with slack variables maximize −x1 + 3x2 − 3x3

ζ =

subject to w1 w2 w3 w4 w5

=
=
=
=
=

7
3
4
8
5

−
+
−
+
−

3x1 + x2 + 2x3
2x1 + 4x2 − 4x3 x1 + 2x3
2x1 − 2x2 − x3
3x1

x1 , x 2 , x 3 , w 1 , w 2 , w 3 , w 4 , w 5 ≥

0.

Notes:
• This layout is called a dictionary.
• Setting x1 , x2 , and x3 to 0, we can read off the values for the other variables: w1 = 7, w2 = 3, etc. This specific solution is called a dictionary solution.
• Dependent variables, on the left, are called basic variables.
• Independent variables, on the right, are called nonbasic variables.

Dictionary Solution is Feasible

maximize

−x1 + 3x2 − 3x3

ζ =

subject to w1 w2 w3 w4 w5

=
=
=
=
=

7
3
4
8
5

−
+
−
+
−

3x1 + x2 + 2x3
2x1 + 4x2 − 4x3 x1 + 2x3
2x1 − 2x2 − x3
3x1

x1, x2, x3, w1, w2, w3 w4 w5 ≥

0.

Notes:
• All the variables in the current dictionary solution are nonnegative.
• Such a solution is called feasible.
• The initial dictionary solution need not be feasible—we were just lucky above.

Simplex Method—First Iteration

• If x2 increases, obj goes up.
• How much can x2 increase? Until w4 decreases to zero.
• Do it. End result: x2 > 0 whereas w4 = 0.
• That is, x2 must become basic and w4 must become nonbasic.
• Algebraically rearrange equations to, in the words of Jean-Luc Picard, ”Make it so.”
• This is a pivot.

A Pivot: x2 ↔ w4

becomes

Simplex Method—Second Pivot
Here’s the dictionary after the first pivot:

• Now, let x1 increase.
• Of the basic variables, w5 hits zero first.