FIT3158 Lecture 2

Modelling and Solving LP Problems in a Spreadsheet The steps in implementing an Linear Programming (LP) Model in a spreadsheet Goals for good spreadsheet design Some examples in building spreadsheet models 3

The Steps in Implementing an LP Model in a Spreadsheet 1. Organize the data for the model on the spreadsheet. 2. Reserve separate cells in the spreadsheet for each decision variable in the model. 3. Create a formula in a cell in the spreadsheet that corresponds to the objective function. 4. For each constraint, create a formula in a separate cell in the spreadsheet that corresponds to the left-hand side (LHS) of the constraint. 6

SumProduct • Is like dot product or scalar product of two vectors • Take two vectors or rows of the same length, multiply the matching pairs, then sum these products • E.g., – (1, 2, 3) . (1, 1, 1) = 1 + 2 + 3 = 6 – (1, 0, 2, 0) . (0, 3, 0, 4) = 0 + 0 + 0 + 0 = 0 – (3/5, 4/5) . (-4/5, 3/5) = -12/25 + 12/25 = 0 – etc. As a digression, two vectors at right angles (or perpendicular) to one another will have a dot product of 0. You could try this on graph paper. 9

How the Solver views the model ▪ Data Tab (Analyze Group)  Solver – Set Objective (objective function) – Min or Max – Changing cells (decision variables), – Constraint cells: LHS and RHS, – Non-negativity – Assume linear model 12

15 If you can’t find Excel Solver, then ... ▪ Click the ‘File’ Tab and select ‘Options’ ▪ Click Add-ins in the left pane, then click the arrow next to the Manage box and click Excel Add-ins ▪ Click the Go button to open the Add-ins dialog box. ▪ Click the Solver Add-ins check box and then click the OK button ▪ Solver will be added to the ‘Data’ tab 🡪 ‘Analyze’ 15

Spreadsheet Design Guidelines - II ▪ The English-reading eye scans left to right, top to bottom. ▪ Use colour, shading, borders and protection to distinguish changeable parameters from other model elements. ▪ Use text boxes and cell notes to document various elements of the model. 18

Defining the Objective Function Minimize the total cost of filling the order. MIN: 50M 1 + 83M 2 + 130M 3 + 61B 1 + 97B 2 + 145B 3 21

Defining the Constraints ▪ Demand Constraints M 1 + B 1 = 3,000 } model 1 M 2 + B 2 = 2,000 } model 2 M 3 + B 3 = 900 } model 3 ▪ Resource Constraints 2M 1 + 1.5M 2 + 3M 3 <= 10,000 } wiring 1M 1 + 2.0M 2 + 1M 3 <= 5,000 } harnessing ▪ Non-negativity Conditions M 1 , M 2 , M 3 , B 1 , B 2 , B 3 >= 0 22

Implementing the Model See file Lecture2-2.xlsm 23

Solver Setup 24

The Solution: 25

An Investment Problem: Retirement Planning Services, Inc. ▪ A client wishes to invest $750,000 in the following bonds. Years to Company Return Maturity Rating Acme Chemical 8.65% 11 1-Excellent DynaStar 9.50% 10 3-Good Eagle Vision 10.00% 6 4-Fair Micro Modeling 8.75% 10 1-Excellent OptiPro 9.25% 7 3-Good Sabre Systems 9.00% 13 2-Very Good 26

Investment Restrictions ▪ No more than 25% can be invested in any single company. ▪ At least 50% should be invested in long-term bonds (maturing in 10+ years). ▪ No more than 35% can be invested in DynaStar, Eagle Vision, and OptiPro - as they are considered risky. 27

Defining the Decision Variables X 1 = amount of money to invest in Acme Chemical X 2 = amount of money to invest in DynaStar X 3 = amount of money to invest in Eagle Vision X 4 = amount of money to invest in MicroModeling X 5 = amount of money to invest in OptiPro X 6 = amount of money to invest in Sabre Systems 28

Defining the Objective Function Maximize the total annual investment return: MAX: .0865X 1 + .095X 2 + .10X 3 + .0875X 4 + .0925X 5 + .09X 6 29

Defining the Constraints ▪ Total amount is invested X 1 + X 2 + X 3 + X 4 + X 5 + X 6 = 750,000 ▪ No more than 25% in any one investment X i <= 187,500, for all i ▪ 50% long term investment restriction. X 1 + X 2 + X 4 + X 6 >= 375,000 ▪ 35% Restriction on DynaStar, Eagle Vision, and OptiPro. X 2 + X 3 + X 5 <= 262,500 ▪ Non-negativity conditions X i >= 0 for all i 30

