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

# wntrn(3)

transportation problem

## NAME

wn\_trans\_problem, wn\_trans\_problem\_feasible, wn\_trans\_problem\_simplex\_improve - transportation problem

## SYNOPSIS

```
#include <wn/wnspmat.h>
#include <wn/wntrn.h>

wn_trans_problem(&code, &objective, &result,
cost_mat, i_capacities, j_capacities)
int code;
double objective;
wn_sparse_matrix result, cost_mat;
double i_capacities[], j_capacities[];

wn_trans_problem_feasible(&code, &result, cost_mat,
i_capacities, j_capacities)
int code;
wn_sparse_matrix result, cost_mat;
double i_capacities[], j_capacities[];

wn_trans_problem_simplex_improve(&code, &objective,
&delta, &new_result, result, cost_mat, max_time)
int code;
double objective, delta;
wn_sparse_matrix new_result, result, cost_mat;
int max_time;
```

## DESCRIPTION

This package is designed to assist in solving the "transportation problem" easily and efficiently.  The "transportation problem" is the following optimization problem:

CHOOSE *result*\[i\]\[j\] TO MINIMIZE

sum\_over(i,j){ *result*\[i\]\[j\]\**cost\_mat*\[i\]\[j\] }

WHILE SATISFYING THE CONSTRAINTS

for\_all(i){ sum\_over(j){ *result*\[i\]\[j\] } == *i\_capacities*\[i\] }

for\_all(j){ sum\_over(i){ *result*\[i\]\[j\] } == *j\_capacities*\[j\] }

for\_all(i,j){ *result*\[i\]\[j\] \>= 0 }

**wn\_trans\_problem** solves the transportation problem specified by *cost\_mat*, *i\_capacities*, and *j\_capacities*.  The optimal solution appears in *result*; its objective function appears in  *objective*.  *code* is set to **WN\_SUCCESS** if the problem is  solved successfully; if no solution is feasible, *code* is set to **WN\_INFEASIBLE**.  Solving a problem using **wn\_trans\_problem** can be too slow for large problems, that is why the routines below are  provided.

**wn\_trans\_problem\_feasible** finds a feasible solution to the transportation problem specified by *cost\_mat*, *i\_capacities*, and *j\_capacities*.  The solution is placed in *result*.  *code* is set to **WN\_SUBOPTIMAL** if a feasible solution is found; *code* is set to **WN\_INFEASIBLE** otherwise.  This routine is generally much faster than **wn\_trans\_problem**.

**wn\_trans\_problem\_simplex\_improve** improves a corner-feasible solution to a transportation problem, spending CPU time bounded by *max\_time*.  The resulting solution is also corner-feasible.    Repeated application of this routine to a solution will eventually yield the optimal solution.  Setting *max\_time*=**WN\_IHUGE** also yields the optimal solution.  *result* contains the beginning solution. *cost\_mat* specifies the transportation problem to be solve. Note that capacities are unnecessary because this information is already contained in *result*.  The improved solution is placed in *new\_result*.  The objective function of *new\_result* is placed in *objective*; the improvement achieved is placed in *delta*.  *code* indicates the status of the solution; if the solution is optimal, *code*=**WN\_SUCCESS**; if the solution is not optimal, *code*=**WN\_SUBOPTIMAL**.

## RESOURCES

**wn\_trans\_problem** runs with

WORST and AVERAGE CASE:

time = e\*(len\_i+len\_j)\
 stack\_memory = 1\
 dynamic\_memory = e

**wn\_trans\_problem**\_feasible" runs with

WORST CASE:

time = e\*(len\_i+len\_j)\
 stack\_memory = 1\
 dynamic\_memory = e

AVERAGE CASE:

time = e\*log(e)\
 stack\_memory = 1\
 dynamic\_memory = e

"wn\_trans\_simplex\_improve"

WORST and AVERAGE CASE:

time = *max\_time*\*log(e)\
 stack\_memory = 1\
 dynamic\_memory = e

if *max\_time* \< **WN\_IHUGE**.

**wn\_trans\_simplex\_improve** finds the optimum solution if *max\_time* == **WN\_IHUGE**, with

WORST CASE:

time = e\*(len\_i+len\_j)\*log(e)\
 stack\_memory = 1\
 dynamic\_memory = e

The actual time taken depends heavily on the start solution.   Generally, the closer the start solution to optimum, the less time to get to optimum.

In the above, "len\_i" and "len\_j" are the i and j lengths of *cost\_mat*; "e" is the number of entries of *cost\_mat*.

## DIAGNOSTICS

**wn\_trans\_problem** and **wn\_trans\_problem\_feasible** crash if *i\_capacities* and *j\_capacities* do not sum to equal quantities.

**wn\_trans\_problem\_simplex\_improve** crashes if *result* is not corner-feasible.

## BUGS

This *code* is new and has not been tested in large industrial  applications.

## SEE ALSO

wnsplx, wnprm, wnmst

## REFERENCES

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

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

## AUTHOR

Will Naylor