MTH 242 – OPERATIONS RESEARCH CSMJACOB

HANDOUT #5 – THE TRANSPORTATION PROBLEM

The Transportation Problem

- a special type of linear programming problem that can be solved by using more efficient computational
procedures than the simplex method;
- concerned with selecting routes in a product-distribution network among manufacturing plants and
distribution warehouses or among regional distribution warehouses and local distribution outlets

In applying the transportation method, management is searching for a distribution route which will minimize
the total cost of transporting goods from the source to the destination. The transportation problem was first solved
using the simplex method developed by George B. Dantzig. In 1953, William W. Cooper and Abraham Charnes
developed the stepping-stone method, a special-purpose algorithm for solving the transportation problem. Subsequent
improvements led to the computationally easier modified distribution (MODI)method.

Illustration:
Bass Gravel Company has received a contract to supply gravel for three new road projects located in the towns of
Greenville, Fountain, and Ayden. Construction engineers have estimated the amounts of gravel which will be needed at
three road construction projects:

Weekly requirement
Project Location (truckloads)
A Greenville 72
B Fountain 102
c Ayden 41
Total 215

The Bass Gravel Company has three gravel plants located in the towns of Kinston, Wilson, and Bethel. The gravel
required for the construction projects can be supplied by these three plants. Bass’s chief dispatcher has calculated the
amounts of gravel which can be supplied by each plant:

Amount available/week
Plant Location (truckloads)
W Kinston 56
X Wilson 82
Y Bethel 77
Total 215

The given values give rise to a balanced condition, where supply is equal to demand. The company has computed the
delivery costs from each plant to each project site:

Cost per truckload ($)

From To project A To project B To project C
Plant W 4 8 8
Plant X 16 24 16
Plant Y 8 16 24

MTH 242/Handout 4/CSMJACOB Page | 1

Any transportation problem is essentially a network flow problem. A network is composed of points (called nodes) and
lines (called arcs) which join pairs of nodes. The network flow for the Bass Gravel Company problem is shown below:

Project A (Greenville) 72 loads required

Plant W (Kinston) 56 loads available

$4

Project B (Fountain) 102 loads required

$8 $16
Plant X (Wilson) 82 loads available
$24

$8 $8
$16
$18 Project C (Ayden) 41 loads required

$24
Plant Y
(Bethel) 77

Solution:
1. Set up the transportation tableau, which serves the same basic purpose as the simplex tableau. It provides a
framework for presenting all the relevant data in a concise manner and facilitates the search for progressively
better solutions.

Destination points

To
Project A Project B Project C Plant Capacity
From
Sources WA 4 WB 8 WC 8 Capacity constraints or
of Plant W 56 rim requirements for the
supply XA 16 XB 24 XC 16 rows
Plant X 82
YA 8 YB 16 YC 24
Plant Y 77

Project requirements 72 102 41 215

Demand constraints or rim
requirements for the columns

The cells inside the table represent the alternative source-to-destination assignments that could be made. Each
cell consists of the following parts:

Cell identification symbol representing transportation cost per truckload from

the combination “Plant W to Project A” WA 4 plant W to project A

number of truckloads shipped from plant

W to project A (value ≥ 0); A value = 0
means that no quantity is shipped from
plant W to project A

MTH 242/Handout 4/CSMJACOB Page | 2

2. Develop an initial solution.
A. The Northwest Corner Rule
It starts at the upper-left-hand corner (northwest corner), exhausting the available supply for each row before moving
down to the next row, and exhausting the rim requirement for a column before moving on to the next column on the
right. Once all the available supply have been exhausted, check to see that all rim requirements have been satisfied.

The initial solution using the northwest corner rule is shown below:

To
Project A Project B Project C Plant Capacity
From
WA 4 WB 8 WC 8
Plant W 56
56
XA 16 XB 24 XC 16
Plant X 82
16 66
YA 8 YB 16 YC 24
Plant Y 77
36 41
Project requirements 72 102 41 215

The initial solution has the unused squares WB, WC, XC, and YA. Thus, since no quantity is shipped between the points
in each unused square, they are not in the initial solution outlined below:
From To Quantity,
plant project truckloads per week
W A 56
X A 16
X B 66
Y B 36
Y C 41

- The solution shown above is feasible since all rim requirements have been met, i.e. the sum of each row or
column is equal to its rim requirement.
- The use of the northwest corner rule always results in a stair-step appearance of the initial solution.
- For any feasible solution, the number of used squares must be equal to the total number of rim
requirements minus 1. The problem above has a total of 6 rim requirements – 3 for the rows and 3 for the columns.
Thus,
Used squares = 6 – 1 = 5

