Here is a common problem that may arise in several forms. We have a commodity that is available at several sources and is needed at several destinations. Suppose, for example, that a company has widgets stockpiled in several warehouses and must ship them to several stores to meet the demands of the customers. The problem is to minimize the shipping costs. Or, on a global scale, suppose that crude oil is available at several ports like Caracas and Valdez and is needed by refineries at others like Rotterdam and Philadelphia. How much oil should we ship from each port to each refinery in order to meet the demands at minimum shipping cost? In general the total supply and total demand may not be the same, and in the oil example there may be political considerations. We may not be allowed to ship Alaskan crude to Yokohama but only to the United States. The actual solution of a problem like this may be very complicated, but to illustrate the ideas let's take a very simple situation where there are only two sources of supply, two of demand, and the total supply is equal to the total demand. Here is a table showing Amalagamated Widgets transportatrion problem.  Inside the table, the numbers in red indicate the cost of shipping a single unit of widgets.

	Store 1 10 units needed	Store 2 20 units needed
Warehouse 1 15 units available	$1	$2
Warehouse 2 15 units available	$3	$5

Each store manager will naturally try to minimize the cost of shipping, so Store 1 will place all of its orders with Warehouse 1, while Store 2, realizing that it can't get all the units it needs from Warehouse 1, will order 15 from Warehouse 1 (all it has available) and the remaining 5 from Warehouse 2. Of course, this doesn't work but neither manager will budge because the cost of shipping has to be added to the final price the store charges the customer. The Chief Operations Officer of the company has an idea. The probem is that the costs of shipping out of Warehouse 2 are too high. Instead of dictating how much should be shipped from each warehouse to each store he decides that he will draw money from total company profits and "subsidize'' the shippping from Warehouse 2 by  $2 per unit shipped. The table now looks to the store managers like this:

	Store 1 10 units needed	Store 2 20 units needed
Warehouse 1 15 units available	$1	$2
Warehouse 2 15 units available	$1	$3

The manager of Store 2 will still insist on ordering 15 units from Warehouse 1 and 5 units from Warehouse 2, but the manager of Store 1 is now indifferent as to where he gets his units since the costs of shipping from the two warehouses is now the same. He is willing to order his 10 units from Warehouse 2. This minimizes the "subsidized" shipping costs but it also really does minimize the true costs of shipping, which are shown in the following table.

	Store 1 10 units needed	Store 2 20 units needed
Warehouse 1 15 units available	$1x0 = $0	$2x15 =$30
Warehouse 2 15 units available	$3x10 = $30	$5x5 = $25

The numbers in black indicate the shipping schedule; nothing from Warehouse 1 to Store 1, 15 from Warehouse 1 to Store 2, 10 from Warehouse 2 to Store 1, and 5 from Warehouse 2 to Store2.
The total cost of meeting the stores' requirements with this shipping schedule is $30 + $30 + $25 = $85. Here is the reason that this is the best you can do: Since 15 units must be shipped out of Warehouse 2 the subsidy of $2 per unit will always reduce the total cost of shipping by exactly $30 no matter what shipping schedule is used. Thus, no matter what shipping schedule is used, the difference between the true cost and the subsidized cost will always be exactly $30. So if the subsidized cost is minimized, so is the true cost


This subsidy method will give the same result if instead of subsidizing the cost of shipping out of a particular warehouse we subsidize the cost of shipping into a particular store and let the warehouse managers decide how much they will ship to each store. With the original costs, both warehouses will want to ship all their units of widgets to Store 1, which is impossible. Suppose, however, we subsidize shipments into Store 2 by $1 per unit. Then Warehouse 2 will still want to ship as much as it can, namely 10 units, to Store 1 because the coast of shipping there is only $3 per unit, which is still $1 less than the subsidized cost of shipping to Store 2. It will have to ship the remaining 5 uits to Store 2. However, Warehouse 1 now is indifferent as to whether it ships to Store 1 or to Store 2 since after the subsidy the shipping costs are the same. Since the requirements of Store 1 are now filled, it is now willing to ship  all 15 of its units to Store 2.  Notice that we get exactly the same shipping schedule.  The COO was brilliant, because there is always a set of subsidies which allows the problem to be solved.

The situation changes slightly if there is an imbalance in supply and demand. If demand exceeds supply we are only allowed to subsidize shipments out of a warehouse; if supply exceeds demand we are only allowed to subsidize shipments into stores. But it remains the case that there is always some system of subsidies that works.
Exercise 1. Solve the problem if a) the demand of Store 1 is increased to 15 units, with no increase in supply, and b) if the supply available in Warehouse 2 is increased by 5 units, with no increase in demand.
Exercise 2. Solve the following transportation problem by the method of subsidies.

	Store 1 10 units needed	Store 2 20 units needed	Store 3 30 units needed
Warehouse 1 15 units available	$1	$3	$2
Warehouse 2 20 units available	$2	$4	$3
Warehouse 3 25 units available	$1	$5	$1

The transportation problem is actually a special case of the linear programming problem but there are also special tools to solve it, like the the subsidy approach.  In the example with which we started the subsidy approach is actually very inefficient. Here is a direct and much faster approach for this problem. Suppose we let   x   be the the number of units to be shipped from Warehouse 1 to Store 1.  There are limitations on x: it can't be  negative or greater than 10. The shipping schedule now looks like this:

	Store 1 10 units needed	Store 2 20 units needed
Warehouse 1 15 units available	X	15-X
Warehouse 2 15 units available	10-X	5+X

The cost, with this shipping schedule, is then  x + 2(15-x) + 3(10-x) + 5(5+x), or  x+85. (Check this!) The best we can do therefore is to set x = 0 which is what we found before; the minimum shipping cost is $85. While this problem is very simple, for a large transportation problem the subsidy method may be much more efficient than a direct (linear programming) approach.