Transcript abcsoptm - The University of Chicago Booth School of Business

University of Chicago
Graduate School of Business
Introduction to Computer Based Models
Mr. Schrage
The ABC’s of Optimization
Bus-36102-81
Spring 2003
Example Applications of Optimization
Auction of Electricity Transmission Capacity in a U.S. state:
Maximize the value of awards, subject to not selling more
capacity than is available. Interesting feature: a bidder may bid on
a combination of lines, e.g., if in series. Dual prices are the
clearing prices.
Electrical Generator Unit Commitment at GE:
Given forecasted demand over next 24 hours, week, etc., and
cost structure of each generator, which generators should be run
in which intervals?
Example Applications, cont.
Plant Configuration Under Uncertainty at GM:
Which plants to close, which to re-focus, given demand
scenarios and their probabilities. Used three scenarios/year over
a five year planning horizon.
Gas contract selection under uncertainty at Peoples Gas:
which gas contracts to buy when, how much gas to store,
when to draw it out, in the face of uncertainty(represented by
about a dozen scenarios).
Example Applications, cont.
Cutting stock: Cable cutting at Anixter, paper rolls at a paper
company. Given length(width) of master or jumbo, and
amount needed of the smaller f.g., lengths(widths), what cutting
patterns should be used?
Supply Chain Redesign/DC Location at P&G: After merging in
several new product lines and distribution centers, which DC’s
should be closed? Which DC’s should serve which customers?
Tire Production Scheduling at Bridgestone/Firestone: Given daily
demand schedule and which combinations of tires can be
produced together in which heaters, which tire combinations
should be run in which heaters?
Example Applications, cont.
Gas Pipeline capacity auction (Midwestern U.S.) Given pipeline
capacity requested over what interval of days, and amount bid,
which bids should be awarded, so as to maximize sales revenue
and not exceed daily pipeline capacity.
Quality Improvement via Matching of Components(electronics
manufacturer). Certain devices, e.g., cell phone mikes, blades in
a jet engine turbine, should be closely matched to improve
performance/quality. Solved a “matching” IP to increase yield to
about 75% from 60%.
Staffing and Rostering of maintenance personnel at a cell phone
company, regular labor at metal fabrication firm, crew
scheduling at airlines, telephone call center.
Example Applications, cont.
Multiperiod Production Planning and Blending at Welch’s
Grape:
Meet demands each month at locations around the country from
sources around the country, taking into account the required
quality levels(mainly acidity) at the demand points, and available
quality at each supply point.
Financial Portfolios: How much to invest in which assets given
expected returns, interactions/correlations among investments,
at a telecommunications company, mutual fund firm.
The A B C's of Optimization
A) Identify the Adjustable cells,
i.e., the decision variables
B) How do we measure Best?
i.e., specify an objective function,
or criterion function
C) What are the Constraints?
i.e., the relationships that limit
what we can do.
Typical variables:
How much do we buy, produce, ship, carry
in inventory; - from a specific vendor
of a specific product in a specific period.
Typical objectives:
Maximize wealth at end of period T.
Typical constraint:
sources of a commodity = uses of a commodity,
where commodity could be cash, labor, capacity,
product, etc.
Example
Enginola Company makes 2 types of TV's:
Astro: Profit contribution(PC) = $20/unit,
uses 1 hour of labor.
Cosmo: PC = $30/unit, uses 2 hours of labor.
Each product is produced on its own line
with capacities: 60/day on Astro line, 50/day on Cosmo line.
Labor availability is 120 hours/day.
Some questions:
How much should we produce of each?
How much are extra resources worth?
of Astro capacity,
Cosmo capacity,
Labor capacity?
Model in words:
A) Decision variables:
A = no. of Astros produced/day
C = no. of Cosmos produced/day.
B) Objective:
Maximize profit contribution.
C) Constraints:
Astro production not to exceed 60,
Cosmo production not to exceed 50,
Labor usage not to exceed 120 hours.
What would you recommend?
Cosmo is more profitable/unit....
Astro makes more $/hour of labor..
What is the value of an additional
hour of labor?
$20, $15, $0?
An LP Model
[1] MAX = 20 * A + 30 * C;
[2]
A
<= 60;
[3]
C <= 50;
[4]
A + 2 * C <= 120;
The Solution Report is:
Variable
A
C
Row
1
2
3
4
Value
60.00000
30.00000
Slack or Surplus
2100.00000
0.00000
20.00000
0.00000
Reduced Cost
0.0000000
0.0000000
Dual Price
1.000000
5.000000
0.000000
15.000000
Economic Information in the Report
Dual Price = value of an additional unit of the
resource associated with the constraint.
Reduced Cost = amount by which the cost per unit
of the associated variable must be
reduced to make it “competitive”.
Alternatively: amount by which profit
contribution must be increased, or
reduction in profit if you force one
unit of this variable into the solution.
Graphical Version of Astro/Cosmo
If we have two or less decision variables,
or two or less constraints, then the
problem can be represented graphically.
A Spreadsheet Digression, More Later….
Astro/Cosmo Problem in Spreadsheet form. (astrocos.xls)
Product:
Volume:
Astro
60
Cosmo
30
DR
0
Profit C.:
A-line:
C-Line:
Labor:
20
1
0
1
30
0
1
2
47
1
1
3
Reduced Cost:
0
0
3
Total
Usage
2100
60 =<=
30 <=
120 =<=
This LP formulated in What'sBest! Style, see http://www.lindo.com
To do the ABC's, see the WB! Menu above.
To solve, click on the bullseye.
Availability
Dual
Prices
60
50
120
5
0
15
A Complete Example
A new condominium conversion.
City fathers require each apartment to be assigned
at least one parking spot.
From C. H. von Lanzenauer
Optimization Problems in General
When we try to solve a problem,
Possible Outcomes:
Infeasible
Feasible
Optimum(Finite)
Unbounded
Formulations with Anomalies
1) Unbounded, Clearly a mistake.
2) Infeasible,
Could be a mistake, but could be a
misunderstanding of what is
simultaneously possible.
3) Multiple or Alternative Optima
Quite common, but not good.
God’s way of telling us to put more detail into the
objective function. Real people are not indifferent
between alternatives.
Example: Unbounded Formulation
Suppose we forget some constraints in Astro/Cosmo:
MAX = 20 * A + 30 * C;
A
<= 60;
LINGO Reports:
Unbounded solution.
Variable
A
C
Row
1
2
Value
60.000000
0.9999999E+08
Slack or Surplus
0.3000001E+10
0.0000000
Reduced Cost
0.000000
-30.000000
Dual Price
1.000000
20.00000
Example: Infeasible Formulation
We type an inequality and RHS incorrectly:
MAX = 20 * A + 30 * C;
A
<= 60;
C <= 50;
A
+ 2* C >= 190;
LINGO reports:
No feasible solution found.
Variable
Value
A
60.00000
C
50.00000
Row
1
2
3
4
Slack or Surplus
2700.000
0.0000000
0.0000000
-30.00000
Reduced Cost
0.0000000
0.0000000
Dual Price
0.0000000
1.000000
2.000000
-1.000000
Example: Multiple Optima
MAX = 15 * A + 30 * C;
A
<= 60;
C <= 50;
A + 2 * C <= 120;
Lingo reports:
Variable
A
C
Row
1
2
3
4
Value
20.00000
50.00000
Reduced Cost
0.000000
0.000000
Slack or Surplus
1800.000000
40.000000
0.000000
0.000000
Dual Price
1.000000
0.000000
0.000000
15.000000
Ranges in which the basis is unchanged:
Objective Coefficient Ranges
Current
Allowable
Variable Coefficient
Increase
A
15.00000
0.0
C
30.00000
INFINITY
Row
2
3
4
Allowable
Decrease
15.00000
0.0
Righthand Side Ranges
Current
Allowable
Allowable
RHS
Increase
Decrease
60.00000
INFINITY
40.00000
50.00000
10.00000
20.00000
120.00000
40.00000
20.00000
We can coax out an alternate optima:
MAX = 15.0001 * A + 30 *
A
<=
C <=
A + 2 * C <=
Variable
A
C
Row
1
2
3
4
Value
60.00000
30.00000
C;
60;
50;
120;
Reduced Cost
0.0000000
0.0000000
Slack or Surplus
Dual Price
1800.006
1.000000
0.0000000
0.1000000E-03
20.00000
0.0000000
0.0000000
15.00000
Linearity
Typical model has hundreds, or
thousands of decision variables and constraints.
If it is not linear, it is:
i) hard to solve,
ii) hard to prove you have a global optimum.
What is linearity?
Graphically:
Constraints and objective are straight lines.
Linearity continued:
Mathematically:
a) Effect of individual variable is proportional,
e.g., no quantity discounts.
b) Interactions between variable are additive,
e.g., cannot have: price * quantity,
if both are decision variables.
c) Continuous values are allowed,
e.g., if 2 and 3 are possible values,
then so is 2.6731.
Linearity restrictions can be circumvented*,
but at the price of (perhaps much) longer computation time.
(*by using integer programming)
Opportunity Costs: Dual Prices and Reduced Costs
Enginola is considering the manufacture of a digital tape recorder.
Producing one would require
1 unit of capacity on the Astro line,
1 unit of capacity on the Cosmo line,
3 hours of labor, Its profit contribution would be $47/unit
Is it worthwhile to produce the digital recorder(DR)?
Recall, before DR came upon the scene:
MAX = 20 * A + 30 * C;
A
<= 60;
C <= 50;
A + 2 * C <= 120;
Variable
A
C
Row
1
2
3
4
Value
60.00000
30.00000
Slack or Surplus
2100.00000
0.00000
20.00000
0.00000
Reduced Cost
0.0000000
0.0000000
Dual Price
1.000000
5.000000
0.000000
15.000000
Observations:
DR is most profitable product/unit.
Its profit contribution per labor hour is better than Cosmo.
But it does use more resources.
Without re-solving, what do you recommend?
The expanded formulation is:
MAX = 20 * A + 30 * C + 47
A
C
A + 2 * C + 3
*
+
+
*
DR;
DR <= 60;
DR <= 50;
DR <= 120;
with solution:
Variable
A
C
DR
Row
1
2
3
4
Value
60.000000
30.000000
0.000000
Slack or Surplus
2100.000000
0.000000
20.000000
0.000000
Reduced Cost
0.0000000
0.0000000
3.0000000
Dual Price
1.000000
5.000000
0.000000
15.000000
The Costing Out Operation/Reduced Costs
For activity DR:
Row
Coefficient
1
2
3
4
-47.0
1.0
1.0
3.0
Dual Price
Coef*Price
1.0
5.0
0.0
15.0
-47.0
5.0
0.0
45.0
--------Net opportunity cost=
3.0
Note, we do everything in terms of cost, so we put a -47.0 in the
objective row because the 47 is a profit contribution, which is
equivalent to a cost of -47. The whole operation is stated terms of
net opportunity cost.
For activity A:
Row
1
2
3
4
Coefficient
-20.0
1.0
0.0
1.0
Dual Price
Coef*Price
1.0
5.0
0.0
15.0
-20.0
5.0
0.0
15.0
--------Net opportunity cost=
0.0
So the Reduced Cost is the
net opportunity cost of an activity,
relative to the "incumbent" or “basic” activities.
Integer Programming
Example with general integer variables
MAX = 20 * A + 30 * C;
A
<= 60;
C <= 50;
A + 2 * C <= 119;
Variable
A
C
Row
1
2
3
4
Value
60.00000
29.50000
Reduced Cost
0.0000000
0.0000000
Slack or Surplus
Dual Price
2085.000000
1.000000
0.000000
5.000000
20.500000
0.0000000
0.000000
15.00000
That fractional value for C may not useful, so use @GIN...
1]MAX = 20 * A + 30 * C;
2]
A
<= 60;
3]
C <= 50;
4]
A + 2 * C <= 119;
5]! Require C to be General INteger;
6] @GIN( C);
Now we get the more useful solution:
Variable
A
C
Row
1
2
3
4
Value
59.000000
30.000000
Slack or Surplus
2080.000000
1.000000
20.000000
0.000000
Reduced Cost
0.000000
10.000000
Dual Price
1.000000
0.000000
0.000000
20.000000
Note, dual prices and reduce costs have limited interpretation with integer variables.
Go/No-Go Decisions and Binary Variables
1]! Make or buy decisions:
2]
Case 1) Minimum batch size;
3]! If we do any C, must do at least 40;
4]MAX = 20 * A + 30 * C;
5]
A
<= 60;
6]
C <= 50;
7]
A + 2 * C <= 120;
8]! Define YC = 1 if we make any C, else 0;
9]! Make YC a BINary variable;
10]
@BIN( YC);
11]! If YC = 1, then C >= 40;
12]
C >= 40 * YC;
13]! If YC = 0, then C <= 0;
14]
C <= 50 * YC;
The solution says its worth “taking the plunge” with C:
Variable
A
C
YC
Row
1
2
3
4
5
6
Value
40.00000
40.00000
1.000000
Reduced Cost
0.000000
0.000000
400.000000
Slack or Surplus
Dual Price
2000.000000
1.000000
20.000000
0.000000
10.000000
0.000000
0.000000
20.000000
0.000000
-10.000000
10.00000
0.0000000
A Second Common Use of Binary Variables:
1]! Make or buy decisions:
2]
Case 2) Fixed cost;
3]! If we do any A, must pay $700 fixed cost;
4]! Define YA = 1 if we make any A, else 0;
5]MAX = 20 * A + 30 * C - 700 * YA;
6]
A
<= 60;
7]
C <= 50;
8]
A + 2 * C <= 120;
9]! Make YA a BINary variable;
10]@BIN( YA);
11]! If YA = 0, then A <= 0;
12]
A <= 60 * YA;
Solution says it is not worth “paying the entry fee” for A:
Optimal solution found at step:
Objective value:
Branch count:
Variable
A
C
YA
Row
1
2
3
4
5
Value
0.000000
50.000000
0.000000
Slack or Surplus
1500.000000
60.000000
0.000000
20.000000
0.000000
8
1500.000
1
Reduced Cost
0.0000000
0.0000000
-500.0000
Dual Price
1.000000
0.000000
30.000000
0.000000
20.000000
Sensitivity/Range Analysis
Consider our old friend/acquaintance:
MODEL:
[PROFIT] MAX = 20 * A + 30 * C + 47
[ACAP]
A
[CCAP]
C
[LABOR]
A + 2 * C + 3
END
with solution:
VARIABLE
A
C
DR
ROW
PROFIT
ACAP
CCAP
LABOR
VALUE
60.00000
30.00000
.0000000
SLACK OR SURPLUS
2100.000000
0.000000
20.000000
0.000000
*
+
+
*
DR;
DR <= 60;
DR <= 50;
DR <= 120;
REDUCED COST
.0000000
.0000000
3.000000
DUAL PRICE
1.000000
5.000000
0.000000
15.000000
Over what range can we vary:
an objective coefficient and still have
the same values for the decision variables,
a RHS coefficient and still have
the same dual prices and reduced costs?
The range report gives this info:
RANGES IN WHICH THE BASIS IS UNCHANGED:
VARIABLE
A
C
DR
ROW
ACAP
CCAP
LABOR
CURRENT
COEF
20.000000
30.000000
47.000000
CURRENT
RHS
60.000000
50.000000
120.000000
OBJ COEFFICIENT RANGES
ALLOWABLE
ALLOWABLE
INCREASE
DECREASE
INFINITY
3.000000
10.000000
3.000000
3.000000
INFINITY
RIGHTHAND SIDE
ALLOWABLE
INCREASE
60.000000
INFINITY
40.000000
RANGES
ALLOWABLE
DECREASE
40.000000
20.000000
60.000000