Sources:
(Others are noted in the body of this notes template)

1. Jensen, P.A. & Barnes, J.W. Network Flow Programming, Wiley, 1980.
2. Winston, W.L. Operations Research: Applications and Algorithms (Ch. 2) (Third Edition), Duxbury, Belmont, CA, 1994.

An Example Problem:

Consider the following problem:

Generous Electric -- Southwest Refrigerator Division

Generous Electric owns primary warehouses located near its production plants and secondary warehouses in most major cities in the United States. As stocks of refrigerators are depleted in the secondary warehouses, a demand is created for replenishment from the primary warehouses. Company economists have arrived at the unit costs associated with transporting refrigerators from any primary warehouse to any secondary warehouse. Using the information below, the company wants to derive a replenishment policy that will minimize the cost of updating the secondary warehouses.

                                           Primary Warehouses           
Secondary Warehouse      Houston        Dallas      Lufkin
Austin                                  4                  7             6
Corpus Christi                     6                   9            7
Oklahoma City                    6                  4             5
Houston                              2                  5             5
San Antonio                        4                  9             7
Nacogdoches                      3                  6             7     

City                       Demand       City            Availability
Austin                       49             Houston        173
Corpus
Christi                      38              Dallas             68
Oklahoma
City                          17              Lufkin             44
Houston                    64
San
Antonio                     57
Nacogdoches              9                                                
Total                       234                                   285

Let's draw the transportation network associated with this problem:

Formulating and solving the Example Problem as a Linear Program:
Variable and Parameter Definitions

Formulation

LINDO Solution

C:\LINDO> TYPE TRAN.EX

MIN 4 X11 + 6 X12 + 6 X13 + 2 X14 + 4 X15 + 3 X16
+ 7 X21 + 9 X22 + 4 X23 + 5 X24 + 9 X25 + 6 X26
+ 6 X31 + 7 X32 + 5 X33 + 5 X34 + 7 X35 + 7 X36
ST
X11 + X12 + X13 + X14 + X15 + X16 < 173
X21 + X22 + X23 + X24 + X25 + X26 < 68
X31 + X32 + X33 + X34 + X35 + X36 < 44
X11 + X21 + X31 > 49
X12 + X22 + X32 > 38
X13 + X23 + X33 > 17
X14 + X24 + X34 > 64
X15 + X25 + X35 > 57
X16 + X26 + X36 > 9
END

C:\LINDO>LINDO
...
: TAKE TRANS.EX 
: PIC

   X X X X X X X X X X X X X X X X X X
   1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3
   1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 

1: 4 6 6 2 4 3 7 9 4 5 9 6 6 7 5 5 7 7 MIN
2: 1 1 1 1 1 1 '     '     '     '     < C
3: '  '  '  '  1 1'1 1 1'1 ' '   '  '  < B
4:       '     '     '     1 1 1 1 1 1 < B
5: 1     '     1     '     1     '     > B
6: ' 1'  '  '  ' 1'  '  '  ' 1'  '  '  > B
7:     1 '     '   1 '     '    1'     > B
8:       1     '     1     '     1     > B
9: ' ' '  1'   '  '  ' 1'  ' ' '  1  ' > B
10:       ' 1  '     '  1  '      ' 1  > 9

: LOOK ALL

MIN 4 X11 + 6 X12 + 6 X13 + 2 X14 + 4 X15 + 3 X16 + 7 X21
+ 9 X22 + 4 X23 + 5 X24 + 9 X25 + 6 X26 + 6 X31 + 7 X32
+ 5 X33 + 5 X34 + 7 X35 + 7 X36

SUBJECT TO

2) X11 + X12 + X13 + X14 + X15 + X16 <= 173
3) X21 + X22 + X23 + X24 + X25 + X26 <= 68
4) X31 + X32 + X33 + X34 + X35 + X36 <= 44
5) X11 + X21 + X31 >= 49
6) X12 + X22 + X32 >= 38
7) X13 + X23 + X33 >= 17
8) X14 + X24 + X34 >= 64
9) X15 + X25 + X35 >= 57
10) X16 + X26 + X36 >= 9

