Chapter 2 Section 1

Excel Companion Chapter 2
Chapter 2 Index
EC_2		LINEAR OPTIMIZATION
	*Vitamins.xls*	Two variable LP Minimization
	*Machines.xls*	Two variable LP Maximization
	*Rlestate.xls*	Integer Programming
		Return to Table of Contents

Linear Programming			*Vitamins.xls*

Solving linear programming problems involves determining maximum or minimum value(s) of a linear objective function expressed in two or more decision variables subject to certain constraints. All of the decision variables must be non-negative and each constraint must be either a linear inequality or a linear equation.

Open the workbook Vitamins.xls to the sheet Graph 1.

SITUATION: A special diet utilizes food X and food Y to supply the following minimum daily requirements: 45 milligrams of vitamin A, 64 milligrams of vitamin B, and 45 milligrams of vitamin C. Each unit of food X costs $0.35 and supplies 15 milligram of vitamin A, 8 milligrams of vitamin B, and 5 milligrams of vitamin C. Each unit of food Y costs $0.45 and supplies 3 milligrams of vitamin A, 8 milligrams of vitamin B, and 9 milligrams of vitamin C. The goal is to determine the mixture of food X and food Y that minimizes the total cost and to calculate that minimum cost.

Vitamins.xls contains a formulation of this two variable LP problem and illustrates two different solution methods. The graphical method, shown in Graph 1, is based on the fact that optimal solutions to LP problems are found at a corner point or on an edge that connects corner points. The second method, illustrated in Solver 1, finds an optimal solution by a very powerful numerical algorithm called the simplex method.

Appendix B, entitled Linear Optimization Problems --- Using Excel and Excel Solver, contains detailed instructions on preparing worksheets for the Solver Add-in. Appendix B also shows the dialog boxes that appear in the process of directing Solver to apply the simplex method. We strongly recommend that you work through this appendix step by step.

Vitamins.xls - Graph 1

For the vitamins problem the objective function is of the form Z = ax + by where a is the unit cost for Food X and b is the unit cost for Food Y. By changing a and b we can change the cost function which could lead to a different optimal solution. The values of a and b in Vitamins.xls are initially set to 0 .35 and 0.45 respectively.

Since there is no "shading" or "fill" tool in Excel, you must be able to the correctly identify the feasible region from the Excel graph by visualizing those points in the first quadrant that satisfy all of the constraints. Each of the vitamin constraints in the Vitamins problem defines a region on or above a boundary line.

The actual feasible region is unbounded. In the figure on the right, the feasible region is the un-shaded part. The four corner points P, Q, R, and S are listed in counter-clockwise order:

P (0.00, 15.00), Q (1.75, 6.25), R (6.75, 1.25), and S (9.00, 0.00).

It may be necessary to use zoom control in order to see each of the corner points clearly. The square dots correspond to a $4.00 cost. The dotted line with the double headed arrows corresponds to a line with an approximate $6.00 cost. All cost lines, called iso-value lines or level curves, are parallel to each other. The slope of an iso-cost line is determined by the coefficients a and b of the cost function. Observe that the associated costs decrease as the iso-cost lines get closer to the origin (0,0). Click on the middle part of the cost line with the arrows and slowly move it toward the origin. You should observe that the last iso-value line in contact with the feasible region contains the corner point R(6.75, 1.25). This point corresponds to a minimum cost. We can verify this observation by evaluating all four corner points in the objective function.

QUESTIONS:

Suppose that you have $3.50 to spend and you are not concerned about minimizing cost. One way that you can spend $3.50 and satisfy the minimum vitamin requirements is to buy 4 units of Food X and 4 2/3 units of Food Y. Name three other ways that you could spend exactly $3.50.

Food X

Food Y

With $2.50 we could buy 2 units of Food X and 4 units of Food Y. Explain precisely why (2,4) could not be a solution to the original optimization problem.

If the objective function were changed to Z = 0.50*x + 0.50*y then all iso-cost lines will have slope equal to -1.

[This new family of iso-cost lines will not be parallel to the dotted line with the double arrows shown in graph 1]

a) Verify that the pink corner point (1.75, 6.25) and the gold corner point (6.75,1.25) produce the same minimum cost.

