Linear Programming: Simplex Method

Management Science

Eunji Kim
eunjikim@cau.ac.kr

College of Business Administration, CAU

Summary of Model Formulation Steps 2

Step 1 : Define the decision variables

Step 2 : Define the objective function

Step 3 : Define the constraints

Model Formulation: A Maximization 3

Beaver Creek Pottery Company

Complete Model:

Maximize Z = $40x1 + $50x2 Objective function

subject to: 1x1 + 2x2  40

4x1 + 3x2  120 constraints

x1 , x 2  0

Where x1, x2 is the number of

Decision variables
mugs and bowls, respectively
Terminology 4

▪ Solution: A set of values for the decision variables

▪ Feasible solution: A solution for which all of the constraints in the model are
satisfied

▪ Optimal solution: A feasible solution where the objective function reaches its
maximum (or minimum) value – for example, the most profit or the least cost.

Feasible solution Optimal solution

Solution
Infeasible solution
Different types of LPs 5

▪ Feasible LPs: having at least a feasible solution

▪ Infeasible LPs: no feasible solution

▪ Unbounded LPs: value of objective function increases infinitely

Unique optimal solution
Feasible
Multiple optimal solutions
LP Infeasible

Unbounded

▪ Quiz: Try to develop an LP with one or two variables for each of the
flowing three properties.
Limitation of Graphical
Methods 6
 Graphical Solution of LP 7

▪ Graphical methods provide visualization of how a solution for a

linear programming problem is obtained.

Maximize Z = $40x1 + $50x2

subject to: 1x1 + 2x2  40
4x1 + 3x2  120
x1, x2  0
An Example: McDonalds 8

▪ What would be a good diet at McDonalds?

▪ Suppose that we wanted to design a good 1 week diet at McDonalds.

What would we do?

▪ What data would we need?

▪ Decision variables?

▪ Objective function?

▪ Constraints?
What would be a good diet at McDonalds? 9

▪ A simpler problem
• Objective: Minimize the cost of a meal
• Constraints
• between 600 and 900 calories
• less than 50% of daily sodium (2300 mg per day)
• fewer than 40% of the calories are from fat
• at least 30 grams of protein.
• fractional meals permitted.

• Data
What would be a good diet at McDonalds? 10

▪ LP for McDonalds
• Decision variables: the number of menu
• H (Hamburger), B (Big Mac), M (McChicken), C (Caesar salad), R (French Fries)

• Formulation
Total cost
(variable definition)
Total calories
Fat calories
Protein

1170 Sodium
Non-negativity
What would be a good diet at McDonalds? 11

▪ This model has 5 decision variables. How can we solve this model?
• Graphical method?
• Simplex method?

Total cost
(variable definition)
Total calories
Fat calories
Protein

1170 Sodium
Non-negativity

Can we draw the feasible region of this model?

Beyond 2d… 12
Beyond 2d… (1) Graphical Method 13

▪ When the problem contains more than 2 decision variables…

Product 1

Product 2

Product 3
Pros and Cons of Graphical Method 14

▪ Pros
• Intuitive

▪ Cons
• Bothersome when the number of constraints increases
• Limited to the problems containing only two decision variables

▪ In real world, most of the problems have more than 2 decision

variables.

▪ We need a more efficient way to solve linear programming models!

Beyond 2d… (2) Simplex Method 15

▪ Simplex Method
• Mathematical procedure to solve LP
• Invented by George B. Dantzig
• One of the most important development in optimization
in the last 100 years
• It is based on Gaussian elimination operations.
Simplex Method 16
LP Model Formulation: A Maximization 17

Complete Linear Programming Model:

Maximize Z = $40x1 + $50x2

subject to: 1x1 + 2x2  40

4x2 + 3x2  120
x1, x2  0
Simplex Method: How to 18

1. Check if the LP is in a standard form

2. Create slack variables to convert inequalities to equations

3. Create an LP tableau from the LP

4. Repeat the following steps until no more positive entries in the z-

