Home | | **Operations Research An Introduction** | | **Resource Management Techniques** | The Transportation Algorithm

1. Determination of the Starting Solution
2. Iterative Computations of the Transportation Algorithm
3. Simplex Method Explanation of the Method of Multipliers

**THE TRANSPORTATION ALGORITHM**

The transportation algorithm follows the *exact steps* of the simplex method (Chapter 3). However, instead of
using the regular simplex tableau, we take advantage of the special structure
of the transportation model to organize the computations in a more convenient
form.

The special transportation algorithm was developed early on when hand
computations were the norm and the shortcuts were warranted. Today, we have
powerful computer codes that can solve a transportation model of any size as a
regular Lp' Nevertheless, the transportation algorithm, aside from its
historical significance, does pro-vide insight into the use of the theoretical
primal-dual relationships (introduced in Section 4.2) to achieve a practical
end result, that of improving hand computations. The 5. exercise is theoretically
intriguing.

The details of the algorithm are explained using the following numeric
example.

**Example 5.3-1**** ****(SunRay Transport)**

SunRay Transport Company ships truckloads of grain from three silos to
four mills. The supply (in truckloads) and the demand (also in truckloads)
together with the unit transportation costs per truckload on the different
routes are summarized in the transportation model in Table 5.16. The unit
transportation costs, *eij,* (shown in the northeast corner of each box) are in hundreds of dollars.
The model seeks the minimum-cost shipping schedule *Xij* between silo *i* and mill *j *(i = *1,2,3; j* = 1,2,3,4).

**Summary of the Transportation
Algorithm.** The steps of the transportation
algorithm are exact parallels of the simplex algorithm.

**Step 1.**** **Determine a *starting* basic
feasible solution, and go to step 2.

**Step 2. **Use the optimality condition of the simplex method to determine the *entering variable *from among all the
nonbasic variables.* *If* *the optimality* *condition is
satisfied, stop. Otherwise, go to step 3.

**Step 3. **Use the feasibility condition of the simplex method to determine the *leaving* *variable *from among all the current basic variables, and find the
new basic solution. Return to step 2.

**1. Determination of the Starting
Solution**

A general transportation model with *m*
sources and *n* destinations has *m* + *n* constraint equations, one for each
source and each destination. However, because the transportation model is
always balanced (sum of the supply = sum of
the demand), one of these equations is redundant. Thus, the model has *m* + *n* - 1 independent constraint equations, which means that the starting basic
solution consists of *m* + *n* - 1 basic variables. Thus, in
Example 5.3-1, the starting solution has 3 + 4 - 1 = 6 basic variables.

The special structure of the transportation problem allows securing a
nonartificiaI starting basic solution using one of three methods:^{}

a) Northwest-corner method

b) Least-cost method

c) Vogel approximation method

. The three methods differ in the "quality" of the starting
basic solution they produce, in the sense that a better starting solution
yields a smaller objective value. In general, though not always, the Vogel
method yields the best starting basic solution, and the northwest-corner method
yields the worst. The tradeoff is that the northwest-corner method involves the
least amount of computations.

**Northwest-Corner Method. **The method starts at the northwest-corner cell (route) of the tableau
(variable x_{11}).

**Step 1.** Allocate as much as possible to the selected cell, and adjust the
associated amounts of supply and demand by subtracting the allocated amount.

**Step 2. **Cross out the row or column with zero supply or demand to indicate that
no further assignments can be made in that row or column. If both a row and a column net to zero simultaneously, *cross out one only,* and leave a zero
sup-ply (demand) in the uncrossed-out TOW (column).

**Step 3. **If *exactly one* row or column is
left uncrossed out, stop. Otherwise, move to the cell to the right if a column
has just been crossed out or below if a row has been crossed out. Go to step 1.

**Example 5.3-2**

The application of the procedure to the model of Example 5.3-1 gives the
starting basic solution in Table 5.17. The arrows show the order in which the
allocated amounts are generated.

The starting basic solution is

**Least-Cost Method. **The least-cost method finds a better starting solution by concentrating
on the cheapest routes. The method assigns as much as possible to the cell with
the smallest unit cost (ties are broken arbitrarily). Next, the satisfied row
or column is crossed out and the amounts of supply and demand are adjusted
accordingly.

If both a row and a column are satisfied simultaneously, *only one is crossed out,* the
same as in the northwest-corner method. Next, look
for the uncrossed-out cell with the smallest unit cost and repeat the process
until exactly one row or column is left uncrossed out.

**Example 5.3-3**

The least-cost method is applied to Example 5.3-1 in the following
manner:

1. Cell (1, 2) has the least unit cost in the tableau (= $2). The most
that can be shipped through (1,2) is *X _{12}* = 15 truckloads, which happens to satisfy both row 1 and column 2
simultaneously. We arbitrarily cross out column 2 and adjust the supply in row
1 to 0.

2. Cell (3,1) has the smallest uncrossed-out unit cost (= $4). Assign *X _{31}* = 5, and cross out column 1 because it is satisfied, and adjust the
demand of row 3 to 10 - 5 = 5
truckloads.

3. Continuing in the same manner, we successively assign 15 truckloads
to cell (2, 3), 0 truckloads
to cell (1,4), 5 truckloads to cell (3, 4), and 10 truckloads to cell (2,4) (verify!).

The
resulting starting solution is summarized in Table 5.18. The arrows show the
order in which the allocations are made. The starting solution (consisting of 6
basic variables) is *x _{12} *=

z =
15 X 2 + 0 x 11 + 15 x 9 + 10 x 20 + 5 x 4 + 5 x 18 = $475

The
quality of the least-cost starting solution is better than that of the
northwest-corner method (Example 5.3-2) because it yields a smaller value of *z* ($475
versus $520 in the northwest-corner method).

**Vogel Approximation Method (VAM).
**VAM is an improved version of the least-cost method
that generally, but not always, produces better starting solutions.

**Step 1. **For each row (column), determine a penalty measure by subtracting the *smallest *unit cost element in the row
(column) from the* next smallest *unit* *cost element in the same row (column).

**Step 2.** Identify the row or column with the largest penalty. Break ties
arbitrarily. Allocate as much as possible to the variable with the least unit
cost in the selected row or column. Adjust the supply and demand, and cross out
the satisfied row *or* column. If a row and a column are satisfied simultaneously, only one of the two is
crossed out, and the remaining row (column) is assigned zero supply (demand).

**Step 3. **

(a) If exactly one row or column with zero supply or demand remains un-crossed
out, stop.

(b) If one row (column) with *positive* supply (demand) remains uncrossed out,
determine the basic variables in the row (column) by the least-cost method.
Stop.

(c) If all the uncrossed out rows and columns have (remaining) zero supply and demand, determine the *zero*
basic variables by the least-cost method. Stop.

(d) Otherwise, go to step 1.

**Example 5.3-4**

VAM is
applied to Example 5.3-1. Table 5.19 computes the first set of penalties.

Because
row 3 has the largest penalty (= 10) and cell (3, 1) has the smallest unit cost
in that row, the amount 5 is
assigned to *x _{31}.* Column 1
is now satisfied and must be crossed out. Next, new penalties are recomputed as
in Table 5.20.

Table
5.20 shows that row 1 has the highest penalty (= 9). Hence, we assign the maximum amount possible to cell (1,2), which
yields x_{12} = 15 and simultaneously
satisfies both row 1 and 5. column 2. We arbitrarily cross out column 2 and
adjust the supply in row 1 to zero.

Continuing
in the same manner, row 2 will produce the highest penalty (= 11), and we
as-sign *x _{23}* = 15, which
crosses out column 3 and leaves 10 units in row 2. Only column 4 is left, and
it has a positive supply of 15 units. Applying the least-cost method to that
column, we successively assign x

*z *=* *15* *x*
*2* *+* *0* *x*
*11* *+* *15* *x*
*9* *+* *10* *x*
*20* *+* *5* *x*
*4* *+* *5* *x*
*18* *=* *$475

This
solution happens to have the same objective value as in the least-cost method.

**2. Iterative Computations of the
Transportation Algorithm**

After
determining the starting solution (using any of the three methods in Section 5.3.1), we use the
following algorithm to determ~ne the
optimum solution:

**Step 1.** Use the simplex *optimality condition* to determine the *entering variable* as the current
nonbasic variable that can improve the solution. If the optimality condition is satisfied, stop. Otherwise, go to step 2.

**Step 2.** Determine the *leaving variable* using the simplex *feasibility condition.* Change the basis,
and return to step 1.

The
optimality and feasibility conditions do not involve the familiar row operations
used in the simplex method. Instead, the special structure of the
transportation model allows simpler computations.

**Example
5.3-5**

Solve the
transportation model of Example 5.3-1, starting with the northwest-corner
solution.

Table
5.21 gives the northwest-corner starting solution as determined in Table 5.17,
Example 5.3-2.

The
determination of the entering variable from among the current nonbasic
variables (those that are not part of the starting basic solution) is done by
computing the nonbasic coeffi-cients in the z-row, using the method of
multipliers (which, as we show in Section 5.3.4, is rooted in LP duality
theory).