Implementing the Model See file Lecture2-3.xlsm 31

Implementing the Model Objective function: =SUMPRODUCT(E6:E11,$C$6:$C$11) Total investment constraint: =SUM(C6:C11)=C13 LT investment constraint: =SUMPRODUCT(G6:G11,$C$6:$C$11)>=G13 Risky constraint: =SUMPRODUCT(I6:I11,$C$6:$C$11) <= I13 32 DD1

Slide 32 DD1 David Dowe, 28/07/2023

Solver settings … and the solution: 33

A Blending Problem: The Agri-Pro Company ▪ Agri-Pro has received an order for 8,000 pounds of chicken feed to be mixed from the following feeds. Nutrient Feed 1 Feed 2 Feed 3 Feed 4 Corn 30% 5% 20% 10% Grain 10% 30% 15% 10% Minerals 20% 20% 20% 30% Cost per pound $0.25 $0.30 $0.32 $0.15 Percent of Nutrient in ▪ The order must contain at least 20% corn, 15% grain, and 15% minerals. 34

Defining the Decision Variables X 1 = pounds of feed 1 to use in the mix X 2 = pounds of feed 2 to use in the mix X 3 = pounds of feed 3 to use in the mix X 4 = pounds of feed 4 to use in the mix 35

Defining the Objective Function Minimize the total cost of filling the order. MIN: 0.25X 1 + 0.30X 2 + 0.32X 3 + 0.15X 4 36

Defining the Constraints ▪ Produce 8,000 pounds of feed X 1 + X 2 + X 3 + X 4 = 8,000 ▪ Mix consists of at least 20% corn (0.3X 1 + 0.05X 2 + 0.2X 3 + 0.1X 4 )/8000 >= 0.2 ▪ Mix consists of at least 15% grain (0.1X 1 + 0.3X 2 + 0.15X 3 + 0.1X 4 )/8000 >= 0.15 ▪ Mix consists of at least 15% minerals (0.2X 1 + 0.2X 2 + 0.2X 3 + 0.3X 4 )/8000 >= 0.15 ▪ Non-negativity conditions X 1 , X 2 , X 3 , X 4 >= 0 37

A Comment About Scaling ▪ Notice the coefficient for X 2 in the ‘corn’ constraint is 0.05/8000 = 0.00000625 ▪ As Solver runs, intermediate calculations are made that make coefficients larger or smaller. ▪ Storage problems may force the computer to use approximations of the actual numbers. ▪ Such ‘scaling’ problems sometimes prevents (MicroSoft Excel) Solver from being able to solve the problem accurately. ▪ Many – or most - problems can be formulated in a way to minimize scaling errors ... So, we now re-formulate the problem 38

Re-Defining the Decision Variables X 1 = thousands of pounds of feed 1 to use in the mix X 2 = thousands of pounds of feed 2 to use in the mix X 3 = thousands of pounds of feed 3 to use in the mix X 4 = thousands of pounds of feed 4 to use in the mix 39

Re-Defining the Objective Function Minimize the total cost of filling the order. MIN: 250X 1 + 300X 2 + 320X 3 + 150X 4 40

Re-Defining the Constraints ▪ Produce 8,000 pounds of feed X 1 + X 2 + X 3 + X 4 = 8 ▪ Mix consists of at least 20% corn (0.3X 1 + 0.05X 2 + 0.2X 3 + 0.1X 4 )/8 >= 0.2 ▪ Mix consists of at least 15% grain (0.1X 1 + 0.3X 2 + 0.15X 3 + 0.1X 4 )/8 >= 0.15 ▪ Mix consists of at least 15% minerals (0.2X 1 + 0.2X 2 + 0.2X 3 + 0.3X 4 )/8 >= 0.15 ▪ Non-negativity conditions X 1 , X 2 , X 3 , X 4 >= 0 41

Scaling: Before and After ▪ Before: – Largest constraint coefficient was 8,000 – Smallest constraint coefficient was 0.05/8 = 0.00000625. ▪ After: – Largest constraint coefficient is 8 – Smallest constraint coefficient is 0.05/8 = 0.00625. ▪ The problem is now more evenly scaled! 42

Implementing the Model See file Lecture2-4.xlsm 43

Solver settings … and the solution: 44

