LINEAR OPTIMIZATION PROBLEMS USING EXCEL SOLVER

Overview of Working with Microsoft Excel Solver (taken from MS Office documentation)

Microsoft Excel Solver is a powerful optimization and resource allocation tool. It can help you to uncover the best uses of scarce resources so that desired goals such as profit can be maximized, or undesired goals such as cost can be minimized. Microsoft Excel Solver answers questions such as:

• What product price or promotion mix will maximize profit?
• How can I live within the budget?
• How fast can we grow without running out of cash?

Instead of guessing over and over, you can use Microsoft Excel Solver to find the best answer. When you solve a problem using Solver, you:

• Specify the target cell that you want to minimize, maximize, or set to a certain value.
• Specify the changing cells that you want to be adjusted until a solution is found. You can specify up to 200 changing cells.
• Specify constraint cells that must fall within certain limits or satisfy target values. You can specify up to 500 constraints, 2 for each changing cell plus 100 additional constraints, representing a total
  of no more than 1000 cells in a problem.

After solving the problem, you can create three types of reports that summarize the results of a successful solution process.

When you save a workbook, the last selections made in the Solver Parameters dialog box are retained for each worksheet on which you have defined a Solver problem. However, you can define more than one problem for a worksheet by saving them individually using the Save Model button in the Solver Options dialog box.

You can then use the Load Model button to open a saved problem model.

You can also save the Solver settings for the problem as a scenario using the Scenario Manager.

See Also

Help

Adding, changing, or deleting constraints in Solver
Adjusting the Solver settings
Creating a report using Solver
Defining a problem using Solver
Saving and loading a problem model using Solver
Scenarios Command (Tools Menu)
Solver Command (Tools Menu)
Solving a problem using Solver
The Difference Between Linear and Nonlinear Problems

User's Guide

Chapter 29, "Using Solver to Analyze Multiple-Variable Problem

Frontline Systems Inc. is the spreadhseet solver company that created the Solver Add-in for Microsoft Excel. Their home page http://www.frontsys.com contains announcements of new products and can lead you to technical information and resources including help with Solver, a tutorial on optimization, and a private Web for Solver users.

In order to use Excel as an electronic assistant for solving Linear Programming problems you must become familiar with (1) the basic steps involved in building a spreadsheet model and (2) the sequence of commands for using the Solver Add-In tool. Solver must be installed on the network or on your hard drive. Ask for assistance if you discover that Solver is not available from the main menu under Tools.

An efficient way to learn to use Solver is to work through examples. We start with a simple two-variable LP problem and illustrate:

• How to enter the relevant data, formulas, and cell names into an EXCEL worksheet.
• How to use Solver to enter the relevant parameters and search for an optimal solution.
• How to make modifications to the model, including the introduction of new decision variables and additional constraints.

SITUATION:

Ace Tire Company manufactures two types of tires: Model P (the premium) and Model R (the regular). Model P sells for $95 per tire and costs $85 per tire to make, whereas Model R sells for $50 per tire and costs $42 per tire to make. To make one Model P tire, it requires two hours on Machine A and four hours on Machine B. On the other hand, to make one Model R tire, it takes nine hours on Machine A and three hours on Machine B. Production scheduling indicates that during the coming week Machine A will be available for at most 36 hours and Machine B for at most 42 hours. How many of each tire should the company make in the coming week in order to maximize its profit? What is this maximum profit?

 

The two decision variables in this model are the number of premium tires, x, and the number of regular tires, y. The objective is to find an optimal weekly production plan. That is, to determine the number of each type of tire to produce each week in order to maximize the total weekly profit. The formulation for this LP problem is given below:

Maximize Profit = 10x + 8y subject to constraints (1) - (4)

To prepare an Excel model for Solver, start by entering the relevant labels as shown below:

• Type the labels Premium in cell B1 and Regular in cell C1. Cells B2 and C2 will contain the decision variables.
  
• Type the label Bounds in cell E1.
  
• Type the labels Decision Variables in cell A2 and Profit Function in cell A3.
  
• Type labels Machine A in cell A4 and Machine B in cell A5. Rows 4 and 5 will contain the constraint information.

Associate cells B2 and C2 (now empty) with the decision variables whose names are "Premium" and "Regular". In Figure B_1 these two cells have been given borders and a very light shaded background simply to remind you that they contain the values of the decision variables, x and y. Each of the formulas entered in column D contains a reference to B2 and to C2. Columns B and C also contain important coefficients related to the profit function (row 3) and to the utilization of each type of machine (rows 4 and 5). When Solver goes to work, the values in these "target cells", B2 and C2, are adjusted as the software tool searches for an optimal solution. In this example, an optimal solution means "the maximum possible profit". The cell that will contain the optimal value of the objective function is referred to as the "target cell". In Figure B_1 this target cell is shaded in gray for identification purposes only. When you build your spreadsheet models, no shading will be required.