row (except -z)
A. Find pivot column
B. Find pivot row
C. Pivoting
LP in Standard Form 19

▪ LP in standard form has constraints that satisfy:

• All variables on the left-hand side
• A number on the right-hand side

Max/min z = c1x1 + c2x2 + ... + cnxn

subject to:
a11x1 + a12x2 + ... + a1nxn (≤, =, ≥) b1
a21x1 + a22x2 + ... + a2nxn (≤, =, ≥) b2
:
am1x1 + am2x2 + ... + amnxn (≤, =, ≥) bm

xj = decision variables
cj = objective function coefficients
bi = resource levels
aij = constraint coefficients
Slack variables 20

▪ Introduce slack variables to transform inequalities to equations

Introducing slack variables

max z = 40x1 + 50x2
s.t. 1x1 + 2x2 + s1 = 40
4x1 + 3x2 + s2 = 120
x1, x2  0

▪ To apply the simplex method, the LP must satisfy all of the following:
LP tableau 21

▪ Create an LP tableau by placing the systems of equations into a

matrix.

max z = 40x1 + 50x2

s.t. 1x1 + 2x2 + s1 = 40
4x1 + 3x2 + s2 = 120

LP tableau

-z x1 x2 s1 s2 RHS
-z +40x1+ 50x2 = 0 1 40 50 0 0 = 0
0 1 2 1 0 = 40
0 4 3 0 1 = 120
Terminologies 22

▪ When an LP tableau is given,

-z x1 x2 s1 s2 RHS
1 40 50 0 0 = 0 z-row
0 1 2 1 0 = 40
0 4 3 0 1 = 120

the identity matrix

• Basic variables: the variables corresponding to the identity matrix. {-z, s1, s2}
• Non-basic variables: the remaining variables. {x1, x2}
• Basic feasible solution (BFS) is the unique solution obtained by setting the
non-basic variables to 0. z=0, x1=0, x2=0, s1=40, s2=120
Same problem, different basic variables 23

▪ Basic variables and Non-basic variables

Basic -z x1 x2 s1 s2 RHS
Var.
-z 1 40 50 0 0 = 0
Initial BFS
s1 0 1 2 1 0 = 40
s2 0 4 3 0 1 = 120
z=0, x1=0, x2=0, s1=40, s2=120

Basic -z x1 x2 s1 s2 RHS
Var.
-z 1 15 0 -25 0 = -1000
Another BFS x2 0 1/2 1 1/2 0 = 20
s2 0 5/2 0 -3/2 1 = 60
z=1000, x1=0, x2=40, s1=0, s2=24
A. Find the pivot column 24

▪ Find the greatest positive entry in the z-row (except -z column).

• In this tableau, there are four entries: 40, 50, 0, 0
• Pivot column is the column with the greatest positive entry in the z-row
(except -z column).

Basic -z x1 x2 s1 s2 RHS
Var.
-z 1 40 50 0 0 = 0
s1 0 1 2 1 0 = 40
s2 0 4 3 0 1 = 120

pivot column
B. Find the pivot row 25

▪ The smallest non-negative ratio determines the pivot row.

• Divide the RHS column value by the pivot column value in the same row
(except z-row and rows with negative RHS value).
• Pivot row is the row having the smallest non-negative ratio.

Basic -z x1 x2 s1 s2 RHS Min. Ratio

Var. Test
-z 1 40 50 0 0 = 0
pivot
s1 0 1 2 1 0 = 40 40/2=20
row
s2 0 4 3 0 1 = 120 120/3=40

pivot column
C. Pivoting 26

▪ Make the pivot column identical to the unit vector with 1 at the pivot
row by applying elementary row operations.

Basic -z x1 x2 s1 s2 RHS
Var. z=0,
x1=0,
-z 1 40 50 0 0 = 0
x2=0,
s1 0 1 2 1 0 = 40 s1=40,
s2 0 4 3 0 1 = 120 s2=120

Pivoting

Basic -z x1 x2 s1 s2 RHS z=1000,

