Using Microsoft Excel to Solve Linear Programs



Solving Linear Programming Problems with Microsoft Excel

Instructions Paper

Karl Wimmer

September 15, 2003

Using Microsoft Excel to Solve Linear Programs

This document is intended for use as a guide to enter and solve linear programs using Microsoft Excel. This document assumes basic familiarity with Microsoft Excel or another spreadsheet program and familiarity with standard forms for linear programming.

INSTALLATION

The Microsoft Excel solver command is not always visible by default when Microsoft Excel is originally installed. Some versions do not contain the solver command. Upon finishing this tutorial, you will have access to the solver or conclude that your version of Microsoft Excel does not have the solver.

1. Open the Microsoft Excel program.

2. On the menu bar, click Tools. If you see two arrows pointing downward at the bottom of the list of commands, click on the arrows.

|If you see the command “Solver…”, the solver is already installed. You may proceed to “SETTING UP THE LINEAR PROGRAM |

|MATHEMATICALLY.” |

3. Choose “Add-Ins…” From the Tools menu. A dialog box will pop up displaying the available add-ins for Microsoft Excel.

4. Scroll down through the list of options until you see “Solver Add-in.” Check the box to the left of the text by clicking on it.

5. Click the “OK” button.

6. If a dialog box pops up and says that the feature needs to be installed, click the “OK” button.

7. Follow the on-screen instructions to install the Microsoft Excel solver command.

8. On the menu bar, click Tools. You should see the “Solver…” command.

|If you do not see the “Solver…” command, then stop, you do not have access to the Microsoft Excel solver command. |

SETTING UP THE LINEAR PROGRAM MATHEMATICALLY

Now you are ready to solve linear programs. First of all, the objective function needs to be in the form [pic], where the x variables are the resource variables and the c variables are the coefficients associated with them. Each constraint must be in the form[pic]. The ≤ sign may be substituted with = or ≥. Also, every variable can have an upper bound and a lower bound. This type of constraint will be handled differently. Now you are ready to begin. To become comfortable with the solver, initially select problems with less than five variables and less than five constraint equations. Throughout this tutorial, there will example screens for solving the linear programming problem:

Maximize the function [pic]

Subject to the constraints:

[pic]

[pic]

[pic]

and [pic],[pic], and [pic]

[pic] will be named “Var 1”, [pic] will be named “Var 2”, and [pic] will be named “Var 3”. The constraint will be named “Cons 1”, “Cons 2”, and “Cons 3”, where the order of the constraints is top to bottom. Remember, the bounds on the variables in the “and” statement are not handled as constraints. You may use the example problem or one of your own to use this tutorial.

SETTING UP A TEMPLATE IN MICROSOFT EXCEL

Although the solver command does not use labels for variables, it proves helpful for entering the program into a spreadsheet.

1. In cell A1, you may type whatever you wish to identify that this is a linear programming table.

2. In row 1, starting at column B and moving right, enter a name for each variable. Use one cell for one variable name. The labels can be descriptive, like “Steel Used” or “Gallons of Fuel.” The labels can also be generic, like “Var 1,” “Var 2,” and so on.

3. Still moving right in row 1, skip a column, and type “Eval” in the cell. This column will contain evaluations of the constraint equations and objective function.

4. Again moving right in row 1, skip a column, and type “Constraint” in the cell. This column will contain the right hand side number of the constraint equations.

5. In cell A2, type “High value”. This row will contain upper bounds for the variables. You will be filling column A with labels. You may need to expand the width of column A to see the entire label.

6. In cell A3, type “Value”. This row will contain the values of the variables. This row will be adjusted by the solver in solving the problem.

7. In cell A4, type “Low value”. This row will contain the lower bounds for the variables.

8. In cell A5, type “Objective”. This row contains the cost coefficients in the objective function.

9. Starting at cell A6 and moving downwards, add one label for each constraint. Each label can have a specific name such as “Storage,” “Time,” or “Water.” Each label can instead have a generic name such as “Cons 1,” “Cons 2,” and so on.

At this point, the template is completed, and we are ready to add numbers. Your spreadsheet should resemble the following table.

|A |B |C |D |E |F |G |H | |1 |LP is fun |Var 1 |Var 2 |Var 3 | |Eval | |Constraint | |2 |High value | | | | | | | | |3 |Value | | | | | | | | |4 |Low value | | | | | | | | |5 |Objective | | | | | | | | |6 |Cons 1 | | | | | | | | |7 |Cons 2 | | | | | | | | |8 |Cons 3 | | | | | | | | |