Evaluating the cost of the initial solution:

Source-destination Quantity Unit cost Total cost

combination shipped X ($) = ($)
WA 56 x 4 = 224
XA 16 x 16 = 256
XB 66 x 24 = 1,584
YB 36 x 16 = 576
YC 41 x 24 = 984
Total transportation cost $3,624

MTH 242/Handout 4/CSMJACOB Page | 3

B. The Least-Cost Method or the Minimum-Cost Method
This method involves assigning the highest possible quantity to the cell with the smallest unit cost in the entire
tableau. (Ties are broken arbitrarily.) Cross out a satisfied column or row, such that only the unit costs in the uncrossed-
out column or row will be considered in determining the lowest unit cost for the next allocation. After adjusting the
supply and demand for all uncrossed-out columns and rows, the procedure is repeated until all the rim requirements
have been satisfied.
Using the Bass Gravel Company example to illustrate this method:

To
Project A Project B Project C Plant Capacity
From
WA 4 WB 8 WC 8
Plant W 56
56
XA 16 XB 24 XC 16
Plant X 82
41 41
YA 8 YB 16 YC 24
Plant Y 77
16 61
Project requirements 72 102 41 215

Step 1. The lowest unit cost ($4) is found in cell WA, and the maximum quantity that can be assigned to this
variable is 56. With this allocation, row 1 will be “crossed out”.
Step 2. Among the unit costs in the two remaining rows, the lowest ($8) can be found in cell YA, and the
maximum quantity that can be assigned to this variable is 16. With this allocation, column 1 will also be crossed
out.
Step 3.Among the remaining cells, both XC and YB have the lowest unit costs. This tie can be broken arbitrarily.
Suppose XC is chosen first, and allocated the maximum quantity of 41, then this would cross out column 3.
Step 4.Between the two remaining variables, YB has the lowest unit cost of $16, earning for it the maximum
allowable allocation of 61, leaving 41 for cell XB, and completing the allocation process.
Step 5.Compute the total transportation cost for this initial solution as:
Total transportation cost = (56 x 4) + (16 x 8) + (41 x 24) + (61 x 16) + (41 x 16)
= $2968
This cost is better than the initial cost using the northwest corner rule, which was $3624.

C. Vogel’s Approximation Method (VAM)

VAM is an investigative method and usually provides a better starting solution than the two other methods
previously discussed. It requires a little more effort, but results in a better solution that is close to optimality, if not
optimal yet.
Again, the previous problem on Bass Gravel Company will be used to illustrate this method.

Step1.Evaluate a penalty cost for each row (column) by subtracting the smallest cost element in the row
(column) from the next smallest cost element in the same row (column).

Step 2.Select the row or column with the highest penalty cost. Breaking ties can be done arbitrarily. However,
different solutions result from different choices, and some are invariably better (lower cost) than the others.
Thus, it would be wise to break a tie by choosing the cell with the smallest cost element.
The highest penalty is 8, occurring in two rows and two columns. Among these four candidates, row 3
contains the smallest unit cost at $8, thus the entering variable will be chosen from among the cells in this row.

MTH 242/Handout 4/CSMJACOB Page | 4

 To
Project A Project B Project C Plant Capacity Penalty
From
WA 4 WB 8 WC 8
Plant W 56 4 0 - - -
56 2nd
XA 16 XB 24 XC 16
Plant X 82 8 8 8 24 -
41 4th 41 3rd
YA 8 YB 16 YC 24
Plant Y 77 8 8 8 16 -
72 1st 5 5th
Project requirements 72 102 41 215

4 8 8
- 8 8
Penalty - 8 8
- 8 -
- 24 -

Step 3.Allocate as much as possible to the variable with the least cost in the row or column with the highest
penalty cost, “crossing out” satisfied rows or columns. Such rows or columns will no longer be computed for
penalties.
The cell with the least cost element in row 3 is YA, thus the maximum quantity of 72 will be allocated to
it, crossing out column 1 in the process, as it has been fully satisfied.

Step 4. Repeat steps 1, 2, and 3 until all requirements have been met.
i. Row 2 and 3, as well as columns 2 and 3 all have the same highest penalty of 8. Although the ties can
be broken arbitrarily, it is wiser to choose the row or column that contains the cell with the lowest cost
element. This will lead us to choose between columns 2 and 3 which both contain the smallest remaining cost
element of
$8. Since cell WB in column 2 can accommodate more than WC in column 3, the next entering cell will be WB, to
which 56 will be allocated. This effectively crosses out row 1.
ii. Among the four tied with penalty values = 8, row 2 and columns 2 and 3 contain the cell with the
least cost element of $16. In row 2 and column 3, cell XC can be allocated with a maximum of 41 truckloads,
while in column 2, cell YB can be assigned a maximum of 5 truckloads. Thus, cell XC is the entering variable that
will be used to break the tie. Allocating 41 truckloads to cell XC effectively crosses out column 3.
Iii. Row 2 has the highest penalty of 24, leading us to allocate the remaining 41 truckloads to cell XB, and
crossing out Row 2 in the process.
iv. The final allocation will be 5 truckloads to cell YB, as this will balance out the remaining rim
requirements.

