wntrn(3)

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 "trans

portation 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 speci

fied 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

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

WN_INFEASIBLE

than wn_trans_problem.
wn_trans_problem_simplex_improve improves a corner-feasi

ble solution to a transportation problem, spending CPU time

bounded by max_time. The resulting solution is also corner-fea

sible. 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 infor

mation 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 op

timal, 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 solu

tion. 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 indus

trial applications.

SEE ALSO

wnsplx, wnprm, wnmst

REFERENCES

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

tions Research. Holden-Day Inc.

[2] J. Franklin: Methods of Mathematical Economics.

Springer-Verlag.

AUTHOR

Will Naylor

WNLIB August 23, 1998

WNTRN(3)