Quantitative Methods for Business دوره علم داده
دکتر فرزاد مینویی:مدرس
S03: Linear Programming – Part 2
Farzad Minooei, PhD, MBA
Implementing an LP Model in a Spreadsheet
• Organize the data on the spreadsheet.
• Preferably set adjacent cells for the
decision variables (changing variable
cells).
• Select one cell for the objective
function value.
• Use one row per constraint, ensuring
to line up the columns with the
corresponding changing variable
cells.
2
Excel Solver on Data Ribbon
If Excel Solver has been activated, you will find it on
the Data Ribbon toolbar.
3
Activating Excel Solver
To activate
Solver if it is
not on the data
toolbar, click
on the File
Tab and then
choose Excel
Options.
Activating Solver
Add-In
Choose Add-Ins
and Click Go…
Check Solver Add-In and
OK
Flair Furniture Company
Maximize profit = $70T + $50C
subject to
4T + 3C ≤ 240 (carpentry constraint)
2T + 1C ≤ 100 (painting and varnishing constraint)
T, C ≥0 (nonnegativity constraint)
6
Flair Furniture Company
7
Flair Furniture Company
8
Sensitivity Analysis in Linear Programming
• After solving a model, a number of questions often arise about the
optimal solution to the LP model.
• In particular we might be interested in how sensitive the optimal
solution is to changes in various coefficients of the LP model.
• Businesses rarely know with certainty which costs will be incurred or
the exact amount of resources that will be consumed or available in a
given situation or time period.
• Sensitivity analysis provides a better picture of how the solution to a
problem will change if different factors in the model change.
9
Sensitivity Analysis in Linear Programming
• When we formulate and solve an LP problem, we implicitly assume
that we can specify the exact values for these coefficients.
• Realizing that such uncertainties exist, a manager should consider how
sensitive an LP model’s solution is to changes or estimation errors in:
• The objective function coefficients
• The constraint coefficients
• The RHS values for the constraints
• A manager might consider a number of “What-if” questions about
these values.
10
Flair Furniture Company
11
Example Questions
• By how much would the profit per unit of table ($70) have to increase
or decrease before the current solution is no longer optimal?
• By how much would the profit per unit of chair ($50) have to increase
or decrease before the current solution is no longer optimal?
• How much would our profit increase if we could obtain 1 more hour
of carpentry time?
• How much would our profit increase if we could obtain 1 more hour
of painting and varnishing time?
12
Flair Furniture Company
Variable Changing Cells Sensitivity
Between allowable increase and decrease,
the optimal solution will not change.
However, profit will change.
Constraints (RHS) Sensitivity
Between allowable increase and decrease,
shadow price will not change, however
optimal solution may change.
13
Flair Furniture Company
14
Super Grain Corp. Advertising-Mix Problem
Let TV = Number of commercials for separate spots on television
M = Number of advertisements in magazines.
SS = Number of advertisements in Sunday supplements.
Maximize Exposure = 1,300TV + 600M + 500SS
subject to
Ad Spending: 300TV + 150M + 100SS ≤ 4,000 ($thousand)
Planning Cost: 90TV + 30M + 30SS ≤ 1,000 ($thousand)
Number of TV Spots: TV ≤ 5
and
TV ≥ 0, M ≥ 0, SS ≥ 0.
15
Super Grain Corp. Advertising-Mix Problem
16
Think-Big Capital Budgeting Problem
Let OB = Participation share in the office building,
H = Participation share in the hotel,
SC = Participation share in the shopping center.
Maximize NPV = 45OB + 70H + 50SC
subject to
Total invested now: 40OB + 80H + 90SC ≤ 25 ($million)
Total invested within 1 year: 100OB + 160H + 140SC ≤ 45 ($million)
Total invested within 2 years: 190OB + 240H + 160SC ≤ 65 ($million)
Total invested within 3 years: 200OB + 310H + 220SC ≤ 80 ($million)
and
OB ≥ 0, H ≥ 0, SC ≥ 0.
17
Think-Big Capital Budgeting Problem
18
Union Airways Personnel Scheduling
Let Si = Number working shift i (for i = 1 to 5),
Minimize Cost = $170S1 + $160S2 + $175S3 + $180S4 + $195S5
subject to
Total agents 6AM–8AM: S1 ≥ 48
Total agents 8AM–10AM: S1 + S2 ≥ 79
Total agents 10AM–12PM: S1 + S2 ≥ 65
Total agents 12PM–2PM: S1 + S2 + S3 ≥ 87
Total agents 2PM–4PM: S2 + S3 ≥ 64
Total agents 4PM–6PM: S3 + S4 ≥ 73
Total agents 6PM–8PM: S3 + S4 ≥ 82
Total agents 8PM–10PM: S4 ≥ 43
Total agents 10PM–12AM: S4 + S5 ≥ 52
Total agents 12AM–6AM: S5 ≥ 15
and
Si ≥ 0 (for i = 1 to 5)
19
Union Airways Personnel Scheduling
20
The Big M Transportation Problem
Let Sij = Number of lathes to ship from i to j (i = F1, F2; j = C1, C2, C3).
Minimize Cost = $700SF1-C1 + $900SF1-C2 + $800SF1-C3
+ $800SF2-C1 + $900SF2-C2 + $700SF2-C3
subject to
Factory 1: SF1-C1 + SF1-C2 + SF1-C3 = 12
Factory 2: SF2-C1 + SF2-C2 + SF2-C3 = 15
Customer 1: SF1-C1 + SF2-C1 = 10
Customer 2: SF1-C2 + SF2-C2 = 8
Customer 3: SF1-C3 + SF2-C3 = 9
and
Sij ≥ 0 (i = F1, F2; j = C1, C2, C3).
21
The Big M Transportation Problem
22
Five “Special Conditions” in LP Models
Condition Description Awareness Via
1 Unbounded (no limit) Error Message
2 Infeasibility (impossible) Error Message
3 Nonlinearity (not in textbook) Error Message
Observation: “unnecessary”
4 Redundant Constraints
constraint
Observation: Optimal
5 Alternate Optimal Solutions
solution keeps changing
Five “Special Conditions” in LP Models
1) Unbounded (no limit)
Solver has recognized that the
solution is an infinite value.
In an investment problem, an upper limit must be set
on the total amount of the investment. Otherwise the
optimal solution is to invest an “infinite” amount of
money to maximize the return.
constraint needed
Solution: In a Maximization problem you need at least one ≤ constraint. (In a
Minimization problem you need at least one ≥ constraint or the solution will be 0.)
Likely forgot to add a constraint.
Five “Special Conditions” in LP Models
2) Infeasibility
What if we get the signs mixed up when we put it
into Solver…..
W < 100
W > 120
100 120
Solver has determined that there is no set of values for the changing
cells that satisfies the constraints; you need to examine the
constraints to identify the conflict – often a sign reversal.
Five “Special Conditions” in LP Models
3) Nonlinearity
You have selected the ‘Simplex LP’ option, but Solver
determines that your model is not linear.
Solution: Check constraints and or the target cell for
formulas that are non-linear
Likely dividing changing cells by changing cells
Five “Special Conditions” in LP Models
4) Redundant Constraints
• Sometimes a constraint may not impact the feasible
region because the existence of all of the other
constraints mean that it is always satisfied. Therefore,
the constraint is not strictly necessary.
• You should keep a redundant constraint in with the
current model since a change in the formulation of the
problem may make it necessary in the future.
Five “Special Conditions” in LP Models
5) Alternate Optimal Solutions
• Sometimes there may be more than one “best solution”. Thus we
have ‘alternate optimal solutions’.
• Solver does not indicate whether there are alternate optimal
solutions.
• This is a rare case because the Objective Function would need to be
parallel to the binding constraint and the solution would be a line
segment.
29