Step 5.Compute total transportation cost for the solution.

Total transportation cost = (72 x 8) + (56 x 8) + (41 x 24) + (5 x 16) + (41 x 16) = $2744

This initial cost is the best among the three initialization methods used.

MTH 242/Handout 4/CSMJACOB Page | 5

3. Test the solution for improvement.
In determining whether the solution is the best, or least-cost, solution, each unused square in the tableau is
examined to see whether it is more desirable to move a shipment into one of them.

A. The Stepping-stone Method

The used squares (containing the circled values) are said to be in solution(representing the basic variables) and
will be referred to as stone squares. Evaluating an unused square involves answering the question “What would happen
if one truckload of gravel were tentatively shipped or assigned to an unused square?” If the tentative assignment results
in a favorable effect (reduction of cost), the unused square evaluated becomes a potential candidate for entering the
next solution. (Note: This is similar to examining the Cj – Zjrow in the simplex method to determine which variable should
enter the product mix.)

To illustrate, the initial solution resulting from the northwest-corner rule method will be used:

To
Project A Project B Project C Plant Capacity
From
WA 4 WB 8 WC 8
Plant W 56
56 – +
XA 16 XB 24 XC 16
Plant X 82
16 + 6 6–
YA 8 YB 16 YC 24
Plant Y 77
36 41
Project requirements 72 102 41 215

The net change in costs, referred to as the improvement index, resulting from the closed path drawn above is computed
as follows:
Addition to cost: From plant W to project B $ 8
(“+“ squares) From plant X to project A 16 $24

Reduction in cost: From plant W to project A $ 4

( “–“ squares) From pant X to project B 24 – 28
-$4
Using an equation to compute the same above:
WB improvement index = WB – WA + XA – XB
= 8 – 4 + 16 – 24
= –$4
This value means that for every truckload shipped from plant W to project B, total transportation costs would be
reduced by $4. Thus, this square is a potential candidate to enter the next improved solution.
Evaluating the unused square WC will result in the closed path between stone squares as shown below:
WC improvement index:
To =WC – WA + XA – XB + YB - YC
Project A Project B Project C Plant Capacity
From = 8 – 4 + 16 – 24 + 16 - 24
WA 4 WB 8 WC 8 = –$12
Plant W 56
56 – + XC improvement index:
XA 16 XB 24 XC 16 = XC – XB + YB - YC
Plant X 82
16 + 66 – = 16 – 24 + 16 – 24 = –$16
YA 8 YB 16 YC 24 YA improvement index:
Plant Y 77
36 + 41 – = YA – YB + XB – XA
Project requirements 72 102 41 215 = 8 – 16 + 24 – 16 = $0

MTH 242/Handout 4/CSMJACOB Page | 6

The tableau below shows the current (initial) solution and the improvement indices for each unused square:
To
Project A Project B Project C Plant Capacity
From
WA 4 WB 8 WC 8
Plant W 56
56 -4 -12
XA 16 XB 24 XC 16
Plant X 82
16 66 -16
YA 8 YB 16 YC 24
Plant Y 77
0 36 41
Project requirements 72 102 41 215

B. The MODI Method

The modified distribution (MODI) method is similar to the stepping-stone method except that it provides a more
efficient means for computing the improvement indices for the unused squares. It requires tracing only one closed path
(as compared to the various closed paths drawn using the stepping-stone method).
To illustrate, the Same Bass Gravel Company problem will be solved, with the initial solution still obtained by the
use of the northwest corner rule. Values for each row (Ri) and each column (Kj) are assigned as shown below:

Kj
Ri K1 K2 K3
To
Project A Project B Project C Plant Capacity
From
WA 4 WB 8 WC 8
R1 Plant W
56
56
XA 16 XB 24 XC 16
R2 Plant X
16 66
82
YA 8 YB 16 YC 24
R3 Plant Y
36 41
77

Project requirements 72 102 41 215

For identification purposes, let Cijrepresent the cost in square ij (the square in the intersection of row i and column j),
computed as
Cij = Ri + Kj
The formula above is applied only to the stone squares in a particular solution. Thus, for the five stone squares in the
solution:

