EMIS 3360: OR Models The Simplex Method 1

basic solution: For a system of linear equations Ax = b

with n variables and m ≤ n constraints, set n − m
non-basic variables equal to zero and solve the remaining
m basic variables.

basic feasible solutions (BFS): a basic solution that is

feasible. That is Ax = b, x ≥ 0 and x is a basic solution.

The feasible corner-point solutions to an LP are basic

feasible solutions. The Simplex Method uses the pivot
procedure to move from one BFS to an “adjacent” BFS
with an equal or better objective function value.
EMIS 3360: OR Models The Simplex Method 2

The Pivot Procedure

1. Choose a pivot element aij

2. Divide row i of the augmented matrix [A|b] by aij
   
ai`
 . . . a ij . . . a i` . . .   . . . 1 . . . aij
... 
   
 ... ... ... ... ...  →  ... ... ... ... ... 
   
   
. . . akj . . . ak` . . . . . . akj . . . ak` . . .

3. For each row k (other than row i), add −akj × row i to row k.
The element in row k, column ` becomes −akj × ai` + ak` .
   
ai` ai`
 ... 1 ... aij
...   ... 1 ... aij
... 
   
 ... ... ... ... ...  → 
 ... 
  ... ... ... ... 
   
akj ai`
. . . akj . . . ak` . . . . . . 0 . . . ak` − aij
...
EMIS 3360: OR Models The Simplex Method 3

Pivoting Example 1

Suppose we want to solve the following the LP with the Simplex method:

maximize x + 2y
s.t. x + y ≤4
x − 2y ≤2
−2x + y ≤2
x, y ≥0

First, we put the problem in standard form:

maximize x + 2y
s.t. x + y + s1 =4
x − 2y + s2 =2
−2x + y + s3 =2
x, y, s1 , s2 , s3 ≥0
EMIS 3360: OR Models The Simplex Method 4

Pivoting Example 1

Augmented matrix form of the constraints:

 
1 1 1 0 0 4
 
 1 −2 0 1 0 2 
 
−2 1 0 0 1 2

BFS 1:
Basic variables: BV = {s1 , s2 , s3 }
Non-basic variables: N B = {x, y}
Solution: s1 = 4, s2 = 2, s3 = 2, x = y = 0
Objective function value: x + 2y = 0 + 0 = 0
EMIS 3360: OR Models The Simplex Method 5

Pivoting Example 1

Pivot on row 3, column 1.

First, divide row 3 by −2:
   
1 1 1 1
0 0 4 1 1 0 0 4
   
 1 −2 0 1 0 2   2 
  →  1 −2 0 1 0 
−2 1 0 0 1 2 1 − 12 0 0 − 12 −1

Next, add −1 times row 3 to rows 1 and 2:

   
3 1
1 1 1 0 0 4 0 2 1 0 2 5
   
 1 2   − 32 1
3 
 −2 0 1 0  →  0 0 1 2 
1 − 12 0 0 − 12 −1 1 − 12 0 0 − 21 −1
EMIS 3360: OR Models The Simplex Method 6

Pivoting Example 1

 
3 1 3y s3
0 2 1 0 2 5 2 + s1 + 2 = 5
 
 0 − 32 1
3  3y s3
 0 1 2  ≡ − 2 + s2 + 2 = 3
y s3
1 − 12 0 0 − 12 −1 x − 2 − 2 = −1

BFS 2:

Basic variables: BV = {x, s1 , s2 }

Non-basic variables: N B = {y, s3 }
Solution: x = −1, s1 = 5, s2 = 3, y = s3 = 0
Objective function value: x + 2y = 0 + 0 = 0
Solution is infeasible since x < 0.
This BFS is said to be adjacent to the first one since it shares two of the three
basic variables.
EMIS 3360: OR Models The Simplex Method 7

Pivoting Example 1

Pivot on row 2, column 1.

Add −1 times row 2 to rows 1 and two times row 1 to row 3:
   
1 1 1 0 0 4 0 3 1 −1 0 2
   
 1 −2 0 1 0 2  →  1 −2 0 1 0 2 
   
−2 1 0 0 1 2 0 −3 0 2 1 6

 
0 3 1 −1 0 2 3y + s1 − s2 = 2
 
 1 2 
 −2 0 1 0  ≡ x − 2y + s2 = 2
0 −3 0 2 1 6 − 3y + 2s2 + s3 = 6

