Selected topics in finite mathematics/Transportation problems

Objectives

To minimize the total cost of meeting the required demands based solely upon the supplies available.

Details

Optimization Problem: A problem that seeks to discover either the minimum or maximum value possible

Constraint: An equation in an optimizing problem that must be satisfied.

Linear Program: an optimization problem in which the constraints and objectives are linear.

Transportation Problem: A linear program that can be thought of in terms of suppliers producing goods and demanders receiving the goods.

Northwest Corner Rule: To find a feasible solution "read the chart like a book," start in the top left hand corner.

Examples

1. Consider the situation where two mills A and B are supplied by two farms M and N. Mill A demands 4 trucks of grain while mill B demands 6 trucks of grain. Farm M can produce 5 trucks of grain and farm N can produce 6 trucks of grain. Due to the location of the farms and mills, the transportation costs also vary: farm M can ship to mills A and B with costs 2 and 3 respectively, while farm N can ship to mills A and B with costs 1 and 4 respectively.

Solution

Step 1		Step 2		Step 3		Step 4
A B  Supply  M     2       3   5 N     1       4   6  Demand  4 7		A B  Supply  M     2 4       3 1   5 N     1       4 6   6  Demand  4 7		A B  Supply  M     2 4 -     3 1 + 5 N     1 +     4 6 - 6  Demand  4 7		A B  Supply  M     2       3 5   5 N     1 4       4 2   6  Demand  4 7

Step 1: Write the information from the problem into a tableau.

Step 2: The initial feasible solution from the Norhtwest Corner Rule.

Step 3: This is the only cycle we can possibly use to shift the grain transportation from one farm to another, without disrupting the supply and demand: we must continue to satisfy these. The indicator is for cell (N,A) is 1 − 2 + 3 − 4 = −2. This is negative, and so is advantageous. Pushing grain through this cycle involves increasing some of the cells and decreasing others. In fact we can push four goods through this cycle until one of the cells becomes zero. At this point the cycle is broken.

Step 4: This is the optimal solution. It has total cost 0+15+4+8=24. To verify that it is optimal we would need to check to see that all indicators are positive. In fact there is only one indicator, and its value is 2.

Caution: The following example may appear formidable because of its length. Consider that it is really four examples in one, because we push goods through a cycle four times: each time we are rearranging the transportation routes to reduce the total cost.

2. Consider the scenario where there are now three stores A, B, C trying to sell goods supplied by M, N, and L. The stores can sell 2, 3, and 7 goods respectively. The suppliers can supply 3, 4, and 5 goods respectively. The transportation cost for M to ship to the stores are 1, 5, and 2 respectively. For N the transportation costs are 2, 1, and 5 respectively. And lastly for L these costs are 4, 4, and 6 respectively.

Solution part 1: Initial Solution

We first organize all the information from the problem into the tableau below.

Initial Setup
	A	B	C	Supply
M	1	5	2	3
N	2	1	5	4
L	4	4	6	5
Demand	2	3	7

Next using the Northwest Corner Rule we obtain the initial feasible solution shown below. Note in particular that every store has it's demand met, and every supplier has shipped all their goods.

Initial Solution
	A	B	C	Supply
M	1 2	5 1	2	3
N	2	1 2	5 2	4
L	4	4	6 5	5
Demand	2	3	7

Solution part 2: Improving the solution

Now we find the indicators for each of the blank entries, asking the question "How will our costs change if we have this supplier ship goods to this store?". The cycles for all four indicators are shown below. We are looking for negative indicators, as these would decrease our total cost. Positive indicators we may ignore.

• (M,C): 2 − 5 + 1 − 5 = −7 (A maximum of 1 good can be pushed through this cycle)
• (N,A): 2 − 1 + 5 − 1 = 5 (A maximum of 2 goods can be pushed through this cycle) (Confer with example 3 below)
• (L,A): 4 − 1 + 5 − 1 + 5 −6 = 6 (A maximum of 2 goods can be pushed through this cycle) (Confer with example 3 below)
• (L,B): 4 − 1 + 5 − 6 = 2 (A maximum of 2 goods can be pushed through this cycle)

Illustration of cycles corresponding to each indicator
A B C  Supply  M     1 2       5 1 -     2 + 3 N     2       1 2 +     5 2 - 4 L     4       4       6 5   5  Demand  2 3 7		A B C  Supply  M     1 2 -     5 1 +     2   3 N     2 +     1 2 -     5 2   4 L     4       4       6 5   5  Demand  2 3 7		A B C  Supply  M     1 2 -     5 1 +     2   3 N     2       1 2 -     5 2 + 4 L     4 +     4       6 5 - 5  Demand  2 3 7		A B C  Supply  M     1 2       5 1       2   3 N     2       1 2 -     5 2 + 4 L     4       4 +     6 5 - 5  Demand  2 3 7

Only one of these indicators is advantageous (that is, negative), so we use the cycle corresponding to indicator (M,C). This gives us:

Improved Solution
	A	B	C	Supply
M	1 2	5	2 1	3
N	2	1 3	5 1	4
L	4	4	6 5	5
Demand	2	3	7

Solution part 3: Improving the solution

Once again, we must check all the indicators:

• (M,B): 5 − 2 + 5 − 1 = 7 (A maximum of 1 good can be pushed through this cycle)
• (N,A): 2 − 1 + 2 − 5 = −2 (A maximum of 1 good can be pushed through this cycle)
• (L,A): 4 − 1 + 2 − 6 = −1 (A maximum of 2 goods can be pushed through this cycle)
• (L,B): 4 − 1 + 5 − 6 = 2 (A maximum of 3 goods can be pushed through this cycle)