R1 + K1 = C11 R1 + K 1 = 4
R2 + K1 = C21 R2 + K1 = 16
R2 + K2 = C22 R2 + K2 = 24
R3 + K2 = C32 R3 + K2 = 16
R3 + K3 = C33 R3 + K3 = 24

MTH 242/Handout 4/CSMJACOB Page | 7

Since there are 6 unknowns and only five equations, this system of equations has several solutions. To find a particular
solution, let R1 = 0. (Any value for any row or column variable could have been assigned.) Thus, if R1= 0:

0 + K1 = 4 R2 + 4 = 16 12 + K2 = 24 R3 + 12 = 16 4 + K3 = 24
K1 = 4 R2 = 12 K2 = 12 R3 = 4 K3 = 20

Thus, using the values computed, the initial tableau is as follows:

Kj
Ri K1=4 K2=12 K3=20
To
Project A Project B Project C Plant Capacity
From
WA 4 WB 8 WC 8
R1=0 Plant W
56 -4 -12
56
XA 16 XB 24 XC 16
R2=12 Plant X 16 66 -16 82
YA 8 YB 16 YC 24
R3=4 Plant Y 0 36 41 77
Project requirements 72 102 41 215

To compute the improvement index for any unused square, the following formula is used:

Improvement index = Cij -Ri - Kj

Using the formula above, the improvement indices for the unused squares will be computed as shown below:

Unused Cij - Ri - Kj Improvement

square index
12 (WB) 8 – 0 – 12 -4
13 (WC) 8 – 0 – 20 -12
23 (XC) 16 – 12 – 20 -16
31 (YA) 8–4–4 0

Step 4. Develop the improved solution.

Determining the route that would reduce cost the most involves choosing the unused square with the most negative
improvement index to enter the next solution. This is represented by square XC, with an index of -$16. Using this route
will reduce cost by $16 per truckload assigned to it.
A. Using the stepping-stone method, and looking at the closed path taken for square XC below:

XB 24 XC 16
66 – +
YB 16 YC 24
36 + 41 –

The maximum quantity that Bass can ship from plant X to project C is found by determining the smallest stone in a
negative position on the closed path. The closed path for square XC has negative corners at squares XB and YC, and the
smaller of these two stones is 41 truckloads per week. To obtain the improved solution, shift (add) 41 truckloads to a

MTH 242/Handout 4/CSMJACOB Page | 8

positive square, and take away (subtract) 41 truckloads from a negative square. Thus, the improved solution for the
closed path involved is shown below:
XB 24 XC 16
25 41
YB 16 YC 24
77
This leads to the second tableau showing the improved solution:
Total transportation cost:
To = (56)(4) +(16)(16) +(25)(24) +
Project A Project B Project C Plant Capacity
From (41)(16) +(77)(16) = $2,968
WA 4 WB 8 WC 8
Plant W 56
56 -4 4 or
XA 16 XB 24 XC 16
Plant X 82
16 25 41 New cost = Old cost + (number of
YA 8 YB 16 YC 24 added units in the entering cell x
Plant Y 77
0 77 16 improvement index)
Project requirements 72 102 41 215 = $3624 + (41 x -16)
= $2968
Going back to step 3 and evaluating the improvement indices of the unused squares:
Improvement index of square WB = WB – WA + XA – XB = 8 – 4 + 16 – 24 = –
$4 Improvement index of square WC =
WC – WA + XA – XC = 8 – 4 + 16 – 16 = $4 Improvement index of square YA =
YA – YB + XB – XA = 8 – 16 + 24 – 16 = $0
Improvement index of square YC = YC – XC + XB – YB = 24 – 16 + 24 – 16 =
$16
The improvement indices in the previous page show a negative value only for square WB, with the closed path below:
WA 4 WB 8
56 – +
XA 16 XB 24
16 + 25 –
Since the smallest stone in the negative position is 25, the improved solution is shown below:
To Total transportation cost:
Project A Project B Project C Plant Capacity
From = (31)(4) +(25)(8) +(41)(16) +
WA 4 WB 8 WC 8 (41)(16) +(77)(16) = $2,868
Plant W 56
31 25 4
XA 16 XB 24 XC 16 or
Plant X 82
41 4 41
YA 8 YB 16 YC 24 Total transportation cost :
Plant Y 77
-4 77 12 = $2968 + (25 x -4)
Project requirements 72 102 41 215 = $2868

