Example 1: Because of a major storm on the East Coast that shut down airports causing a large number of flights to divert inland, Agony Air has 12 planes in Dallas, 9 in Chicago, 7 in St Louis, and 7 in Denver that are needed urgently on the Coast as air operations resume. The basic relocation costs in units of $1,000 are tabled below:
| From \ To | Boston | New York | Washington | Atlanta | Miami |
|---|---|---|---|---|---|
| Dallas | 5 | 4 | 4 | 3 | 5 |
| Chicago | 4 | 4 | 4 | 5 | 6 |
| St Louis | 5 | 4 | 4 | 3 | 6 |
| Denver | 6 | 5 | 5 | 4 | 7 |
Six planes are needed in Boston, 10 in New York, 12 in Washington, 6 in Atlanta, and 6 in Miami. Planes that cannot be supplied from the cities listed above will need to come from West Coast airports at a cost of $11,000 each.
The weather problems have also left pilots in inconvenient locations. There is a shortage of pilots in Miami so planes being sent there will each carry an extra crew at a cost of $3,000. Only three pilot crews are available in Chicago so six of the planes there will require a pilot relocation cost of $2,500.
Set up the transportation problem to decide how to relocate their planes at minimum cost in the grid below. Put the demands at the bottom of the table of costs and the supplies to the right. Note that the grid is not necessarily of the correct size.
Solution: We split the row for Chicago into 2 rows to reflect the difference between the 3 planes with pilot crews and the 6 planes without. We add a row for West Coast airports, a row for demand at the bottom and a column for supply to the right. Note that 5 planes are needed to come from West Coast. Here is the set up of the transportation problem.
| Boston | New York | Washington | Atlanta | Miami | Supply | |
|---|---|---|---|---|---|---|
| Dallas | 5 | 4 | 4 | 3 | 5+3 | 12 |
| Chicago 1 | 4 | 4 | 4 | 5 | 6+3 | 3 |
| Chicago 2 | 4+2.5 | 4+2.5 | 4+2.5 | 5+2.5 | 6+3+2.5 | 6 |
| St Louis | 5 | 4 | 4 | 3 | 6+3 | 7 |
| Denver | 6 | 5 | 5 | 4 | 7+3 | 7 |
| West Coast | 11 | 11 | 11 | 11 | 11+3 | 5 |
| Demand | 6 | 10 | 12 | 6 | 6 | 40 |
Example 2: The Short Stock Company (SSC) has contracted to provide 500, 300, and 400 units of its product to markets A, B and C, respectively, in October, and 400, 300, and 500, respectively, in November. However, they have been a bit over zealous in their marketing in that they have production capacities of only 500 at Plant 1 and 600 at Plant 2 each month.
Their contract allows October’s demands to be fulfilled late by November production with a $100 penalty per item.
The SSC contracts call for a $200 penalty in markets A and C and $250 in B for every unit they are short.
The relevant shipping costs are:
| A | B | C | |
|---|---|---|---|
| Plant 1 | 15 | 20 | 8 |
| Plant 2 | 6 | 12 | 25 |
Formulate the linear program to solve the balanced transportation problem to minimize the shipping and penalty costs for SSC.
Solution: The grid consists of 7 columns representing markets A, B, C in Oct and Nov and the supply, and it consists of 6 rows representing Plant 1 and 2 in Oct and Nov, short times and demand.
| A Oct | B Oct | C Oct | A Nov | B Nov | C Nov | Supply | |
|---|---|---|---|---|---|---|---|
| Plant 1 Oct | 15 | 20 | 8 | 15 | 20 | 8 | 500 |
| Plant 2 Oct | 6 | 12 | 25 | 6 | 12 | 25 | 600 |
| Plant 1 Nov | 15+100 | 20+100 | 8+100 | 15 | 20 | 8 | 500 |
| Plant 2 Nov | 6+100 | 12+100 | 25+100 | 6 | 12 | 25 | 600 |
| Short | 200 | 250 | 200 | 200 | 250 | 200 | 200 |
| Demand | 500 | 300 | 400 | 400 | 300 | 500 | 2400 |