Illustration of cycles corresponding to each indicator
A B C  Supply  M     1 2       5 +     2 1 - 3 N     2       1 3 -     5 1 + 4 L     4       4       6 5   5  Demand  2 3 7		A B C  Supply  M     1 2 -     5       2 1 + 3 N     2 +     1 3       5 1 - 4 L     4       4       6 5   5  Demand  2 3 7		A B C  Supply  M     1 2 -     5       2 1 + 3 N     2       1 3       5 1   4 L     4 +     4       6 5 - 5  Demand  2 3 7		A B C  Supply  M     1 2       5       2 1   3 N     2       1 3 -     5 1 + 4 L     4       4 +     6 5 - 5  Demand  2 3 7

While the indicators (N,A) and (L,A) are different, the total saved will be the same. We'll push into (L,A):

Improved Solution
	A	B	C	Supply
M	1	5	2 3	3
N	2	1 3	5 1	4
L	4 2	4	6 3	5
Demand	2	3	7

Solution part 4: Improving the solution

But we're still not done! Let's check the indicators again:

• (M,A): 1 − 2 + 6 − 4 = 1 (A maximum of 2 goods can be pushed through this cycle)
• (M,B): 5 − 2 + 5 − 1 = 7 (A maximum of 3 goods can be pushed through this cycle)
• (N,A): 2 − 5 + 6 − 4 = −1 (A maximum of 1 good can be pushed through this cycle)
• (L,B): 4 − 1 + 5 − 6 = 2 (A maximum of 3 goods can be pushed through this cycle)

Illustration of cycles corresponding to each indicator
A B C  Supply  M     1 +     5       2 3 - 3 N     2       1 3     5 1 4 L     4 2 -     4       6 3 + 5  Demand  2 3 7		A B C  Supply  M     1       5 +     2 3 - 3 N     2       1 3 -     5 1 + 4 L     4 2       4       6 3 5  Demand  2 3 7		A B C  Supply  M     1       5       2 3   3 N     2 +     1 3     5 1 - 4 L     4 2 -     4       6 3 + 5  Demand  2 3 7		A B C  Supply  M     1       5       2 3   3 N     2       1 3 -     5 1 + 4 L     4 2       4 +     6 3 - 5  Demand  2 3 7

Pushing one good through this cycle, the one with indicator (N,A), we obtain:

Improved Solution
	A	B	C	Supply
M	1	5	2 3	3
N	2 1	1 3	5	4
L	4 1	4	6 4	5
Demand	2	3	7

Solution part 5: Verifying optimality

Hoozah! We're finally done, by verifying that all the indicators are now positive:

• (M,A): 1 − 2 + 6 − 4 = 1
• (M,B): 5 − 1 + 2 − 4 + 6 − 2 = 5
• (N,C): 5 − 6 + 4 − 2 = 1
• (L,B): 4 − 4 + 2 − 1 = 1

Illustration of cycles corresponding to each indicator
A B C  Supply  M     1 +     5       2 3 - 3 N     2 1       1 3     5   4 L     4 1 -     4       6 4 + 5  Demand  2 3 7		A B C  Supply  M     1       5 +     2 3 - 3 N     2 1 +     1 3 -     5   4 L     4 1 -     4       6 4 + 5  Demand  2 3 7		A B C  Supply  M     1       5       2 3   3 N     2 1 -     1 3     5   + 4 L     4 1 +     4       6 4 - 5  Demand  2 3 7		A B C  Supply  M     1       5       2 3   3 N     2 1 +     1 3 -     5   4 L     4 1 -     4 +     6 4 5  Demand  2 3 7

Hence the final solution is given below, with a total cost of 6+2+3+4+24=39

Optimal Solution
	A	B	C	Supply
M	1	5	2 3	3
N	2 1	1 3	5	4
L	4 1	4	6 4	5
Demand	2	3	7

3. In the example above, how were the cycles for the indicators found?

Solution

Consider the initial solution from example 2. The costs don't matter, so they were omitted. Below is one method to find the cycles corresponding to indicators (N,A) and (L,A).

Indicator (N,A)
Step 1		Step 2		Step 3		Corresponding tableau
Starting graph		Add an edge		Find the cycle		A B C  Supply  M     2 -     1 + 3 N     +     2 -     2   4 L     5   5  Demand  2 3 7

Indicator (L,A)
Step 1		Step 2		Step 3		Corresponding tableau
Starting graph		Add an edge		Find the cycle		A B C  Supply  M     2 -     1 + 3 N     2 -     2 + 4 L     +     5 - 5  Demand  2 3 7

Step 1: Draw the graph that represents the current solution. The suppliers are listed as vertices in one column, the demanders are listed as vertices in another column. Draw an edge from each supplier to the demanders being supplied.

Step 2: Draw a dotted edge to indicate the new supply route you would like to introduce.

Step 3: There is now a unique cycle, identified in blue. A "+" represents a supply route that must be increased, a "−" represents a supply route that must be decreased.

Step 4: If you were going to use this indicator, you would increase/decrease supply routes until it is impossible to do so: this would eliminate an edge from the graph. (The elimination of this edge occurs when a cell is reduced to zero in the tableau: no goods are being shipped on that supply route anymore)