In the
method of multipliers, we associate the multipliers *Ui* and *v;* with row *i* and column
j of the transportation tableau. For each current *basic* variable *Xi;,* these multipliers are shown in
Section 5.3.4 to satisfy the following equations:

*u _{i} *+

As Table
5.21 shows, the starting solution has 6 basic variables, which leads to 6
equations in 7 unknowns. To solve these equations, the method of multipliers
calls for arbitrarily setting any *u _{i} *=

The
results of these evaluations are shown in the following table:

The
preceding information, together with the fact that *u _{i}* +

Because
the transportation model seeks to *minimize*
cost, the entering variable is the one having the *most positive* coefficient in the z-row. Thus, *x _{31}* is the
entering variable.

The
preceding computations are usually done directly on the transportation tableau
as shown in Table 5.22, meaning that it is not necessary really to write the *(u,* v)-equations explicitly. Instead, we
start by setting u_{1} = 0. Then
we can compute the v-values of all the columns that have *basic*
variables in row I-namely, v_{I} and *v _{2}.* Next, we compute

Having
identified *x _{31}* as the entering variable, we need to detennine the
leaving variable. Remember that if

The
selection of *x _{31}* as the
entering variable means that we want to ship through this route because it
reduces the total shipping cost. What is the most that we can ship through the
new route? Observe in Table 5.22 that if route (3, 1) ships () units (i.e.,

a)
Supply limits and demand requirements remain
satisfied.

b)
Shipments through all routes remain nonnegative.

These two
conditions determine the maximum value of *Ф* and the leaving variable in the
following manner. First, construct a *closed
loop* that starts and ends at the entering variable cell, (3, 1). The loop
consists of *connected horizontal* and *vertical* segments only (no diagonals are
al-lowed).7 Except for the entering variable cell, each corner of the closed
loop must coincide with a basic variable. Table 5.23 shows the loop for *x _{31}.* Exactly
one loop exists for a given entering variable.

Next, we
assign the amount *Ф* to the entering variable cell (3, 1). For the
supply and demand limits to remain satisfied, we must alternate between
subtracting and adding the amount *Ф* at the successive *corners* of the loop as shown in Table
5.23 (it is immaterial whether the loop is traced in a clockwise or
counterclockwise direction). For *Ф* *≥* 0, the new values of the
variables then remain nonnegative if

The
corresponding maximum value of *Ф* is 5, which occurs when both *x _{11}* and

The
selection of *x _{31}* (= 5) as the entering variable
and

Given the
new basic solution, we repeat the computation of the multipliers *u* and *v,* as Table 5.24 shows. The entering variable is x_{14}.
The closed loop shows that *x _{14}* = 10 and that the leaving
variable is

The new
solution, shown in Table 5.25, costs $4 X 10 = $40 less than the preceding one,
thus yielding the new cost $475 - $40 = $435.
The new *u _{i}* +

The
following table summarizes the optimum solution.

**TORA
Moment.**

From Solve/Modiy Menu , select Solve ->
Iterations and choose one of the three
methods
(northwest corner, least cost or Vogel) to start the transportation model iterations.
The iterations module offers two useful interactive features:

1. You
can set any *u *or *v* to zero before generating Iteration 2 (the default is u_{1}
= 0). Observe then that although
the values of *u _{i}* and

2. You
can test your understanding of the selection of the *closed loop* by clicking (in any order) the *corner* cells that comprise the path. If your selection is correct, the cell will change color (green for
entering variable, red for leaving variable, and gray otherwise).

**Solver
Moment.**

Entering
the transportation model into Excel spreadsheet is straightforward. Figure 5.4
provides the Excel Solver template for Example 5.3-1 (file solverEx5.3-l.xls),
together with all the formulas and the definition of range names.

In the input
section, data include unit cost matrix (cells B4:E6), source names (cells
A4:A6), destination names (cells B3:E3), supply (cells F4:F6), and demand
(cells B7:E7). In the output section, cells B11:E13 provide the optimal
solution in matrix form. The total cost formula is given in target cell A10.

**AMPl
Moment.**

Figure
5.5 provides the AMPL model for the transportation model of Example 5.3-1 (file
amplEx5.3-1a.txt). The names used in the model are self-explanatory. Both the
constraints and the objective function follow the format of the LP model
presented in Example 5.1-I.

The model
uses the sets sNodes and dNodes to conveniently allow the use of
the alphanumeric set members {s1, s2, s3} and {Dl, D2, D3, D4} which are
entered in the data section. All the input data are then entered in terms of
these set members as shown in Figure 5.5.