Var.
x1=0,
-z 1 15 0 -25 0 = -1000 x2=20,
x2 0 1/2 1 1/2 0 = 20 s1=0,
0 5/2 0 -3/2 1 = 60
s2=60
s2
Pivoting: How to 27

1. Divide the pivot row by the pivot coefficient.

• Then, we can obtain “1” in the intersection of pivot row and pivot column.

Basic -z x1 x2 s1 s2 RHS
Var.
-z 1 40 50 0 0 = 0
s1 0 1 2 1 0 = 40
s2 0 4 3 0 1 = 120

Multiply
Basic -z x1 x2 s1 s2 RHS by 1/2
Var.
-z 1 40 50 0 0 = 0
0 1/2 1 1/2 0 = 20
s2 0 4 3 0 1 = 120
Pivoting: How to 28

2. To obtain zeros for all rest entries in the pivot column, add
multiples of the pivot row to the rest rows.
• Then, the pivot column becomes a unit vector.

Basic -z x1 x2 s1 s2 RHS
Var.
Subtract 50 times
-z 1 40 50 0 0 = 0
0 1/2 1 1/2 0 = 20
s2 0 4 3 0 1 = 120
Subtract 3 times

Basic -z x1 x2 s1 s2 RHS
Var.
-z 1 15 0 -25 0 = -1000 Pivoting
x2 0 1/2 1 1/2 0 = 20 finished
s2 0 5/2 0 -3/2 1 = 60
Entering and Exiting Variables 29

▪ After pivoting, the basic variable in the pivot row is changed from s1
to x2.
• s1 and x2 is called exiting and entering variables.

Basic -z x1 x2 s1 s2 RHS
Var.
-z 1 40 50 0 0 = 0
Exiting 0 1 2 1 0 = 40
s1
variable
s2 0 4 3 0 1 = 120

Pivoting

Basic -z x1 x2 s1 s2 RHS
Var.
-z 1 15 0 -25 0 = -1000
Entering x2 0 1/2 1 1/2 0 = 20
variable
s2 0 5/2 0 -3/2 1 = 60
LP tableau after pivoting 30

▪ Check if there are no more positive entries in the z-row (except -z)
• If yes, stop and read the results.
• If no, repeat steps A (select pivot column), B (select pivot row), and C
(pivoting) to the tableau.

Basic -z x1 x2 s1 s2 RHS
Var.
-z 1 15 0 -25 0 = -1000
x2 0 1/2 1 1/2 0 = 20
s2 0 5/2 0 -3/2 1 = 60

In this tableau, a positive entry exists in the x1 column.

Thus, repeat steps A~C.
A Find the pivot column 31

▪ Find the greatest positive entry in the z-row (except -z column).

• In this tableau, there are four entries: 15, 0, -25, 0
• Pivot column is the column with the greatest positive entry in the z-row
(except -z column).

Basic -z x1 x2 s1 s2 RHS
Var.
-z 1 15 0 -25 0 = -1000
x2 0 1/2 1 1/2 0 = 20
s2 0 5/2 0 -3/2 1 = 60

pivot column
B. Find the pivot row 32

▪ The smallest non-negative ratio determines the pivot row.

• Divide the RHS column value by the pivot column value in the same row
(except z-row and rows with negative RHS value).
• Pivot row is the row having the smallest non-negative ratio.

Basic -z x1 x2 s1 s2 RHS Min. Ratio

Var. Test
-z 1 15 0 -25 0 = -1000
x2 0 1/2 1 1/2 0 = 20 20/(1/2)=40
pivot
s2 0 5/2 0 -3/2 1 = 60 60/(5/2)=24 row

pivot column
C. Pivoting 33

▪ Make the pivot column identical to the unit vector with 1 at the pivot
row by applying elementary row operations.

Basic -z x1 x2 s1 s2 RHS
Var. z=1000,
x1=0,
-z 1 15 0 -25 0 = -1000
x2=20,
x2 0 1/2 1 1/2 0 = 20 s1=0,
s2 0 5/2 0 -3/2 1 = 60 s2=60

