CHAPTER 2

Linear Programming
Models: Graphical and
Computer Methods
PowerPoint presentation to accompany
Balakrishnan/Render/Stair
Managerial Decision Modeling with Spreadsheets, 3/e
© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-1
 LEARNING OBJECTIVES
1. Understand the basic assumptions and properties
of linear programming (LP).
2. Use graphical procedures to solve LP problems
with only two variables to understand how LP
problems are solved.
3. Understand special situations such as
redundancy, infeasibility, unboundedness, and
alternate optimal solutions in LP problems.
4. Understand how to set up LP problems on a
spreadsheet and solve them using Excel’s Solver.

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-2

 Introduction

• Management decisions involve the

most effective use of resources
• Most widely used modeling technique
is linear programming (LP)
• Deterministic models

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-3

 Developing a LP Model
• All LP models can be viewed in terms
of the three distinct steps

1. Formulation of simple mathematical

expressions
2. Solution to identify an optimal (or best)
solution to the model
3. Interpretation of the results and answer
“what if?” questions

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-4

 Properties of a LP Model
1. Seek to maximize of minimize a some
quantity
2. Restrictions or constraints
3. Alternative courses of action
4. Linear equations or inequalities
(=, ≤, ≥)

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

 LP Characteristics

• Feasible Region – The set of points

that satisfies all constraints
• Corner Point Property – An optimal
solution must lie at one or more corner
points
• Optimal Solution – The corner point
with the best objective function value
is optimal

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-6

 Formulating a LP Model

• A product mix problem

• Decide how much to make of two or more
products
• Objective is to maximize profit
• Limited resources
• Flair Furniture
• Best combination of tables and chairs

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-7

 Decision Variables

• What we are solving for

• Two variables in the Flair problem
• Number of tables (T, Tables or X ) 1

• Number of chairs (C, Chairs or X ) 2

• Decision variables can be in different

units of measurement

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

 The Objective Function

• States the goal of a problem

• A single objective function
• Objective is often to maximize profit or
minimize cost

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-9

 The Objective Function

• For Flair Furniture

Profit = ($7 profit per table)
x (number of tables produced)
+ ($5 profit per chairs)
x (numbers of chairs produced)

• Using decision variables T and C

Maximize $7T + $5C

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-10

 Constraints

• Restrictions or limits on our decisions

• As many as necessary
• Can be independent
• Flair has four constraints
• Carpentry time
• Painting time
• Number of chairs to make
• Number of tables to make
© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-11
 Constraints
• For carpentry time
(3 hours per table)
x (number of tables produced) +
(3 hours per chair)
x (number of chairs produced)

• There are 2,400 hours of time available

3T + 4C ≤ 2,400

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-12

 Constraints
• All four constraints
Carpentry time – 3T + 4C ≤ 2,400
Painting time – 2T + 1C ≤ 1,000
Chairs sold – C ≤ 450
Tables sold – T ≥ 100

• Interactions exist between variables

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-13

 Nonnegativity and Integers
• Decision variables must be ≥ 0, so
T ≥ 0, and
C≥0

• Decision variables may have to be

integers

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-14

 Flair Model Matrix

TABLES (T) CHAIRS (C) LIMIT

Profit Contribution $7 $5
Carpentry 3 hrs 4 hrs 2,400
Painting 2 hrs 1 hr 1,000
Chairs 0 unit 1 unit 450
Tables 1 unit 0 unit 100

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-15

 Guidelines

• Recognizing and defining decision

variables
• Different variables, different units
• Use only the decision variables in the
model
• Difficulties may point to a need for
more variables or better definitions

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-16

 Guidelines

• One expression, one entity

• One unit of measurement per
expression
• Constraints are separate
• Translate expressions into words

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-17

 Graphical Solution

• Complete model
Maximize profit = $7T + $5C
Subject to
3T + 4C ≤ 2,400(carpentry time)
2T + 1C ≤ 1,000(painting time)
C ≤ 450 (maximum chairs allowed)
T ≥ 100 (maximum tables allowed)
T, C ≥ 0 (nonnegativity)

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-18

 Graphical Representation

1,000 –
–
Number of Chairs (C)

800 – (T = 0, C = 600)
–
600 – Carpentry Constraint Line
–
400 – (T = 400, C = 300)
–
200 – (T = 800, C = 0)
–
0 –| | | | | | | | | | | |
0 200 400 600 800 1,000

Number of Tables(T)
Figure 2.1

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-19

 Graphical Representation

1,000 –
– Region Satisfying
Number of Chairs (C)

