Chapter 1

Introduction to
Quantitative Analysis

To accompany
Quantitative Analysis for Management, Tenth Edition,
by Render, Stair, and Hanna © 2008 Prentice-Hall, Inc.
Power Point slides created by Jeff Heyl © 2009 Prentice-Hall, Inc.
 Learning Objectives
After completing this chapter, students will be able to:

1. Describe the quantitative analysis approach

2. Understand the application of quantitative
analysis in a real situation
3. Describe the use of modeling in quantitative
analysis
4. Use computers and spreadsheet models to
perform quantitative analysis
5. Discuss possible problems in using
quantitative analysis
6. Perform a break-even analysis

© 2009 Prentice-Hall, Inc. 1–2

 Chapter Outline
1.1 Introduction
1.2 What Is Quantitative Analysis?
1.3 The Quantitative Analysis Approach
1.4 How to Develop a Quantitative Analysis
Model
1.5 The Role of Computers and Spreadsheet
Models in the Quantitative Analysis
Approach
1.6 Possible Problems in the Quantitative
Analysis Approach
1.7 Implementation — Not Just the Final Step

© 2009 Prentice-Hall, Inc. 1–3

 Introduction

 Mathematical tools have been used for

thousands of years
 Quantitative analysis can be applied to
a wide variety of problems
 It’s not enough to just know the
mathematics of a technique
 One must understand the specific
applicability of the technique, its
limitations, and its assumptions

© 2009 Prentice-Hall, Inc. 1–4

Examples of Quantitative Analyses

 Taco Bell saved over $150 million using

forecasting and scheduling quantitative
analysis models
 NBC television increased revenues by
over $200 million by using quantitative
analysis to develop better sales plans
 Continental Airlines saved over $40
million using quantitative analysis
models to quickly recover from weather
delays and other disruptions

© 2009 Prentice-Hall, Inc. 1–5

 What is Quantitative Analysis?

Quantitative analysis is a scientific approach

to managerial decision making whereby raw
data are processed and manipulated
resulting in meaningful information

Quantitative Meaningful
Raw Data Analysis Information

© 2009 Prentice-Hall, Inc. 1–6

 What is Quantitative Analysis?

Quantitative factors might be different

investment alternatives, interest rates,
inventory levels, demand, or labor cost
Qualitative factors such as the weather,
state and federal legislation, and
technology breakthroughs should also be
considered
 Information may be difficult to quantify but
can affect the decision-making process

© 2009 Prentice-Hall, Inc. 1–7

 The Quantitative Analysis Approach

Defining the Problem

Developing a Model

Acquiring Input Data

Developing a Solution

Testing the Solution

Analyzing the Results

Figure 1.1 Implementing the Results

© 2009 Prentice-Hall, Inc. 1–8
 Defining the Problem
Need to develop a clear and concise
statement that gives direction and meaning
to the following steps
 This may be the most important and difficult
step
 It is essential to go beyond symptoms and
identify true causes
 May be necessary to concentrate on only a few
of the problems – selecting the right problems
is very important
 Specific and measurable objectives may have to
be developed

© 2009 Prentice-Hall, Inc. 1–9

 Developing a Model
Quantitative analysis models are realistic,
solvable, and understandable mathematical
representations of a situation

+ b 1X
$ Sales

b
Y= 0

$ Advertising

There are different types of models

Scale Schematic
models models
© 2009 Prentice-Hall, Inc. 1 – 10
 Developing a Model

 Models generally contain variables

(controllable and uncontrollable) and
parameters
 Controllable variables are generally the
decision variables and are generally
unknown
 Parameters are known quantities that
are a part of the problem

© 2009 Prentice-Hall, Inc. 1 – 11

 Acquiring Input Data

Input data must be accurate – GIGO rule

Garbage
In
Process
Garbage
Out

Data may come from a variety of sources such as

company reports, company documents, interviews,
on-site direct measurement, or statistical sampling
© 2009 Prentice-Hall, Inc. 1 – 12
 Developing a Solution
 The best (optimal) solution to a problem
is found by manipulating the model
variables until a solution is found that is
practical and can be implemented
 Common techniques are
 Solving equations
 Trial and error – trying various approaches
and picking the best result
 Complete enumeration – trying all possible
values
 Using an algorithm – a series of repeating
steps to reach a solution

© 2009 Prentice-Hall, Inc. 1 – 13

 Testing the Solution

Both input data and the model should be

tested for accuracy before analysis and
implementation
 New data can be collected to test the model
 Results should be logical, consistent, and
represent the real situation

© 2009 Prentice-Hall, Inc. 1 – 14

 Analyzing the Results
Determine the implications of the solution
 Implementing results often requires change
in an organization
 The impact of actions or changes needs to
be studied and understood before
implementation

Sensitivity analysis determines how much

the results of the analysis will change if
the model or input data changes
 Sensitive models should be very thoroughly
tested

© 2009 Prentice-Hall, Inc. 1 – 15

 Implementing the Results
Implementation incorporates the solution
into the company
 Implementation can be very difficult
 People can resist changes
 Many quantitative analysis efforts have failed
because a good, workable solution was not
properly implemented
Changes occur over time, so even
successful implementations must be
monitored to determine if modifications are
necessary

© 2009 Prentice-Hall, Inc. 1 – 16

 Modeling in the Real World

Quantitative analysis models are used

extensively by real organizations to solve
real problems
 In the real world, quantitative analysis
models can be complex, expensive, and
difficult to sell
 Following the steps in the process is an
important component of success

© 2009 Prentice-Hall, Inc. 1 – 17

 How To Develop a Quantitative
Analysis Model

 An important part of the quantitative

analysis approach
 Let’s look at a simple mathematical
model of profit

Profit = Revenue – Expenses

© 2009 Prentice-Hall, Inc. 1 – 18

 How To Develop a Quantitative
Analysis Model
Expenses can be represented as the sum of fixed and
variable costs and variable costs are the product of
unit costs times the number of units
Profit = Revenue – (Fixed cost + Variable cost)
Profit = (Selling price per unit)(number of units
sold) – [Fixed cost + (Variable costs per
unit)(Number of units sold)]
Profit = sX – [f + vX]
Profit = sX – f – vX
where
s = selling price per unit v = variable cost per unit
f = fixed cost X = number of units sold
© 2009 Prentice-Hall, Inc. 1 – 19
 How To Develop a Quantitative
Analysis Model
Expenses can be represented as the sum of fixed and
variable costs and variable costs are the
The parameters product
of this modelof
unit costs times the number
are f, v,ofand
units
s as these are the
inputscost
Profit = Revenue – (Fixed inherent in the cost)
+ Variable model
Profit = (Selling priceThe
perdecision variable
unit)(number of of
units
sold) – [Fixedinterest
cost +is(Variable
X costs per
unit)(Number of units sold)]
Profit = sX – [f + vX]
Profit = sX – f – vX
where
s = selling price per unit v = variable cost per unit
f = fixed cost X = number of units sold
© 2009 Prentice-Hall, Inc. 1 – 20
 Pritchett’s Precious Time Pieces
The company buys, sells, and repairs old clocks.
Rebuilt springs sell for $10 per unit. Fixed cost of
equipment to build springs is $1,000. Variable cost
for spring material is $5 per unit.

s = 10 f = 1,000 v=5
Number of spring sets sold = X
Profits = sX – f – vX

If sales = 0, profits = –$1,000

If sales = 1,000, profits = [(10)(1,000) – 1,000 – (5)(1,000)]
= $4,000

© 2009 Prentice-Hall, Inc. 1 – 21

 Pritchett’s Precious Time Pieces
Companies are often interested in their break-even
point (BEP). The BEP is the number of units sold
that will result in $0 profit.

0 = sX – f – vX, or 0 = (s – v)X – f
Solving for X, we have
f = (s – v)X
f
X=
s–v

Fixed cost
BEP =
(Selling price per unit) – (Variable cost per unit)

© 2009 Prentice-Hall, Inc. 1 – 22

 Pritchett’s Precious Time Pieces
Companies are often interested in their break-even
point (BEP). The BEP is the number of units sold
BEP for Pritchett’s Precious Time Pieces
that will result in $0 profit.
BEP
0= sX –= f$1,000/($10
– vX, or – 0$5) = –200
= (s v)Xunits
–f
Salesfor
Solving of less
X, wethan
have 200 units of rebuilt springs
will result in a loss
f = (s – v)X
Sales of over 200 units of rebuilt springs will
result in a profit X = f
s–v

Fixed cost
BEP =
(Selling price per unit) – (Variable cost per unit)

© 2009 Prentice-Hall, Inc. 1 – 23

 Advantages of Mathematical Modeling

1. Models can accurately represent reality

2. Models can help a decision maker
formulate problems
3. Models can give us insight and information
4. Models can save time and money in
decision making and problem solving
5. A model may be the only way to solve large
or complex problems in a timely fashion
6. A model can be used to communicate
problems and solutions to others
© 2009 Prentice-Hall, Inc. 1 – 24
 Models Categorized by Risk

 Mathematical models that do not involve

risk are called deterministic models
 We know all the values used in the model
with complete certainty
 Mathematical models that involve risk,
chance, or uncertainty are called
probabilistic models
 Values used in the model are estimates
based on probabilities

© 2009 Prentice-Hall, Inc. 1 – 25

 Computers and Spreadsheet Models

QM for Windows
 An easy to use
decision support
system for use in
POM and QM
courses
 This is the main
menu of
quantitative
models

Program 1.1
© 2009 Prentice-Hall, Inc. 1 – 26
 Computers and Spreadsheet Models
Excel QM’s Main Menu (2003)
 Works automatically within Excel spreadsheets

Program 1.2A
© 2009 Prentice-Hall, Inc. 1 – 27
 Computers and Spreadsheet Models

Excel QM’s
Main Menu
(2007)

Program 1.2B
© 2009 Prentice-Hall, Inc. 1 – 28
 Computers and Spreadsheet Models

Excel QM
for the
Break-
Even
Problem

Program 1.3A
© 2009 Prentice-Hall, Inc. 1 – 29
 Computers and Spreadsheet Models

Excel QM
Solution
to the
Break-
Even
Problem

Program 1.3B
© 2009 Prentice-Hall, Inc. 1 – 30
 Computers and Spreadsheet Models

Using
Goal Seek
in the
Break-
Even
Problem

Program 1.4
© 2009 Prentice-Hall, Inc. 1 – 31
 Possible Problems in the
Quantitative Analysis Approach
Defining the problem
 Problems are not easily identified
 Conflicting viewpoints
 Impact on other departments
 Beginning assumptions
 Solution outdated
Developing a model
 Fitting the textbook models
 Understanding the model

© 2009 Prentice-Hall, Inc. 1 – 32

 Possible Problems in the
Quantitative Analysis Approach
Acquiring input data
 Using accounting data
 Validity of data
Developing a solution
 Hard-to-understand mathematics
 Only one answer is limiting
Testing the solution
Analyzing the results

© 2009 Prentice-Hall, Inc. 1 – 33

 Implementation –
Not Just the Final Step
Lack of commitment and resistance
to change
 Management may fear the use of
formal analysis processes will
reduce their decision-making power
 Action-oriented managers may want
“quick and dirty” techniques
 Management support and user
involvement are important

© 2009 Prentice-Hall, Inc. 1 – 34

 Implementation –
Not Just the Final Step
Lack of commitment by quantitative
analysts
 An analysts should be involved with
the problem and care about the
solution
 Analysts should work with users and
take their feelings into account

© 2009 Prentice-Hall, Inc. 1 – 35

 Summary
 Quantitative analysis is a scientific
approach to decision making
 The approach includes
 Defining the problem
 Acquiring input data
 Developing a solution
 Testing the solution
 Analyzing the results
 Implementing the results

© 2009 Prentice-Hall, Inc. 1 – 36

 Summary
 Potential problems include
 Conflicting viewpoints
 The impact on other departments
 Beginning assumptions
 Outdated solutions
 Fitting textbook models
 Understanding the model
 Acquiring good input data
 Hard-to-understand mathematics
 Obtaining only one answer
 Testing the solution
 Analyzing the results
© 2009 Prentice-Hall, Inc. 1 – 37
 Summary
 Implementation is not the final step
 Problems can occur because of
 Lack of commitment to the approach
 Resistance to change

© 2009 Prentice-Hall, Inc. 1 – 38

 Chapter 7
Linear Programming Models:
Graphical and Computer
Methods

To accompany
Quantitative Analysis for Management, Tenth Edition,
by Render, Stair, and Hanna © 2008 Prentice-Hall, Inc.
Power Point slides created by Jeff Heyl © 2009 Prentice-Hall, Inc.
 Introduction

◼ Many management decisions involve trying to

make the most effective use of limited resources
◼ Machinery, labor, money, time, warehouse space, raw
materials
◼ Linear programming (LP) is a widely used
mathematical modeling technique designed to
help managers in planning and decision making
relative to resource allocation
◼ Belongs to the broader field of mathematical
programming
◼ In this sense, programming refers to modeling and
solving a problem mathematically

© 2009 Prentice-Hall, Inc. 7–2

 Requirements of a Linear
Programming Problem

◼ LP has been applied in many areas over

the past 50 years
◼ All LP problems have 4 properties in
common
1. All problems seek to maximize or minimize
some quantity (the objective function)
2. The presence of restrictions or constraints that
limit the degree to which we can pursue our
objective
3. There must be alternative courses of action to
choose from
4. The objective and constraints in problems
must be expressed in terms of linear equations
or inequalities
© 2009 Prentice-Hall, Inc. 7–3
 Examples of Successful
LP Applications
◼ Development of a production schedule that will
◼ satisfy future demands for a firm’s production
◼ while minimizing total production and inventory costs

◼ Determination of grades of petroleum products to yield

the maximum profit

◼ Selection of different blends of raw materials to feed

mills to produce finished feed combinations at
minimum cost

◼ Determination of a distribution system that will

minimize total shipping cost from several warehouses
to various market locations

© 2009 Prentice-Hall, Inc. 7–4

 LP Properties and Assumptions
PROPERTIES OF LINEAR PROGRAMS
1. One objective function
2. One or more constraints
3. Alternative courses of action
4. Objective function and constraints are linear
ASSUMPTIONS OF LP
1. Certainty
2. Proportionality
3. Additivity
4. Divisibility
5. Nonnegative variables
Table 7.1
© 2009 Prentice-Hall, Inc. 7–5
 Basic Assumptions of LP
◼ We assume conditions of certainty exist and numbers
in the objective and constraints are known with
certainty and do not change during the period being
studied
◼ We assume proportionality exists in the objective and
constraints
▪ constancy between production increases and resource
utilization – if 1 unit needs 3 hours then 10 require 30
hours
◼ We assume additivity in that the total of all activities
equals the sum of the individual activities
◼ We assume divisibility in that solutions need not be
whole numbers
◼ All answers or variables are nonnegative as we are
dealing with real physical quantities
© 2009 Prentice-Hall, Inc. 7–6
 Formulating LP Problems
◼ Formulating a linear program involves
developing a mathematical model to represent
the managerial problem
◼ The steps in formulating a linear program are
1. Completely understand the managerial
problem being faced
2. Identify the objective and constraints
3. Define the decision variables
4. Use the decision variables to write
mathematical expressions for the objective
function and the constraints

© 2009 Prentice-Hall, Inc. 7–7

 Formulating LP Problems

◼ One of the most common LP applications is the

product mix problem
◼ Two or more products are produced using limited
resources such as personnel, machines, and raw
materials
◼ 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
© 2009 Prentice-Hall, Inc. 7–8
 Flair Furniture Company
◼ The Flair Furniture Company produces
inexpensive tables and chairs
◼ Processes are similar in that both require a certain
amount of hours of carpentry work and in the
painting and varnishing department
◼ Each table takes 4 hours of carpentry and 2 hours
of painting and varnishing
◼ Each chair requires 3 of carpentry and 1 hour of
painting and varnishing
◼ There are 240 hours of carpentry time available
and 100 hours of painting and varnishing
◼ Each table yields a profit of $70 and each chair a
profit of $50
© 2009 Prentice-Hall, Inc. 7–9
 Flair Furniture Company
◼ The company wants to determine the best
combination of tables and chairs to produce to
reach the maximum profit
HOURS REQUIRED TO
PRODUCE 1 UNIT
(T) (C) AVAILABLE HOURS
DEPARTMENT TABLES CHAIRS THIS WEEK
Carpentry 4 3 240

Painting and varnishing 2 1 100

Profit per unit $70 $50

Table 7.2

© 2009 Prentice-Hall, Inc. 7 – 10

 Flair Furniture Company
◼ The objective is to
Maximize profit
◼ The constraints are
1. The hours of carpentry time used cannot
exceed 240 hours per week
2. The hours of painting and varnishing time
used cannot exceed 100 hours per week
◼ The decision variables representing the actual
decisions we will make are
T = number of tables to be produced per week
C = number of chairs to be produced per week

© 2009 Prentice-Hall, Inc. 7 – 11

 Flair Furniture Company

◼ We create the LP objective function in terms of T

and C
Maximize profit = $70T + $50C
◼ Develop mathematical relationships for the two
constraints
◼ For carpentry, total time used is
(4 hours per table)(Number of tables produced)
+ (3 hours per chair)(Number of chairs produced)
◼ We know that
Carpentry time used ≤ Carpentry time available
4T + 3C ≤ 240 (hours of carpentry time)

© 2009 Prentice-Hall, Inc. 7 – 12

 Flair Furniture Company
◼ Similarly
Painting and varnishing time used
≤ Painting and varnishing time available
2 T + 1C ≤ 100 (hours of painting and varnishing time)

This means that each table produced

requires two hours of painting and
varnishing time

◼ Both of these constraints restrict production

capacity and affect total profit

© 2009 Prentice-Hall, Inc. 7 – 13

 Flair Furniture Company
◼ The values for T and C must be nonnegative

T ≥ 0 (number of tables produced is greater

than or equal to 0)
C ≥ 0 (number of chairs produced is greater
than or equal to 0)

◼ The complete problem stated mathematically

Maximize profit = $70T + $50C

subject to
4T + 3C ≤ 240 (carpentry constraint)
2T + 1C ≤ 100 (painting and varnishing constraint)
T, C ≥ 0 (nonnegativity constraint)

© 2009 Prentice-Hall, Inc. 7 – 14

 Graphical Solution to an LP Problem

◼ The easiest way to solve a small LP

problems is with the graphical solution
approach
◼ The graphical method only works when
there are just two decision variables
◼ When there are more than two variables, a
more complex approach is needed as it is
not possible to plot the solution on a two-
dimensional graph
◼ The graphical method provides valuable
insight into how other approaches work
© 2009 Prentice-Hall, Inc. 7 – 15
 Graphical Representation of a
Constraint
C

100 –
– This Axis Represents the Constraint T ≥ 0
80 –
Number of Chairs

–
60 –
–
40 – This Axis Represents the
– Constraint C ≥ 0
20 –
–
|– | | | | | | | | | | |
0 20 40 60 80 100 T

Figure 7.1 Number of Tables

© 2009 Prentice-Hall, Inc. 7 – 16

 Graphical Representation of a
Constraint

◼ The first step in solving the problem is to

identify a set or region of feasible
solutions
◼ To do this we plot each constraint
equation on a graph
◼ We start by graphing the equality portion
of the constraint equations
4T + 3C = 240
◼ We solve for the axis intercepts and draw
the line

© 2009 Prentice-Hall, Inc. 7 – 17

 Graphical Representation of a
Constraint
◼ When Flair produces no tables, the
carpentry constraint is
4(0) + 3C = 240
3C = 240
C = 80
◼ Similarly for no chairs
4T + 3(0) = 240
4T = 240
T = 60
◼ This line is shown on the following graph

© 2009 Prentice-Hall, Inc. 7 – 18

 Graphical Representation of a
Constraint
C
Graph of carpentry constraint equation
100 –
–
80 –
Number of Chairs

(T = 0, C = 80)
–
60 –
–
40 –
–
(T = 60, C = 0)
20 –
–
|– | | | | | | | | | | |
0 20 40 60 80 100 T

Figure 7.2 Number of Tables

© 2009 Prentice-Hall, Inc. 7 – 19

 Graphical Representation of a
Constraint
C ◼ Any point on or below the constraint
plot will not violate the restriction
100 –
◼ Any point above the plot will violate
– the restriction
80 –
Number of Chairs

–
60 –
–
(30, 40) (70, 40)
40 –
–
20 –
– (30, 20)
|– | | | | | | | | | | |
0 20 40 60 80 100 T

Figure 7.3 Number of Tables

© 2009 Prentice-Hall, Inc. 7 – 20

 Graphical Representation of a
Constraint

◼ The point (30, 40) lies on the plot and

exactly satisfies the constraint
4(30) + 3(40) = 240
◼ The point (30, 20) lies below the plot and
satisfies the constraint
4(30) + 3(20) = 180
◼ The point (30, 40) lies above the plot and
does not satisfy the constraint
4(70) + 3(40) = 400

© 2009 Prentice-Hall, Inc. 7 – 21

 Graphical Representation of a
Constraint
C

100 – (T = 0, C = 100)
–
80 –
Number of Chairs

Graph of painting and varnishing

– constraint equation
60 –
–
40 –
–
(T = 50, C = 0)
20 –
–
|– | | | | | | | | | | |
0 20 40 60 80 100 T

Figure 7.4 Number of Tables

© 2009 Prentice-Hall, Inc. 7 – 22

 Graphical Representation of a
Constraint

◼ To produce tables and chairs, both

departments must be used
◼ We need to find a solution that satisfies both
constraints simultaneously
◼ A new graph shows both constraint plots
◼ The feasible region (or area of feasible
solutions) is where all constraints are satisfied
◼ Any point inside this region is a feasible
solution
◼ Any point outside the region is an infeasible
solution

© 2009 Prentice-Hall, Inc. 7 – 23

 Graphical Representation of a
Constraint
C
◼ Feasible solution region for Flair Furniture
100 –
–
80 –
Number of Chairs

Painting/Varnishing Constraint
–
60 –
–
40 –
–
Carpentry Constraint
20 – Feasible
– Region
|– | | | | | | | | | | |
0 20 40 60 80 100 T

Figure 7.5 Number of Tables

© 2009 Prentice-Hall, Inc. 7 – 24

 Graphical Representation of a
Constraint
◼ For the point (30, 20)

Carpentry 4T + 3C ≤ 240 hours available

constraint (4)(30) + (3)(20) = 180 hours used ✓
Painting 2T + 1C ≤ 100 hours available
constraint (2)(30) + (1)(20) = 80 hours used
✓

◼ For the point (70, 40)

Carpentry 4T + 3C ≤ 240 hours available

constraint (4)(70) + (3)(40) = 400 hours used 
Painting 2T + 1C ≤ 100 hours available
constraint (2)(70) + (1)(40) = 180 hours used 

© 2009 Prentice-Hall, Inc. 7 – 25

 Graphical Representation of a
Constraint
◼ For the point (50, 5)

Carpentry 4T + 3C ≤ 240 hours available

constraint (4)(50) + (3)(5) = 215 hours used ✓
Painting 2T + 1C ≤ 100 hours available
constraint (2)(50) + (1)(5) = 105 hours used 

© 2009 Prentice-Hall, Inc. 7 – 26

 Isoprofit Line Solution Method
◼ Once the feasible region has been graphed, we need
to find the optimal solution from the many possible
solutions
◼ The speediest way to do this is to use the isoprofit
line method
◼ Starting with a small but possible profit value, we
graph the objective function
◼ We move the objective function line in the direction of
increasing profit while maintaining the slope
◼ The last point it touches in the feasible region is the
optimal solution

© 2009 Prentice-Hall, Inc. 7 – 27

 Isoprofit Line Solution Method
◼ For Flair Furniture, choose a profit of $2,100
◼ The objective function is then
$2,100 = 70T + 50C
◼ Solving for the axis intercepts, we can draw the
graph
◼ This is obviously not the best possible solution
◼ Further graphs can be created using larger profits
◼ The further we move from the origin while
maintaining the slope and staying within the
boundaries of the feasible region, the larger the
profit will be
◼ The highest profit ($4,100) will be generated when
the isoprofit line passes through the point (30, 40)
© 2009 Prentice-Hall, Inc. 7 – 28
Isoprofit Line Solution Method
C
◼ Isoprofit line at $2,100
100 –
–
80 –
Number of Chairs

–
60 –
– $2,100 = $70T + $50C
(0, 42)
40 –
–
(30, 0)
20 –
–
|– | | | | | | | | | | |
0 20 40 60 80 100 T

Figure 7.6 Number of Tables

© 2009 Prentice-Hall, Inc. 7 – 29

Isoprofit Line Solution Method
C
◼ Four isoprofit lines
100 –
–
$3,500 = $70T + $50C
80 –
Number of Chairs

– $2,800 = $70T + $50C

60 –
– $2,100 = $70T + $50C
40 –
– $4,100 = $70T + $50C
20 –
–
|– | | | | | | | | | | |
0 20 40 60 80 100 T

Figure 7.7 Number of Tables

© 2009 Prentice-Hall, Inc. 7 – 30

Isoprofit Line Solution Method
C
◼ Optimal solution to the
100 – Flair Furniture problem
–
80 –
Number of Chairs

Maximum Profit Line

–
60 – Optimal Solution Point
– (T = 30, C = 40)
40 –
– $4,100 = $70T + $50C
20 –
–
|– | | | | | | | | | | |
0 20 40 60 80 100 T

Figure 7.8 Number of Tables

© 2009 Prentice-Hall, Inc. 7 – 31

 Corner Point Solution Method
◼ A second approach to solving LP problems
employs the corner point method
◼ 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, or extreme point, in the
feasible region
◼ For Flair Furniture, the feasible region is a
four-sided polygon with four corner points
labeled 1, 2, 3, and 4 on the graph
© 2009 Prentice-Hall, Inc. 7 – 32
Corner Point Solution Method
C
◼ Four corner points of
100 – the feasible region
2 –
80 –
Number of Chairs

–
60 –
–
3
40 –
–
20 –
–
1 |– | | | | | | | | | | |
0 20 40 60 80 100 T
4
Figure 7.9 Number of Tables

© 2009 Prentice-Hall, Inc. 7 – 33

 Corner Point Solution Method
Point 1 : (T = 0, C = 0) Profit = $70(0) + $50(0) = $0
Point 2 : (T = 0, C = 80) Profit = $70(0) + $50(80) = $4,000
Point 4 : (T = 50, C = 0) Profit = $70(50) + $50(0) = $3,500
Point 3 : (T = 30, C = 40) Profit = $70(30) + $50(40) = $4,100

◼ Because Point 3 returns the highest profit, this

is the optimal solution
◼ To find the coordinates for Point 3 accurately we
have to solve for the intersection of the two
constraint lines
◼ The details of this are on the following slide

© 2009 Prentice-Hall, Inc. 7 – 34

 Corner Point Solution Method

◼ Using the simultaneous equations method, we

multiply the painting equation by –2 and add it to
the carpentry equation
4T + 3C = 240 (carpentry line)
– 4T – 2C = –200 (painting line)
C = 40
◼ Substituting 40 for C in either of the original
equations allows us to determine the value of T
4T + (3)(40) = 240 (carpentry line)
4T + 120 = 240
T = 30
© 2009 Prentice-Hall, Inc. 7 – 35
 Summary of Graphical Solution
Methods
ISOPROFIT METHOD
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).
CORNER POINT METHOD
1. Graph all constraints and find the feasible region.
2. Find the corner points of the feasible reason.
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.

Table 7.3

© 2009 Prentice-Hall, Inc. 7 – 36

 Solving Flair Furniture’s LP Problem
Using QM for Windows and Excel

◼ Most organizations have access to

software to solve big LP problems
◼ While there are differences between
software implementations, the approach
each takes towards handling LP is
basically the same
◼ Once you are experienced in dealing with
computerized LP algorithms, you can
easily adjust to minor changes

© 2009 Prentice-Hall, Inc. 7 – 37

 Using QM for Windows

◼ First select the Linear Programming module

◼ Specify the number of constraints (non-negativity
is assumed)
◼ Specify the number of decision variables
◼ Specify whether the objective is to be maximized
or minimized
◼ For the Flair Furniture problem there are two
constraints, two decision variables, and the
objective is to maximize profit

© 2009 Prentice-Hall, Inc. 7 – 38

 Using QM for Windows

◼ Computer screen for input of data

Program 7.1A

© 2009 Prentice-Hall, Inc. 7 – 39

 Using QM for Windows

◼ Computer screen for input of data

Program 7.1B

© 2009 Prentice-Hall, Inc. 7 – 40

 Using QM for Windows

◼ Computer screen for output of solution

Program 7.1C

© 2009 Prentice-Hall, Inc. 7 – 41

 Using QM for Windows
◼ Graphical output of solution

Program 7.1D

© 2009 Prentice-Hall, Inc. 7 – 42

Solving Minimization Problems
◼ Many LP problems involve minimizing an
objective such as cost instead of
maximizing a profit function
◼ 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

© 2009 Prentice-Hall, Inc. 7 – 43

 Holiday Meal Turkey Ranch
◼ The Holiday Meal Turkey Ranch is considering
buying two different brands of turkey feed and
blending them to provide a good, low-cost diet for
its turkeys
Let
X1 = number of pounds of brand 1 feed purchased
X2 = number of pounds of brand 2 feed purchased

Minimize cost (in cents) = 2X1 + 3X2

subject to:
5X1 + 10X2 ≥ 90 ounces (ingredient constraint A)
4X1 + 3X2 ≥ 48 ounces (ingredient constraint B)
0.5X1 ≥ 1.5 ounces (ingredient constraint C)
X1 ≥ 0 (nonnegativity constraint)
X2 ≥ 0 (nonnegativity constraint)
© 2009 Prentice-Hall, Inc. 7 – 44
 Holiday Meal Turkey Ranch
◼ Holiday Meal Turkey Ranch data

COMPOSITION OF EACH POUND

OF FEED (OZ.) MINIMUM MONTHLY
REQUIREMENT PER
INGREDIENT BRAND 1 FEED BRAND 2 FEED TURKEY (OZ.)
A 5 10 90
B 4 3 48
C 0.5 0 1.5
Cost per pound 2 cents 3 cents

Table 7.4

© 2009 Prentice-Hall, Inc. 7 – 45

 Holiday Meal Turkey Ranch
X2
◼ Using the corner –
point method
◼ First we construct 20 –
the feasible Ingredient C Constraint

Pounds of Brand 2
solution region
15 –
◼ The optimal Feasible Region
solution will lie at a
10 –
on of the corners
as it would in a Ingredient B Constraint
maximization 5–
Ingredient A Constraint
b
problem
0 |– | | | c | |
5 10 15 20 25 X1
Figure 7.10 Pounds of Brand 1
© 2009 Prentice-Hall, Inc. 7 – 46
 Holiday Meal Turkey Ranch
◼ We solve for the values of the three corner points
◼ Point a is the intersection of ingredient constraints
C and B
4X1 + 3X2 = 48
X1 = 3
◼ Substituting 3 in the first equation, we find X2 = 12
◼ Solving for point b with basic algebra we find X1 =
8.4 and X2 = 4.8
◼ Solving for point c we find X1 = 18 and X2 = 0

© 2009 Prentice-Hall, Inc. 7 – 47

 Holiday Meal Turkey Ranch
◼ Substituting these value back into the objective
function we find

Cost = 2X1 + 3X2