Although
the alphanumeric code for set members is more readable, generating them for
large problems may not be convenient. File ampIExS.3-1b shows how the same sets
can be defined as {1 .. m) and {1 .. n}, where m and n represent the number of sources
and the number of destinations. By simply assigning numeric values for In and n, the sets are
automatically defined for any size model.

The data
of the transportation model can be retrieved from a spreadsheet (file TM.xls)
using the AMPL table statement. File amplEx3S1c.txt provides the details. To
study this model, you will need to review the material in Section A.5.5.

**PROBLEM
SET 5.3B**

1. Consider
the transportation models in Table 5.26.

a)
Use the northwest-corner method to find the
starting solution.

b)
Develop the iterations that lead to the optimum
solution.

c)
*TO RA
Experiment. *Use TORA's Iterations module to compare the effect
of using* *the northwest-corner rule,
least-cost method, and Vogel method on the number of iterations leading to the
optimum solution.

d)
*Solver
Experiment. *Solve the problem by modifying file
solverEx5.3-l.xls.

*2. AMPL Experiment. *Solve the
problem by modifying file ampIEx5.3-lb.txt.

In the
transportation problem in Table 5.27, the total demand exceeds the total
supply.

Suppose
that the penalty costs per unit of unsatisfied demand are $5, $3, and $2 for
destinations 1,2, and 3, respectively. Use the least-cost starting solution and
compute the iterations leading to the optimum solution.

3. In
Problem 2, suppose that there are no penalty costs, but that the demand at
destination 3 must be satisfied completely.

a)
Find the optimal solution.

b)
*Solver
Experiment. *Solve the problem by modifying file
solverExS.3-l.xls.

c)
*AMPL
Experiment. *Solve the problem by modifying file
ampIEx5.3b-l.txt.

4. In the
unbalanced transportation problem in Table 5.28, if a unit from a source is not
shipped out (to any of the destinations), a storage cost is incurred at the
rate of $5, $4, and $3 per unit for sources 1,2, and 3, respectively.
Additionally, all the supply at source 2 must be shipped out completely to make
room for a new product. Use Vogel's starting solution and determine all the
iterations leading to the optimum ship-ping schedule.

*5. In a
3 X 3 transportation problem, let *x _{ij}* be the
amount shipped from source

(a) Find the associated optimal
cost.

(b)
Determine the smallest value of *Gij* for each nonbasic variable that
will maintain the optimality of the northwest-corner solution.

6. The
transportation problem in Table 5.29 gives the indicated *degenerate* basic solution (i.e., at least one of the basic
variables is zero). Suppose that the multipliers associated with this solution
are u_{1} = 1, *u _{2}* = -1, v

(a) If the given solution is optimal, determine
the associated optimal value of the objective function.

(b) Determine the value of () that will
guarantee the optimality of the given solution.

on (Hint: Locate the zero basic variable.)

7. Consider the problem

**3. Simplex Method Explanation of the Method of Multipliers**

The relationship between the method of multipliers and the simplex
method can be explained based on the primal-dual relationships (Section 4.2).
From the special structure of the LP representing the transportation model (see
Example 5.1-1 for an illustra-tion), the associated dual problem can be written
as

From
Formula 2, Section 4.2.4, the objective-function coefficients (reduced costs)
of the variable *x _{ij}* equal the difference between the
left- and right-hand sides of the corresponding dual constraint-that is,

There are
*m* + *n* - 1 such
equations whose solution (after assuming an arbitrary value u_{1} = 0)
yields the multipliers *u _{i}* and

The
assignment of an arbitrary value to one of the dual variables (i.e., u_{1}
= 0) may appear inconsistent with
the way the dual variables are computed using Method 2 in Section 4.2.3. Namely, for a
given basic solution (and, hence, inverse), the dual values must be unique.
Problem 2, Set 5.3c, addresses this point.

**PROBLEM SET **5.3C

1. Write
the dual problem for the LP of the transportation problem in Example 5.3-5
(Table 5.21). Compute the associated optimum *dual* objective value using the optimal dual values given in Table
5.25, and show that it equals the optimal cost given in the example.

2. In the
transportation model, one of the dual variables assumes an arbitrary value.
This means that for the same basic solution, the values of the associated dual
variables are not unique. The result appears to contradict the theory of linear
programming, where the dual values are determined as the product of the vector
of the objective coefficients for the basic variables and the associated
inverse basic matrix (see Method 2, Section 4.2.3). Show that for the
transportation model, although the inverse basis is unique, the vector of *basic* objective coefficients need not be
so. Specifically, show that if *C _{ij}* is changed to

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.