Report

Excel Tools: Solver and Goal Seek A Brown Bag discussion for N-81 26 Sept 2012 THIS PRESENTATION IS UNCLASSIFIED Purpose • This Talk promises to: – (re)introduce some powerful tools in Excel • Optimization – centric functions • Goal seek • Solver – To show practical examples of how they may be used • This Talk will not: – Be a course in Linear Optimization References • Albright, S. C. (2007) VBA for modelers Thompson – Brookstone. • Walkenbach, J Microsoft Excel 2010 Bible Wiley. • Ragsdale, C. Decision Analysis with Spreadsheets • Balakrishnan, N. Managerial Decision Modeling with Spreadsheets • Frontline Systems: www.solver.com Block 0: Goal Seek • Goal Seek: A Line Search algorithm that iteratively seeks to find the (User set) goal value. – Goods: Robust, fast, and easy to use. Can work on non-linear problems – Bads: Goal Seek is not an optimization algorithm, but rather a regulated form of iterated guessing. Sometimes doesn’t work. Can miss multiple/optimal solutions – Others: Will only take literals as the goal value. – For Nerds: Is it Binary or Golden Section? Microsoft doesn’t specify in documentation The important thing to know about Goal Seek: • G/S simply automates the ‘trial – and – error’ approach to problem solving. • In strict terms, Goal Seek is Guessing. Invoking Goal Seek • Data -> What If Analysis -> Goal Seek Set Cell: The ‘target’ The desired value of the Set Cell. Must be a ‘literal’. “By Changing” Goal Seek Example • Given a maintenance department with two ‘shops’, if aircraft break at a rate of 1 per day, at what rate does each shop need to fix planes in order to have 80% chance that at any given moment there are no down planes? • This is a queuing problem Solving • The hard way: Break out your stochs textbook, and try to formulate this as a Markov Chain • The Easy way: Q.xls and Goal Seek! Goal Seek Example Goal Seek Example II: Military Application • Recall Lanchester’s Aimed Fire model of combat from our last lunchtime series: dB R dt dB B dt • Given .05; B 100; R 100 , find the value of that results in 70 blue survivors when the Red side is eliminated. 0 0 Approach 1 TOO EASY! Just solve: 1 B (t ) B0 R0 2 B 1 R (t ) R0 B0 2 R R B e e t t BR BR 1 B0 R0 2 B 1 R0 B0 2 R R B e e t BR t BR Approach II • Use Goal Seek! Summary • Goal seek is ideal in situations where you want answers, not proofs! • DISCLAIMERS: – You will not know if there are multiple solutions – You will not get any sensitivity analysis SOME USEFUL EXCEL FUNCTIONS Named Cells • Sometimes, you want to use cells, but D$3$ can become cumbersome to type. • Also, you might want to be able to understand the formulae without an interpreter. • Naming Cells is very handy for this! • How to? – Use the Name box! Naming Cells Name Box Which is easier to understand? Formula Auditing • Sometimes, you want to know what the ‘goezintas’ for a particular answer are. There’s a great function for this: Formula Auditing – Formulas -> Formula Auditing Example I cannot overstress how useful this is for reviewing someone else’s spreadsheet! SUMPRODUCT() • Sometimes you have data in two columns, and you wish to find the total the product of the two sides. – Such as finding the expectation and variance of a discrete variable manually – Tallying up costs by aircraft type • Excel has a special function for this: SUMPRODUCT() SUMPRODUCT() II • Takes two arrays, X and Y as inputs – Must be equally sized • Returns a single number, which is: i X i Yi • In English: Multiply all these by all those and add up • Very useful for the objective function of a LP. SUMXMY2() • Sometimes you want to find the squared Euclidian distance between two points or sets of points. – Such as distance between ships in the example we will work later – Or OLS (Ordinary Least Squares) • SUMXMY2: – Why did they name it that? I don’t know! – SUM of X Minus Y Squared (2) SUMXMY2() II • Takes two arrays, X and Y and returns the sum of square differences (i.e. squared Euclidian measure) (X i i Yi ) 2 Block 1: Solver • What is it: an optimization package. Can handle LP, MIP, NLP. It’s not anyone’s favorite package, but it’s the one we have. • Goods: Graphical interface with spreadsheets can make formulation more visually appealing • Bads: There are some problems where it fails to converge. Limits on number of variables, and number of Integer/Binary variables • Others: Some important things ‘under the hood’ that should be considered (upcoming slides) • For Nerds: I’ve never used Evolutionary Solver mode. Invoking Solver • To use Solver, it must be installed – Why? Because Bill Gates Hates you, that’s why! • To use Solver in VBA, it must be installed there as well – Why? See above! Installing Solver – Main Body Installing Solver- VBA Block II: How to use Solver Solver Differences - 2010 • Excel 2010 has a different (and not better) interface. • Report options are now available after the solution is complete – Used to be an option in the dialog box Report Options A Toy Force Structure Problem • You need to put together a force that is able to carry 15 helicopters, using a mix of ships at a minimum cost. • Data Given: Ship Type Aircraft per Ship Cost Per Steaming Day DDG 1 1000 FFG 2 1000 CG 2 3000 LHA 8 5000 LCS 1 1000 Use at least 1 LHA, 2 LCS, and no more than 4 of any type of ship. Switch to Spreadsheet Some Pointers • I like to use color: – Objective function GREEN – Constraints RED – Variables BLUE • This makes it easy to see ‘what’s what Sensitivity Report Microsoft Excel 14.0 Sensitivity Report Worksheet: [Book1]Sheet1 Report Created: 9/23/2012 7:52:46 PM Variable Cells Cell $K$8 $K$9 $K$10 $K$11 $K$12 Name Number Ships Total A/C Number Ships Needed Number Ships Number Ships Number Ships Final Reduced Objective Allowable Allowable Value Cost Coefficient Increase Decrease 0 500 1000 1E+30 500 2.5 0 1000 250 1000 0 2000 3000 1E+30 2000 1 1000 5000 1E+30 1000 2 500 1000 1E+30 500 Constraints Final Shadow Constraint Allowable Allowable Cell Name Value Price R.H. Side Increase Decrease $E$9 Total A/C Cost Per Steaming Day 15 500 15 3 5 Okay, well, that answer was great… (but what does .5 ships mean?) • In order to go forward, we need to solve as a Mixed Integer Program. • In Excel, we add another constraint… … and a whole universe of complexity WARNING! It is NOT GENERALLY true that the solution to a problem with Integer constraints is ‘close’ to the associated Linear Program! Solver – Pro Tips • Frontline solvers claims that the limit on variables is 200, – But it might crash much, much sooner! • Solutions: – A. Upgrade solver – B. Use MATLAB solver – C. Ask us (NPS) for help. Solver: what can go wrong • Here’s something that can go wrong: – Max X^2, unconstrained, with an incumbent solution of zero. Practical Example: Optimum placement of Ships • http://puzzlor.editme.com/Relief-Mission Problem Description • Given the map shown and the ability to place two ships, what is the optimum placement to minimize the maximum distance to a target? • Real-world applications: – Ballistic Missile Defense – Medical Facility Placement – Logistics Hubs – Others? First, an easier Problem • What if there was only one ship to be placed? m in z X ,Y , Z s .t . Z ( X x i ) (Y -y i ) 2 0 X 10 0 Y 10 2 i Now, the Placement Problem • This is actually two problems – If we knew which ship was associated with each Target , this would be easy – If we knew where the two ships were stationed, it would be easy to know which Target to associate with them • We have to figure both out, simultaneously • This is a hard problem – but one that is probably worth the effort Formulation m in Z X ,Y , Z , S s .t . Z ( X 1 x i ) (Y1 y i ) (1 S ) * B igP en i Z ( X 2 x i ) (Y 2 y i ) ( S ) * B igP e n i 2 2 S [0,1] 2 2 Why does this work? • Because for at one and only one of the constraints, the RHS is negative, and therefore irrelevant. – Here we’re using constraints to shape the objective function! • While combining the constraints into an expression like S * ( X x ) (1 S ) * ( X x ) looks good, it is highly non-linear and may cause solver to crash 1 i 2 i Summary • Today we talked about: – Excel Practice, generally – Goal Seek: A useful way for getting answers but Proofs – Excel Functions: • Named cells are infinitely better than R$2$:D$2$, etc. • SUMPRODUCT() • SUMXMY2() – Solver – Practical Applications. Final Note: Presentation Don’ts • BEWARE what MS office does when you copy and paste! – If you copy and paste a graph from a spreadsheet, you might be pasting the entire spreadsheet. This may be handing someone else your entire analysis. – Solution: Be sure to paste graphs as pictures • BEWARE what MS office does when you use track changes. – You might leave them in. – Solution: Copy your text, paste to clipboard, then copy and paste back to word • Solution to both problems: convert to .pdf before distribution Point of Contact • CDR Harrison Schramm [email protected] [email protected] 831.656.2358 • After April, 2013 – BE922