Pivoting

Basic -z x1 x2 s1 s2 RHS z=1360,

Var.
x1=24,
-z 1 0 0 -16 -6 = -1360 x2=8,
x2 0 0 1 4/5 -1/5 = 8 s1=0,
0 1 0 -3/5 2/5 = 24
s2=0
x1
Procedure finished 34

▪ There are no more positive entries in the z-row (except -z), in which
case we would have reached the optimal solution.
Basic -z x1 x2 s1 s2 RHS
Var.
-z 1 0 0 -16 -6 = -1360
x2 0 0 1 4/5 -1/5 = 8
x1 0 1 0 -3/5 2/5 = 24

Optimal solution:
z=1360, x1=24, x2=8, s1=0, s2=0
Simplex Method: How to 35

1. Check if the LP is in a standard form

2. Create slack variables to convert inequalities to equations

3. Create an LP tableau from the LP

4. Repeat the following steps until no more positive entries in the z-

row (except -z)
A. Find pivot column
B. Find pivot row
C. Pivoting
Exercise 36

▪ Linpro Limited, a manufacturing enterprise, produces two products,

namely product A and product B. Both products are manufactured
from the same raw material and processed by the same machine.
The company wants to determine what combination of product A
and product B must be produced in order to obtain maximum profit.
• The available machine capacity is 600 hours and 10,000 kilogram of raw
materials are available.
• The production of one unit of product A utilizes 30 minutes of machine time
while one unit of product B takes one hour to produce.
• To produce one unit of product A, 12.5 kg of raw material is required whereas
10 kg is required for one unit of product B.
• The marginal income of product A, of which a maximum of 700 units can be
sold, amounts to 4 per unit. Product B has a marginal income of 6 per unit.

▪ Formulate a linear programming model for the above problem and

hence find the optimal solution by using the simplex method.
Solution 37

▪ LP model formulation
Solution 38

▪ LP in standard form
Solution 39

▪ Initial simplex tableau

Basic -z x1 x2 s1 s2 s3 RHS
Var.
-z 1 4 6 0 0 0 = 0
s1 0 0.5 1 1 0 0 = 600
s2 0 12.5 10 0 1 0 = 10000
s3 0 1 0 0 0 1 = 700

Initial BFS:
z=0, x1=0, x2=0, s1=600, s2=10000, s3=700
Solution 40

▪ Final simplex tableau

Basic -z x1 x2 s1 s2 s3 RHS
Var.
-z 1 0 0 -4.67 -0.13 0 = -4130
x2 0 0 1 1.67 -0.067 0 = 333
x1 0 1 0 -1.33 0.13 0 = 533
s3 0 0 0 1.33 -0.13 1 = 167

Optimal solution:
z=4130, x1=533, x2=333, s1=0, s2=0, s3=167
Geometry and visualization of
LPs 41
Feasible Region of LP 42

▪ What does the feasible region of an LP look like?

Corner points 43

▪ Corner points of the feasible region

• A point that is not the midpoint of two other points of the feasible region

Where are the corner points of the following feasible regions?

Corner points 44

▪ Generally, the optimal solution is one of the corner points.

Max Z=4x+3y
s.t.
2x+4y ≤ 40
4x+2y ≤ 36
3x-1y ≤ 20
1x+0y ≤ 8
x, y ≥ 0

Which corner point

will be the optimal?

Z=4x+3y
Corner points 45

▪ Generally, the optimal solution is one of the corner points.

Corner points 46

▪ Generally, the optimal solution is one of the corner points.

Simplex Method in 3D 47

▪ Visual examples

Some 3-dimensional feasible region examples…

Polyhedron of simplex
algorithm in 3D
Example: Corner points in Pottery example 48

▪ The feasible region has 4 corner points.

Maximize Z = $40x1 + $50x2

subject to: 1x1 + 2x2  40
4x1 + 3x2  120
x1, x2  0
x1 = 0 bowls
x2 = 0 mugs
Z = $0
Simplex Method and Corner Points 49

