Chapter 7 Introduction

Linear Programming Models: „ Many management decisions involve trying to

Graphical and Computer make the most effective use of limited resources
„ Machinery,
M hi labor,
l b money, time,
ti warehouse
h space, raw
Methods materials
„ Linear p g ((LP
programming
g LP)) is a widely
y used
mathematical modeling technique designed to
help managers in planning and decision making
relative to limited resource allocation
„ Belongs to the broader field of mathematical
programming
„ In management science, programming refers to
modeling g and solving
g a problem mathematically
y–
Quantitative Analysis for Management, Tenth Edition, it is not the same as computer programming
by Render, Stair, and Hanna © 2008 Prentice-Hall, Inc.
7–2

Examples of Successful Requirements of a Linear

LP Applications 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
„ Development of a production schedule that will quantity,
tit usually
ll profit
fit or costt (th
(the objective ti )
bj ti ffunction)
function
„ satisfy future demands for a firm’s production 2. The presence of restrictions or constraints that limit
„ while minimizingg total p
production and inventory
y the degree to which we can pursue our objective
costs
3. There must be alternative courses of action to choose
„ Determination of grades of petroleum products to
yield the maximum profit from
„ Selection of different blends of raw materials to 4. The objective and constraints in problems must be
feed mills to produce finished feed combinations expressed in terms of linear equations or inequalities
at minimum cost „ 2A + 5B = 10 (linear equation)
„ Determination of a distribution system that will „ 3A + 2B < 25 (linear inequality)
minimize total shipping cost from several „ 2A2 + 5B3 + 3AB < 10 ((non-linear inequality)
q y))
warehouses
h to
t various
i market
k t llocations
ti
7–3 7–4
 Requirements of a Linear
Programming Problem LP Properties and Assumptions

„ In a linear equation, each term is either a PROPERTIES OF LINEAR PROGRAMS

constant or the pproduct of a constant and 1. One objective function

(the first power of) a single variable. 2. One or more constraints

3. Alternative courses of action
„ The general linear equation in n variables
4. Objective function and constraints are linear
is:
ASSUMPTIONS OF LP

a1 X1 + a2 X 2 + ...... + an X n = b 1. Certainty
2. Proportionality
3. Additivity
4. Divisibility
Table 7.1 5. Nonnegative variables

7–5 7–6

Basic Assumptions of LP Formulating LP Problems

„ We assume conditions of certainty exist and „ Formulating a linear program involves developing
numbers in the objective and constraints are a mathematical model to represent the managerial
known with certainty y and do not change g during
g the problem
period being studied
„ The steps in formulating a linear program are
„ We assume proportionality exists in the objective
and constraints – if 1 unit of product uses 3 hours 1 Completely understand the managerial
1.
then 10 units of that product use 30 hours problem being faced
„ We assume additivity y in that the total of all y the objective
2. Identify j and constraints
activities equals the sum of the individual activities 3. Define the decision variables
„ We assume divisibility in that solutions need not be 4. Use the decision variables to write
whole numbers – they are divisible and may take mathematical expressions forf the objective
any fractional value
function and the constraints
„ All answers or variables are nonnegative – negative
values off physical quantities are impossible
7–7 7–8
 Formulating LP Problems Flair Furniture Company

„ One of the most common LP applications is the „ The Flair Furniture Company produces inexpensive
product mix problem tables and chairs
„ Two
T or more products
d t are produced
d d using
i „ B th products
Both d t require
i a certain
t i number
b off h
hours off
limited resources such as personnel, machines, carpentry work and certain number of labor hours in
and raw materials tthe
e pa
painting
t gaand
d varnishing
a s g depa
department
t e t
„ The profit that the firm seeks to maximize is „ Each table takes 4 hours of carpentry and 2 hours of
based on the profit contribution per unit of each painting and varnishing
product
d t „ Each chair requires 3 hours of carpentry and 1 hour
„ The company would like to determine how of painting and varnishing
many units of each product it should produce „ There are 240 hours of carpentry time and 100 hours
so as to maximize overall profit given its limited of painting and varnishing time available each week
resources „ Each table yields a profit of $70 and each chair a
profit of $50
7–9 7 – 10

Flair Furniture Company Flair Furniture Company

„ The company wants to determine the best
„ The objective is to
combination of tables and chairs to produce to
reach the maximum profit Maximize profit
„ This problem can be formulated as an LP problem „ The
Th constraints
t i t are
1. The hours of carpentry time used cannot
HOURS REQUIRED exceed 240 hours per week
TO PRODUCE 1 UNIT
2. The hours of painting and varnishing time
(T) (C) AVAILABLE HOURS
DEPARTMENT TABLES CHAIRS THIS WEEK used cannot exceed 100 hours p per week
Carpentry 4 3 240 „ The decision variables representing the actual
decisions we will make are
Painting and varnishing 2 1 100
T = number of tables to be produced per week
Profit per unit $70 $50
C = number of chairs to be produced per week