Cost at point a = 2(3) + 3(12) = 42
Cost at point b = 2(8.4) + 3(4.8) = 31.2
Cost at point c = 2(18) + 3(0) = 36

◼ The lowest cost solution is to purchase 8.4

pounds of brand 1 feed and 4.8 pounds of brand 2
feed for a total cost of 31.2 cents per turkey

© 2009 Prentice-Hall, Inc. 7 – 48

 Holiday Meal Turkey Ranch
X2
◼ Using the isocost –
approach Feasible Region
◼ Choosing an 20 –
initial cost of 54

Pounds of Brand 2
cents, it is clear
15 –
improvement is
possible
10 –

5–

(X1 = 8.4, X2 = 4.8)

0 |– | | | | |
5 10 15 20 25 X1
Figure 7.11 Pounds of Brand 1
© 2009 Prentice-Hall, Inc. 7 – 49
 Holiday Meal Turkey Ranch
◼ QM for Windows can also be used to solve the
Holiday Meal Turkey Ranch problem

Program 7.3

© 2009 Prentice-Hall, Inc. 7 – 50

 Employee Scheduling Applications

◼ Assignment Problems
◼ Involve determining the most efficient way to
assign resources to tasks
◼ Objective may be to minimize travel times or
maximize assignment effectiveness
◼ Assignment problems are unique because they
have a coefficient of 0 or 1 associated with
each variable in the LP constraints and the
right-hand side of each constraint is always
equal to 1

© 2009 Prentice-Hall, Inc. 7 – 51

 Employee Scheduling Applications

◼ Ivan and Ivan law firm maintains a large staff of

young attorneys
◼ Ivan wants to make lawyer-to-client assignments
in the most effective manner
◼ He identifies four lawyers who could possibly be
assigned new cases
◼ Each lawyer can handle one new client
◼ The lawyers have different skills and special
interests
◼ The following table summarizes the lawyers
estimated effectiveness on new cases

© 2009 Prentice-Hall, Inc. 7 – 52

 Employee Scheduling Applications

◼ Effectiveness ratings
CLIENT’S CASE
CORPORATE
LAWYER DIVORCE MERGER EMBEZZLEMENT EXHIBITIONISM
Adams 6 2 8 5
Brooks 9 3 5 8
Carter 4 8 3 4
Darwin 6 7 6 4

1 if attorney i is assigned to case j

Let Xij =
0 otherwise
where i = 1, 2, 3, 4 stands for Adams, Brooks,
Carter, and Darwin respectively
j = 1, 2, 3, 4 stands for divorce, merger,
embezzlement, and exhibitionism © 2009 Prentice-Hall, Inc. 7 – 53
 Employee Scheduling Applications

◼ The LP formulation is

6X=
Maximize effectiveness 11 + 2X12 + 8X13 + 5X14 + 9X21 + 3X22
+ 5X23 + 8X24 + 4X31 + 8X32 + 3X33 + 4X
+ 6X41 + 7X42 + 6X43 + 4X44
subject to X11 + X21 + X31 + X41 = 1 (divorce case)
X12 + X22 + X32 + X42 = 1 (merger)
X13 + X23 + X33 + X43 = 1 (embezzlement)
X14 + X24 + X34 + X44 = 1 (exhibitionism)
X11 + X12 + X13 + X14 = 1 (Adams)
X21 + X22 + X23 + X24 = 1 (Brook)
X31 + X32 + X33 + X34 = 1 (Carter)
X41 + X42 + X43 + X44 = 1 (Darwin)
© 2009 Prentice-Hall, Inc. 7 – 54
 Employee Scheduling Applications

◼ Solving Ivan and Ivan’s assignment scheduling

LP problem using QM for Windows

Program 8.4
© 2009 Prentice-Hall, Inc. 7 – 55
 Four Special Cases in LP

◼ Four special cases and difficulties arise at

times when using the graphical approach
to solving LP problems
◼ Infeasibility
◼ Unboundedness
◼ Redundancy
◼ Alternate Optimal Solutions

© 2009 Prentice-Hall, Inc. 7 – 56

 Four Special Cases in LP
◼ No feasible solution
◼ Exists when there is no solution to the
problem that satisfies all the constraint
equations
◼ No feasible solution region exists
◼ This is a common occurrence in the real world
◼ Generally one or more constraints are relaxed
until a solution is found

© 2009 Prentice-Hall, Inc. 7 – 57

 Four Special Cases in LP

◼ A problem with no feasible

X1+2X2 <=6
solution 2X1+X2 <=8
X2
X1 >=7

8–
–
6–
–
Region Satisfying
4– Third Constraint
–
2–
–
0– | | | | | | | | | |
2 4 6 8 X1

Figure 7.12 Region Satisfying First Two Constraints

© 2009 Prentice-Hall, Inc. 7 – 58

 Four Special Cases in LP
◼ Unboundedness
◼ Sometimes a linear program will not have a
finite solution
◼ In a maximization problem, one or more
solution variables, and the profit, can be made
infinitely large without violating any
constraints
◼ In a graphical solution, the feasible region will
be open ended
◼ This usually means the problem has been
formulated improperly

© 2009 Prentice-Hall, Inc. 7 – 59

 Four Special Cases in LP
◼ A solution region unbounded to the right
X2

X1 ≥ 5
15 –

X2 ≤ 10
10 –

Feasible Region
5–
X1 + 2X2 ≥ 15

0 |– | | | |
5 10 15 X1

Figure 7.13
© 2009 Prentice-Hall, Inc. 7 – 60
 Four Special Cases in LP
◼ Redundancy
◼ A redundant constraint is one that does not
affect the feasible solution region
◼ One or more constraints may be more binding
◼ This is a very common occurrence in the real
world
◼ It causes no particular problems, but
eliminating redundant constraints simplifies
the model

© 2009 Prentice-Hall, Inc. 7 – 61

 Four Special Cases in LP
◼ A problem with X2
a redundant 30 –
constraint
25 –
2X1 + X2 ≤ 30
20 –
Redundant
Constraint
15 –
X1 ≤ 25

10 –
X1 + X2 ≤ 20
Feasible
5–
Region

0– | | | | | |
Figure 7.14 5 10 15 20 25 30 X1
© 2009 Prentice-Hall, Inc. 7 – 62
 Four Special Cases in LP

◼ Alternate Optimal Solutions

◼ Occasionally two or more optimal solutions
may exist
◼ Graphically this occurs when the objective
function’s isoprofit or isocost line runs
perfectly parallel to one of the constraints
◼ This actually allows management great
flexibility in deciding which combination to
select as the profit is the same at each
alternate solution

© 2009 Prentice-Hall, Inc. 7 – 63

 Four Special Cases in LP
◼ Example of X2
alternate 8–
optimal
solutions 7–

6 –A
Optimal Solution Consists of All
5– Combinations of X1 and X2 Along
Maximize 3X1 + 2X2 the AB Segment
Subj. To: 6X1 + 4X2 < 24 4–
X1 <3 3– Isoprofit Line for $8
X1, X 2 > 0
2–
B Isoprofit Line for $12
1 – Feasible Overlays Line Segment AB
Region
0– | | | | | | | |
Figure 7.15 1 2 3 4 5 6 7 8 X1

© 2009 Prentice-Hall, Inc. 7 – 64

 Sensitivity Analysis
◼ Optimal solutions to LP problems thus far have
been found under what are called deterministic
assumptions
◼ This means that we assume complete certainty in
the data and relationships of a problem
◼ But in the real world, conditions are dynamic and
changing
◼ We can analyze how sensitive a deterministic
solution is to changes in the assumptions of the
model
◼ This is called sensitivity analysis, postoptimality
analysis, parametric programming, or optimality
analysis

© 2009 Prentice-Hall, Inc. 7 – 65

 Sensitivity Analysis
◼ Sensitivity analysis often involves a series of
what-if? questions concerning constraints,
variable coefficients, and the objective function
◼ What if the profit for product 1 increases by 10%?
◼ What if less advertising money is available?
◼ One way to do this is the trial-and-error method
where values are changed and the entire model is
resolved
◼ The preferred way is to use an analytic
postoptimality analysis
◼ After a problem has been solved, we determine a
range of changes in problem parameters that will not
affect the optimal solution or change the variables in
the solution without re-solving the entire problem
© 2009 Prentice-Hall, Inc. 7 – 66
 Sensitivity Analysis
◼ Sensitivity analysis can be used to deal not
only with errors in estimating input
parameters to the LP model but also with
management’s experiments with possible
future changes in the firm that may affect
profits.

© 2009 Prentice-Hall, Inc. 7 – 67

 High Note Sound Company
◼ The High Note Sound Company manufactures
quality CD players and stereo receivers
◼ Products require a certain amount of skilled
artisanship which is in limited supply
◼ The firm has formulated the following product mix
LP model
Maximize profit = $50X1 + $120X2
Subject to 2X1 + 4X2 ≤ 80 (hours of electrician’s
time available)
3X1 + 1X2 ≤ 60 (hours of audio
technician’s time
available)
X1, X2 ≥ 0

© 2009 Prentice-Hall, Inc. 7 – 68

 High Note Sound Company
◼ The High Note Sound Company graphical solution
X2
(receivers)
60 –

– Optimal Solution at Point a

X1 = 0 CD Players
40 – X2 = 20 Receivers
Profits = $2,400
a = (0, 20) –
b = (16, 12)
20 –
Isoprofit Line: $2,400 = 50X1 + 120X2
10 –

0– | | | | | |
10 20 30 40 50 60 X1
Figure 7.16 c = (20, 0) (CD players)
© 2009 Prentice-Hall, Inc. 7 – 69
 Changes in the
Objective Function Coefficient
◼ In real-life problems, contribution rates in the
objective functions fluctuate periodically
◼ Graphically, this means that although the feasible
solution region remains exactly the same, the
slope of the isoprofit or isocost line will change
◼ We can often make modest increases or
decreases in the objective function coefficient of
any variable without changing the current optimal
corner point
◼ We need to know how much an objective function
coefficient can change before the optimal solution
would be at a different corner point

© 2009 Prentice-Hall, Inc. 7 – 70

 Changes in the
Objective Function Coefficient
◼ Changes in the receiver contribution coefficients
X2
40 –
Profit Line for 50X1 + 80X2
(Passes through Point b)
30 –
Profit Line for 50X1 + 120X2
(Passes through Point a)
20 –
b
a Profit Line for 50X1 + 150X2
10 – (Passes through Point a)

0– | | c | | | |
10 20 30 40 50 60 X1
Figure 7.17

© 2009 Prentice-Hall, Inc. 7 – 71

 QM for Windows and Changes in
Objective Function Coefficients
◼ Input and sensitivity analysis for High Note Sound
data

Program 7.5A

Program 7.5B

© 2009 Prentice-Hall, Inc. 7 – 72

 Changes in the
Technological Coefficients

◼ Changes in the technological coefficients often

reflect changes in the state of technology
◼ If the amount of resources needed to produce a
product changes, coefficients in the constraint
equations will change
◼ This does not change the objective function, but
it can produce a significant change in the shape
of the feasible region
◼ This may cause a change in the optimal solution

© 2009 Prentice-Hall, Inc. 7 – 73

 Changes in the
Technological Coefficients

◼ Change in the technological coefficients for the

High Note Sound Company
(a) Original Problem (b) Change in Circled (c) Change in Circled
Coefficient Coefficient
X2 X2 X2
60 – 60 – 60 –
Stereo Receivers

3X1 + 1X2 ≤ 60 2 X1 + 1X2 ≤ 60 3X1 + 1X2 ≤ 60

40 – 40 – 40 –
Optimal Still Optimal
Solution Optimal Solution
20 –a 20 –a 20 –
d
b 2X1 + 4X2 ≤ 80 2X1 + 4X2 ≤ 80 16 f g 2X1 + 5 X2 ≤ 80
– |c | | – | e | | | – |c | |
0 20 40 X1 0 20 30 40 X1 0 20 40 X1
CD Players

Figure 7.18

© 2009 Prentice-Hall, Inc. 7 – 74

 Changes in Resources or
Right-Hand-Side Values
◼ The right-hand-side values of the constraints
often represent resources available to the firm
◼ If additional resources were available, a higher
total profit could be realized
◼ Sensitivity analysis about resources will help
answer questions such as:
◼ How much should the company be willing to pay
for additional hours?
◼ Is it profitable to have some electricians work
overtime?
◼ Should we be willing to pay for more audio
technician time?
© 2009 Prentice-Hall, Inc. 7 – 75
 Changes in Resources or
Right-Hand-Side Values
◼ If the right-hand side of a constraint is
changed, the feasible region will change
(unless the constraint is redundant) and
often the optimal solution will change
◼ The amount of change (increase or
decrease) in the objective function value
that results from a unit change in one of
the resources available is called the dual
price or dual value

© 2009 Prentice-Hall, Inc. 7 – 76

 Changes in Resources or
Right-Hand-Side Values
◼ However, the amount of possible increase in the
right-hand side of a resource is limited
◼ If the number of hours increases beyond the
upper bound (or decreases below the lower
bound), then the objective function would no
longer increase (decrease) by the dual price.
◼ There may be excess (slack) hours of a resource
or the objective function may change by an
amount different from the dual price.
◼ Thus, the dual price is relevant only within limits.
◼ If the dual value of a constraint is zero
◼ The slack is positive, indicating unused resource
◼ Additional amount of resource will simply increase
the amount of slack.
◼ The upper limit of infinity indicates that adding
more hours would simply increase the amount of
slack.
© 2009 Prentice-Hall, Inc. 7 – 77
 Changes in the Electrician's Time
for High Note Sound

X2 (a)
60 – If the electricians’ hours are changed from 80 to
100, the new optimal solution is (0,25) with profit
of $3,000. The extra 20 hours resulted in an
increase in profit of $600 or $30/hour
40 –
Constraint Representing 60 Hours of
Audio Technician’s Time Resource
a
25 –
20 – b Changed Constraint Representing 100 Hours
of Electrician’s Time Resource

– | c | | |
0 20 40 50 60 X1

Figure 7.19

© 2009 Prentice-Hall, Inc. 7 – 78

 Changes in the Electrician's Time
for High Note Sound
If the hours are decreased to 60,
X2 (b)
the new solution is (0,15) and the
60 –
profit is $1,800. Reducing hours
by 20 results in a $600 decrease in
profit or $30/hour
40 –
Constraint Representing 60 Hours of
Audio Technician’s Time Resource

20 – Changed Constraint Representing 60 Hours

a of Electrician’s Time Resource
15 –
b

– c | | | |
0 20 30 40 60 X1

Figure 7.19

© 2009 Prentice-Hall, Inc. 7 – 79

 Changes in the Electrician's Time
for High Note Sound

X2 (c)
60 –
Changed Constraint Representing 240 Hours
of Electrician’s Time Resource

40 –

Constraint
Representing
20 – 60 Hours of Audio
Technician’s
Time Resource

– | | | | | |
0 20 40 60 80 100 120
X1
Figure 7.19

© 2009 Prentice-Hall, Inc. 7 – 80

 Changes in the Electrician's Time
for High Note Sound

◼ If total electrician time was increased to 240,

the optimal solution would be (0,60) with a
profit of $7,200. This is $2,400 (the original
solution) + $30 (dual price)*160 hours(240-80)
◼ If the hours increases beyond 240, then the
optimal solution would still be (0,60) and profit
would not increase. The extra time is slack during
which the electricians are not working

© 2009 Prentice-Hall, Inc. 7 – 81

 QM for Windows and Changes in
Right-Hand-Side Values
◼ Input and sensitivity analysis for High Note Sound
data

Program 7.5A

Program 7.5B

© 2009 Prentice-Hall, Inc. 7 – 82

Flair Furniture – Sensitivity
Analysis

Dual/Value RHS change Solution change

Carpentry/1.5 240→241 30/40: 410→

29.5/41: 411.5
Painting/.5 100→101 30/40: 410→
31.5/38: 410.5

Profit per item Solution Range

Table 7 6.67 → 10

Chair 5 3.5→ 5.25

© 2009 Prentice-Hall, Inc. 7 – 83

 Personal Mini Warehouses
1. For the optimal solution, how much is spent on
advertising?
2. For the optimal solution, how much square footage
will be used?
3. Would the solution change if the advertising budget
were only $300 instead of $400? Why?
4. What would the optimal solution be if the profit on
the large spaces were reduced from $50 to $45?
5. How much would earnings increase if the square
footage requirement were increased from 8,000 to
9,000?

1. 2*60 + 4*40 = 280 (note slack of 120 on advertising constraint)

2. 100*60 + 50*40 = 8,000 (no slack)
3. Advertising has a lower bound of 280 and upper bound of Infinity. 300 is within the
bounds so the solution does not change.
4. The profit on large spaces has a range of 40 to Infinity, 45 is within that range so the
solution would not change. However, earnings would be reduced from $3,800 to 45*60 +
20*40 = $3,500.
5. The dual price for square footage is .4 and the upper bound is 9,500. By increasing the
square footage by 1,000 we increase the earning by .4*1,000 = $400

© 2009 Prentice-Hall, Inc. 7 – 84

 Chapter 9

Linear Programming:
The Simplex Method

To accompany
Quantitative Analysis for Management, Tenth Edition,
by Render, Stair, and Hanna © 2008 Prentice-Hall, Inc.
Power Point slides created by Jeff Heyl © 2009 Prentice-Hall, 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
9.1 Introduction
9.2 How to Set Up the Initial Simplex
Solution
9.3 Simplex Solution Procedures
9.4 The Second Simplex Tableau
9.5 Developing the Third Tableau
9.6 Review of Procedures for Solving
LP Maximization Problems
9.7 Surplus and Artificial Variables

© 2009 Prentice-Hall, Inc. 9–3

 Chapter Outline
9.8 Solving Minimization Problems
9.9 Review of Procedures for Solving
LP Minimization Problems
9.10 Special Cases
9.11 Sensitivity Analysis with the
Simplex Tableau
9.12 The Dual
9.13 Karmarkar’s Algorithm

© 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 40 60 80 T
Figure 9.1 Number of Tables
© 2009 Prentice-Hall, Inc. 9 – 13
 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
s
it

le

bl
un

ns iab
n on

ns ria
n r

n t
m ti
m e

m n
m a
m r
lu it p

lu l va
lu uc

lu k v

lu sta
co rod

co lac
co rof

co on
co ea
R

C
P
P

S
Cj SOLUTION $70 $50 $0 $0 Profit per
MIX T C S1 S2 QUANTITY unit row
$0 S1 2 1 1 0 100 Constraint
equation rows
$0 S2 4 3 0 1 240
Gross
Zj $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
C 0
=
S1 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 0
S2 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 $50 $0 $0
SOLUTION
S1 S2 QUANTITY
MIX T C
$0 S1 2 1 1 0 100
$0 S2 4 3 0 1 240

© 2009 Prentice-Hall, Inc. 9 – 19

 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)
+ (profit per unit of S2) × (Substitution rate in row 2)

© 2009 Prentice-Hall, Inc. 9 – 21

 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.
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.
row The number at the intersection of
the pivot row and pivot column is the pivot
number.
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.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 S2 (RHS)
$0 S1 2 1 1 0 100
$0 S2 4 3 0 1 240
Zj $0 $0 $0 $0 $0
Cj - Zj $70 $50 $0 $0 total profit
Pivot column

Table 9.2
© 2009 Prentice-Hall, Inc. 9 – 29
 The Second Simplex Tableau
Step 2.
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 $50 $0 $0
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 $0
Cj - Zj $70 $50 $0 $0
Pivot column

Table 9.3

© 2009 Prentice-Hall, Inc. 9 – 31

 The Second Simplex Tableau
Step 3.
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 100
=1 = 0.5 = 0.5 =0 = 50
2 2 2 2 2

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.
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 S Row Pivot Number × in the New T Row
2

0 = 4 – (4) × (1)
1 = 3 – (4) × (0.5)
–2 = 0 – (4) × (0.5)
1 = 1 – (4) × (0)
40 = 240 – (4) × (50)

Cj SOLUTION MIX T C S1 S2 QUANTITY

$70 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
0
contains , necessary conditions for variables to
1
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.
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
 Completed $0 $15
second simplex tableau
–$35 $0

Cj $70 $50 $0 $0
SOLUTION QUANTITY
MIX T C S1 S2 (RHS)
$0 T 1 0.5 0.5 0 50
$0 S2 0 1 –2 1 40
Zj $70 $35 $35 $0 $3,500
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.
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.
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 : = 100 chairs
0.5
40
For the S2 row : = 40 chairs
1
© 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 QUANTITY
$70 T 1 0.5 0.5 0 50
$0 S2 0 1 –2 1 40
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.
3 The pivot row is replaced by dividing every
number in it by the pivot point number

0 1 −2 1 40
=0 =1 = −2 =1 = 40
1 1 1 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.
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.
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) + ($50)(40) = $4,100
And the net profit per unit row is now
COLUMN
T C S1 S2
Cj for column $70 $50
$0 $0
Zj for column $70 $50
$5 $15
Cj – Zj for column $0 $0 –
© 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 QUANTITY
$70 T 1 0 1.5 –0.5 30
$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 1 rewritten : 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 surplus units

© 2009 Prentice-Hall, Inc. 9 – 51

 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 1 completed : 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 + X2 = 1,000 lb
X1 ≤ 300 lb
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 –
E D| |C
0 |– | | |
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 ≥0

© 2009 Prentice-Hall, Inc. 9 – 63

 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) = $M
Zj (for X2 column) = $M(1) + $0(0) + $M(1) = $2M
Zj (for S1 column) = $M(0) + $0(1) + $M(0) = $0
Zj (for S2 column) = $M(0) + $0(0) + $M(–1) = –$M
Zj (for A1 column) = $M(1) + $0(0) + $M(0) = $M
Zj (for A2 column) = $M(0) + $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 –$M $ $

$0 M M
Cj – Zj for
–$M + $5 –$2M + $6 $0 $M $0 $0
column

© 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
=
0
S2
1,000
A1
150
A2
© 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 S1 1 0 1 0 0 0 300
$M A2 0 1 0 –1 0 1 150
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,000
1
300 (this is an undefined ratio,
For the S1 row = so we ignore it)
0
150 (smallest quotient,
For the A2 row = = 150 indicating pivot row)
1

 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 × in newly replaced row
number
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)
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)
© 2009 Prentice-Hall, Inc. 9 – 73
 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) = $M(–1) + $0(0) + $6(1) = –$M + 6
Zj (for total cost) = $M(850) + $0(300) + $6(150) = $850M + 900
COLUMN
X1 X2 S1 S2 A1 A2
Cj for column $5 $6 $0 $0 $M $M

Zj for column –$M +

$M $6 $0 $M – 6 $M
6
Cj – Zj for –$M + $2M –
–$M + $5 $0 $0
column $0 6 6 9 – 74
© 2009 Prentice-Hall, Inc.
 Developing the Second Tableau

 Second simplex tableau

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

$M A1 1 0 0 1 1 –1 850
$0 S1 1 0 1 0 0 0 300
Pivot number Pivot row
$6 X2 0 1 0 –1 0 1 150

Zj $850M +
$M $6 $0 $M – 6 $M –$M + 6
$900
Cj – Zj –$M + $5 $0 $0 –$M + $6 $0 $2M – 6
Pivot column

Table 9.8

© 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 = = 850
1
300
For the S1 row = = 300 (smallest ratio)
1
150
For the X 2 row = = undefined
0

 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)
550 = 850 – (1)(300) 150 = 150 – (0)(300)

© 2009 Prentice-Hall, Inc. 9 – 77

 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
COLUMN
X1 X2 S1 S2 A1 A2
Cj for column $5 $6 $0 $0 $M $M

Zj for column –$M +

$5 $6 –$M + 5 $M – 6 $M
6
Cj – Zj for $2M –
$0 $0 $M + 5 –$M + 6 $0
column 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 $0 $M $M
SOLUTION X1 X2 S1 S2 A1 A2
MIX QUANTITY

$M A1 0 0 –1 1 1 –1 550
Pivot number Pivot row
$5 X1 1 0 1 0 0 0 300
$6 X2 0 1 0 –1 0 1 150
Zj $5 $6 –$M + 5 $M – 6 $M –$M + 6 $550M + 2,400
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 X 1 row = (undefined)
0
150 (not considered
For the X 2 row = because it is
−1
negative)

© 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) + $5(300) + $6(700) = $5,700
COLUMN
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 $M –
$0 $0 $1 $0 $M
column 6
© 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 X1 X2 S1 S2 A1 A2
MIX 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 X1 X2 S1 S2 A1 A2
MIX 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 QUANTITY
$9 X2 –1 1 2 0 30
$0 S2 –2 0 –1 1 10
Zj –$9 $9 $18 $0 $270
Cj - Zj $15 $0 –$18 $0
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 :
−1
Negative ratios
unacceptable
10
Ratio for the S2 row :
−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 QUANTITY
MIX
$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 : = 40
0.25

20
For the S2 row : =5 Tie for the smallest
4 ratio indicates
degeneracy
10
For the S3 row : =5
2

© 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

 Sensitivity Analysis with the
Simplex Tableau
 Sensitivity analysis shows how the optimal
solution and the value of its objective function
change given changes in various inputs to the
problem
 Computer programs handling LP problems of all
sizes provide sensitivity analysis as an important
output feature
 Those programs use the information provided in
the final simplex tableau to compute ranges for
the objective function coefficients and ranges for
the RHS values
 They also provide “shadow prices,” a concept we
will introduce in this section

© 2009 Prentice-Hall, Inc. 9 – 98

 High Note Sound Company Revisited

 You will recall the model formulation is

Maximize profit = $50X1 +

$120X2
subject to 2X1 + 4X2 ≤
80
(hours of
electrician time)
 And the optimal solution is
3X1 + 1X2 ≤
60
X2 = 20 receivers Basic
(hours of
variablestime)
S2 = 40 hours slack in technician time technician
X1 = 0 CD players Nonbasic
variables
S1 = 0 hours slack in electrician time

© 2009 Prentice-Hall, Inc. 9 – 99

 High Note Sound Company Revisited
 High Note Sound Company graphical solution
X2
(receivers)
60 –

– Optimal Solution at Point a

40 – X1 = 0 CD Players
X2 = 20 Receivers
–
Profits = $2,400
a = (0, 20)
20 –
b = (16, 12)
10 –
Isoprofit Line: $2,400 = 50X1 + 120X2
0–

| | | | | |
10 20 30 40 50 60 X1
Figure 9.4 c = (20, 0) (CD players)
© 2009 Prentice-Hall, Inc. 9 – 100
 Changes in the
Objective Function Coefficient
 Optimal solution by the simplex method

Cj $50 $120 $0 $0
SOLUTION X1 X2 S1 S2 QUANTITY
MIX
$120 X2 0.5 1 0.25 0 20
$0 S2 2.5 0 –0.25 1 40
Zj $60 $120 $30 $0 $2,400
Cj - Zj –$10 $0 –$30 $0

Table 9.15

© 2009 Prentice-Hall, Inc. 9 – 101

 Changes in the
Objective Function Coefficient
 Nonbasic objective function coefficient
 The goal is to find out how sensitive the
problem’s optimal solution is to changes in the
contribution rates of variables not currently in
the basis
 How much would the objective function
coefficients have to change before X1 or S1
would enter the solution mix and replace one
of the basic variables?
 The answer lies in the Cj – Zj row of the final
simplex tableau

© 2009 Prentice-Hall, Inc. 9 – 102

 Changes in the
Objective Function Coefficient
 This is a maximization problem so the basis will not
change unless the Cj – Zj value of one of the
nonbasic variables becomes greater than 0
 The values in the basis will not change as long as Cj
≤ Zj
 The solution will not change as long as X1 does not
exceed $60 and the contribution rate of S2 does not
exceed $30
 These values can also be made smaller without limit
in this situation
 So the range of insignificance for the nonbasic
variables is
− ∞ ≤ C j ( for X 1 ) ≤ $60 − ∞ ≤ C j ( for S1 ) ≤ $30
© 2009 Prentice-Hall, Inc. 9 – 103
 Changes in the
Objective Function Coefficient
 Basic objective function coefficient
 Sensitivity analysis on objective function
coefficients of variables in the basis or
solution mix is slightly more complex
 A change in the profit or cost of a basic
variable can affect the Cj – Zj values for all
nonbasic variables
 That’s because the Cj value is in both the row
and column
 This then impacts the Cj – Zj row

© 2009 Prentice-Hall, Inc. 9 – 104

 Changes in the
Objective Function Coefficient
 Consider a change in the profit contribution of
stereo receivers
 The current coefficient is $120
 The changed coefficient will be represented as ∆
 The revised final tableau will then be

Cj $50 $120 + ∆ $0 $0
SOLUTION X1 X2 S1 S2
MIX QUANTITY

$120 + ∆ X2 0.5 1 0.25 0 20

$0 S2 2.5 0 –0.25 1 40
Zj $60 + 0.5∆ $120 + ∆ $30 + 0.25∆ $0 $2,400 + 20∆

Cj - Zj –$10 –
$0 –$30 – 0.25∆ $0
0.5∆
Table 9.16

© 2009 Prentice-Hall, Inc. 9 – 105

 Changes in the
Objective Function Coefficient
 The new Cj – Zj values in the table were
determined in the same way as previous
examples
 How may the value of ∆ vary so that all Cj – Zj
entries remain negative?
 To find out, solve for ∆ in each column
–10 – 0.5∆ ≤ 0
–10 ≤ 0.5∆
–20 ≤ ∆ or ∆ ≥ –20
 This inequality means the optimal solution will not
change unless X2’s profit coefficient decreases by at
least $20, ∆ = –20
© 2009 Prentice-Hall, Inc. 9 – 106
 Changes in the
Objective Function Coefficient
 Variable X1 will not enter the basis unless the
profit per receiver drops to $100 or less
 For the S1 column

–30 – 0.25∆ ≤ 0
–30 ≤ 0.25∆
–120 ≤ ∆ or ∆ ≥ –120

 Since the first inequality is more binding, we can

say that the range of optimality for X2’s profit
coefficient is
$100 ≤ C j ( for X 2 ) ≤ ∞

© 2009 Prentice-Hall, Inc. 9 – 107

 Changes in the
Objective Function Coefficient
 In larger problems, we would use this procedure
to test for the range of optimality of every real
decision variable in the final solution mix
 Using this procedure helps us avoid the time-
consuming process of reformulating and
resolving the entire LP problem each time a small
change occurs
 Within the bounds, changes in profit coefficients
will not force a change in the optimal solution
 The value of the objective function will change,
but this is a comparatively simple calculation

© 2009 Prentice-Hall, Inc. 9 – 108

Changes in Resources or RHS Values

 Making changes in the RHS values of

constraints result in changes in the feasible
region and often the optimal solution
 Shadow prices
 How much should a firm be willing to pay for
one additional unit of a resource?
 This is called the shadow price
 Shadow pricing provides an important piece of
economic information
 This information is available in the final
tableau

© 2009 Prentice-Hall, Inc. 9 – 109

 Changes in Resources or RHS Values

 Final tableau for High Note Sound

Cj $50 $120 $0 $0
SOLUTION X1 X2 S1 S2 QUANTITY
MIX
$120 X2 0.5 1 0.25 0 20
$0 S2 2.5 0 –0.25 1 40
Zj $60 $120 $30 $0 $2,400
Cj - Zj –$10 $0 –$30 $0

