CHAPTER 4

THE TRANSPORTATION PROBLEM

4.1 INTRODUCTION

Finding the best shipment plan is the objective of a typical transportation problem. The problem is
to determine how many units should be shipped from each source to each destination (considering
what routes to use and in what capacity) so that all demands are satisfied (if possible) at the
minimum total shipping cost.

4.2. TRANSPORTATION MODELS

A classic transportation model involves the shipment of some homogeneous commodity from m
sources of supply, or origins, to n points of demand, or destinations.

In the typical problem, each origin can supply any of the destinations. The demand at each
destination may be supplied jointly from a combination of origins or totally from one origin. The
decision variables take the form Xij, ith origin to jth destination.

Each origin usually has a specific capacity, which represents the maximum number of units it can
supply. Each destination has a specific demand, which represents the number of units needed.

Given that each origin may supply units to each destination, some measure of cost or effort of
shipping a unit is specified for each origin-destination combination. This may take the form of
money cost, distance between the two points, or time required to move from one point to another.

A typical problem is concerned with determining the number of units which should be supplied
from each origin to each destination. The objective is to minimize the total transportation or
delivery costs, while ensuring that: (1) the number of units shipped from any origin does not exceed
the number of units available at that origin, and (2) the demand at each destination is satisfied.

Example 4.1:

Farm to Market Road Maintenance: A small village has two locations at which gravel is stockpiled
for use during the rainy season. The gravel is distributed from these two locations to four zones in
the village were maintenance is required. The delegate of Public Works is interested in determining
the minimum cost of allocating gravel supplies during the rainy season. Table 4.1 summarizes the
cost of supplying one tonne of gravel from each stockpile to each zone in the village (expressed in
monetary units (MU)). In addition, stockpile capacities and normal levels of demand for each zone
are indicated in tonnes. Formulate the relevant Linear programming (LP) model.
Table 4.1: Farm to Market Road Maintenance
Zone Supply (tonnes)
A B C D
L1 2MU 3MU 1.5MU 2.5MU 900
L2 4MU 3.5MU 2.5MU 3MU 750
Demand (tonnes) 300 450 500 350

Remarks:
It may be instructive to make some general remarks before solving Example 4.1. This problem
could be represented as follows:

D1 300
S1 c11
900 c12
c14 D2 450
c13
c21 c22
S2 D3
750 c23 500
c24
D4 350

1650 = SS 1600 = DD

where arrows leave each source to all the destinations.

Let cij be the cost of shipping one unit from source i (where i=1, 2) to destination j (where j=1, ...,
4), and if Xij represents the quantity shipped from source i to destination j, suggesting 8 decision
variables, then:

Total cost = C = c11X11 + c12X12 + c13X13 + c14X14

+ c21X21 + c22X22 + c23X23 + c24X24

The supply (SS) and demand (DD) constraints generally suggest three possibilities: either SS <
DD, or SS = DD, or SS > DD.

Except otherwise imposed by the problem setting, these three possible situations can be interpreted
as follows:

a) Total Supply < Total Demand, that is, SS < DD. In this case, all the supply will be shipped
from all points i, but not all demand will be satisfied for all destinations j. Such a situation can be
expressed as:

 SS constraints are of the form (=)

 DD constraints are of the form ()

b) Total supply = Total demand, that is, SS = DD

 All constraints are equalities (=)

c) Total supply > Total demand

 SS constraints are of the form ()
 DD constraints are of the form (=)

Solution to Example 4.1:

Let Xij equal the number of tonnes supplied from stockpile i to zone j. For example, X11 equals the
number of tonnes supplied by stockpile 1 to zone 1. Thus, we have 8 decision variables.

Total cost of distributing gravel has the form

Total cost = C = 2X11 + 3X12 + 1.5X13 + 2.5X14
+ 4X21 + 3.5X22 + 2.5X23 + 3X24

SS > DD suggests two () stockpile constraints.

X11 + X12 + X13 + X14  900

X21 + X22 + X23 + X24  750

Since SS > DD, for each zone's demand to be satisfied, we need four (=) demand constraints.

For zone 1: X11 + X21 = 300

For zone 2: X12 + X22 = 450
For zone 3: X13 + X23 = 500
For zone 4: X14 + X24 = 350

The complete LP model is as follows:

Minimize Z = 2X11 + 3X12 + 1.5X13 + 2.5X14