ENTERING DATA

Entering data can be a slow and monotonous process. Be sure that your linear program is in the standard form. Be sure not to make mistakes entering the numbers into the spreadsheet, for it may be difficult to track errors down.

1. Click on cell B2. Row 2 will contain the upper bound for each variable. If you do not have an upper bound for a variable, enter a formula with a large result, such as “=10^25.” If you do this, the computer will change it to “1E+25.” This is normal.

2. Proceed to the right to fill row 2 with upper bounds until every column with a variable name has an upper bound entry. Rows 1 and 2 should resemble the table:

3. Click on cell B4. Row 4 will contain the lower bound for each variable. If you do not have a lower bound for a variable, enter a formula with a large negative result, such as “=-10^25.” If you do this, the computer will change it to “-1E+25.” This is normal.

4. Proceed to the right to fill row 4 with lower bounds until every column with a variable name has a lower bound entry.

At this point, the first four rows should resemble the following table:

|A |B |C |D |E |F |G |H | |1 |LP is fun |Var 1 |Var 2 |Var 3 | |Eval | |Constraint | |2 |High value |1E+25 |1E+25 |4 | | | | | |3 |Value | | | | | | | | |4 |Low value |0 | 30 |-1E+25 | | | | | |

5. Click on cell B5. Row 5 will contain the cost coefficients for each variable. Enter zero if there is no cost coefficient for a variable.

6. Proceed to the right to fill row 5 with cost coefficients until every column with a variable name has a cost coefficient.

You have now set up the variables, their bounds, and the objective function. You must now set up the constraints.

7. Start at row 6.

8. Click on the cell in the current row that is also in column B.

9. Starting in column B and moving right, enter the constraint coefficient of each variable in the cell with the matching column name.

10. Once you are done, move right, skipping two columns and enter the sign of the constraint in the cell. Enter either “=”.

11. Move one cell to the right once more and enter the number on the right hand side of the constraint equation.

12. If there is another constraint, move down one row and go to step 8. If not, you are done entering constraints.

|A |B |C |D |E |F |G |H | |1 |LP is fun |Var 1 |Var 2 |Var 3 | |Eval | |Constraint | |2 |High value |1E+25 |1E+25 |4 | | | | | |3 |Value | | | | | | | | |4 |Low value |0 |30 |-1E+25 | | | | | |5 |Objective |1 |-1 |2 | | | | | |6 |Cons 1 |2 |3 |0 | | |= |100 | |

You will now enter a formula into the spreadsheet that evaluates the objective function.

13. Find the cell in row 5 that is also in the column labeled “Eval” and click on it.

14. Type “=SUMPRODUCT(”, but do not press the Enter key.

15. Click on cell B3 and hold, dragging right across the row until every column with a variable name is inside the selection. Release the mouse button.

16. Press the comma key.

17. Click on cell B5 and hold, dragging right across the row until every column with a variable name is inside the selection. Release the mouse button.

18. Type “)” and press the Enter key. The number zero should appear in the cell.

The process of entering the formulae that evaluate the constraints is nearly the same as the process used to enter the objective function.

19. Start at row 6.

20. Find the cell in current row that is also in the column labeled “Eval” and click on it.

21. Type “=SUMPRODUCT(”.

22. Click on cell B3 and hold, dragging right across the row until every column with a variable name is inside the selection. Release the mouse button.

23. Press the comma key.

24. Click on the cell in the current row that is also in column B and hold, dragging right across the row until every column with a variable name is inside the selection. Release the mouse button.

25. Type “)” and press the Return key. The number zero should appear in the cell.

26. If there is another constraint, move down one row and go to step 20. If not, you are done entering formulae.

Your table should resemble the following:

|A |B |C |D |E |F |G |H | |1 |LP is fun |Var 1 |Var 2 |Var 3 | |Eval | |Constraint | |2 |High value |1E+25 |1E+25 |4 | | | | | |3 |Value | | | | | | | | |4 |Low value |0 |30 |-1E+25 | | | | | |5 |Objective |1 |-1 |2 | |0 | | | |6 |Cons 1 |2 |3 |0 | |0 |= |100 | |

USING THE SOLVER

Now that the data entry section is done, you are ready to solve your problem.

1. From the menubar, select “Solver…” from the Tools menu. The solver dialog appears. Below is the solver dialog.

