Systems Optimization Introduction to LP

Linear Programming Hierarchy of Models Define Linear Models Modeling Examples in Excel and AMPL Hierarchy of Models Network Flows Linear Programs Mixed Integer Linear Programs 2 A More Academic View Mixed Integer Linear Programs Non-Convex Optimization Network Flows Linear Programs Convex Optimization 3 The Differences Objective Function Variables Linear Linear Continuous Continuous Convex Linear Continuous Discete or Continuous Linear Forms General Continuous General Network Flows Linear Programs Convex Optimization Mixed Integer Linear Programs Non-linear Optimization Constraints Special Linear Forms Linear Forms Convex Our Focus: • Linear Programs (LP), • Mixed Integer Linear Programs (MIP) • Heuristics 4 Agenda for LP First Example What is Linear? Several Illustrative Examples Excel and AMPL Revenue Optimization Application Portfolio Optimization 5 A First Example Simplified Oak Products Model Chair Style Captain Mate Profit/Chair $ 56 $ 40 Profit 0 0 0 Poduction Qty. Chair Component Total Usage Long Dowels 8 4 0 Short Dowels 4 12 0 Legs 4 4 0 Heavy Seats 1 0 0 Light Seats 0 1 0 Chairs Chair Production 1 1 0 ≤ ≤ ≤ ≤ ≤ ≥ Start Inventory End Inv. 1280 1280 1600 1600 760 760 140 140 120 120 Min. Production Slack 100 -100 6 Challenge Build a Solver Model 7 A First Example Simplified Oak Products Model Chair Style Captain Mate Profit/Chair $ 56 $ 40 Profit 0 0 0 Poduction Qty. Chair Component Total Usage Long Dowels 8 4 0 Short Dowels 4 12 0 Legs 4 4 0 Heavy Seats 1 0 0 Light Seats 0 1 0 Chairs Chair Production 1 1 0 ≤ ≤ ≤ ≤ ≤ ≥ Start Inventory End Inv. 1280 1280 1600 1600 760 760 140 140 120 120 Min. Production Slack 100 -100 8 The Model Objective: Maximize Profit =SUMPRODUCT(UnitProfit,Production) =$56*Production of Captains + $40*Production of Mates Variables: Production $B$4:$C$4 Production of Captains Production of Mates 9 Constraints Constraints: TotalUsage <= StartInventory =SUMPRODUCT(LongDowelsPerChair,Production) <= 1280 =SUMPRODUCT(ShortDowelsPerChair,Production) <= 1600 ... TotalProduction >= MinProduction =SUM(Production) >= 100 Options Assume Non-negative Assume Linear Model 10 What’s a Linear Model What is a linear function? Sum of known constants * variables NOTHING ELSE IS LINEAR Examples: Sum across a row of variables Sum down a column of variables $56*Production of Captains + $40*Production of Mates In Excel SUMPRODUCT(CONSTANTS, VARIABLES) In AMPL sum {index in Index Set}parameter[index]*variable[index] Index Set cannot depend on values of variables 11 A Test Variables: x and y Which are linear? x2 + y2 (1-sqrt(2))2 x + y/200 |x - y| x*y 10/x x/10 + y/20 sqrt(x2 + y2) 12 Linear Programs Objective: A linear function of the variables Variables: May be restricted to lie between a lower bound and an upper bound In AMPL var x >= 1, <= 200; Constraints: ≤ Linear Function of the variables ≥ Constant = 13 Why These Limitations! Can anything real be expressed with such limited tools? What do we get for all the effort? 14 Power of Expression The Marketing Hype: LOTS You will be amazed… Call before midnight tonight and get... Experience: Most of Almost Everything All of Almost Nothing 15 My Own Perspective Linear Programming Large portions of most real applications Basis for understanding Background for MIP (Mixed Integer Programming) Everything can be modeled with MIP, but... 16 What do we get for playing? Guarantees! Readily available algorithms that Find a provably best solution Quite fast even for large problems Less compelling generally Sensitivity Analysis (not available with MIP) 17 Review of Sensitivity Simplified Oak Products Model Chair Style Captain Mate Profit/Chair $ 56 $ 40 Profit Poduction Qty. 0 0 0 Total Usage Chair Component Long Dowels 8 4 0 Short Dowels 4 12 0 Legs 4 4 0 Heavy Seats 1 0 0 Light Seats 0 1 0 Chairs Chair Production 1 1 0 ≤ ≤ ≤ ≤ ≤ ≥ Start Inventory End Inv. 1280 1280 1600 1600 760 760 140 140 120 120 Min. Production Slack 100 -100 18 Review of Sensitivity Analysis Microsoft Excel 8.0a Sensitivity Report Worksheet: [07OakProductsLP.xls]Sheet1 Report Created: 12/19/01 4:52:52 PM Adjustable Cells Cell Name $B$4 Poduction Qty. Captain $C$4 Poduction Qty. Mate If the unit profit on the Mate were to drop, how much could it drop before we would quit making it? Final Reduced Objective Allowable Allowable Value Cost Coefficient Increase Decrease 16 130 0 56 24 12 60 0 40 16 Constraints Final Shadow Constraint Allowable Allowable Cell Name Value Price R.H. Side Increase Decrease 180 $D$6 Long Dowels Total Usage 1280 4 1280 40 $D$7 Short Dowels Total Usage 1240 0 1600 1E+30 360 $D$8 Legs Total Usage 760 6 760 72 40 $D$9 Heavy Seats Total Usage 130 0 140 1E+30 10 $D$10 Light Seats Total Usage 60 0 120 1E+30 60 $D$12 TotalProduction 190 0 100 90 1E+30 More Examples Illustrate “tricks” Build experience AMPL Examples 20 Blending Example Eastern Steel Blending Example (Described in Moore et al. Page 105 and following) 1 Tons of Ore/Ton of Alloy Cost/Ton $ 800 $ Mines 2 400 $ 3 600 $ 4 500 Lbs of each basic element/Ton of Ore Basic Element A B C 10 90 45 3 150 25 8 75 20 Lbs/Ton of Alloy 2 0 175 0 37 0 ≥ ≥ ≥ Min. Lbs/Ton of Alloy 5 100 30 21 Challenge Build a Solver model 22 Blending Example Eastern Steel Blending Example (Described in Moore et al. Page 105 and following) 1 Tons of Ore/Ton of Alloy Cost/Ton $ 800 $ Mines 2 400 $ 3 600 $ 4 500 Lbs of each basic element/Ton of Ore Basic Element A B C 10 90 45 3 150 25 8 75 20 Lbs/Ton of Alloy 2 0 175 0 37 0 ≥ ≥ ≥ Min. Lbs/Ton of Alloy 5 100 30 23 AMPL Model set MINES; set ELEMENTS; param MinLbs{ELEMENTS}; param CostPerTon{MINES}; param LbsPerTon{MINES, ELEMENTS}; var Tons{MINES} >= 0; minimize TotalCost: sum{mine in MINES} CostPerTon[mine]*Tons[mine]; s.t. CompositionConsts {elem in ELEMENTS}: sum{mine in MINES} LbsPerTon[mine, elem]*Tons[mine] >= MinLbs[elem]; s.t. TotalWeight: sum{mine in MINES} Tons[mine] = 1; 24 A Fixed Income Example Investment Example Bond Yield Quality Years to Maturity A B C D E 4.30% 2 9 2.70% 2 15 2.50% 1 4 2.20% 1 3 4.50% 5 2 Maximize Yield Conditions: at most at most at most 10 4 1.4 5 million to invest million total in C, D, and E average quality years average years to maturity 25 Challenge Build a linear model 26 A Fixed Income Example Investment Example Bond Yield Quality Years to Maturity A B C D E 4.30% 2 9 2.70% 2 15 2.50% 1 4 2.20% 1 3 4.50% 5 2 Maximize Yield Conditions: at most at most at most 10 4 1.4 5 million to invest million total in C, D, and E average quality years average years to maturity 27 Diseconomies of Scale If we are minimizing cost Unit cost increases with volume If we are maximizing profit Unit profit decreases with volume Inherent incentive towards small volumes 28 Example: Marketing Total Volume = 1000 Segment 2 Segment 1 ≤ 10 800 Revenue + Segment 1 First exposures drive sales 600 Then the novelty fades 400 200 0 0 Revenue = 5 60*Segment 1 10 Volume + 15 20 20*Segment 2 29 What about…. 1000 Revenue 800 600 400 200 0 0 5 10 Volume 15 20 30 A Financial Application Œ Financial Analysis Œ Define goals Œ Assess Risk vs. Return Œ Asset Allocation Œ Allocate assets among classes of investments Œ Track and forecast market swings Œ Fund Selection Œ No-Load Funds Œ Established Performance 31 Asset Allocation Asset Classes ¾Treasury Bills ¾Small Value Funds ¾Large Growth Funds ¾ Europe ¾ Emerging Markets ¾ HighYield Asset Allocation ¾Each Investor has target for each asset class 32 Fund Selection Screen Funds Rank in each Class for each Fund ¾Fidelity Equity Income II ¾LV LG SV JA EU GV HY ¾66 4 16 2 1 6 5 ¾Roughly speaking, the rank is the % of each funds investments that is in the asset class, e.g., Fidelity Equity Income II has 4% of its assets in Large Growth. Select Funds that meet the target allocation ¾ Minimize the total “deviation” from the targets ¾ Deviation is |Actual - Target| 33 Example Data Fund Ratings Fund Name Fidelity Adv Equity Fidelity Advisor Gro Fidelity Equity-Income Fidelity Equity Income-II Fidelity Growth/Income Fidelity Ins Cash Po Fidelity Investment Fidelity Intermediat Fidelity Limited Ter Fidelity Mortgage Se Fidelity Retirement Fidelity Short-Term Fidelity Value Fund Fidelity Worldwide F Targets T-Bill 7 0 0 0 2 100 0 13 5 53 0 44 0 0 Large Value 71 48 60 66 47 0 0 0 18 0 8 0 50 27 Large Growth 2 5 5 4 0 0 0 0 0 0 35 0 5 0 Small Value 6 26 20 16 17 0 2 0 0 0 24 0 31 14 Small Growth 7 7 0 0 11 0 0 0 0 0 16 0 1 0 Japan 2 0 3 2 3 0 0 0 0 2 1 0 4 11 Pacific 0 0 0 1 0 0 0 0 4 1 0 0 0 0 Europe 0 11 0 0 5 0 0 0 0 3 3 0 8 37 Emerging Markets 5 2 3 6 2 0 4 0 0 0 11 6 2 11 Government 0 0 0 0 0 0 92 83 45 34 0 25 0 0 High Yield 0 0 9 5 12 0 1 0 28 7 0 23 0 0 International Bonds 0 0 0 0 0 0 0 3 0 0 0 3 0 0 Gold 0 0 0 0 0 0 1 0 0 0 0 0 0 0 43 3 3 5 4 10 2 5 10 15 0 0 0 34 Example If we allocate 50% to the two funds… Asset Classes T-Bill Large Value Large Growth Small Value Small Growth Japan Pacific Europe Emerging Markets Government High Yield International Bonds Gold Fidelity Adv Equity Fidelity Advisor Gro 7 71 2 6 7 2 0 0 5 0 0 0 0 50% 0 48 5 26 7 0 0 11 2 0 0 0 0 50% Implied Allocation Target to Asset Classes Allocation Deviation 3.5 43 39.5 59.5 3 56.5 3.5 3 0.5 16 5 11 7 4 3 1 10 9 0 2 2 5.5 5 0.5 3.5 10 6.5 0 15 15 0 0 0 0 0 0 0 0 0 Total 143.5 35 Challenge #2 Build a linear model to find a best portfolio. First build your model in Excel (Use the file Portfolio.xls) Then build your model in AMPL (Use the file Portfolio.mdb) Deliverables Models (Self documenting) Solutions (Self documenting) Due: Beginning of Lecture #7 36