+ 4X21 + 3.5X22 + 2.5X23 + 3X24
Subject to:
X11 + X12 + X13 + X14  900
X21 + X22 + X23 + X24  750
X11 + X21 = 300
X12 + X22 = 450
X13 + X23 = 500
X14 + X24 = 350

Xij  0, i =1, 2 and j=1, …,4

Although all transportation problems can be expressed as LP problems, it is not always efficient to
do so. Special solution methods can do the job much better.

4.3 SOLVING THE TRANSPORTATION MODEL

Three methods are typically used in solving transportation models.

(1) Method of complete Enumeration

This method could be time-consuming and cumbersome; and hence not worthwhile.

(2) The Linear Programming Method

Since the transportation problem is essentially an LP problem, it can be solved as such. Presentation
of a large transportation problem in LP format, however, results in considerable computational
effort, significantly more than the special transportation method. For instance, if we have 30 sources
and 20 destinations, we will be dealing with 30x20 = 600 decision variables and 30+20 = 50
constraints. Such a presentation will definitely be unpalatable, even to an ardent lover of algebra.

(3) Transportation method

This method provides a computationally efficient procedure for solving large transportation
problems.

4.4 THE TRANSPORTATION METHOD

The transportation method is a search and evaluation algorithm, very similar to that of the simplex
method in LP. The procedure involves five steps:

Step 1: Arrange the data in tabular form.

Step 2: Balance the table, if it is unbalanced.

This involves ensuring that total supply must equal total demand. That is, ensure that SS = DD.

• If SS > DD, such a table is balanced by incorporating an artificial destination column to absorb
the excess supply (sometimes labeled a dummy destination). Per unit shipment costs of zero are
usually associated with the destination dummy.

• If SS < DD, such a table is balanced by incorporating a dummy source row to accommodate
the extra demand. Again, per unit shipping costs for the dummy row are set to zero.
Example 4.2:
Balance the following Transportation model tables. Supply and demand are expressed in tonnes and
unit costs in MU. Unit costs are presented in square brackets within the table.

(i) Unbalanced table (the case of excess supply)

Destination D1 D2 D3 Supply

Source
S1 [1] [2] [3]
200
S2 [4] [1] [5]
100
300
80 120 60 260
Demand

Solution: Balance by incorporating a dummy destination column to absorb the access supply.

Destination D1 D2 D3 D(dummy) Supply

Source
S1 [1] [2] [3] [0] 200

S2 [4] [1] [5] [0] 100

300
Demand 80 120 60 40(excess SS) 300
(ii) Unbalanced table (the case of excess demand)

Destination D1 D2 D3 Supply

Source
S1 [1] [2] [3] 100
S2 [4] [1] [5] 110
210
80 120 60 260
Demand

Solution: Balance by incorporating a dummy source row to accommodate the extra demand.

Destination D1 D2 D3 Supply

Source
S1 [1] [2] [3] 100
S2 [4] [1] [5] 110
S(dummy) [0] [0] [0] 50
(extra demand)
260
80 120 60 260
Demand

Step 3: The Initial Feasible Solution

Two procedures are commonly used to generate the initial feasible solution: (a) The Northwest
corner rule, and (b) the least-cost method.

(a) The Northwest Corner Rule of Generating the Initial Solution

(i) Starting with the northwest corner (left, uppermost in the table), allocate the smaller amount of
either the row supply or the column demand.
(ii) Subtract from the row supply and from the column demand the amount allocated.
(iii) If the column demand is now zero, move to the next cell on the right; or if the row supply is
zero, move down to the cell in the next row. If both are zero, move first to the next cell on the right,
then down one cell.
(iv) Continue the process until all the remaining supply and demand are exhausted. Cells that
receive allocations are called occupied cells, to distinguish them from the remaining empty cells.

Example 4.3:
Generate the initial solution of Example 4.2 by the Northwest Corner Rule.

Solution: The Initial solution by the Northwest Corner Rule

Destination D1 D2 D3 Supply Remaining

Supply
Source
S1 [1] [2] [3] 100 20
80 20 0
S2 [4] [1] [5] 110 10
0
100 10
S(dummy) [0] [0] [0] 50 0
50
Demand 80 120 60 260
Remaining 0 100 50
demand 0 0

The initial feasible solution calls for shipments of:

Units from each source to each destination Cost of Shipment
80 tonnes from S1 to D1 at a cost of 80(1) 80 MU
20 tonnes from S1 to D2 at a cost of 20(2) 40 MU
100 tonnes from S2 to D2 at a cost of 100(1) 100 MU
10 tonnes from S2 to D3 at a cost of 10(5) 50 MU
50 tonnes from S to D3 at a cost of 50(0) 0 MU
Total cost 270 MU

(b) The Least-Cost Method of Generating the Initial Solution

The least-cost method (LCM) yields not only an initial feasible solution but also one that is very
close to the optimal solution, especially in small problems.
The procedure requires that the first allocation be made to the cell with the lowest cost; if there are
ties, start with the cell having the potential of receiving more units. If there are ties and the cells
have the potential of receiving the same quantities, then start with the cell that has the largest
remaining supply or demand as the case may be. The process continues in this manner, seeking the
empty cell with the lowest cost until the initial solution is completed.

EXAMPLE 4.4:
Obtain the initial solution of the following table by the least-cost method.

Destination D E F G Supply

Source
A [1] [5] [3] [4] 100
B [4] [2] [2] [5] 60
C [3] [1] [2] [4] 120
Demand 280
70 50 100 60 280

Solution: Initial solution by the Least-cost method

Destination D E F G Supply RS

Source
A [1] [5] [3] [4] 100 30
70 30 0
B [4] [2] [2] [5] 30 60 30
30 0
C [3] [1] [2] [4] 120 70
50 70 0
Demand 70 50 100 60 280
RD 0 0 30 30
0 0

Once the initial solution is achieved (by any method), a test for optimality is conducted.
Steps (4 and 5): Test for Optimality and possible improvement
The procedure for testing for optimality is analogous to that of the simplex method. A distinction is
made between basic variables, that is, those associated with the occupied cells, and non-basic
variables, that is, those associated with the empty cells.

For each empty cell, the effect of changing it to an occupied cell is examined. If any of these
changes are favourable, the solution is not optimal and a new solution must be found. The solution
to be verified for optimality, however, must be non-degenerate. That is, the number of occupied
cells most = m+n-1, where m = number of sources and n= number of destinations. A degenerate
solution is one in which there are insufficient number of occupied cells to permit testing for
optimality.

Procedures for testing for optimality and improvements include: The stepping-stone and the
modified distribution (MODI) methods. We are going to explore only the stepping-stone method
here.

• The stepping-stone procedure

The stepping-stone procedure implements the final two stages of the transportation method,
namely: (i) testing for optimality and, (ii) improving upon a non-optimal solution.

Step 4: Testing for optimality

This is accomplished by first calculating a cell evaluator for each empty cell. A cell evaluator for an
empty cell is a number indicating the change in cost resulting from occupying that cell (i.e.,
shipping one unit through it) rather than one of the currently occupied cells. In other to occupy an
empty cell, a transfer has to be made from a currently occupied cell. Such a transfer, subject to the
supply and demand constraints, will affect an even number of at least four cells envisaged mainly in
a clockwise direction.

Each gaining cell is associated with a positive (+ve) sign and each losing cell is associated with a
negative (-ve) sign. The value of a cell evaluator is the sum of the per unit shipping costs in the
gaining cells less the sum of the per unit shipping costs in the losing cells of the enclosed path. The
enclosed path is the circuit formed by the gaining and the losing cells.
Evaluator of an empty cell =  unit costs in gaining cells -  unit costs in losing cells.

If the cell evaluator is positive, then the solution cannot be improved via the newly occupied cell.
But if the cell evaluator is negative, then the solution tested is improvable, and therefore, not
optimal. The evaluation process is extended to all empty cells.

If all cell evaluators are positive, then the optimal solution has been achieved, otherwise, check all
the empty cells and select for improvement the one with the largest improvement potential.

Step 5: Improving a Non-optimal Solution

The operations involved are:

(1) Identify the incoming cell, that is, the empty cell to be occupied. In a minimization case, the
incoming cell is located by identifying the most negative cell evaluator. If there are ties, then any
may be selected.

(2) Design an improved solution. Once the incoming cell has been identified, an improvement is
made by shifting as many units as possible, along the enclosed path into the empty cell. The
quantity limit to this shifting process is reached when one of the losing cells in the enclosed path
becomes empty. If two or more cells become empty simultaneously, then a degenerate solution will
result.