A Multi-Period Cash Flow Problem: The Taco-Viva Sinking Fund - I ▪ Taco-Viva needs a sinking fund to pay $800,000 in building costs for a new restaurant in the next 6 months. ▪ Payments of $250,000 are due at the end of months 2 and 4, and a final payment of $300,000 is due at the end of month 6. ▪ The following investments may be used. Investment Available in Month Months to Maturity Yield at Maturity A 1, 2, 3, 4, 5, 6 1 1.8% B 1, 3, 5 2 3.5% C 1, 4 3 5.8% D 1 6 11.0% 45

Summary of Possible Cash Flows Investment 1 2 3 4 5 6 7 A 1 -1 1.018 B 1 -1 < _____ > 1.035 C 1 -1 < _____ >< _____ > 1.058 D 1 -1 < _____ > < _____ > < _____ > < _____ > < _____ > 1.11 A 2 -1 1.018 A 3 -1 1.018 B 3 -1 < _____ > 1.035 A 4 -1 1.018 C 4 -1 < _____ > < _____ > 1.058 A 5 -1 1.018 B 5 -1 < _____ > 1.035 A 6 -1 1.018 Req’d Payments (in $1,000s) $0 $0 $250 $0 $250 $0 $300 Cash Inflow/Outflow at the Beginning of Month 46

Defining the Decision Variables A i = amount (in $1,000s) placed in investment A at the beginning of month i =1, 2, 3, 4, 5, 6 B i = amount (in $1,000s) placed in investment B at the beginning of month i =1, 3, 5 C i = amount (in $1,000s) placed in investment C at the beginning of month i =1, 4 D i = amount (in $1,000s) placed in investment D at the beginning of month i =1 47

Defining the Objective Function Minimize the total cash invested in month 1. MIN: A 1 + B 1 + C 1 + D 1 48

Defining the Constraints ▪ Cash Flow Constraints 1.018A 1 – 1A 2 = 0 } month 2 1.035B 1 + 1.018A 2 – 1A 3 – 1B 3 = 250 } month 3 1.058C 1 + 1.018A 3 – 1A 4 – 1C 4 = 0 } month 4 1.035B 3 + 1.018A 4 – 1A 5 – 1B 5 = 250 } month 5 1.018A 5 –1A 6 = 0 } month 6 1.11D 1 + 1.058C 4 + 1.035B 5 + 1.018A 6 = 300 } month 7 ▪ Non-negativity Conditions A i , B i , C i , D i >= 0, for all i 49

Implementing the Model See file Lecture2-5.xlsm 50

Solver settings … and the solution: 51

Re-capping ▪ Recall Week 0, Week 1 (Introduction: policies, procedures, Assessment, etc.) ▪ Week 1 (Lecture or) Seminar Part 1: Introduction to Modelling and Decision Analysis and Part 2: Introduction to Optimisation and Linear Programming This week: ▪ Modelling and Solving Linear Programming (LP) Problems in a Spreadsheet – goals for good spreadsheet design; and then – we started out with 2 variables, 2 non-negativity constraints, and 3 other constraints – we got as far as 12 variables, 12 non-negativity constraints, and 6 other constraints 52

End of Seminar 2 (or Lecture 2) from Week 1 Introduction, Learning Outcomes and from FIT3158 Unit Handbook 2023: “develop interactive decision models for business analysis and business process improvements” and “communicate the results of model-based decision analysis” References : Ragsdale, C. T. (2021). Spreadsheet Modeling & Decision Analysis: A Practical Introduction to Business Analytics (9e) Cengage Learning: Chapter 3 (similarly for Ragsdale (2017, 8 th edn)) 53

Applied class (or Tutorial) 1 this week: ▪ LP: Graphical Method on two decision variables – Maximisation – Minimisation Multi-variable problem formulation 54

Homework ▪ Recall week 0 and week 1 Introduction. ▪ Go through today’s examples ▪ Make sure you understand each problem including formulation and MicroSoft Excel setup. ▪ Refer to Lecture 2 Excel Model files in Moodle. ▪ Revise Ragsdale Chapter 3. 55 55

Next week ▪ Sensitivity analysis 56 🖙 Readings for next week’s Seminar/Lecture: Ragsdale, C. T. (2021). Spreadsheet Modeling & Decision Analysis: A Practical Introduction to Business Analytics (9e) Cengage Learning: Chapter 4 🖙 (and similarly for Ragsdale (8 th edn, 2017)) 56