800 – 3T + 4C ≤ 2,400
–
600 – (T = 300, C = 200)
–
400 – (T = 600, C = 400)
–
200 –
–
0 –| | | | | | | | | | | |
0 200 400 600 800 1,000

Number of Tables(T)
Figure 2.2

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-20

 Graphical Representation
(T = 0, C = 1,000)
1,000 – (T = 100, C = 700)
–
Number of Chairs (C)

(T = 0, C = 600)
800 –
– Painting Constraint
600 –
(T = 300, C = 200)
–
Carpentry Constraint
400 –
– (T = 500, C = 200)
200 – (T = 500, C = 0)
– (T = 800, C = 0)
0 –| | | | | | | | | | | |
0 200 400 600 800 1,000

Number of Tables(T)
Figure 2.3

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-21

 Graphical Representation
Painting Constraint

1,000 –
Infeasible Solution (T = 50, C = 500)
–
Number of Chairs (C)

800 –
Maximum Tables Required Constraint
–
600 – Maximum Chairs Allowed Constraint
–
400 – (T = 300, C = 200)
– Carpentry Constraint
200 – Infeasible Solution
Feasible (T = 500, C = 200)
–
Region
0 –| | | | | | | | | | | |
0 200 400 600 800 1,000

Number of Tables(T)
Figure 2.4

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-22

 Using Level Lines
800 –
(T = 0, C = 560)
–
(T = 0, C = 420)
Number of Chairs (C)

600 –

– Feasible Region
$7

400 –
T
$7

+$
T

–
+$

5C

(T = 300, C = 0)
5C

=$

200 –
=$

2,8
2,1

00

– (T = 400, C = 0)
00

| | | | | | | | | |
0–
0 200 400 600 800 1,000
Number of Tables(T) Figure 2.5

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-23

 Using Level Lines
800 –
Optimal Level Profit Line
–
Number of Chairs (C)

600 – Carpentry Constraint

– 2 3
Optimal Corner Point Solution
$7

400 –
T
$7

+$

4
T

Level Profit Line with No Feasible

–
+$

5C

Points ($7T + $5C = $4,200)

5C

=$

200 –
=$

2,8
00
2,1

Painting Constraint
–
00

| | | | | | | | | |
0–
0 1 200 400 5 600 800 1,000
Number of Tables(T) Figure 2.6

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-24

 Calculating a Solution

• Optimal point 4 is the intersection of

two constraints, carpentry and painting
• Solving simultaneously
6T + 8C = 4,800
– (6T + 3C = 3,000)
5C = 1,800
implies C = 360
and T = 320

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-25

 Using All Corner Points
Point 1 (T = 100, C = 0)
Profit = $7 x 100 + $5 x 0 = $700
Point 2 (T = 100, C = 450)
Profit = $7 x 100 + $5 x 450 = $2,950
Point 3 (T = 200, C = 450)
Profit = $7 x 200 + $5 x 450 = $3,650
Point 4 (T = 320, C = 360)
Profit = $7 x 320 + $5 x 360 = $4,040
Point 5 (T = 500, C = 0)
Profit = $7 x 500 + $5 x 0 = $3,500

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-26

 Extension to the Model
800 –
Optimal Level Profit Line for Revised Problem
– (T = 300, C = 375) is the New
Optimal Corner Point Solution
Number of Chairs (C)

600 –
(T = 320, C = 360) is No
– 2 3 Longer Feasible

7 Additional Constraint C – T ≥ 75
400 –
4 Has a Positive Slope
– ($7T + $5C = $2,800)
200 –
6
This Portion of the Original Feasible
– Region Is No Longer Feasible
| | | | | | | | | |
0–
0 1 200 4005 600 800 1,000
Number of Tables(T) Figure 2.7

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-27

 Minimization Problem

• Minimize cost
• Holiday Meal Turkey Ranch
• Two types of feed
Minimize cost = $0.10A + $0.15B
subject to
5A + 10B ≥ 45 (protein required)
4A + 3B ≥ 24 (vitamin required)
0.5A ≥ 1.5 (iron required)
A,B ≥ 0 (nonnegativity)

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-28

 Minimization Problem

• Data for Holiday Meal Turkey Ranch

NUTRIENTS PER POUND OF FEED MINIMUM REQUIRED
PER TURKEY PER
NUTRIENT BRAND A FEED BRAND B FEED MONTH
Protein (units) 5 10 45
Vitamin (units) 4 3 24
Iron (units) 0.5 0 1.5
Cost Per Pound $0.10 $0.15

Table 2.1

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-29

 Minimization Problem
10 –
Iron Constraint
9–
8–
Pounds of Brand B (B)

7– Feasible Region is Unbounded

6–
Vitamin Constraint
5–
4– 1
3– 2
2– Protein Constraint