Figure B_1

Notice that the formula for the objective function and for the LHS of the constraints for machine A and machine B all contain references to the decision variables B2 and C2. Since cells B2 and C2 are currently empty, the values of cells D3, D4, and D5 will also be zero. Figure B_2 displays the formulas in column D rather than the values of these cells as shown in Figure B_1.

Figure B_2

Figure B_3, below, serves as a check on our formulas. By placing a 1 in both cells B2 and C2, we obtain the values 18, 11, and 7 in column D. We interpret these numbers as the values of the profit function, the number of machine A hours used, and the number of machine B hours used, respectively. Making exactly one Premium tire and exactly one Regular tire would generate a profit of 18 dollars, using 11 hours on machine A and 7 hours on machine B.

Figure B_3

Prior to our explorations with Solver, we will first use trial and error to test different values of the decision variables. This approach involves manually entering trial values for the decision variables, B2 and C2, and then inspecting the worksheet to determine if these values satisfy the boundary conditions associated with the constraints.

[Before you begin to experiment it would be a good idea to save your work as the file ACETIRE.xls].

If we make 3 Premium tires and 2 Regular tires then we would enter a 3 in cell B2 and a 2 in cell C2. From Figure B_4 we see that the corresponding dollar profit would be 30 + 16 = 46. We can also see that this production plan uses exactly 24 hours on machine A and 18 hours on machine B, neither of which exceeds the total available time on the respective machines.

Figure B_4

You should keep a record of all points that you enter along with the corresponding values of the profit function.

Is it feasible to make 5 Premium and 4 Regular tires? Why or why not? When you are finished experimenting, restore the worksheet to look like Figure B_1 with zeros (or like Figure B_3 with ones). Keep in mind that cell B2 corresponds to the decision variable x, the number of Premium tires, and cell C2 corresponds to the decision variable y, the number of Regular tires. We have now prepared a spreadsheet which is at least adequate for investigation by the Solver Add-in tool. Later will consider some modifications which are more efficient for preparing worksheets for Solver, especially those that have more variables and constraints than this small example.

When you load Solver from the Tools menu, a dialog box entitled Solver Parameters will appear. Your task at this stage is to fill in the blank dialog box, Figure B_5, with the parameters as shown in Figure B_6.

Figure B_5

Figure B_6

The first entry to be specified is Set Target Cell. Solver may make a guess about the location of the target cell. In this case the formula in column D and row 3 is the correct target cell so click on cell D3. Next move to the Equal to row and click on the Max button. This will direct Solver to maximize the weekly profit from the two types of tires. Buttons for Min and Value will be blank since only one of these buttons can be in effect at any one time. Next move to the box By Changing Cells. The entry here should appear as $B$2:$C$2, the absolute address of the range of cells which contain the decision variables. Note: If Solver is successful at finding an optimal solution then B2:C2 will be the cells into which Solver will store these optimal values.

Next move to the Subject to the Constraints box. A dotted rectangle will appear in this box. Click on the Add button and a new dialog box entitled Add Constraint will appear:

Figure B_7

Cells D4 and D5 of the spreadsheet contain the formula for the left hand sides (LHS) of the machine constraints, These values should be respectively less than or equal to (<=) the right hand sides (RHS) of the boundary values which are stored in cells E4 and E5.

Click in the Cell Reference box and highlight cells D4:D5 on the worksheet. You should see the <= sign in the middle box. If not, click on the black down arrow to the right and select the <= sign. This sets the direction of the constraint. Click in the Constraint box and then highlight cells E4:E5, the cells containing the expressions for the RHS of the constraints. Lastly press the OK button in the dialog box and you will be returned to the Solver Parameters dialog box. This time you will see the constraint highlighted in the Subject to Constraints box. It should read: $D$4:$D$5 <= $E$4:$E$5.

If you make an error, move the cursor over to the Change key and the Change Constraint dialog box will appear. It should look similar to the Add Constraint dialog box and the same instructions apply as before. Move the cursor over to where the change has to be made, make the change, and press OK to return to the Solver Parameters dialog box. Now the non-negativity constraints must be made explicit. Click on the Add button. When the Add Constraint dialog box appears, include the non-negativity constraints as follows.