Objective function increases by $30

if 1 additional hour of electricians’
time is made available

Table 9.17

© 2009 Prentice-Hall, Inc. 9 – 110

Changes in Resources or RHS Values

 An important property of the Cj – Zj row is that the

negatives of the numbers in its slack variable (Si)
columns provide us with shadow prices
 A shadow price is the change in value of the
objective function from an increase of one unit of
a scarce resource
 High Note Sound is considering hiring an extra
electrician at $22 per hour
 In the final tableau we see S1 (electricians’ time) is
fully utilized and has a Cj – Zj value of –$30
 They should hire the electrician as the firm will
net $8 (= $30 – $22)
© 2009 Prentice-Hall, Inc. 9 – 111
Changes in Resources or RHS Values

 Should High Note Sound hire a part-time audio

technician at $14 per hour?
 In the final tableau we see S2 (audio technician
time) has slack capacity (40 hours) a Cj – Zj value
of $0
 Thus there would be no benefit to hiring an
additional audio technician

© 2009 Prentice-Hall, Inc. 9 – 112

Changes in Resources or RHS Values

 Right-hand side ranging

 We can’t add an unlimited amount of a
resource without eventually violating one of
the other constraints
 Right-hand-side ranging tells us how much we
can change the RHS of a scarce resource
without changing the shadow price
 Ranging is simple in that it resembles the
simplex process

© 2009 Prentice-Hall, Inc. 9 – 113

Changes in Resources or RHS Values

 This table repeats some of the information from

the final tableau for High Note Sound and
includes the ratios

QUANTITY S1 RATIO

20 0.25 20/0.25 = 80

40 –0.25 40/–0.25 = –160

 The smallest positive ratio (80 in this example)

tells us how many hours the electricians’ time
can be reduced without altering the current
solution mix
© 2009 Prentice-Hall, Inc. 9 – 114
Changes in Resources or RHS Values

 The smallest negative ratio (–160) tells us the

number of hours that can be added to the
resource before the solution mix changes
 In this case, that’s 160 hours
 So the range over which the shadow price for
electricians’ time is valid is 0 to 240 hours
 The audio technician resource is slightly different
 There is slack in this resource (S2 = 40) so we can
reduce the amount available by 40 before a
shortage occurs
 However, we can increase it indefinitely with no
change in the solution

© 2009 Prentice-Hall, Inc. 9 – 115

Changes in Resources or RHS Values

 The substitution rates in the slack variable

column can also be used to determine the actual
values of the solution mix variables if the right-
hand-side of a constraint is changed using the
following relationship

New Original Substitution Change in

quantity = quantity + rate the RHS

© 2009 Prentice-Hall, Inc. 9 – 116

Changes in Resources or RHS Values

 For example, if 12 more electrician hours were

made available, the new values in the quantity
column of the simplex tableau are found as
follows
ORIGINAL QUANTITY S1 NEW QUANTITY
20 0.25 20 + 0.25(12) = 23
40 –0.25 40 + (–0.25)(12) = 37

 If 12 hours were added, X2 = 23 and S2 = 37

 Total profit would be 50(0) + 120(23) = $2,760, an
increase of $360
 This of course, is also equal to the shadow price
of $30 times the 12 additional hours
© 2009 Prentice-Hall, Inc. 9 – 117
 Sensitivity Analysis by Computer

 Solver in Excel has the capability of producing

sensitivity analysis that includes the shadow
prices of resources
 The following slides present the solution to the
High Note Sound problem and the sensitivity
report showing shadow prices and ranges

© 2009 Prentice-Hall, Inc. 9 – 118

Sensitivity Analysis by Computer

Program 9.1a
© 2009 Prentice-Hall, Inc. 9 – 119
 Sensitivity Analysis by Computer

Program 9.1b

© 2009 Prentice-Hall, Inc. 9 – 120

 The Dual
 Every LP problem has another LP problem
associated with it called the dual
 The first way of stating a problem (what we have
done so far) is called the primal
 The second way of stating it is called the dual
 The solutions to the primal and dual are
equivalent, but they are derived through
alternative procedures
 The dual contains economic information useful to
managers and may be easier to formulate

© 2009 Prentice-Hall, Inc. 9 – 121

 The Dual
 Generally, if the LP primal is a maximize profit
problem with less-than-or-equal-to resource
constraints, the dual will involve minimizing total
opportunity cost subject to greater-than-or-equal-
to product profit constraints
 Formulating a dual problem is not complex and
once formulated, it is solved using the same
procedure as a regular LP problem

© 2009 Prentice-Hall, Inc. 9 – 122

 The Dual
 Illustrating the primal-dual relationship with the
High Note Sound Company data
 The primal problem is to determine the best
