Linear Programming Models: Graphical and Computer Methods
7
To accompany Quantitative Analysis for Management, Twelfth Edition,
by Render, Stair, Hanna and Hale
Power Point slides created by Jeff Heyl
Copyright ©2015 Pearson Education, Inc.
After completing this chapter, students will be able to:
LEARNING OBJECTIVES
Copyright ©2015 Pearson Education, Inc.
7 – 2
Understand the basic assumptions and properties of linear programming (LP).
Graphically solve any LP problem that has only two variables by both the corner point and isoprofit line methods.
Understand special issues in LP such as infeasibility, unboundedness, redundancy, and alternative optimal solutions.
Understand the role of sensitivity analysis.
Use Excel spreadsheets to solve LP problems.
Copyright ©2015 Pearson Education, Inc.
7 – 3
7.1 Introduction
7.2 Requirements of a Linear Programming Problem
7.3 Formulating LP Problems
7.4 Graphical Solution to an LP Problem
7.5 Solving Flair Furniture’s LP Problem using QM for Windows, Excel 2013, and Excel QM
7.6 Solving Minimization Problems
7.7 Four Special Cases in LP
7.8 Sensitivity Analysis
CHAPTER OUTLINE
Introduction
Many management decisions involve making the most effective use of limited resources
Linear programming (LP)
Widely used mathematical modeling technique
Planning and decision making relative to resource allocation
Broader field of mathematical programming
Here programming refers to modeling and solving a problem mathematically
Copyright ©2015 Pearson Education, Inc.
7 – 4
Requirements of a Linear Programming Problem
Four properties in common
Seek to maximize or minimize some quantity (the objective function)
Restrictions or constraints are present
Alternative courses of action are available
Linear equations or inequalities
Copyright ©2015 Pearson Education, Inc.
7 – 5
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 – proportionality and divisibility
5. Certainty
6. Divisibility
7. Nonnegative variables
TABLE 7.1
Copyright ©2015 Pearson Education, Inc.
7 – 6
Formulating LP Problems
Developing a mathematical model to represent the managerial problem
Steps in formulating a LP problem
Completely understand the managerial problem being faced
Identify the objective and the constraints
Define the decision variables
Use the decision variables to write mathematical expressions for the objective function and the constraints
Copyright ©2015 Pearson Education, Inc.
7 – 7
Formulating LP Problems
Common LP application – product mix problem
Two or more products are produced using limited resources
Maximize profit based on the profit contribution per unit of each product
Determine how many units of each product to produce
Copyright ©2015 Pearson Education, Inc.
7 – 8
Flair Furniture Company
Flair Furniture produces inexpensive tables and chairs
Processes are similar, both require carpentry work and painting and varnishing
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
Copyright ©2015 Pearson Education, 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
DEPARTMENT (T) TABLES (C) CHAIRS AVAILABLE HOURS THIS WEEK
Carpentry 4 3 240
Painting and varnishing 2 1 100
Profit per unit $70 $50
TABLE 7.2
Copyright ©2015 Pearson Education, Inc.
7 – 10
Flair Furniture Company
The objective is
Maximize profit
The constraints are
The hours of carpentry time used cannot exceed 240 hours per week
The hours of painting and varnishing time used cannot exceed 100 hours per week
The decision variables are
T = number of tables to be produced per week
C = number of chairs to be produced per week
Copyright ©2015 Pearson Education, Inc.
7 – 11
Flair Furniture Company
Create 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)
First constraint is
Carpentry time used ≤ Carpentry time available
4T + 3C ≤ 240 (hours of carpentry time)
Copyright ©2015 Pearson Education, 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
Copyright ©2015 Pearson Education, 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)
Copyright ©2015 Pearson Education, Inc.
7 – 14
Graphical Solution to an LP Problem
Easiest way to solve a small LP problems is graphically
Only works when there are just two decision variables
Not possible to plot a solution for more than two variables
Provides valuable insight into how other approaches work
Nonnegativity constraints mean that we are always working in the first (or northeast) quadrant of a graph
Copyright ©2015 Pearson Education, Inc.
7 – 15
Graphical Representation of Constraints
100 –
–
80 –
–
60 –
–
40 –
–
20 –
–
C
| | | | | | | | | | | |
0 20 40 60 80 100
T
Number of Chairs
Number of Tables
This Axis Represents the Constraint T ≥ 0
This Axis Represents the Constraint C ≥ 0
FIGURE 7.1 – Quadrant Containing All Positive Values
Copyright ©2015 Pearson Education, Inc.
7 – 16
Graphical Representation of Constraints
The first step is to identify a set or region of feasible solutions
Plot each constraint equation on a graph
Graph the equality portion of the constraint equations
4T + 3C = 240
Solve for the axis intercepts and draw the line
Copyright ©2015 Pearson Education, Inc.
7 – 17
Graphical Representation of Constraints
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
Copyright ©2015 Pearson Education, Inc.
7 – 18
Graphical Representation of Constraints
100 –
–
80 –
–
60 –
–
40 –
–
20 –
–
C
| | | | | | | | | | | |
0 20 40 60 80 100
T
Number of Chairs
Number of Tables
(T = 0, C = 80)
FIGURE 7.2 – Graph of Carpentry Constraint Equation
(T = 60, C = 0)
Copyright ©2015 Pearson Education, Inc.
7 – 19
FIGURE 7.3 – Region that Satisfies the Carpentry Constraint
Graphical Representation of Constraints
100 –
–
80 –
–
60 –
–
40 –
–
20 –
–
C
| | | | | | | | | | | |
0 20 40 60 80 100
T
Number of Chairs
Number of Tables
Any point on or below the constraint plot will not violate the restriction
Any point above the plot will violate the restriction
(30, 40)
(30, 20)
(70, 40)
Copyright ©2015 Pearson Education, Inc.
7 – 20
Graphical Representation of Constraints
The point (30, 40) lies on the line and exactly satisfies the constraint
4(30) + 3(40) = 240
The point (30, 20) lies below the line and satisfies the constraint
4(30) + 3(20) = 180
The point (70, 40) lies above the line and does not satisfy the constraint
4(70) + 3(40) = 400
Copyright ©2015 Pearson Education, Inc.
7 – 21
Graphical Representation of Constraints
100 –
–
80 –
–
60 –
–
40 –
–
20 –
–
C
| | | | | | | | | | | |
0 20 40 60 80 100
T
Number of Chairs
Number of Tables
(T = 0, C = 100)
FIGURE 7.4 – Region that Satisfies the Painting and Varnishing Constraint
(T = 50, C = 0)
Copyright ©2015 Pearson Education, Inc.
7 – 22
Graphical Representation of Constraints
To produce tables and chairs, both departments must be used
Find a solution that satisfies both constraints simultaneously
A new graph shows both constraint plots
The feasible region is where all constraints are satisfied
Any point inside this region is a feasible solution
Any point outside the region is an infeasible solution
Copyright ©2015 Pearson Education, Inc.
7 – 23
Graphical Representation of Constraints
100 –
–
80 –
–
60 –
–
40 –
–
20 –
–
C
| | | | | | | | | | | |
0 20 40 60 80 100
T
Number of Chairs
Number of Tables
FIGURE 7.5 – Feasible Solution Region
Painting/Varnishing Constraint
Carpentry Constraint
Feasible Region
Copyright ©2015 Pearson Education, Inc.
7 – 24
Graphical Representation of Constraints
For the point (30, 20)
Carpentry constraint 4T + 3C ≤ 240 hours available (4)(30) + (3)(20) = 180 hours used
Painting constraint 2T + 1C ≤ 100 hours available (2)(30) + (1)(20) = 80 hours used
Carpentry constraint 4T + 3C ≤ 240 hours available (4)(70) + (3)(40) = 400 hours used
Painting constraint 2T + 1C ≤ 100 hours available (2)(70) + (1)(40) = 180 hours used
For the point (70, 40)
Copyright ©2015 Pearson Education, Inc.
7 – 25
Graphical Representation of Constraints
For the point (50, 5)
Carpentry constraint 4T + 3C ≤ 240 hours available (4)(50) + (3)(5) = 215 hours used
Painting constraint 2T + 1C ≤ 100 hours available (2)(50) + (1)(5) = 105 hours used
Copyright ©2015 Pearson Education, Inc.
7 – 26
Isoprofit Line Solution Method
Find the optimal solution from the many possible solutions
Speediest method is to use the isoprofit line
Starting with a small possible profit value, graph the objective function
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
Copyright ©2015 Pearson Education, Inc.
7 – 27
Isoprofit Line Solution Method
Choose a profit of $2,100
The objective function is
$2,100 = 70T + 50C
Solving for the axis intercepts, draw the graph
Obviously not the best possible solution
Further graphs can be created using larger profits
The further we move from the origin, the larger the profit
The highest profit ($4,100) will be generated when the isoprofit line passes through the point (30, 40)
Copyright ©2015 Pearson Education, Inc.
7 – 28
100 –
–
80 –
–
60 –
–
40 –
–
20 –
–
C
| | | | | | | | | | | |
0 20 40 60 80 100
T
Number of Chairs
Number of Tables
$2,100 = $70T + $50C
Isoprofit Line Solution Method
(30, 0)
FIGURE 7.6 – Profit line of $2,100
Copyright ©2015 Pearson Education, Inc.
7 – 29
100 –
–
80 –
–
60 –
–
40 –
–
20 –
–
C
| | | | | | | | | | | |
0 20 40 60 80 100
T
Number of Chairs
Number of Tables
FIGURE 7.7 – Four Isoprofit Lines
$2,100 = $70T + $50C
$2,800 = $70T + $50C
$3,500 = $70T + $50C
$4,200 = $70T + $50C
Isoprofit Line Solution Method
Copyright ©2015 Pearson Education, Inc.
7 – 30
100 –
–
80 –
–
60 –
–
40 –
–
20 –
–
C
| | | | | | | | | | | |
0 20 40 60 80 100
T
Number of Chairs
Number of Tables
FIGURE 7.8 – Optimal Solution
$4,100 = $70T + $50C
Isoprofit Line Solution Method
Optimal Solution Point
(T = 30, C = 40)
Maximum Profit Line
Copyright ©2015 Pearson Education, Inc.
7 – 31
Corner Point Solution Method
The corner point method for solving LP problems
Look at the profit at every corner point of the feasible region
Mathematical theory is that an optimal solution must lie at one of the corner points or extreme points
Copyright ©2015 Pearson Education, Inc.
7 – 32
100 –
–
80 –
–
60 –
–
40 –
–
20 –
–
C
| | | | | | | | | | | |
0 20 40 60 80 100
T
Number of Chairs
Number of Tables
FIGURE 7.9 – Four Corner Points of the Feasible Region
Corner Point Solution Method
(0, 0)
(50, 0)
(0, 80)
(?)
Copyright ©2015 Pearson Education, Inc.
7 – 33
Corner Point Solution Method
Solve for the intersection of the two constraint lines
Using the elimination method to solve simultaneous equations method, select a variable to be eliminated
Eliminate T by multiplying the second equation by –2 and add it to the first equation
– 2(2T + 1C = 100) = – 4T – 2C = –200
4T + 3C = 240 (carpentry)
– 4T – 2C = –200 (painting)
C = 40
Copyright ©2015 Pearson Education, Inc.
7 – 34
Corner Point Solution Method
Substitute C = 40 into either equation to solve for T
4T + 3(40) = 240
4T + 120 = 240
4T = 120
T = 30
Thus the corner point is (30, 40)
NUMBER OF TABLES (T) NUMBER OF CHAIRS (C) PROFIT = $70T + $50C
0 0 $0
50 0 $3,500
0 80 $4,000
30 40 $4,100
TABLE 7.3 – Feasible Corner Points and Profits
Copyright ©2015 Pearson Education, Inc.
7 – 35
Highest profit – Optimal Solution
Slack and Surplus
Slack is the amount of a resource that is not used
For a less-than-or-equal constraint
Slack = (Amount of resource available) – (Amount of resource used)
Flair decides to produce 20 tables and 25 chairs
4(20) + 3(25) = 155 (carpentry time used)
240 = (carpentry time available)
240 – 155 = 85 (Slack time in carpentry)
Copyright ©2015 Pearson Education, Inc.
7 – 36
Slack is the amount of a resource that is not used
For a less-than-or-equal constraint
Slack = (Amount of resource available) – (Amount of resource used)
Slack and Surplus
Flair decides to produce 20 tables and 25 chairs
4(20) + 3(25) = 155 (carpentry time used)
240 = (carpentry time available)
240 – 155 = 85 (Slack time in carpentry)
At the optimal solution, slack is 0 as all 240 hours are used
Copyright ©2015 Pearson Education, Inc.
7 – 37
Slack and Surplus
Surplus is used with a greater-than-or-equal-to constraint to indicate the amount by which the right-hand side of the constraint is exceeded
Surplus = (Actual amount) – (Minimum amount)
New constraint
T + C ≥ 42
If T = 20 and C = 25, then
20 + 25 = 45
Surplus = 45 – 42 = 3
Copyright ©2015 Pearson Education, Inc.
7 – 38
Summaries 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.4
Copyright ©2015 Pearson Education, Inc.
7 – 39
Solving Flair Furniture’s LP Problem
Most organizations have access to software to solve big LP problems
There are differences between software implementations, the approach is basically the same
With experience with computerized LP algorithms, it is easy to adjust to minor changes
Copyright ©2015 Pearson Education, Inc.
7 – 40
Using QM for Windows
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 Flair Furniture there are two constraints, two decision variables, and the objective is to maximize profit
Copyright ©2015 Pearson Education, Inc.
7 – 41
Using QM for Windows
PROGRAM 7.1A – QM for Windows Linear Programming Computer Input Screen
Copyright ©2015 Pearson Education, Inc.
7 – 42
Using QM for Windows
PROGRAM 7.1B – QM for Windows Data Input
Copyright ©2015 Pearson Education, Inc.
7 – 43
Using QM for Windows
PROGRAM 7.1C –
QM for Windows
Output and Graph
Copyright ©2015 Pearson Education, Inc.
7 – 44
Using Excel’s Solver
The Solver tool in Excel can be used to find solutions to
LP problems
Integer programming problems
Noninteger programming problems
Solver is limited to 200 variables and, in some situations, 100 constraints
Copyright ©2015 Pearson Education, Inc.
7 – 45
Using Solver
Recall the model for Flair Furniture is
Maximize profit = $70T + $50C
Subject to 4T + 3C ≤ 240
2T + 1C ≤ 100
To use Solver, it is necessary to enter data and formulas
Copyright ©2015 Pearson Education, Inc.
7 – 46
Using Solver
Enter problem data
Variable names, coefficients for the objective function and constraints, RHS values for each constraint
Designate specific cells for the values of the decision variables
Write a formula to calculate the value of the objective function
Write a formula to compute the left-hand sides of each of the constraints
Copyright ©2015 Pearson Education, Inc.
7 – 47
Using Solver
PROGRAM 7.2A – Excel Data Input
Copyright ©2015 Pearson Education, Inc.
7 – 48
Using Solver
PROGRAM 7.2B – Formulas
Copyright ©2015 Pearson Education, Inc.
7 – 49
Using Solver
PROGRAM 7.2C – Excel Spreadsheet
Copyright ©2015 Pearson Education, Inc.
7 – 50
Using Solver
PROGRAM 7.2D – Starting Solver
Copyright ©2015 Pearson Education, Inc.
7 – 51
Using Solver
PROGRAM 7.2E –
Solver Parameters
Dialog Box
Copyright ©2015 Pearson Education, Inc.
7 – 52
Using Solver
PROGRAM 7.2F – Solver Add Constraint Dialog Box
Copyright ©2015 Pearson Education, Inc.
7 – 53
Using Solver
PROGRAM 7.2G – Solver Results Dialog Box
Copyright ©2015 Pearson Education, Inc.
7 – 54
Using Solver
PROGRAM 7.2H – Solution
Copyright ©2015 Pearson Education, Inc.
7 – 55
Using Excel QM
Copyright ©2015 Pearson Education, Inc.
PROGRAM 7.3A –
Excel QM in Excel 2013
7 – 56
Using Excel QM
Copyright ©2015 Pearson Education, Inc.
PROGRAM 7.3B – Excel QM Input Data
7 – 57
Using Excel QM
Copyright ©2015 Pearson Education, Inc.
PROGRAM 7.3C – Excel QM Output
7 – 58
Solving Minimization Problems
Many LP problems involve minimizing an objective such as cost
Minimization problems can be solved graphically
Set up the feasible solution region
Use either the corner point method or an isocost line approach
Find the values of the decision variables (e.g., X1 and X2) that yield the minimum cost
Copyright ©2015 Pearson Education, Inc.
7 – 59
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
INGREDIENT COMPOSITION OF EACH POUND OF FEED (OZ.) MINIMUM MONTHLY REQUIREMENT PER TURKEY (OZ.)
BRAND 1 FEED BRAND 2 FEED
A 5 10 90
B 4 3 48
C 0.5 0 1.5
Cost per pound 2 cents 3 cents
TABLE 7.5 – Holiday Meal Turkey Ranch data
Copyright ©2015 Pearson Education, Inc.
7 – 60
Minimize cost (in cents) = 2X1 + 3X2
subject to:
5X1 + 10X2 ≥ 90 ounces (ingredient A constraint)
4X1 + 3X2 ≥ 48 ounces (ingredient B constraint)
0.5X1 ≥ 1.5 ounces (ingredient C constraint)
X1 ≥ 0 (nonnegativity constraint)
X2 ≥ 0 (nonnegativity constraint)
Holiday Meal Turkey Ranch
X1 = number of pounds of brand 1 feed purchased
X2 = number of pounds of brand 2 feed purchased
Let
Copyright ©2015 Pearson Education, Inc.
7 – 61
Holiday Meal Turkey Ranch
–
20 –
15 –
10 –
5 –
0 –
X2
| | | | | |
5 10 15 20 25
X1
Pounds of Brand 2
Pounds of Brand 1
Ingredient C Constraint
Ingredient B Constraint
Ingredient A Constraint
Feasible Region
a
b
c
FIGURE 7.10 – Feasible Region
Copyright ©2015 Pearson Education, Inc.
7 – 62
Holiday Meal Turkey Ranch
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 we find X1 = 8.4 and X2 = 4.8
Solving for point c we find X1 = 18 and X2 = 0
Copyright ©2015 Pearson Education, Inc.
7 – 63
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
Holiday Meal Turkey Ranch
Substituting these values back into the objective function we find
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
Copyright ©2015 Pearson Education, Inc.
7 – 64
Holiday Meal Turkey Ranch
Solving using an isocost line
Move the isocost line toward the lower left
The last point touched in the feasible region will be the optimal solution
Copyright ©2015 Pearson Education, Inc.
7 – 65
Holiday Meal Turkey Ranch
–
20 –
15 –
10 –
5 –
0 –
X2
| | | | | |
5 10 15 20 25
X1
Pounds of Brand 2
Pounds of Brand 1
FIGURE 7.11 – Graphical Solution Using the Isocost Approach
Feasible Region
54¢ = 2X1 + 3X2 Isocost Line
Direction of Decreasing Cost
31.2¢ = 2X1 + 3X2
(X1 = 8.4, X2 = 4.8)
Copyright ©2015 Pearson Education, Inc.
7 – 66
Holiday Meal Turkey Ranch
PROGRAM 7.4 – Solution in QM for Windows
Copyright ©2015 Pearson Education, Inc.
7 – 67
Holiday Meal Turkey Ranch
PROGRAM 7.5A – Excel 2013 Solution
Copyright ©2015 Pearson Education, Inc.
7 – 68
Holiday Meal Turkey Ranch
PROGRAM 7.5B – Excel 2013 Formulas
Copyright ©2015 Pearson Education, Inc.
7 – 69
Four Special Cases in LP
Four special cases and difficulties arise at times when using the graphical approach
No feasible solution
Unboundedness
Redundancy
Alternate Optimal Solutions
Copyright ©2015 Pearson Education, Inc.
7 – 70
No Feasible Solution
No solution to the problem that satisfies all the constraint equations
No feasible solution region exists
A common occurrence in the real world
Generally one or more constraints are relaxed until a solution is found
Consider the following three constraints
Copyright ©2015 Pearson Education, Inc.
7 – 71
No Feasible Solution
8 –
–
6 –
–
4 –
–
2 –
–
0 –
| | | | | | | | | |
2 4 6 8
X2
X1
Region Satisfying First Two Constraints
FIGURE 7.12 – A problem with no feasible solution
Region Satisfying Third Constraint
Copyright ©2015 Pearson Education, Inc.
7 – 72
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
Usually means the problem has been formulated improperly
Copyright ©2015 Pearson Education, Inc.
7 – 73
Unboundedness
15 –
10 –
5 –
0 –
X2
| | | | |
5 10 15
X1
Feasible Region
X1 ≥ 5
X2 ≤ 10
X1 + 2X2 ≥ 10
FIGURE 7.13 – A Feasible Region That Is Unbounded to the Right
Maximize profit = $3X1 + $5X2
subject to X1 ≥ 5
X2 ≤ 10
X1 + 2X2 ≥ 10
X1, X2 ≥ 0
Copyright ©2015 Pearson Education, Inc.
7 – 74
Redundancy
A redundant constraint is one that does not affect the feasible solution region
One or more constraints may be binding
This is a very common occurrence in the real world
Causes no particular problems, but eliminating redundant constraints simplifies the model
Maximize profit = $1X1 + $2X2
subject to X1 + X2 ≤ 20
2X1 + X2 ≤ 30
X1 ≤ 25
X1, X2 ≥ 0
Copyright ©2015 Pearson Education, Inc.
7 – 75
Redundancy
Maximize profit = $1X1 + $2X2
subject to X1 + X2 ≤ 20
2X1 + X2 ≤ 30
X1 ≤ 25
X1, X2 ≥ 0
30 –
25 –
20 –
15 –
10 –
5 –
0 –
X2
| | | | | |
5 10 15 20 25 30
X1
FIGURE 7.14 – Problem with a Redundant Constraint
Redundant Constraint
Feasible Region
X1 ≤ 25
2X1 + X2 ≤ 30
X1 + X2 ≤ 20
Copyright ©2015 Pearson Education, Inc.
7 – 76
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
Allows management great flexibility in deciding which combination to select as the profit is the same at each alternate solution
Maximize profit = $3X1 + $2X2
subject to 6X1 + 4X2 ≤ 24
X1 ≤ 3
X1, X2 ≥ 0
Copyright ©2015 Pearson Education, Inc.
7 – 77
Alternate Optimal Solutions
Maximize profit = $3X1 + $2X2
subject to 6X1 + 4X2 ≤ 24
X1 ≤ 3
X1, X2 ≥ 0
8 –
7 –
6 –
5 –
4 –
3 –
2 –
1 –
0 –
X2
| | | | | | | |
1 2 3 4 5 6 7 8
X1
FIGURE 7.15 – Example of Alternate Optimal Solutions
Feasible Region
Isoprofit Line for $8
Optimal Solution Consists of All Combinations of X1 and X2 Along the AB Segment
Isoprofit Line for $12 Overlays Line Segment AB
B
A
Copyright ©2015 Pearson Education, Inc.
7 – 78
Sensitivity Analysis
Optimal solutions to LP problems thus far have been found under deterministic assumptions
We assume complete certainty in the data and relationships of a problem
Real world conditions are dynamic
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
Copyright ©2015 Pearson Education, Inc.
7 – 79
Sensitivity Analysis
Involves a series of what-if? questions concerning constraints, variable coefficients, and the objective function
Trial-and-error method
Values are changed and the entire model is resolved
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
Copyright ©2015 Pearson Education, Inc.
7 – 80
High Note Sound Company
The company manufactures quality speakers and stereo receivers
Products require a certain amount of skilled artisanship which is in limited supply
Product mix LP model
Maximize profit = $50X1 + $120X2
subject to 2X1 + 4X2 ≤ 80 (hours of electricians’ time available)
3X1 + 1X2 ≤ 60 (hours of audio technicians’ time available)
X1, X2 ≥ 0
Copyright ©2015 Pearson Education, Inc.
7 – 81
High Note Sound Company
b = (16, 12)
Optimal Solution at Point a
X1 = 0 Speakers
X2 = 20 Receivers
Profits = $2,400
a = (0, 20)
Isoprofit Line: $2,400 = 50X1 + 120X2
60 –
–
40 –
–
20 –
10 –
0 –
X2
| | | | | |
10 20 30 40 50 60
X1
(Receivers)
(Speakers)
c = (20, 0)
FIGURE 7.16 – The High Note Sound Company Graphical Solution
Copyright ©2015 Pearson Education, Inc.
7 – 82
High Note Sound Company
Electrician hours used are
2X1 + 4X2 = 2(0) + 4(20) = 80
All hours are utilized so slack = 0
Additional units of a binding constraint will generally increase profits
Technician hours used are