Network Models Assignment Transportation Intro to Modeling/Excel How the Solver Works Sensitivity Analysis Objective Mini Course on Networks Introduction to modeling In Excel and AMPL Intuitive description of solution approach Intuitive description of sensitivity analysis Intuitive and visual context for covering technical aspects Assignment Model Autopower Europe Manufactures UPS for major installations Four manufacturing plants Leipzig, Germany Nancy, France Liege, Belgium Tilburg, The Netherlands One VP to audit each plant Autopower, Europe Netherlands * Belgium * * Liege France * Miles 0 50 Germany Tilburg 100 Nancy Leipzig Assignment Problem Who’s to visit whom? VP’s expertise and plant’s needs Available time and travel requirements Language abilities ... The Challenge Estimate costs (Done - Thoughts?) One VP to each plant One plant for each VP Minimize cost of assignments 01AssignmentModel.xls Autoppow e r Europe : Assignme nt Mode l Moore et al. pp224 VP Finance (F) Marketing (M) Operations (O) Personnel (P) VP Estimated Assignment Costs Leipzig Nancy Liege Tilburg 1 2 3 4 24 10 21 11 14 22 10 15 15 17 20 19 11 19 14 13 Leipzig 1 Finance (F) Marketing (M) Operations (O) Personnel (P) VPs Assigned VP Finance (F) Marketing (M) Operations (O) Personnel (P) Total Cost Assignme nts Nancy Liege 2 3 0 Leipzig 1 0 0 0 0 0 0 Tilburg 4 0 Cost of Assignments Nancy Liege 2 3 0 0 0 0 0 0 0 0 0 0 Plants Assigned 0 0 0 0 0 Tilburg 4 0 0 0 0 0 Total Cost 0 0 0 0 0 A Challenge Find best assignments Building a Network Model In Excel Tools | Solver... Set Target Cell: $F$28 By Changing Cells: $B$15:$E$18 The Constraints Each VP assigned to one plant $F$15 $F$16 $F$17 $F$18 = = = = 1 1 1 1 Shortcut $F$15:$F$18 = 1 Each plant assigned one VP $B$19 = 1 $C$19 = 1 $D$19 = 1 $E$19 = 1 Shortcut $B$19:$E$19 = 1 What’s Missing Additional Constraints... Non-negativity The variables cannot be negative Handled separately Integrality The variables should have integral values We can ignore these because this is a network model!!! Model Components Set Target Cell: Objective $F$28 The value we want to minimize/maximize Equal to: Min Min for Minimize or Max for Maximize By Changing Cells: Variables or Adjustables $B$15:$E$18 The values we can change to find the answer Subject to the Constraints …. $B$19:$B$18 = 1 $F$15:$F$18 = 1 Excel Model Options Limits Max time: Limits the time allowed for the solution process in seconds Iterations:Limits the number of interim calculations. (More details to come) Precision Controls the precision of solutions. Is 1/3 <= 0.3333? 0.333333? Quality of Solutions Tolerance: For integer problems. Later Convergence: For non-linear problems. Later Review & Terminology Objective: Target Cell Equal to: Max or Min Variables: By Changing Cells Constraints: Constraints LHS: Reference Cell - a function of the variables RHS: Constraint - a constant (ideally) Options: Assume Linear Model Assume Non-negative Solve What do you think? Realistic? Practical? Issues? Questions… First Kind of Network Model Sum across row = Const. Sum down column = Const. Each variable in two constraints: A “row” constraint A “column” constraint Finance (F) Marketing (M) Operations (O) IT (I) Personnel (P) Estimated Assignment Costs Leipzig Nancy Liege Tilburg 1 2 3 4 24 10 21 11 14 22 10 15 15 17 20 19 19 24 15 10 11 19 14 13 VP Leipzig 1 VP Finance (F) Marketing (M) Operations (O) IT (I) Personnel (P) VPs Assigned VP Finance (F) Marketing (M) Operations (O) IT (I) Personnel (P) Total Cost 0 0 0 0 0 0 Leipzig 1 Assignments Nancy Liege 2 3 0 0 0 0 0 0 Tilburg 4 0 0 0 0 0 0 0 0 0 0 0 0 Plants Assigned 0 0 0 0 0 Cost of Assignments Nancy Liege Tilburg 2 3 4 Total Cost 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Influence of Optimization Changes focus of “negotiation” about assignments from emotion and personal preferences to estimation of cost Motor Distribution Netherlands 500 Amsterdam The Hague 800 * * * Antwerp * 700 Belgium Tilburg 500 * Liege Miles 50 400 * * 0 Germany 100 200 Nancy 900 Leipzig Transportation Costs From Origin Amsterdam Antwerp The Hague Leipzig 120 61 102.5 To Destination Nancy Liege 130 41 40 100 90 122 Tilburg 59.5 110 42 Unit transportation costs from harbors to plants Minimize the transportation costs involved in moving the motors from the harbors to the plants A Transportation Model Autopower Transportation Model Unit Cost Leipzig From/To Amsterdam $ 120.0 Antwerp $ 61.0 The Hague $ 102.5 Nancy $ 130.0 $ 40.0 $ 90.0 Liege $ 41.0 $ 100.0 $ 122.0 Tilburg $ 59.5 $ 110.0 $ 42.0 Shipments From/To Amsterdam Antwerp The Hague Total Required Leipzig 400 Nancy 900 Liege 200 Tilburg Total 500 Total Cost From/To Amsterdam Antwerp The Hague Total Leipzig - Nancy - Liege - Tilburg - $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ Total $ $ $ $ - - Available 500 700 800 Challenge Find a best answer Building a Solver Model Tools | Solver… Set Target Cell: The cell holding the value you want to minimize (cost) or maximize (revenue) Equal to: Choose Max to maximize or Min to minimize this By Changing Cells: The cells or variables the model is allowed to adjust Solver Model Cont’d Subject to the Constraints: The constraints that limit the choices of the values of the adjustables. Click on Add Cell Reference is a cell that holds a value calculated from the adjustables Constraint is a cell that holds a value that constraints the Cell Reference. <=, =, => is the sense of the constraint. Choose one. What are the Constraints? Supply Constraints Amsterdam: G9 <= H9 Antwerp: G10 <= H10 The Hague: G11 <= H11 Demand Constraints Leipzig: C12 => C13 Nancy: D12 => D13 Liege: E12 => E13 Tilburg: F12 => F13 G9 is the total volume shipped from Amsterdam Short cut: G9:G11 <= H9:H11 C12 is the total volume shipped to Leipzig Short cut: C12:F12 => C13:F13 The Model What’s Missing? Options How the Solver Works Not magic Quick and intuitive Not comprehensive Basic understanding of tool and terms How the Solver works A “Basic Feasible” solution: This choice of variables admits one and only one answer and the answer is non-negative Netherlands 500 Amsterdam The Hague * * 800 * * Antwerp 700 Belgium Tilburg 500 * Liege 200 Nancy 900 Miles 50 400 * * 0 Germany 100 Leipzig A Basic Feasible Solution Netherlands 500 Amsterdam The Hague 800 Antwerp 700 * 500 * 0 * Belgium * Tilburg 500 200 * Liege 100 200 800 * Nancy 900 Miles 0 50 100 Germany 400 400 * Leipzig More Technical Detail Netherlands 500 Amsterdam The Hague 800 Antwerp 700 * 500 * 0 * Belgium * Tilburg 500 200 * Liege 100 200 800 * Nancy 900 Miles 0 50 100 Germany 400 400 * Leipzig Mathematically* z are the basic variables y are the non-basic variables Write the constraints as Ax = Bz + Ny = b Fix the non-basic variables to y* The unique solution for the basic variables x = B-1(b – Ny*) B must be invertible and so square Question: We have 7 constraints (3 ports, 4 plants) and only 6 basic variables. How so? * For those who care to know More Technical Detail Netherlands 500 Amsterdam The Hague 800 Antwerp 700 * 500 * 0 * Belgium * Tilburg 500 200 * Liege 100 200 800 * Nancy 900 Miles 0 50 100 Germany 400 400 * Leipzig How Solver Works Basic Feasible Solution because it is basic AND the basic variables satisfy the bounds (≥ 0) Netherlands 500 Amsterdam The Hague 800 Antwerp 700 * 500 * 0 * Belgium * Tilburg 500 200 * Liege 100 200 800 * Nancy 900 Miles 0 50 100 Germany 400 400 * Leipzig Simple Improvement Consider sending product from The Hague to Liege Netherlands Amsterdam The Hague * * * Antwerp Germany Tilburg * Belgium * * Liege * Miles 0 50 100 Nancy Leipzig Conserving Flow Amsterdam 500 * The Hague 800 * * Antwerp Tilburg 500 700 * * Liege200 * Nancy Conserving Flow Costs $122 $ 40 $162 Saves $100 $ 90 $190 Net $28 Amsterdam 500 * The Hague 800 * * Antwerp $122 * $100 500 Tilburg * Liege200 $90 Reduced Cost $40 * Nancy How Much Can We Save? Costs $122 $ 40 $162 Current Flows Amsterdam Red flows increase * The Hague Green flows decrease * * Saves Antwerp $100 200 $ 90 $190 How much can we send Tilburg 0700 * Net $28 500 * Liege200 800 to Liege? How much do we save? What’s the new answer? 100 * Nancy New Answer Costs $122 $ 40 $162 Saves $100 $ 90 $190 Net $28 Amsterdam 500 * The Hague 800 * * Antwerp * 0 Tilburg 500 200 * Liege200 600 300 * Nancy The New Answer Netherlands Amsterdam The Hague * Tilburg * Germany * Antwerp * Belgium * * Liege * Miles 0 50 100 Nancy Leipzig The New Answer Netherlands What kind of solution is this? 500 Amsterdam The Hague * 800 * * 500Tilburg 500 200 Antwerp 700 * 300 Liege 200 600 * 50 Nancy 900 Miles 0 Germany 100 400 * Leipzig 400 An Optimal Basic Feasible Solution Netherlands 500 Amsterdam 500 The Hague 800 Antwerp 700 * 300 * * * 700 Tilburg 500 200 100 * Liege 200 200 * Nancy 900 Miles 0 50 Germany 100 400 * Leipzig Summary Solver Finds a basic feasible solution Satisfies all the constraints Using these variables there is just one answer Computes reduced costs of non-basic variables one at a time How would increasing the new variable affect cost? Selects an entering variable Increasing this non-basic variable saves money Computes a leaving variable What basic variable first reaches zero? Repeats Sensitivity Analysis How would the answer change if the data were a little different? Why is this important? Intuitive understanding Price Sensitivity Amsterdam The Hague * Antwerp Tilburg Liege Nancy Leipzig At what unit cost would Antwerp to Tilburg be attractive? Price Sensitivity Amsterdam The Hague $42 * Antwerp Tilburg $110 Liege $40 At what unit cost would Antwerp to Tilburg be attractive? Costs: Leipzig $110 $ 90 $200 $90 Nancy The carrier would have to PAY us $8! Savings: $42 $40 $82 Net $118 Try It! Autopower Transportation Model Unit Cost Leipzig Nancy Liege Tilburg From/To Amsterdam $ 120.0 $ 130.0 $ 41.0 $ 59.5 Antwerp $ 61.0 $ 40.0 $ 100.0 $ 110.0 The Hague $ 102.5 $ 90.0 $ 122.0 $ 42.0 Shipments From/To Amsterdam Antwerp The Hague Total Required Leipzig 400 Nancy 900 Liege 200 Tilburg Total 500 Total Cost From/To Amsterdam Antwerp The Hague Total Leipzig - Nancy - Liege - Tilburg - $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ Total $ $ $ $ - - Available 500 700 800 Reduced Costs are... The reduced cost of a variable is… The rate of change in the objective if we are forced to use some of that variable The reduced costs of basic variables are 0 Price Sensitivity: Basic Variables Amsterdam The Hague * Antwerp Tilburg Leipzig If the unit cost from Amsterdam to Liege increases by $10 does the Nancy answer change? Liege Checking Reduced Costs: Example Amsterdam The Hague $120 * Antwerp $100 $40 Example: Check the reduced cost of Antwerp to Liege Tilburg$102.5 Leipzig $51 = $41 + $10 If the unit cost from Amsterdam to Liege increases by $10 does the Nancy answer change? Liege $90 Check All Reduced Costs Amsterdam The Hague Antwerp Tilburg Liege Nancy Leipzig Why only these two? Value of Price Sensitivity? Resource Sensitivity How would the objective value change if we had more of a resource Tells us the marginal value of that resource If the optimal solution doesn’t use all of the resource, then… Resource Sensitivity Amsterdam 500 The Hague 700 Antwerp 800 401 Tilburg 500 Leipzig 400 Liege 200 What would happen if we needed 1 more Nancy engine in Leipzig? 900 Infeasible Supply Amsterdam 500 Antwerp 700 The Hague 800 Total 2,000 Demand Leipzig Nancy Liege Tilburg Total 400+1 900 200 500 2,000+1 Resource Sensitivity Amsterdam 500 The Hague 700 Antwerp 800 Tilburg 500 Leipzig 400 What would Liege 200 happen to cost if we moved supply for 1 engine from Nancy Amsterdam to 900 Antwerp? Resource Sensitivity Amsterdam -1 The Hague $120 $102.5 Leipzig Tilburg Antwerp +1 $40 What’s the value of Liege supply in Antwerp $90 relative to supply in Amsterdam? Nancy Value of Resource Sensitivity A Special Feature We can eliminate any one of the constraints in this problem without changing the answers! Why? Redundant Constraint Supply Amsterdam 500 Antwerp 700 The Hague 800 Total 2,000 Demand Leipzig Nancy Liege Tilburg Total 400 900 200 500 2,000 Know shipments from Amsterdam Antwerp And they provide... Leipzig Nancy Liege Tilburg 200 600 0 400 That means... We can arbitrarily set the (relative) value of one constraint to 0. (the one we throw away) Set the shadow price or marginal value of supply in Amsterdam to 0, then the shadow price of supply in Antwerp is -$67.5. Why negative? If we had extra supply, where would we want it? Amsterdam or Antwerp? Internally Consistent Given the Shadow Prices Constraint Shadow Price Amsterdam Antwerp -67.5 The Hague -17.5 Leipzig 120 Nancy 107.5 Liege 41 Tilburg 59.5 Example: Antwerp-Tilburg Reduced Cost = Cost - Origin - Dest. 118 = 110 - (-67.5) - 59.5 = 110 + 8 We can calculate the Reduced Costs Edge Amsterdam Leipzig Amsterdam Nancy Amsterdam Liege Amsterdam Tilburg Antwerp Leipzig Antwerp Nancy Antwerp Liege Antwerp Tilburg The Hague Leipzig The Hague Nancy The Hague Liege Value Reduced Cost 300 22.5 200 8.5 700 126.5 118.0 100 200 98.5 Cost 120.0 130.0 41.0 59.5 61.0 40.0 100.0 110.0 102.5 90.0 122.0 Summary Solver can tell us at what price a non-basic (inactive) variable will be attractive through the Reduced Cost. Solver can tell us how changes in the price of a basic variable affect the solution Solver can tell us the value of a resource via the Shadow Price or Marginal Value Sensitivity Info From Solver Sensitivity Report: Price Adjustable Cells Cell $C$9 $D$9 $E$9 $F$9 $C$10 $D$10 $E$10 $F$10 $C$11 $D$11 $E$11 $F$11 Name Amsterdam Leipzig Amsterdam Nancy Amsterdam Liege Amsterdam Tilburg Antwerp Leipzig Antwerp Nancy Antwerp Liege Antwerp Tilburg The Hague Leipzig The Hague Nancy The Hague Liege The Hague Tilburg Final Reduced Objective Value Cost Coefficient 300 120 130 22.5 200 41 59.5 8.5 60.99999999 700 40 126.5 99.99999998 110 118.0 100 102.5 200 90 122 98.5 500 42 Allowable Increase 0 1E+30 98.49999999 1E+30 1E+30 8.499999988 1E+30 1E+30 8.499999988 22.49999998 1E+30 0 Allowable Decrease 17.5 22.49999998 41 0 8.499999988 1E+30 126.5 118 0 8.499999988 98.49999999 59.5 Sensitivity Report: Resource Constraints Cell $G$9 $G$10 $G$11 $C$12 $D$12 $E$12 $F$12 Name Amsterdam Total Antwerp Total The Hague Total Total Leipzig Total Nancy Total Liege Total Tilburg Final Shadow Constraint Allowable Allowable Value Price R.H. Side Increase Decrease 500 500 1E+30 0 700 (67.5) 700 200 0 800 (17.5) 800 300 0 400 120.0 400 0 300 900 107.5 900 0 200 200 41.0 200 0 200 500 59.5 500 0 300 Value If our proposal comes up non-basic, reduced cost tells us how much harder we have to work to make it attractive. If we are unsure of prices, price sensitivity can tell us whether it is worth refining our estimates of the values Marginal values can help us target investments in capacity Caveats Sensitivity Analysis is pretty nerdy stuff Technical difficulties Only meaningful for changes to a single value Only meaningful for small changes Doesn’t work for Integer Programming Can always just change the values and re-solve, but... Bad Example Autopower Transportation Model Unit Cost Leipzig From/To Amsterdam $ 120.0 Antwerp $ The Hague $ 120.0 Shipments From/To Amsterdam Antwerp The Hague Total Required Nancy Liege $ 120.0 $ 120.0 $ $ $ $ 120.0 Leipzig 400 400 400 Total Cost Leipzig From/To Amsterdam $ Antwerp $ The Hague $ Total $ - Nancy 100 800 900 900 $ $ $ $ Nancy - Liege 200 200 200 Liege $ $ $ $ - Tilburg $ $ 120.0 $ 120.0 Tilburg Total 500 500 500 Tilburg $ $ $ $ - Total $ $ $ $ Available 500 500 700 700 800 800 - - Sensitivity Moving one unit from Liege to Tilburg should save $120 Constraints Cell $C$12 $D$12 $E$12 $F$12 $G$9 $G$10 $G$11 Name Total Leipzig Total Nancy Total Liege Total Tilburg Amsterdam Total Antwerp Total The Hague Total Final Shadow Constraint Allowable Allowable Value Price R.H. Side Increase Decrease 400 120 400 0 0 900 120 900 0 0 200 120 200 0 0 0 500 500 500 500 500 1E+30 0 700 (120) 700 0 0 800 (120) 800 0 0 Solver says the price is not good for 1 unit Try It! Autopower Transportation Model Unit Cost Leipzig From/To Amsterdam $ 120.0 $ Antwerp The Hague $ 120.0 Shipments From/To Amsterdam Antwerp The Hague Total Required Nancy Liege $ 120.0 $ 120.0 $ $ $ $ 120.0 Leipzig 400 400 400 Total Cost Leipzig From/To Amsterdam $ Antwerp $ The Hague $ Total $ - Nancy 100 800 900 900 $ $ $ $ Nancy - Liege 200 200 200 Liege $ $ $ $ - Tilburg $ $ 120.0 $ 120.0 Tilburg Total 500 500 500 Tilburg $ $ $ $ - Total $ $ $ $ Available 500 500 700 700 800 800 - -