Chapter 9

Linear Programming:
The Simplex Method

To accompany
Quantitative Analysis for Management, Tenth Edition,
by Render, Stair, and Hanna © 2008 Prentice-Hall,
Power Point slides created by Jeff Heyl © 2009 Prentice-Hall, Inc.
Inc.
 Learning Objectives
After completing this chapter, students will be able to:
1. Convert LP constraints to equalities with slack,
surplus, and artificial variables
2. Set up and solve LP problems with simplex
tableaus
3. Interpret the meaning of every number in a
simplex tableau
4. Recognize special cases such as infeasibility,
unboundedness, and degeneracy
5. Use the simplex tables to conduct sensitivity
analysis
6. Construct the dual problem from the primal
problem
© 2009 Prentice-Hall, Inc. 9–2
 Chapter Outline
1. Introduction
2. How to Set Up the Initial Simplex
Solution
3. Simplex Solution Procedures
4. The Second Simplex Tableau
5. Developing the Third Tableau
6. Review of Procedures for Solving
LP Maximization Problems
7. Surplus and Artificial Variables

© 2009 Prentice-Hall, Inc. 9–3

 Chapter Outline
8. Solving Minimization Problems
9. Review of Procedures for Solving
LP Minimization Problems
10. Special Cases

© 2009 Prentice-Hall, Inc. 9–4

 Introduction
 With only two decision variables it is possible to
use graphical methods to solve LP problems
 But most real life LP problems are too complex for
simple graphical procedures
 We need a more powerful procedure called the
simplex method
 The simplex method examines the corner points in
a systematic fashion using basic algebraic
concepts
 It does this in an iterative manner until an optimal
solution is found
 Each iteration moves us closer to the optimal
solution
© 2009 Prentice-Hall, Inc. 9–5
 Introduction
 Why should we study the simplex method?
 It is important to understand the ideas used to
produce solutions
 It provides the optimal solution to the decision
variables and the maximum profit (or
minimum cost)
 It also provides important economic
information
 To be able to use computers successfully and to
interpret LP computer printouts, we need to know
what the simplex method is doing and why

© 2009 Prentice-Hall, Inc. 9–6

 How To Set Up The Initial
Simplex Solution
 Let’s look at the Flair Furniture Company from
Chapter 7
 This time we’ll use the simplex method to solve
the problem
 You may recall

T = number of tables produced

C = number of chairs produced
and
Maximize profit = $70T + $50C (objective function)
subject to 2T + 1C ≤ 100 (painting hours constraint)
4T + 3C ≤ 240
(carpentry hours constraint)
T, C ≥ 0
(nonnegativity constraint) © 2009 Prentice-Hall, Inc. 9–7
 Converting the Constraints
to Equations
 The inequality constraints must be converted into
equations
 Less-than-or-equal-to constraints (≤) are
converted to equations by adding a slack variable
to each
 Slack variables represent unused resources
 For the Flair Furniture problem, the slacks are
S1 = slack variable representing unused hours
in the painting department
S2 = slack variable representing unused hours
in the carpentry department
 The constraints may now be written as
2T + 1C + S1 = 100
4T + 3C + S2 = 240
© 2009 Prentice-Hall, Inc. 9–8
 Converting the Constraints
to Equations
 If the optimal solution uses less than the
available amount of a resource, the unused
resource is slack
 For example, if Flair produces T = 40 tables
and
C = 10 chairs, the painting constraint will
be

2T + 1C + S1 = 100
2(40) +1(10) + S1 = 100
S1 = 10
 There will be 10 hours of slack, or unused
painting capacity © 2009 Prentice-Hall, Inc. 9–9
 Converting the Constraints
to Equations
 Each slack variable must appear in every
constraint equation
 Slack variables not actually needed for an
equation have a coefficient of 0
 So
2T + 1C + 1S1 + 0S2 = 100
4T + 3C +0S1 + 1S2 = 240
T, C, S1, S2 ≥ 0

 The objective function becomes

Maximize profit = $70T + $50C + $0S1 +
$0S2
© 2009 Prentice-Hall, Inc. 9 – 10
 Finding an Initial Solution
Algebraically
 There are now two equations and four
variables
 When there are more unknowns than
equations, you have to set some of the
variables equal to 0 and solve for the
others
 In this example, two variables must be set
to 0 so we can solve for the other two
 A solution found in this manner is called
a
basic feasible solution
© 2009 Prentice-Hall, Inc. 9 – 11
 Finding an Initial Solution
Algebraically
 The simplex method starts with an initial feasible
solution where all real variables are set to 0
 While this is not an exciting solution, it is a corner
point solution
 Starting from this point, the simplex method will
move to the corner point that yields the most
improved profit
 It repeats the process until it can further improve
the solution
 On the following graph, the simplex method starts
at point A and then moves to B and finally to C,
the optimal solution

© 2009 Prentice-Hall, Inc. 9 – 12

 Finding an Initial Solution
Algebraically
 Corner points C
for the Flair
100 –
Furniture
–
Company B = (0, 80)

Number of Chairs
80 –
problem 2T + 1C ≤ 100
–
60 –
–
40 – C = (30, 40)
–
20 –
4T + 3C ≤ 240
– D = (50, 0)
(0, 0) A | | |
0 20 | T
|–
Figure 9.1 40 60
80
© 2009 Prentice-Hall, Inc. 9 – 13
Number of Tables
 The First Simplex Tableau
 Constraint equations
 It simplifies handling the LP equations if we
put them in tabular form
 These are the constraint equations for the Flair
Furniture problem

QUANTITY
SOLUTION MIX T C S1 S2 (RIGHT-HAND SIDE)
S1 2 1 1 0 100

S2 4 3 0 1 240

© 2009 Prentice-Hall, Inc. 9 – 14

 The First Simplex Tableau
 The first tableau is is called a simplex tableau

ix

es
es
t

m
ni

bl
bl
u

n on

ns ria
ns ia
n r

n t
m ti
m e

m a

m n
m ar
lu it p

lu k v
lu uc

lu sta
lu l v
co rod

co lac
co rof

co on
co ea
R

C
S
P
P

Cj SOLUTION $70 $50 $0 $0 Profit per

S1 S2 QUANTITY unit row
MIX T C
$0 S1 2 1 1 0 100 Constraint
equation rows
$0 4 3 0 1 240
Gross
SZ2j $0 $0 $0 $0 $0
profit row
Cj - Zj $70 $50 $0 $0 $0
Net profit row
Table 9.1
© 2009 Prentice-Hall, Inc. 9 – 15
 The First Simplex Tableau
 The numbers in the first row represent the
coefficients in the first constraint and the
numbers in the second the second constraint
 At the initial solution, T = 0 and C = 0, so S1 = 100
and S2 = 240
 The two slack variables are the initial solution
mix
 The values are found in the QUANTITY column
 The initial solution is a basic feasible solution
T 0
0
=
SC1 100
S2 240
© 2009 Prentice-Hall, Inc. 9 – 16
 The First Simplex Tableau
 Variables in the solution mix, called the basis in
LP terminology, are referred to as basic variables
 Variables not in the solution mix or basis (value
of 0) are called nonbasic variables
 The optimal solution was T = 30, C = 40, S1 = 0,
and S2 = 0
 The final basic variables would be

T 30
C 40
=
S1
S
02
0
© 2009 Prentice-Hall, Inc. 9 – 17
 The First Simplex Tableau
 Substitution rates
 The numbers in the body of the tableau are the
coefficients of the constraint equations
 These can also be thought of as substitution
rates
 Using the variable T as an example, if Flair
were to produce 1 table (T = 1), 2 units of S1
and 4 units of S2 would have to be removed
from the solution
 Similarly, the substitution rates for C are 1 unit
of S1 and 3 units of S2
 Also, for a variable to appear in the solution
mix, it must have a 1 someplace in its column
and 0s in every other place in that column
© 2009 Prentice-Hall, Inc. 9 – 18
 The First Simplex Tableau
 Adding the objective function
 We add a row to the tableau to reflect the
objective function values for each variable
 These contribution rates are called Cj and