1–
3
0–
| | | | | | | | | | |
0 1 2 3 4 5 6 7 8 9 10
Pounds of Brand A (A) Figure 2.8

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-30

 Graphical Solution
10 –
Level Cost
9 – Line for
8 – Minimum
Pounds of Brand B (B)

Cost Unbounded Feasible Region

7–
6–
5–
$0
4– 1 .10
Dir A+
ec $ Level Cost Line
tio
3– n o 0.15
2 fD B=
ec
2– Optimal Corner rea $1
sin
gC
Point Solution o st
1–
(A = 4.2, B = 2.4) 3
0–
| | | | | | | | | | |
0 1 2 3 4 5 6 7 8 9 10
Pounds of Brand A (A) Figure 2.9

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-31

 Calculating a Solution
• Optimal point 2 is the intersection of
two constraints, vitamin and protein
• Solving simultaneously

4(5A + 10B = 45) implies 20A + 40B = 180

– 5(4A + 3B = 24) implies – (20A + 15B = 120)
25B = 60
implies B = 2.4
and A = 4.2

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-32

 Special Situations

• Redundant Constraints
• Do not affect the feasible region
• Changed constraint in Flair Furniture
problem

T ≥ 100 becomes T ≤ 100

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-33

 Special Situations

1,000 –
– C ≤ 450
Number of Chairs (C)

800 –
–
Carpentry Constraint Is Redundant
600 –
–
400 –
Feasible Region

Constraint Changed to T ≤ 100

–
200 – Painting Constraint
– Is Redundant
0 –| | | | | | | | | | | |
0 200 400 600 800 1,000

Number of Tables(T)
Figure 2.10

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-34

 Special Situations

• Infeasibility
• No one solution satisfies all the
constraints
• Changed constraint in Flair Furniture
problem

T ≥ 100 becomes T ≤ 600

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-35

 Special Situations
Constraint Changed
to T ≥ 600
1,000 –
C ≤ 450
–
Number of Chairs (C)

800 –
Two Regions
– Do Not Overlap Region
Satisfying
600 – 3T + 4C ≤ 2,400 Fourth
– Constraint
400 –
– Region 2T + C ≤ 1,000
Satisfying
200 –
Three
– Constraints
0 –| | | | | | | | | | | |
0 200 400 600 800 1,000

Number of Tables(T)
Figure 2.11

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-36

 Special Situations
• Alternate Optimal Solutions
• More than one solution satisfies all the
constraints
• Changed objective in Flair Furniture problem

$7T + $5C becomes $6T + $3C

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-37

 Special Situations
800 – Level Profit Line for Maximum Profit
Overlaps Painting Constraint
–
Number of Chairs (C)

600 – Level Profit Line Is Parallel to Painting Constraint

– 2 3 $6T + $5C = $2,100

400 –
4
Optimal Solution Consists of All
–
Points Between Corner
Points 4 and 5
200 –
Feasible
– Region

| | | | | | | | | |
0–
0 1 200 400 5 600 800 1,000
Number of Tables(T) Figure 2.12

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-38

 Special Situations

• Unbounded Solution
• May or may not have a finite solution
• Usually improper formulation
• Changed objective in Holiday Meal
problem

Minimize = $0.10A + $0.15B

becomes
Maximize = 8A + 12B

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-39

 Special Situations
10 –
Iron Constraint
9–
8– Unbounded
Pounds of Brand B (B)

7– Va Direc Feasible Region

lue tio
Ca n o
6– n B f In
8A e I cre
5– +1 nc as
2B reas ing V
4– 8A = 1 ed to alue
+1 00 Inf
2B init
3– =8 y
Vitamin 0
2 – Constraint
1– Protein Constraint
0–
| | | | | | | | | | |
0 1 2 3 4 5 6 7 8 9 10
Pounds of Brand A (A) Figure 2.13

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-40

 Using Excel’s Solver

• Excel’s built-in LP solution tool for LP

• Commonly available and easy access
• Familiar software

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-41

 Using Solver

Screenshot 2-1A

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-42

 Using Solver

Screenshot 2-1B

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-43

 Using Solver

Screenshot 2-1B

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-44

 Using Solver

Screenshot 2-1C

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-45

 Using Solver

Screenshot 2-1D

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-46

 Using Solver

Screenshot 2-1E

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-47

 Using Solver

Screenshot 2-1F
© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-48
 Using Solver

Screenshot 2-2

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-49

 Using Solver

Screenshot 2-3A

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-50

 Using Solver

Screenshot 2-3B

© 2013 Pearson Education, Inc. publishing as Prentice Hall 2-51