wnsplx(3)

NAME

wn_simplex_method, wn_simplex_loop - simplex method pack

age

SYNOPSIS

#include <wn/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 easi

ly and efficiently. The "linear programming" problem is the fol

lowing 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 }

Difficult optimization problems from many fields can be

put into this form, and thus solved efficiently with this pack

age.

Set objective 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 re

quires

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 per

formance.

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 it

erations 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 con

straints.

WN_INFEASIBLE also given if mat is degenerate, even if so

lutions are feasible.

SEE ALSO

wnminv, wnanl, wnnlp

REFERENCES

[1] F. Hillier and G. Lieberman: Introduction to Opera

tions 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 Inequal

ity Restraints, Pacific J. Math. Vol. 5 (1955) pp. 183-195.

AUTHOR

Will Naylor

WNLIB August 23, 1998

WNSPLX(3)