appear just above each respective variable
 In the leftmost column, Cj indicates the unit
profit for each variable currently in the solution
mix
Cj $70 $0

$50 QUANTITY
S2
$0 $0 0 100
$0 SOLUTION 1 240
MIX T C S1
© 2009 Prentice-Hall, Inc. 9 – 19
S1 2 1
1
S2 4 3
0
 The First Simplex Tableau
 The Zj and Cj – Zj rows
 We can complete the initial tableau by adding
two final rows
 These rows provide important economic
information including total profit and whether
the current solution is optimal
 We compute the Zj value by multiplying the
contribution value of each number in a column
by each number in that row and the jth column,
and summing

© 2009 Prentice-Hall, Inc. 9 – 20

 The First Simplex Tableau
 The Zj value for the quantity column provides the
total contribution of the given solution
Zj (gross profit) = (Profit per unit of S1)  (Number of units of
S1)
+ (profit per unit of S2)  (Number of units of
S2)
= $0  100 units + $0  240
units
= $0 profit

 The Zj values in the other columns represent the

gross profit given up by adding one unit of this
variable into the current solution
Zj = (Profit per unit of S1)  (Substitution rate in ©row 1)
2009 Prentice-Hall, Inc. 9 – 21

+ (profit per unit of S2)  (Substitution rate in row 2)

 The First Simplex Tableau
 Thus,
Zj (for column T) = ($0)(2) + ($0)(4) = $0
Zj (for column C) = ($0)(1) + ($0)(3) = $0
Zj (for column S1) = ($0)(1) + ($0)(0) = $0
Zj (for column S2) = ($0)(0) + ($0)(1) = $0

 We can see that no profit is lost by adding one

unit of either T (tables), C (chairs), S1, or S2

© 2009 Prentice-Hall, Inc. 9 – 22

 The First Simplex Tableau
 The Cj – Zj number in each column represents the
net profit that will result from introducing 1 unit of
each product or variable into the solution
 It is computed by subtracting the Zj total for each
column from the Cj value at the very top of that
variable’s column

COLUMN
T C S1 S2
Cj for column $70 $50 $0 $0
Zj for column 0 0 0 0
Cj – Zj for column $70 $50 $0 $0

© 2009 Prentice-Hall, Inc. 9 – 23

 The First Simplex Tableau
 Obviously with a profit of $0, the initial solution is
not optimal
 By examining the numbers in the Cj – Zj row in
Table 9.1, we can see that the total profits can be
increased by $70 for each unit of T and $50 for
each unit of C
 A negative number in the number in the Cj – Zj
row would tell us that the profits would decrease
if the corresponding variable were added to the
solution mix
 An optimal solution is reached when there are no
positive numbers in the Cj – Zj row

© 2009 Prentice-Hall, Inc. 9 – 24

 Simplex Solution Procedures

 After an initial tableau has been

completed, we proceed through a series of
five steps to compute all the numbers
needed in the next tableau
 The calculations are not difficult, but they
are complex enough that even the
smallest arithmetic error can produce a
wrong answer

© 2009 Prentice-Hall, Inc. 9 – 25

 Five Steps of the Simplex Method for
Maximization Problems
1. Determine the variable to enter the solution mix
next. One way of doing this is by identifying the
column, and hence the variable, with the largest
positive number in the Cj - Zj row of the preceding
tableau. The column identified in this step is
called the pivot column.
2. Determine which variable to replace. This is
accomplished by dividing the quantity column by
the corresponding number in the column selected
in step 1. The row with the smallest nonnegative
number calculated in this fashion will be replaced
in the next tableau. This row is often referred to as
the pivot row. The number at the intersection of
the pivot row and pivot column is the pivot
number.
© 2009 Prentice-Hall, Inc. 9 – 26
 Five Steps of the Simplex Method for
Maximization Problems
3. Compute new values for the pivot row. To do this,
we simply divide every number in the row by the
pivot column.
4. Compute the new values for each remaining row.
All remaining rows are calculated as follows:

(New row numbers) = (Numbers in old row)

Number above Corresponding number in

– or below x the new row, that is, the
pivot number row replaced in step 3

© 2009 Prentice-Hall, Inc. 9 – 27

 Five Steps of the Simplex Method for
Maximization Problems

5. Compute the Zj and Cj - Zj rows, as demonstrated

in the initial tableau. If all the numbers in the Cj - Zj
row are 0 or negative, an optimal solution has
been reached. If this is not the case, return to step
1.

© 2009 Prentice-Hall, Inc. 9 – 28

 The Second Simplex Tableau
 We can now apply these steps to the Flair
Furniture problem
Step 1. Select the variable with the largest positive
Cj - Zj value to enter the solution next. In this case,
variable T with a contribution value of $70.
Cj $70 $50 $0 $0
SOLUTION QUANTITY
MIX T C S1 (RHS)
$0 S1 S2 100
$0 S2 2 1 1 240
0
Zj $0
4 3 0
Cj - Zj total profit
1
$0 $0 $0
Table 9.2 $0
© 2009 Prentice-Hall, Inc. 9 – 29
$70 $50 $0 $0
Pivot column
 The Second Simplex Tableau
Step 2. Select the variable to be replaced. Either S1
or S2 will have to leave to make room for T in the
basis. The following ratios need to be calculated.
For the S1 row

100(hours of painting time available)

 50 tables
2(hours required per table)
For the S2 row

240(hours of carpentry time available)

 60 tables
4(hours required per table)
© 2009 Prentice-Hall, Inc. 9 – 30
 The Second Simplex Tableau
We choose the smaller ratio (50) and this determines
the S1 variable is to be replaced. This corresponds
to point D on the graph in Figure 9.2.
Cj $70 $0 $0
$50 SOLUTION QUANTITY
MIX T C S1 S2 (RHS)
$0 S1 2 1 1 0 100
$0 S2 4 3 0 1 240
Pivot number Pivot row
Zj $0 $0 $0 $0
$70 $0
$50 $0
Cj - Zj

$0
Table 9.3 Pivot column

© 2009 Prentice-Hall, Inc. 9 – 31

 The Second Simplex Tableau
Step 3. We can now begin to develop the second,
improved simplex tableau. We have to compute a
replacement for the pivot row. This is done by
dividing every number in the pivot row by the pivot
number. The new version of the pivot row is below.

2 1
1  0.5 1* 0.5 0 100
2 2 2  2 0 2  50

Cj SOLUTION MIX T C S1 S2 QUANTITY

$70 T 1 0.5 0.5 0 50

© 2009 Prentice-Hall, Inc. 9 – 32

 The Second Simplex Tableau
Step 4. Completing the rest of the tableau, the S2
row, is slightly more complicated. The right of the
following expression is used to find the left side.
Number in Number in Number Below Corresponding Number
New S2 Row = – 
Old S2 Row Pivot Number in the New T Row
0 4 (4)  (1)
= – (4)  (0.5)
1 3 (4) (0.5)

= –
(4)  (0)
–2 = 0
– (4)  (50)
1
= 1
40 Cj –
SOLUTION MIX T C S1 S2 QUANTITY
= $70 240
T – 1 0.5 0.5 0
50
$0 S2 0 1 –2 1
40 © 2009 Prentice-Hall, Inc. 9 – 33
 The Second Simplex Tableau
1
The T column contains and the S2 column
0
contains 10 , necessary conditions for variables
to
be in the solution. The manipulations of steps 3 and
4 were designed to produce 0s and 1s in the
appropriate positions.

© 2009 Prentice-Hall, Inc. 9 – 34

 The Second Simplex Tableau
Step 5. The final step of the second iteration is to
introduce the effect of the objective function. This
involves computing the Cj - Zj rows. The Zj for the
quantity row gives us the gross profit and the other
Zj represent the gross profit given up by adding
one unit of each variable into the solution.

Zj (for T column) = ($70)(1) + ($0)(0) = $70