Click in the Cell Reference box on the left and then highlight B2:C2 (the locations of the decision variables). In the inequality box select the >= direction and then enter 0 in the Constraint box on the right. Both sets of constraints should be visible in the Subject to Constraints box when you click on OK and return to the Solver Parameters box. Before you go on, compare your parameters with those in Figure B_6. Next click on the Options button. A new dialog box appears entitled Solver Options. Click on the check box Assume Linear Model. This instructs Solver to check that the objective function and the constraints are indeed linear and to use a special algorithm, called the simplex method, to solve the problem. Turning on this checkbox is likely to improve the time it takes for Excel to find a solution (which is important for larger models). The setup of the problem is now complete.

Figure B_8

For now , ignore the rest of the options. Most of these have to do with default settings and solving non-linear optimization problems. Click on the OK button and return to the Solver Parameters dialog box. Click on the Solve button and Solver will proceed to search for the optimum solution.

Figure B_9

Information about the search for an optimal solution will appear in the status bar at the lower left part of your screen.

When Solver has finished, another dialog box will appear indicating whether or not a solution was found. Since the search was successful a solution appears on the worksheet. For managers, no solution is complete without a report containing an interpretation and a conclusion. The dialog box in Figure B_9 contains references to the Excel Solver completion reports Answers, Sensitivity, and Limits. As you learn more about linear programming, you will want to generate and interpret Sensitivity and/or Limits reports. For now, we will generate just an Answer report. First highlight Answer in the Reports box and then click on the OK box.

The answer report for this two variable problem should look like Figure B_10 below

Figure B_10

Checking the button Keep Solver Solution instructs Solver to display the optimal values of each variable on the spreadsheet. If you choose Restore Original Values, then Solver will restore these variables to their original values. Saving the spreadsheet as the file ACETIRE.XLS on your data diskette will also save the Solver parameters in your model along with the spreadsheet data and the Answer Report. Each Answer Report is numbered and identified as a tabbed sheet.

New decision variables and/or additional constraints can be introduced in the spreadsheet at any point. For example, suppose Ace Tire decides to make a third model which they refer to as the Discount tire. To make one Model D will require four hours on machine A and four hours on machine B. To improve the quality of their products, Ace Tire must also bring in a new finishing machine, machine C, which can be utilized for at most 30 hours per week. The machine C utilization requirements are as follows: three hours per Premium tire, one-half hour per Discount tire, and two hours per Regular tire. The profit function also changes. The new profit function will be defined by the formula Profit = 8*Premium + 9*Discount + 7*Regular.

To add a new decision variable for Discount tires, we must first insert a new column

Highlight the column containing the data for Regular tires and then select Insert… Columns

To add a new constraint in row 6 for machine C

The formulas in cells E3:E6 should be modified as follows

When the modified worksheet is ready for Solver, the values and formulas should look like Figure B_11.

Figure B_11

Figure B_12 shows the parameters of the completed Solver dialog box.

Figure B_12

Make sure that Linear Model has been checked under Options before you run Solver. Once Solver indicates that a solution has been found, select the Answer Report before you click the OK button.

Note that Answer Report shown in Figure B_13 shows the original and final values of the target cell and the changing cells. It also lists the constraints and gives important information about each constraint.

Figure B_13

INTEGER SOLUTIONS

If you are interested in looking for an optimal solution in which decision variables are all integers then you must invoke Solver again and add an int constraint to cells B2, C2, and D2. See Figure B_14 for the new Answer Report. With integer programming models you should not be surprised if Solver returns a message indicating that a solution could not be found under the given conditions.

Figure B_14

IMPROVING THE EFFICIENCY OF BUILDING AND INTERPRETING LARGER MODELS

The AceTire worksheet in Figure B_11 has only three decision variables, three < constraints, and one > constraint (non-negativity). It is not unusual for real - world linear optimization problems to have hundreds (or even thousands) of variables and constraints. Some examples of very large LP models occur in airline reservation systems and the design of telephone switching circuitry. The nutrition model below has nine variables and thirteen constraints. Before we examine this model, we will first learn how to prepare spreadsheets for Solver that uses a more efficient method of entering data and formulas. These modifications will also make it easier for us to read the reports and interpret the results.

To understand this new approach we will re-build the entire AceTire worksheet starting with a new (blank) worksheet. As you will see, the major difference will be in the way we build the formulas for the target cell, E3, and for the cells immediately below the target cell.

