Using Excel to Find Numerical Solutions to LP's
by Anil Arya and Richard A. Young
This handout sketches how to solve a linear programming problem using Excel. (Click here to download a pdf Adobe Acrobat version of this tutorial, for printing purposes.)
Suppose you wish to solve the following LP:
Max 100 x1 + 2 x2
subject to: 2 x1 + x2 <= 100
x1 + 3 x2 <= 120
x1, x2 >= 0
A. Setting Up the Parameters in the Spreadsheet:
1. Enter Excel. Open up a new spreadsheet.
2. Enter the objective function coefficients in cells A1 and B1. See Table 1 below for input display.
3. Enter the coefficients on x1 and x2 respectively for the left-hand side of the first constraint in cells A3 and B3. (See Table 1 below.) Enter the right-hand side of this constraint in cell C3. Repeat for the second constraint in row 4. You get the idea.
B. Enter the Data into the Spreadsheet in the Form to be Used Directly by Solver:
1. Place trial values in cells A6 and B6. These are purely arbitrary -- they don't even have to satisfy the constraints. After you solve the LP these cells will contain the solution.
2. Enter the objective function in cell A8, referring to the parameters set up in Step A.2 and the trial values in Step B.2. Notice that in the example the objective function is a linear function of the variables over which we shall optimize.
3. Enter the left- and right-hand side of the constraints, referring to the parameters set up in Step A.3. For the first constraint they are placed in cells A11 and B11, respectively. Repeat for the other constraints in rows 12-14. Notice that in the example the left-hand side is a linear function of the variables over which we shall optimize.
4. Be sure to explicitly enter the non-negativity constraints as illustrated in Table 1 and 2. You might get into trouble if the optimal solution would set one of the variables = 0 (as it does for the above LP).
Tables 1 and 2 display the spreadsheet that I used to set up the problem. Notice, to make it easier to understand what I have done, I typed in labels such as "Obj fcn coefficients." In Table 1 (for purposes of instruction), within the "Tools" menu I selected "Preferences," then "View," and checked the "Formulas" box in the "Windows options" area of the "View" window. Table 2 displays the spreadsheet in the default mode ("Formulas" not checked). This is what things should look like just before you solve the LP.
Table 1: Setting up the Spreadsheet (Display set to show formulas)
Table 2: Setting up the Spreadsheet (Display set to hide formulas)
C. Initializing and Running Solver:
1. Select Solver from the "Tools" menu. Solver will work directly with cell A8 (the objective function) and cells A11, B11 and A12, B12 and A13, B13 and A14, B14 (the constraints). On the screen will appear the Solver Parameters window, which will appear as shown in Table 5 when you are all done. Continue.
2. Type A8 in the "Set Target Cell:" box. Be sure "Max" is selected (for maximization).
3. Type A6:B6 in "By Changing Cells:" box.
4. To build the constraints click "Add." The "Add Constraint" window will appear as in Table 3. Type A11 in the Cell Reference box. The direction of the inequality should be set at "<=" for the first constraint. Type B11 in the "Constraint:" box. Click "Add" to keep adding constraints. A blank "Add Constraint" window will re-appear. When you get to the non-negativity constraints make sure ">=" is selected. To stop adding constraints click "OK."
5. Click the Options box and then click Assume Linear Model, since this is an LP. Click Okay to return to Solver box. (See Table 4.)
Table 3: Add Constraint Window
Table 4: Solver Options Window
Table 5: Solver Window for Correctly Specified Model
Tables 5 displays the Solver window for the model we wish to solve. At some point, the the software may insert dollar signs in cell labels; you did not need to do that yourself. Also, as you get more facile, you will learn that you can click and point or drag instead of typing in cell labels.
6. Now you are ready to solve the LP. Click Solve. If you've done everything okay, a window should appear with the message "Solver found a solution. All constraints and optimality conditions are satisfied." (See Table 6 above.) Alternatively, you may get a message that the algorithm has not converged, indicating that you need to run a few more iterations. This is unlikely with an LP of the size we'll be dealing with, but may obtain if you run a non-linear program. Or, less problematic, the solution may look a little messy (like "-1.1E-11," which is practically zero). In either of these cases, simply click "OK" and then run the Solver again, with the current solution as the starting solution. If you get a more troublesome message, such as "the problem has not converged," etc., you probably have entered the problem incorrectly. Make sure that it's maximizing if that's what you want to do. Make sure the direction of the inequalities is correct. Make sure the non-negativity constraints have been entered.
Note: In the above example you were instructed to check Assume Linear Model, since this is an LP. If you wish to solve a non-linear program (non-linear objective or constraints), you should go into Options and make sure you have not selected "Assume Linear Model." The other options are normally fine to leave at their default settings.
Table 6: Results Window for Solver
D. Sensitivity Analysis:
1. Try selecting from within the "Reports" section of the "Solver Results" window one or more of: "Answer," "Sensitivity," and "Limits." For example, if you select "Sensitivity," a window will appear as in Table 7 below. This report is automatically placed into a separate Excel Sheet titled "Sensitivity Report 1." You see the shadow prices are 50 on the first resource constraint and zero on the second.
Table 7: Results of Sensitivity Analysis
3. Now click on "Sheet 1", which will appear as in Table 8 below. The optimal solution is: x1 = 50, x2 = 0, and the objective function is 5,000. Congratulations!
Table 7: Successfully-Run Program