Zj (for C column) = ($70)(0.5) + ($0)(1) = $35
Zj (for S1 column) = ($70)(0.5) + ($0)(–2) = $35
Zj (for S2 column) = ($70)(0) + ($0)(1) = $0
Zj (for total profit) = ($70)(50) + ($0)(40) =
$3,500
© 2009 Prentice-Hall, Inc. 9 – 35
 The Second Simplex Tableau
COLUMN
T C S1 S2
Cj for column $70 $50 $0 $0
Zj for column $70 $35 $35 $0
Cj – Zj for column $0 $0
$15 –$35

 Completed second simplex tableau

$0
Cj SOLUTION $70 $50 $0 QUANTITY
MIX T C S1 S2
$0 T 1 0.5 (RHS)
0 50
$0 0.5 1 40
SZ2 0
$70 1
$35 –
$35 $0 $3,500
j
2
Cj - Zj $0 $15 –$35 $0
Table 9.4
© 2009 Prentice-Hall, Inc. 9 – 36
 Interpreting the Second Tableau

 Current solution
 The solution point of 50 tables and 0 chairs
(T = 50, C = 0) generates a profit of $3,500. T is
a basic variable and C is a nonbasic variable.
This corresponds to point D in Figure 9.2.
 Resource information
 Slack variable S2 is the unused time in the
carpentry department and is in the basis. Its
value implies there is 40 hours of unused
carpentry time remaining. Slack variable S1 is
nonbasic and has a value of 0 meaning there is
no slack time in the painting department.

© 2009 Prentice-Hall, Inc. 9 – 37

 Interpreting the Second Tableau
 Substitution rates
 Substitution rates are the coefficients in the
heart of the tableau. In column C, if 1 unit of C
is added to the current solution, 0.5 units of
T and 1 unit of S2 must be given up. This is
because the solution T = 50 uses up all 100
hours of painting time available.
 Because these are marginal rates of
substitution, so only 1 more unit of S2 is
needed to produce 1 chair
 In column S1, the substitution rates mean that
if 1 hour of slack painting time is added to
producing a chair, 0.5 less of a table will be
produced
© 2009 Prentice-Hall, Inc. 9 – 38
 Interpreting the Second Tableau

 Net profit row

 The Cj - Zj row is important for two reasons
 First, it indicates whether the current solution
is optimal
 When there are no positive values in the
bottom row, an optimal solution to a
maximization LP has been reached
 The second reason is that we use this row to
determine which variable will enter the
solution next

© 2009 Prentice-Hall, Inc. 9 – 39

 Developing the Third Tableau
 Since the previous tableau is not optimal, we
repeat the five simplex steps
Step 1. Variable C will enter the solution as its Cj - Zj
value of 15 is the largest positive value. The C
column is the new pivot column.
Step 2. Identify the pivot row by dividing the number
in the quantity column by its corresponding
substitution rate in the C column.

50
For the T row :0.5  100
chairs
40
For the S2 row : 1  40
chairs © 2009 Prentice-Hall, Inc. 9 – 40
 Developing the Third Tableau
These ratios correspond to the values of C at points
F and C in Figure 9.2. The S2 row has the smallest
ratio so S2 will leave the basis and will be replaced
by C.
Cj $70 $50 $0 $0
SOLUTION
MIX T C S1 S2
$70 T 1 0.5 0.5 QUANTITY
0 50
$0 0 1 –2 1 40
S2 Pivot number Pivot row
Zj $70 $35 $35 $0 $3,500
Cj - Zj $0 $15 –$35 $0
Pivot column

Table 9.5
© 2009 Prentice-Hall, Inc. 9 – 41
 Developing the Third Tableau

Step 3. The pivot row is replaced by dividing every

number in it by the pivot point number
0
1
0 2 1 40
1 1  2 1 1 1  40
1
1

The new C row is

Cj SOLUTION MIX T C S1 S2 QUANTITY

$5 C 0 1 –2 1 40

© 2009 Prentice-Hall, Inc. 9 – 42

 Developing the Third Tableau
Step 4. The new values for the T row may now be
computed

Number in Number in Number above Corresponding number

= – 
new T row old T row pivot number in new C row
1 = 1 – (0.5)  (0)
0 = 0.5 – (0.5)  (1)
1.5 = 0.5 – (0.5)  (–2)
–0.5 = 0 – (0.5)  (1)
30 = 50 – (0.5)  (40)

Cj SOLUTION MIX T C S1 S2
QUANTITY
$70 T 1 0 1.5 –0.5 30
$50 C 0 1 –2 1 40

© 2009 Prentice-Hall, Inc. 9 – 43

 Developing the Third Tableau
Step 5. The Zj and Cj - Zj rows can now be calculated

Zj (for T column) = ($70)(1) + ($50)(0) =

$70 Zj (for C column) =
($70)(0) + ($50)(1) = $50 Zj (for S1 column)
= ($70)(1.5) + ($50)(–2)=
$5 Zj (for S2 column) = ($70)(–0.5) + ($50)(1)=
$15
Zj (for total profit) = ($70)(30) +COLUMN
($50)(40) =
$4,100 T C S1 S2
Cj for column $70 $50 $0 $0
And theZjnet profit per unit$70row is$50now
for column $5 $15
Cj – Zj for column $0 $0 –$5 –
$15
© 2009 Prentice-Hall, Inc. 9 – 44
 Developing the Third Tableau
 Note that every number in the Cj - Zj row is 0 or
negative indicating an optimal solution has been
reached
 The optimal solution is

T = 30 tables
C = 40 chairs
S1 = 0 slack hours in the painting department
S2 = 0 slack hours in the carpentry department
profit = $4,100 for the optimal solution

© 2009 Prentice-Hall, Inc. 9 – 45

 Developing the Third Tableau
 The final simplex tableau for the Flair Furniture
problem corresponds to point C in Figure 9.2

Cj $70 $50 $0 $0
SOLUTION
MIX T C S1 S2
$70 T 1 0 1.5 QUANTITY 30
–0.5
$50 C 0 1 –2 1 40
Zj $70 $50 $5 $15 $4,100
Cj - Zj $0 $0 –$5 –$15
Table 9.6

 Arithmetic mistakes are easy to make

 It is always a good idea to check your answer by going
back to the original constraints and objective function
© 2009 Prentice-Hall, Inc. 9 – 46
 Review of Procedures for Solving
LP Maximization Problems

I. Formulate the LP problem’s objective function

and constraints
II. Add slack variables to each less-than-or-equal-
to constraint and to the objective function
III. Develop and initial simplex tableau with slack
variables in the basis and decision variables set
equal to 0. compute the Zj and Cj - Zj values for
this tableau.
IV. Follow the five steps until an optimal solution
has been reached

© 2009 Prentice-Hall, Inc. 9 – 47

 Review of Procedures for Solving
LP Maximization Problems

1. Choose the variable with the greatest positive

Cj - Zj to enter the solution in the pivot column.
2. Determine the solution mix variable to be
replaced and the pivot row by selecting the row
with the smallest (nonnegative) ratio of the
quantity-to-pivot column substitution rate.
3. Calculate the new values for the pivot row
4. Calculate the new values for the other row(s)
5. Calculate the Zj and Cj - Zj values for this
tableau. If there are any Cj - Zj numbers greater
than 0, return to step 1. If not, and optimal
solution has been reached.

© 2009 Prentice-Hall, Inc. 9 – 48

 Surplus and Artificial Variables
 Greater-than-or-equal-to (≥) constraints are just as
common in real problems as less-than-or-equal-to
(≤) constraints and equalities
 To use the simplex method with these constraints,
they must be converted to a special form similar to
that made for the less-than-or-equal-to (≤)
constraints
 If they are not, the simplex technique is unable to
set up an initial solution in the first tableau
 Consider the following two constraints
Constraint 1: 5X1 + 10X2 + 8X3 ≥
210
Constraint 2: 25X1 + 30X2
= 900 © 2009 Prentice-Hall, Inc. 9 – 49
 Surplus and Artificial Variables
 Surplus variables
 Greater-than-or-equal-to (≥) constraints
require a different approach than the less-
than-or-equal-to (≤) constraints we have seen
 They involve the subtraction of a surplus
variable rather than the addition of a slack
variable
 The surplus variable tells us how much the