END

: GO
LP OPTIMUM FOUND AT STEP 9

OBJECTIVE FUNCTION VALUE

1)             925.000000

VARIABLE          VALUE       REDUCED COST
     X11          43.000000    0.000000
     X12           0.000000    1.000000
     X13           0.000000    4.000000
     X14          64.000000    0.000000
     X15          57.000000    0.000000
     X16           9.000000    0.000000
     X21           0.000000    1.000000
     X22           0.000000    2.000000
     X23          17.000000    0.000000
     X24           0.000000    1.000000
     X25           0.000000    3.000000
     X26           0.000000    1.000000
     X31           6.000000    0.000000
     X32          38.000000    0.000000
     X33           0.000000    1.000000
     X34           0.000000    1.000000
     X35           0.000000    1.000000
     X36           0.000000    2.000000

ROW           SLACK OR SURPLUS   DUAL PRICES
  2)           0.000000            2.000000
  3)          51.000000            0.000000
  4)           0.000000            0.000000
  5)           0.000000           -6.000000
  6)           0.000000           -7.000000
  7)           0.000000           -4.000000
  8)           0.000000           -4.000000
  9)           0.000000           -6.000000
 10)           0.000000           -5.000000

NO. ITERATIONS= 9

DO RANGE(SENSITIVITY) ANALYSIS?
? NO
: QUIT

The General Linear Programming Formulation for the Transportation Problem:

LINGO Formulation (Time Permitting)

 Returning to the Transportation Problem:

The Balanced Transportation Problem (Winston, p. 341):

The Transportation Tableau (Winston, p. 343):

Exercises: Winston, pp. 349ff, #1-10

Addtional Problem: Solve the following problem using LINDO.

The Battle of Clesius] General Ozymandias has just received word that the Visigoths are on a forced march and will attack the northern provinces in three days unless a sufficient force can be gathered in time to repel the invaders. The general has three message runners in his camp and can communicate by means of signal flags to three other nearby encampments that have two, one, and two runners. No other encampments can be contacted except by message runners. If the other camps receive the message, they will send troops as quickly as possible. Of course, the sooner the message is received the more troops any camp can get to the battlefield on time. The following table gives the expected number of troops that each camp can provide, dependent upon the message source.

Expected Number of Troops

                                   Frontier Camps                                    
Message
Source         1      2      3     4    5     6   7  8   9  10 11 12

1 (3 runners) 225 200 210 150 60 175 0 10 25 25 0 190
2 (2 runners) 200 210 210 25 90 90 22 0 100 100 0 120
3 (1 runner) 210 220 225 75 50 160 75 65 50 160 35 65
4 (2 runners) 75 90 95 100 75 135 90 50 75 200 25 175 

Formulate as a transportation problem, where we are to maximize the expected number of troops present at the battlefield in time to fight the Visigoths.

HINT: Let the "suppliers" be the runners and the "demanders" be the frontier camps (each requiring 1). You will also need a "dummy" supply. Why? Remember that the transportation model is has a minimization function in the objective function. 

The Source for these two examples is Hillier and Liebermann (4th Edition), Operations Research, pp. 189ff. 

The Northern Airplane Company

The Northern Airplane Company builds commercial airplanes for various airline companies around the world. The last stage in the production process is to produce the jet engines and then to install them (a very fast operation) in the completed airplane frame. The company has been working under some contracts to deliver a considerable number of airplanes in the near future, and the production of the jet engines for these planes must now be scheduled for the next 4 months.