Once an improved solution is generated, the optimality test is repeated.

In the final solution, if cell evaluators of 0 exist, this indicates the existence of multiple optimal
solutions.

4.5.1. SUMMARY OF THE STEPPING-STONE

METHOD

(i) Compute the cell evaluators for all empty cells. This is done by subtracting the unit costs of
the losing cells from that of the gaining cells in the enclosed path.

(ii) If all cell evaluators are non-negative, then the solution is optimal. Otherwise, (a) an
improvement is possible, or (b) an alternative solution exists in the case of 0 evaluators.
(iii) Generating an improved solution involves identifying the incoming cell (that cell with the
largest cost reduction potential for minimization problems) and transferring as much as possible to
it until one of the losing cells along the enclosed path becomes empty.

(iv) The improved solution is then tested. If it is not optimal, another improvement is made.
Eventually, an optimal solution (if any) will be reached.

EXAMPLE
4.5:

Test the initial solution generated in Example 4.3 for

optimality.

Solution: We start by checking whether the solution is non-degenerate. Since the number of
occupied cells = m+n-1 = 3+3-1= 5, the solution is non-degenerate.

Destination D1 D2 D3 Supply

Source
S1 [1] 80 [2] 20 [3] 100
S2 [4] [1] 100 [5] 10 110
S(dummy) [0] [0] [0] 50 50
Demand 80 120 60 260

Next we compute cell evaluators for the empty cells.

(1) Evaluation of cell S1D3

The cell evaluator for cell S1D3 is calculated by:
(a) moving 1 unit from S1D2 to S1D3;
(b) moving 1 unit from S2D3 to S2D2, in order to maintain the demand requirement in D3,
and
(c) evaluating the cost effect of these changes. S1D2 and S2D3 are labeled losing cells and (-)
signs attributed to them, while S1D3 and S2D2 are called the gaining cells and (+) signs attributed to
them.

As a result of these transactions, row supply capacities are maintained:

For row S1: 80 + (19) + 1 = 100
For row S2: (101) + 9 = 110

And column demand requirements are also maintained:

For column D2: (19) + (101) = 120
For column D3: (1) + (9) + 50 = 60

These transactions form the enclosed path:

S1D3 → S2D3 → S2D2 → S1D2

Cell evaluator of cell S1D3

= the cost effect of shipping 1 unit to S1D3
=  unit costs in gaining cells -  unit costs in losing cells
= (3+1) - (5+2)
= -3.

(2) Evaluation of cell S2D1

* The enclosed path is S2D1 → S1D1 → S1D2 → S2D2.
* The gaining cells are S2D1 and S1D2.
* The losing cells are S1D1 and S2D2.

* Cell evaluator of cell S2D1

=  unit costs in gaining cells -  unit costs in losing cells
= (4 + 2) - (1 + 1)
= 4.

(3) Evaluation of cell SD1

* The enclosed path is: SD1 → S1D1 → S1D2 → S2D2 → S2D3 → SD3.

* The gaining cells are SD1, S1D2 and S2D3.

* The losing cells are S1D1, S2D2 and SD3.

* Cell evaluator of cell SD1

 =  unit costs in gaining cells -  unit costs in losing cells
= (0 + 2 + 5) - (1 + 1 + 0)
= 5.

4) Evaluation of cell SD2

* The enclosed path is SD2 → S2D2 → S2D3 → SD 3
* Cell evaluator of cell SD2 = (0 + 5) - (1 + 0)
= 4.
Summary of cell evaluators

Empty Cell Cell evaluator

S1D3 -3
S2D1 4
SD1 5
SD2 4

Since cell S1D3 has a negative evaluator, the initial solution is not optimal. A negative cell evaluator
for a minimization problem implies the possibility for cost reduction by rescheduling the shipping
plan.

Example 4.6:
Improve the non-optimal initial solution of Example 4.5 and test for optimality.

We start by recalling the non-optimal initial solution of Example 4.5.

Destination D1 D2 D3 Supply

Source
S1 [1] 80 [2] 20 [3] 100
S2 [4] [1] 100 [5] 10 110
S(dummy) [0] [0] [0] 50 50
Demand 80 120 60 260

Improved solution:
The most improvable empty cell is S1D3 as suggested by its cell evaluator of -3 and the enclosed
path is S1D3 → S2D3 → S2D2 → S1D2.