production mix between CD players (X1) and
receivers (X2) to maximize profit
Maximize profit = $50X1 +
$120X2
subject to 2X1 + 4X2 ≤
80
(hours of
available
electrician time)
3X1 + 1X2 ≤
60
(hours© 2009
of Prentice-Hall,
audio Inc. 9 – 123
 The Dual
 The dual of this problem has the objective of
minimizing the opportunity cost of not using the
resources in an optimal manner
 The variables in the dual are
U1 = potential hourly contribution of
electrician time, or the dual value of 1
hour of electrician time
U2 = the imputed worth of audio technician
time, or the dual of technician resource
 Each constraint in the primal problem will have a
corresponding variable in the dual and each
decision variable in the primal will have a
corresponding constraint in the dual
© 2009 Prentice-Hall, Inc. 9 – 124
 The Dual
 The RHS quantities of the primal constraints
become the dual’s objective function coefficients
 The total opportunity cost will be represented by
the function
Minimize opportunity cost = 80U1 + 60U2
 The corresponding dual constraints are formed
from the transpose of the primal constraint
coefficients
2 U1 + 3 U2 ≥ 50 Primal profit coefficients
4 U1 + 1 U2 ≥ 120 Coefficients from the second
primal constraint
Coefficients from the first
primal constraint
© 2009 Prentice-Hall, Inc. 9 – 125
 The Dual
 The first constraint says that the total imputed
value or potential worth of the scarce resources
needed to produce a CD player must be at least
equal to the profit derived from the product
 The second constraint makes an analogous
statement for the stereo receiver product

© 2009 Prentice-Hall, Inc. 9 – 126

 Steps to Form the Dual
 If the primal is a maximization problem in the
standard form, the dual is a minimization, and
vice versa
 The RHS values of the primal constraints become
the dual’s objective coefficients
 The primal objective function coefficients
become the RHS values of the dual constraints
 The transpose of the primal constraint
coefficients become the dual constraint
coefficients
 Constraint inequality signs are reversed

© 2009 Prentice-Hall, Inc. 9 – 127

 Solving the Dual of the High Note
Sound Company Problem
 The formulation can be restated as

Minimize
opportunity = 80U1 + 60U2 + 0S1 + 0S2 + MA1 + MA2
cost
subject to:
2U1 + 3U2 – 0S1 + 1A1 = 50
4U1 + 1U2 – 0S2 + 1A2 = 120

© 2009 Prentice-Hall, Inc. 9 – 128

 Solving the Dual of the High Note
Sound Company Problem
 The first and second tableaus

Cj 80 60 0 0 M M
SOLUTION U1 U2 S1 S2 A1 A2 QUANTITY
MIX
First A1
$M 2 3 –1 0 1 0 50
tableau
$M A2 4 1 0 –1 0 1 120
Zj $6M $4M –$M –$M $M $M $170M
Cj – Zj 80 – 6M 60 – 4M M M 0 0
Second U1
$80 1 1.5 –0.5 0 0.5 0 25
tableau
$M A2 0 –5 2 –1 –2 1 20
$120 – $2,000 + 20M
Xj $80 –$40 + 2M –$M $40 – 2M $M
5M
Cj – Xj 0 5M – 60 –2M + 40 M 3M – 40 0

Table 9.18

© 2009 Prentice-Hall, Inc. 9 – 129

 Solving the Dual of the High Note
Sound Company Problem
 Comparison of the primal and dual optimal
tableaus Primal’s Optimal Solution
Cj $50 $120 $0 $0
Solution Mix X1 X2 S1 S2 Quantity
$120 X2 0.5 1 0.25 0 20
$0 S2 2.5 0 –0.25 1 40
Zj 60 120 30 0 $2,400
Cj – Zj –10 0 –30 0

Dual’s Optimal Solution

Cj 80 60 0 0 M M
Solution Mix U1 U2 S1 S2 A1 A2 Quantity
80 U1 1 0.25 0 –0.25 0 0.5 30
0 S1 0 –2.5 1 –0.5 –1 0.25 10
Zj 80 20 0 –20 0 20 $2,400
Cj – Zj 0 40 0 20 M M – 20
Figure 9.5
© 2009 Prentice-Hall, Inc. 9 – 130
 Solving the Dual of the High Note
Sound Company Problem
 In the final simplex tableau of a primal problem,
the absolute values of the numbers in the Cj – Zj
row under the slack variables represent the
solutions to the dual problem
 They are shadow prices in the primal solution
and marginal profits in the dual
 The absolute value of the numbers of the Cj – Zj
values of the slack variables represent the
optimal values of the primal X1 and X2 variables
 The maximum opportunity cost derived in the
dual must always equal the maximum profit
derived in the primal

© 2009 Prentice-Hall, Inc. 9 – 131

 Karmakar’s Algorithm
 In 1984, Narendra Karmakar developed a new
method of solving linear programming problems
called the Karmakar algorithm
 The simplex method follows a path of points on
the outside edge of feasible space
 Karmakar’s algorithm works by following a path a
points inside the feasible space
 It is much more efficient than the simplex method
requiring less computer time to solve problems
 It can also handle extremely large problems
allowing organizations to solve previously
unsolvable problems

© 2009 Prentice-Hall, Inc. 9 – 132

 Chapter 8

Linear Programming
Applications

To accompany
Quantitative Analysis for Management, Eleventh Edition,
by Render, Stair, and Hanna
Power Point slides created by Brian Peterson
 Marketing Applications
 Linear programming models have been
used in the advertising field as a decision
aid in selecting an effective media mix.
 Media selection problems can be
approached with LP from two perspectives:
 Maximize audience exposure.
 Minimize advertising costs.

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-2

 Win Big Gambling Club
 The Win Big Gambling Club promotes gambling
junkets to the Bahamas.
 It has $8,000 per week to spend on advertising.
 Its goal is to reach the largest possible high-
potential audience.
 Media types and audience figures are shown in
the following table.
 It needs to place at least five radio spots per week.
 No more than $1,800 can be spent on radio
advertising each week.

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-3

 Win Big Gambling Club
Advertising options

AUDIENCE COST PER MAXIMUM ADS

MEDIUM REACHED PER AD AD ($) PER WEEK
TV spot (1 minute) 5,000 800 12
Daily newspaper (full-
8,500 925 5
page ad)
Radio spot (30
2,400 290 25
seconds, prime time)
Radio spot (1 minute,
2,800 380 20
afternoon)

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-4

 Win Big Gambling Club
The problem formulation is
X1 = number of 1-minute TV spots each week
X2 = number of daily paper ads each week
X3 = number of 30-second radio spots each week
X4 = number of 1-minute radio spots each week
Objective:
Maximize audience coverage = 5,000X1 + 8,500X2 + 2,400X3 + 2,800X4
Subject to X1 ≤ 12 (max TV spots/wk)
X2 ≤ 5 (max newspaper ads/wk)
X3 ≤ 25 (max 30-sec radio spots ads/wk)
X4 ≤ 20 (max newspaper ads/wk)
800X1 + 925X2 + 290X3 + 380X4 ≤ $8,000 (weekly advertising budget)
X3 + X4 ≥ 5 (min radio spots contracted)
290X3 + 380X4 ≤ $1,800 (max dollars spent on radio)
X 1, X 2, X 3, X 4 ≥ 0

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-5

 Win Big Gambling Club
Solution in Excel 2010

Program 8.1

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-6

 Manufacturing Applications
 Production Mix
 LP can be used to plan the optimal mix of
products to manufacture.
 Company must meet a myriad of constraints,
ranging from financial concerns to sales
demand to material contracts to union labor
demands.
 Its primary goal is to generate the largest profit
possible.

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-7

 Fifth Avenue Industries
 Fifth Avenue Industries produces four varieties of
ties:
 One is expensive all-silk
 One is all-polyester
 Two are polyester and cotton blends
 The table on the below shows the cost and
availability of the three materials used in the
production process:

MATERIAL AVAILABLE PER

MATERIAL COST PER YARD ($) MONTH (YARDS)
Silk 24 1,200
Polyester 6 3,000
Cotton 9 1,600

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-8

 Fifth Avenue Industries
 The firm has contracts with several major
department store chains to supply ties.
 Contracts require a minimum number of ties but
may be increased if demand increases.
 Fifth Avenue’s goal is to maximize monthly profit
given the following decision variables.

X1 = number of all-silk ties produced per month

X2 = number all-polyester ties
X3 = number of blend 1 polyester-cotton ties
X4 = number of blend 2 silk-cotton ties

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-9

 Fifth Avenue Industries Data

MATERIAL
SELLING MONTHLY REQUIRED
VARIETY OF PRICE PER CONTRACT MONTHLY PER TIE MATERIAL
TIE TIE ($) MINIMUM DEMAND (YARDS) REQUIREMENTS
All silk 19.24 5,000 7,000 0.125 100% silk

All polyester 8.70 10,000 14,000 0.08 100% polyester

Poly – cotton 50% polyester –

9.52 13,000 16,000 0.10
blend 1 50% cotton

Silk-cotton 60% silk - 40%

10.64 5,000 8,500 0.11
blend 2 cotton

Table 8.1

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-10

 Fifth Avenue Industries
 Fifth Avenue also has to calculate profit per tie
for the objective function.

SELLING MATERIAL MATERIAL

PRICE REQUIRED PER COST PER COST PER PROFIT
VARIETY OF TIE PER TIE ($) TIE (YARDS) YARD ($) TIE ($) PER TIE ($)
All silk $19.24 0.125 $24 $3.00 $16.24
All polyester $8.70 0.08 $6 $0.48 $8.22
Poly-cotton
$9.52 0.05 $6 $0.30
blend 1
0.05 $9 $0.45 $8.77
Silk – cotton
$10.64 0.06 $24 $1.44
blend 2
0.06 $9 $0.54 $8.66

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-11

 Fifth Avenue Industries
The complete Fifth Avenue Industries Model
Objective function
Maximize profit = $16.24X1 + $8.22X2 + $8.77X3 + $8.66X4
Subject to 0.125X1+ 0.066X4 ≤ 1200 (yds of silk)
0.08X2 + 0.05X3 ≤ 3,000 (yds of polyester)
0.05X3 + 0.44X4 ≤ 1,600 (yds of cotton)
X1 ≥ 5,000 (contract min for silk)
X1 ≤ 7,000 (contract min)
X2 ≥ 10,000 (contract min for all polyester)
X2 ≤ 14,000 (contract max)
X3 ≥ 13,000 (contract mini for blend 1)
X3 ≤ 16,000 (contract max)
X4 ≥ 5,000 (contract mini for blend 2)
X4 ≤ 8,500 (contract max)
X 1, X 2, X 3, X 4 ≥ 0
Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-12
 Fifth Avenue Solution in Excel
2010

Program 8.3

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-13

 Financial Applications
 Portfolio Selection
 Bank, investment funds, and insurance
companies often have to select specific
investments from a variety of alternatives.
 The manager’s overall objective is generally to
maximize the potential return on the
investment given a set of legal, policy, or risk
restraints.

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-14

 International City Trust
 International City Trust (ICT) invests in short-term
trade credits, corporate bonds, gold stocks, and
construction loans.
 The board of directors has placed limits on how
much can be invested in each area:

INTEREST MAXIMUM INVESTMENT

INVESTMENT EARNED (%) ($ MILLIONS)
Trade credit 7 1.0
Corporate bonds 11 2.5
Gold stocks 19 1.5
Construction loans 15 1.8

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-15

 International City Trust
 ICT has $5 million to invest and wants to
accomplish two things:
 Maximize the return on investment over the next six
months.
 Satisfy the diversification requirements set by the
board.
 The board has also decided that at least 55% of
the funds must be invested in gold stocks and
construction loans and no less than 15% be
invested in trade credit.

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-16

 International City Trust
The variables in the model are:

X1 = dollars invested in trade credit

X2 = dollars invested in corporate bonds
X3 = dollars invested in gold stocks
X4 = dollars invested in construction loans

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-17

 International City Trust
Objective:
Maximize
dollars of
interest = 0.07X1 + 0.11X2 + 0.19X3 + 0.15X4
earned

subject to: X1 ≤ 1,000,000

X2 ≤ 2,500,000
X3 ≤ 1,500,000
X4 ≤ 1,800,000
X3 + X 4 ≥ 0.55(X1 + X2 + X3 + X4)
X1 ≥ 0.15(X1 + X2 + X3 + X4)
X1 + X2 + X3 + X 4 ≤ 5,000,000
X 1, X 2, X 3, X 4 ≥ 0

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-18

 International City Trust
 The optimal solution to the ICT is to make the
following investments:
X1 = $750,000
X2 = $950,000
X3 = $1,500,000
X4 = $1,800,000
 The total interest earned with this plan is
$712,000.

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-19

 ICT Portfolio Solution in Excel
2010

Program 8.6

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 8-20

 Chapter 10
Transportation and
Assignment Models

To accompany
Quantitative Analysis for Management, Tenth Edition,
by Render, Stair, and Hanna © 2008 Prentice-Hall, Inc.
Power Point slides created by Jeff Heyl © 2009 Prentice-Hall, Inc.
 Learning Objectives
After completing this chapter, students will be able to:

1. Structure special LP problems using the

transportation and assignment models
2. Use the northwest corner, VAM, MODI, and
stepping-stone methods
3. Solve facility location and other application
problems with transportation models
4. Solve assignment problems with the
Hungarian (matrix reduction) method

© 2009 Prentice-Hall, Inc. 10 – 2

 Chapter Outline
10.1 Introduction
10.2 Setting Up a Transportation Problem
10.3 Developing an Initial Solution: Northwest
Corner Rule
10.4 Stepping-Stone Method: Finding a
Least-Cost Solution
10.5 MODI Method
10.6 Vogel’s Approximation Method: Another
Way to Find an Initial Solution
10.7 Unbalanced Transportation Problems

© 2009 Prentice-Hall, Inc. 10 – 3

 Chapter Outline
10.8 Degeneracy in Transportation Problems
10.9 More Than One Optimal Solution
10.10 Maximization Transportation Problems
10.11 Unacceptable or Prohibited Routes
10.12 Facility Location Analysis
10.13 Assignment Model Approach
10.14 Unbalanced Assignment Problems
10.15 Maximization Assignment Problems

© 2009 Prentice-Hall, Inc. 10 – 4

 Introduction
 In this chapter we will explore two special
linear programming models
 The transportation model
 The assignment model
 Because of their structure, they can be
solved more efficiently than the simplex
method
 These problems are members of a category
of LP techniques called network flow
problems

© 2009 Prentice-Hall, Inc. 10 – 5

 Introduction
 Transportation model
 The transportation problem deals with the
distribution of goods from several points of
supply (sources)
sources to a number of points of
demand (destinations)
destinations
 Usually we are given the capacity of goods at
each source and the requirements at each
destination
 Typically the objective is to minimize total
transportation and production costs

© 2009 Prentice-Hall, Inc. 10 – 6

 Introduction
 Example of a transportation problem in a network
format
Factories Warehouses
(Sources) (Destinations)

100 Units Des Moines Albuquerque 300 Units

300 Units Evansville Boston 200 Units

300 Units Fort Lauderdale Cleveland 200 Units

Capacities Shipping Routes Requirements

Figure 10.1
© 2009 Prentice-Hall, Inc. 10 – 7
 Introduction
 Assignment model
 The assignment problem refers to the class of
LP problems that involve determining the most
efficient assignment of resources to tasks
 The objective is most often to minimize total
costs or total time to perform the tasks at hand
 One important characteristic of assignment
problems is that only one job or worker can be
assigned to one machine or project

© 2009 Prentice-Hall, Inc. 10 – 8

 Introduction
 Special-purpose algorithms
 Although standard LP methods can be used to
solve transportation and assignment problems,
special-purpose algorithms have been
developed that are more efficient
 They still involve finding and initial solution and
developing improved solutions until an optimal
solution is reached
 They are fairly simple in terms of computation

© 2009 Prentice-Hall, Inc. 10 – 9

 Introduction
 Streamlined versions of the simplex method are
important for two reasons
1. Their computation times are generally 100 times faster
2. They require less computer memory (and hence can
permit larger problems to be solved)
 Two common techniques for developing initial
solutions are the northwest corner method and
Vogel’s approximation
 The initial solution is evaluated using either the
stepping-stone method or the modified
distribution (MODI) method
 We also introduce a solution procedure called the
Hungarian method,
method Flood’s technique,
technique or the
reduced matrix method
© 2009 Prentice-Hall, Inc. 10 – 10
 Setting Up a Transportation Problem

 The Executive Furniture Corporation

manufactures office desks at three locations: Des
Moines, Evansville, and Fort Lauderdale
 The firm distributes the desks through regional
warehouses located in Boston, Albuquerque, and
Cleveland
 Estimates of the monthly production capacity of
each factory and the desks needed at each
warehouse are shown in Figure 10.1

© 2009 Prentice-Hall, Inc. 10 – 11

 Setting Up a Transportation Problem

 Production costs are the same at the three

factories so the only relevant costs are shipping
from each source to each destination
 Costs are constant no matter the quantity
shipped
 The transportation problem can be described as
how to select the shipping routes to be used and
the number of desks to be shipped on each route
so as to minimize total transportation cost
 Restrictions regarding factory capacities and
warehouse requirements must be observed

© 2009 Prentice-Hall, Inc. 10 – 12

 Setting Up a Transportation Problem

 The first step is setting up the transportation

table
 Its purpose is to summarize all the relevant data
and keep track of algorithm computations

Transportation costs per desk for Executive Furniture

TO
FROM ALBUQUERQUE BOSTON CLEVELAND

DES MOINES $5 $4 $3
EVANSVILLE $8 $4 $3
FORT LAUDERDALE $9 $7 $5

Table 10.1

© 2009 Prentice-Hall, Inc. 10 – 13

 Setting Up a Transportation Problem

 Geographical locations of Executive Furniture’s

factories and warehouses

Boston

Cleveland
Factory
Des Moines
Evanston Warehouse

Albuquerque

Fort Lauderdale

Figure 10.2

© 2009 Prentice-Hall, Inc. 10 – 14

 Setting Up a Transportation Problem

Des Moines
 Transportation table for Executive Furniture capacity
constraint

TO WAREHOUSE WAREHOUSE WAREHOUSE

AT AT AT FACTORY
FROM ALBUQUERQUE BOSTON CLEVELAND CAPACITY

DES MOINES $5 $4 $3
100
FACTORY

EVANSVILLE $8 $4 $3
300
FACTORY

FORT LAUDERDALE $9 $7 $5
300
FACTORY

WAREHOUSE
300 200 200 700
REQUIREMENTS
Cell representing a
Table 10.2 Total supply source-to-destination
Cost of shipping 1 unit from Cleveland (Evansville to Cleveland)
and demand
Fort Lauderdale factory to warehouse shipping assignment
Boston warehouse demand that could be made
© 2009 Prentice-Hall, Inc. 10 – 15
 Setting Up a Transportation Problem

 In this table, total factory supply exactly

equals total warehouse demand
 When equal demand and supply occur, a
balanced problem is said to exist
 This is uncommon in the real world and
we have techniques to deal with
unbalanced problems

© 2009 Prentice-Hall, Inc. 10 – 16

 Developing an Initial Solution:
Northwest Corner Rule
 Once we have arranged the data in a table, we
must establish an initial feasible solution
 One systematic approach is known as the
northwest corner rule
 Start in the upper left-hand cell and allocate units
to shipping routes as follows
1. Exhaust the supply (factory capacity) of each row
before moving down to the next row
2. Exhaust the demand (warehouse) requirements of
each column before moving to the right to the next
column
3. Check that all supply and demand requirements are
met.
 In this problem it takes five steps to make the
initial shipping assignments © 2009 Prentice-Hall, Inc. 10 – 17
 Developing an Initial Solution:
Northwest Corner Rule
1. Beginning in the upper left hand corner, we
assign 100 units from Des Moines to
Albuquerque. This exhaust the supply from Des
Moines but leaves Albuquerque 200 desks short.
We move to the second row in the same column.
TO ALBUQUERQUE BOSTON CLEVELAND FACTORY
FROM (A) (B) (C) CAPACITY

DES MOINES $5 $4 $3
100 100
(D)

EVANSVILLE $8 $4 $3
300
(E)

FORT LAUDERDALE $9 $7 $5
300
(F)

WAREHOUSE
300 200 200 700
REQUIREMENTS

© 2009 Prentice-Hall, Inc. 10 – 18

 Developing an Initial Solution:
Northwest Corner Rule
2. Assign 200 units from Evansville to Albuquerque.
This meets Albuquerque’s demand. Evansville
has 100 units remaining so we move to the right
to the next column of the second row.

TO ALBUQUERQUE BOSTON CLEVELAND FACTORY

FROM (A) (B) (C) CAPACITY

DES MOINES $5 $4 $3
100 100
(D)

EVANSVILLE $8 $4 $3
200 300
(E)

FORT LAUDERDALE $9 $7 $5
300
(F)

WAREHOUSE
300 200 200 700
REQUIREMENTS

© 2009 Prentice-Hall, Inc. 10 – 19

 Developing an Initial Solution:
Northwest Corner Rule
3. Assign 100 units from Evansville to Boston. The
Evansville supply has now been exhausted but
Boston is still 100 units short. We move down
vertically to the next row in the Boston column.

TO ALBUQUERQUE BOSTON CLEVELAND FACTORY

FROM (A) (B) (C) CAPACITY

DES MOINES $5 $4 $3
100 100
(D)

EVANSVILLE $8 $4 $3
200 100 300
(E)

FORT LAUDERDALE $9 $7 $5
300
(F)

WAREHOUSE
300 200 200 700
REQUIREMENTS

© 2009 Prentice-Hall, Inc. 10 – 20

 Developing an Initial Solution:
Northwest Corner Rule
4. Assign 100 units from Fort Lauderdale to Boston.
This fulfills Boston’s demand and Fort
Lauderdale still has 200 units available.

TO ALBUQUERQUE BOSTON CLEVELAND FACTORY

FROM (A) (B) (C) CAPACITY

DES MOINES $5 $4 $3
100 100
(D)

EVANSVILLE $8 $4 $3
200 100 300
(E)

FORT LAUDERDALE $9 $7 $5
100 300
(F)

WAREHOUSE
300 200 200 700
REQUIREMENTS

© 2009 Prentice-Hall, Inc. 10 – 21

 Developing an Initial Solution:
Northwest Corner Rule
5. Assign 200 units from Fort Lauderdale to
Cleveland. This exhausts Fort Lauderdale’s
supply and Cleveland’s demand. The initial
shipment schedule is now complete.
Table 10.3
TO ALBUQUERQUE BOSTON CLEVELAND FACTORY
FROM (A) (B) (C) CAPACITY

DES MOINES $5 $4 $3
100 100
(D)

EVANSVILLE $8 $4 $3
200 100 300
(E)

FORT LAUDERDALE $9 $7 $5
100 200 300
(F)

WAREHOUSE
300 200 200 700
REQUIREMENTS

© 2009 Prentice-Hall, Inc. 10 – 22

 Developing an Initial Solution:
Northwest Corner Rule
 We can easily compute the cost of this shipping
assignment
ROUTE

FROM TO UNITS PER UNIT TOTAL

SHIPPED x COST ($) = COST ($)
D A 100 5 500
E A 200 8 1,600
E B 100 4 400
F B 100 7 700
F C 200 5 1,000
4,200

 This solution is feasible but we need to check to

see if it is optimal
© 2009 Prentice-Hall, Inc. 10 – 23
 Stepping-Stone Method:
Finding a Least Cost Solution
 The stepping-stone method is an iterative
technique for moving from an initial
feasible solution to an optimal feasible
solution
 There are two distinct parts to the process
 Testing the current solution to determine if
improvement is possible
 Making changes to the current solution to
obtain an improved solution
 This process continues until the optimal
solution is reached
© 2009 Prentice-Hall, Inc. 10 – 24
 Stepping-Stone Method:
Finding a Least Cost Solution
 There is one very important rule
 The number of occupied routes (or squares) must
always be equal to one less than the sum of the
number of rows plus the number of columns
 In the Executive Furniture problem this means
the initial solution must have 3 + 3 – 1 = 5
squares used
Occupied shipping Number Number of
routes (squares) = of rows + columns –1

 When the number of occupied rows is less than

this, the solution is called degenerate

© 2009 Prentice-Hall, Inc. 10 – 25

 Testing the Solution for
Possible Improvement
 The stepping-stone method works by
testing each unused square in the
transportation table to see what would
happen to total shipping costs if one unit
of the product were tentatively shipped on
an unused route
 There are five steps in the process

© 2009 Prentice-Hall, Inc. 10 – 26

 Five Steps to Test Unused Squares
with the Stepping-Stone Method
1. Select an unused square to evaluate
2. Beginning at this square, trace a closed path
back to the original square via squares that are
currently being used with only horizontal or
vertical moves allowed
3. Beginning with a plus (+) sign at the unused
square, place alternate minus (–) signs and plus
signs on each corner square of the closed path
just traced

© 2009 Prentice-Hall, Inc. 10 – 27

 Five Steps to Test Unused Squares
with the Stepping-Stone Method
4. Calculate an improvement index by adding
together the unit cost figures found in each
square containing a plus sign and then
subtracting the unit costs in each square
containing a minus sign
5. Repeat steps 1 to 4 until an improvement index
has been calculated for all unused squares. If all
indices computed are greater than or equal to
zero, an optimal solution has been reached. If
not, it is possible to improve the current solution
and decrease total shipping costs.

© 2009 Prentice-Hall, Inc. 10 – 28

 Five Steps to Test Unused Squares
with the Stepping-Stone Method
 For the Executive Furniture Corporation data

Steps 1 and 2.
2 Beginning with Des Moines–Boston
route we trace a closed path using only currently
occupied squares, alternately placing plus and
minus signs in the corners of the path
 In a closed path,
path only squares currently used for
shipping can be used in turning corners
 Only one closed route is possible for each square
we wish to test

© 2009 Prentice-Hall, Inc. 10 – 29

 Five Steps to Test Unused Squares
with the Stepping-Stone Method
Step 3.
3 We want to test the cost-effectiveness of the
Des Moines–Boston shipping route so we pretend
we are shipping one desk from Des Moines to
Boston and put a plus in that box
 But if we ship one more unit out of Des Moines
we will be sending out 101 units
 Since the Des Moines factory capacity is only
100, we must ship fewer desks from Des Moines
to Albuquerque so we place a minus sign in that
box
 But that leaves Albuquerque one unit short so we
must increase the shipment from Evansville to
Albuquerque by one unit and so on until we
complete the entire closed path
© 2009 Prentice-Hall, Inc. 10 – 30
 Five Steps to Test Unused Squares
with the Stepping-Stone Method
 Evaluating the unused Warehouse A Warehouse B

Des Moines–Boston Factory

100
$5 $4
D
shipping route – +
Factory
+ $8 – $4
E 200 100

TO FACTORY
ALBUQUERQUE BOSTON CLEVELAND
FROM CAPACITY
$5 $4 $3
DES MOINES 100 100

$8 $4 $3
EVANSVILLE 200 100 300

$9 $7 $5
FORT LAUDERDALE 100 200 300

WAREHOUSE
REQUIREMENTS 300 200 200 700 Table 10.4
© 2009 Prentice-Hall, Inc. 10 – 31
 Five Steps to Test Unused Squares
with the Stepping-Stone Method
 Evaluating the unused Warehouse A Warehouse B

Des Moines–Boston Factory

99
100
$5
1
$4
D
shipping route – +
Factory 201 + $8 99 – $4
E 200 100

TO FACTORY
ALBUQUERQUE BOSTON CLEVELAND
FROM CAPACITY
$5 $4 $3
DES MOINES 100 100

$8 $4 $3
EVANSVILLE 200 100 300

$9 $7 $5
FORT LAUDERDALE 100 200 300

WAREHOUSE
REQUIREMENTS 300 200 200 700 Table 10.4
© 2009 Prentice-Hall, Inc. 10 – 32
 Five Steps to Test Unused Squares
with the Stepping-Stone Method
 Evaluating the unused Warehouse A Warehouse B

Des Moines–Boston Factory

99
100
$5
1
$4
D
shipping route – +
Factory 201 + $8 99 – $4
E 200 100

TO FACTORY
ALBUQUERQUE BOSTON CLEVELAND
FROM Result
CAPACITY of Proposed
$5 $4 $3
Shift in Allocation
DES MOINES 100 100
= 1 x $4
$8 $4 $3 – 1 x $5
EVANSVILLE 200 100 300 + 1 x $8
– 1 x $4 = +$3
$9 $7 $5
FORT LAUDERDALE 100 200 300

WAREHOUSE
REQUIREMENTS 300 200 200 700 Table 10.4
© 2009 Prentice-Hall, Inc. 10 – 33
 Five Steps to Test Unused Squares
with the Stepping-Stone Method
Step 4. 4 We can now compute an improvement index
(Iij) for the Des Moines–Boston route
 We add the costs in the squares with plus signs
and subtract the costs in the squares with minus
signs
Des Moines–
Boston index = IDB = +$4 – $5 + $5 – $4 = + $3

 This means for every desk shipped via the Des

Moines–Boston route, total transportation cost
will increase by $3 over their current level

© 2009 Prentice-Hall, Inc. 10 – 34

 Five Steps to Test Unused Squares
with the Stepping-Stone Method
Step 5.
5 We can now examine the Des Moines–
Cleveland unused route which is slightly more
difficult to draw
 Again we can only turn corners at squares that
represent existing routes
 We must pass through the Evansville–Cleveland
square but we can not turn there or put a + or –
sign
 The closed path we will use is
+ DC – DA + EA – EB + FB – FC

© 2009 Prentice-Hall, Inc. 10 – 35

 Five Steps to Test Unused Squares
with the Stepping-Stone Method
 Evaluating the Des Moines–Cleveland shipping
route
TO FACTORY
ALBUQUERQUE BOSTON CLEVELAND
FROM CAPACITY
$5 $4 Start $3
DES MOINES 100 100
– +
$8 $4 $3
EVANSVILLE 200 100 300
+ –
$9 $7 $5
FORT LAUDERDALE 100 200 300
+ –
WAREHOUSE 300 200 200 700
REQUIREMENTS

Table 10.5

Des Moines–Cleveland
improvement index = IDC = + $3 – $5 + $8 – $4 + $7 – $5 = + $4

© 2009 Prentice-Hall, Inc. 10 – 36

 Five Steps to Test Unused Squares
with the Stepping-Stone Method
 Opening the Des Moines–Cleveland route will not
lower our total shipping costs
 Evaluating the other two routes we find
Evansville-
Cleveland index = IEC = + $3 – $4 + $7 – $5 = + $1
 The closed path is
+ EC – EB + FB – FC
Fort Lauderdale–
Albuquerque index = IFA = + $9 – $7 + $4 – $8 = – $2
 The closed path is
+ FA – FB + EB – EA
 So opening the Fort Lauderdale-Albuquerque
route will lower our total transportation costs
© 2009 Prentice-Hall, Inc. 10 – 37
 Obtaining an Improved Solution

 In the Executive Furniture problem there is only

one unused route with a negative index (Fort
Lauderdale-Albuquerque)
 If there was more than one route with a negative
index, we would choose the one with the largest
improvement
 We now want to ship the maximum allowable
number of units on the new route
 The quantity to ship is found by referring to the
closed path of plus and minus signs for the new
route and selecting the smallest number found in
those squares containing minus signs

© 2009 Prentice-Hall, Inc. 10 – 38

 Obtaining an Improved Solution

 To obtain a new solution, that number is added to

all squares on the closed path with plus signs
and subtracted from all squares the closed path
with minus signs
 All other squares are unchanged
 In this case, the maximum number that can be
shipped is 100 desks as this is the smallest value
in a box with a negative sign (FB route)
 We add 100 units to the FA and EB routes and
subtract 100 from FB and EA routes
 This leaves balanced rows and columns and an
improved solution

© 2009 Prentice-Hall, Inc. 10 – 39

 Obtaining an Improved Solution

 Stepping-stone path used to evaluate route FA

TO FACTORY
A B C
FROM CAPACITY
$5 $4 $3
D 100 100

$8 $4 $3
E 200 100 300
– +
$9 $7 $5
F 100 200 300
+ –
WAREHOUSE 300 200 200 700
REQUIREMENTS

Table 10.6

© 2009 Prentice-Hall, Inc. 10 – 40

 Obtaining an Improved Solution
 Second solution to the Executive Furniture
problem
TO FACTORY
A B C
FROM CAPACITY
$5 $4 $3
D 100 100

$8 $4 $3
E 100 200 300

$9 $7 $5
F 100 200 300

WAREHOUSE 300 200 200 700

REQUIREMENTS

Table 10.7

 Total shipping costs have been reduced by (100

units) x ($2 saved per unit) and now equals $4,000
© 2009 Prentice-Hall, Inc. 10 – 41
 Obtaining an Improved Solution
 This second solution may or may not be optimal
 To determine whether further improvement is
possible, we return to the first five steps to test
each square that is now unused
 The four new improvement indices are

D to B = IDB = + $4 – $5 + $8 – $4 = + $3
(closed path: + DB – DA + EA – EB)
D to C = IDC = + $3 – $5 + $9 – $5 = + $2
(closed path: + DC – DA + FA – FC)
E to C = IEC = + $3 – $8 + $9 – $5 = – $1
(closed path: + EC – EA + FA – FC)
F to B = IFB = + $7 – $4 + $8 – $9 = + $2
(closed path: + FB – EB + EA – FA)
© 2009 Prentice-Hall, Inc. 10 – 42
 Obtaining an Improved Solution
 Path to evaluate for the EC route

TO FACTORY
A B C
FROM CAPACITY
$5 $4 $3
D 100 100

E 100
$8
200
$4 Start $3
300
– +
$9 $7 $5
F 100 200 300
+ –
WAREHOUSE 300 200 200 700
REQUIREMENTS

Table 10.8

 An improvement can be made by shipping the

maximum allowable number of units from E to C
© 2009 Prentice-Hall, Inc. 10 – 43
 Obtaining an Improved Solution
 Total cost of third solution

ROUTE

FROM TO DESKS PER UNIT TOTAL

SHIPPED x COST ($) = COST ($)
D A 100 5 500
E B 200 4 800
E C 100 3 300
F A 200 9 1,800
F C 100 5 500
3,900

© 2009 Prentice-Hall, Inc. 10 – 44

 Obtaining an Improved Solution
 Third and optimal solution

TO FACTORY
A B C
FROM CAPACITY
$5 $4 $3
D 100 100

$8 $4 $3
E 200 100 300

$9 $7 $5
F 200 100 300

WAREHOUSE 300 200 200 700

REQUIREMENTS

Table 10.9

© 2009 Prentice-Hall, Inc. 10 – 45

 Obtaining an Improved Solution
 This solution is optimal as the improvement
indices that can be computed are all greater than
or equal to zero

D to B = IDB = + $4 – $5 + $9 – $5 + $3 – $4 = + $2
(closed path: + DB – DA + FA – FC + EC – EB)
D to C = IDC = + $3 – $5 + $9 – $5 = + $2
(closed path: + DC – DA + FA – FC)
E to A = IEA = + $8 – $9 + $5 – $3 = + $1
(closed path: + EA – FA + FC – EC)
F to B = IFB = + $7 – $5 + $3 – $4 = + $1
(closed path: + FB – FC + EC – EB)

© 2009 Prentice-Hall, Inc. 10 – 46

 Summary of Steps in Transportation
Algorithm (Minimization)
1. Set up a balanced transportation table
2. Develop initial solution using either the
northwest corner method or Vogel’s
approximation method
3. Calculate an improvement index for each empty
cell using either the stepping-stone method or
the MODI method. If improvement indices are all
nonnegative, stop as the optimal solution has
been found. If any index is negative, continue to
step 4.
4. Select the cell with the improvement index
indicating the greatest decrease in cost. Fill this
cell using the stepping-stone path and go to step
3.
© 2009 Prentice-Hall, Inc. 10 – 47
 Using Excel QM to Solve
Transportation Problems
 Excel QM input screen and formulas

Program 10.1A

© 2009 Prentice-Hall, Inc. 10 – 48

 Using Excel QM to Solve
Transportation Problems
 Output from Excel QM with optimal solution

Program 10.1B

© 2009 Prentice-Hall, Inc. 10 – 49

 MODI Method
 The MODI (modified distribution)
distribution method allows
us to compute improvement indices quickly for
each unused square without drawing all of the
closed paths
 Because of this, it can often provide considerable
time savings over the stepping-stone method for
solving transportation problems
 If there is a negative improvement index, then only
one stepping-stone path must be found
 This is used in the same manner as before to
obtain an improved solution

© 2009 Prentice-Hall, Inc. 10 – 50

 How to Use the MODI Approach

 In applying the MODI method, we begin with an

initial solution obtained by using the northwest
corner rule
 We now compute a value for each row (call the
values R1, R2, R3 if there are three rows) and for
each column (K1, K2, K3) in the transportation table
 In general we let

Ri = value for assigned row i

Kj = value for assigned column j
Cij = cost in square ij (cost of
shipping from source i to destination j)

© 2009 Prentice-Hall, Inc. 10 – 51

 Five Steps in the MODI Method to
Test Unused Squares
1. Compute the values for each row and column, set
Ri + Kj = Cij
but only for those squares that are currently used
or occupied
2. After all equations have been written, set R1 = 0
3. Solve the system of equations for R and K values
4. Compute the improvement index for each unused
square by the formula
Improvement Index (Iij) = Cij – Ri – Kj
5. Select the best negative index and proceed to
solve the problem as you did using the stepping-
stone method
© 2009 Prentice-Hall, Inc. 10 – 52
 Solving the Executive Furniture
Corporation Problem with MODI
 The initial northwest corner solution is repeated
in Table 10.10
 Note that to use the MODI method we have added
the Ris (rows) and Kjs (columns)
Kj K1 K2 K3
TO FACTORY
Ri A B C
FROM CAPACITY
$5 $4 $3
R1 D 100 100

$8 $4 $3
R2 E 200 100 300

$9 $7 $5
R3 F 100 200 300

WAREHOUSE
300 200 200 700
REQUIREMENTS

Table 10.10
© 2009 Prentice-Hall, Inc. 10 – 53
 Solving the Executive Furniture
Corporation Problem with MODI
 The first step is to set up an equation for each
occupied square
 By setting R1 = 0 we can easily solve for K1, R2, K2,
R3, and K3

(1) R1 + K1 = 5 0 + K1 = 5 K1 = 5
(2) R2 + K1 = 8 R2 + 5 = 8 R2 = 3
(3) R2 + K2 = 4 3 + K2 = 4 K2 = 1
(4) R3 + K2 = 7 R3 + 1 = 7 R3 = 6
(5) R3 + K3 = 5 6 + K3 = 5 K3 = –1

© 2009 Prentice-Hall, Inc. 10 – 54

 Solving the Executive Furniture
Corporation Problem with MODI
 The next step is to compute the improvement
index for each unused cell using the formula
Improvement index (Iij) = Cij – Ri – Kj
 We have

Des Moines- IDB = C12 – R1 – K2 = 4 – 0 – 1

Boston index = +$3
Des Moines- IDC = C13 – R1 – K3 = 3 – 0 – (–1)
Cleveland index = +$4
Evansville- IEC = C23 – R2 – K3 = 3 – 3 – (–1)
Cleveland index = +$1
Fort Lauderdale- I = C31 – R3 – K1 = 9 – 6 – 5
Albuquerque indexFA
= –$2
© 2009 Prentice-Hall, Inc. 10 – 55
 Solving the Executive Furniture
Corporation Problem with MODI
 The steps we follow to develop an improved
solution after the improvement indices have been
computed are
1. Beginning at the square with the best
improvement index, trace a closed path back
to the original square via squares that are
currently being used
2. Beginning with a plus sign at the unused
square, place alternate minus signs and plus
signs on each corner square of the closed
path just traced

© 2009 Prentice-Hall, Inc. 10 – 56

 Solving the Executive Furniture
Corporation Problem with MODI
3. Select the smallest quantity found in those
squares containing the minus signs and add
that number to all squares on the closed path
with plus signs; subtract the number from
squares with minus signs
4. Compute new improvement indices for this
new solution using the MODI method
 Note that new Ri and Kj values must be
calculated
 Follow this procedure for the second and third
solutions

© 2009 Prentice-Hall, Inc. 10 – 57

 Vogel’s Approximation Method:
Another Way To Find An Initial Solution
 Vogel’s Approximation Method (VAM)
VAM is not as
simple as the northwest corner method, but it
provides a very good initial solution, often one
that is the optimal solution
 VAM tackles the problem of finding a good initial
solution by taking into account the costs
associated with each route alternative
 This is something that the northwest corner rule
does not do
 To apply VAM, we first compute for each row and
column the penalty faced if we should ship over
the second-best route instead of the least-cost
route
© 2009 Prentice-Hall, Inc. 10 – 58
 Vogel’s Approximation Method
 The six steps involved in determining an initial
VAM solution are illustrated below beginning with
the same layout originally shown in Table 10.2
VAM Step 1.1 For each row and column of the
transportation table, find the difference between
the distribution cost on the best route in the row
or column and the second best route in the row or
column
 This is the opportunity cost of not using the
best route
 Step 1 has been done in Table 10.11

© 2009 Prentice-Hall, Inc. 10 – 59

 Vogel’s Approximation Method
 Transportation table with VAM row and column
differences shown
OPPORTUNITY
3 0 0 COSTS
TO TOTAL
FROM
A B C AVAILABLE
$5 $4 $3
D 100 100 1

$8 $4 $3
E 200 100 300 1

$9 $7 $5
F 100 200 300 2

TOTAL REQUIRED 300 200 200 700

Table 10.11

© 2009 Prentice-Hall, Inc. 10 – 60

 Vogel’s Approximation Method

VAM Step 2.
2 identify the row or column with the
greatest opportunity cost, or difference (column A in
this example)
VAM Step 3.Assign
3 as many units as possible to the
lowest-cost square in the row or column selected
VAM Step 4.
4 Eliminate any row or column that has
been completely satisfied by the assignment just
made by placing Xs in each appropriate square
VAM Step 5.
5 Recompute the cost differences for the
transportation table, omitting rows or columns
eliminated in the previous step

© 2009 Prentice-Hall, Inc. 10 – 61

 Vogel’s Approximation Method
 VAM assignment with D’s requirements satisfied

OPPORTUNITY
31 03 02 COSTS
TO TOTAL
FROM
A B C AVAILABLE
$5 $4 $3
D 100 X X 100 1

$8 $4 $3
E 300 1

$9 $7 $5
F 300 2

TOTAL REQUIRED 300 200 200 700

Table 10.12

© 2009 Prentice-Hall, Inc. 10 – 62

 Vogel’s Approximation Method

VAM Step 6. 6 Return to step 2 for the rows and

columns remaining and repeat the steps until an
initial feasible solution has been obtained

 In this case column B now has the greatest

difference, 3
 We assign 200 units to the lowest-cost square in
the column, EB
 We recompute the differences and find the
greatest difference is now in row E
 We assign 100 units to the lowest-cost square in
the column, EC

© 2009 Prentice-Hall, Inc. 10 – 63

 Vogel’s Approximation Method
 Second VAM assignment with B’s requirements
satisfied
OPPORTUNITY
31 03 02 COSTS
TO TOTAL
FROM
A B C AVAILABLE
$5 $4 $3
D 100 X X 100 1

$8 $4 $3
E 200 300 1

$9 $7 $5
F X 300 2

TOTAL REQUIRED 300 200 200 700

Table 10.13

© 2009 Prentice-Hall, Inc. 10 – 64

 Vogel’s Approximation Method
 Third VAM assignment with E’s requirements
satisfied

TO TOTAL
FROM
A B C AVAILABLE
$5 $4 $3
D 100 X X 100

$8 $4 $3
E X 200 100 300

$9 $7 $5
F X 300

TOTAL REQUIRED 300 200 200 700

Table 10.14

© 2009 Prentice-Hall, Inc. 10 – 65

 Vogel’s Approximation Method
 Final assignments to balance column and row
requirements

TO TOTAL
FROM
A B C AVAILABLE
$5 $4 $3
D 100 X X 100

$8 $4 $3
E X 200 100 300

$9 $7 $5
F 200 X 100 300

TOTAL REQUIRED 300 200 200 700

Table 10.15

© 2009 Prentice-Hall, Inc. 10 – 66

 Unbalanced Transportation Problems

 In real-life problems, total demand is frequently

not equal to total supply
 These unbalanced problems can be handled
easily by introducing dummy sources or dummy
destinations
 If total supply is greater than total demand, a
dummy destination (warehouse), with demand
exactly equal to the surplus, is created
 If total demand is greater than total supply, we
introduce a dummy source (factory) with a supply
equal to the excess of demand over supply

© 2009 Prentice-Hall, Inc. 10 – 67

 Unbalanced Transportation Problems

 In either case, shipping cost coefficients of zero

are assigned to each dummy location or route as
no goods will actually be shipped
 Any units assigned to a dummy destination
represent excess capacity
 Any units assigned to a dummy source represent
unmet demand

© 2009 Prentice-Hall, Inc. 10 – 68

 Demand Less Than Supply
 Suppose that the Des Moines factory increases its
rate of production from 100 to 250 desks
 The firm is now able to supply a total of 850 desks
each period
 Warehouse requirements remain the same (700) so
the row and column totals do not balance
 We add a dummy column that will represent a fake
warehouse requiring 150 desks
 This is somewhat analogous to adding a slack
variable
 We use the northwest corner rule and either
stepping-stone or MODI to find the optimal
solution
© 2009 Prentice-Hall, Inc. 10 – 69
 Demand Less Than Supply
 Initial solution to an unbalanced problem where
demand is less than supply
TO DUMMY TOTAL
FROM
A B C WAREHOUSE AVAILABLE
$5 $4 $3 0
D 250 250

$8 $4 $3 0
E 50 200 50 300

$9 $7 $5 0
F 150 150 300

WAREHOUSE 300 200 200 150 850

REQUIREMENTS

Total cost = 250($5) + 50($8) + 200($4) + 50($3) + 150($5) + 150(0) = $3,350

New Des Moines

Table 10.16
capacity

© 2009 Prentice-Hall, Inc. 10 – 70

 Demand Greater than Supply
 The second type of unbalanced condition occurs
when total demand is greater than total supply
 In this case we need to add a dummy row
representing a fake factory
 The new factory will have a supply exactly equal
to the difference between total demand and total
real supply
 The shipping costs from the dummy factory to
each destination will be zero

© 2009 Prentice-Hall, Inc. 10 – 71

 Demand Greater than Supply
 Unbalanced transportation table for Happy
Sound Stereo Company

TO WAREHOUSE WAREHOUSE WAREHOUSE PLANT

FROM A B C SUPPLY
$6 $4 $9
PLANT W 200

$10 $5 $8
PLANT X 175

$12 $7 $6
PLANT Y 75

Totals
WAREHOUSE 450
DEMAND
250 100 150
500
do not
balance

Table 10.17

© 2009 Prentice-Hall, Inc. 10 – 72

 Demand Greater than Supply
 Initial solution to an unbalanced problem in
which demand is greater than supply
TO WAREHOUSE WAREHOUSE WAREHOUSE PLANT
FROM A B C SUPPLY

$6 $4 $9
PLANT W 200 200

$10 $5 $8
PLANT X 50 100 25 175

$12 $7 $6
PLANT Y 75 75

0 0 0
PLANT Y 50 50

WAREHOUSE 250 100 150 500

DEMAND

Total cost of initial solution = 200($6) + 50($10) + 100($5) + 25($8) + 75($6)

+ $50(0) = $2,850

Table 10.18
© 2009 Prentice-Hall, Inc. 10 – 73
 Degeneracy in Transportation
Problems
 Degeneracy occurs when the number of occupied
squares or routes in a transportation table
solution is less than the number of rows plus the
number of columns minus 1
 Such a situation may arise in the initial solution
or in any subsequent solution
 Degeneracy requires a special procedure to
correct the problem since there are not enough
occupied squares to trace a closed path for each
unused route and it would be impossible to apply
the stepping-stone method or to calculate the R
and K values needed for the MODI technique

© 2009 Prentice-Hall, Inc. 10 – 74

 Degeneracy in Transportation
Problems
 To handle degenerate problems, create an
artificially occupied cell
 That is, place a zero (representing a fake
shipment) in one of the unused squares and then
treat that square as if it were occupied
 The square chosen must be in such a position as
to allow all stepping-stone paths to be closed
 There is usually a good deal of flexibility in
selecting the unused square that will receive the
zero

© 2009 Prentice-Hall, Inc. 10 – 75

 Degeneracy in an Initial Solution

 The Martin Shipping Company example illustrates

degeneracy in an initial solution
 They have three warehouses which supply three
major retail customers
 Applying the northwest corner rule the initial
solution has only four occupied squares
 This is less than the amount required to use
either the stepping-stone or MODI method to
improve the solution (3 rows + 3 columns – 1 = 5)
 To correct this problem, place a zero in an
unused square, typically one adjacent to the last
filled cell

© 2009 Prentice-Hall, Inc. 10 – 76

 Degeneracy in an Initial Solution

 Initial solution of a degenerate problem

TO WAREHOUSE
CUSTOMER 1 CUSTOMER 2 CUSTOMER 3
FROM SUPPLY
$8 $2 $6
WAREHOUSE 1 100 0 100

$10 $9 $9
WAREHOUSE 2 0 100 20 120

$7 $10 $7
WAREHOUSE 3 80 80

CUSTOMER 100 100 100 300

DEMAND

Table 10.19
Possible choices of
cells to address the
degenerate solution
© 2009 Prentice-Hall, Inc. 10 – 77
 Degeneracy During
Later Solution Stages
 A transportation problem can become degenerate
after the initial solution stage if the filling of an
empty square results in two or more cells
becoming empty simultaneously
 This problem can occur when two or more cells
with minus signs tie for the lowest quantity
 To correct this problem, place a zero in one of the
previously filled cells so that only one cell
becomes empty

© 2009 Prentice-Hall, Inc. 10 – 78

 Degeneracy During
Later Solution Stages

 Bagwell Paint Example

 After one iteration, the cost analysis at
Bagwell Paint produced a transportation table
that was not degenerate but was not optimal
 The improvement indices are

factory A – warehouse 2 index = +2

factory A – warehouse 3 index = +1
factory B – warehouse 3 index = –15
factory C – warehouse 2 index = +11
Only route with
a negative index

© 2009 Prentice-Hall, Inc. 10 – 79

 Degeneracy During
Later Solution Stages
 Bagwell Paint transportation table

TO WAREHOUSE WAREHOUSE WAREHOUSE

1 2 3 FACTORY
FROM CAPACITY
$8 $5 $16
FACTORY A 70 70

$15 $10 $7
FACTORY B 50 80 130

$3 $9 $10
FACTORY C 30 50 80

WAREHOUSE
150 80 50 280
REQUIREMENT

Table 10.20

© 2009 Prentice-Hall, Inc. 10 – 80

 Degeneracy During
Later Solution Stages
 Tracing a closed path for the factory B –
warehouse 3 route
TO
WAREHOUSE 1 WAREHOUSE 3
FROM

$15 $7
FACTORY B 50
– +
$3 $10
FACTORY C 30 50
+ –
Table 10.21

 This would cause two cells to drop to zero

 We need to place an artificial zero in one of these
cells to avoid degeneracy
© 2009 Prentice-Hall, Inc. 10 – 81
 More Than One Optimal Solution
 It is possible for a transportation problem to have
multiple optimal solutions
 This happens when one or more of the
improvement indices zero in the optimal solution
 This means that it is possible to design
alternative shipping routes with the same total
shipping cost
 The alternate optimal solution can be found by
shipping the most to this unused square using a
stepping-stone path
 In the real world, alternate optimal solutions
provide management with greater flexibility in
selecting and using resources
© 2009 Prentice-Hall, Inc. 10 – 82
Maximization Transportation Problems

 If the objective in a transportation problem is to

maximize profit, a minor change is required in the
transportation algorithm
 Now the optimal solution is reached when all the
improvement indices are negative or zero
 The cell with the largest positive improvement
index is selected to be filled using a stepping-
stone path
 This new solution is evaluated and the process
continues until there are no positive improvement
indices

© 2009 Prentice-Hall, Inc. 10 – 83

 Unacceptable Or Prohibited Routes

 At times there are transportation problems in

which one of the sources is unable to ship to one
or more of the destinations
 When this occurs, the problem is said to have an
unacceptable or prohibited route
 In a minimization problem, such a prohibited
route is assigned a very high cost to prevent this
route from ever being used in the optimal
solution
 In a maximization problem, the very high cost
used in minimization problems is given a
negative sign, turning it into a very bad profit

© 2009 Prentice-Hall, Inc. 10 – 84

 Facility Location Analysis
 The transportation method is especially useful in
helping a firm to decide where to locate a new
factory or warehouse
 Each alternative location should be analyzed
within the framework of one overall distribution
system
 The new location that yields the minimum cost
for the entire system is the one that should be
chosen

© 2009 Prentice-Hall, Inc. 10 – 85

 Locating a New Factory for
Hardgrave Machine Company
 Hardgrave Machine produces computer
components at three plants and they ship to four
warehouses
 The plants have not been able to keep up with
demand so the firm wants to build a new plant
 Two sites are being considered, Seattle and
Birmingham
 Data has been collected for each possible
location
 Which new location will yield the lowest cost for
the firm in combination with the existing plants
and warehouses

© 2009 Prentice-Hall, Inc. 10 – 86

 Locating a New Factory for
Hardgrave Machine Company
 Hardgrave’s demand and supply data

MONTHLY
DEMAND PRODUCTION MONTHLY COST TO PRODUCE
WAREHOUSE (UNITS) PLANT SUPPLY ONE UNIT ($)
Detroit 10,000 Cincinnati 15,000 48
Dallas 12,000 Salt Lake 6,000 50
New York 15,000 Pittsburgh 14,000 52
Los Angeles 9,000 35,000
46,000
Supply needed from new plant = 46,000 – 35,000 = 11,000 units per month

Table 10.22
ESTIMATED PRODUCTION COST
PER UNIT AT PROPOSED PLANTS

Seattle $53

Birmingham $49

© 2009 Prentice-Hall, Inc. 10 – 87

 Locating a New Factory for
Hardgrave Machine Company
 Hardgrave’s shipping costs

TO LOS
FROM DETROIT DALLAS NEW YORK ANGELES
CINCINNATI $25 $55 $40 $60
SALT LAKE 35 30 50 40
PITTSBURGH 36 45 26 66
SEATTLE 60 38 65 27
BIRMINGHAM 35 30 41 50

Table 10.23

© 2009 Prentice-Hall, Inc. 10 – 88

 Locating a New Factory for
Hardgrave Machine Company
 Optimal solution for the Birmingham location

TO LOS FACTORY
FROM DETROIT DALLAS NEW YORK ANGELES CAPACITY
73 103 88 108
CINCINNATI 10,000 1,000 4,000 15,000

85 80 100 90
SALT LAKE 1,000 5,000 6,000

88 97 78 118
PITTSBURGH 14,000 14,000

84 79 90 99
BIRMINGHAM 11,000 11,000

WAREHOUSE 10,000 12,000 15,000 9,000 46,000

REQUIREMENT

Table 10.24

© 2009 Prentice-Hall, Inc. 10 – 89

 Locating a New Factory for
Hardgrave Machine Company
 Optimal solution for the Seattle location

TO LOS FACTORY
FROM DETROIT DALLAS NEW YORK ANGELES CAPACITY
73 103 88 108
CINCINNATI 10,000 4,000 1,000 15,000

85 80 100 90
SALT LAKE 6,000 6,000

88 97 78 118
PITTSBURGH 14,000 14,000

113 91 118 80
SEATTLE 2,000 9,000 11,000

WAREHOUSE 10,000 12,000 15,000 9,000 46,000

REQUIREMENT

Table 10.25

© 2009 Prentice-Hall, Inc. 10 – 90

 Locating a New Factory for
Hardgrave Machine Company

 By comparing the total system costs of the two

alternatives, Hardgrave can select the lowest cost
option
 The Birmingham location yields a total system
cost of $3,741,000
 The Seattle location yields a total system cost of
$3,704,000
 With the lower total system cost, the Seattle
location is favored
 Excel QM can also be used as a solution tool

© 2009 Prentice-Hall, Inc. 10 – 91

 Locating a New Factory for
Hardgrave Machine Company
 Excel input screen

Program 10.2A
© 2009 Prentice-Hall, Inc. 10 – 92
 Locating a New Factory for
Hardgrave Machine Company
 Output from Excel QM analysis

Program 10.2A
© 2009 Prentice-Hall, Inc. 10 – 93
 Assignment Model Approach
 The second special-purpose LP algorithm is the
assignment method
 Each assignment problem has associated with it
a table, or matrix
 Generally, the rows contain the objects or people
we wish to assign, and the columns comprise the
tasks or things we want them assigned to
 The numbers in the table are the costs associated
with each particular assignment
 An assignment problem can be viewed as a
transportation problem in which the capacity
from each source is 1 and the demand at each
destination is 1
© 2009 Prentice-Hall, Inc. 10 – 94
 Assignment Model Approach
 The Fix-It Shop has three rush projects to repair
 They have three repair persons with different
talents and abilities
 The owner has estimates of wage costs for each
worker for each project
 The owner’s objective is to assign the three
project to the workers in a way that will result in
the lowest cost to the shop
 Each project will be assigned exclusively to one
worker

© 2009 Prentice-Hall, Inc. 10 – 95

 Assignment Model Approach
 Estimated project repair costs for the Fix-It shop
assignment problem

PROJECT

PERSON 1 2 3

Adams $11 $14 $6

Brown 8 10 11

Cooper 9 12 7

Table 10.26

© 2009 Prentice-Hall, Inc. 10 – 96

 Assignment Model Approach
 Summary of Fix-It Shop assignment alternatives
and costs

PRODUCT ASSIGNMENT
LABOR TOTAL
1 2 3 COSTS ($) COSTS ($)
Adams Brown Cooper 11 + 10 + 7 28
Adams Cooper Brown 11 + 12 + 11 34
Brown Adams Cooper 8 + 14 + 7 29
Brown Cooper Adams 8 + 12 + 6 26
Cooper Adams Brown 9 + 14 + 11 34
Cooper Brown Adams 9 + 10 + 6 25

Table 10.27

© 2009 Prentice-Hall, Inc. 10 – 97

 The Hungarian Method
(Flood’s Technique)
 The Hungarian method is an efficient method of
finding the optimal solution to an assignment
problem without having to make direct
comparisons of every option
 It operates on the principle of matrix reduction
 By subtracting and adding appropriate numbers
in the cost table or matrix, we can reduce the
problem to a matrix of opportunity costs
 Opportunity costs show the relative penalty
associated with assigning any person to a project
as opposed to making the best assignment
 We want to make assignment so that the
opportunity cost for each assignment is zero
© 2009 Prentice-Hall, Inc. 10 – 98
Three Steps of the Assignment Method

1. Find the opportunity cost table by:

by
(a) Subtracting the smallest number in each row
of the original cost table or matrix from every
number in that row
(b) Then subtracting the smallest number in
each column of the table obtained in part (a)
from every number in that column
2. Test the table resulting from step 1 to see
whether an optimal assignment can be made by
drawing the minimum number of vertical and
horizontal straight lines necessary to cover all
the zeros in the table. If the number of lines is
less than the number of rows or columns,
proceed to step 3.
© 2009 Prentice-Hall, Inc. 10 – 99
Three Steps of the Assignment Method

3. Revise the present opportunity cost table by

subtracting the smallest number not covered by
a line from every other uncovered number. This
same number is also added to any number(s)
lying at the intersection of horizontal and
vertical lines. Return to step 2 and continue the
cycle until an optimal assignment is possible.

© 2009 Prentice-Hall, Inc. 10 – 100

 Steps in the Assignment Method

Not
Set up cost table for problem Revise opportunity cost table
optimal
in two steps:
Step 1 (a) Subtract the smallest
number not covered by a line
from itself and every other
Find opportunity cost
uncovered number
(a) Subtract smallest number in
(b) add this number at every
each row from every number
intersection of any two lines
in that row, then
(b) subtract smallest number in
each column from every
number in that column Optimal solution at zero
locations. Systematically make
final assignments.
Step 2
(a) Check each row and
column for a unique zero and
Test opportunity cost table to make the first assignment in
see if optimal assignments are that row or column
possible by drawing the
minimum possible lines on (b) Eliminate that row and
columns and/or rows such that Optimal column and search for another
all zeros are covered unique zero. Make that
assignment and proceed in a
like manner.
Figure 10.3
© 2009 Prentice-Hall, Inc. 10 – 101
 The Hungarian Method
(Flood’s Technique)
 Step 1: Find the opportunity cost table
 We can compute row opportunity costs and
column opportunity costs
 What we need is the total opportunity cost
 We derive this by taking the row opportunity
costs and subtract the smallest number in that
column from each number in that column

© 2009 Prentice-Hall, Inc. 10 – 102

 The Hungarian Method
(Flood’s Technique)
 Cost of each person-  Row opportunity
project assignment cost table

PROJECT PROJECT
PERSON 1 2 3 PERSON 1 2 3

Adams $11 $14 $6 Adams $5 $8 $0

Brown 8 10 11 Brown 0 2 3

Cooper 9 12 7 Cooper 2 5 0

Table 10.28 Table 10.29

 The opportunity cost of assigning Cooper to

project 2 is $12 – $7 = $5
© 2009 Prentice-Hall, Inc. 10 – 103
 The Hungarian Method
(Flood’s Technique)
 We derive the total opportunity costs by taking
the costs in Table 29 and subtract the smallest
number in each column from each number in that
column
 Row opportunity  Total opportunity
cost table cost table
PROJECT PROJECT
PERSON 1 2 3 PERSON 1 2 3

Adams $5 $8 $0 Adams $5 $6 $0

Brown 0 2 3 Brown 0 0 3

Cooper 2 5 0 Cooper 2 3 0

Table 10.29 Table 10.30

© 2009 Prentice-Hall, Inc. 10 – 104
 The Hungarian Method
(Flood’s Technique)
 Step 2: Test for the optimal assignment
 We want to assign workers to projects in such
a way that the total labor costs are at a
minimum
 We would like to have a total assigned
opportunity cost of zero
 The test to determine if we have reached an
optimal solution is simple
 We find the minimum number of straight lines
necessary to cover all the zeros in the table
 If the number of lines equals the number of
rows or columns, an optimal solution has been
reached
© 2009 Prentice-Hall, Inc. 10 – 105
 The Hungarian Method
(Flood’s Technique)
 Test for optimal solution

PROJECT
PERSON 1 2 3

Adams $5 $6 $0

Brown 0 0 3 Covering line 1

Cooper 2 3 0

Table 10.31 Covering line 2

 This requires only two lines to cover the zeros so

the solution is not optimal

© 2009 Prentice-Hall, Inc. 10 – 106

 The Hungarian Method
(Flood’s Technique)
 Step 3: Revise the opportunity-cost table
 We subtract the smallest number not covered
by a line from all numbers not covered by a
straight line
 The same number is added to every number
lying at the intersection of any two lines
 We then return to step 2 to test this new table

© 2009 Prentice-Hall, Inc. 10 – 107

 The Hungarian Method
(Flood’s Technique)
 Revised opportunity cost table (derived by
subtracting 2 from each cell not covered by a line
and adding 2 to the cell at the intersection of the
lines)
PROJECT
PERSON 1 2 3

Adams $3 $4 $0

Brown 0 0 5

Cooper 0 1 0

Table 10.32

© 2009 Prentice-Hall, Inc. 10 – 108

 The Hungarian Method
(Flood’s Technique)
 Optimality test on the revised opportunity cost
table
PROJECT
PERSON 1 2 3

Adams $3 $4 $0

Brown 0 0 5 Covering line 2

Cooper 0 1 0

Table 10.33 Covering line 1 Covering line 3

 This requires three lines to cover the zeros so the

solution is optimal
© 2009 Prentice-Hall, Inc. 10 – 109
 Making the Final Assignment
 The optimal assignment is Adams to project 3,
Brown to project 2, and Cooper to project 1
 But this is a simple problem
 For larger problems one approach to making the
final assignment is to select a row or column that
contains only one zero
 Make the assignment to that cell and rule out its
row and column
 Follow this same approach for all the remaining
cells

© 2009 Prentice-Hall, Inc. 10 – 110

 Making the Final Assignment
 Total labor costs of this assignment are

ASSIGNMENT COST ($)

Adams to project 3 6

Brown to project 2 10

Cooper to project 1 9

Total cost 25

© 2009 Prentice-Hall, Inc. 10 – 111

 Making the Final Assignment
 Making the final assignments

(A) FIRST (B) SECOND (C) THIRD

ASSIGNMENT ASSIGNMENT ASSIGNMENT

1 2 3 1 2 3 1 2 3

Adams 3 4 0 Adams 3 4 0 Adams 3 4 0

Brown 0 0 5 Brown 0 0 5 Brown 0 0 5

Cooper 0 1 0 Cooper 0 1 0 Cooper 0 1 0

Table 10.34

© 2009 Prentice-Hall, Inc. 10 – 112

 Using Excel QM for the Fix-It Shop
Assignment Problem
 Excel QM assignment module

Program 10.3A
© 2009 Prentice-Hall, Inc. 10 – 113
 Using Excel QM for the Fix-It Shop
Assignment Problem
 Excel QM output screen

Program 10.3A

© 2009 Prentice-Hall, Inc. 10 – 114

Unbalanced Assignment Problems

 Often the number of people or objects to be

assigned does not equal the number of tasks or
clients or machines listed in the columns, and the
problem is unbalanced
 When this occurs, and there are more rows than
columns, simply add a dummy column or task
 If the number of tasks exceeds the number of
people available, we add a dummy row
 Since the dummy task or person is nonexistent,
we enter zeros in its row or column as the cost or
time estimate

© 2009 Prentice-Hall, Inc. 10 – 115

Unbalanced Assignment Problems
 The Fix-It Shop has another worker available
 The shop owner still has the same basic problem
of assigning workers to projects
 But the problem now needs a dummy column to
balance the four workers and three projects
PROJECT
PERSON 1 2 3 DUMMY
Adams $11 $14 $6 $0
Brown 8 10 11 0
Cooper 9 12 7 0
Davis 10 13 8 0

Table 10.35

© 2009 Prentice-Hall, Inc. 10 – 116

 Maximization Assignment Problems
 Some assignment problems are phrased in terms
of maximizing the payoff, profit, or effectiveness
 It is easy to obtain an equivalent minimization
problem by converting all numbers in the table to
opportunity costs
 This is brought about by subtracting every
number in the original payoff table from the
largest single number in that table
 Transformed entries represent opportunity costs
 Once the optimal assignment has been found, the
total payoff is found by adding the original
payoffs of those cells that are in the optimal
assignment

© 2009 Prentice-Hall, Inc. 10 – 117

 Maximization Assignment Problems
 The British navy wishes to assign four ships to
patrol four sectors of the North Sea
 Ships are rated for their probable efficiency in
each sector
 The commander wants to determine patrol
assignments producing the greatest overall
efficiencies

© 2009 Prentice-Hall, Inc. 10 – 118

 Maximization Assignment Problems

 Efficiencies of British ships in patrol sectors

SECTOR
SHIP A B C D
1 20 60 50 55
2 60 30 80 75
3 80 100 90 80
4 65 80 75 70

Table 10.36

© 2009 Prentice-Hall, Inc. 10 – 119

 Maximization Assignment Problems

 Opportunity cost of British ships

SECTOR
SHIP A B C D
1 80 40 50 45
2 40 70 20 25
3 20 0 10 20
4 35 20 25 30

Table 10.37

© 2009 Prentice-Hall, Inc. 10 – 120

 Maximization Assignment Problems

 First convert the maximization efficiency table

into a minimizing opportunity cost table by
subtracting each rating from 100, the largest
rating in the whole table
 The smallest number in each row is subtracted
from every number in that row and the smallest
number in each column is subtracted from every
number in that column
 The minimum number of lines needed to cover
the zeros in the table is four, so this represents
an optimal solution

© 2009 Prentice-Hall, Inc. 10 – 121

 Maximization Assignment Problems

 The overall efficiency

ASSIGNMENT EFFICIENCY

Ship 1 to sector D 55

Ship 2 to sector C 80

Ship 3 to sector B 100

Ship 4 to sector A 65

Total efficiency 300

© 2009 Prentice-Hall, Inc. 10 – 122

 Chapter 3

Decision Analysis

To accompany
Quantitative Analysis for Management, Tenth Edition,
by Render, Stair, and Hanna © 2008 Prentice-Hall, Inc.
Power Point slides created by Jeff Heyl © 2009 Prentice-Hall, Inc.
 Chapter Outline
3.1 Introduction
3.2 The Six Steps in Decision Making
3.3 Types of Decision-Making
Environments
3.4 Decision Making under Uncertainty
3.5 Decision Making under Risk
3.5.1 EMV
3.5.2 Sensitivity Analysis

© 2009 Prentice-Hall, Inc. 3–2

 Introduction

 What is involved in making a good

decision?
 Decision theory is an analytic and
systematic approach to the study of
decision making
 A good decision is one that is based
on logic, considers all available data
and possible alternatives, and the
quantitative approach described here

© 2009 Prentice-Hall, Inc. 3–3

 The Six Steps in Decision Making

1. Clearly define the problem at hand

2. List the possible alternatives
3. Identify the possible outcomes or states
of nature
4. List the payoff or profit of each
combination of alternatives and
outcomes
5. Select one of the mathematical decision
theory models
6. Apply the model and make your decision
© 2009 Prentice-Hall, Inc. 3–4
Thompson Lumber Company

Step 1 – Define the problem

 Expand by manufacturing and
marketing a new product, backyard
storage sheds
Step 2 – List alternatives
 Construct a large new plant
 A small plant
 No plant at all
Step 3 – Identify possible outcomes
 The market could be favorable or
unfavorable

© 2009 Prentice-Hall, Inc. 3–5

 Thompson Lumber Company

Step 4 – List the payoffs

 Identify conditional values for the
profits for large, small, and no plants
for the two possible market
conditions
STATE OF NATURE

FAVORABLE UNFAVORABLE
ALTERNATIVE MARKET ($) MARKET ($)
Construct a large plant 200,000 –180,000

Construct a small plant 100,000 –20,000

Do nothing 0 0

© 2009 Prentice-Hall, Inc. 3–6

 Thompson Lumber Company
Step 5 – Select the decision model
 Depends on the environment and amount
of risk and uncertainty
Step 6 – Apply the model to the data
 Solution and analysis used to help the
decision making

© 2009 Prentice-Hall, Inc. 3–7

 Types of Decision-Making
Environments

Type 1: Decision making under certainty

 Decision maker knows with certainty the
consequences of every alternative or
decision choice
Type 2: Decision making under uncertainty
 The decision maker does not know the
probabilities of the various outcomes
Type 3: Decision making under risk
 The decision maker knows the
probabilities of the various outcomes

© 2009 Prentice-Hall, Inc. 3–8

 Decision Making Under
Uncertainty
There are several criteria for making decisions
under uncertainty

1. Maximax (optimistic)
2. Maximin (pessimistic)
3. Criterion of realism (Hurwicz)
4. Equally likely (Laplace)
5. Minimax regret

© 2009 Prentice-Hall, Inc. 3–9

 Maximax
Used to find the alternative that maximizes
the maximum payoff
 Locate the maximum payoff for each alternative
 Select the alternative with the maximum
number
STATE OF NATURE
FAVORABLE UNFAVORABLE MAXIMUM IN
ALTERNATIVE MARKET ($) MARKET ($) A ROW ($)
Construct a large 200,000 –180,000 200,000
plant
Maximax
Construct a small 100,000 –20,000 100,000
plant
Do nothing 0 0 0

Table 3.2
© 2009 Prentice-Hall, Inc. 3 – 10
 Maximin
Used to find the alternative that maximizes
the minimum payoff
 Locate the minimum payoff for each alternative
 Select the alternative with the maximum
number
STATE OF NATURE
FAVORABLE UNFAVORABLE MINIMUM IN
ALTERNATIVE MARKET ($) MARKET ($) A ROW ($)
Construct a large 200,000 –180,000 –180,000
plant
Construct a small 100,000 –20,000 –20,000
plant
Do nothing 0 0 0

Table 3.3
Maximin
© 2009 Prentice-Hall, Inc. 3 – 11
 Criterion of Realism (Hurwicz)
A weighted average compromise between
optimistic and pessimistic
 Select a coefficient of realism α
 Coefficient is between 0 and 1
 A value of 1 is 100% optimistic
 Compute the weighted averages for each
alternative
 Select the alternative with the highest value

Weighted average = α (maximum in row)

+ (1 – α )(minimum in row)

© 2009 Prentice-Hall, Inc. 3 – 12

 Criterion of Realism (Hurwicz)
 For the large plant alternative using α = 0.8
(0.8)(200,000) + (1 – 0.8)(–180,000) = 124,000
 For the small plant alternative using α = 0.8
(0.8)(100,000) + (1 – 0.8)(–20,000) = 76,000
STATE OF NATURE
CRITERION
FAVORABLE UNFAVORABLE OF REALISM
ALTERNATIVE MARKET ($) MARKET ($) (α = 0.8)$
Construct a large
200,000 –180,000 124,000
plant
Realism
Construct a small
100,000 –20,000 76,000
plant
Do nothing 0 0 0
Table 3.4
© 2009 Prentice-Hall, Inc. 3 – 13
 Equally Likely (Laplace)
Considers all the payoffs for each alternative
 Find the average payoff for each alternative
 Select the alternative with the highest average

STATE OF NATURE
FAVORABLE UNFAVORABLE ROW
ALTERNATIVE MARKET ($) MARKET ($) AVERAGE ($)
Construct a large 200,000 –180,000 10,000
plant
Construct a small
100,000 –20,000 40,000
plant
Equally likely
Do nothing 0 0 0
Table 3.5

© 2009 Prentice-Hall, Inc. 3 – 14

 Minimax Regret
Based on opportunity loss or regret,
regret the
difference between the optimal profit and
actual payoff for a decision.

 Create an opportunity loss table by determining

the opportunity loss for not choosing the best
alternative

© 2009 Prentice-Hall, Inc. 3 – 15

 Minimax Regret
 Opportunity loss is calculated by subtracting
each payoff in the column from the best payoff in
the column STATE OF NATURE
FAVORABLE UNFAVORABLE
MARKET ($) MARKET ($)
Table 3.6 200,000 – 200,000 0 – (–180,000)
200,000 – 100,000 0 – (–20,000)
200,000 – 0 0–0

STATE OF NATURE
FAVORABLE UNFAVORABLE
ALTERNATIVE MARKET ($) MARKET ($)
Construct a large plant 0 180,000 Table 3.7
Construct a small plant 100,000 20,000
Do nothing 200,000 0© 2009 Prentice-Hall, Inc. 3 – 16
 Minimax Regret
 Find the maximum opportunity loss for each
alternative and pick the alternative with the
minimum number

STATE OF NATURE
FAVORABLE UNFAVORABLE MAXIMUM IN
ALTERNATIVE MARKET ($) MARKET ($) A ROW ($)
Construct a large
0 180,000 180,000
plant
Construct a small 100,000 20,000 100,000
plant
Minimax
Do nothing 200,000 0 200,000

Table 3.8

© 2009 Prentice-Hall, Inc. 3 – 17

 Decision Making Under Risk
 Decision making when there are several possible
states of nature and we know the probabilities
associated with each possible state
 Most popular method is to choose the alternative
with the highest expected monetary value (EMV)

native i) = (payoff of first state of nature)