• Obtain a blank worksheet and enter the column labels Premium, Discount, and Regular in cells B1, C1, and D1 respectively. Also enter the label bounds in cell F1.
  
• Enter the same row labels in column A as shown in Figure B_11
  
• Leave cells B2:D2 empty for the three decision variables or set these initial values to zero.
  
• Enter the coefficients (8, 9, and 7 ) for the objective function in columns B, C, and D of row 3.
  
• Enter the nine coefficients which are to be used in the LHS for the Machine A, B, and C constraints.
  
• Enter the three values of the bounds for Machine A, B, and C (these will become the RHS of <= constraints in the Solver parameters).
  

The formula for the objective function in cell E3 could be entered as

=B3*B2+C3*C2+D3*D2

Cells E4, E5, and E6 must contain formulas for the LHS of each machine constraint. Using the earlier method, these formulas were expressed as:

=B4*B2+C4*C2+D4*D2

=B5*B2+C5*C2+D5*D2

=B6*B2+C6*C2+D6*D2

In each of these four formulas, notice that the values in columns B, C, and D of each row (rows 3, 4, 5, and 6) are multiplied by the corresponding values of the decision variables which are always in cells B2, C2, and D2. These individual products are then added together, as a "sum of products". Using Excel's SUMPRODUCT function, the formula for cell E3 can be efficiently implemented as

= SUMPRODUCT( B3: D3, $B$2:$D$2)

References to the range of cells B2, C2, and D2 with $ signs in front of the column and row position, are called "absolute references". This has the effect of insuring that a reference to such a cell will not change if the formula containing the absolute reference is copied to another location. The LHS (left-hand side) formulas for cells E4, E5, and E6 can be easily obtained by copying cell E3, which contains the formula = SUMPRODUCT( B3: D3, $B$2:$D$2), into the three rows directly below E3. One easy way to perform this action is to select cell E3, locate its fill handle in the lower right corner of the cell's border, and then click and drag the cursor (in the shape of a crossbar ) through the three rows while holding down the left mouse button. Once the range E4: E6 has been highlighted, let up on the left mouse button and the filling down will be accomplished. In Figure B_15, below, column E shows the formula for the objective function (shaded) and the LHS of the constraints for each machine.

Figure B_15

At this point the worksheet is ready for you to enter the parameters as shown in Figure B_16.

Figure B_16

Make sure that Linear Model has been selected under Options. Click on Solve and convince yourself that this more efficient procedure for building the worksheet in Figure B_15 is equivalent to the original method.

A MINIMAL COST NUTRITION PROBLEM

The efficiencies of building a model in the new way will become more apparent as you investigate the following nutrition/diet problem.

Ten male soccer players are all between 19 and 22 years old and weigh from 154 to 177 pounds. The recommended daily intake of calories, protein, fat, cholesterol, and sodium for each individual are the recommended limits found to the right side of the table Nutrition Information per Serving below. The team intends to eat together at a local McDonald's. They know that no one can order 1.7 hamburgers but they could order 17 and cut them up. Their coach has advised them to avoid carbonated beverages. Most of them will drink water and orange juice. From their previous trips to McDonald's they have sampled the food, checked the prices, and obtained nutrition information per serving. Their main concerns are (1) meeting the recommended daily requirements including 100 % of the RDA for Vitamins A and C, Thiamin, Riboflavin, Niacin, Calcium, and Iron (2) staying within the recommended limits for fat, cholesterol, and sodium (3) keeping their costs under $10.00 per person and (4) maintaining good relationships with the busy restaurant staff. From the 80 possible choices on the menu they have decided to limit their choices to the nine shown in Figure B_17.

The following tables show 1994 unit prices at a local McDonald's and data taken from a 1993 McDonald's publication entitled Nutrition Information per Serving. This data has been stored in the file MCDNLD9.xls.

Figure B_17

Recommended limits: Based on Males between 19-22 years of age and weighing 154 to 177 lbs.

Note: * signifies the amount is insignificantly small

Figure B-18

	Given the information in Figures 17 and Figure 18, your task is to build the worksheet and then use Solver. Note that there will be ten > constraints (counting non-negativity) and three < constraints. Load Solver and enter the appropriate parameters as shown in Figure B_19. Be sure to check Linear Model in Options and then Solve.
Figure B_19

In Figure B_20 the optimal solutions have been saved with the worksheet.

Figure B_20

The target cell and the cells containing the decision variables are shaded as before for ease of identification. As you might expect, the optimal solution which corresponds to a minimum cost does not have integer values.

Return to Table of Contents

Copyright © Joseph F. Aieta, Babson College 1997