Select the smallest number (shipment) in the enclosed path. Add this number to all cells with a +ve
sign and subtract it from all cells with a -ve sign.

The Improved Solution using the improvable empty cell, S1D3

Destination D1 D2 D3 Supply

Source
S1 [1] 80 - [2] + [3] 100
20-10=10 0+10= 10
S2 [4] + [1] - [5] 110
100+10=110 10-10 = 0
S(dummy) [0] [0] [0] 50
50
Demand 80 120 60 260

Testing for Optimality:

We can now calculate the cell evaluators of all the empty cells of the improved solution. The
results are:

Empty Cell Cell evaluator

S2D1 (4+2) - (1+1) = 4
SD1 (0+3) - (1+0) = 2
SD2 (0+3) - (2+0) = 1
S2D3 (5+2) - (1+3) = 3

Since all empty cells have non-negative evaluators, an optimal solution has been obtained.

The optimal shipping plan is as follows:

UNITS FROM EACH SOURCE TO EACH DESTINATION COST OF SHIPMENT (MU)
80 units from S1 to D1 at a cost of 1 MU per tonne 80
10 units from S1 to D2 at a cost of 2 MU per tonne 20
10 units from S1 to D3 at a cost of 3 MU per tonne 30
110 units from S2 to D2 at a cost of 1 MU per tonne 110
50 units from dummy source to D3 at no cost 0
Total cost 240
The initial solution gave a total transportation cost of 270 MU, while the optimal shipping
 plan gives a total transportation cost of 240 MU, suggesting a reduction in cost of 30 MU.

New total Cost = Previous total cost + (Sum of cost of gaining cell – Sum of cost of losing cells)
Where  = amount allocated along the enclosed
path. Thus, NTC = 270 + 10(4 – 7) =270 – 30 =
240

It is to be noted that the demand requirements in D3 have, indeed not been completely
satisfied, since 50 units are shipped to D3 out of the dummy source S.

4.6. DEGENERACY

A solution to a transportation problem is said to degenerate if less than m+n-1 cells are occupied.
With less than m+n-1 cells occupied, it is not possible to compute cell evaluators. To salvage this
situation, an empty cell is assigned the value  which is defined as a very small quantity. The value
 is used to bring the number of occupied cells to m+n-1.

The allocation of  to an empty cell depends on the method used in generating the initial solution. If
the Northwest-Corner Rule was used, then the empty cell nearest the northwest-corner is assigned .
If the least-cost method was used, then the empty cell with the lowest cost receives .

 is disposed of immediately it serves the purpose of ensuring that m+n-1 cells are occupied. Steps
4 and 5 are then implemented as usual.

Example 4.7:
Consider the following transportation situation where S1 and S2 represent sources; D1, D2, and D3
represent destinations.

Destination D1 D2 D3 Supply

Source
S1 [2] [1] [2] 20
S2 [3] [4] [1] 40
Demand 20 15 25 60
(a) Find the optimal shipping plan via the Northwest-corner Rule.
(b) Find the optimal shipping plan via the least-cost method Rule.
Solution to Example 4.6:
(a)
(i) The initial solution by the Northwest-Corner Rule.

Destination D1 D2 D3 Supply Remaining

Supply
Source
S1 [2] [1] [2] 20 0
20
S2 [3] [4] [1] 40 25
15 25 0
Demand 20 15 25 60
Remaining 0 0 0
demand

(ii) m+n-1 = 4, but there are only 3 occupied cells, this is a case of degeneracy. In order to remedy
the situation, we introduce  in cell S1D2 (because it is nearest to the northwest-corner).

Destination D1 D2 D3 Supply

Source
S1 [2] [1]  [2] 20
20
S2 [3] [4] 15 [1] 25 40
Demand 20 15 25 60

(iii) Since we now have m+n-1 occupied cells, testing for optimality can then be conducted by
computing cell evaluators.
Empty Cell Cell evaluator
S1D3 (4+2) - (1+1) = 4
S2D1 (3+1) - (2+4) = -2
S2D1 has a negative cell evaluator, hence, suggesting that occupying this route will reduce the total
transportation cost.

(iv) Improved solution

The smaller of the quantities of the losing cells is allocated along the enclosed path of S2D1,
while respecting the demand and supply constraints accordingly.
 Destination D1 D2 D3 Supply