Going back to step 3 and evaluating the improvement indices of the unused squares:
Improvement index of square WC = WC – WA + XA – XC = 8 – 4 + 16 – 16 = $4
Improvement index of square XB = XB – XA + WA – WB = 24 – 16 + 4 – 8 = $4
Improvement index of square YA = YA – YB + WB – WA = 8 – 16 + 8 – 4 = –$4
Improvement index of square YC = YC – YB + WB – WA + XA - XC = 24 – 16 + 8 – 4 + 16 – 16 = $12

MTH 242/Handout 4/CSMJACOB Page | 9

The improvement indices above show a negative value only for square YA, with the closed path below:
WA 4 WB 8
31 – 25 +
XA 16 XB 24
41
YA 8 YB 16
+ 77 –

Since the smallest stone in the negative position is 31, the improved solution is shown below:

To Total transportation cost:

Project A Project B Project C Plant Capacity
From = (56)(8) +(41)(16) +(41)(16) +
WA 4 WB 8 WC 8 (31)(8) +(46)(16) = $2,744
Plant W 56
4 56 8
XA 16 XB 24 XC 16 or
Plant X 82
41 0 41
YA 8 YB 16 YC 24 Total transportation cost:
Plant Y 77
31 46 16 = $2868 + (31 x -4)
Project requirements 72 102 41 215 = $2744

Going back to step 3 and evaluating the improvement indices of the unused squares:
Improvement index of square WA = WA – YA + YB – WB = 4 – 8 + 16 – 8 = $4
Improvement index of square WC = WC – XC + XA – YA + YB - WB = 8 – 16 + 16 – 8 + 16 – 8 =
$8 Improvement index of square XB = XB – XA + YA – YB = 24 – 16 + 8 – 16 = $0
Improvement index of square YC = YC – XC + XA – YA = 24 – 16 + 16 – 8 = $16

Since there are no more negative improvement indices, the optimal routes for Bass Gravel Company are as follows:

Shipping Quantity Unit cost Total cost

assignments shipped x ($) = ($)
WB 56 x 8 = 448
XA 41 x 16 = 656
XC 41 x 16 = 656
YA 31 x 8 = 248
YB 46 x 16 = 736
Total transportation cost $2,744

B. Using the MODI Method, and determining the closed path taken for unused square XC below:

XB 24 XC 16
66 – +
YB 16 YC 24
36 + 41 –

MTH 242/Handout 4/CSMJACOB Page | 10

Letting square XC into the improved solution:

Kj
Ri K1=4 K2=12 K3=4
To
Project A Project B Project C Plant Capacity
From
WA 4 WB 8 WC 8
R1=0 Plant W
56 -4 4
56
XA 16 XB 24 XC 16
R2=12 Plant X 16 25 41 82
YA 8 YB 16 YC 24
R3=4 Plant Y 0 77 16 77
Project requirements 72 102 41 215

Letting square WB into the improved solution:

Kj
Ri K1=4 K2=8 K3=4
To
Project A Project B Project C Plant Capacity
From
WA 4 WB 8 WC 8
R1=0 Plant W
31 25 4
56
XA 16 XB 24 XC 16
R2=12 Plant X 41 4 41 82
YA 8 YB 16 YC 24
R3=8 Plant Y -4 77 12 77
Project requirements 72 102 41 215

Letting square YA into the improved solution:

Kj
Ri K1=0 K2=8 K3=0
To
Project A Project B Project C Plant Capacity
From
WA 4 WB 8 WC 8
R1=0 Plant W
4 56 8
56
XA 16 XB 24 XC 16
R2=16 Plant X 41 0 41 82
YA 8 YB 16 YC 24
R3=8 Plant Y 31 46 16 77
Project requirements 72 102 41 215

MTH 242/Handout 4/CSMJACOB Page | 11

Since there are no more negative improvement indices, the optimal routes for Bass Gravel Company are as follows:

Shipping Quantity Unit cost Total cost

assignments shipped x ($) = ($)
WB 56 x 8 = 448
XA 41 x 16 = 656
XC 41 x 16 = 656
YA 31 x 8 = 248
YB 46 x 16 = 736
Total transportation cost $2,744

Alternative Optimal Solutions

Examining the last set of improvement indices prior to determining optimality, one can observe that the
improvement index of square XB is $0. This means that the route XB can be brought into the solution, altering the
shipping assignments, but resulting in the same optimal cost. To illustrate, suppose route XB is brought into the solution,
this would result in the tableau shown below:

To Total transportation cost:

Project A Project B Project C Plant Capacity
From =(56)(8) +(41)(24) +(41)(16) +
WA 4 WB 8 WC 8 (72)(8) +(5)(16) = $2,744
Plant W 56
4 56 8
XA 16 XB 24 XC 16 or
Plant X 82
0 41 41
YA 8 YB 16 YC 24 Total transportation cost:
Plant Y 77
72 5 16 = $2744 + (41 x 0)
Project requirements 72 102 41 215 = $2744

