---
name: "wnsplx"
section: "3"
platform: "linux"
package: "libwn-dev"
version: "6.0-17"
release: "Debian 4.0 (Etch)"
platforms: ["linux"]
url: "https://new.carta.tech/wnsplx"
---

# wnsplx(3)

simplex method package

*.*

## NAME

*wn\_simplex\_method, wn\_simplex\_loop - simplex method package*

## 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 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 }*

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

*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** *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.*

## SEE ALSO

*wnminv, wnanl, wnnlp*

## 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*