BFS 3:
Basic variables: BV = {x, s1 , s3 }
Non-basic variables: N B = {y, s2 }
Solution: x = 2, s1 = 2, s3 = 6, y = s2 = 0
Objective function value: x + 2y = 2 + 0 = 2
EMIS 3360: OR Models The Simplex Method 8

Pivoting Example 1

Pivot on row 3, column 2.

   
1 1 1 0 0 4
3 0 1 0 −1 2
   
 1 −2 0 1 0 2   6 
  →  −3 0 0 1 2 
−2 1 0 0 1 2 −2 1 0 0 1 2

 
3 0 1 0 −1 2 3x + s1 − s3 = 2
 
 −3 0 6 
 0 1 2  ≡ −3x + s2 + 2s3 = 6
−2 1 0 0 1 2 −2x + y + s3 = 2

BFS 4:
Basic variables: BV = {y, s1 , s2 }
Non-basic variables: N B = {x, s3 }
Solution: y = 2, s1 = 2, s2 = 6, x = s3 = 0
Objective function value: x + 2y = 0 + 4 = 4
EMIS 3360: OR Models The Simplex Method 9

Row-Zero Form of an LP
Standard form:

maximize x + 2y
s.t. x + y + s1 =4
x − 2y + s2 =2
−2x + y + s3 =2
x, y, s1 , s2 , s3 ≥0

Row-Zero form:

maximize z
s.t. z − x − 2y =0
x + y + s1 =4
x − 2y + s2 =2
−2x + y + s3 =2
x, y, s1 , s2 , s3 ≥0
EMIS 3360: OR Models The Simplex Method 10

• A system of linear equations is in canonical form if each equation

has a variable xj with a coefficient of 1 in that equation such that
the coefficient xj is 0 in all other equations.
• If an LP is in canonical form, then we can find a basic solution
by inspection.
• If an LP is in canonical form and all the constraints have
non-negative right-hand sides, then we can find a basic feasible
solution by inspection.
• If an LP is in Row-Zero form and the row 1, row 2, . . ., row m
constraints have non-negative right-hand sides,then we can find
BFS and its objective function variable by inspection.
EMIS 3360: OR Models The Simplex Method 11

Row-Zero Form BFS

Row-Zero form:

maximize z
s.t. z − x − 2y =0
x + y + s1 =4
x − 2y + s2 =2
− 2x + y + s3 =2
x, y, s1 , s2 , s3 ≥0

Basic variables: BV = {z, s1 , s3 , s2 }

Non-basic variables: N B = {x, y}
Solution: z = 0, s1 = 4, s2 = 2, s3 = 2, x = y = 0
Objective function value: z = x + 2y = 0 + 0 = 0
EMIS 3360: OR Models The Simplex Method 12

Row-Zero Form and Augmented Matrix

Row-Zero form:

maximize z
s.t. z − x − 2y =0
x + y + s1 =4
x − 2y + s2 =2
− 2x + y + s3 =2
x, y, s1 , s2 , s3 ≥0

Augmented Matrix:
 
1 −1 −2 0 0 0 0
 
 0 1 1 1 0 0 4 
 
 
 0 1 −2 0 1 0 2 
 
0 −2 1 0 0 1 2
EMIS 3360: OR Models The Simplex Method 13

Fundamental Steps of the Simplex Method

Is the current BFS Optimal?

Can we increase the value of z by increasing the value of
a non-basic variable?
If we increase x or y, we will have to increase z to satisfy
the constraint in Row 0, z − x − 2y = 0.
Which non-basic variable should we increase?
A one-unit increase in x will give us a one-unit increase
in z.
A two-unit increase in y will give us a two-unit increase
in z.
EMIS 3360: OR Models The Simplex Method 14

How much can we increase y?

• Row-1 constraint: x + y + s1 = 4
x + y + s1 = 4 ⇒ s1 = 4 − x − y
x = 0 ⇒ s1 = 4 − y
s1 ≥ 0 ⇒ y ≤ 4
• Row-2 constraint: x − 2y + s2 = 2
x − 2y + s2 = 2 ⇒ s2 = 2 − x + 2y
x = 0 ⇒ s2 = 2 + 2y
s2 ≥ 0 ⇒ y ≥ −1
• Row-3 constraint: −2x + y + s3 = 2
−2x + y + s3 = 2 ⇒ s3 = 2 + 2x − y
x = 0 ⇒ s3 = 2 − y
s3 ≥ 0 ⇒ y ≤ 2
We can increase y to 2 if we decrease s3 to 0 at the same
time.
EMIS 3360: OR Models The Simplex Method 15