solution exceeds the constraint amount
 This is sometimes called negative slack

© 2009 Prentice-Hall, Inc. 9 – 50

 Surplus and Artificial Variables
 To convert the first constraint we subtract a
surplus variable, S1, to create an equality
Constraint 1rewritten : 5 X 1  10 X 2  8 X 3 
S1  210
 If we solved this for X1 = 20, X2 = 8, X3 = 5, S1 would
be
5 X 1  10 X 2  8 X 3  S1  210
5(20)  10(8)  8(5)  S1  210
100  80  40  S1  210
 S1  210
 220
S1  10
© 2009 Prentice-Hall, Inc. 9 – 51

surplus
units
 Surplus and Artificial Variables
 Artificial variables
 There is one more step in this process
 If a surplus variable is added by itself, it would
have a negative value in the initial tableau
where all real variables are set to zero
5(0)  10(0)  8(0)  S1  210
0  S1  210
S1 
210

 But all variables in LP problems must be

nonnegative at all times
© 2009 Prentice-Hall, Inc. 9 – 52
 Surplus and Artificial Variables
 To resolve this we add in another variable called
an artificial variable

Constraint 1completed : 5 X 1  10 X 2  8 X 3  S1  A1
 210

 Now X1, X2, X3, and S1 can all be 0 in the initial

solution and A1 will equal 210
 The same situation applies in equality constraint
equations as well

Constraint 2 rewritten : 25 X 1  30 X 2  A2  900

© 2009 Prentice-Hall, Inc. 9 – 53

 Surplus and Artificial Variables
 Artificial variables are inserted into equality
constraints so we can easily develop an initial
feasible solution
 When a problem has many constraint equations
with many variables, it is not possible to “eyeball”
an initial solution
 Using artificial variables allows us to use the
automatic initial solution of setting all the other
variables to 0
 Unlike slack or surplus variables, artificial
variables have no meaning in the
problem formulation
 They are strictly a computational tool, they will be
gone in the final solution
© 2009 Prentice-Hall, Inc. 9 – 54
 Surplus and Artificial Variables

 Surplus and artificial variables in the

objective function
 Both types of variables must be included in
the objective function
 Surplus variables, like slack variables,
carry a
$0 cost coefficient
 Since artificial variables must be forced out of
the solution, we assign an arbitrarily high
cost
 By convention we use the coefficient M (or –M
in maximization problems) which simply
represents a very large number
© 2009 Prentice-Hall, Inc. 9 – 55
 Surplus and Artificial Variables

 A problem with this objective function

Minimize cost  $5 X 1  $9 X 2  $7 X 3

And the constraint equations we saw before would

appear as follows:

Minimize cost = $5X1 + $9X2 + $7X3 + $0S1 + $MA1 + $MA2

subject to 5X1 + 10X2 + 8X3 – 1S1 + 1A1 + 0A2 =
210
25X1 + 30X2 + 0X3 + 0S1 +
0A1 + 1A2 = 900
© 2009 Prentice-Hall, Inc. 9 – 56
Solving Minimization Problems
 Once the necessary equations are
developed for a minimization problem, we
can use the simplex method to solve for
an optimal solution

© 2009 Prentice-Hall, Inc. 9 – 57

 The Muddy River Chemical
Corporation Example
 The Muddy River Chemical Corporation must
produce exactly 1,000 pounds of a special
mixture of phosphate and potassium for a
customer
 Phosphate costs $5 per pound and potassium $6
per pound
 No more than 300 pounds of phosphate can be
used and at least 150 pounds of potassium must
be used
 The company wants to find the least-cost blend of
the two ingredients

© 2009 Prentice-Hall, Inc. 9 – 58

 The Muddy River Chemical
Corporation Example
 The model formulation would be

Minimize cost = $5X1

+ $6X2 subject to X1 = 1,000 lb
+ X2 ≤ 300 lb
X1 X2 ≥
150 lb
X1, X2 ≥ 0
where
X1 = number of pounds of phosphate
X2 = number of pounds of potassium

© 2009 Prentice-Hall, Inc. 9 – 59

 The Muddy River Chemical
Corporation Example

 Graphical analysis
 Because there are only two decision variables,
we can plot the constraints and the feasible
region as shown in Figure 9.3
 Because X1 + X2 = 1,000 is an equality, the
optimal solution must lie on this line
 It must also lie between points A and B
because of the X1 ≤ 300 constraint
 It turns out the X2 ≥ 150 is redundant and
nonbinding
 The optimal corner point is point B (300, 700)
for a total cost of $5,700

© 2009 Prentice-Hall, Inc. 9 – 60

 The Muddy River Chemical
Corporation Example
X2
–
X1 ≤ 300
1,000 – A

800 –
B
600 –
X1 + X2 = 1,000
400 –

X2 ≥ 150
200 – F G H
100 –
0 |–E | D| | | |C
200 400 600 800 1,000 X1
Figure 9.3
© 2009 Prentice-Hall, Inc. 9 – 61
 The Muddy River Chemical
Corporation Example

 Rarely will problems be this simple

 The simplex method can be used to solve
much more complex problems
 In this example, the simplex method will
start at coroner point E, move to point F,
then G and finally to point B which is
the optimal solution

© 2009 Prentice-Hall, Inc. 9 – 62

 The Muddy River Chemical
Corporation Example
 Converting the constraints and objective
function
 The necessary artificial variables, slack
variables, and surplus variables need to be
added to the equations
 The revised model is

Minimize cost = $5X1 + $6X2 + $0S1 + $0S2 + $MA1 + $MA2

subject to 1X1 + 1X2 + 0S1 + 0S2 + 1A1 + 0A2 =
1,000 1X1 + 0X2 + 1S1 + 0S2 + 0A1 +
0A2 = 300
0X1 + 1X2 + 0S1 – 1S2
+ 0A1 + 1A2 = 150
X1, X2, S1, S2, A1, A2 © 2009 Prentice-Hall, Inc. 9 – 63

≥0
 Rules of the Simplex Method for
Minimization Problems
 Minimization problems are quite similar to the
maximization problems tackled earlier
 The significant difference is the Cj - Zj row
 We will now choose the variable with the
negative
Cj - Zj that gives the largest improvement
 We select the variable that decreases costs the
most
 In minimization problems, an optimal solution is
reached when all the numbers in the Cj - Zj are 0
or positive
 All other steps in the simplex method remain the
same
© 2009 Prentice-Hall, Inc. 9 – 64
 Steps for Simplex Minimization
Problems

1. Choose the variable with the greatest negative

Cj - Zj to enter the solution in the pivot column.
2. Determine the solution mix variable to be
replaced and the pivot row by selecting the row
with the smallest (nonnegative) ratio of the
quantity-to-pivot column substitution rate.
3. Calculate the new values for the pivot row
4. Calculate the new values for the other row(s)
5. Calculate the Zj and Cj - Zj values for this
tableau. If there are any Cj - Zj numbers less
than 0, return to step 1. if not, and optimal
solution has been reached.

© 2009 Prentice-Hall, Inc. 9 – 65

 First Simplex Tableau for the Muddy
River Chemical Corporation Example
 The initial tableau is set up in the same manner
as the in the maximization problem
 The first three rows are
 Note the costs for the artificial variables are $M
 We simply treat this as a very large number which
forces the artificial variables out of the solution
quickly

Cj SOLUTION MIX X1 X2 S1 S2 A1 A2
QUANTITY
$M A1 1 1 0 0 1 0
1,000
$0 S1 1 0 1 0 0 0
300
$M A2 0 1 0 –1 0 1 150
© 2009 Prentice-Hall, Inc. 9 – 66
 First Simplex Tableau for the Muddy
River Chemical Corporation Example
 The numbers in the Zj are computed by
multiplying the Cj column on the far left of the
table times the corresponding numbers in each
other column

Zj (for X1 column) = $M(1) + $0(1) + $M(0) =