To meet the contracted dates for delivery, the company must supply engines for installation in the quantities indicated in the second column of the table given below. Thus the cumulative number of engines produced by the end of months 1, 2, 3, and 4 must be at least 10, 25, 50, 70, respectively. The facilities that will be available for producing the engines vary according to other production, maintenance, and renovation work scheduled during this period. The resulting monthly differences in the maximum number that can be produced and the cost (in millions of dollars) of producing each one are given in the third and fourth columns of the table given below. Because of the variations in production costs, it may well be worthwhile to produce some of the engines in a month or more before they are scheduled for installation, and this possibility is being considered. The drawback is that such engines must be stored until the scheduled installation (the airplane frames will not be ready early) at a storage cost of $15,000/month (including interest on expended capital) for each engine (For modeling purposes, assume that this storage cost is incurred at the end of the month) for just those engines that are being held over into the next month. Thus engines that are produced in a given month for installation in the same month are assumed to incur no storage cost.] as shown in the last column of the table given below. Therefore, the production manager wants a schedule developed for the number of engines to be produced in each of the 4 months so that the total of the production and storage costs will be minimized.

Month           Scheduled      Maximum     Unit Cost    Unit Cost
                     Installations    Production    of Prod.      of Storage
                                                                  $10⁶            $10⁶
1                       10                  25            1.08             0.015
2                       15                  35             1.11            0.015
3                       25                  30             1.10            0.015
4                       20                  10             1.13             -----

Consider the following "Non-Transportation" LP formulation:

Let,

x_j = Number of jet engines produced in month j (j = 1, 2, 3, 4). 

z_j = "Over-production" in month j (j = 1, 2, 3, 4).

Consider the following LINDO solution:

C:\LINDO> TYPE PLANE.LIN

MIN 1.08 X1 + 1.11X2 + 1.1 X3 +1.13 X4 + .015 Z1 + .015 Z2
+.015 Z3 + .015 Z4
ST
X1 - Z1 = 10
X1 + X2 - Z2 = 25
X1 + X2 + X3 -Z3 = 50
X1 + X2 + X3 + X4 - Z4 = 70
END
SUB X1 25
SUB X2 35
SUB X3 30
SUB X4 10

C:\LINDO> LINDO

...
: TAKE PLANE.LIN 

: PIC

X X X X Z Z Z Z

1 2 3 4 1 2 3 4

 .....

: LOOK ALL
MIN 1.08 X1 + 1.11 X2 + 1.1 X3 + 1.13 X4 + 0.015 Z1
+ 0.015 Z2 + 0.015 Z3 + 0.015 Z4
SUBJECT TO
2) X1 - Z1 = 10
3) X1 + X2 - Z2 = 25
4) X1 + X2 + X3 - Z3 = 50
5) X1 + X2 + X3 + X4 - Z4 = 70
END
SUB X1 25.00000
SUB X2 35.00000
SUB X3 30.00000
SUB X4 10.00000
: GO

LP OPTIMUM FOUND AT STEP 7

OBJECTIVE FUNCTION VALUE

1)     77.3000031

VARIABLE     VALUE     REDUCED COST
     X1     25.000000    -0.015000
     X2      5.000000     0.000000
     X3     30.000000    -0.025000
     X4     10.000000    -0.010000
     Z1     15.000000     0.000000
     Z2      5.000000     0.000000
     Z3     10.000000     0.000000
     Z4      0.000000     1.155000

ROW        SLACK OR SURPLUS    DUAL PRICES

...

NO. ITERATIONS= 7

DO RANGE(SENSITIVITY) ANALYSIS?
? N
: QUIT 

 Now consider formulating the problem as a transportation problem:

Let,

Source i = production of jet engines in month i (i = 1, 2, 3, 4).

Destination j = installation of jet engines in month j (j = 1, 2, 3, 4).

c_ij = cost associated with each unit of x_ij, i.e.cost per unit for production and any storage, if i < j, and ?

if i > j.

s_i = ?

d_j = number of scheduled installations in month j. 

Exercise: Solve the Northern Airplane problem using both formulations.
(cp. Example 3 in Winston, pp. 344ff)

The Metro District is an agency that administers the distribution of water in a certain large geographic region. The region is fairly arid, so the District must purchase and bring in water from outside the region. The sources of this imported water are the Columbo, Sacron, and Calorie Rivers. The District then resells the water to users in its region. Its main customers are the water departments of the cities of Berdoo, Los Devils, San go, and Hollyglass. It is possible to supply any of these cities with water brought in from any of the three rivers, with one exception that no provision has been made to supply Hollyglass with Calorie River water. However, because of the geographic layouts of the viaducts and the cities in the region, the cost to the District of supplying water depends upon both the source of the water and the city being supplied. The variable cost per acre foot of water (in dollars) for each combination of river and city is given in the table, below. Despite these variations, the price per acre foot charged by the District is independent of the source of the water and is the same for all cities.