Improvement index of square WA = WA – YA + YB – WB = 4 – 8 + 16 – 8 = $4

Improvement index of square WC = WC – WB + XB – XC = 8 – 8 + 24 – 16 = $8
Improvement index of square XA = XA – YA + YB – XB = 16 – 8 + 16 – 24 = $0
Improvement index of square YC = YC – XC + XB – YB = 24 – 16 + 24 – 16 =
$16

The existence of alternative optimal solutions gives valuable flexibility to the management of Bass Gravel Company. In
this illustration, project A can be supplied either by plant Y fully, or by a combination of plant X and Y. If, for some
reason, it would be difficult to transport the gravel from plant X to project Y, then, at the same minimum cost, the route
can be altered so that only plant Y has to supply project A.

MTH 242/Handout 4/CSMJACOB Page | 12

The Transportation Problem (demand does not equal supply)

CASE 1: DEMAND LESS THAN SUPPLY

Consider again the Bass Gravel Company problem, but suppose that plant W has a capacity of 76 truckloads per
week rather than 56. The company would be able to supply 235 truckloads per week. However, the project
requirements remain the same. Using the northwest corner rule to establish an initial solution, and assigning a dummy
project to balance out the demand with the supply,

To
Project A Project B Project C Dummy D Plant Capacity Total cost = (72)(4) + (4)
From
0 (8) + (82)(24) + 16)(16) +
WA 4 WB 8 WC 8
Plant W 76 (41)(24) + (20)(0)
72 4
= $3,528
XA 16 XB 24 XC 16 0
Plant X 82
82
YA 8 YB 16 YC 24 0
Plant Y 77
16 41 20
235
Project requirements
72 102 41 20 235

The dummy project (with distribution costs of 0) serves the same purpose as the slack variable in the simplex method.
Solving the problem using the steps discussed previously, the optimal solution below is obtained:

To
Project A Project B Project C Dummy D Plant Capacity
From
0 Total cost = (76)(8) + (21)
WA 4 WB 8 WC 8
Plant W 76 (24) + (41)(16) + (20)(0) +
76
(72)(8) + (5)(16)
XA 16 XB 24 XC 16 0
Plant X 82 = $2,424
21 41 20
YA 8 YB 16 YC 24 0
Plant Y 77
72 5
235
Project requirements
72 102 41 20 235

The solution above shows a shipment of 20 truckloads from plant X to the dummy project. This means that plant X will
have an excess supply of 20 truckloads which will not really be shipped anywhere. With this information, the decision-
maker knows not only the optimal shipping program, but also the plant which should not be utilized at full capacity.

CASE 2: DEMAND GREATER THAN SUPPLY

The unbalanced case of demand being greater than supply, in reference to the Gravel Bass problem, would
occur when the customers (the projects) require more gravel than the Bass Gravel Company plants can supply.
Referring to the same problem, assume that project A will require 10 additional truckloads per week and that project C
estimates additional requirements of 20 truckloads. The total project requirements now would be equal to 245
truckloads, as opposed to the 215 available from the plants. To balance the requirements, a dummy plant is set up
having a capacity that is exactly equal to the additional demand (30 truckloads). The distribution costs from this plant
are equal to zero, since no actual deliveries will be made from this dummy plant.
The initial solution to the unbalanced problem (demand > supply) is shown below:
MTH 242/Handout 4/CSMJACOB Page | 13
 To
Project A Project B Project C Plant Capacity
From
WA 4 WB 8 WC 8
Plant W 56 Total cost = (56)(4) + (26)(16) + (56)(24)
56
+ (46)(16) + (31)(24) + (30)(0)
XA 16 XB 24 XC 16
Plant X 82 = $3,464
26 56
YA 8 YB 16 YC 24
Plant Y 77
46 31
Dummy 0 0 0
30
30
245
Project requirements
82 102 61 245

The optimal tableau is shown below:

To
Project A Project B Project C Plant Capacity
From
WA 4 WB 8 WC 8 Total cost = (56)(8) + (21)(16) + (61)(16)
Plant W 56 + (61)(8) + (16)(16) + (30)(0)
56
XA 16 XB 24 XC 16 = $2,504
Plant X 82
21 61
YA 8 YB 16 YC 24
Plant Y 77
61 16
Dummy 0 0 0
30
30
245
Project requirements
82 102 61 245

Such an unbalanced case implies that one or more of the projects will not have its requirements satisfied. In this case,
the optimal solution indicates that project B will be short by 30 truckloads per week, as it receives 30 from the dummy
plant. This method, however, does distribute all available gravel at the lowest transportation cost for the Bass Gravel
Company.

