Optimization Linear Programming SumProduct Function SUMPRODUCT a very useful Excel function SUMPRODUCT array1 array2 array3 Array1 array2 array3 are 2 to 30 arrays whose components you want to multiply and then add Remarks The array arguments must have the same dimensions If they do not SUMPRODUCT returns the VALUE error value SUMPRODUCT treats array entries that are not numeric as if they were zeros 2 SUMPRODUCT Arguments must be exactly the same size and shape Example SUMPRODUCT A10 B11 E12 F13 Produces the sum of 4 products A10 E12 A11 E13 B10 F12 B11 F13 3 Optimization Optimization Problems have Decision variables can be varied Objective function what are we optimizing Constraints typically business rules In Excel Changing cells decision variables Target cell contains the objective one to be minimized or maximized Constraints formulas or cells 4 Optimization A feasible solution satisfies all constraints But may not be optimum The feasible region is the set of all feasible An infeasible solution violates at least one of solutions the constraints The optimal solution is the feasible solution that optimizes the objective It is possible that no feasible solution exists 5 Simplex Method An algorithm that works well in solving linear programming problems a set of linear inequalities is the simplex method This is implemented in Excel via the Solver add in included in Excel for free Data Solver Must be turned on File Options Add ins 6 Dessert Example Maggie Stewart loves desserts but due to weight and cholesterol concerns she has decided she must plan her desserts carefully Maggie will allow herself no more then 450 calories and 25 grams of fat in her daily desserts She requires at least 120 grams of desserts a day Each dessert also has a taste index What should her daily dessert plan be to stay within her constraints and maximizes the total taste index of her dessert 7 We elect to model in grams not servings Details arbitrary Snack bars grams of fat Ice cream have a taste index 85 gram weighs 37 grams has 120 calories and 5 has a taste index 95 gram One serving of ice cream is 65 grams has 160 calories and 10 grams of fat 8 Algebraic Model Identify the decision variable write expressions for the total taste index and the constraints in terms of the x s Then add explicit constraints to ensure that the x s are nonnegative Maximize 37 85 x1 65 95 x2 Taste Subject to 120x1 160x2 450 Calories 5x1 10x2 25 Fat daily dose 37x1 65x2 120 x1 x2 0 9 Graphical Solution When there are only two decision variables the problem can be solved graphically To graph this consider the associate equality 120x1 160x2 450 and find where the associated line crosses the axes Graph the constraints on the figure as shown on the next slide To see which feasible point maximizes the objective draw a sequence of lines where for each the objective is a constant The last feasible point that it touches is the optimal point 10 Graphical Solution continued 11 Spreadsheet Model Common elements in all LP spreadsheet models are Inputs all numeric data given in the statement of the problem Blue border Changing cells the values in these cells can be changed to optimize the objective Red border Target objective cell contains the value of the objective Double line black boarder Constraints specified in the Solver dialog box Nonnegativity check an option in a Solver dialog box to indicate nonnegative changing cells 12 Spreadsheet Model continued Three stages of the complete solution 1 Model development stage enter all inputs trial values for the changing cells and formulas relating these in spreadsheet Invoke Solver designate the objective cell changing cells the constraints and selected options and tell Solver to find the optimal solution 2 3 Sensitivity analysis see how the optimal solution changes as the selected inputs vary 13 The Solution First step is to identify appropriate decision variables the appropriate objective the constraints and the relationships between them 14 L4 DessertPlanning xls 15 Developing the Model 1 Inputs Enter all inputs from the statement of the problem in the shaded cells as shown 2 Range Names Create the range names shown in columns F and G 3 Changing Cells Enter any two values for the changing cells in the Dessert plan range Any trial values can be used initially Solver eventually finds the optimal values 16 Developing the Model continued 4 Ingredients consumed To operationalize the calorie and fat constraints we must calculate the amounts consumed by the dessert plan To do this enter the formula SUMPRODUCT B5 C5 Dessert Plan in cell B20 for calories and copy it to cell B21 for fat 17 Developing the Spreadsheet Model continued 5 Grams consumed Similarly we must calculate the total number of grams of dessert consumed daily To do this enter the formula SUMPRODUCT B8 C8 Dessert Plan in cell B25 6 Total taste index To calculate the total taste index enter the formula SUMPRODUCT B12 C12 B8 C8 Dessert Plan in cell B25 18 Experimenting with Possible Solutions The next step is to specify the changing cells the target cell and the constraints in a Solver dialog box and then instruct Solver to find the optimal solution But first take a few guesses in the changing cells Why First to confirm that formulas are working Second this experimentation can help you to develop a better understanding of the model 19 To invoke Excel s Solver select the Data Solver menu item The Solver dialog boxes on the next slides should be Using Solver completed as shown Three important sections The target cell The changing cells Constraints For the dessert plan we can fill these in by typing cell references or we can point click and drag the appropriate ranges 20 Using Solver continued 21 The Solution The solution says that Maggie should consume 1 25 servings of snack bars and 1 875 servings of ice cream per day In this solution the calorie and fat constraints are met exactly We say they are binding The constraint on grams is nonbinding since the number of grams consumed is greater than the number required The difference is called slack 22 Solver Example Use L4 Pony Espresso xls from Bb Pony Expresso Regular Coffee 1 25 Premium Latte 2 00 Premium Mocha 2 25 Under capacity constraints Max cups 500 Max premium 350 Max Mocha 125 How can Pony Espresso maximize its revenue by optimally deciding how many cups to produce for each kinds of coffee 23 Problem setup rewrite the problem in mathematical way Your target maximize revenue
View Full Document
Unlocking...