Zj (for X2 column) = $M(1) $M
+ $0(0) + $M(1) = $2M
Zj (for S1 column) = + $0(1) + $M(0) =
$M(0)
Z j (for S2 column) = $0$0(0) + $M(–1) = –$M
+
$M(0)
Z j (for A1 column) = $M(1) + $0(0) + $M(0) =
Zj (for A2 column) = $M(0) $M+ $0(0) + $M(1) = $M
Zj (for total cost) = $M(1,000) + $0(300) + $M(150) =
$1,150M

© 2009 Prentice-Hall, Inc. 9 – 67

 First Simplex Tableau for the Muddy
River Chemical Corporation Example
 The Cj – Zj entires are determined as follows

COLUMN
X1 X2 S1 S2 A1 A2
Cj for column $5 $6 $0 $0 $M $M
Zj for column $M $2M $0 –$M $M $M
Cj – Zj for column –$M + $5 –$2M + $6 $0 $M $0 $0

© 2009 Prentice-Hall, Inc. 9 – 68

 First Simplex Tableau for the Muddy
River Chemical Corporation Example
 The initial solution was obtained by letting each
of the variables X1, X2, and S2 assume a value of 0
 The current basic variables are A1 = 1,000, S1 =
150, and A2 = 150
 The complete solution could be expressed in
vector form as

X1 0
X2 0
S1 300
=
S2 0
A1 1,000
A2 150

© 2009 Prentice-Hall, Inc. 9 – 69

 First Simplex Tableau for the Muddy
River Chemical Corporation Example
 The initial tableau

Cj $5 $6 $0 $0 $M $M
SOLUTION
X1 X2 S1 S2 A1 A2 QUANTITY
MIX
$M A1 1 1 0 0 1 0 1,000
$0 1 0 1 0 0 0 300
$M A2 0 1 0 –1 0 1 150
S1
Pivot number Pivot row
Zj $M $M $0 –$M $M $M $1,150M
Cj – Zj –$M + $5 –2M + $6 $0 $M $0 $0
Pivot column

Table 9.7

© 2009 Prentice-Hall, Inc. 9 – 70

 Developing the Second Tableau

 In the Cj – Zj row there are two entries with

negative values, X1 and X2
 This means an optimal solution does not
yet exist
 The negative entry for X2 indicates it has the will
result in the largest improvement, which means it
will enter the solution next
 To find the variable that will leave the solution, we
divide the elements in the quantity column by the
respective pivot column substitution rates

© 2009 Prentice-Hall, Inc. 9 – 71

 Developing the Second Tableau

1,000
For the A1 row  1  1,000
(this is an undefined ratio,
300
For the S1 row  0 so we ignore it)

(smallest quotient,
150
For the A2 row  1  150 indicating pivot row)

 Hence the pivot row is the A2 row and the pivot

number is at the intersection of the X2 column and
the A2 row

© 2009 Prentice-Hall, Inc. 9 – 72

 Developing the Second Tableau
 The entering row for the next tableau is found by
dividing each element in the pivot row by the pivot
number
(New row numbers) = (Numbers in old row)

Number above or Corresponding

– 
number below pivot number in newly
replaced row
A1 Row S1 Row
1 = 1 – (1)(0) 1=1–
(0)(0)
0 = 1 – (1)(1) 0=0–
(0)(1)
0 = 0 – (1)(0) 1=1–
(0)(0)
© 2009 Prentice-Hall, Inc. 9 – 73
1 = 0 – (1)(–1) 0=0–
(0)(–1)
1 = 1 – (1)(0) 0=0–
(0)(0)
–1 = 0 – (1)(1) 0=0–
(0)(1)
850 = 1,000 – (1)(150) 300 = 300 –
(0)(150)
 Developing the Second Tableau

 The Zj and Cj – Zj rows are computed next

Zj (for X1) = $M(1) + $0(1) + $6(0) =
$M Zj (for X2) = $M(0) + $0(0) + $6(1) =
$6 Zj (for S1) = $M(0) + $0(1) + $6(0) =
$0
Zj (for S2) = $M(1) + $0(0) + $6(–1) =
$M – 6
Zj (for A1) = $M(1) + $0(0) + $6(0) =
$M
Zj (for A2) X1 = $M(–1)
X2 + $0(0)
S1 + $6(1)
S2 = –A1 A2
Cj$M +6
for column $5 $6 $0 $0 $M $M
ZjZ j (for total cost) = $M(850) + $0(300) + $6(150) =
for column $M $6 $0 $M – 6 $M –$M + 6
Cj$850M + 900 –$M + $5 $0
– Zj for column $0 –$M + 6 $0 $2M – 6

COLUMN © 2009 Prentice-Hall, Inc. 9 – 74

 Developing the Second Tableau

 Second simplex tableau

Cj $5 $0 $M $M
SOLUTION
MIX X1
$6 X2 S2 A1 A2 QUANTITY
S1
$M A1 1 1 –1 850
$0
$0 S1 1 0 0 0 0 300
0
Pivot row
1 0
$6 X2 1 –1 0 1 150
Pivot number $850M +
Zj $M – 6 $M –$M + 6
$900
Cj – Zj 0 1 –$M + $6 $0 $2M – 6
0

$M $6 $0
Table 9.8
–$M + $5 $0 $0
Pivot column © 2009 Prentice-Hall, Inc. 9 – 75
 Developing a Third Tableau

 The new pivot column is the X1 column and we

check the quantity column-to-pivot column ratio

850
For the A1 row  1  850

300 (smallest ratio)

For the S row  1  300
1

150
For the X 2 row  0  undefined

 Hence variable S1 will be replaced by X1

© 2009 Prentice-Hall, Inc. 9 – 76

 Developing a Third Tableau

 To replace the pivot row we divide each number in

the S1 row by 1 leaving it unchanged
 The other calculations are shown below

A1 Row S1 Row
0 = 1 – (1)(1) 0 = 0 – (0)(1)
0 = 0 – (1)(0) 1 = 1 – (0)(0)
–1 = 0 – (1)(1) 0 = 0 – (0)(1)
1 = 1 – (1)(0)
–1 = –1 – (0)(0)
1 = 1 – (1)(0)

0 = 0 – (0)(0)
–1 = –1 – (1)(0)
1 = 1 – (0)(0) © 2009 Prentice-Hall, Inc. 9 – 77

550 = 850 – (1)(300) 150

= 150 – (0)(300)
 Developing a Third Tableau
 The Zj and Cj – Zj rows are computed next
Zj (for X1) = $M(0) + $5(1) + $6(0) = $5
Zj (for X2) = $M(0) + $5(0) + $6(1) = $6
Zj (for S1) = $M(–1) + $5(1) + $6(0) = –$M +
5 Zj (for S2) = $M(1) + $5(0) + $6(–1) = $M –
6 Zj (for A1) = $M(1) + $5(0) + $6(0) = $M
Zj (for A2) = $M(–1) + $5(0) + $6(1) = –$M +
6
Zj (for total cost) = $M(550) + $5(300) + $6(150) = $550M
+ 2,400 X1 X2 S1 S2 A1 A2
Cj for column $5 $6 $0 $0 $M $M
COLUMN
Zj for column $5 $6 –$M + 5 $M – 6 $M –$M + 6
Cj – Zj for column $0 $0 $M + 5 –$M + 6 $0 $2M – 6
© 2009 Prentice-Hall, Inc. 9 – 78
 Developing a Third Tableau
 The third simplex tableau for the Muddy River
Chemical problem
Cj $5 $6 $0 $M $M
$0
SOLUTION
MIX S2 A1 A2 QUANTITY
X1 X2
$M A1 1 1 550
S1
–1
Pivot row
0 0 – Pivot number
$5 X1 1 0 1 0 0 0 300
1
$6 0 1 0 –1 0 1 150
$M – 6 $M –$M + 6 $550M + 2,400
XZ2j $5 $6 –$M + 5
Cj – Zj $0 $0 $M – 5 –$M + 6 $0 $2M – 6
Pivot column

Table 9.9

© 2009 Prentice-Hall, Inc. 9 – 79

 Fourth Tableau for Muddy River

 The new pivot column is the S2 column

550
For the A1 row   550 (row to be replaced)
1
300
For the X1 row  (undefined)
0
(not considered
150
For the X 2 row   because it is negative)
1