The management of the District is now faced with the problem of how to allocate the available water during the upcoming summer season. Using units of 1 million acre feet, the amounts available from the three rivers are given in the right-hand column of the table, below. The District is committed to providing a certain minimum amount to meet the essential needs of each city (with the exception of San Go, which has an independent source of water), as shown in the min. needed row of the table. The requested row indicates that Los Devils desires no more than the minimum amount, but that Berdoo would like to buy as much as 20 more, San Go would buy up to 30 more, and Hollyglass will take as much as it can get. 

Management wishes to allocate all the available water from the three rivers to the four cities in such a way as to at least meet the essential needs of each city while minimizing the total cost to the District.

                                    Cost ($) per acre foot

                                         City

 \
R\
i   \
v   \                Berdoo       Los      San      Holly-      Supply
er   \                                 Devils  Go        glass                    
Columbo R.    16               13      22          17            50
Sacron R.       14               13      19          15            60
Calorie R.       19               20       23          --           50      
Min. Needed   30               70       0           10        (in units
                                                                               of million
Requested        50               70      30          inf.        acre feet) 

We now proceed to formulate the problem as a transportation problem:

(cp. Example 2 inWinston, pp. 343ff)

Additional Transportation Problem Assignment:

Source: Hillier & Lieberman, Operations Research-- 4th edition, # 17. p. 231)

The Build-Em-Fast Company has agreed to supply its best customer with three widgits during each of the next three weeks, even though producing them will require some overtime work. The relevant production data are as follows: 

Week       Maximum      Maximum     Production cost
                Production     Production   per unit, regular
                regular           overtime       regular time
                time                                                             
1                2                    2                  $6,000
2                2                    1               $10,000
3                1                    2                 $8,000 

The cost per unit produced with overtime for each week is $2,000 more than for regular time. The cost of storage is $1,000 per unit for each week it is stored. There is already an inventory of two widgits on hand currently, but the company does not want to retain any widgits in inventory after the three weeks. 

Management wants to know how many units should be produced in each week in order to maximize profit.

Formulate as a transportation problem and solve using LINDO.

Plausibility Argument for the number of variables in a basic feasible solution for a balanced transportation problem:

Theorem: A basic solution to a balanced transportation problem has m + n -1 variables.

Three methods for obtaining an initial basic feasible solution for a transportation problem:

1. Northwest Corner Method
2. Minimum Cost Method
3. Vogel’s Method

Northwest Corner Rule
(Winston, pp. 354ff)

To find a bfs by the Northwest Corner method, we begin in the upper left (or northwest) corner of the transportation tableau and set x₁₁ as large as possible. Clearly, x₁₁ can be no larger than the smaller of s₁ and d₁. If x₁₁ = s₁, cross out the first row of the transportation tableau; this indicates that no more basic variables will come from row 1. Also change d₁ to d₁ - s₁. If x₁₁ = d₁, cross out the first column of the transportation tableau; this indicates that no more basic variables will come from column 1. Also change s₁ to s₁ - d₁. If x₁₁ = s₁ = d₁, cross out either row 1 or column 1 (but not both). If you cross out row1, change d₁ to 0; if you cross out column 1, change s₁ to 0.

Continue applying this procedure to the most northwest cell in the tableau that does not lie in a crossed-out row or column. Eventually, you will come to a point where there is only one cell that can be assigned a value. Assign this cell a value equal to its row or column demand, and cross out both the cell’s row and column. A basic feasible solution has now been obtained.

Example:

Minimum Cost Method for Finding a Basic Feasible Solution
(Winston, pp. 356ff)