Table 7.2: Summarizing the information to better understand the problem

7 – 11 7 – 12
 Flair Furniture Company Flair Furniture Company
„ Similarly
„ We create the LP objective function in terms of T
and C Painting and varnishing time used
≤ Paintingg and varnishing g time available
Maximize profit = $70T + $50C 2 T + 1C ≤ 100 (hours of painting and varnishing time)
„ Develop mathematical relationships for the two
constraints
t i t This means that each table produced
„ For carpentry, total time used is requires two hours of painting and
varnishing time
(4 hours per table)(Number of tables produced)
+ (3 hours per chair)(Number of chairs produced)
„ Both of these constraints restrict production
p
„ We know that capacity and affect total profit
Carpentry time used ≤ Carpentry time available
4T + 3C ≤ 240 (hours of carpentry time)
7 – 13 7 – 14

Flair Furniture Company Graphical Solution to an LP Problem

„ The values for T and C must be nonnegative

„ The easiest way to solve a small LP
T ≥ 0 (number of tables produced is greater problems is with the graphical solution
than or equal to 0) approach (2D coordinate system)
C ≥ 0 (number of chairs produced is greater
than or equal to 0) „ The graphical method only works when
there are just two decision variables
„ The complete problem is stated mathematically as
„ When there are more than two variables, a
Maximize profit = $70T + $50C more complex approach is needed as it is
subject to not possible to plot the solution on a two-
4T + 3C ≤ 240 (carpentry constraint) dimensional graph
2T + 1C ≤ 100 (painting and varnishing constraint) „ The graphical method provides valuable
T C≥0
T, (nonnegati it constraint)
(nonnegativity insight into how other approaches work
7 – 15 7 – 16
 Graphical Representation of a Graphical Representation of a
Constraint Constraint
„ The first step in solving the problem is to C

identify a set or region of feasible solutions 100 –

„ T do
To d this
thi we plotl t each
h constraint
t i t equation
ti – Thi Axis
This A i Represents
R t the
th Constraint
C t i tT≥0
80 –

Chairs
on a graph (2D coordinate frame – Fig. 7.1) –
Th nonnegativity
The t i t mean that
th t we

umber of C
„ ti it constraints 60 –
are always working in the first (or northeast) –
quadrant (see Fig. 7.1) 40 – This Axis Represents the

Nu
– Constraint C ≥ 0
„ We start by graphing the equality portion of 20 –
the first ((carpentry
p y hour)) constraint –
4T + 3C = 240 |–
0
| |
20
| |
40
| |
60
| |
80
| |
100
|
T
„ It is a straight line and we need to find any Figure 7.1 Number of Tables
two points to draw the line
7 – 17 7 – 18

Graphical Representation of a Graphical Representation of a

Constraint Constraint
„ The two easiest points are the points at C
which the line intercepts the T and C axes The line represent all combinations
100 – of (T, C) that satisfy the carpentry
„ When
Wh Fl Flair
i produces
d no ttables
bl (T = 0),
0) the
th – constraint equation: 4T + 3C = 240
carpentry constraint is 80 – (T = 0, C = 80)
4(0) + 3C = 240 hairs
–
mber of Ch
60 –
3C = 240 –
C = 80
Num

40 –

„ Similarly for no chairs (C = 0) –

(T = 60, C = 0)
20 –
4T + 3(0) = 240 –
4T = 240 |–
0
| |
20
| |
40
| |
60
| |
80
| |
100
|
T
T = 60 Number of Tables
Figure 7.2
„ This line is shown on the following graph
7 – 19 7 – 20
 Graphical Representation of a Graphical Representation of a
Constraint Constraint
„ We need to identify all points (i.e. the region) that C Conclusion:
satisfy the constraint inequality: 4T + 3C ≤ 240
100 – „ Any point on or below the constraint
„ There are three possible solution points – those –
plot
l t will
ill nott violate
i l t th
the restriction
t i ti
on the line, below the line and above the line (shaded area)
80 –

hairs
„ Any point above the plot will violate
„ The point (30, 40) lies on the line and exactly –

mber of Ch
th restriction
the t i ti
satisfies the constraint 60 –
4(30) + 3(40) = 240 –
(30, 40) (70, 40)
40 –

Num
„ The point (30, 20) lies below the line and satisfies
–
the constraint
20 –
4(30) + 3(20) = 180 ≤ 240 – (30, 20)
„ The point (70, 40) lies above the line and does not |– | | | | | | | | | | |
0 20 40 60 80 100
satisfy the constraint T
Number of Tables
4(70) + 3(40) = 400 > 240 Figure 7.3

7 – 21 7 – 22

Graphical Representation of a Graphical Representation of a

Constraint Constraint