© 2009 Prentice-Hall, Inc. 9 – 80

 Fourth Tableau for Muddy River

 Each number in the pivot row is again divided by 1

 The other calculations are shown below

X1 Row X2 Row
1 = 1 – (0)(0) 0 = 0 – (–1)(0)
0 = 0 – (0)(0) 1 = 1 – (–1)(0)
1 = 1 – (0)(–1) –1 = 0 – (–1)(–1)
0 = 0 – (0)(1) 0 = –1 – (–1)(1)
0 = 0 – (0)(1) 1 = 0 – (–1)(1)
0 = 0 – (0)(–1) 0 = 1 – (–1)(–1)
300 = 300 – (0)(550) 700 = 150 – (–1)(550)

© 2009 Prentice-Hall, Inc. 9 – 81

 Fourth Tableau for Muddy River
 Finally the Zj and Cj – Zj rows are computed
Zj (for X1) = $0(0) + $5(1) + $6(0) =
$5 Zj (for X2) = $(0) + $5(0) + $6(1) =
$6 Zj (for S1) = $0(–1) + $5(1) + $6(–1) =
–$1 Zj (for S2) = $0(1) + $5(0) + $6(0) =
$0 Zj (for A1) = $0(1) + $5(0) + $6(1) =
$6 Zj (for A2) = $0(–1) + $5(0) + $6(0) =
$0
Zj (for total cost) = $0(550) + COLUMN
$5(300) + $6(700) =
$5,700 X1 X2 S1 S2 A1 A2
Cj for column $5 $6 $0 $0 $M $M
Zj for column $5 $6 –$1 $0 $6 $0
Cj – Zj for column $0 $0 $1 $0 $M – 6 $M
© 2009 Prentice-Hall, Inc. 9 – 82
 Fourth Tableau for Muddy River
 Fourth and optimal tableau for the Muddy River
Chemical Corporation problem

Cj $5 $6 $0 $0 $M $M
SOLUTION
MIX X1 X2 S1 S2 A1 A2 QUANTITY

$0 S2 0 0 –1 1 1 –1 550
$5 X1 1 0 1 0 0 0 300
$6 X2 0 1 –1 0 1 0 700
Zj $5 $6 –$1 $0 $6 $0 $5,700
Cj – Zj $0 $0 $1 $0 $M – 6 $M

Table 9.10

© 2009 Prentice-Hall, Inc. 9 – 83

 Review of Procedures for Solving
LP Minimization Problems

I. Formulate the LP problem’s objective function

and constraints
II. Include slack variables to each less-than-or-
equal-to constraint and both surplus and
artificial variables to greater-than-or-equal-to
constraints and add all variables to the objective
function
III. Develop and initial simplex tableau with artificial
and slack variables in the basis and the other
variables set equal to 0. compute the Zj and
Cj - Zj values for this tableau.
IV. Follow the five steps until an optimal solution
has been reached
© 2009 Prentice-Hall, Inc. 9 – 84
 Review of Procedures for Solving
LP Minimization Problems
1. Choose the variable with the negative Cj - Zj
indicating the greatest improvement to enter the
solution in the pivot column
2. Determine the row to be replaced and the pivot
row by selecting the row with the smallest
(nonnegative) quantity-to-pivot column
substitution rate ratio
3. Calculate the new values for the pivot row
4. Calculate the new values for the other row(s)
5. Calculate the Zj and Cj - Zj values for the tableau.
If there are any Cj - Zj numbers less than 0, return
to step 1. If not, and optimal solution has been
reached.
© 2009 Prentice-Hall, Inc. 9 – 85
 Special Cases
 We have seen how special cases arise
when solving LP problems
graphically
 They also apply to the simplex
method
 You remember the four cases are
 Infeasibility
 Unbounded Solutions
 Degeneracy
 Multiple Optimal Solutions

© 2009 Prentice-Hall, Inc. 9 – 86

 Infeasibility

 Infeasibility comes about when there is no

solution that satisfies all of the problem’s
constraints
 In the simplex method, an infeasible solution is
indicated by looking at the final tableau
 All Cj - Zj row entries will be of the proper sign to
imply optimality, but an artificial variable will still
be in the solution mix
 A situation with no feasible solution may exist if
the problem was formulated improperly

© 2009 Prentice-Hall, Inc. 9 – 87

 Infeasibility

 Illustration of infeasibility

Cj $5 $8 $0 $0 $M $M
SOLUTION
MIX X1 X2 S1 S2 A1 A2 QUANTITY

$5 X1 1 0 –2 3 –1 0 200
$8 X2 0 1 1 2 –2 0 100
$M A2 0 0 0 –1 –1 1 20
Zj $5 $8 –$2 $31 – M –$21 – M $M $1,800 + 20M
Cj – Zj $0 $0 $2 $M – 31 $2M + 21 $0

Table 9.11

© 2009 Prentice-Hall, Inc. 9 – 88

 Unbounded Solutions

 Unboundedness describes linear programs that

do not have finite solutions
 It occurs in maximization problems when a
solution variable can be made infinitely large
without violating a constraint
 In the simplex method this will be discovered
prior to reaching the final tableau
 It will be manifested when trying to decide which
variable to remove from the solution mix
 If all the ratios turn out to be negative or
undefined, it indicates that the problem is
unbounded

© 2009 Prentice-Hall, Inc. 9 – 89

 Unbounded Solutions

 Problem with an unbounded solution

Cj $6 $9 $0 $0
SOLUTION MIX X1 X2 S1 S2
$9 –1 1 2 QUANTITY
0 30
X2
$0 –2 0 –1 1 10
Z –$9 $9 $18 $0 $270
S2j
Cj - Zj $15 $0 – $0
$18
Pivot column

Table 9.12

© 2009 Prentice-Hall, Inc. 9 – 90

 Unbounded Solutions

 The ratios from the pivot column

30
Ratio for the X 2 row :
Negative ratios
1
unacceptable
10
Ratio for the S row :
2

2
 Since both pivot column numbers are negative,
an unbounded solution is indicated

© 2009 Prentice-Hall, Inc. 9 – 91

 Degeneracy
 Degeneracy develops when three constraints
pass through a single point
 For example, suppose a problem has only these
three constraints X1 ≤ 10, X2 ≤ 10, and X1 + X2 < 20
 All three constraint lines will pass through the
point (10, 10)
 Degeneracy is first recognized when the ratio
calculations are made
 If there is a tie for the smallest ratio, this is a
signal that degeneracy exists
 As a result of this, when the next tableau is
developed, one of the variables in the solution
mix will have a value of zero
© 2009 Prentice-Hall, Inc. 9 – 92
 Degeneracy
 Degeneracy could lead to a situation known as
cycling in which the simplex algorithm alternates
back and forth between the same nonoptimal
solutions
 One simple way of dealing with the issue is to
select either row in question arbitrarily
 If unlucky and cycling does occur, simply go
back and select the other row

© 2009 Prentice-Hall, Inc. 9 – 93

 Degeneracy
 Problem illustrating degeneracy

Cj $5 $8 $2 $0 $0 $0
SOLUTION
X1 X2 X3 S1 S2 S3
MIX
QUANTITY
$8 X2 0.25 1 1 –2 0 0 10
$0 S2 4 0 0.33 –1 1 0 20
$0 S3 2 0 2 0.4 0 1 10
Zj $2 $8 $8 $16 $0 $0 $80
Cj - Zj $3 $0 –$6 –$16 $0 $0
Pivot column

Table 9.13

© 2009 Prentice-Hall, Inc. 9 – 94

 Degeneracy
 The ratios are computed as follows

10
For the X 2 row :0.25  40

20 Tie for the smallest

For the S2 row : 4  5
ratio indicates
degeneracy
10
For the S3 row : 
2
5

© 2009 Prentice-Hall, Inc. 9 – 95

 Multiple Optimal Solutions

 In the simplex method, multiple, or alternate,

optimal solutions can be spotted by looking at
the final tableau
 If the Cj – Zj value is equal to 0 for a variable that
