NAME
     wnsplx -- simplex method package

SYNOPSIS
     #include "wnmat.h"


     wn_simplex_method(&code,&objective,shadow_prices,solution,
                       objective_vect,mat,right_side,
                       len_i,len_j)
     int code;
     double objective;
     double *shadow_prices,*solution,*objective_vect;
     double **mat;
     double *right_side;
     int len_i,len_j;


     wn_simplex_loop(&code,mat,right_side,right_side_control,
			   non_zero_vars,zero_vars,
                           len_i,len_j)
     int code;
     double **mat;
     double *right_side,*right_side_control;
     int *non_zero_vars,*zero_vars;
     int len_i,len_j;


DESCRIPTION
     This package solves the "linear programming" problem easily and
     efficiently.  The "linear programming" problem is the following
     optimization problem:

         CHOOSE solution[j] TO MAXIMIZE

             sum_over(j){ objective_vect[j]*solution[j] } 

         WHILE SATISFYING THE CONSTRAINTS

             for_all(i){ sum_over(j){mat[i][j]*solution[j]} == right_side[i] }

                 AND

             for_all(j){ solution[j] >= 0 }

     Note the i contraints above, unlike the j constraints, are EQUALITY
     constraints.  If you have inequality constraints, you have to
     convert them to equality constraints by adding slack variables
     to your matrix.  For an example of this, see wnlib/acc/mat/selftest.c

     Difficult optimization problems from many fields can be put into
     this form, and thus solved efficiently with this package.

     Set "objective_vect" to NULL if you want any feasible solution;
     set "shadow_prices" to NULL if you don't care about shadow prices.

     For an introduction to the linear programming problem, consult
     [1] and [2].  The basis of the algorithm used here is the "revised
     simplex method" given in [3].  However, the algorithm used has these 
     improvements:
     
       1)  It is randomized to avoid various degeneracy problems.  

       2)  The pivot element is selected for numerical stability

       3)  A perturbed right side is provided as an anti-cycling 
	   measure.

     Naive users should confine themselves to "wn_simplex_method".

     "wn_simplex_loop" makes available to sophisticated users the 
     (improved) simplex loop given in [3] in raw form.
     The 0'th row is the objective row.  right_side[0] contains minus 
     the objective after completion of the algorithm.  "right_side_control" 
     should be an array with "len_i" entries, initialized to the values
     in "right_side" plus a small random perturbation.  The perturbation
     is necessary to prevent cycling.
     "wn_simplex_loop" uses "right_side_control" to control the basis;
     "right_side" is carried along with it to give the exact answer.

RESOURCES
     Solving the simplex problem using "wn_simplex_method" requires

       AVERAGE CASE:

         time = len_i^2 * len_j
         stack memory = 1
         dynamic memory = len_i*len_j

     Randomizing is used to avoid exponential worst-case performance.

     "wn_simplex_loop" requires

       AVERAGE CASE:

         time = len_i * len_j
         stack memory = 1
         dynamic memory = 0

     for each iteration.  Usually no more than order len_i iterations 
     are required for an optimal solution.

DIAGNOSTICS
     code == WN_SUCCESS  for successful solution.
     code == WN_UNBOUNDED  for unbounded solution.
     code == WN_INFEASIBLE if no solution satisfies the constraints.

     WN_INFEASIBLE also given if "mat" is degenerate, even if solutions
     are feasible.
  
BUGS

SEE ALSO
     wnminv, wnanl, wnnlp
     wnlib/acc/mat/selftest.c

REFERENCES
     [1]  F. Hillier and G. Lieberman:  Introduction to Operations Research.
               Holden-Day Inc.

     [2]  J. Franklin:  Methods of Mathematical Economics.  
               Springer-Verlag.

     [3]  G. B. Dantzig, A. Orden, and P. Wolfe:  Generalized Simplex 
               Method for Minimizing a Linear Form under Linear 
               Inequality Restraints, Pacific J. Math. Vol. 5 (1955)
               pp. 183-195.

AUTHOR
     Will Naylor