„ Next we need to do the same for the

C

second (painting and varnishing hour) 100 – (T = 0, C = 100)

–
constraint
t i t: 80 –

Chairs
Graph of painting and varnishing
2T + 1C ≤ 100 – constraint equation – the shaded

umber of C
60 – area represents all the possible
„ We start by graphing the equality portion – solution points
of the constraint: 40 –
Nu

–
(T = 50, C = 0)
2T + 1C = 100 20 –
–
„ The two points at which the line intercepts |– | | | | | | | | | | |

the T and C axes are: 0 20 40 60 80 100 T

Figure 7.4 Number of Tables
(T =0, C =100) and (T =50, C =0)
7 – 23 7 – 24
 Graphical Representation of a Graphical Representation of a
Constraint Constraint
C
„ Feasible solution region for Flair Furniture
„ To produce tables and chairs, both carpentry and
painting and varnishing departments must be used 100 –
–
„ We need to find a solution that satisfies both
80 –

Chairs
constraints simultaneously Painting/Varnishing Constraint
–
A new graph is drawn to show both constraint

umber of C
„ 60 –
plots (Fig. 7.5) –
„ The feasible region (or area of feasible solutions)
solutions is 40 –

Nu
where all constraints are satisfied – i.e. the –
Carpentry Constraint
overlapped area 20 – Feasible
g
– Region
„ A point
Any i t inside
i id this
thi region
i isi a feasible
f ibl solution
l ti |– | | | | | | | | | | |
„ Any point outside the region is an infeasible 0 20 40 60 80 100 T
solution Figure 7.5 Number of Tables

7 – 25 7 – 26

Graphical Representation of a Graphical Representation of a