is not in the solution mix, more than one optimal
solution exists

© 2009 Prentice-Hall, Inc. 9 – 96

 Multiple Optimal Solutions
 A problem with alternate optimal solutions

Cj $3 $2 $0 $0
SOLUTION MIX X1 X2 S1 S2
QUANTITY
$2 X2 1.5 1 1 0 6
$0 S2 1 0 0.5 1 3
Zj $3 $2 $2 $0 $12
Cj - Zj $0 $0 –$2 $0

Table 9.14

© 2009 Prentice-Hall, Inc. 9 – 97

 Chapter 7

Linear
Programming
Models: Graphical
and Computer
Methods
Prepared by Lee Revere and John Large

To accompany Quantitative Analysis 7-1 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 Introduction

Linear programming (LP) is

 a widely used mathematical modeling
technique
 designed to help managers in planning
and decision making
 relative to resource allocation.
 LP is a technique that helps in resource
allocation decisions.
Programming refers to
 modeling and solving a problem
mathematically.

To accompany Quantitative Analysis 7-2 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 Examples of Successful
LP Applications

1. Development of a production schedule

that will
 satisfy future demands for a firm’s
production
 while minimizing total production
and inventory costs
2. Selection of product mix in a
factory to
 make best use of machine-hours and
labor-hours available
 while maximizing the firm’s
products

To accompany Quantitative Analysis 7-3 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
Examples of Successful
LP Applications (continued)
3. Determination of grades of petroleum
products to yield the maximum profit
4. Selection of different blends of raw
materials to feed mills to produce
finished feed combinations at minimum
cost
5. Determination of a distribution system
that will minimize total shipping cost
from several warehouses to various
market locations

To accompany Quantitative Analysis 7-4 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
Requirements of a Linear
Programming Problem
All LP problems have 4 properties in
common:
 All problems seek to maximize or
minimize some quantity (the objective
function).
 The presence of restrictions or
constraints limits the degree to which
we can pursue our objective.
 There must be alternative courses of
action to choose from.
 The objective and constraints in linear
programming problems must be
expressed in terms of linear equations
or inequalities.

To accompany Quantitative Analysis 7-5 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 5 Basic Assumptions of
Linear Programming
1. Certainty:
 numbers in the objective and constraints
are known with certainty and do not
change during the period being studied
2. Proportionality:
 exists in the objective and constraints
 constancy between production
increases and resource utilization
3. Additivity:
 the total of all activities equals the sum of
the individual activities

To accompany Quantitative Analysis 7-6 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 5 Basic Assumptions of
Linear Programming
(continued)
4. Divisibility:
 solutions need not be in whole numbers
(integers)
 solutions are divisible, and may take any
fractional value
5. Non-negativity:
 all answers or variables are greater than or
equal to (≥) zero
 negative values of physical quantities are
impossible

To accompany Quantitative Analysis 7-7 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 Formulating Linear
Programming
Problems
 Formulating a linear program involves
developing a mathematical model to
represent the managerial problem.
 Once the managerial problem is
understood, begin to develop the
mathematical statement of the problem.
 The steps in formulating a linear
program follow on the next slide.

To accompany Quantitative Analysis 7-8 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 Formulating Linear
Programming Problems
(continued)
Steps in LP Formulations
1. Completely understand the
managerial problem being faced.
2. Identify the objective and the
constraints.
3. Define the decision
variables.
4. Use the decision variables to write
mathematical expressions for the
objective function and the
constraints.

To accompany Quantitative Analysis 7-9 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 Formulating Linear
Programming Problems
(continued)
The Product Mix Problem
 Two or more products are usually
produced using limited resources such as
- personnel, machines, raw materials,
and so on.
 The profit that the firm seeks to
maximize is based on the profit
contribution per unit of each product.
 The company would like to determine
how many units of each product it
should produce so as to maximize
overall profit given its limited resources.
 A problem of this type is formulated in
the following example on the next slide.
To accompany Quantitative Analysis 7-10 © 2006 by Prentice Hall, Inc.
for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
Flair Furniture Company
Data - Table 7.1
Hours Required to Produce One Unit
Available
T C Hours This
Department Tables Chairs Week
• Carpentry 4 3 240
• Painting 2 1 100
&Varnishing
Mathematical formulation:
Profit Amount $7 $5

Constraints: 4T + 3C  240 (Carpentry)

2T + 1C  100 (Paint & Varnishing)
T ≥ 0 (1st nonnegative cons)
C ≥ 0 (2nd nonnegative cons)
Max. Objective, z: 7T + 5C
To accompany Quantitative Analysis 7-11 © 2006 by Prentice Hall, Inc.
for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 Flair Furniture Company
Constraints
The easiest way to solve a small LP problem,
such as that of the Flair Furniture Company, is
with the graphical solution approach.
The graphical method works only when there are
two decision variables, but it provides valuable
insight into how larger problems are structured.
When there are more than two variables, it is not
possible to plot the solution on a two-dimensional
graph; a more complex approach is needed.
But the graphical method is invaluable in providing
us with insights into how other approaches work.

To accompany Quantitative Analysis 7-12 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
Flair Furniture Company
Constraints
120

100 2T + 1C ≤ 100
Painting/Varnishing
Number of Chairs

80

60

40 4T + 3C ≤ 240
Carpentry
20

0
20 40 60 80 100
Number of Tables
To accompany Quantitative Analysis 7-13 © 2006 by Prentice Hall, Inc.
for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
Flair Furniture Company
Feasible Region

120
Painting/Varnishing
Number of Chairs

100

80

60
Carpentry
40
Feasible
20 Region

0
20 40 60 80 100
Number of Tables
To accompany Quantitative Analysis 7-14 © 2006 by Prentice Hall, Inc.
for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 Isoprofit Lines Steps
1. Graph all constraints and find the
feasible region.
2. Select a specific profit (or cost) line
and graph it to find the slope.
3. Move the objective function line in
the direction of increasing profit (or
decreasing cost) while maintaining
the slope. The last point it touches in
the feasible region is the optimal
solution.
4. Find the values of the decision
variables at this last point and
compute the profit (or cost).

To accompany Quantitative Analysis 7-15 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
Flair Furniture Company
Isoprofit Lines
Isoprofit Line Solution Method
 Start by letting profits equal some
arbitrary but small dollar
amount.
 Choose a profit of, say, $210.
- This is a profit level that can
be obtained easily without
violating either of the two
constraints.
 The objective function can be
written as
$210 = 7T + 5C.

To accompany Quantitative Analysis 7-16 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
Flair Furniture Company
Isoprofit Lines
Isoprofit Line Solution Method
• The objective function is just the
equation of a line called an isoprofit line.
- It represents all combinations of (T, C) that
would yield a total profit of $210.
 To plot the profit line, proceed exactly as
done to plot a constraint line:
- First, let T = 0 and solve for the point
at which the line crosses the C axis.
- Then, let C = 0 and solve for T.
 $210 = $7(0) + $5(C)
 C = 42 chairs
 Then, let C = 0 and solve for T.
 $210 = $7(T) + $5(0)
 T = 30 tables
To accompany Quantitative Analysis 7-17 © 2006 by Prentice Hall, Inc.
for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
Flair Furniture Company
Isoprofit Lines
Isoprofit Line Solution Method
 Next connect these two points with a
straight line. This profit line is illustrated
in the next slide.
 All points on the line represent feasible
solutions that produce an approximate
profit of $210
 Obviously, the isoprofit line for $210
does not produce the highest
possible profit to the firm.
 Try graphing more lines, each yielding a
higher profit.
 Another equation, $420 = $7T + $5C, is
plotted in the same fashion as the
lower line.

To accompany Quantitative Analysis 7-18 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
Flair Furniture Company
Isoprofit Lines
Isoprofit Line Solution Method
 When T = 0,
 $420 = $7(0) + 5(C)
 C = 84 chairs
 When C = 0,
 $420 = $7(T) + 5(0)
 T = 60 tables
 This line is too high to be considered as
it no longer touches the feasible
region.
 The highest possible isoprofit line is