x (probability of first state of nature)
+ (payoff of second state of nature)
x (probability of second state of nature)
+ … + (payoff of last state of nature)
x (probability of last state of nature)

© 2009 Prentice-Hall, Inc. 3 – 18

 EMV for Thompson Lumber
 Each market has a probability of 0.50
 Which alternative would give the highest EMV?
 The calculations are

rge plant) = (0.50)($200,000) + (0.50)(–$180,000)

= $10,000
mall plant) = (0.50)($100,000) + (0.50)(–$20,000)
= $40,000
o nothing) = (0.50)($0) + (0.50)($0)
= $0

© 2009 Prentice-Hall, Inc. 3 – 19

 EMV for Thompson Lumber

STATE OF NATURE
FAVORABLE UNFAVORABLE
ALTERNATIVE MARKET ($) MARKET ($) EMV ($)
Construct a large 200,000 –180,000 10,000
plant
Construct a small 100,000 –20,000 40,000
plant
Do nothing 0 0 0
Probabilities 0.50 0.50

Table 3.9 Largest EMV

© 2009 Prentice-Hall, Inc. 3 – 20

 Expected Value of Perfect
Information (EVPI)
 EVPI places an upper bound on what you should
pay for additional information
EVPI = EVwPI – Maximum EMV
 EVwPI is the long run average return if we have
perfect information before a decision is made

EVwPI = (best payoff for first state of nature)

x (probability of first state of nature)
+ (best payoff for second state of nature)
x (probability of second state of nature)
+ … + (best payoff for last state of nature)
x (probability of last state of nature)

© 2009 Prentice-Hall, Inc. 3 – 21

 Expected Value of Perfect
Information (EVPI)
 Scientific Marketing, Inc. offers analysis
that will provide certainty about market
conditions (favorable)
 Additional information will cost $65,000
 Is it worth purchasing the information?

© 2009 Prentice-Hall, Inc. 3 – 22

 Expected Value of Perfect
Information (EVPI)
1. Best alternative for favorable state of nature is
build a large plant with a payoff of $200,000
Best alternative for unfavorable state of nature is
to do nothing with a payoff of $0
EVwPI = ($200,000)(0.50) + ($0)(0.50) = $100,000
2. The maximum EMV without additional
information is $40,000
EVPI = EVwPI – Maximum EMV
= $100,000 - $40,000
= $60,000

© 2009 Prentice-Hall, Inc. 3 – 23

 Expected Value of Perfect
Information (EVPI)
1. Best alternative for favorable state of nature is
build a large plant with a payoff of $200,000
So the maximum Thompson
Best alternative for unfavorable
should pay for the state of nature is
additional
to do nothinginformation
with a payoff
is of $0
$60,000
EVwPI = ($200,000)(0.50) + ($0)(0.50) = $100,000
2. The maximum EMV without additional
information is $40,000
EVPI = EVwPI – Maximum EMV
= $100,000 - $40,000
= $60,000

© 2009 Prentice-Hall, Inc. 3 – 24

 Expected Opportunity Loss
 Expected opportunity loss (EOL) is the
cost of not picking the best solution
 First construct an opportunity loss table
 For each alternative, multiply the
opportunity loss by the probability of that
loss for each possible outcome and add
these together
 Minimum EOL will always result in the
same decision as maximum EMV
 Minimum EOL will always equal EVPI

© 2009 Prentice-Hall, Inc. 3 – 25

 Expected Opportunity Loss
STATE OF NATURE
FAVORABLE UNFAVORABLE
ALTERNATIVE MARKET ($) MARKET ($) EOL
Construct a large plant 0 180,000 90,000
Construct a small 100,000 20,000 60,000
plant
Do nothing 200,000 0 100,000
Probabilities 0.50 0.50
Table 3.10 Minimum EOL
arge plant) = (0.50)($0) + (0.50)($180,000)
= $90,000
mall plant) = (0.50)($100,000) + (0.50)($20,000)
= $60,000
o nothing) = (0.50)($200,000) + (0.50)($0)
= $100,000
© 2009 Prentice-Hall, Inc. 3 – 26
 Sensitivity Analysis
 Sensitivity analysis examines how our decision
might change with different input data
 For the Thompson Lumber example

P = probability of a favorable market

(1 – P) = probability of an unfavorable market

© 2009 Prentice-Hall, Inc. 3 – 27

 Sensitivity Analysis
EMV(Large Plant) = $200,000P – $180,000)(1 – P)
= $200,000P – $180,000 + $180,000P
= $380,000P – $180,000
EMV(Small Plant) = $100,000P – $20,000)(1 – P)
= $100,000P – $20,000 + $20,000P
= $120,000P – $20,000
EMV(Do Nothing) = $0P + 0(1 – P)
= $0

© 2009 Prentice-Hall, Inc. 3 – 28

 Sensitivity Analysis
EMV Values

$300,000

$200,000
Point 2 EMV (large plant)
$100,000
Point 1 EMV (small plant)
0
EMV (do nothing)
–$100,000
.167 .615 1
–$200,000 Values of P

Figure 3.1

© 2009 Prentice-Hall, Inc. 3 – 29

 Sensitivity Analysis
Point 1:
EMV(do nothing) = EMV(small plant)
20,000
0 = $120,000 P − $20,000 P= = 0.167
120,000

Point 2:
EMV(small plant) = EMV(large plant)
$120,000 P − $20,000 = $380,000 P − $180,000
160,000
P= = 0.615
260,000

© 2009 Prentice-Hall, Inc. 3 – 30

 Sensitivity Analysis
BEST RANGE OF P
ALTERNATIVE VALUES
Do nothing Less than 0.167
EMV Values Construct a small plant 0.167 – 0.615
$300,000 Construct a large plant Greater than 0.615
$200,000
Point 2 EMV (large plant)
$100,000
Point 1 EMV (small plant)
0
EMV (do nothing)
–$100,000
.167 .615 1
–$200,000 Values of P

Figure 3.1
© 2009 Prentice-Hall, Inc. 3 – 31
 Using Excel QM to Solve
Decision Theory Problems

Program 3.1A
© 2009 Prentice-Hall, Inc. 3 – 32
 Using Excel QM to Solve
Decision Theory Problems

Program 3.1B
© 2009 Prentice-Hall, Inc. 3 – 33
 Decision Trees
 Any problem that can be presented in a
decision table can also be graphically
represented in a decision tree
 Decision trees are most beneficial when a
sequence of decisions must be made
 All decision trees contain decision points
or nodes and state-of-nature points or
nodes
 A decision node from which one of several
alternatives may be chosen
 A state-of-nature node out of which one state
of nature will occur
© 2009 Prentice-Hall, Inc. 3 – 34
 Five Steps to
Decision Tree Analysis

1. Define the problem

2. Structure or draw the decision tree
3. Assign probabilities to the states of
nature
4. Estimate payoffs for each possible
combination of alternatives and states of
nature
5. Solve the problem by computing
expected monetary values (EMVs) for
each state of nature node

© 2009 Prentice-Hall, Inc. 3 – 35

 Structure of Decision Trees
 Trees start from left to right
 Represent decisions and outcomes in
sequential order
 Squares represent decision nodes
 Circles represent states of nature nodes
 Lines or branches connect the decisions
nodes and the states of nature

© 2009 Prentice-Hall, Inc. 3 – 36

 Thompson’s Decision Tree
A State-of-Nature Node
Favorable Market
A Decision Node
1
Unfavorable Market
uct nt
r
n st Pla
e
Co arg
L Favorable Market
Construct
2
Small Plant Unfavorable Market
Do
No
th
in
g
Figure 3.2

© 2009 Prentice-Hall, Inc. 3 – 37

 Thompson’s Decision Tree
EMV for Node = (0.5)($200,000) + (0.5)(–$180,000)
1 = $10,000
Payoffs
Favorable Market (0.5)
$200,000
Alternative with best
EMV is selected 1
Unfavorable Market (0.5)
ct nt –$180,000
r u
n st Pla
e
Co arg
L Favorable Market (0.5)
$100,000
Construct
2
Small Plant Unfavorable Market (0.5)
–$20,000
Do
No
th EMV for Node = (0.5)($100,000)
in
g 2 = $40,000 + (0.5)(–$20,000)
Figure 3.3
$0
© 2009 Prentice-Hall, Inc. 3 – 38
 Thompson’s Complex Decision Tree
