Linear Programming
Numerical Recipes
by Elmer G. Wiens
Egwald's popular web pages are provided without cost to users. Please show your support by joining Egwald Web Services as a Facebook Fan:
Follow Elmer Wiens on Twitter:
Linear programming example 
Zero sum two person game 
Solve your own l.p. problem 
Simplex method algorithm
I will use the following example from:
Press, William H., et al. Numerical Recipes. Cambridge: Cambridge UP, 1989;
to show, step by step, how the linear programming package can be used. (The algorithm is based on the one in the reference above.)
Maximize Z = X1 + X2 + 3*X3  .5*X4
with all the X's nonnegative and also with
X1   + 2*X3 
 <= 740 
 2*X2    7*X4 
<= 0 
 X2   X3  + 2*X4 
>= .5 
X1  + X2  + X3  + X4 
= 9 
The first equation is the objective function. The next four equations are the constraints on the independent variables (X1, X2, X3, X4).
Notice that the RHS numbers (to the right of <=, >=, or =) must all be positive.
We need to set some parameters for my program.
n = 4 (the number of independent variables)
m = 4 (the number of constraints)
m1 = 2 (the number of <= constraints)
m2 = 1 (the number of >= constraints)
m3 = 1 (the number of = constraints)

We also need to introduce slack variables (Y1, Y2, Y3), one for each <= and >= constraint, so that the set of constraints are:
X1   + 2*X3 
 + Y1   
= 740  
 2*X2    7*X4 
 + Y2   = 0 
 X2   X3  + 2*X4 
   Y3  = .5 
X1  + X2  + X3  + X4 
   = 9 
Notice the pattern of + and  signs for the <= and >= constraints.
Not done yet! Now we create artificial variables (Z1,Z2,Z3,Z4) and rewrite the equations (including the objective function) as:
Z0 =  0 
+ 1*X1  + 1*X2  + 3*X3   .5*X4 
+ 0*Y1  + 0*Y2  + 0*Y3 
Z1 =  740 
 1*X1  + 0*X2   2*X3 
+ 0*X4   1*Y1  + 0*Y2;  + 0*Y3 
Z2 =  0 
+ 0*X1   2*X2  + 0*X3  + 7*X4 
+ 0*Y1   1*Y2  + 0*Y3 
Z3 =  0.5 
+ 0*X1   1*X2  + 1*X3   2*X4 
+ 0*Y1  + 0*Y2  + 1*Y3 
Z4 =  9 
 1*X1   1*X2   1*X3   1*X4 
+ 0*Y1  + 0*Y2  + 0*Y3 
The above equations are in "restricted normal form".
You must convert your linear programming problem to the above form. Then do the following steps.
Certain restrictions apply to the parameters:
m = m1 + m2 + m3; n <= 8; m <= 15; n > 0;
m > 0; m1 >= 0; m2 >= 0; m3 >= 0.
Once you fill in the table below, another table will be displayed where you will be able to put the data of your table.
So you give your linear programming problem a name, and enter it with the parameters into the table. Then click 'submit parameters'.
You can also solve a small linear programming problem with the Dual Simplex Method, using a user friendly interface.
Return to Linear Programming entry page.