illustrated in the second following slide.
It touches the tip of the feasible region at
the corner point (T = 30, C = 40) and
yields a profit of $410.
7-19
To accompany Quantitative Analysis © 2006 by Prentice Hall, Inc.
for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
Flair Furniture Company
Isoprofit Lines
120

100
Painting/Varnishing
Number of Chairs

80 7T + 5C = 210

60 7T + 5C = 420

40 Carpentry

20

0
20 40 60 80 100
Number of Tables
To accompany Quantitative Analysis 7-20 © 2006 by Prentice Hall, Inc.
for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
Flair Furniture Company
Optimal Solution
120
Isoprofit Lines
100
Painting/Varnishing
Number of Chairs

80

Solution
60
(T = 30, C = 40)

40 Carpentry

20

0
20 40 60 80 100
Number of Tables
To accompany Quantitative Analysis 7-21 © 2006 by Prentice Hall, Inc.
for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
Flair Furniture Company
Corner Point
Corner Point Solution Method
 A second approach to solving LP
problems
 It involves looking at the profit at
every corner point of the feasible
region
 The mathematical theory behind LP is
that the optimal solution must lie at
one of the corner points in the feasible
region

To accompany Quantitative Analysis 7-22 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 Corner Point
Corner Point Solution Method, Summary
1. Graph all constraints and find the
feasible region.
2. Find the corner points of the feasible
region.
3. Compute the profit (or cost) at each
of the feasible corner points.
4. Select the corner point with the best
value of the objective function
found in step 3. This is the optimal
solution.

To accompany Quantitative Analysis 7-23 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 Flair Furniture Company
Corner Point
Corner Point Solution Method
 The feasible region for the Flair Furniture
Company problem is a four-sided polygon
with four corner, or extreme, points.
 These points are labeled 1 ,2 ,3 , and 4 on
the next graph.
 To find the (T, C) values producing the
maximum profit, find the coordinates of
each corner point and test their profit levels.

Point 1:(T = 0,C = 0) profit = $7(0) + $5(0) = $0

Point 2:(T = 0,C = 80) profit = $7(0) + $5(80) =
$400
Point 3:(T = 30,C = 40) profit = $7(30) +
$5(40) =
$410
Point 4 : (T = 50, C = 0) profit = $7(50) + $5(0)
=
To accompany Quantitative Analysis 7-24 © 2006 by Prentice Hall, Inc.
$350
for Management, 9e
by Render/Stair/Hanna
Upper Saddle River, NJ 07458
Flair Furniture Company
Optimal Solution
120
2
Corner Points
100
Painting/Varnishing
Number of Chairs

80

Solution
60
(T = 30, C = 40)

40 Carpentry
3
20
1
0
20 4 60
40 80 100
Number of Tables
To accompany Quantitative Analysis 7-25 © 2006 by Prentice Hall, Inc.
for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 Solving Minimization
Problems
Many LP problems minimize an objective,
such as cost, instead of maximizing a
profit function. For example,
• A restaurant may wish to develop a work
schedule to meet staffing needs while
minimizing the total number of employees.
Or,
 A manufacturer may seek to distribute its
products from several factories to its many
regional warehouses in such a way as to
minimize total shipping costs.
Or,
 A hospital may want to provide a daily
meal plan for its patients that meets certain
nutritional standards while minimizing food
purchase costs.
To accompany Quantitative Analysis 7-26 © 2006 by Prentice Hall, Inc.
for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 Solving Minimization
Problems
Minimization problems can be solved
graphically by
 first setting up the feasible solution
region and then using either
 the corner point method or
 an isocost line approach (which is
analogous to the isoprofit approach in
maximization problems)
to find the values of the decision variables
(e.g., X1 and X2) that yield the minimum
cost.

To accompany Quantitative Analysis 7-27 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 Solving Minimization
Problems
Holiday Meal Turkey Ranch example
Minimize: 2X1 + 3X2

Subject to:
5X1 + 10X2  90 oz. (A)
4X1 + 3X2  48 oz. (B)
½ X1  1 ½ oz. (C)
X1 , X2  0 (D)
where,
X 1 = # of pounds of brand 1 feed purchased
X 2 = # of pounds of brand 2 feed
purchased A constraint
(A) = ingredient
(B) = ingredient B constraint
(C) = ingredient C constraint
(D) = non-negativity constraints
To accompany Quantitative Analysis 7-28 © 2006 by Prentice Hall, Inc.
for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 Holiday Meal Turkey
Ranch
Using the Corner Point Method
To solve this problem:
1. Construct the feasible solution region.
 This is done by plotting each of the three
constraint equations.
2. Find the corner points.
 This problem has 3 corner points, labeled
a, b, and c.

- Minimization problems are often unbound

outward (i.e., to the right and on top), but
this causes no difficulty in solving them.
- As long as they are bounded inward (on
the left side and the bottom), corner points
may be established.
- The optimal solution will lie at one of the
corners as it would in a maximization
problem.
To accompany Quantitative Analysis 7-29 © 2006 by Prentice Hall, Inc.
for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 Holiday Meal Turkey
Problem
Corner Points

To accompany Quantitative Analysis 7-30 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 Solving Minimization
Problems
Using the Isocost Line Approach
 As with isoprofit lines, there is no
need to compute the cost at each
corner point, but instead draw a series
of parallel cost lines.
 The lowest cost line (i.e., the one
closest in toward the origin) to touch
the feasible region provides the
optimal solution corner.
1. Start, for example, by drawing a 54-
cent cost line, namely 54 = 2X1 + 3X2.
- Obviously, there are many points in the
feasible region that would yield a
lower total cost.

To accompany Quantitative Analysis 7-31 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 Solving Minimization
Problems (continued)
2. Proceed to move the isocost line
toward the lower left, in a plane
parallel to the 54-cent solution
line.
3. The last point touched while still in
contact with the feasible region is
the same as corner point b of the
Corner Point diagram in the
previous slide.
- It has the coordinates (X1 = 8.4, X2
= 4.8) and an associated cost of
31.2 cents.

To accompany Quantitative Analysis 7-32 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 Holiday Meal Turkey
Problem
Isoprofit Lines

To accompany Quantitative Analysis 7-33 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 Special Cases in LP
Four special cases and difficulties arise at times
when solving LP problems:
1. Infeasibility:
- lack of a feasible solution region can occur if
constraints conflict with one another.

2. Unbounded Solutions:
- when the objective function in a maximization
problem can be infinitely large, the problem is
unbounded and is missing one or more constraints.

3. Redundancy:
- a redundant constraint is one that does not affect
the feasible solution region.

4. More than One Optimal Solution:

- two or more optimal solutions may exist, and
- this actually allows management great flexibility in
deciding which combination to select.

To accompany Quantitative Analysis 7-34 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 A Problem with No
Feasible Solution
X2

6
Region Satisfying
4
3rd Constraint
2

2 4 6 8 X1

Region Satisfying First 2 Constraints

To accompany Quantitative Analysis 7-35 © 2006 by Prentice Hall, Inc.
for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
A Solution Region That is
Unbounded to the Right
X2

15 X1 > 5
X2 < 10

10

Feasible Region
5

X1 + 2X2 > 10
0

5 10 15 X1

To accompany Quantitative Analysis 7-36 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
 A Problem with a
Redundant Constraint
X2

30

25 2X1 + X2 < 30 Redundant

20
Constraint
15 X1 < 25

10
X1 + X2 < 20
5

0 Feasible

Region
X1
5 10 15 20 25 30
To accompany Quantitative Analysis 7-37 © 2006 by Prentice Hall, Inc.
for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna
An Example of Alternate
Optimal Solutions

8
Optimal Solution Consists of
7
All Combinations of X1 and
6
X2 Along the AB Segment
5 A Isoprofit Line for $8
4
Isoprofit
3 B for
Line$12
2 AB
Overlays Line
1
Segment
0 1 2 3 4 5 6 7 8

To accompany Quantitative Analysis 7-38 © 2006 by Prentice Hall, Inc.

for Management, 9e Upper Saddle River, NJ 07458
by Render/Stair/Hanna