b) Name two other points on the segment connecting the points (1.75, 6.25) and (6.75,1.25).

x	y

c) What are the values of Z for the points you found in question b.

We will now investigate a non-graphical technique based on the simplex method. This method is widely-used for solving multi-variable LP problems. Appendix B has detailed illustrations of the steps involved in using the Solver Add-in with LP problems. Guidelines for solving the formulated Vitamin problem with Solver are outlined below in a fairly compact form.

The goal of steps 1 -5 is the preparation of the worksheet as shown below:

1.	Reserve separate cells in the spreadsheet to represent the decision variables ( Solver refers to them as the "changing cells"). We have used cells D11:E11 for the values of Food X and Food Y in the Vitamins example. These cells are shaded in blue.
2.	Place descriptive labels in appropriate rows and columns to identify the key data elements. Place the decision variable labels "Food X" and "Food Y" in D10:E10 and the constraint labels in C13:C15.
*3.	Choose the cell, F12 to contain the formula for the objective function as the sum of the products D12 times D11 plus E12 times E11. Solver calls this the "target cell".
*4.	Create formulas in cells F13, F14, and F15 for the Left Hand Sides (LHS) of the vitamin constraints. * A very efficient way to accomplish both steps 3 and 4 for the Vitamin problem is to use Excel’s sumproduct function as follows: Enter the formula = SUMPRODUCT(D12:E12,$D$11:$E$11) in cell F12 then fill this formula down through cells F13, F14, and F15.
5.	Enter values for the Right Hand Sides (RHS) of each of the constraints. For Vitamins these boundary values are entered in cells H13:H15. The direction signs are in column G and are placed there as only as reminders. Once all the labels, values, and formulas have been correctly entered, the spreadsheet is now ready for Solver.
6.	Invoke Solver from the Tools Menu. After a few seconds you should see the Solver Parameters dialog box. When this dialog box is completed it should look like the following:

To complete a blank Solver Parameters dialog box

identify F12 as the target cell
click the radio button for Min
identify D11:E11 as the Changing Cells
click the Add button and complete the Add Constraint dialog box as follows:

identify F13:F15 as the LHS of the vitamin constraints
click the down arrow and select >=
identify H13:H15.as the RHS of the vitamin constraints
add the non-negativity constraint by entering D11:E11 as the LHS

click the down arrow and select >=
enter 0 as the RHS

7.	Under Options make sure that you check Assume Linear Model. This instruction essentially directs Excel to check for the conditions of a linear model and to apply the simplex method. After you complete all of these dialog boxes you should review the model and correct any errors.
8.	Click the Solve button. If Solver finds an optimal solution it will present another dialog box that enables you to keep the solution on the spreadsheet and to generate one or more reports. These reports provide additional information about the solution. [Keep in mind that not all LP problems have solutions and for those that do, the solution is not always unique].

Once you have completed all these steps correctly you can generate an Answer Report similar to sheet 2_1_4. If the names in the Answer Report generated by Solver are not as clear and concise as you wish then you can easily edit the text. The report in sheet 2_1_4 shows that a minimum cost of 2.925 dollars, rounded to 2.93, is obtained when the amount of Food X is 6.75 units and the amount of Food Y is 1.25 units.

Vitamins.xls - Answer Report 1

An LP problem may have more than one optimal solution. For two-variable problems solved by the graphical method, alternative solutions are easy to detect. If Solver is used, however, the Answer Report, by itself, will not enable you to tell whether or not the stated solution is unique.

QUESTIONS:

4.	If the cost function is changed to Z = 1.00x + 0.80y then all iso-cost lines will have slope equal to -1.00/0.80 = -5/4= -1.25. One of these lines passes through (8,0) and ( 0,10) and is associated with a cost of $8.00.
	a) How can you tell that $8.00 could not be the minimum cost?
	b) What is the minimum cost?
5.	Explore Graph 2 in the Vitamins.xls workbook which features randomly generated objective functions and constraints.
	Each time you press the <F9> key, a new problem is generated. Write the objective function and the constraints for the first problem you generate that gives a minimum cost above $8.00.

Enter your name here:

first name last name

Return to Table of Contents

Return to Chapter 2 Index