Source
S1 [2] [1] [2] 20
5 15+
S2 [3] [4] [1] 25 40
15 0
Demand 20 15 25 60

(v) Testing the improved solution for optimality.

Empty Cell Cell evaluator
S1D3 (3+2) - (2+1) = 2
S2D2 (2+4) - (3+1) = 2

All the empty cell evaluators are now positive, implying that the optimal solution has
been obtained.

(vi) The optimal shipping plan is as follows:

UNITS FROM EACH SOURCE TO EACH DESTINATION COST OF SHIPMENT (MU)
5 units from S1 to D1 at a cost of 2 MU per tonne 10
15 units from S1 to D2 at a cost of 1 MU per tonne 15
15 units from S2 to D1 at a cost of 3 MU per tonne 45
25 units from S2 to D3 at a cost of 1 MU per tonne 25
Total cost 95

(b) The reader may do this as an exercise.

4.7 TRANSPORTATION PROBLEMS INVOLVING PROFIT MAXIMIZATION

In maximization situations, the elements within the given matrix represent revenues or profits. A
profit maximization problem can be adjusted slightly to make it solvable by the usual minimization
procedures. The adjustment involves constructing a new matrix called an opportunity loss matrix by
subtracting all elements in the initial matrix from the largest profit element. The opportunity loss is
measured by the difference between the largest value of profit in the matrix and the profit actually
recorded in each cell. A profit maximization table is balanced before the computation of the
opportunity loss matrix.
The usual minimization procedure can now be employed because profit is maximized if the total
opportunity loss is minimized.

Example 4.8:
Consider a transportation situation in which S1, S2, and S3 are sources; and D1, D2, D3 and D4 are
destinations. The figures within the matrix are unit profits realized from particular transfers. The
problem is to allocate with a view to maximizing total profits.

Destination D1 D2 D3 D4 Supply

Source

S1 (5) (4) (5) (7) 50

S2 (4) (8) (6) (5) 40

S3 (6) (3) (4) (5) 60

Demand 40 30 50 30 150

4.8 TRANSSHIPMENT
Situations are sometimes encountered where it may not be cost-effective or practical to transport
directly from sources to destinations. This is the case when it is necessary for a commodity to pass
through intermediate warehouses before reaching the ultimate destination. This situation is
described as transshipment. A slight modification of such a problem will permit the use of the
standard minimization procedure.

The modification requires working out the cost of supplying each demand centre from each
supply point via all possible routes. The least costly route to each destination from each source is
then selected and registered in the matrix. The standard minimization procedure can now be
followed.

Example
4.9:
UCB has decided to introduce a new product. The new product may be distributed though any
combination of the two warehouses belonging to the company, W1 and W2. The available annual
capacities for the new product are:

100 units at plant

S1
200 units at plant
S2
100 units at plant
S3
The three major concentrations of customer demand are at locations D1, D2 and D3 which are
estimated to require each year:
90 units at
D1
80 units at
D2
90 units at
D3

The unit production costs amount to 3MU, 4MU and 1MU at S1, S2, and S3, respectively. The unit
handling costs at the warehouses amount to 2MU and 3MU at W1 and W2, respectively. The unit
shipping cost from plant to warehouse and unit delivery costs from warehouse to customer are
as
follows
:
W1 W2 D1 D2 D3
S1 6 6 W1 3 5 8
S2 5 5 W2 5 3 9
S3 13 4
All cost are expressed in monetary units
(a) Determine the optimal production and distribution schedule
(b) Assuming that each warehouse can handle a maximum of 200 units a year, explain why
it would be incorrect to solve the problem using the transportation technique to
obtain a solution to the flow between plant and warehouse and then apply the technique
again to the flows between the warehouses and the customer.

Exercises on Chapter 4
;1) Given a transportation problem (with cost coefficients):

Destination D E F G Supply

Source

A [1] [5] [3] [4] 100

 B [4] [2] [2] [4] 60

C [3] [1] [2] [4] 120

Demand
70 50 100 60

(a) Find an initial solution by the Northwest-Corner Rule.

(b) Find an initial solution by the least-cost method.
(c) Find an optimal solution by the stepping stone method:
Start with the results of part (a) then (b).
(d) Are there any other optimal solutions in each case?
(e) Based on findings of part (d), comment on the number of occupied cells in an
optimal solution.