[pic]

2. Click on the cell in the objective row (row 5) under the column heading “Eval.” The reference of the cell should be in the “Set Target Cell:” box.

3. In the “Equal To:” section, decide whether you want to maximize or minimize the value in the cell by selecting the corresponding radio button.

4. Click inside the text box directly under the text “By Changing Cells:”. Click the icon immediately to the right of this text box. The icon has a red arrow on it. By clicking this type of box, you will be able to click and drag over cells you want to reference rather than type the cell references manually. You will now select the adjustable cells, which is our Value row.

5. Click and hold over cell B3, and drag to the right until all variables have been selected. Release the mouse button.

6. Click the icon with the red arrow. The icon looks slightly different than the icon you clicked before.

7. In the “Subject to the Constraints:” box, click “Add”. This is where the solver picks up on constraints.

[pic]

8. Click the icon with the red arrow under the “Cell Reference:” text. This icon the leftmost of the two identical icons.

9. Click and hold over cell B3, and drag to the right until all variables have been selected. Release the mouse button.

10. Click the icon with the red arrow to go back to the constraint window.

11. Click the icon with the red arrow under the “Constraint:” text. This icon the rightmost of the two identical icons with red arrows.

12. Click and hold over cell B2, and drag to the right until all variables have been selected. Release the mouse button.

13. Click the icon with the red arrow to go back to the constraint window.

14. Before clicking “Add”, be sure that “=” from the drop down list between the text boxes, then click “Add”. The cell references will vanish. This sets the lower bounds for the variables.

Now you will begin referencing the constraints. For each constraint row perform the following steps:

20. Click the icon with a red arrow under the “Cell Reference:” text. This is the leftmost of the two identical icons with red arrows.

21. Click the cell in a constraint row that is also in the column under the “Eval” heading.

22. Click the icon with the red arrow to go back to the constraints window.

23. Look at the entry in the cell immediately to the right of the cell which you just clicked. Select the matching entry from the drop down list between the two text boxes in the constraints window.

24. Click the icon with a red arrow under the “Constraint:” text. This is the rightmost of the two identical icons with red arrows.

25. Click the cell in the same row as the cell you clicked in step 21 but in the column after the “constraint” heading.

26. Click the icon with the red arrow to return to the constraint window.

27. Click the “Add” button. The cell references will vanish.

28. Repeat steps 20-27 for all constraints in the problem.

29. Click the “Cancel” button to return to the solver parameters box.

This concludes entering the program. The solver dialog should have a target cell, a range of adjustable cells, and numerous constraints. The “By Changing Cells:” text box should have an entry beginning with “$B$3:”, and the first two entries in the “Subject to the Constraints:” box should begin with the entry in the “By Changing Cells” text box. If not, the solver may not solve the problem you had intended. All that is left is one click.

[pic]

30. Click the “Solve” button. Microsoft Excel will find the optimal solution to the problem that you specified.

The cells on row 3 and in the “Eval” column will change values. The next page shows what Microsoft Excel states as the optimal solution.

|A |B |C |D |E |F |G |H | |1 |LP is fun |Var 1 |Var 2 |Var 3 | |Eval | |Constraint | |2 |High value |1E+25 |1E+25 |4 | | | | | |3 |Value |136 |60 |4 | | | | | |4 |Low value |0 |30 |-1E+25 | | | | | |5 |Objective |1 |-1 |2 | |84 | | | |6 |Cons 1 |2 |3 |0 | |452 |= |100 | |

Recall the original problem:

Maximize the function [pic]

Subject to the constraints:

[pic]

[pic]

[pic]

Where [pic],[pic], and [pic]

The optimal solution is the values of the cells in row 3. Reading row 3, we see that[pic],[pic], and [pic]is the optimal solution.. The optimal value is 84, the value of cell in the intersection of the “Objective” row and the “Eval” column.

The above methods can be generalized for any type of optimization problem, whether linear or nonlinear. The solver may not be as fast as when solving a linear programming problem, but through use of Microsoft Excel formulae other than the SUMPRODUCT formula, you can devise a solvable model for nearly any type of operations research problem. In addition, the drop down list in the add constraint box has the options “int” and “bin” besides the comparison operators. Selecting “int” forces the referenced cells to be integers, and selecting “bin” forces the referenced cells to be zero or one. This is just a taste of the power provided by the Microsoft Excel solver.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download