First Decision Second Decision Payoffs
Point Point
Favorable Market (0.78)
$190,000
nt 2 Unfavorable Market (0.22)
P la –$190,000
ge
Lar Favorable Market (0.78)
$90,000
) Small
. 45 Plant
3 Unfavorable Market (0.22)
(0 –$30,000
ey ts e
urv sul abl No Plant
–$10,000
S
R e vor
a
1 Surv F Favorable Market (0.27)
e $190,000
y

Re y (
ve

nt 4 Unfavorable Market (0.73)

Ne su 0.5 P la
ur

–$190,000
5) ge
tS

ga lts
tiv Lar Favorable Market (0.27)
$90,000
Small
ke

e 5 Unfavorable Market (0.73)

ar

Plant –$30,000
M
t
uc

No Plant
–$10,000
nd
Co

Do Favorable Market (0.50)

Not $200,000
Con t 6 Unfavorable Market (0.50)
duc la n
P –$180,000
tS ge
urv Lar Favorable Market (0.50)
$100,000
e y Small
Plant
7 Unfavorable Market (0.50)
–$20,000
No Plant
$0
Figure 3.4
© 2009 Prentice-Hall, Inc. 3 – 39
 Thompson’s Complex Decision Tree

Given favorable survey results,

EMV(node 2) = EMV(large plant | positive survey)
= (0.78)($190,000) + (0.22)(–$190,000) = $106,400
EMV(node 3) = EMV(small plant | positive survey)
= (0.78)($90,000) + (0.22)(–$30,000) = $63,600
EMV for no plant = –$10,000
Given negative survey results,
EMV(node 4) = EMV(large plant | negative survey)
= (0.27)($190,000) + (0.73)(–$190,000) = –$87,400
EMV(node 5) = EMV(small plant | negative survey)
= (0.27)($90,000) + (0.73)(–$30,000) = $2,400
EMV for no plant = –$10,000

© 2009 Prentice-Hall, Inc. 3 – 40

 Thompson’s Complex Decision Tree

Compute the expected value of the market survey,

EMV(node 1) = EMV(conduct survey)
= (0.45)($106,400) + (0.55)($2,400)
= $47,880 + $1,320 = $49,200
f the market survey is not conducted,
EMV(node 6) = EMV(large plant)
= (0.50)($200,000) + (0.50)(–$180,000) = $10,000
EMV(node 7) = EMV(small plant)
= (0.50)($100,000) + (0.50)(–$20,000) = $40,000
EMV for no plant = $0
Best choice is to seek marketing information

© 2009 Prentice-Hall, Inc. 3 – 41

 Thompson’s Complex Decision Tree
First Decision Second Decision Payoffs
Point Point
$106,400 Favorable Market (0.78)
$190,000
l a nt Unfavorable Market (0.22)

$106,400
P –$190,000
a rge $63,600 Favorable Market (0.78)
L $90,000
) Small
. 45 Plant
Unfavorable Market (0.22)
–$30,000
(0
ey ts e
urv sul abl No Plant
–$10,000
S
R e vor
Su Fa –$87,400 Favorable Market (0.27)
rv $190,000
e
y

Re y (
ve

Ne su 0.5 ant
Pl
Unfavorable Market (0.73)
ur

–$190,000
5) ge
tS

ga lts r $2,400
$2,400
La Favorable Market (0.27)
tiv Small $90,000
ke

e Unfavorable Market (0.73)

ar

Plant –$30,000
Mt
uc

No Plant
–$10,000
d
on
$49,200
C

Do $10,000 Favorable Market (0.50)

Not $200,000
Con t Unfavorable Market (0.50)
duc P la n –$180,000
ge
$40,000

tS urv Lar $40,000 Favorable Market (0.50)

e y Small $100,000
Unfavorable Market (0.50)
Plant –$20,000
No Plant
$0
Figure 3.4
© 2009 Prentice-Hall, Inc. 3 – 42
Expected Value of Sample Information

 Thompson wants to know the actual value

of doing the survey
Expected value Expected value
with sample of best decision
EVSI = information, assuming – without sample
no cost to gather it information

= (EV with sample information + cost)

– (EV without sample information)

EVSI = ($49,200 + $10,000) – $40,000 = $19,200

© 2009 Prentice-Hall, Inc. 3 – 43

 Sensitivity Analysis

 How sensitive are the decisions to

changes in the probabilities?
 How sensitive is our decision to the
probability of a favorable survey result?
 That is, if the probability of a favorable
result (p = .45) where to change, would we
make the same decision?
 How much could it change before we would
make a different decision?

© 2009 Prentice-Hall, Inc. 3 – 44

 Sensitivity Analysis
p = probability of a favorable survey
result
(1 – p) = probability of a negative survey
result 1) = ($106,400)p +($2,400)(1 – p)
EMV(node
= $104,000p + $2,400

We are indifferent when the EMV of node 1 is the

same as the EMV of not conducting the survey,
$40,000

$104,000p + $2,400= $40,000

$104,000p = $37,600
p = $37,600/$104,000 = 0.36
© 2009 Prentice-Hall, Inc. 3 – 45
 Bayesian Analysis
 Many ways of getting probability data
 It can be based on
 Management’s experience and intuition
 Historical data
 Computed from other data using Bayes’
theorem
 Bayes’ theorem incorporates initial
estimates and information about the
accuracy of the sources
 Allows the revision of initial estimates
based on new information
© 2009 Prentice-Hall, Inc. 3 – 46
 Calculating Revised Probabilities

 In the Thompson Lumber case we used these four

conditional probabilities
P (favorable market(FM) | survey results positive) = 0.78
P (unfavorable market(UM) | survey results positive) = 0.22
P (favorable market(FM) | survey results negative) = 0.27
P (unfavorable market(UM) | survey results negative) = 0.73

 The prior probabilities of these markets are

P (FM) = 0.50
P (UM) = 0.50

© 2009 Prentice-Hall, Inc. 3 – 47

 Calculating Revised Probabilities
 Through discussions with experts Thompson has
learned the following
 He can use this information and Bayes’ theorem
to calculate posterior probabilities
STATE OF NATURE
RESULT OF FAVORABLE MARKET UNFAVORABLE MARKET
SURVEY (FM) (UM)

Positive (predicts P (survey positive | FM) P (survey positive | UM)

favorable market
for product) = 0.70 = 0.20

Negative (predicts
unfavorable P (survey negative | FM) P (survey negative | UM)
market for = 0.30 = 0.80
product)

Table 3.11
© 2009 Prentice-Hall, Inc. 3 – 48
 Calculating Revised Probabilities
 Recall Bayes’ theorem is

P ( B | A ) × P ( A)
P( A | B) =
P ( B | A) × P ( A) + P ( B | A′ ) × P ( A′ )

where
A, B = any two events
A′ = complement of A

For this example, A will represent a favorable

market and B will represent a positive survey

© 2009 Prentice-Hall, Inc. 3 – 49

 Calculating Revised Probabilities
 P (FM | survey positive)
P ( survey positive | FM ) × P ( FM )
=
P(survey positive |FM) × P(FM) + P(survey positive |UM) × P(UM)

(0.70 )(0.50 ) 0.35

= = = 0.78
(0.70)(0.50) + (0.20)(0.50 ) 0.45

 P (UM | survey positive)

P ( survey positive | UM ) × P (UM )
=
P(survey positive |UM) × P(UM) + P(survey positive |FM) × P(FM)

(0.20 )(0.50 ) 0.10

= = = 0.22
(0.20)(0.50) + (0.70)(0.50 ) 0.45

© 2009 Prentice-Hall, Inc. 3 – 50

 Calculating Revised Probabilities

POSTERIOR PROBABILITY
CONDITIONAL
PROBABILITY P(STATE OF
P(SURVEY NATURE |
STATE OF POSITIVE | STATE PRIOR JOINT SURVEY
NATURE OF NATURE) PROBABILITY PROBABILITY POSITIVE)
FM 0.70 X 0.50 = 0.35 0.35/0.45 = 0.78
UM 0.20 X 0.50 = 0.10 0.10/0.45 = 0.22
P(survey results positive) = 0.45 1.00

Table 3.12

© 2009 Prentice-Hall, Inc. 3 – 51

 Calculating Revised Probabilities
 P (FM | survey negative)
P ( survey negative | FM ) × P ( FM )
=
P(survey negative |FM) × P(FM) + P(survey negative |UM) × P(UM)

(0.30 )(0.50 ) 0.15

= = = 0.27
(0.30)(0.50) + (0.80)(0.50 ) 0.55

 P (UM | survey negative)

P ( survey negative | UM ) × P (UM )
=
P(survey negative |UM) × P(UM) + P(survey negative |FM) × P(FM)

(0.80 )(0.50 ) 0.40

= = = 0.73
(0.80)(0.50) + (0.30)(0.50 ) 0.55

© 2009 Prentice-Hall, Inc. 3 – 52

 Calculating Revised Probabilities

POSTERIOR PROBABILITY
CONDITIONAL
PROBABILITY P(STATE OF
P(SURVEY NATURE |
STATE OF NEGATIVE | STATE PRIOR JOINT SURVEY
NATURE OF NATURE) PROBABILITY PROBABILITY NEGATIVE)
FM 0.30 X 0.50 = 0.15 0.15/0.55 = 0.27
UM 0.80 X 0.50 = 0.40 0.40/0.55 = 0.73
P(survey results positive) = 0.55 1.00

Table 3.13

© 2009 Prentice-Hall, Inc. 3 – 53

 Potential Problems Using
Survey Results

 We can not always get the necessary

data for analysis
 Survey results may be based on cases
where an action was taken
 Conditional probability information
may not be as accurate as we would
like

© 2009 Prentice-Hall, Inc. 3 – 54

 Utility Theory
 Monetary value is not always a true
indicator of the overall value of the
result of a decision
 The overall value of a decision is called
utility
 Rational people make decisions to
maximize their utility

© 2009 Prentice-Hall, Inc. 3 – 55

 Utility Theory
$2,000,000
Accept
Offer
$0
Heads
(0.5)
Reject
Offer

Tails
(0.5)

EMV = $2,500,000 $5,000,000

Figure 3.6

© 2009 Prentice-Hall, Inc. 3 – 56

 Utility Theory
 Utility assessment assigns the worst outcome
a utility of 0, and the best outcome, a utility of 1
 A standard gamble is used to determine utility
values
 When you are indifferent, the utility values are
equal

Expected utility of alternative 2 =

Expected utility of alternative 1
Utility of other outcome = (p)
(utility of best outcome, which is 1)
+ (1 – p)(utility of the worst
outcome, which is 0)
Utility of other outcome = (p)
(1) + (1 – p)(0) = p © 2009 Prentice-Hall, Inc. 3 – 57
 Standard Gamble

(p)
Best Outcome
Utility = 1

1 (1 – p) Worst Outcome
ve
ati Utility = 0
e rn
Alt

Alt
ern
a ti
ve
2
Other Outcome
Utility = ?
Figure 3.7

© 2009 Prentice-Hall, Inc. 3 – 58

 Investment Example
 Jane Dickson wants to construct a utility curve
revealing her preference for money between $0
and $10,000
 A utility curve plots the utility value versus the
monetary value
 An investment in a bank will result in $5,000
 An investment in real estate will result in $0 or
$10,000
 Unless there is an 80% chance of getting $10,000
from the real estate deal, Jane would prefer to
have her money in the bank
 So if p = 0.80, Jane is indifferent between the bank
or the real estate investment
© 2009 Prentice-Hall, Inc. 3 – 59
 Investment Example
p = 0.80 $10,000
U($10,000) = 1.0

(1 – p) = 0.20 $0
t in U($0.00) = 0.0
ves tate
In s
alE
Re

Inv
es
t in
Ba
n k
$5,000
Figure 3.8
U($5,000) = p = 1.0

Utility for $5,000 = U($5,000) = pU($10,000) + (1 – p)U($0)

= (0.8)(1) + (0.2)(0) = 0.8
© 2009 Prentice-Hall, Inc. 3 – 60
 Investment Example
 We can assess other utility values in the same way
 For Jane these are

Utility for $7,000 = 0.90

Utility for $3,000 = 0.50
 Using the three utilities for different dollar amounts,
she can construct a utility curve

© 2009 Prentice-Hall, Inc. 3 – 61

 Utility Curve
1.0 –
U ($10,000) = 1.0

0.9 – U ($7,000) = 0.90

0.8 – U ($5,000) = 0.80

0.7 –

0.6 –

0.5 –
Utility

0.4 –
U ($3,000) = 0.50

0.3 –

0.2 –

0.1 –

U ($0) = 0
| | | | | | | | | | |
$0 $1,000 $3,000 $5,000 $7,000 $10,000

Monetary Value
Figure 3.9

© 2009 Prentice-Hall, Inc. 3 – 62

 Utility Curve
 Jane’s utility curve is typical of a risk
avoider
 A risk avoider gets less utility from greater risk
 Avoids situations where high losses might
occur
 As monetary value increases, the utility curve
increases at a slower rate
 A risk seeker gets more utility from greater risk
 As monetary value increases, the utility curve
increases at a faster rate
 Someone who is indifferent will have a linear
utility curve
© 2009 Prentice-Hall, Inc. 3 – 63
 Utility Curve

Risk
Avoider

e
nc
re
Utility

ffe
di
In
k
is
R

Risk
Seeker

Monetary Outcome
Figure 3.10

© 2009 Prentice-Hall, Inc. 3 – 64

 Utility as a
Decision-Making Criteria

 Once a utility curve has been developed

it can be used in making decisions
 Replace monetary outcomes with utility
values
 The expected utility is computed instead
of the EMV

© 2009 Prentice-Hall, Inc. 3 – 65

 Utility as a
Decision-Making Criteria

 Mark Simkin loves to gamble

 He plays a game tossing thumbtacks in
the air
 If the thumbtack lands point up, Mark wins
$10,000
 If the thumbtack lands point down, Mark
loses $10,000
 Should Mark play the game (alternative 1)?

© 2009 Prentice-Hall, Inc. 3 – 66

 Utility as a
Decision-Making Criteria
Tack Lands
Point Up (0.45)
$10,000

Tack Lands
1 ame Point Down (0.55)
t ive the G –$10,000
er na ys
a
Alt rk Pl
Ma
Alt
er n
ati
ve
2
Mark Does Not Play the Game
$0
Figure 3.11

© 2009 Prentice-Hall, Inc. 3 – 67

 Utility as a
Decision-Making Criteria

 Step 1– Define Mark’s utilities

U (–$10,000) = 0.05
U ($0) = 0.15
U ($10,000) = 0.30

 Step 2 – Replace monetary values with

utility values
E(alternative 1: play the game) = (0.45)(0.30) + (0.55)(0.05)
= 0.135 + 0.027 = 0.162
E(alternative 2: don’t play the game) = 0.15

© 2009 Prentice-Hall, Inc. 3 – 68

 Utility as a
Decision-Making Criteria
1.00 –

0.75 –
Utility

0.50 –

0.30 –
0.25 –

0.15 –

0.05 –
0 |– | | | |

–$20,000 –$10,000 $0 $10,000 $20,000

Monetary Outcome Figure 3.12

© 2009 Prentice-Hall, Inc. 3 – 69

 Utility as a
Decision-Making Criteria
Tack Lands Utility
E = 0.162 Point Up (0.45)
0.30

Tack Lands
1 ame Point Down (0.55)
t ive the G 0.05
er na ys
a
Alt rk Pl
Ma
Alt
er n
ati
ve
2
Don’t Play
0.15
Figure 3.13

© 2009 Prentice-Hall, Inc. 3 – 70

Queuing Theory Models
or
Waiting Lines
 Learning Objectives
After completing this chapter, we will be able to:
1. Describe the trade-off curves for cost-of-
waiting time and cost of service.
2. Understand the three parts of a queuing
system: the calling population, the queue
itself, and the service facility.
3. Describe the basic queuing system
configurations.
4. Understand the assumptions of the common
models dealt with in this chapter.
5. Analyze a variety of operating characteristics
of waiting lines.
Copyright © 2012 Pearson Education 13-2
 Chapter Outline
1 Introduction
2 Waiting Line Costs
3 Characteristics of a Queuing System
4 Single-Channel Queuing Model with
Poisson Arrivals and Exponential Service
Times (M/M/1)

Copyright © 2012 Pearson Education 13-3

 Introduction
 Queuing theory is the study of waiting lines.
 It is one of the oldest and most widely used
quantitative analysis techniques.
 The three basic components of a queuing
process are arrivals, service facilities, and the
actual waiting line.
 Analytical models of waiting lines can help
managers evaluate the cost and effectiveness
of service systems.

Copyright © 2012 Pearson Education 13-4

 Waiting Line Costs
 Most waiting line problems are focused on
finding the ideal level of service a firm should
provide.
 In most cases, this service level is something
management can control.
 When an organization does have control, they
often try to find the balance between two
extremes.

Copyright © 2012 Pearson Education 13-5

 Waiting Line Costs
 There is generally a trade-off between cost of
providing service and cost of waiting time.
 A large staff and many service facilities generally results
in high levels of service but have high costs.
 Having the minimum number of service facilities keeps
service cost down but may result in dissatisfied
customers.
 Service facilities are evaluated on their total
expected cost which is the sum of service costs
and waiting costs.
 Organizations typically want to find the service
level that minimizes the total expected cost.

Copyright © 2012 Pearson Education 13-6

 Queuing Costs and Service Levels

Figure 1
Copyright © 2012 Pearson Education 13-7
 Characteristics of a Queuing System

 There are three parts to a queuing system:

1. The arrivals or inputs to the system
(sometimes referred to as the calling
population).
2. The queue or waiting line itself.
3. The service facility.
 These components have their own
characteristics that must be examined
before mathematical models can be
developed.

Copyright © 2012 Pearson Education 13-8

 Characteristics of a Queuing System

Arrival Characteristics have three major

characteristics: size, pattern, and behavior.

 The size of the calling population can be either

unlimited (essentially infinite) or limited (finite).

 The pattern of arrivals can arrive according to

a known pattern or can arrive randomly.
 Random arrivals generally follow a Poisson
distribution.

Copyright © 2012 Pearson Education 13-9

 Characteristics of a Queuing System

Behavior of arrivals
 Most queuing models assume customers are
patient and will wait in the queue until they are
served and do not switch lines.
 Balking refers to customers who refuse to join
the queue.
 Reneging customers enter the queue but
become impatient and leave without receiving
their service.
 That these behaviors exist is a strong
argument for the use of queuing theory to
managing waiting lines.

Copyright © 2012 Pearson Education 13-10

 Characteristics of a Queuing System

Waiting Line Characteristics

 Waiting lines can be either limited or unlimited.

 Queue discipline refers to the rule by which

customers in the line receive service.
 The most common rule is first-in, first-out (FIFO).
 Other rules are possible and may be based on other
important characteristics.

 Other rules can be applied to select which

customers enter which queue, but may apply
FIFO once they are in the queue.
Copyright © 2012 Pearson Education 13-11
 Characteristics of a Queuing System

Service Facility Characteristics

 Basic queuing system configurations:
 Service systems are classified in terms of
the number of channels, or servers, and the
number of phases, or service stops.
 A single-channel system with one server is
quite common.
 Multichannel systems exist when multiple
servers are fed by one common waiting line.
 In a single-phase system, the customer
receives service form just one server.
 In a multiphase system, the customer has to
go through more than one server.
Copyright © 2012 Pearson Education 13-12
 Four basic
queuing
system
configurations

Figure 2

Copyright © 2012 Pearson Education 13-13

 Characteristics of a Queuing System

Service time distribution

 Service patterns can be either constant or
random.
 Constant service times are often machine
controlled.
 More often, service times are randomly
distributed according to a negative
exponential probability distribution.
 Analysts should observe, collect, and plot
service time data to ensure that the
observations fit the assumed distributions
when applying these models.

Copyright © 2012 Pearson Education 13-14

 Identifying Models Using
Kendall Notation
 D. G. Kendall developed a notation for queuing
models that specifies the pattern of arrival, the
service time distribution, and the number of
channels.
 Notation takes the form:
Arrival Service time Number of service
distribution distribution channels open

 Specific letters are used to represent probability

distributions.
M = Poisson distribution for number of occurrences
D = constant (deterministic) rate
G = general distribution with known mean and variance

Copyright © 2012 Pearson Education 13-15

 Identifying Models Using
Kendall Notation
 A single-channel model with Poisson arrivals and
exponential service times would be represented
by:
M/M/1
 If a second channel is added the notation would
read:
M/M/2
 A three-channel system with Poisson arrivals and
constant service time would be
M/D/3
 A four-channel system with Poisson arrivals and
normally distributed service times would be
M/G/4
Copyright © 2012 Pearson Education 13-16
 Single-Channel Model, Poisson Arrivals,
Exponential Service Times (M/M/1)
Assumptions of the model:
 Arrivals are served on a FIFO basis.
 There is no balking or reneging.
 Arrivals are independent of each other but the
arrival rate is constant over time.
 Arrivals follow a Poisson distribution.
 Service times are variable and independent but
the average is known.
 Service times follow a negative exponential
distribution.
 Average service rate is greater than the
average arrival rate.
Copyright © 2012 Pearson Education 13-17
 Single-Channel Model, Poisson Arrivals,
Exponential Service Times (M/M/1)

 When these assumptions are met, we

can develop a series of equations that
define the queue’s operating
characteristics.
 Queuing Equations:
Let
 = mean number of arrivals per time period
 = mean number of customers or units
served per time period
The arrival rate and the service rate must be
defined for the same time period.
Copyright © 2012 Pearson Education 13-18
 Single-Channel Model, Poisson Arrivals,
Exponential Service Times (M/M/1)
1. The average number of customers or units in the
system, LS :

LS 
 
2. The average time a customer spends in the
system, WS :
1
WS 
 

3. The average number of customers in the queue, Lq:

2
Lq 
(   )
Copyright © 2012 Pearson Education 13-19
 Single-Channel Model, Poisson Arrivals,
Exponential Service Times (M/M/1)
4. The average time a customer spends waiting in
the queue, Wq :

Wq 
(   )

5. The utilization factor for the system, , the

probability the service facility is being used:




Copyright © 2012 Pearson Education 13-20

 Single-Channel Model, Poisson Arrivals,
Exponential Service Times (M/M/1)
6. The percent idle time, P0, or the probability no one
is in the system:

P0  1 

7. The probability that there are n number of
customers in the system :
Pn   n (1   )

8. The probability that the number of customers in

the system is greater than k, Pn>k:
k 1

Pn k  

Copyright © 2012 Pearson Education 13-21
 Arnold’s Muffler Shop

 Arnold’s mechanic can install mufflers at a rate of

3 per hour.
 Customers arrive at a rate of 2 per hour.
 So:
 = 2 cars arriving per hour
 = 3 cars serviced per hour

2 2 
L    2 cars in the system
  32 1 on average

1 1
W   1 hour that an average car
  32 spends in the system
Copyright © 2012 Pearson Education 13-22
 Arnold’s Muffler Shop

2 22 4
Lq     1.33 cars waiting in line
 (    ) 3(3  2) 3(1) on average
 2
Wq   hour  40 minutes average
(   ) 3 waiting time per car
 2
    0.67  percentage of time
 3 mechanic is busy
 2
P0  1   1   0.33  probability that there
 3 are 0 cars in the system

Copyright © 2012 Pearson Education 13-23

 Arnold’s Muffler Shop

Probability of more than k cars in the system

k Pn>k = (2/3)k+1

0 0.667 Note that this is equal to 1 – P0 = 1 – 0.33 = 0.667

1 0.444
2 0.296
3 0.198 Implies that there is a 19.8% chance that more
than 3 cars are in the system
4 0.132
5 0.088
6 0.058
7 0.039

Copyright © 2012 Pearson Education 13-24

 Single-Channel Model, Poisson Arrivals,
Exponential Service Times (M/M/1:N)
Assumptions of the model:
 Arrivals are served on a FIFO basis.
 There is no balking or reneging.
 Arrivals are independent of each other but the
arrival rate is constant over time.
 Arrivals follow a Poisson distribution.
 Service times are variable and independent but
the average is known.
 Service times follow a negative exponential
distribution.
 Average service rate is greater than the
average arrival rate.
 Capacity of system is limited to N customers
Copyright © 2012 Pearson Education 13-25
 Single-Channel Model, Poisson Arrivals,
Exponential Service Times (M/M/1:N)
1. The average number of customers or units in the
system, LS :
N
 ( N  1)  N 1
LS   nPn  
n 1 1   1   N 1

2. The average time a customer spends in the

system, WS :
LS
WS 
 (1  PN )
3. The average number of customers in the queue, Lq:

Lq  LS  

Copyright © 2012 Pearson Education 13-26

 Single-Channel Model, Poisson Arrivals,
Exponential Service Times (M/M/1:N)
4. The average time a customer spends waiting in
the queue, Wq :
Lq
Wq 
 (1  PN )
5. The utilization factor for the system, , the
probability the service facility is being used:




Copyright © 2012 Pearson Education 13-27

 Single-Channel Model, Poisson Arrivals,
Exponential Service Times (M/M/1:N)
6. The percent idle time, P0, or the probability no one
is in the system:
1 
P0 
1   N 1
7. The probability that there are n number of
customers in the system :
(1   )  n
Pn   P  n

1   N 1
0

7. The probability that the number of customers in

the system is greater than k, Pn>k:
k 1

Pn k  

Copyright © 2012 Pearson Education 13-28
 Chapter 15

Simulation Modeling

To accompany
Quantitative Analysis for Management, Tenth Edition,
by Render, Stair, and Hanna © 2008 Prentice-Hall, Inc.
Power Point slides created by Jeff Heyl © 2009 Prentice-Hall, Inc.
 Learning Objectives
After completing this chapter, students will be able to:

1. Tackle a wide variety of problems by

simulation
2. Understand the seven steps of conducting a
simulation
3. Explain the advantages and disadvantages of
simulation
4. Develop random number intervals and use
them to generate outcomes
5. Understand alternative simulation packages
available

© 2009 Prentice-Hall, Inc. 15 – 2

 Chapter Outline
15.1 Introduction
15.2 Advantages and Disadvantages of Simulation
15.3 Monte Carlo Simulation
15.4 Simulation and Inventory Analysis
15.5 Simulation of a Queuing Problem
15.6 Fixed Time Increment and Next Event
Increment Simulation Models
15.7 Simulation Model for a Maintenance Policy
15.8 Two Other Types of Simulation
15.9 Verification and Validation
15.10 Role of Computers in Simulation

© 2009 Prentice-Hall, Inc. 15 – 3

 Introduction
◼ Simulation is one of the most widely used
quantitative analysis tools
◼ It is used by over half of the largest US
corporations in corporate planning
◼ To simulate is to try to duplicate the features,
appearance, and characteristics of a real system
◼ We will build a mathematical model that comes
as close as possible to representing the reality
of the system
◼ You can also build physical models to test
systems

© 2009 Prentice-Hall, Inc. 15 – 4

 Introduction
◼ The idea behind simulation is to imitate a real-
world situation mathematically
◼ Study its properties and operating characteristics
◼ Draw conclusions and make action decisions

© 2009 Prentice-Hall, Inc. 15 – 5

 Introduction
◼ Using simulation, a manager should
1. Define a problem
2. Introduce the variables associated with the
problem
3. Construct a numerical model
4. Set up possible courses of action for testing
5. Run the experiment
6. Consider the results
7. Decide what courses of action to take

© 2009 Prentice-Hall, Inc. 15 – 6

 Process of Simulation
Define Problem

Introduce Important
Variables

Construct Simulation
Model

Specify Values of
Variables to Be Tested

Conduct the
Simulation

Examine the
Results

Select Best Course

Figure 15.1 of Action

© 2009 Prentice-Hall, Inc. 15 – 7

 Advantages and Disadvantages
of Simulation
◼ Simulation is useful because
1. It is relatively straightforward and flexible
2. Recent advances in computer software make
simulation models very easy to develop
3. Can be used to analyze large and complex
real-world situations
4. Allows “what-if?” type questions
5. Does not interfere with the real-world system
6. Enables study of interactions between
components
7. Enables time compression
8. Enables the inclusion of real-world
complications
© 2009 Prentice-Hall, Inc. 15 – 8
 Advantages and Disadvantages
of Simulation

◼ The main disadvantages of simulation are

1. It is often expensive as it may require a long,
complicated process to develop the model
2. Does not generate optimal solutions, it is a
trial-and-error approach
3. Requires managers to generate all conditions
and constraints of real-world problem
4. Each model is unique and the solutions and
inferences are not usually transferable to
other problems

© 2009 Prentice-Hall, Inc. 15 – 9

 Monte Carlo Simulation
◼ When systems contain elements that exhibit
chance in their behavior, the Monte Carlo method
of simulation can be applied
◼ Some examples are
1. Inventory demand
2. Lead time for inventory
3. Times between machine breakdowns
4. Times between arrivals
5. Service times
6. Times to complete project activities
7. Number of employees absent

© 2009 Prentice-Hall, Inc. 15 – 10

 Monte Carlo Simulation
◼ The basis of the Monte Carlo simulation is
experimentation on the probabilistic elements
through random sampling
◼ It is based on the following five steps
1. Setting up a probability distribution for
important variables
2. Building a cumulative probability distribution
for each variable
3. Establishing an interval of random numbers
for each variable
4. Generating random numbers
5. Actually simulating a series of trials

© 2009 Prentice-Hall, Inc. 15 – 11

 Harry’s Auto Tire Example
◼ A popular radial tire accounts for a large portion
of the sales at Harry’s Auto Tire
◼ Harry wishes to determine a policy for managing
this inventory
◼ He wants to simulate the daily demand for a
number of days

Step 1: Establishing probability distributions

◼ One way to establish a probability distribution for
a given variable is to examine historical outcomes
◼ Managerial estimates based on judgment and
experience can also be used

© 2009 Prentice-Hall, Inc. 15 – 12

 Harry’s Auto Tire Example
◼ Historical daily demand for radial tires

DEMAND FOR TIRES FREQUENCY (DAYS)

0 10
1 20
2 40
3 60
4 40
5 30
200

Table 15.1

© 2009 Prentice-Hall, Inc. 15 – 13

 Harry’s Auto Tire Example
Step 2: Building a cumulative probability distribution
for each variable
◼ Converting from a regular probability to a
cumulative distribution is an easy job
◼ A cumulative probability is the probability that a
variable will be less than or equal to a particular
value
◼ A cumulative distribution lists all of the possible
values and the probabilities
◼ Tables 15.2 and 15.3 show these distributions

© 2009 Prentice-Hall, Inc. 15 – 14

 Harry’s Auto Tire Example
◼ Probability of demand for radial tires

DEMAND VARIABLE PROBABILITY OF OCCURRENCE

0 10/200 = 0.05
1 20/200 = 0.10
2 40/200 = 0.20
3 60/200 = 0.30
4 40/200 = 0.20
5 30/200 = 0.15
200/200 = 1.00

Table 15.2

© 2009 Prentice-Hall, Inc. 15 – 15

 Harry’s Auto Tire Example
◼ Cumulative probability for radial tires

DAILY DEMAND PROBABILITY CUMULATIVE PROBABILITY

0 0.05 0.05
1 0.10 0.15
2 0.20 0.35
3 0.30 0.65
4 0.20 0.85
5 0.15 1.00

Table 15.3

© 2009 Prentice-Hall, Inc. 15 – 16

 Harry’s Auto Tire Example
Step 3: Setting random number intervals
◼ We assign a set of numbers to represent each
possible value or outcome
◼ These are random number intervals
◼ A random number is a series of digits that have
been selected by a totally random process
◼ The range of the random number intervals
corresponds exactly to the probability of the
outcomes as shown in Figure 15.2

© 2009 Prentice-Hall, Inc. 15 – 17

 Harry’s Auto Tire Example
◼ Graphical representation of the cumulative
probability
distribution
1.00
for radial 1.00 – – 00
tires 0.85
– 86
0.80 – 85
Represents 4
Cumulative Probability

Tires Demanded
0.65
– 66
0.60 – 65

Numbers
Random
0.40 – 0.35
– 36
35

0.20 – 0.15
– 16
15 Represents 1
0.05 06 Tire Demanded
–
– 05
Figure 15.2 0.00 – – 01
0 1 2 3 4 5
Daily Demand for Radials
© 2009 Prentice-Hall, Inc. 15 – 18
 Harry’s Auto Tire Example
◼ Assignment of random number intervals for
Harry’s Auto Tire

DAILY DEMAND PROBABILITY CUMULATIVE INTERVAL OF

PROBABILITY RANDOM NUMBERS
0 0.05 0.05 01 to 05
1 0.10 0.15 06 to 15
2 0.20 0.35 16 to 35
3 0.30 0.65 36 to 65
4 0.20 0.85 66 to 85
5 0.15 1.00 86 to 00

Table 15.4

© 2009 Prentice-Hall, Inc. 15 – 19

 Harry’s Auto Tire Example
Step 4: Generating random numbers
◼ Random numbers can be generated in several
ways
◼ Large problems will use computer program to
generate the needed random numbers
◼ For small problems, random processes like
roulette wheels or pulling chips from a hat may
be used
◼ The most common manual method is to use a
random number table
◼ Because everything is random in a random
number table, we can select numbers from
anywhere in the table to use in the simulation
© 2009 Prentice-Hall, Inc. 15 – 20
 Harry’s Auto Tire Example
◼ Table of random numbers (partial)

52 06 50 88 53 30 10 47 99 37
37 63 28 02 74 35 24 03 29 60
82 57 68 28 05 94 03 11 27 79
69 02 36 49 71 99 32 10 75 21
98 94 90 36 06 78 23 67 89 85
96 52 62 87 49 56 59 23 78 71
33 69 27 21 11 60 95 89 68 48
50 33 50 95 13 44 34 62 64 39
88 32 18 50 62 57 34 56 62 31
90 30 36 24 69 82 51 74 30 35

Table 15.5

© 2009 Prentice-Hall, Inc. 15 – 21

 Harry’s Auto Tire Example
Step 5: Simulating the experiment
◼ We select random numbers from Table 15.5
◼ The number we select will have a corresponding
range in Table 15.4
◼ We use the daily demand that corresponds to the
probability range aligned with the random
number

© 2009 Prentice-Hall, Inc. 15 – 22

 Harry’s Auto Tire Example
◼ Ten-day simulation of demand for radial tires
DAY RANDOM NUMBER SIMULATED DAILY DEMAND
1 52 3
2 37 3
3 82 4
4 69 4
5 98 5
6 96 5
7 33 2
8 50 3
9 88 5
10 90 5
39 = total 10-day demand
3.9 = average daily demand for tires

Table 15.6
© 2009 Prentice-Hall, Inc. 15 – 23
 Harry’s Auto Tire Example
◼ Note that the average demand from this
simulation (3.9 tires) is different from the
expected daily demand
Expected 5
daily =  (Probability of i tires)(Demand of i tires)
demand i =0

= (0.05)(0) + (0.10)(1) + (0.20)(2) + (0.30)(3)

+ (0.20)(4) + (0.15)(5)
= 2.95 tires
◼ If this simulation were repeated hundreds or
thousands of times it is much more likely the
average simulated demand would be nearly the
same as the expected demand
© 2009 Prentice-Hall, Inc. 15 – 24
 Using QM for Windows for Simulation

◼ Monte Carlo simulation of Harry’s Auto Tire using

QM for Windows

Program 15.1
© 2009 Prentice-Hall, Inc. 15 – 25
 Simulation with Excel Spreadsheets
◼ Using Excel to simulate tire demand for Harry’s
Auto Tire Shop

Program 15.2A
© 2009 Prentice-Hall, Inc. 15 – 26
 Simulation with Excel Spreadsheets
◼ Excel simulation results for Harry’s Auto Tire
Shop showing a simulated average demand of 2.8
tires per day

Program 15.2B

© 2009 Prentice-Hall, Inc. 15 – 27

 Simulation with Excel Spreadsheets
◼ Generating normal random numbers in Excel

Program 15.3A

© 2009 Prentice-Hall, Inc. 15 – 28

 Simulation with Excel Spreadsheets
◼ Excel output with normal random numbers

Program 15.3B
© 2009 Prentice-Hall, Inc. 15 – 29
Simulation and Inventory Analysis

◼ We have seen deterministic inventory models

◼ In many real-world inventory situations, demand
and lead time are variables
◼ Accurate analysis is difficult without simulation
◼ We will look at an inventory problem with two
decision variables and two probabilistic
components
◼ The owner of a hardware store wants to establish
order quantity and reorder point decisions for a
product that has probabilistic daily demand and
reorder lead time

© 2009 Prentice-Hall, Inc. 15 – 30

 Simkin’s Hardware Store
◼ The owner of a hardware store wants to find a
good, low cost inventory policy for an electric
drill
◼ Simkin identifies two types of variables,
controllable and uncontrollable inputs
◼ The controllable inputs are the order quantity and
reorder points
◼ The uncontrollable inputs are daily demand and
variable lead time
◼ The demand data for the drill is shown in Table
15.7

© 2009 Prentice-Hall, Inc. 15 – 31

 Simkin’s Hardware Store
◼ Probabilities and random number intervals for
daily Ace drill demand
(1) (2) (4) (5)
DEMAND FOR FREQUENCY (3) CUMULATIVE INTERVAL OF
ACE DRILL (DAYS) PROBABILITY PROBABILITY RANDOM NUMBERS
0 15 0.05 0.05 01 to 05
1 30 0.10 0.15 06 to 15
2 60 0.20 0.35 16 to 35
3 120 0.40 0.75 36 to 75
4 45 0.15 0.90 76 to 90
5 30 0.10 1.00 91 to 00
300 1.00

Table 15.7

© 2009 Prentice-Hall, Inc. 15 – 32

 Simkin’s Hardware Store
◼ Probabilities and random number intervals for
reorder lead time
(1) (2) (4) (5)
LEAD TIME FREQUENCY (3) CUMULATIVE RANDOM NUMBER
(DAYS) (ORDERS) PROBABILITY PROBABILITY INTERVAL
1 10 0.20 0.20 01 to 20
2 25 0.50 0.70 21 to 70
3 15 0.30 1.00 71 to 00
50 1.00

Table 15.8

© 2009 Prentice-Hall, Inc. 15 – 33

 Simkin’s Hardware Store
◼ The third step is to develop a simulation model
◼ A flow diagram, or flowchart, is helpful in this
process
◼ The fourth step in the process is to specify the
values of the variables that we wish to test
◼ The first policy Simkin wants to test is an order
quantity of 10 with a reorder point of 5
◼ The fifth step is to actually conduct the
simulation
◼ The process is simulated for a 10 day period

© 2009 Prentice-Hall, Inc. 15 – 34

 Simkin’s Hardware Store
◼ Flow diagram
for Simkin’s Start

inventory Begin day

example of simulation

Has Increase current

order Yes
inventory by
arrived? quantity ordered

No
Select random number
to generate today’s
demand

Is
demand greater Yes Record
than beginning number of
inventory lost sales
?
No

Figure 15.3 (a)

© 2009 Prentice-Hall, Inc. 15 – 35
 Simkin’s Hardware Store
◼ Flow diagram
for Simkin’s No
inventory Compute ending inventory
= Beginning inventory
Record ending
inventory = 0
example – Demand

Is Has
Yes No
ending inventory order been Place
less than reorder placed that hasn’t order
point? arrived yet
?
No Have Yes
Select random
No enough days number to
of this order policy generate lead
been simulated time
?

Yes
Compute average ending inventory,
average lost sales, average number
of orders placed, and corresponding End
costs

Figure 15.3 (b)

© 2009 Prentice-Hall, Inc. 15 – 36
 Simkin’s Hardware Store
◼ Using the table of random numbers, the
simulation is conducted using a four-step process
1. Begin each day by checking whether an ordered
inventory has arrived. If it has, increase the current
inventory by the quantity ordered.
2. Generate a daily demand from the demand probability
by selecting a random number
3. Compute the ending inventory every day. If on-hand
inventory is insufficient to meet the day’s demand,
satisfy as much as possible and note the number of
lost sales.
4. Determine whether the day’s ending inventory has
reached the reorder point. If necessary place an order.

© 2009 Prentice-Hall, Inc. 15 – 37

 Simkin’s Hardware Store
◼ Simkin Hardware’s first inventory simulation
ORDER QUANTITY = 10 UNITS REORDER POINT = 5 UNITS
(2) (3) (4) (6) (7) (9) (10)
(1) UNITS BEGINNING RANDOM (5) ENDING LOST (8) RANDOM LEAD
DAY RECEIVED INVENTORY NUMBER DEMAND INVENTORY SALES ORDER NUMBER TIME
1 … 10 06 1 9 0 No
2 0 9 63 3 6 0 No
3 0 6 57 3 3 0 Yes 02 1
4 0 3 94 5 0 2 No
5 10 10 52 3 7 0 No
6 0 7 69 3 4 0 Yes 33 2
7 0 4 32 2 2 0 No
8 0 2 30 2 0 0 No
9 10 10 48 3 7 0 No
10 0 7 88 4 3 0 Yes 14 1
Total 41 2

Table 15.9

© 2009 Prentice-Hall, Inc. 15 – 38

Analyzing Simkin’s Inventory Cost
◼ The objective is to find a low-cost solution so
Simkin must determine what the costs are
◼ Equations for average daily ending inventory,
average lost sales, and average number of orders
placed
Average 41 total units
ending = = 4.1 units per day
inventory 10 days

Average 2 sales lost

= = 0.2 units per day
lost sales 10 days

Average 3 orders
number of = = 0.3 orders per day
orders placed 10 days
© 2009 Prentice-Hall, Inc. 15 – 39
Analyzing Simkin’s Inventory Cost
◼ Simkin’s store is open 200 days a year
◼ Estimated ordering cost is $10 per order
◼ Holding cost is $6 per drill per year
◼ Lost sales cost $8

Daily order cost = (Cost of placing one order)

x (Number of orders placed per day)
= $10 per order x 0.3 orders per day = $3
Daily holding cost = (Cost of holding one unit for one day) x
(Average ending inventory)
= $0.03 per unit per day x 4.1 units per day
= $0.12

© 2009 Prentice-Hall, Inc. 15 – 40

Analyzing Simkin’s Inventory Cost
◼ Simkin’s store is open 200 days a year
◼ Estimated ordering cost is $10 per order
◼ Holding cost is $6 per drill per year
◼ Lost sales cost $8

Daily stockout cost = (Cost per lost sale)

x (Average number of lost sales per
day)
= $8 per lost sale x 0.2 lost sales per day
= $1.60
Total daily
inventory cost = Daily order cost + Daily holding cost
+ Daily stockout cost
= $4.72

© 2009 Prentice-Hall, Inc. 15 – 41

Analyzing Simkin’s Inventory Cost
◼ For the year, this policy would cost approximately
$944
◼ This simulation should really be extended for
many more days, perhaps 100 or 1,000 days
◼ Even after a larger simulation, the model must be
verified and validated to make sure it truly
represents the situation on which it is based
◼ If we are satisfied with the model, additional
simulations can be conducted using other values
for the variables
◼ After simulating all reasonable combinations,
Simkin would select the policy that results in the
lowest total cost
© 2009 Prentice-Hall, Inc. 15 – 42
 Simulation of a Queuing Problem
◼ Modeling waiting lines is an important application
of simulation
◼ The assumptions of queuing models are quite
restrictive
◼ Sometimes simulation is the only approach that
fits
◼ In this example, arrivals do not follow a Poisson
distribution and unloading rates are not
exponential or constant

© 2009 Prentice-Hall, Inc. 15 – 43

 Port of New Orleans
◼ Fully loaded barges arrive at night for unloading
◼ The number of barges each night varies from 0 - 5
◼ The number of barges vary from day to day
◼ The supervisor has information which can be
used to create a probability distribution for the
daily unloading rate
◼ Barges are unloaded first-in, first-out
◼ Barges must wait for unloading which is
expensive
◼ The dock superintendent wants to do a simulation
study to enable him to make better staffing
decisions

© 2009 Prentice-Hall, Inc. 15 – 44

 Port of New Orleans
◼ Overnight barge arrival rates and random number
intervals

NUMBER OF CUMULATIVE RANDOM

ARRIVALS PROBABILITY PROBABILITY NUMBER INTERVAL
0 0.13 0.13 01 to 13
1 0.17 0.30 14 to 30
2 0.15 0.45 31 to 45
3 0.25 0.70 46 to 70
4 0.20 0.90 71 to 90
5 0.10 1.00 91 to 00

Table 15.10

© 2009 Prentice-Hall, Inc. 15 – 45

 Port of New Orleans
◼ Unloading rates and random number intervals

DAILY UNLOADING CUMULATIVE RANDOM

RATE PROBABILITY PROBABILITY NUMBER INTERVAL
1 0.05 0.05 01 to 05
2 0.15 0.20 06 to 20
3 0.50 0.70 21 to 70
4 0.20 0.90 71 to 90
5 0.10 1.00 91 to 00
1.00

Table 15.11

© 2009 Prentice-Hall, Inc. 15 – 46

 Port of New Orleans
◼ Queuing simulation of barge unloadings
(1) (2) (3) (4) (5) (6) (7)
DAY NUMBER DELAYED RANDOM NUMBER OF TOTAL TO BE RANDOM NUMBER
FROM PREVIOUS DAY NUMBER NIGHTLY ARRIVALS UNLOADED NUMBER UNLOADED
1 — 52 3 3 37 3
2 0 06 0 0 63 0
3 0 50 3 3 28 3
4 0 88 4 4 02 1
5 3 53 3 6 74 4
6 2 30 1 3 35 3
7 0 10 0 0 24 0
8 0 47 3 3 03 1
9 2 99 5 7 29 3
10 4 37 2 6 60 3
11 3 66 3 6 74 4
12 2 91 5 7 85 4
13 3 35 2 5 90 4
14 1 32 2 3 73 3
15 0 00 5 5 59 3
20 41 39
Total delays Total arrivals Total unloadings

Table 15.12 © 2009 Prentice-Hall, Inc. 15 – 47

 Port of New Orleans
◼ Three important pieces of information

Average number of barges 20 delays

=
delayed to the next day 15 days
= 1.33 barges delayed per day

Average number of 41 arrivals

= = 2.73 arrivals
nightly arrivals 15 days

Average number of barges 39 unloadings

unloaded each day = = 2.60 unloadings
15 days

© 2009 Prentice-Hall, Inc. 15 – 48

 Using Excel to Simulate the Port of
New Orleans Queuing Problem
◼ An Excel model for the Port of New Orleans
queuing simulation

Program 15.4A

© 2009 Prentice-Hall, Inc. 15 – 49

 Using Excel to Simulate the Port of
New Orleans Queuing Problem
◼ Output from the Excel formulas in Program 15.4A

Program 15.4B
© 2009 Prentice-Hall, Inc. 15 – 50
 Fixed Time Increment and Next Event
Increment Simulation Models
◼ Simulation models are often classified into fixed
time increment models and next event increment
models
◼ The terms refer to the frequency in which the
system status is updated
◼ Fixed time increments update the status of the
system at fixed time intervals
◼ Next event increment models update only when
the system status changes
◼ Fixed event models randomly generate the
number of events that occur during a time period
◼ Next event models randomly generate the time
that elapses until the next event occurs
© 2009 Prentice-Hall, Inc. 15 – 51
 Simulation Model for a
Maintenance Policy
◼ Simulation can be used to analyze different
maintenance policies before actually
implementing them
◼ Many options regarding staffing levels, parts
replacement schedules, downtime, and labor
costs can be compared
◼ This can including completely shutting down
factories for maintenance

© 2009 Prentice-Hall, Inc. 15 – 52

 Three Hills Power Company
◼ Three Hills provides power to a large city through
a series of almost 200 electric generators
◼ The company is concerned about generator
failures because a breakdown costs about $75
per generator per hour
◼ Their four repair people earn $30 per hour and
work rotating 8 hour shifts
◼ Management wants to evaluate the
1. Service maintenance cost
2. Simulated machine breakdown cost
3. Total cost

© 2009 Prentice-Hall, Inc. 15 – 53

 Three Hills Power Company
◼ There are two important maintenance system
components
◼ Time between successive generator breakdowns
which varies from 30 minutes to three hours
◼ The time it takes to repair the generators which
ranges from one to three hours in one hour
blocks
◼ A next event simulation is constructed to study
this problem

© 2009 Prentice-Hall, Inc. 15 – 54

 Three Hills Power Company
◼ Three Hills Start
flow diagram
Generate random number
for “Time Between
Breakdowns”

Record actual clock time

of breakdown

Examine time previous

repair ends

Is the
repairperson No Wait until previous
free to begin repair is completed
repair?

Figure 15.4 (a)

Yes

© 2009 Prentice-Hall, Inc. 15 – 55

 Three Hills Power Company
◼ Three Hills Generate random number
for repair time required
flow diagram
Compute time repair
completed

Compute hours of machine

downtime = Time repair
completed – Clock time
of breakdown

No Enough
breakdowns
simulated?

Yes
Figure 15.4 (b) Compute downtime and
comparative cost data End

© 2009 Prentice-Hall, Inc. 15 – 56

 Three Hills Power Company
◼ Time between generator breakdowns at Three
Hills Power
TIME BETWEEN
RECORDED NUMBER RANDOM
MACHINE OF TIMES CUMULATIVE NUMBER
FAILURES (HRS) OBSERVED PROBABILITY PROBABILITY INTERVAL
0.5 5 0.05 0.05 01 to 05
1.0 6 0.06 0.11 06 to 11
1.5 16 0.16 0.27 12 to 27
2.0 33 0.33 0.60 28 to 60
2.5 21 0.21 0.81 61 to 81
3.0 19 0.19 1.00 82 to 00
Total 100 1.00

Table 15.13
© 2009 Prentice-Hall, Inc. 15 – 57
 Three Hills Power Company
◼ Generator repair times required

NUMBER RANDOM
REPAIR TIME OF TIMES CUMULATIVE NUMBER
REQUIRED (HRS) OBSERVED PROBABILITY PROBABILITY INTERVAL
1 28 0.28 0.28 01 to 28
2 52 0.52 0.80 29 to 80
3 20 0.20 1.00 81 to 00
Total 100 1.00

Table 15.14

© 2009 Prentice-Hall, Inc. 15 – 58

 Three Hills Power Company
◼ Simulation of generator breakdowns and repairs
(5) (6) (9)
TIME REPAIR- RANDOM NUMBER
(2) (3) PERSON IS NUMBER (7) (8) OF
(1) RANDOM TIME (4) FREE TO FOR REPAIR TIME HOURS
BREAKDOWN NUMBER FOR BETWEEN TIME OF BEGIN THIS REPAIR TIME REPAIR MACHINE
NUMBER BREAKDOWNS BREAKDOWNS BREAKDOWN REPAIR TIME REQUIRED ENDS DOWN
1 57 2 02:00 02:00 07 1 03:00 1
2 17 1.5 03:30 03:30 60 2 05:30 2
3 36 2 05:30 05:30 77 2 07:30 2
4 72 2.5 08:00 08:00 49 2 10:00 2
5 85 3 11:00 11:00 76 2 13:00 2
6 31 2 13:00 13:00 95 3 16:00 3
7 44 2 15:00 16:00 51 2 18:00 3
8 30 2 17:00 18:00 16 1 19:00 2
9 26 1.5 18:30 19:00 14 1 20:00 1.5
10 09 1 19:30 20:00 85 3 23:00 3.5
11 49 2 21:30 23:00 59 2 01:00 3.5
12 13 1.5 23:00 01:00 85 3 04:00 5
13 33 2 01:00 04:00 40 2 06:00 5
14 89 3 04:00 06:00 42 2 08:00 4
15 13 1.5 05:30 08:00 52 2 10:00 4.5
Total 44
Table 15.15
© 2009 Prentice-Hall, Inc. 15 – 59
 Cost Analysis of Simulation
◼ The simulation of 15 generator breakdowns
covers 34 hours of operation
◼ The analysis of this simulation is
Service
maintenance = 34 hours of worker service time
cost x $30 per hour
= $1,020
Simulated machine
breakdown cost = 44 total hours of breakdown
x $75 lost per hour of downtime
= $3,300
Total simulated
maintenance cost of = Service cost + Breakdown cost
the current system = $1,020 + $3,300
= $4,320
© 2009 Prentice-Hall, Inc. 15 – 60
 Cost Analysis of Simulation
◼ The cost of $4,320 should be compared with
other alternative plans to see if this is a “good”
value
◼ The company might explore options like adding
another repairperson
◼ Strategies such as preventive maintenance might
also be simulated for comparison

© 2009 Prentice-Hall, Inc. 15 – 61

 Building an Excel Simulation Model
for Three Hills Power Company
◼ An Excel spreadsheet model for simulating the
Three Hills Power Company maintenance problem

Program 15.5A
© 2009 Prentice-Hall, Inc. 15 – 62
 Building an Excel Simulation Model
for Three Hills Power Company
◼ Output from Excel spreadsheet in Program 15.5A

Program 15.5B
© 2009 Prentice-Hall, Inc. 15 – 63
 Two Other Types of
Simulation Models

◼ Simulation models are often broken into

three categories
◼ The Monte Carlo method
◼ Operational gaming
◼ Systems simulation
◼ Though theoretically different,
computerized simulation has tended to
blur the differences

© 2009 Prentice-Hall, Inc. 15 – 64

 Operational Gaming
◼ Operational gaming refers to simulation involving
two or more competing players
◼ The best examples of this are military games and
business games
◼ These types of simulation allow the testing of
skills and decision-making in a competitive
environment

© 2009 Prentice-Hall, Inc. 15 – 65

 Systems Simulation
◼ Systems simulation is similar in that allows users
to test various managerial policies and decisions
to evaluate their effect on the operating
environment
◼ This models the dynamics of large systems
◼ A corporate operating system might model sales,
production levels, marketing policies,
investments, union contracts, utility rates,
financing, and other factors
◼ Economic simulations, often called econometric
models, are used by governments, bankers, and
large organizations to predict inflation rates,
domestic and foreign money supplies, and
unemployment levels
© 2009 Prentice-Hall, Inc. 15 – 66
 Systems Simulation
◼ Inputs and outputs of a typical economic system
simulation

Income Tax Gross National

Levels Product
Corporate Tax Inflation Rates
Rates Econometric Model Unemployment
Interest Rates (in Series of Rates
Mathematical
Government Equations) Monetary
Spending Supplies
Foreign Trade Population
Policy Growth Rates

Figure 15.5

© 2009 Prentice-Hall, Inc. 15 – 67

 Verification and Validation
◼ It is important that a simulation model be checked
to see that it is working properly and providing
good representation of the real world situation
◼ The verification process involves determining
that the computer model is internally consistent
and following the logic of the conceptual model
◼ Verification answers the question “Did we build
the model right?”
◼ Validation is the process of comparing a
simulation model to the real system it represents
to make sure it is accurate
◼ Validation answers the question “Did we build the
right model?”
© 2009 Prentice-Hall, Inc. 15 – 68
 Role of Computers in Simulation
◼ Computers are critical in simulating complex
tasks
◼ Three types of computer programming languages
are available to help the simulation process
◼ General-purpose languages
◼ Special-purpose simulation languages
1. These require less programming
2. Are more efficient and easier to check for errors
3. Have random number generators built in
◼ Pre-written simulation programs built to handle a
wide range of common problems
◼ Excel and add-ins can also be used for
simulation problems
© 2009 Prentice-Hall, Inc. 15 – 69
 Chapter 13

Project Management

To accompany
Quantitative Analysis for Management, Tenth Edition,
by Render, Stair, and Hanna © 2008 Prentice-Hall, Inc.
Power Point slides created by Jeff Heyl © 2009 Prentice-Hall, Inc.
 Learning Objectives
After completing this chapter, students will be able to:
1. Understand how to plan, monitor, and control
projects with the use of PERT and CPM
2. Determine earliest start, earliest finish, latest
start, latest finish, and slack times for each
activity, along with the total project
completion time
3. Reduce total project time at the least total
cost by crashing the network using manual
or linear programming techniques
4. Understand the important role of software in
project management

© 2009 Prentice-Hall, Inc. 13 – 2

 Chapter Outline

13.1 Introduction
13.2 PERT/CPM
13.3 PERT/Cost
13.4 Project Crashing
13.5 Other Topics in Project
Management

© 2009 Prentice-Hall, Inc. 13 – 3

 Introduction
 Most realistic projects are large and complex
 Tens of thousands of steps and millions of dollars
may be involved
 Managing large-scale, complicated projects
effectively is a difficult problem and the stakes are
high
 The first step in planning and scheduling a project
is to develop the work breakdown structure
 Time, cost, resource requirements, predecessors,
and people required are identified for each activity
 Then a schedule for the project can be developed

© 2009 Prentice-Hall, Inc. 13 – 4

 Project Management
It is nothing more (or less) than knowing
what the status of a project is:
when it should be done
how much (and if) it has slipped from the
original schedule
what the bottlenecks are
what you might drop to save some time

© 2009 Prentice-Hall, Inc. 13 – 5

 Project Management Models
History
 One of the earliest techniques was the Gantt chart
(used by US Navy).
 This type of chart shows the start and finish times
of one or more activities, as shown below:

© 2009 Prentice-Hall, Inc. 13 – 6

 Project Planning, Controlling
and Scheduling
Project Planning:
1. Setting goals.
2. Defining the project.
3. Tying needs into timed project activities.
4. Organizing the team.
Project Scheduling:
1. Tying resources to specific activities.
2. Relating activities to each other.
3. Updating and revising on regular basis.

Before Project Project Controlling:

1. Monitoring resources, costs, quality
During Project and budgets.
2. Revising and changing plans.
3. Shifting resources to meet demands.
© 2009 Prentice-Hall, Inc. 13 – 7
 Project Management Models
 PERT
 PERT/Cost
 Critical Path Method (CPM)

© 2009 Prentice-Hall, Inc. 13 – 8

 Introduction
 The program evaluation and review technique
(PERT)
PERT and the critical path method (CPM)
CPM are two
popular quantitative analysis techniques to help
plan, schedule, monitor, and control projects
 They were developed because there was a critical
need for a better way to manage.
 Originally the approaches differed in how they
estimated activity times
 PERT used three time estimates to develop a
probabilistic estimate of completion time
 CPM was a more deterministic technique
 They have become so similar they are commonly
considered one technique, PERT/CPM
© 2009 Prentice-Hall, Inc. 13 – 9
 Six Steps of PERT/CPM
1. Define the project and all of its significant
activities or tasks
2. Develop the relationships among the activities
and decide which activities must precede others
3. Draw the network connecting all of the activities
4. Assign time and/or cost estimates to each
activity
5. Compute the longest time path through the
network; this is called the critical path
6. Use the network to help plan, schedule, monitor,
and control the project
 The critical path is important since any delay in
these activities can delay the completion of the
project
© 2009 Prentice-Hall, Inc. 13 – 10
 PERT/CPM
 Given the large number of tasks in a project,
it is easy to see why the following questions
are important
1. When will the entire project be completed?
2. What are the critical activities or tasks in the
project, that is, the ones that will delay the
entire project if they are late?
3. Which are the non-critical activities, that is,
the ones that can run late without delaying
the entire project’s completion?
4. If there are three time estimates, what is the
probability that the project will be completed
by a specific date?
© 2009 Prentice-Hall, Inc. 13 – 11
 PERT/CPM
5. At any particular date, is the project on
schedule, behind schedule, or ahead of
schedule?
6. On any given date, is the money spent equal
to, less than, or greater than the budgeted
amount?
7. Are there enough resources available to
finish the project on time?
8. If the project is to be finished in a shorter
amount of time, what is the best way to
accomplish this at the least cost?
© 2009 Prentice-Hall, Inc. 13 – 12
 General Foundry Example of
PERT/CPM
 General Foundry, Inc. has long been trying to
avoid the expense of installing air pollution
control equipment
 The local environmental protection group has
recently given the foundry 16 weeks to install a
complex air filter system on its main smokestack
 General Foundry was warned that it will be forced
to close unless the device is installed in the
allotted period
 They want to make sure that installation of the
filtering system progresses smoothly and on time

© 2009 Prentice-Hall, Inc. 13 – 13

 General Foundry Example of
PERT/CPM
 Activities and immediate predecessors for
General Foundry
IMMEDIATE
ACTIVITY DESCRIPTION PREDECESSORS
A Build internal components —
B Modify roof and floor —
C Construct collection stack A
D Pour concrete and install frame B
E Build high-temperature burner C
F Install control system C
G Install air pollution device D, E
H Inspect and test F, G
Table 13.1

© 2009 Prentice-Hall, Inc. 13 – 14

 Drawing the PERT/CPM Network

 There are two common techniques for drawing

PERT networks
 Activity-on-node (AON)
AON where the nodes
represent activities
 Activity-on-arc (AOA)
AOA where the arcs are used to
represent the activities
 The AON approach is easier and more commonly
found in software packages
 One node represents the start of the project, one
node for the end of the project, and nodes for
each of the activities
 The arcs are used to show the predecessors for
each activity
© 2009 Prentice-Hall, Inc. 13 – 15
 General Foundry Example of
PERT/CPM
 Network for General Foundry

A C F
Build Internal Construct Install Control
Components Collection Stack System

E H
Start Inspect Finish
Build Burner and Test

B D G
Modify Roof Pour Concrete Install Pollution
and Floor and Install Frame Device

Figure 13.1

© 2009 Prentice-Hall, Inc. 13 – 16

 Activity Times
 In some situations, activity times are known with
certainty
 CPM assigns just one time estimate to each
activity and this is used to find the critical path
 In many projects there is uncertainty about activity
times
 PERT employs a probability distribution based on
three time estimates for each activity
 A weighted average of these estimates is used for
the time estimate and this is used to determine the
critical path

© 2009 Prentice-Hall, Inc. 13 – 17

 Activity Times
 The time estimates in PERT are

Optimistic time (a) = time an

activity will take if everything goes
as well as possible. There should be
only a small probability (say, 1/100) of
this occurring.
Pessimistic time (b) = time an
activity would take assuming very
unfavorable conditions. There
should also be only a small
probability that the activity will really
take this long.
Most likely time (m) = most
realistic time estimate to complete
the activity
© 2009 Prentice-Hall, Inc. 13 – 18
 Activity Times
 PERT often assumes time estimates follow a beta probability
distribution
 The beta probability distribution is often used when there is no solid
historical data upon which to activity time base estimates
 Found to be appropriate in many cases for determining an expected value
and variance for activity completion times

Probability of 1 in 100
of a Occurring
Probability

Probability of 1 in 100
of b Occurring

Activity Time
Most Most Most
Optimistic Likely Pessimistic
Time Time Time
(a) (m) (b)
Figure 13.2
© 2009 Prentice-Hall, Inc. 13 – 19
 Activity Times
 To find the expected activity time (t), the beta
distribution weights the estimates as follows

a + 4m + b
t=
6

 To compute the dispersion or variance of activity

completion time,
time we use the formula
2
b−a
Variance =  
 6 

© 2009 Prentice-Hall, Inc. 13 – 20

 Activity Times
 Time estimates (weeks) for General Foundry

MOST EXPECTED VARIANCE,

OPTIMISTIC, PROBABLE, PESSIMISTIC, TIME,
ACTIVITY a m b t = [(a + 4m + b)/6] [(b – a)/6]2
A 1 2 3 2 4/36
B 2 3 4 3 4/36
C 1 2 3 2 4/36
D 2 4 6 4 16/36
E 1 4 7 4 36/36
F 1 2 9 3 64/36
G 3 4 11 5 64/36
H 1 2 3 2 4/36
25

Table 13.2

© 2009 Prentice-Hall, Inc. 13 – 21

 How to Find the Critical Path
 We accept the expected completion time for
each task as the actual time for now
 The total of 25 weeks in Table 13.2 does not take
into account the obvious fact that some of the
tasks could be taking place at the same time
 To find out how long the project will take we
perform the critical path analysis for the network
 The critical path is the longest path through the
network

© 2009 Prentice-Hall, Inc. 13 – 22

 How to Find the Critical Path
 General Foundry’s network with expected activity
times

A 2 C 2 F 3

E 4 H 2
Start Finish

B 3 D 4 G 5

Figure 13.3

© 2009 Prentice-Hall, Inc. 13 – 23

 How to Find the Critical Path
 To find the critical path, need to determine the
following quantities for each activity in the
network
1. Earliest start time (ES):
ES the earliest time an
activity can begin without violation of immediate
predecessor requirements
2. Earliest finish time (EF):
EF the earliest time at
which an activity can end
3. Latest start time (LS):
LS the latest time an activity
can begin without delaying the entire project
4. Latest finish time (LF):
LF the latest time an activity
can end without delaying the entire project

© 2009 Prentice-Hall, Inc. 13 – 24

 How to Find the Critical Path
 In the nodes, the activity time and the early and
late start and finish times are represented in the
following manner
ACTIVITY t
ES EF
LS LF

 Earliest times are computed as

Earliest finish time =

Earliest start time
+ Expected activity time
EF = ES + t
Earliest start = Largest of the earliest finish times of
immediate predecessors
ES = Largest EF of immediate predecessors
© 2009 Prentice-Hall, Inc. 13 – 25
 How to Find the Critical Path
 At the start of the project we set the time to zero
 Thus ES = 0 for both A and B

A t=2
ES = 0 EF = 0 + 2 = 2

Start

B t=3
ES = 0 EF = 0 + 3 = 3

© 2009 Prentice-Hall, Inc. 13 – 26

 How to Find the Critical Path
 General Foundry’s ES and EF times

A 2 C 2 F 3
0 2 2 4 4 7

E 4 H 2
Start 4 8 13 15 Finish

B 3 D 4 G 5
0 3 3 7 8 13

Figure 13.4

© 2009 Prentice-Hall, Inc. 13 – 27

 How to Find the Critical Path
 Latest times are computed as

Latest start time =

Latest finish time
– Expected activity time
LS = LF – t
Latest finish time = Smallest of latest start times
for following activities
LF = Smallest LS of following activities
 For activity H

LS = LF – t = 15 – 2 = 13 weeks

© 2009 Prentice-Hall, Inc. 13 – 28

 How to Find the Critical Path
 General Foundry’s LS and LF times

A 2 C 2 F 3
0 2 2 4 4 7
0 2 2 4 10 13

E 4 H 2
Start 4 8 13 15 Finish
4 8 13 15

B 3 D 4 G 5
0 3 3 7 8 13
1 4 4 8 8 13

Figure 13.5

© 2009 Prentice-Hall, Inc. 13 – 29

 How to Find the Critical Path
 Once ES, LS, EF, and LF have been determined, it
is a simple matter to find the amount of slack time
that each activity has
Slack = LS – ES, or Slack = LF – EF
 From Table 13.3 we see activities A, C, E, G, and H
have no slack time
 These are called critical activities and they are said
to be on the critical path
 The total project completion time is 15 weeks
 Industrial managers call this a boundary timetable

© 2009 Prentice-Hall, Inc. 13 – 30

 How to Find the Critical Path
 General Foundry’s schedule and slack times

EARLIEST EARLIEST LATEST LATEST ON

START, FINISH, START, FINISH, SLACK, CRITICAL
ACTIVITY ES EF LS LF LS – ES PATH?
A 0 2 0 2 0 Yes
B 0 3 1 4 1 No
C 2 4 2 4 0 Yes
D 3 7 4 8 1 No
E 4 8 4 8 0 Yes
F 4 7 10 13 6 No
G 8 13 8 13 0 Yes
H 13 15 13 15 0 Yes

Table 13.3

© 2009 Prentice-Hall, Inc. 13 – 31

 How to Find the Critical Path
 General Foundry’s critical path

A 2 C 2 F 3
0 2 2 4 4 7
0 2 2 4 10 13

E 4 H 2
Start 4 8 13 15 Finish
4 8 13 15

B 3 D 4 G 5
0 3 3 7 8 13
1 4 4 8 8 13

Figure 13.6

© 2009 Prentice-Hall, Inc. 13 – 32

 Probability of Project Completion

 The critical path analysis helped determine the

expected project completion time of 15 weeks
 But variation in activities on the critical path can
affect overall project completion, and this is a
major concern
 If the project is not complete in 16 weeks, the
foundry will have to close
 PERT uses the variance of critical path activities
to help determine the variance of the overall
project

Project variance = ∑ variances of activities

on the critical path

© 2009 Prentice-Hall, Inc. 13 – 33

 Probability of Project Completion
 From Table 13.2 we know that

ACTIVITY VARIANCE
A 4/36
B 4/36
C 4/36
D 16/36
E 36/36
F 64/36
G 64/36
H 4/36

 Hence, the project variance is

Project variance = 4/36 + 4/36 + 36/36 + 64/36 + 4/36 = 112/36 = 3.111

© 2009 Prentice-Hall, Inc. 13 – 34

 Probability of Project Completion

 We know the standard deviation is just the

square root of the variance, so

Project standard deviation = σ T = Project variance

= 3.11 = 1.76 weeks
 We assume activity times are independent and
total project completion time is normally
distributed

© 2009 Prentice-Hall, Inc. 13 – 35

 Probability of Project Completion
 The project’s expected completion date is 15 weeks.
 Assume that the total project completion time follows a
normal probability distribution
 Chart tells us that there is a 50% chance of completing the
entire project in less than 15 weeks and a 50% chance it will
exceed 15 weeks

Standard Deviation = 1.76 Weeks

15 Weeks
(Expected Completion Time)
Figure 13.7
© 2009 Prentice-Hall, Inc. 13 – 36
 Probability of Project Completion
 The standard normal equation can be applied as
follows

Due date − Expected date of completion

Z=
σT
16 weeks − 15 weeks
= = 0.57
1.76 weeks
 From Appendix A we find the probability of
0.71566 associated with this Z value
 That means there is a 71.6% probability this
project can be completed in 16 weeks or less

© 2009 Prentice-Hall, Inc. 13 – 37

 Probability of Project Completion
 Probability of General Foundry meeting the 16-
week deadline

Expected Time is 15 Weeks 0.57 Standard Deviations

Probability
(T ≤ 16 Weeks)
is 71.6%

15 16
Time
Weeks Weeks
Figure 13.8

© 2009 Prentice-Hall, Inc. 13 – 38

 What PERT Was Able to Provide
 PERT has been able to provide the project manager
with several valuable pieces of information
 The project’s expected completion date is 15 weeks
 There is a 71.6% chance that the equipment will be in
place within the 16-week deadline
 Five activities (A, C, E, G, H) are on the critical path
 If any one of the critical activities is delayed for any
reason, the entire project will be delayed.
 Three activities (B, D, F) are not critical but have some
slack time built in
 They can borrow from their resources, if needed, possibly
to speed up the entire project.
 A detailed schedule of activity starting and ending
dates has been made available

© 2009 Prentice-Hall, Inc. 13 – 39

 Sensitivity Analysis and
Project Management
 The time required to complete an activity can vary
from the projected or expected time
 If the activity is on the critical path, the
completion time of the project will change
 This will also have an impact on ES, EF, LS, and
LF times for other activities
 The exact impact depends on the relationship
between the various activities
 A predecessor activity is one that must be
accomplished before the given activity can be
started
 A successor activity is one that can be started
only after the given activity is finished
© 2009 Prentice-Hall, Inc. 13 – 40
 Sensitivity Analysis and
Project Management
 Impact of an increase (decrease) in an activity
time for a critical path activity

SUCCESSOR PARALLEL PREDECESSOR

ACTIVITY TIME ACTIVITY ACTIVITY ACTIVITY
Earliest start Increase (decrease) No change No change

Earliest finish Increase (decrease) No change No change

Latest start Increase (decrease) Increase (decrease) No change

Latest finish Increase (decrease) Increase (decrease) No change

Slack No change Increase (decrease) No change

Table 13.4

© 2009 Prentice-Hall, Inc. 13 – 41

 PERT/COST
 Although PERT is an excellent method of
monitoring and controlling project length, it does
not consider the very important factor of project
cost
 PERT/Cost is a modification of PERT that allows a
manager to plan, schedule, monitor, and control
cost as well as time
 Using PERT/Cost to plan, schedule, monitor, and
control project cost helps accomplish the sixth
and final step of PERT

© 2009 Prentice-Hall, Inc. 13 – 42

Planning and Scheduling Project Costs:
Budgeting Process
 The overall approach in the budgeting
process of a project is to determine how
much is to be spent every week or month
 This can be accomplished in four basic
budgeting steps

© 2009 Prentice-Hall, Inc. 13 – 43

 Four Steps of the Budgeting Process

1. Identify all costs associated with each of the

activities then add these costs together to get
one estimated cost or budget for each activity
2. In large projects, activities can be combined into
larger work packages. A work package is simply
a logical collection of activities.
3. Convert the budgeted cost per activity into a
cost per time period by assuming that the cost of
completing any activity is spent at a uniform rate
over time
4. Using the ES and LS times, find out how much
money should be spent during each week or
month to finish the project by the date desired
© 2009 Prentice-Hall, Inc. 13 – 44
 Budgeting for General Foundry

 The Gantt chart in Figure 13.9 illustrates this

project
 The horizontal bars shown when each activity will
be performed based on its ES-EF times
 We determine how much will be spent on each
activity during each week and fill these amounts
into a chart in place of the bars
 The following two tables show the activity costs
and budgeted cost for the General Foundry
project

© 2009 Prentice-Hall, Inc. 13 – 45

 Budgeting for General Foundry

 Gantt chart General Foundry project

A
B
C
Activity

D
E
F
G
H

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Week
Figure 13.9

© 2009 Prentice-Hall, Inc. 13 – 46

 Budgeting for General Foundry

 Activity costs for General Foundry

EARLIEST LATEST TOTAL BUDGETED
START, START, EXPECTED BUDGETED COST PER
ACTIVITY ES LS TIME, t COST ($) WEEK ($)
A 0 0 2 22,000 11,000
B 0 1 3 30,000 10,000
C 2 2 2 26,000 13,000
D 3 4 4 48,000 12,000
E 4 4 4 56,000 14,000
F 4 10 3 30,000 10,000
G 8 8 5 80,000 16,000
H 13 13 2 16,000 8,000
Total 308,000

Table 13.5

© 2009 Prentice-Hall, Inc. 13 – 47

 Budgeting for General Foundry
 Budgeted cost for General Foundry

WEEK
ACTIVITY 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 TOTAL
A 11 11 22

B 10 10 10 30

C 13 13 26

D 12 12 12 12 48

E 14 14 14 14 56

F 10 10 10 30

G 16 16 16 16 16 80

H 8 8 16

308

Total per week 21 21 23 25 36 36 36 14 16 16 16 16 16 8 8

Total to date 21 42 65 90 126 162 198 212 228 244 260 276 292 300 308

Table 13.6

© 2009 Prentice-Hall, Inc. 13 – 48

 Budgeting for General Foundry

 It is also possible to prepare a budget based on

the latest starting time
 This budget will delay the expenditure of funds
until the last possible moment
 The following table shows the latest start budget
for the General Foundry project
 The two tables form a budget range
 Any budget can be chosen between these two
values depending on when the company wants to
actually spend the money
 The budget ranges are plotted in Figure 13.10

© 2009 Prentice-Hall, Inc. 13 – 49

 Budgeting for General Foundry
 Late start budgeted cost for General Foundry

WEEK
ACTIVITY 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 TOTAL
A 11 11 22

B 10 10 10 30

C 13 13 26

D 12 12 12 12 48

E 14 14 14 14 56

F 10 10 10 30

G 16 16 16 16 16 80

H 8 8 16

308

Total per week 11 21 23 23 26 26 26 26 16 16 26 26 26 8 8

Total to date 11 32 55 78 104 130 156 182 198 214 240 266 292 300 308

Table 13.7

© 2009 Prentice-Hall, Inc. 13 – 50

 Budgeting for General Foundry
Total
Budgeted  A manager can
Cost
$300,000 – choose any budget
Budget Using
that falls between
250,000 – Earliest Start the budgets
Times, ES presented in the
200,000 –
two tables
 The two tables
150,000 –
form feasible
Budget Using budget ranges
Latest Start
100,000 – Times, LS

50,000 –

0–

Figure 13.10
| | | | | | | | | | | | | | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Weeks
© 2009 Prentice-Hall, Inc. 13 – 51
 Monitoring and Controlling
Project Costs
 Costs are monitored and controlled to ensure the
project is progressing on schedule and that cost
overruns are kept to a minimum
 The status of the entire project should be checked
periodically
 The project is now in it’s 6th week of 15 weeks
 Activities A,B, and C have completed at costs of
$20,000, $36,000 and $26,000 respectively
 Activity D is only 10% complete at a cost of $6,000
 Activity E is 20% complete at a cost of $20,000
 Activity F is 20% complete with a cost of $4,000
 What is the value of the work completed?
 Are there any cost overruns?

© 2009 Prentice-Hall, Inc. 13 – 52

 Monitoring and Controlling
Project Costs
 Monitoring and controlling budgeted cost

VALUE OF
TOTAL WORK ACTIVITY
BUDGETED PERCENT OF COMPLETED ACTUAL DIFFERENCE
ACTIVITY COST ($) COMPLETION ($) COST ($) ($)
A 22,000 100 22,000 20,000 –2,000
B 30,000 100 30,000 36,000 6,000
C 26,000 100 26,000 26,000 0
D 48,000 10 4,800 6,000 1,200
E 56,000 20 11,200 20,000 8,800
F 30,000 20 6,000 4,000 –2,000
G 80,000 0 0 0 0
H 16,000 0 0 0 0
Total 100,000 112,000 12,000

Table 13.8 Overrun

© 2009 Prentice-Hall, Inc. 13 – 53

 Monitoring and Controlling
Project Costs
 The value of work completed, or the cost to date
for any activity, can be computed as follows
Value of work (Percentage of work complete)
=
completed x (Total activity budget)

 The activity difference is also of interest

Activity difference = Actual cost

– Value of work completed

 A negative activity difference is a cost underrun

and a positive activity difference is a cost overrun

© 2009 Prentice-Hall, Inc. 13 – 54

 Monitoring and Controlling
Project Costs
 Value completed is $100,000 while actual cost
is $112,000; cost overrun of $12,000
 Using the earliest start times budget, by the
end of the 6th week we should have completed
 75% of D (vs 10%), 50% of E (vs 20%) and 66.7% of
F (vs 20%) and spent $162,000 so the project is
behind schedule
 Using the latest start times budget, by the end
of the 6th week we should have completed
 50% of D (vs 10%), 50% of E (vs 20%) and 0% of F
(vs 20%) and spent $130,000 so the project is also
behind schedule

© 2009 Prentice-Hall, Inc. 13 – 55

 Project Crashing
 Projects will sometimes have deadlines
that are impossible to meet using normal
procedures
 By using exceptional methods it may be
possible to finish the project in less time
than normally required
 However, this usually increases the cost
of the project
 Reducing a project’s completion time is
called crashing

© 2009 Prentice-Hall, Inc. 13 – 56

 Project Crashing
 Crashing a project starts with using the
normal time to create the critical path
 The normal cost is the cost for completing
the activity using normal procedures
 If the project will not meet the required
deadline, extraordinary measures must be
taken
 The crash time is the shortest possible
activity time and will require additional
resources
 The crash cost is the price of completing the
activity in the earlier-than-normal time
© 2009 Prentice-Hall, Inc. 13 – 57
Four Steps to Project Crashing

1. Find the normal critical path and identify

the critical activities
2. Compute the crash cost per week (or
other time period) for all activities in the
network using the formula

Crash cost – Normal cost

Crash cost/Time period =
Normal time – Crash time

© 2009 Prentice-Hall, Inc. 13 – 58

Four Steps to Project Crashing

3. Select the activity on the critical path

with the smallest crash cost per week
and crash this activity to the maximum
extent possible or to the point at which
your desired deadline has been reached
4. Check to be sure that the critical path
you were crashing is still critical. If the
critical path is still the longest path
through the network, return to step 3. If
not, find the new critical path and return
to step 2.

© 2009 Prentice-Hall, Inc. 13 – 59

 General Foundry Example
 General Foundry has been given 14 weeks instead of
16 weeks to install the new equipment
 The critical path for the project is 15 weeks
 What options do they have?
 The normal and crash times and costs are shown in
Table 13.9
 Crash costs are assumed to be linear and Figure 13.11
shows the crash cost for activity B
 Crashing activity A will shorten the completion time to
14 but it creates a second critical path B,D,G,H
because when you recalculate the LF and LS times for
B and D they now match the EF and ES
 Any further crashing must be done to both critical
paths

© 2009 Prentice-Hall, Inc. 13 – 60

 General Foundry Example
 Normal and crash data for General Foundry

TIME (WEEKS) COST ($)

CRASH
COST PER CRITICAL
ACTIVITY NORMAL CRASH NORMAL CRASH WEEK ($) PATH?
A 2 1 22,000 23,000 1,000 Yes
B 3 1 30,000 34,000 2,000 No
C 2 1 26,000 27,000 1,000 Yes
D 4 3 48,000 49,000 1,000 No
E 4 2 56,000 58,000 1,000 Yes
F 3 2 30,000 30,500 500 No
G 5 2 80,000 86,000 2,000 Yes
H 2 1 16,000 19,000 3,000 Yes
Table 13.9

© 2009 Prentice-Hall, Inc. 13 – 61

General Foundry - QM

© 2009 Prentice-Hall, Inc. 13 – 62

General Foundry - QM

© 2009 Prentice-Hall, Inc. 13 – 63

 Revised Path After Crashing
 After crashing the project by 1 week, this is the new
network
 Two critIcal paths
 A-C-E-G-H
 B-D-G-H NODE Time ES EF LS LF
A 1 0 1 0 1
B 3 0 3 0 3
C 2 1 3 1 3
D 4 3 7 3 7
E 4 3 7 3 7
F 3 3 6 9 12
G 5 7 12 7 12
H 2 12 14 12 14

© 2009 Prentice-Hall, Inc. 13 – 64

 Chapter 5

Forecasting

To accompany
Quantitative Analysis for Management, Eleventh Edition,
by Render, Stair, and Hanna
Power Point slides created by Brian Peterson
 Forecasting Models
Forecasting
Techniques

Qualitative Time-Series Causal

Models Methods Methods

Delphi Moving Regression

Methods Average Analysis

Jury of Executive Exponential Multiple

Opinion Smoothing Regression

Sales Force Trend

Composite Projections
Figure 5.1
Consumer
Decomposition
Market Survey

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-2

 Qualitative Models
 Qualitative models incorporate judgmental
or subjective factors.
 These are useful when subjective factors
are thought to be important or when
accurate quantitative data is difficult to
obtain.
 Common qualitative techniques are:
 Delphi method.
 Jury of executive opinion.
 Sales force composite.
 Consumer market surveys.

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-3

 Qualitative Models
 Delphi Method – This is an iterative group
process where (possibly geographically
dispersed) respondents provide input to decision
makers.
 Jury of Executive Opinion – This method collects
opinions of a small group of high-level managers,
possibly using statistical models for analysis.
 Sales Force Composite – This allows individual
salespersons estimate the sales in their region
and the data is compiled at a district or national
level.
 Consumer Market Survey – Input is solicited from
customers or potential customers regarding their
purchasing plans.
Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-4
 Time-Series Models
 Time-series models attempt to predict
the future based on the past.
 Common time-series models are:
 Moving average.
 Exponential smoothing.
 Trend projections.
 Decomposition.
 Regression analysis is used in trend
projections and one type of
decomposition model.

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-5

 Scatter Diagrams
Wacker Distributors wants to forecast sales for
three different products (annual sales in the table,
in units):
TELEVISION COMPACT DISC
YEAR RADIOS
SETS PLAYERS
1 250 300 110
2 250 310 100
3 250 320 120
4 250 330 140
5 250 340 170
6 250 350 150
7 250 360 160
8 250 370 190
Table 5.1 9 250 380 200
10 250 390 190
Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-6
 Scatter Diagram for TVs
(a)
 Sales appear to be
Annual Sales of Televisions

330 –
constant over time
250 –          
Sales = 250
200 –
 A good estimate of
150 – sales in year 11 is
100 – 250 televisions
50 –
| | | | | | | | | |

0 1 2 3 4 5 6 7 8 9 10
Time (Years)
Figure 5.2a

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-7

 Scatter Diagram for Radios
(b)
420 –  Sales appear to be
400 – increasing at a
Annual Sales of Radios

380 –  constant rate of 10


360 – 
 radios per year
340 – 
 Sales = 290 + 10(Year)
320 – 

300 –  
 A reasonable
280 –
estimate of sales in
year 11 is 400
| | | | | | | | | |
0 1 2 3 4 5 6 7 8 9 10 radios.
Time (Years)
Figure 5.2b

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-8

 Scatter Diagram for CD
Players
 This trend line may
(c) not be perfectly
Annual Sales of CD Players

200 –
  accurate because
180 – 
of variation from
160 –  year to year

140 –   Sales appear to be

increasing
120 –

  A forecast would
100 –  probably be a
| | | | | | | | | |
larger figure each
0 1 2 3 4 5 6 7 8 9 10 year
Time (Years)
Figure 5.2c

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-9

 Measures of Forecast Accuracy

 We compare forecasted values with actual values

to see how well one model works or to compare
models.
Forecast error = Actual value – Forecast value

 One measure of accuracy is the mean absolute

deviation (MAD):

MAD 
 forecast error
n

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-10

 Measures of Forecast Accuracy
Using a naïve forecasting model we can compute the MAD:
ACTUAL
SALES OF ABSOLUTE VALUE OF
CD FORECAST ERRORS (DEVIATION),
YEAR PLAYERS SALES (ACTUAL – FORECAST)
1 110 — —
2 100 110 |100 – 110| = 10
3 120 100 |120 – 110| = 20
4 140 120 |140 – 120| = 20
5 170 140 |170 – 140| = 30
6 150 170 |150 – 170| = 20
7 160 150 |160 – 150| = 10
8 190 160 |190 – 160| = 30
9 200 190 |200 – 190| = 10
10 190 200 |190 – 200| = 10
Table 5.2 11 — 190 —
Sum of |errors| = 160
MAD = 160/9 = 17.8
Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-11
 Measures of Forecast Accuracy
Using a naïve forecasting model we can compute the MAD:
ACTUAL ABSOLUTE VALUE OF
SALES OF CD FORECAST ERRORS (DEVIATION),
YEAR PLAYERS SALES (ACTUAL – FORECAST)
1 110 — —
2 100 110 |100 – 110| = 10
3 120 100 |120 – 110| = 20

MAD 

4
5
forecast error 140
170
120

140
160
 17.8
|140 – 120| = 20
|170 – 140| = 30
6 150 n 170 9 |150 – 170| = 20
7 160 150 |160 – 150| = 10
8 190 160 |190 – 160| = 30
9 200 190 |200 – 190| = 10
10 190 200 |190 – 200| = 10
11 — 190 —
Sum of |errors| = 160
MAD = 160/9 = 17.8

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-12

Table 5.2
 Measures of Forecast Accuracy
 There are other popular measures of forecast
accuracy.
 The mean squared error:

MSE 
 ( error ) 2

n
 The mean absolute percent error:
error
 actual
MAPE  100 %
n
 And bias is the average error.

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-13

 Time-Series Forecasting Models

 A time series is a sequence of evenly

spaced events.
 Time-series forecasts predict the future
based solely on the past values of the
variable, and other variables are
ignored.

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-14

 Components of a Time-Series

A time series typically has four components:

1. Trend (T) is the gradual upward or downward
movement of the data over time.
2. Seasonality (S) is a pattern of demand
fluctuations above or below the trend line that
repeats at regular intervals.
3. Cycles (C) are patterns in annual data that
occur every several years.
4. Random variations (R) are “blips” in the data
caused by chance or unusual situations, and
follow no discernible pattern.

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-15

 Decomposition of a Time-Series
Product Demand Charted over 4 Years, with Trend
and Seasonality Indicated
Demand for Product or Service

Trend
Component

Seasonal Peaks

Actual
Demand
Line
Average Demand
over 4 Years

| | | |

Figure 5.3 Year Year Year Year

1 2 3 4
Time
Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-16
 Decomposition of a Time-Series

 There are two general forms of time-series

models:
 The multiplicative model:

Demand = T x S x C x R

 The additive model:

Demand = T + S + C + R

 Models may be combinations of these two

forms.
 Forecasters often assume errors are
normally distributed with a mean of zero.

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-17

 Moving Averages

 Moving averages can be used when

demand is relatively steady over time.
 The next forecast is the average of the
most recent n data values from the time
series.
 This methods tends to smooth out short-
term irregularities in the data series.

Sum of demands in previous n periods

Moving average forecast 
n

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-18

 Moving Averages
 Mathematically:

Yt  Yt 1  ...  Yt  n1
Ft 1 
n

Where:
Ft 1 = forecast for time period t + 1
Yt = actual value in time period t
n = number of periods to average

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-19

 Wallace Garden Supply

 Wallace Garden Supply wants to

forecast demand for its Storage Shed.
 They have collected data for the past
year.
 They are using a three-month moving
average to forecast demand (n = 3).

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-20

 Wallace Garden Supply

MONTH ACTUAL SHED SALES THREE-MONTH MOVING AVERAGE

January 10
February 12
March 13
April 16 (10 + 12 + 13)/3 = 11.67
May 19 (12 + 13 + 16)/3 = 13.67
June 23 (13 + 16 + 19)/3 = 16.00
July 26 (16 + 19 + 23)/3 = 19.33
August 30 (19 + 23 + 26)/3 = 22.67
September 28 (23 + 26 + 30)/3 = 26.33
October 18 (26 + 30 + 28)/3 = 28.00
November 16 (30 + 28 + 18)/3 = 25.33
December 14 (28 + 18 + 16)/3 = 20.67
January — (18 + 16 + 14)/3 = 16.00

Table 5.3
Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-21
 Weighted Moving Averages
 Weighted moving averages use weights to put
more emphasis on previous periods.
 This is often used when a trend or other pattern is
emerging.

Ft 1 
 ( Weight in period i )( Actual value in period)
 ( Weights)
 Mathematically:
w1Yt  w2Yt 1  ...  wnYt  n1
Ft 1 
w1  w2  ...  wn
where
wi = weight for the ith observation
Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-22
 Wallace Garden Supply

 Wallace Garden Supply decides to try a

weighted moving average model to forecast
demand for its Storage Shed.
 They decide on the following weighting
scheme:
WEIGHTS APPLIED PERIOD
3 Last month
2 Two months ago
1 Three months ago
3 x Sales last month + 2 x Sales two months ago + 1 X Sales three months ago
6
Sum of the weights

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-23

 Wallace Garden Supply
THREE-MONTH WEIGHTED
MONTH ACTUAL SHED SALES MOVING AVERAGE
January 10
February 12
March 13
April 16 [(3 X 13) + (2 X 12) + (10)]/6 = 12.17
May 19 [(3 X 16) + (2 X 13) + (12)]/6 = 14.33
June 23 [(3 X 19) + (2 X 16) + (13)]/6 = 17.00
July 26 [(3 X 23) + (2 X 19) + (16)]/6 = 20.50
August 30 [(3 X 26) + (2 X 23) + (19)]/6 = 23.83
September 28 [(3 X 30) + (2 X 26) + (23)]/6 = 27.50
October 18 [(3 X 28) + (2 X 30) + (26)]/6 = 28.33
November 16 [(3 X 18) + (2 X 28) + (30)]/6 = 23.33
December 14 [(3 X 16) + (2 X 18) + (28)]/6 = 18.67
January — [(3 X 14) + (2 X 16) + (18)]/6 = 15.33
Table 5.4
Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-24
 Exponential Smoothing
 Exponential smoothing is a type of moving
average that is easy to use and requires little
record keeping of data.

New forecast = Last period’s forecast

+ (Last period’s actual demand
– Last period’s forecast)

Here  is a weight (or smoothing constant) in

which 0≤≤1.

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-25

 Exponential Smoothing
Mathematically:

Ft 1  Ft   (Yt  Ft )

Where:
Ft+1 = new forecast (for time period t + 1)
Ft = pervious forecast (for time period t)
 = smoothing constant (0 ≤  ≤ 1)
Yt = pervious period’s actual demand

The idea is simple – the new estimate is the old

estimate plus some fraction of the error in the
last period.

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-26

 Exponential Smoothing Example
 In January, February’s demand for a certain
car model was predicted to be 142.
 Actual February demand was 153 autos
 Using a smoothing constant of  = 0.20, what
is the forecast for March?

New forecast (for March demand) = 142 + 0.2(153 – 142)

= 144.2 or 144 autos

 If actual demand in March was 136 autos, the

April forecast would be:
New forecast (for April demand) = 144.2 + 0.2(136 – 144.2)
= 142.6 or 143 autos

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-27

 Selecting the Smoothing Constant

 Selecting the appropriate value for  is key

to obtaining a good forecast.
 The objective is always to generate an
accurate forecast.
 The general approach is to develop trial
forecasts with different values of  and
select the  that results in the lowest MAD.

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-28

 Exponential Smoothing
Port of Baltimore Exponential Smoothing Forecast
for =0.1 and =0.5.
ACTUAL
TONNAGE FORECAST FORECAST
QUARTER UNLOADED USING  =0.10 USING  =0.50
1 180 175 175
2 168 175.5 = 175.00 + 0.10(180 – 175) 177.5
3 159 174.75 = 175.50 + 0.10(168 – 175.50) 172.75
4 175 173.18 = 174.75 + 0.10(159 – 174.75) 165.88
5 190 173.36 = 173.18 + 0.10(175 – 173.18) 170.44
6 205 175.02 = 173.36 + 0.10(190 – 173.36) 180.22
7 180 178.02 = 175.02 + 0.10(205 – 175.02) 192.61
8 182 178.22 = 178.02 + 0.10(180 – 178.02) 186.30
9 ? 178.60 = 178.22 + 0.10(182 – 178.22) 184.15
Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-29
Table 5.5
 Exponential Smoothing
Absolute Deviations and MADs for the Port of
Baltimore Example
ACTUAL ABSOLUTE ABSOLUTE
TONNAGE FORECAST DEVIATIONS FORECAST DEVIATIONS
QUARTER UNLOADED WITH  = 0.10 FOR  = 0.10 WITH  = 0.50 FOR  = 0.50
1 180 175 5….. 175 5….
2 168 175.5 7.5.. 177.5 9.5..
3 159 174.75 15.75 172.75 13.75
4 175 173.18 1.82 165.88 9.12
5 190 173.36 16.64 170.44 19.56
6 205 175.02 29.98 180.22 24.78
7 180 178.02 1.98 192.61 12.61
8 182 178.22 3.78 186.30 4.3..
Sum of absolute deviations 82.45 98.63
Σ|deviations|
MAD = = 10.31 MAD = 12.33
n

Table 5.6
Best choice
Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-30
 Trend Projections
 Trend projection fits a trend line to a
series of historical data points.
 The line is projected into the future for
medium- to long-range forecasts.
 Several trend equations can be
developed based on exponential or
quadratic models.
 The simplest is a linear model developed
using regression analysis.

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-31

 Trend Projection
The mathematical form is

Yˆ  b0  b1 X

Where
Ŷ = predicted value
b0 = intercept
b1 = slope of the line
X = time period (i.e., X = 1, 2, 3, …, n)

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-32

 Midwestern Manufacturing
 Midwest Manufacturing has a demand for
electrical generators from 2004 – 2010 as given
in the table below.

YEAR ELECTRICAL GENERATORS SOLD

2004 74
2005 79
2006 80
2007 90
2008 105
2009 142
Table 5.7
2010 122
Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-33
 Midwestern Manufacturing
Company Example
 The forecast equation is

Yˆ  56.71  10.54 X

 To project demand for 2011, we use the coding

system to define X = 8
(sales in 2011) = 56.71 + 10.54(8)
= 141.03, or 141 generators

 Likewise for X=9

(sales in 2012) = 56.71 + 10.54(9)
= 151.57, or 152 generators
Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-34
 Midwestern Manufacturing

Electrical Generators and the Computed Trend Line

Figure 5.4

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-35

 Trend projections
 Observing a time series for the GDP of
Jordan from 2001 to 2011, annual data
20
18
16
14
12
JD bl

10
8
6
4
2
0
 Souce:
0
2000 IMF
2 World
4 Development
6
2005 8 Database
10
2010 12
year

36
 Trend projections
 Observing a time series for the GDP of
Jordan from 2001 to 2011, annual data
20
18 y = 1.4431x + 3.2106
16 R² = 0.9355
14
12
JD bl

10
8
6
4
2
0
 Souce:
0
2000 IMF
2 World
4 Development
6
2005 8 Database
10
2010 12
year

37
 Trend projections

 Different trend models can be

compared
 E.g.
20 linear versus quadratic
18

16
y = 4.9615x0.4884
14
R² = 0.8158
12
y = 1.4431x + 3.2106
JD bl

10
R² = 0.9355
8

0
0 2 4 6 8 10 12
2000 2005
year 2010
38
 Trend projections

 Different trend models can be

compared
20

18 E.g. linear versus

y =exponential
5.092e0.1294x
16 R² = 0.977
14

12 y = 1.4431x + 3.2106
JD bl

10 R² = 0.9355
8

0
0 2 4 6 8 10 12
2000 2005
year 2010
39
 Seasonal Variations
 Recurring variations over time may
indicate the need for seasonal
adjustments in the trend line.
 A seasonal index indicates how a
particular season compares with an
average season.
 When no trend is present, the seasonal
index can be found by dividing the
average value for a particular season by
the average of all the data.

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-40

 Eichler Supplies

 Eichler Supplies sells telephone

answering machines.
 Sales data for the past two years has
been collected for one particular model.
 The firm wants to create a forecast that
includes seasonality.

Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-41

 Eichler Supplies Answering Machine
Sales and Seasonal Indices
AVERAGE
SALES DEMAND
AVERAGE TWO- MONTHLY SEASONAL
MONTH YEAR 1 YEAR 2 YEAR DEMAND DEMAND INDEX
January 80 100 90 94 0.957
February 85 75 80 94 0.851
March 80 90 85 94 0.904
April 110 90 100 94 1.064
May 115 131 123 94 1.309
June 120 110 115 94 1.223
July 100 110 105 94 1.117
August 110 90 100 94 1.064
September 85 95 90 94 0.957
October 75 85 80 94 0.851
November 85 75 80 94 0.851
December 80 80 80 94 0.851
Total average demand = 1,128
1,128 Average two-year demand
Average monthly demand = = 94 Seasonal index = Average monthly demand
12 months
Table 5.9
Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-42
 Seasonal Variations
 The calculations for the seasonal indices are

1,200 1,200
Jan.  0.957  96 July  1.117  112
12 12
1,200 1,200
Feb.  0.851  85 Aug.  1.064  106
12 12
1,200 1,200
Mar.  0.904  90 Sept.  0.957  96
12 12
1,200 1,200
Apr.  1.064  106 Oct.  0.851  85
12 12
1,200 1,200
May  1.309  131 Nov.  0.851  85
12 12
1,200 1,200
June  1.223  122 Dec.  0.851  85
12 12
Copyright ©2012 Pearson Education, Inc. publishing as Prentice Hall 5-43