Examples: Georgia Crackers Toxic Waste Cleanup
A capacitated trans-shipment problem has a number of
locations, or nodes, that can serve as sources, destinations, or points
en-route for a number of
items.
Not all nodes are connected to all other nodes; all connections are
one-way, so a two-way connection is represented as two one-way ones.
Each connection has a capacity showing the maximum number of items that
can move along that connection, and a cost for each item that moves
along
it. (Think of Internet connections with capacity = bandwidth, or
cargo
holds of ships or planes with capacity = number of items that will
fit.)
A problem is defined by the connections, their capacities and costs,
and the number of items that each node wants to receive or ship
out. The total number shipped out must equal the total number
received.
This is a linear programming problem that uses some gimmicks worked out
by very clever people.
There is one decision variable for each potential link, even if it has
no capacity.
These are arranged in a matrix.
The number of items shipped out from a node is the row total of the
decision variables, and the number received is the column total.
The net, or "total from - total to" is calculated using the row and
column total.
A node that wants to send out items is constrained to have the net
equal to a positive number showing how many to ship out.
A node that wants to be the final destination for items is constrained
to have the net equal to a negative number equal to the number of items
for which
it wants to be the final destination.
A node that can serve only as an en-route point but not as an original
source or final destination is constrained to have the net equal to
zero.
The number of items traveling along a connection is constrained by that
connection's capacity (zero for non-operative connections.)
The objective is to minimize the sum of the product of the number of
items traveling along each connection times the cost for that
connection.
The number of items traveling along each connection
automatically works out to an integer;
it is NOT necessary to use integer programming!