To begin the minimum cost method, find the variable with the smallest shipping cost (call it x_ij). Then assign x_ij its largest possible value, min{s_i, d_j}. As in the Northwest Corner method, cross out row I or column j and reduce the supply or demand of the noncrossed-out row or column the cell with the minimum shipping cost and repeat the procedure. Continue until there is only one cell that can be chosen. In this case, cross out both the cell’s row and column. Remember that (with the exception of the last variable) if a variable satisfies both a supply and demand constraint, only cross out a row or column, not both.

Example:

Vogel’s Method for Finding a Basic Feasible Solution
(Winston, pp. 358ff) 

Begin by computing for each row (and column) a "penalty" equal to the difference between the two smallest costs in a row (column). Next find the row or column with the largest penalty. Choose as the first basic variable the variable inthe row or column that has the smallest shipping cost. As described in the Northwest Corner and minimum cost methods, make this variable as large as possible, cross out a row or column, and change the supply or demand associated with the basic variable. Now recompute new penalties (using only cells that do not lie in a crossed-out row or column), and repeat the procedure until only one uncrossed cell remains. Set this variable equal to the supply or demand associated with the variable, and cross out the variable’s row and column. A bfs has now been obtained. 

Example

Assignment: Winston, p. 360, #1-4

The following two methods will be discussed:

1. Stepping Stone Method
2. U-V Method

Stepping Stone Method

 Source: Ravindran, et. al. Operations Research, p. 82

Partial Description of Stepping Stone Method: 

This method determines whether the an initial basic feasible solution is optimal. We know from the simplex method that a given basic feasible solution minimizes the objective function only if the net change in the objective function per unit increase in all nonbasic variables (taken one at a time) causes the objective function to increase. These individual net changes in the objective function (for each nonbasic variable) are called relative cost coefficients in some references.

In a transportation problem the relative cost coefficients are computed by increasing a nonbasic variable by one unit, and computing the resulting change in the total transportation cost. If all are nonnegative, then, the current basic feasible solution is optimal. If there are negative relative cost coefficients, choose the nonbasic variable with the most negative relative cost coefficient to be a basic variable and make the appropriate adjustments to obtain the next basic feasible solution. Continue until optimality is reached.

Example: 

U-V Method (Transportation Simplex Method)
(Winston, pp. 366-367)

Step 1: If the problem is unbalanced, balance it.

Step 2: Use one of the methods described earlier to find a bfs.

Step 3: Set u₁ = 0 and determine u_i and v_j such that u_i + v_j = c_ij for all basic variables.

Step 4: If u_i + v_j - c_ij < 0 for all nonbasic variables, then the current bfs is optimal. If this is not the case, we enter the variable with the most positive u_i + v_j - c_ij into the basis using the pivoting procedure (see below). This yields a new bfs.

Step 5: Using the new bfs, return to Steps 3 and 4.

For maximation problems, proceed as stated, but replace Step 4 by Step 4’ (below):

Step 4’: If u_i + v_j - c_ij > 0 for all nonbasic variables, the current bfs is optimal. Otherwise, enter the variable with the most negative u_i + v_j - c_ij into the basis using the pivoting procedure described earlier.

Pivoting in a Transportation Problem
(Winston, p. 361) 

Step 1: Determine (by the criterion used above) the variable that should enter the basis.

Step 2: Find the loop (it can be shown that there is only one loop) involving the entering variable and some of the basic variables.

Step 3: Counting only cells in the loop, label those found in Step 2 that are an even number (0, 2, 4 and so on) of cells away from the entering variable as even cells. Also label those that are an odd number of cells away from the entering variable as odd cells.

Step 4: Find the odd cell whose variable assumes the smallest value. Call this value theta. The variable corresponding to this odd cell will leave the basis. To perform the pivot, decrease the value of each odd cell by theta and increase the value of each even cell by theta. The values of variables not in the loop remain unchanged. The pivot is now complete. If theta = 0, the entering variable will equal 0, and an odd variable that has a current value of 0 will leave the basis. In this case, a degenerate bfs existed before and will result after the pivot. If more than one odd cell in the loop equals theta, you may arbitrarily choose one of these odd cells to leave the basis; again a degenerate bfs will result. 

Example