Engineering Optimization: Theory and Practice, Fourth Edition

4.6 Transportation Problem 221

The problem stated in Eqs. (4.52) to (4.56) was originally formulated and solved by
Hitchcock in 1941 [4.6]. This was also considered independently by Koopmans in
1947 [4.7]. Because of these early investigations the problem is sometimes called the
Hitchcock-Koopmans transportation problem. The special structure of the transportation
matrix can be seen by writing the equations in standard form:

x 11 +x 12 + · · · +x 1 n =a 1

x 21 +x 22 + · · · +x 2 n =a 2

..

.

..

.

xm 1 +xm 2 + · · · +xmn=am

(4.58a)

x 11 +x 21 +xm 1 =b 1

x 12 +x 22 +xm 2 =b 2

..

.

..

.

..

.

x 1 n +x 2 n +xmn =bn

(4.58b)

c 11 x 11 +c 12 x 12 + · · · +c 1 nx 1 n+c 21 x 21 + · · · +c 2 nx 2 n+ · · ·

+cm 1 xm 1 + · · · +cmnxmn=f (4.58c)

We notice the following properties from Eqs. (4.58):

1.All the nonzero coefficients of the constraints are equal to 1.

2.The constraint coefficients appear in a triangular form.

3.Any variable appears only once in the firstmequations and once in the nextn

equations.

These are the special properties of the transportation problem that allow devel-
opment of thetransportation technique. To facilitate the identification of a starting
solution, the system of equations (4.58) is represented in the form of an array, called
thetransportation array, as shown in Fig. 4.2. In all the techniques developed for solv-
ing the transportation problem, the calculations are made directly on the transportation
array.

Computational Procedure. The solution of a LP problem, in general, requires a
calculator or, if the problem is large, a high-speed digital computer. On the other hand,
the solution of a transportation problem can often be obtained with the use of a pencil
and paper since additions and subtractions are the only calculations required. The basic
steps involved in the solution of a transportation problem are

1.Determine a starting basic feasible solution.

2.Test the current basic feasible solution for optimality. If the current solution is

optimal, stop the iterative process; otherwise, go to step 3.

3.Select a variable to enter the basis from among the current nonbasic variables.