Lawrence&Pasternack - Ch02 - LPILP Models
Lawrence&Pasternack - Ch02 - LPILP Models
Lawrence&Pasternack - Ch02 - LPILP Models
Linear
Linear and
and Integer
Integer
Programming
Programming Models
Models
1
2.1 Introduction to Linear Programming
• A Linear Programming model seeks to maximize or
minimize a linear function, subject to a set of linear
constraints.
• The linear model consists of the following
components:
– A set of decision variables.
– An objective function.
– A set of constraints.
2
Introduction to Linear Programming
• The Importance of Linear Programming
– Many real world problems lend themselves to linear
programming modeling.
– Many real world problems can be approximated by linear models.
– There are well-known successful applications in:
• Manufacturing
• Marketing
• Finance (investment)
• Advertising
• Agriculture
3
Introduction to Linear Programming
• The Importance of Linear Programming
– There are efficient solution techniques that solve linear
programming models.
– The output generated from linear programming packages
provides useful “what if” analysis.
4
Introduction to Linear Programming
• Assumptions of the linear programming model
– The parameter values are known with certainty.
– The objective function and constraints exhibit
constant returns to scale.
– There are no interactions between the decision
variables (the additivity assumption).
– The Continuity assumption: Variables can take on
any value within a given feasible range.
5
The Galaxy Industries Production Problem –
A Prototype Example
6
The Galaxy Industries Production Problem –
A Prototype Example
• Marketing requirement
– Total production cannot exceed 700 dozens.
– Number of dozens of Space Rays cannot exceed
number of dozens of Zappers by more than 350.
• Technological input
– Space Rays requires 2 pounds of plastic and
3 minutes of labor per dozen.
– Zappers requires 1 pound of plastic and
4 minutes of labor per dozen. 7
The Galaxy Industries Production Problem –
A Prototype Example
• The current production plan calls for:
– Producing as much as possible of the more profitable product,
Space Ray ($8 profit per dozen).
– Use resources left over to produce Zappers ($5 profit
per dozen), while remaining within the marketing guidelines.
• The current production plan consists of:
Space Rays = 450 dozen 8(450) + 5(100)
Zapper = 100 dozen
Profit = $4100 per week
8
Management is seeking a
production schedule that will
increase the company’s profit.
9
A linear programming model
can provide an insight and an
intelligent solution to this problem.
10
The Galaxy Linear Programming Model
• Decisions variables:
– X1 = Weekly production level of Space Rays (in dozens)
– X2 = Weekly production level of Zappers (in dozens).
• Objective Function:
– Weekly profit, to be maximized
11
The Galaxy Linear Programming Model
FEASIBLE REGION
13
Using a graphical presentation
we can represent all the constraints,
the objective function, and the three
types of feasible points.
14
Graphical Analysis – the Feasible Region
X2
X1
15
Graphical Analysis – the Feasible Region
X2
Infeasible
Production Feasible
Time
3X1+4X2 2400 X1
500 700
16
Graphical Analysis – the Feasible Region
X2
1000 The Plastic constraint
2X1+X2 1000
700 Total production constraint:
X1+X2 700 (redundant)
500
Infeasible
Production mix
constraint:
Production Feasible X1-X2 350
Time
3X1+4X22400
X1
500 700
Interior points. Boundary points. Extreme points.
• There are three types of feasible points 17
Solving Graphically for an
Optimal Solution
18
The search for an optimal solution
X2 Start at some arbitrary profit, say profit = $2,000...
1000 Then increase the profit, if possible...
...and continue until it becomes infeasible
X1
19
500
Summary of the optimal solution
Space Rays = 320 dozen
Zappers = 360 dozen
Profit = $4360
– This solution utilizes all the plastic and all the production hours.
20
Extreme points and optimal solutions
21
Multiple optimal solutions
• For multiple optimal solutions to exist, the objective
function must be parallel to one of the constraints
22
2.4 The Role of Sensitivity Analysis
of the Optimal Solution
• Is the optimal solution sensitive to changes in
input parameters?
• Range of Optimality
– The optimal solution will remain unchanged as long as
• An objective function coefficient lies within its range of
optimality
• There are no changes in any other input parameters.
M
Ma ax 4
x3
.75 X1 +
X 5X
1 +
Ma
5X 2
x8
2
X1
+5
500
X2
Max
2X + 5X
1
2
X1
25
500 800
Sensitivity Analysis of
Objective
X
Function Coefficients.
1000 2
Ma
x8
X1
Ma
Allowable Increase = 10 – 8 = $2
x
10
Ma
x3
+5
.7 5
X1 +
X2
5X
2
28
Sensitivity Analysis of
Right-Hand Side Values
• Any change to the right hand side of a binding
constraint will change the optimal solution.
30
Shadow Price – graphical demonstration
The Plastic
constraint X2
When more plastic becomes available (the
plastic constraint is relaxed), the right hand
side of the plastic constraint increases.
1000
2X 1
+1
+1
x 2<
x 2<
=10
01
500
00
Shadow price =
4363.40 – 4360.00 = 3.40
Production time X1
constraint
500 31
Range of Feasibility
32
The Plastic
Range of Feasibility
constraint X2
1000
x 2<
constraint constraint
X1 + X2 700
500
This is an infeasible solution
Production time
constraint
X1
500 33
The Plastic
Range of Feasibility
constraint 2X 1 X2
1000
as the amount of plastic
x 2
increases.
100
0
500
Production time
constraint
X1
500 34
2X1 + 1X2
Range of Feasibility
X2
500
2X1 + 1X2 1000
Allowable Increase=1100-100=100
A new active Allowable Decrease=1000– 600=400
constraint
X1
500 35
The correct interpretation of shadow prices
– Sunk costs: The shadow price is the value of an
extra unit of the resource, since the cost of the
resource is not included in the calculation of the
objective function coefficient.
36
Other Post - Optimality Changes
• Addition of a constraint.
• Deletion of a constraint.
• Addition of a variable.
• Deletion of a variable.
• Changes in the left - hand side coefficients.
37
2.5 Using Excel Solver to Find an
Optimal Solution and Analyze Results
• To see the input screen in Excel click Galaxy.xls
• Click Solver to obtain the following dialog box.
This cell contains Set Target cell $D$6
the value of the Equal To:
objective function By Changing cells
These cells contain $B$4:$C$4
the decision variables
$D$7:$D$10<=$F$7:$F$10
Click on ‘Options’
and check ‘Linear
Programming’ and
‘Non-negative’.
39
Using Excel Solver
$D$7:$D$10<=$F$7:$F$10
40
Using Excel Solver – Optimal Solution
GALAXY INDUSTRIES
Space Rays Zappers
Dozens 320 360
Total Limit
Profit 8 5 4360
Plastic 2 1 1000 <= 1000
Prod. Time 3 4 2400 <= 2400
Total 1 1 680 <= 700
Mix 1 -1 -40 <= 350
41
Using Excel Solver – Optimal Solution
GALAXY INDUSTRIES
Space Rays Zappers
Dozens 320 360
Total Limit
Profit 8 5 4360
Plastic 2 1 1000 <= 1000
Prod. Time 3 4 2400 <= 2400
Total 1 1 680 <= 700
Mix 1 -1 -40 <= 350
Adjustable Cells
Cell Name Original Value Final Value
$B$4 Dozens Space Rays 320 320
$C$4 Dozens Zappers 360 360
Constraints
Cell Name Cell Value Formula Status Slack
$D$7 Plastic Total 1000 $D$7<=$F$7 Binding 0
$D$8 Prod. Time Total 2400 $D$8<=$F$8 Binding 0
$D$9 Total Total 680 $D$9<=$F$9 Not Binding 20
$D$10 Mix Total -40 $D$10<=$F$10 Not Binding 390
43
Using Excel Solver –Sensitivity Report
Microsoft Excel Sensitivity Report
Worksheet: [Galaxy.xls]Sheet1
Report Created:
Adjustable Cells
Final Reduced Objective Allowable Allowable
Cell Name Value Cost Coefficient Increase Decrease
$B$4 Dozens Space Rays 320 0 8 2 4.25
$C$4 Dozens Zappers 360 0 5 5.666666667 1
Constraints
Final Shadow Constraint Allowable Allowable
Cell Name Value Price R.H. Side Increase Decrease
$D$7 Plastic Total 1000 3.4 1000 100 400
$D$8 Prod. Time Total 2400 0.4 2400 100 650
$D$9 Total Total 680 0 700 1E+30 20
$D$10 Mix Total -40 0 350 1E+30 390
44
2.7 Models Without Unique Optimal
Solutions
45
Infeasible Model
No point, simultaneously,
lies both above line 1 and
below lines 2 and 3
2
.
3 1
46
Solver – Infeasible Model
47
Unbounded solution
the Ma
xim
Ob
jec ize
Th ive t
ef Fu
ea nct
reg sib ion
ion le
48
Solver – Unbounded solution
49
Solver – An Alternate Optimal Solution
• Solver does not alert the user to the existence of
alternate optimal solutions.
• Many times alternate optimal solutions exist
when the allowable increase or allowable
decrease is equal to zero.
• In these cases, we can find alternate optimal
solutions using Solver by the following
procedure:
50
Solver – An Alternate Optimal Solution
• Observe that for some variable Xj the
Allowable increase = 0, or
Allowable decrease = 0.
• Add a constraint of the form:
Objective function = Current optimal value.
• If Allowable increase = 0, change the objective to
Maximize Xj
• If Allowable decrease = 0, change the objective to
Minimize Xj
51
2.8 Cost Minimization Diet Problem
• Mix two sea ration products: Texfoods, Calration.
• Minimize the total cost of the mix.
• Meet the minimum requirements of Vitamin A,
Vitamin D, and Iron.
52
Cost Minimization Diet Problem
• Decision variables
– X1 (X2) -- The number of two-ounce portions of
Texfoods (Calration) product used in a serving.
• The Model
Minimize 0.60X1 + 0.50X2 Cost per 2 oz.
Subject to
20X1 + 50X2 100 Vitamin A
% Vitamin A 25X1 + 25X2 100 Vitamin D
provided per 2 oz. 50X1 + 10X2 100 Iron % required
X1, X2 0
53
The Diet Problem - Graphical solution
10
The Iron constraint
Feasible Region
2 4 5 54
Cost Minimization Diet Problem
• Summary of the optimal solution
– The minimum requirement for Vitamin D and iron are met with
no surplus.
57