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
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!