▪ Initial LP tableau and its basic feasible solution (BFS)

Basic -z x1 x2 s1 s2 RHS
Var.
-z 1 40 50 0 0 = 0
s1 0 1 2 1 0 = 40
s2 0 4 3 0 1 = 120

BFS: z=0, x1=0, x2=0,

s1=40, s2=120

Maximize Z = $40x1 + $50x2

subject to: 1x1 + 2x2  40
4x1 + 3x2  120
x1, x2  0
x1 = 0 bowls
x2 = 0 mugs This corner point is suboptimal because an adjacent
Z = $0 corner point has a better objective value.
Simplex Method and Corner Points 50

▪ Second LP tableau and its basic feasible solution (BFS)

Basic -z x1 x2 s1 s2 RHS
Var.
-z 1 15 0 -25 0 = -1000
x2 0 1/2 1 1/2 0 = 20
s2 0 5/2 0 -3/2 1 = 60

BFS: z=1000, x1=0,

x2=20, s1=0, s2=60

Maximize Z = $40x1 + $50x2

subject to: 1x1 + 2x2  40
4x1 + 3x2  120
x1, x2  0
x1 = 0 bowls
x2 = 0 mugs This corner point is suboptimal because an adjacent
Z = $0 corner point has a better objective value.
Simplex Method and Corner Points 51

▪ Third LP tableau and its basic feasible solution (BFS)

Basic -z x1 x2 s1 s2 RHS
Var.
-z 1 0 0 -16 -6 = -1360
x2 0 0 1 4/5 0 = 8
x1 0 1 0 -3/5 2/5 = 24

BFS: z=1360, x1=8,

x2=24, s1=0, s2=0
(optimal)

Maximize Z = $40x1 + $50x2

subject to: 1x1 + 2x2  40
4x1 + 3x2  120
x1, x2  0
x1 = 0 bowls
x2 = 0 mugs This corner point is optimal because no adjacent corner
Z = $0 point has a better objective value.
Exercise 52
Gemstone processing company 53

▪ Two types of gemstone products: ruby and jade

▪ Gemstones requires time for gathering and smoothing. Unit profit

and time constraints information are provided below:

Ruby Jade Resources

Gem gathering time 2 days 4 days 40 days
Gem smoothing 4 days 2 days 6 days
Profit (in $1000) 4 3

▪ Upper and lower bounds for demand

• Upper bound on the total demand for ruby: 8 units
• Lower bound on the total demand for jade: 3 times ruby production - 20

▪ Determine production amount to maximize profit

2d LP example 54

▪ A two variable LP example

• x:ruby, y: jade

maximize z = 4x + 3y

Gem gathering time z = 2x + 4y 40

Gem smoothing time z = 4x + 2y 36
Lower bound for amethyst z = 3x - 1y 20
Upper bound for ruby z = 1x + 0y 8
Non-negativity
Feasible region 55

▪ A two variable LP example maximize

• Add constraint 1 (Gem gathering time)

(1)
Feasible region 56

▪ A two variable LP example maximize

• Add constraint 2 (Gem smoothing time)

(2)

(1)
Feasible region 57

▪ A two variable LP example maximize

• Add constraint 3 (Lower bound for amethyst)

(2)

(1)

(3)
Feasible region 58

▪ A two variable LP example maximize

• Add constraint 4 (Upper bound for ruby)

(4)
(2)

(1)

(3)
Terminology 59

▪ Redundant constraint maximize

(4)
(2)

A constraint is called
(1) redundant if deleting the
constraint does not increase
the size of the feasible region.

Which of the constraints

(3) (1)~(4) is redundant?
Feasible region 60

▪ A two variable LP example maximize

• We have now graphed the feasible region.

Feasible region

4x+3y=z
Exercise 61

▪ Apply the simplex method to the example below.

▪ Match each intermediate tableau to one corner point.

maximize

Feasible region

4x+3y=z
QnA