Web Solver

A Web page to solve linear programming problems using the simplex method

How to Use the Solver

This Web page explains how to use WebSolver in conjunction with instructional materials to solve linear programming problems. I will not describe the simplex method here. WebSolver is designed to assist the student enrolled in an upper division or graduate course to understand the method. This description is not meant to be a self-contained tutorial on linear programming.

If you don't know what linear programming is, or are not sufficiently familiar with it, you may not understand all or part of this discussion.

Please see the excellent references located at the bottom of this page for an introduction to the science of linear programming, and to learn more about  the simplex method for solving linear programming problems.

The Canonical Problem

The objective in a linear programming (LP) problem is to
maximize Z=ctx
x1,x2,...,xn
subject to
Ax <= b
x1,x2,...,xn >= 0
where x1,x2,...,xn are the control variables. While any feasible problem may be written in this form, WebSolver allows the user to minimize, and allows less than, greater than, and equality constraints.  Just remember that <= is the same as <, and >= is the same as >.

Example 1

You may wish to solve the following LP problem:
Maximize x1 + 2x2 + 3x3
subject to 3x1 + 2x2 + 2x3 = 3
2x1 + 3x2 + x3 <= 2
This problem would be input into WebSolver as follows:

max 1 2 3
3 2 2 = 3
2 3 1 < 2

(You may wish to cut this out and paste it into WebSolver using your operating system's clipboard to see what it does.) Pressing the Evaluate button produces a sequence of tables (called tableaus in LP-speak), ending with the following output:
 
x1 x2 x3 x4 C
1.5 1 1 0 1.5 =
0.5 2 0 1 0.5 < =
-3.5 -1 0 0 -4.5 Max

Final values:

Variable Value 
x1 0
x2 0
x3 1.5
Slack Value Dual 
x4 0.5 -0
Optimum
Z 4.5

The first table shown above is the final tableau one might obtain when solving with pencil and paper. WebSolver interprets this tableau and places this information in the last table. The second table above reports the final values of the control variables that obtain the largest value for Z, the objective function. This is followed by the values of the so-called slack variables. Slack is the distance of the left-hand side of a constraint from the right-hand side at the optimum. The dual values (or shadow prices) associated with each of the constraints are reported next to them. Finally, WebSolver reports the optimum value of Z.  In a maximization problem, this is the highest attainable value; in minimization, the lowest.

This LP problem might more properly be written as

max 1 2 3
3 2 2 < 3
3 2 2 > 3
2 3 1 < 2

where the equality constraint is now represented by two inequalities. WebSolver now produces the following output:
 
x1 x2 x3 x4 x5 x6 C
1.5 1 1 0.5 0 0 1.5 < =
0 0 0 -1 -1 0 0 > =
0.5 2 0 -0.5 0 1 0.5 < =
-3.5 -1 0 -1.5 0 0 -4.5 Max

Final values:

Variable Value
x1 0
x2 0
x3 1.5
Slack Value Dual
x4 0 1.5
x5 0 0
x6 0.5 -0
Optimum
Z 4.5

This output more clearly shows that the first constraint is binding from below and has a shadow price of 1.5.

Example 2

The Diet Problem

In the diet problem a consumer is presented with a collection of foods, each providing a certain amount of the nutrients necessary for survival. Ignoring taste considerations, she wishes to minimize cost subject to the condition that all of her nutritional requirements are satisfied. Suppose that her decision problem can be represented in the following table:
 

Protein
Vitamin C
Iron
Cost		 Arugula
0.4
6
0.4
8		 Bean Sprouts
1.2
10
6
10		 Cheeze Whiz
0.6
3
0.4
3		 Dolmas
0.6
1
0.2
20		 Elderberries
12.2
0
2.6
15		 Requirements
70
50
12

In WebSolver, her problem should be written as follows:

min  8   10    3   20   15
     0.4  1.2  0.6  0.6 12.2 > 70
     6   10    3    1    0   > 50
     0.4  0.6  0.4  0.2  2.6 > 12

As you can see, spacing and alignment of columns is irrelevant, but notice that 0 must be entered as a placeholder. To see the process of arriving at the solution of this problem, copy the code, paste into the text field in WebSolver and press Evaluate. The final output is reproduced here:
 
x1 x2 x3 x4 x5 x6 x7 x8 C
0.23 0.563 0 0.0186 0 -0.213 -0.0907 1 7.45 > = 
2 3.33 1 0.333 0 0 -0.333 0 16.7 > = 
-0.0656 -0.0656 0 0.0328 1 -0.082 0.0164 0 4.92 > = 
2.98 0.984 0 18.5 0 1.23 0.754 0 -124 Min 

Final values:

Variable Value 
x1 0
x2 0
x3 16.7
x4 0
x5 4.92
Slack Value Dual 
x6 0 1.23
x7 0 0.754
x8 7.45 0
Optimum
Z 124

The table indicates that she should consume 16.7 units of Cheeze Whiz, and 4.92 units of Elderberries at a cost of 124.  She should consume zero of the other items, since the amount of nutrition per dollar spent is too high given her preferences.  The first two constraints, Protein and Vitamin C are binding, while the Iron constraint is not.  The non-zero dual values on these constraints indicate the value of reducing her requirement for either nutrient by one unit.  For example, she should be willing to pay 1.23 for a food item that would provide one unit of protein, and 0.754 for one that provides one unit of Vitamin C.

Of course, no consideration of other health issues are present.  If a constraint was introduced to limit her intake of fat, a different diet might well have been recommended.
 

Go Forth, and Optimize

That's pretty much all you need to know, assuming you have textbook in hand. If any of the coefficients are zero, you must enter them as placeholders. If you submit an unbounded or cycling problem that the program doesn't recognize, rest assured that the program will stop after 15 iterations. Also, you might want to avoid submitting very large problems. You are limited to 30 control and slack variables.  This is an ancient NeXT cube, have a heart!

Run WebSolver

Word has it this program always arrives at the correct solution. If you think otherwise, or you have trouble with the program please send me e-mail with a description of what happened. I will fix the problem ASAP.

References

Chvátal, Vasek (1983) Linear Programming, W. H. Freeman and Company, New York. ISBN 0-7167-1587-2, or 0-7167-1587-8.

Thie, Paul R. (1988) An Introduction to Linear Programming and Game Theory, John Wiley and Sons, New York. ISBN 0-471-62488-8. 

WebSolver version 1.0, by Geoffrey R. Gerdes. Copyright 1996. This page, copyright 1996,1999.  All rights reserved.