Constraint Constraint
„ For the point (30,
(30 20) „ For the point (50,
(50 5)
Carpentry 4T + 3C ≤ 240 hours available Carpentry 4T + 3C ≤ 240 hours available
constraint (4)(30) + (3)(20) = 180 h
hours used
d 9 constraint (4)(50) + (3)(5) = 215 h
hours used
d 9
Painting 2T + 1C ≤ 100 hours available Painting 2T + 1C ≤ 100 hours available
constraint (2)(30) + (1)(20) = 80 hours used
9 constraint (2)(50) + (1)(5) = 105 hours used 8
„ For the p
point (70,
( 40))
Carpentry 4T + 3C ≤ 240 hours available
constraint ((4)(70)
)( ) + (3)(40)
( )( ) = 400 hours used 8
Painting 2T + 1C ≤ 100 hours available
constraint (2)(70) + (1)(40) = 180 hours used 8

7 – 27 7 – 28
 Isoprofit Line Solution Method Isoprofit Line Solution Method
„ Once the feasible region has been graphed, we „ For Flair Furniture, choose a profit of $2,100
$
need to find the optimal solution from the many „ The objective function is then
possible solutions $2,100
$2 100 = 70T + 50C
„ It is the point lying in the feasible region that produces
the highest profit
„ Solving for the axis intercepts which are (0, 42)
and (30
(30, 0)
0), we can draw the graph
„ The speediest way to do this is to use the isoprofit
line method „ The line represents all combinations of (T, C) that
yield a total profit of $2,100
„ Starting with a small but possible profit value,
value we
graph the objective function (a straight line) „ This is obviously not the best possible solution
„ We move the objective
j function line in the „ Further graphs can be created using larger profits
direction of increasing profit while maintaining the „ The further away we move from the origin, the
slope (isoprofit lines are parallel to each other) larger the profit will be
„ The
Th last
l t point
i t the
th line
li touches
t h ini the
th feasible
f ibl „ The highest profit ($4,100)
($4 100) will be generated when
region is the optimal solution the isoprofit line passes through the point (30, 40)
7 – 29 7 – 30

Isoprofit Line Solution Method Isoprofit Line Solution Method

C C
„ Isoprofit line at $2,100 „ Four isoprofit lines
100 – 100 –
– –
$3,500 = $70T + $50C
80 – 80 –
Chairs

Chairs
– – $2,800
, = $70T + $50C
umber of C

umber of C
60 – 60 –
– $2,100 = $70T + $50C – $2,100 = $70T + $50C
(0, 42)
40 – 40 –
Nu

Nu

– – $4,200 = $70T + $50C

(30, 0)
20 – 20 –
– –
|– | | | | | | | | | | | |– | | | | | | | | | | |
0 20 40 60 80 100 T 0 20 40 60 80 100 T
Figure 7.6 Number of Tables Figure 7.7 Number of Tables

7 – 31 7 – 32
Isoprofit Line Solution Method Corner Point Solution Method
C
„ Optimal solution to the „ A second
d approach
h tto solving
l i LP problems
bl
100 – Flair Furniture problem employs the corner point method
– „ It is a simpler technique but involves
80 – looking at the profit at every corner point
Chairs

Maximum Profit Line

– of the feasible regiong
umber of C

60 – Optimal Solution Point

– (T = 30, C = 40) „ The mathematical theory behind LP is that
40 – the optimal solution must lie at one of the
i t or extreme
corner points
points, t i t in
point
point, i the
th
Nu

– $4,100 = $70T + $50C

20 – feasible region
– „ For Flair Furniture,
Furniture the feasible region is a
|– | | | | | | | | | | |
0 20 40 60 80 100 T
four-sided polygon with four corner points
Number of Tables
labeled 1,, 2,, 3,, and 4 on the graph
g p
Figure 7.8

7 – 33 7 – 34

Corner Point Solution Method Corner Point Solution Method

C
„ Four corner points of Point 1 : (T
( = 0, C = 0)) Profit
f = $70(0)
$ ( ) + $50(0)
$ ( ) = $0
$
100 – the feasible region Point 2 : (T = 0, C = 80) Profit = $70(0) + $50(80) = $4,000
2 – P i
Point 4 : (T
( = 50,
0 C = 0) P fi = $70(50)
Profit $ 0( 0) + $50(0)
$ 0(0) = $3
$3,500
00
80 –
Chairs

–
Point 3 : (T = 30, C = 40) Profit = $70(30) + $50(40) = $4,100
umber of C

60 –
– „ Because Point 3 returns the highest profit, this
3 is the optimal solution
40 –
Nu

– „ To find the coordinates for Point 3 accurately we

20 – have to solve for the intersection of the two
– constraint lines
1 |– | | | | | | | | | | |
0 20 40 60 80 100 T
4T + 3C = 240 (carpentry line)
4
Figure 7.9 Number of Tables 2T + 1C = 100 (painting line)
„ The details of this are on the following slide
7 – 35 7 – 36
 Summary of Graphical Solution
Corner Point Solution Method Methods
ISOPROFIT METHOD
„ Using the simultaneous equations method,
method we
1. Graph all constraints and find the feasible region.
multiply the painting equation by –2 and add it to
th carpentry
the t equation
ti 2 Select a specific profit (or cost) line and graph it to find the slope
2. slope.
3. Move the objective function line in the direction of increasing profit
4T + 3C = 240 (carpentry line) (or decreasing cost) while maintaining the slope. The last point it
touches in the feasible region is the optimal solution.
solution
– 4T – 2C = –200 (painting line)
4. Find the values of the decision variables at this last point and
C = 40 compute the profit (or cost).
„ Substituting 40 for C in either of the original CORNER POINT METHOD
equations allows us to determine the value of T 1. Graph all constraints and find the feasible region.
2 Find the corner points of the feasible reason
2. reason.
4T + (3)(40) = 240 (carpentry line) 3. Compute the profit (or cost) at each of the feasible corner points.
4T + 120 = 240 4. Select the corner p
point with the best value of the objective
j function
T = 30 found in step 3. This is the optimal solution.

7 – 37 Table 7.3 7 – 38

Solving Flair Furniture’s LP Problem

Using QM for Windows
Using QM for Windows and Excel

„ Most organizations have access to „ First select the Linear Programming module
software to solve big LP problems „ Specify the number of constraints (non-negativity
is assumed)
ass med)
„ While there are differences between
„ Specify the number of decision variables
software implementations, the approach
eachh takes
t k ttowardsd hhandling
dli LP is
i „ Specify whether the objective is to be maximized
or minimized
basically the same
„ For the Flair Furniture p
problem there are two
„ Once
O you are experienced
i d in
i dealing
d li with
ith constraints, two decision variables, and the
computerized LP algorithms, you can objective is to maximize profit
easily adjust to minor changes

7 – 39 7 – 40
 Using QM for Windows Using QM for Windows

„ Computer screen for input of data „ Computer screen for input of data

Program 7.1A Program 7.1B

7 – 41 7 – 42

Using QM for Windows Using QM for Windows

„ Graphical output of solution
„ Computer screen for output of solution

Program 7.1C

Program 7.1D

7 – 43 7 – 44
 Using Excel’s Solver Command to Using Solver to Solve the Flair
Solve LP Problems Furniture Problem

„ The Solver tool in Excel can be used to find „ Recall the model for Flair Furniture is
solutions to
Maximize profit = $70T + $50C
„ LP problems
bl
Subject to 4T + 3C ≤ 240
„ Integer programming problems
2T + 1C ≤ 100
„ Noninteger programming problems
„ Solver may be sensitive to the initial values it uses „ To use Solver, it is necessary to enter formulas
„ Solver is limited to 200 variables and 100 based on the initial model
constraints „ Program 7.2A shows how the data and formulas
„ It can be used for small real world problems
p are entered into Solver to solve this problem
p
„ Add-ins like What’sBest! Can be used to expand „ The following slide details the steps in creating
Solver’s capabilities the Solver model

7 – 45 7 – 46

Using Solver to Solve the Flair Using Solver to Solve the Flair
Furniture Problem Furniture Problem
Program 7.2A
7 2A
1. Modify the variable names and the
constraint names if needed
2. Enter the coefficients for the objective
function and constraints
3. Indicate constraint signs (≤, =, and ≥) for
display purposes only
4. Input the right-hand side values for each
constraint
5. Initialize the values of the variables to 1s to
make it easier to check the formula

7 – 47 7 – 48
 Using Solver to Solve the Flair Using Solver to Solve the Flair
Furniture Problem Furniture Problem
„ Once the model has been entered
entered, the following
steps can be used to solve the problem 3. The Set Target Cell contains the cell that is used
1A. In Excel 2003,
1A 2003 select Tools—
Tools—Solver to calculate the value of the objective
j function.
1B. In Excel 2007, select the Data tab and then select 4. The By Changing Cells box contains the cells that
Solver in the Analysis
y group
g p will hold the values for the variables
5. The Subject to the Constraints box contains the
If Solver does not appear in the indicated place, constraints for the model
follow the installation instructions in the text 6 In the Solver Parameters window,
6. window click Options
and check Assume Linear Model and check
2. Once Solver has been selected, a window will Assume Non-
Non-negative
negative, as illustrated in Program
open for
f th the iinputt off th
the S
Solver
l P
Parameters.
t Make
M k 7.2C, then click OK
sure all the parameters set by Solver are correct

7 – 49 7 – 50

Using Solver to Solve the Flair Using Solver to Solve the Flair
Furniture Problem Furniture Problem

7. Review the information in the Solver window to

make sure it is correct, and click Solve
8. The Solver Solutions window in Program 7.2D is
displayed and indicates that a solution was
found Select Keep Solver Solution
found. Solution, and the
values in the spreadsheet will be kept at the
optimal solution. You may select what sort of
additional
ddi i l information
i f i (e.g.,
( A
Answer, S
Sensitivity,
ii i
etc.
etc.) is to be presented from the reports Window.

Program 7.2C

7 – 51 7 – 52
 Using Solver to Solve the Flair Using Solver to Solve the Flair
Furniture Problem Furniture Problem
„ Excel’s
E l’ answer reportt for
f the
th Flair
Fl i Furniture
F it problem
bl

Program 7.2D Program 7.2E

7 – 53 7 – 54

Solving Minimization Problems Holiday Meal Turkey Ranch

„ The Holiday Meal Turkey Ranch is considering
„ Many LP problems involve minimizing an objective
buying two different brands of turkey feed and
such as cost instead of maximizing a profit blending them to provide a good, low-cost diet for
function i turkeys
its k
„ Minimization problems can be solved graphically
„ 1 lb. of brand 1 contains 5 oz. of ingredient A, 4 oz.
byy first setting
g up the feasible solution region
g and of ingredient B,
B and 0.50 5 oz.
oz of ingredient C
then using either the corner point method or an
isocost line approach (which is analogous to the „ 1 lb. of brand 2 contains 10 oz. of ingredient A, 3
isoprofit approach in maximization problems) to oz. of ingredient
g B,, but no ingredient
g C
find the values of the decision variables (e.g., X1 „ The cost for brand 1 feed is 2 cents/lb.
and X2) that yield the minimum cost „ The cost for brand 2 feed is 3 cents/lb.
„ To meet the minimum nutritional requirement, for
each turkey and each month, the diet must contain
at least 90 oz
oz. of ingredient A,A 48 oz.
oz of ingredient
B, and 1.5 oz. of ingredient C.
7 – 55 7 – 56
 Holiday Meal Turkey Ranch Holiday Meal Turkey Ranch
„ Use LP to determine the lowest-cost diet that
meets the minimum monthly intake requirement Let
for each nutritional ingredient
ingredient. X1 = number of p
pounds of brand 1 feed purchased
p
X2 = number of pounds of brand 2 feed purchased
„ Holiday Meal Turkey Ranch data

COMPOSITION OF EACH POUND

MINIMUM MONTHLY
Minimize cost (in cents) = 2X1 + 3X2
OF FEED (OZ.)
REQUIREMENT PER
INGREDIENT BRAND 1 FEED BRAND 2 FEED TURKEY (OZ.)
(OZ ) subject to:
A 5 10 90 5X1+ 10X2 ≥ 90 ounces (ingredient A constraint)
B 4 3 48 4X1 + 3X2 ≥ 48 ounces (ingredient B constraint)
0.5X1 ≥ 1.5 ounces (ingredient C constraint)
C 0.5 0 1.5
X1 ≥ 0 (nonnegativity constraint)
Cost per pound 2 cents 3 cents X2 ≥ 0 (nonnegativity constraint)
Table 7.4
7 – 57 7 – 58

Holiday Meal Turkey Ranch Holiday Meal Turkey Ranch

„ Using the corner X2 „ We solve for the values of the three corner points
–
point method „ Point a is the intersection of ingredient constraints C
„ First
Fi t we construct
t t and B
20 –
the feasible Ingredient C Constraint 4X1 + 3X2 = 48
nd 2

solution region
g X1 = 3
ds of Bran

15 –
„ The optimal Feasible Region „ Substituting 3 in the first equation, we find X2 = 12
solution will lie at a „ Point b is the intersection of ingredient constraints A
10 – and
dB
on off th
the corners
Pound

as it would in a Ingredient B Constraint 5X1 + 10X2 = 90

maximization 5–
I
Ingredient
di t A Constraint
C t i t 4X1 + 3X2 = 48
b
problem „ Solving for point b with basic algebra we find X1 = 8.4
0 |– | | | c | | and X2 = 4.8
5 10 15 20 25 X1
Figure 7.10 Pounds of Brand 1
„ Solving for point c we find X1 = 18 and X2 = 0

7 – 59 7 – 60
 Holiday Meal Turkey Ranch Holiday Meal Turkey Ranch
„ Substituting
S these value back into the objective „ Using the isocost X2
–
function we find approach Feasible Region
„ Choosing
Ch i an
Cost = 2X1 + 3X2 20 –
initial cost of 54
Cost at point a = 2(3) + 3(12) = 42

nd 2
cents

ds of Bran
Cost at point b = 2(8.4) + 3(4.8) = 31.2 2X1 + 3X2 = 54
15 –

Cost at point c = 2(18) + 3(0) = 36 X1 = 0; X2 = 18 10 –

Pound
X1 = 27; X2 = 0
„ The lowest cost solution is to purchase 8.4
„ It is clear
pounds of brand 1 feed and 4.8 pounds of brand 2 5–
feed for a total cost of 31.2 cents per turkey per i
improvement t is
i
month possible (X1 = 8.4, X2 = 4.8)
0 |– | | | | |
5 10 15 20 25 X1
Figure 7.11 Pounds of Brand 1

7 – 61 7 – 62

Holiday Meal Turkey Ranch Holiday Meal Turkey Ranch

„ Setting up Solver to solve the Holiday Meal Turkey
„ QM for Windows can also be used to solve the Ranch problem
Holiday Meal Turkey Ranch problem

Program 7.3

Program 7.4A
7 – 63 7 – 64
 Holiday Meal Turkey Ranch Four Special Cases in LP
„ Solution to the Holiday Meal Turkey Ranch
problem using Solver „ Four special cases and difficulties arise at
times when using the graphical approach
to solving LP problems
„ Infeasibility
y
„ Unboundedness
„ Redundancy
y
„ Alternate Optimal Solutions

Program 7.4B
7 – 65 7 – 66

Four Special Cases in LP Four Special Cases in LP

„ No feasible solution „ A problem
bl with
ith no ffeasible
ibl solution
l ti
„ Exists when there is no solution to the
X2 X1 >=7
problem that satisfies all the constraint
equations
„ No feasible solution region exists 8–
2X1+X2 ≤ 8
–
„ This is a common occurrence in the real world
6–
„ Generallyy one or more constraints are relaxed –
Region Satisfying
until a solution is found 4– X1+2X2 ≤ 6 Third Constraint
–
2–
–
0– | | | | | | | | | |
2 4 6 8 X1
Fig re 7.12
Figure 7 12
Region Satisfying First Two Constraints
7 – 67 7 – 68
 Four Special Cases in LP Four Special Cases in LP
„ Unboundedness „ A solution
l i region
i unbounded
b d d to the
h right
i h
„ Sometimes a linear program will not have a X2
fi it solution
finite l ti
„ In a maximization problem, one or more
X1 ≥ 5
solution variables,
variables and the profit,
profit can be made 15 –
infinitely large without violating any
constraints X2 ≤ 10
10 –
„ In a graphical solution, the feasible region will
be open ended 5–
Feasible Region

„ This usually means the problem has been X1 + 2X2 ≥ 15

formulated improperly
0 |– | | | |
5 10 15 X1
Figure 7.13

7 – 69 7 – 70

Four Special Cases in LP Four Special Cases in LP

„ A problem
bl with
ith X2
„ Redundancy
a redundant 30 –
„ A redundant constraint is one that does not constraint
affect
ff t th
the ffeasible
ibl solution
l ti region
i 25 –
„ One or more constraints may be more binding 2X1 + X2 ≤ 30

„ This is a very common occurrence in the real 20 –

Redundant
world Constraint
15 –
„ It causes no particular problems, but X1 ≤ 25
eliminating redundant constraints simplifies 10 –
the model X1 + X2 ≤ 20
Feasible
5–
Region

0– | | | | | |
Figure 7.14 5 10 15 20 25 30 X1

7 – 71 7 – 72
 Four Special Cases in LP Four Special Cases in LP
„ Example
E l off
„ Alternate Optimal Solutions X2
alternate 8–
„ Occasionally two or more optimal solutions optimal
p
may exist solutions 7–
„ Graphically this occurs when the objective 6 –A
function’s
function s isoprofit or isocost line runs Opt a So
Optimal Solution
ut o Consists
Co s sts o
of All
5– Combinations of X1 and X2 Along
perfectly parallel to one of the constraints Maximize: 3X1 + 2X2 the AB Segment
„ This actually y allows management
g great
g Subj.
j to: 6X1 + 4X2 < 24 4–
flexibility in deciding which combination to X1 < 3 3– Isoprofit Line for $8
select as the profit is the same at each X 1 , X2 > 0
2–
alternate solution 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

7 – 73 7 – 74

Sensitivity Analysis Sensitivity Analysis

„ Optimal solutions to LP problems thus far have „ Sensitivity
S iti it analysis
l i often
ft involves
i l a series
i off
been found under what are called deterministic what-if? questions concerning constraints,
assumptions variable coefficients,, and the objective
j function
„ This means that we assume complete certainty in „ What if the profit for product 1 increases by 10%?
„ What if less advertising money is available?
the data and relationships of a problem
„ One way to do this is the trial-and-error
trial and error method
„ But in the real world, conditions are dynamic and
where values are changed and the entire model is
changing
resolved
„ W can analyze
We l how
h iti a deterministic
sensitive d t i i ti
„ The preferred way is to use an analytic
solution is to changes in the assumptions of the
postoptimality analysis
model
„ After
f a problem has been solved, we determine a
„ This is called sensitivity analysis,
analysis postoptimality
range of changes in problem parameters that will
analysis programming or optimality
analysis, parametric programming,
not affect the optimal solution or change the
analysis
l i
variables in the solution
7 – 75 7 – 76
 High Note Sound Company High Note Sound Company
„ The High Note Sound Company manufactures „ The High Note Sound Company graphical solution
quality CD players and stereo receivers X2
„ Products require a certain amount of skilled (receivers)

artisanship which is in limited supply 60 – Optimal Solution at Point a

„ The firm has formulated the following product mix – 3X1 + 1X2 ≤ 60
X1 = 0 CD Players
X2 = 20 Receivers
LP model
d l to
t determine
d t i the
th best
b t production
d ti mix i off Profits = $2,400
40 –
CD players (X1) and stereo receivers (X2).
Maximize profit = $50X
$ (0, 20) –
a = (0
1 + $120X
$ 2
b = (16, 12)
Subject to 2X1 + 4X2 ≤ 80 (weekly hours of 20 –
electrician’s time 2X1+ 4X2 ≤ 80
available)) Isoprofit Line: $2,400
$2 400 = 50X1 + 120X2
10 –
3X1 + 1X2 ≤ 60 (weekly hours of
audio technician’s 0– | | | | | |
ti
time available)
il bl ) 10 20 30 40 50 60 X1
Figure 7.16 c = (20, 0) (CD players)
X 1 , X2 ≥ 0
7 – 77 7 – 78

Changes in the Changes in the

Objective Function Coefficient Objective Function Coefficient
„ In
I real-life
l lif problems,
bl contribution
t ib ti rates
t ((usually
ll „ Changes in the receiver contribution coefficients
profit or cost) in the objective functions fluctuate X2
p
periodically y 40 –
Profit Line for 50X1 + 80X2
„ Graphically, this means that although the feasible (Passes through Point b)
solution region remains exactly the same, the 30 –
slope
l off the
th iisoprofit
fit or iisocostt li
line will
ill change
h
Profit Line for 50X1 + 120X2
„ We can often make modest increases or (Passes through Point a)
20 –
decreases in the objective function coefficient of b
any variable without changing the current optimal a Profit Line for 50X1 + 150X2
corner point 10 – (Passes through Point a)

„ We need to know how much an objective function

coefficient can change before the optimal solution 0– | | c | | | |
would be at a different corner point 10 20 30 40 50 60 X1
Figure 7.17
„ Both QM programs provide the answer
7 – 79 7 – 80
 QM for Windows and Changes in Excel Solver and Changes in
Objective Function Coefficients Objective Function Coefficients
„ Input and sensitivity analysis for High Note Sound „ Excel spreadsheet analysis of High Note Sound
data

Program 7.5A
7 5A

Program 7.5B Program 7.6A

7 – 81 7 – 82

Excel Solver and Changes in Changes in the

Objective Function Coefficients Technological Coefficients
„ Excel sensitivity analysis output
„ Changes in the technological coefficients often
reflect changes in the state of technology
„ If the
th amountt off resources needed
d d to
t produce
d 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
off the
h feasible
f ibl region
i
„ This may cause a change in the optimal solution

Program 7.6B
7 – 83 7 – 84
 Changes in the Changes
g in Resources or
Technological Coefficients Right-Hand-Side Values

„ Change in the technological coefficients for the „ The right-hand-side values of the constraints
High Note Sound Company often represent resources available to the firm
(a) Original Problem (b) Change in Circled (c) Change in Circled
„ Labor
L b hours,
h machine
hi time,
ti money available
il bl …
Coefficient Coefficient
X2 X2 X2 „ If additional resources were available, a
60 – 60 – 60 – higher total profit could be realized
Receivers

3X1 + 1X2 ≤ 60 2 X1 + 1X2 ≤ 60 3X1 + 1X2 ≤ 60 „ Sensitivity analysis about resources will help
40 – 40 – 40 –
answer questions such as:
Stereo R

Optimal Still Optimal

20 –a
Solution
20 –a
Optimal
20 –
Solution „ How much should the company be willing to
d
b 2X1 + 4X2 ≤ 80 2X1 + 4X2 ≤ 80 16 f g 2X1 + 5 X2 ≤ 80 pay for additional hours?
– |c | | – | e | | | – |c | |
„ Is it profitable to have some electricians work
0 20 40 0 20 30 40 0 20 40
CD Players
X1 X1 X1
overtime?
Figure 7.18 „ Should
Sh ld we be b willing
illi to
t pay for
f more audiodi
technician time?
7 – 85 7 – 86

Changes
g in Resources or Changes
g in Resources or
Right-Hand-Side Values Right-Hand-Side Values
„ If the right-hand side of a constraint (e.g. 80 hrs) „ However, the amount of possible increase in the
is changed, the feasible region will change right-hand side of a resource is limited
(unless the constraint is redundant) (Fig
(Fig. 7-19) „ If the number of hours increased beyond the
„ Often the optimal solution will change (Fig. 7-19) upper bound, then the objective function would no
„ The amount of change (increase or decrease) in longer
g increase by y the dual p
price (Fig.
( g 7-19c))
the objective function value that results from a „ There would simply be excess (slack
slack) hours of a
unit change in one of the resources available is resource or the objective function may change by
called the dual price or dual value an amount different from the dual price
„ The dual price for a constraint is the improvement „ The dual price is relevant only within limits
(or deterioration) in the objective function value „ If the dual value of a constraint is zero
that results from a one-unit increase (or decrease) „ The slack is positive, indicating unused resource
in the right-hand side of the constraint
„ Additional amount of resource will simply
p y increase
the amount of slack
7 – 87 7 – 88
 Changes in the Electrician's Time Changes in the Electrician's Time
for High Note Sound for High Note Sound
If available electrician time is increased by 20 hrs If available electrician time is decreased by 20 hrs
X2 X2
(from 80 to 100 hrs), the optimum solution (from 80 to 60 hrs), the optimum solution
60 – will be changed from (0, 20) to (0, 25), and the 60 – will be changed from (0, 20) to (0, 15), and the
maximum profit will be changed from $2400 maximum profit will be changed from $2400
to $3000 – an increase of $600 (= 20×30) to $1800 – an decrease of $600 (= 20×30)

40 – 40 –
C
Constraint
t i t Representing
R ti 60 Hours
H off C
Constraint
t i t Representing
R ti 60 Hours
H off
Audio Technician’s Time Resource Audio Technician’s Time Resource
a
25 –
20 – b Changed Constraint Representing 100 Hours 20 – Changed Constraint Representing 60 Hours
of Electrician’s Time Resource a of Electrician’s Time Resource
15 –
b

– | c | | | – c | | | |
0 20 40 50 60 X1 0 20 30 40 60 X1
Figure 7.19a Figure 7.19b

7 – 89 7 – 90

Changes in the Electrician's Time QM for Windows and Changes in

for High Note Sound Right-Hand-Side Values
Optimum Solution – (0, 60)
„ Input and sensitivity analysis for High Note Sound
X2
Maximum Profit – $7200 data
60 – Originally – (0, 20) and $2400

Changed Constraint Representing 240 Hours

40 – of Electrician’s Time Resource – Originally
80 Hours

Constraint
Representing
p g Program 7.5A
7 5A
20 – 60 Hours of Audio
Technician’s
Time Resource

– | | | | | |
0 20 40 60 80 100 120
X1
Figure 7.19c If the number of hours increased beyond 240, the profit would no Program 7.5B
longer increase and the optimum solution would still be (0, 60)
7 – 91 7 – 92
 Excel Solver and Changes in
Right-Hand-Side Values
„ Excel sensitivity analysis output

Shadow price is equ

uivalent to dual price
Program 7.6B
7 – 93