To increase y and decrease s3 , we pivot on Row 3, Column 3

of the augmented matrix:
   
 1 −1 −2 0 0 0 0   1 −5 0 0 0 2 4 
   
 0 1 1 1 0 0 4   0 3 0 1 0 −1 2 
   
  →  
 0 1 −2 0 1 0 2   0 −3 0 0 1 2 6 
   
   
0 −2 1 0 0 1 2 0 −2 1 0 0 1 2

 
 1 −5 0 0 0 2 4  z − 5x + 2s3 = 4
 
 0 3 0 1 0 −1 2  3x + s1 − s3 = 2
 
  ≡
 0 −3 0 0 1 2 6  −3x + s2 + 2s3 = 6
 
 
0 −2 1 0 0 1 2 −2x + y + s3 = 2
EMIS 3360: OR Models The Simplex Method 16

Is the current BFS optimal?

 
 1 −5 0 0 0 2 4  z − 5x + 2s3 = 4
 
 0 3 0 1 0 −1 2  3x + s1 − s3 = 2
 
  ≡
 0 −3 0 0 1 2 6  −3x + s2 + 2s3 = 6
 
 
0 −2 1 0 0 1 2 −2x + y + s3 = 2

If we increase x we will have to increase z to satisfy the constraint in

row 0, z − 5x + 2s3 = 4. Therefore, the basis is might not be optimal.
Which non-basic variable should we increase?
A one-unit increase in x will give us a five-unit increase in z.
A one-unit increase in s3 will give us a two-unit decrease in z.
Increase x.
EMIS 3360: OR Models The Simplex Method 17

How much can we increase x?

• Row-1 constraint: 3x + s1 − s3 = 2
3x + s1 − s3 = 2 ⇒ s1 = 2 − 3x + s3
s3 = 0 ⇒ s1 = 2 − 3x
2
s1 ≥ 0 ⇒ x ≤ 3

• Row-2 constraint: −3x + s2 + 2s3 = 6

−3x + s2 + 2s3 = 6 ⇒ s2 = 6 + 3x − 2s3
s3 = 0 ⇒ s2 = 6 + 3x
s2 ≥ 0 ⇒ x ≥ −2 (we can increase s2 to compensate for any
increase in x)
• Row-3 constraint: −2x + y + s3 = 2
−2x + y + s3 = 2 ⇒ y = 2 + 2x − s3
s3 = 0 ⇒ y = 2 + 2x
y ≥ 0 ⇒ x ≥ −1
EMIS 3360: OR Models The Simplex Method 18

We can increase x to 23 if we decrease s1 to 0 at the same

time. x becomes basic and s1 becomes non-basic.

z x y s1 s2 s3
1 −5 0 0 0 2 4 (z)
0 3 0 1 0 −1 2 (s1 )
0 −3 0 0 1 2 6 (s2 )
0 −2 1 0 0 1 2 (y)

Pivot on column 2, the x column, row 1 (the only row

where s1 has a non-zero entry).
EMIS 3360: OR Models The Simplex Method 19

   
5 1 22
 1 −5 0 0 0 2 4   1 0 0 3
0 3 3 
   
 0 3 0 1 0 −1 2   0 1 0 1
0 − 13 2
   3 3
  →  
 0 −3 0 0 1 2 6   0 0 0 1 1 1 8 
   
   
2 1 10
0 −2 1 0 0 1 2 0 0 1 3
0 3 3

 
5 1 22
 1 0 0 3
0 3 3  z + 35 s1 + 13 s3 = 22
3
 
 0 1 0 1
0 − 31 2 x + 13 s1 − 13 s3 = 2
 3 3 3

 0 0 0
 ≡
 1 1 1 8 
 s1 + s2 + s3 = 8
 
2 1 10
0 0 1 3
0 3 3
y + 23 s1 + 13 s3 = 10
3
EMIS 3360: OR Models The Simplex Method 20

After the two pivots, the LP is now in the following form:

max z
s.t. z + 53 s1 + 13 s3 = 22
3

x + 13 s1 − 13 s3 = 2
3

s1 + s2 + s3 = 8
y + 23 s1 + 13 s3 = 10
3

x, y, s1 , s2 , s3 ≥ 0

The BFS z = 22
3 , x = 2
3, y =
10
3, s2 = 8, s1 = s3 = 0 is
optimal. Why?