Degeneracy
A solution is degenerate when one of the basic variables necessarily equals zero. In the transportation simplex
tableau, degeneracy is indicated when the number of stone squares is not equal to the number of rim requirements
minus 1. A solution can fail the degeneracy test in two ways:
1. There may be an excessive number of stone squares in a solution. This type of degeneracy arises only in
developing the initial solution and is caused by an improper assignment or an error in formulating the problem. In such
cases, one must modify the initial solution in order to get a solution that satisfies the rule of rim requirements minus 1.
2. There may be an insufficient number of stone squares in a solution. Degeneracy of this type may occur either
in the initial solution or in subsequent solutions. Special procedures are needed to address this type of degeneracy.

MTH 242/Handout 4/CSMJACOB Page | 14

DEGENERACY IN ESTABLISHING AN INITIAL SOLUTION
Assume that the plant capacities and project requirements in the original Bass Gravel Company problem have
been changed, as shown in the initial solution below.

To
Project A Project B Project C Plant Capacity
From
WA 4 WB 8 WC 8
Plant W 55
35 20
XA 16 XB 24 XC 16
Plant X 25
25
YA 8 YB 16 YC 24
Plant Y 35
35
115
Project requirements
35 45 35 115

The solution above shows only four stone squares, which is less than the required 6 – 1 = 5, hence the solution
is degenerate. This arises when, in using the northwest corner rule, both a column requirement and a row requirement
are satisfied simultaneously, thus breaking the stair-step pattern. In the solution above, this occurs in square XB.
To resolve this degeneracy, a zero stone is assigned to one of the unused squares such that an unbroken chain
of stone squares is maintained. Any of the unused squares that will satisfy this requirement may be used. Using square
XC results in the initial solution below, this can then be solved for optimality using the methods previously discussed.

To
Project A Project B Project C Plant Capacity
From
WA 4 WB 8 WC 8
Plant W 55
35 20
XA 16 XB 24 XC 16
Plant X 25
25 0
YA 8 YB 16 YC 24
Plant Y 35
35
115
Project requirements
35 45 35 115

The zero stone square has no meaning in a problem: it is merely a computational device which permits the Bass Gravel
Company to apply the regular solution method.

MTH 242/Handout 4/CSMJACOB Page | 15

DEGENERACY DURING SUBSEQUENT SOLUTIONS
The initial solution to another version of the problem is shown below. The improvement indices are shown in
the unused squares, showing that an improved solution may be obtained by introducing the unused square YB into the
next solution.

To
Project A Project B Project C Plant Capacity
From
WA 4 WB 8 WC 8
Plant W 90
45 45 +12
XA 16 XB 24 XC 16
Plant X 60
+8 30 30
YA 8 YB 16 YC 24
Plant Y 30
+8 –8 30
180
Project requirements
45 75 60 180

Tracing the closed path for unused square YB results in a tie between the stones in the squares having the
minus sign. Reducing a negative stone square by 30 results in eliminating two stone squares,

XB 24 XC 16 XB 24 XC 16
30 – 30 + 60
The results
YB of
16 YCassignment
the 24 of 30 units to square YB reduced
YB both 16 theYCquantities
24 shipped through
squares XB and YC to zero.
+ This will30always
– occur when a tie exists between 30two or more stone squares when these
stones represent the smallest stones on the path in squares assigned a minus sign. To satisfy the rule that the number of
stone squares equals the number of rim requirements minus 1, the stone square XB will be retained, and only stone
square YC will be eliminated, as shown below:

To
Project A Project B Project C Plant Capacity
From
WA 4 WB 8 WC 8
Plant W 90
45 45
XA 16 XB 24 XC 16
Plant X 60
0 60
YA 8 YB 16 YC 24
Plant Y 30
30
180
Project requirements
45 75 60 180

In some cases more than two stone squares may be reduced to zero. In such cases, only one of the squares
should be eliminated so that the number of stone squares in the solution still satisfies the rule of rim requirements
minus 1. The Bass Gravel company problem can now be solved using the standard procedure discussed previously.
Furthermore, some solutions may also be temporarily degenerate, that is, degeneracy may appear in one of the
iterations, but may disappear in subsequent iterations.

MTH 242/Handout 4/CSMJACOB Page | 16

Maximization with the transportation method
David Santos is Marketing Vice president with the Monarch Company. Monarch is planning to expand its sales of
computer software into three new areas – Calamba, Lipa, and San Pablo. It has been determined that 20, 15, and30
salespersons will be required to service each of the three areas, respectively. The company recently hired 65 new
salespersons to cover these area, and based on their experience and prior sales performance, the new hires have been
classified as Type A, B, or C salespersons. Depending upon the area to which each of the three types are assigned,
Monarch estimates the following annual revenues per salesperson:

Number of Annual revenues (in pesos) by area

salespersons
Type available Calamba Lipa San Pablo
A 24 5,000,000 6,000,000 6,500,000
B 27 4,500,000 5,300,000 6,300,000
C 14 4,200,000 4,900,000 6,000,000

David wishes to determine how many salespersons of each type to assign to the three areas so that total revenues will
be maximized.
Solution:
Using VAM, the penalty for each row/column will be computed as the difference between the highest and the
second highest cost element.
K1 = 5 K2 = 6 K3= 6.8

To Calamba Lipa San Pablo

Salespers
Type ons
5.0 6.0 6.5
M M M a v a2i l4a b
R1 = 0
A 4 th 15 3rd M
9 -
0.3
4.5 M
M 5.3M 6.3
R2 = 27
B 5 th - M
-0.5
11 0.2 2 nd

M 16
4.2 4.9
M M 6.0
R3 = C - M 14
-0.8 0
0.3M 1st
14
Salesperso
ns 20 15 30 65
required
0.5M 0.7M 0.2M
0.5M 0.7M 0.2M
Penalty 0.5M 0.7M -
0.5M - -
0.3M - -

The solution is optimal because there are no more positive improvement indices. Hence, the optimal solution is:
Assignment Number Revenue per Salesperson Total Revenue
Type A salespersons to Calamba 9 P5 million P45 million

MTH 242/Handout 4/CSMJACOB Page | 17

 Type A salespersons to Lipa 15 6 million 90 million
Type B salespersons to Calamba 11 4.5 million 49.5 million
Type B salespersons to San Pablo 16 6.3 million 100.8 million
Type c salespersons to San Pablo 14 6 million 84 million
Total annual revenues = P369,300,000

Exercises:
1. Saniware manufactures, among other products, a full line of bathtubs. The company has three warehouses from
which bathtubs are to be delivered to customers in three locations. Data are presented below.

Transportation Cost (in pesos) per bathtub

for Saniware
To Quantity
Makati Cavite San Juan
From Available
Cubao 200 560 120 45
Pasig 320 160 120 50
Caloocan 360 280 200 30
Quantity Required 35 55 35

a. Set up the initial table by each of the following methods, and compute the total transportation cost for each table:
i. Northwest corner rule ii. Minimum cost iii. Vogel’s approximation (indicate the order of allocation)
b. Design an optimum schedule of shipment that will minimize the total transportation cost. State your decision and its
cost of transportation.
2. The Rent-A-Car company has accumulated extra cars at three of its outlets, as shown below:
Leasing outlet Extra cars Leasing outlet Car shortage
1. Baguio 70 A. Greenhills 90
2. Iloilo 115 B. Makati 60
3. Davao 60 C. Cebu 90
D. Clark 25
The firm wants to transfer cars from outlets with extra to those with shortage at the minimum total cost. The following
costs of transporting the cars from city to city have been determined as follows:
To
A B C D
From
1 700 800 450 900
2 1200 400 300 750
3 1100 600 700 800
a. Set up the initial table by each of the following methods, and compute the total transportation cost for each table:
i. Northwest corner rule ii. Minimum cost iii. Vogel’s approximation
Design an optimum schedule of shipment that will minimize the total transportation cost. State your decision and its
cost of transportation.
3. Klein Chemicals, Inc. produces a special oil-based material that is currently in short supply. Four of Klein’s customers
have already placed orders that together exceed the combined capacity of Klein’s two plants. Klein’s management faces
the problem of deciding how many units it should supply to each customer. Because the four customers are in different
industries, different prices can be charged because of the various industry pricing structures. However, slightly different
production costs at the two plants and varying transportation cost between the plants and customers make a “sell to
the highest bidder” strategy unacceptable. After considering price, production costs, and transportation costs, Klein
established the following parameter table containing the profit per unit for each plant-customer alternative, as well as
the distributor demands and the plant capacities.
Customer Plant capacity (units)
Plant D1 D2 D3 D4
MTH 242/Handout 4/CSMJACOB Page | 18
 Clifton Springs $32 $34 $32 $40 5000
Danville $34 $30 $28 $38 3000
Distributor orders (units) 200 500 300 200
0 0 0 0
How many units should each plant produce for each customer to maximize profits? Which customer demands
will not be met? Use Vogel’s Approximation and the Modified Distribution Methods to arrive at the optimum solution.

MTH 242/Handout 4/CSMJACOB Page | 19