Chapter 5: �Transportation Model and Its Variants

A lecture by:

Dr. Moayad Tanash

​

​

Transportation Model

• Companies produce products at locations called sources and ship these products to customers locations called destinations
• Each source has a limited quantity that can ship
• Each customer destination must receive a required quantity of the product

​

Transportation Model

• Only possible shipments are those directly from a source to destination
• The problem with the above characteristics are generally called “ Transportation problem”. These problems involve the shipment of homogeneous product from a number of supply locations to a number of demand locations

​

Transportation Model

• A transportation problem basically deals with problem, which aims to find the best way to fulfill the demand of n demand points using the capacities of m supply points. While trying to find the best way, generally a variable cost of shipping the product from one supplier to a customer. 

Transportation Model

A typical transportation problem requires three sets of parameters

• Capacities( or suppliers): indicate the most each plant can supply in a given time period.
• Demands( requirements): they are typically estimated from some type of forecasting models.
• Unit shipping cost: it is calculated through a transportation cost analysis

Transportation Model

• The transportation or shipping problems involves determining the amount of goods or items to be transported from a number of sources to a number of destinations.
• Usually the objective is to minimize the total shipping cost.
• Transportation problem is a specific case of linear programming and special algorithm has been developed to solve it.

Transportation Model

The problem: Given need at demand locations, how should we take the limited supply at supply locations and move the goods. The objective is to minimize the total transportation cost.

Transportation Model

• Objective: minimize total transportation cost.
• Variables: quantity of goods shipped from each supply point to each demand point.
• Restrictions:

- nonnegative shipments

- supply availability at each supply location

- demand need at each demand location

Transportation problem variables

Transportation problem stander model

Assumptions

• Unit transportation costs are independent of transported volume.
• Supply and demand are known and independent on price charged for the product.
• Unlimited transportation capacity to ship across any particular transportation route.
• A single commodity is transported.

Standard form of transportation tableau

Example

MG Auto has three plants in Los Angeles, Detroit, and New Orleans and two major distribution centers in Denver and Miami. The quarterly capacities of the three plants are 1000, 1500, and 1200 cars, and the demands at the two distribution centers for the same period are 2300 and 1400 cars. The mileage chart between the plants and the distribution centers is given in Table 5.1.

Example

Example

Balancing the transportation model.

The transportation tableau representation assumes that model is balanced, meaning that the total demand equals to the total supply (which happened to be true—coincidentally—in the MG model). If the model is unbalanced, a dummy source or a dummy destination must be added to restore balance.

Balancing the transportation model.

In the MG model, suppose that the Detroit plant capacity is 1300 cars (instead of 1500). The total supply 1= 3500 cars2 is less than the total demand 1= 3700 cars2, meaning that part of the demand at Denver and Miami will not be satisfied. Because the demand exceeds the supply, a dummy plant (source) with a capacity of 200 cars 1= 3700 - 35002 is added to balance the model. The unit transportation cost from the dummy plant to the two destinations is zero because the plant does not exist.

Balancing the transportation model.

Balancing the transportation model.

The case where the supply exceeds the demand can be demonstrated by assuming that the demand at Denver is 1900 cars only. In this case, we need to add a dummy distribution center to “receive” the surplus supply. Again, the unit transportation cost to the dummy distribution center is zero, unless we require a factory to “ship out” completely. In this case, a high unit transportation cost is assigned from the designated factory to the dummy destination.

Balancing the transportation model.

The transportation Algorithm

The basic steps of the transportation algorithm are exactly those 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 carry out the algorithmic computations more conveniently

The Transportation 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.

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 the equations is redundant, reducing the model to m + n - 1 independent equations and m + n - 1 basic variables.

Determination of the starting solution

The special structure of the transportation problem allows securing a nonartificial starting basic solution using one of three methods:

1. Northwest-corner method
2. Least-cost method
3. Vogel approximation method

Northwest-corner method

The method starts at the northwest-corner cell (route) of the tableau (variable x11).

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 supply (demand) in the uncrossed-out row (column).

Northwest-corner method

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.

Northwest-corner method

Example 5.3-2: 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 Table 5.8. The unit transportation costs, cij (shown in the northeast corner of each box), are in hundreds of dollars. The model seeks the minimum cost shipping schedule between the silos and the mills.

Northwest-corner method

z = 5 * 10 + 10 * 2 + 5 * 7 + 15 * 9 + 5 * 20 + 10 * 18 = $520.

Least-cost method.

The least-cost method finds a better starting solution by targeting the cheapest routes.

​

Step 1: assign as much as possible to the cell with the smallest unit cost (ties are broken arbitrarily).

​

Step 2: 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.

​

Step 3: select the uncrossed-out cell with the smallest unit cost and repeat the process until exactly one row or column is left uncrossed out.

Least-cost method.

Example 5.3-3: The least-cost method is applied to Example 5.3-1. 1.

1- Cell (1, 2) has the least unit cost in the tableau 1= $22. The most that can be shipped through (1, 2) is x12 = 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 1= $42. Assign x31 = 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 truckload to cell (2, 4) (verify!).

Least-cost method.

Example 5.3-3:

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

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 in the row (column) from the next smallest unit cost in the same row (column). This penalty is actually a measure of lost opportunity one forgoes if the smallest unit cost cell is not chosen.

​

​

Vogel approximation method (VaM).

Step 2. Identify the row or column with the largest penalty, breaking 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).

​

Vogel approximation method (VaM).

​

Step 3.

​

1. If exactly one row or column with zero supply or demand remains uncrossed out, stop.
2. 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.
3. 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.
4. Otherwise, go to step 1.

Vogel approximation method (VAM).

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

​

​

​

​

​

​

​

​

​

​

​

​

Vogel approximation method (VAM).

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 x31. Column 1 is now satisfied and must be crossed out. Next, new penalties are recomputed as in Table 5.12, showing that row 1 has the highest penalty (= 9). Hence, we assign the maximum amount possible to cell (1, 2), which yields x12 = 15 and simultaneously satisfies both row 1 and 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 assign x23 = 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 x14 = 0, x34 = 5, and x24 = 10 (verify!).

​

The associated objective value for this solution is z = 15 * 2 + 0 * 11 + 15 * 9 + 10 * 20 + 5 * 4 + 5 * 18 = $475. This solution happens to have the same objective value as in the least-cost method.

Vogel approximation method (VAM).

​

The associated objective value for this solution is z = 15 * 2 + 0 * 11 + 15 * 9 + 10 * 20 + 5 * 4 + 5 * 18 = $475. This solution happens to have the same objective value as in the least-cost method.

Transportation Algorithm

After determining the starting solution (using one of the methods in Section 5.3.1), we use the following algorithm to determine the optimum solution:

​

Step 1. Use the simplex optimality condition to determine the entering variable. 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 (hand) computations.

Transportation Algorithm

Example: Solve the transportation model of Example 5.3-1, starting with the northwest-corner solution. Table 5.13 gives the northwest-corner starting solution as determined in Table 5.9 in

Transportation Algorithm

In the method of multipliers, we associate the multipliers ui and vj with row i and column j of the transportation tableau. For each current basic variable xij, these multipliers are shown in Section 5.3.3 to satisfy the following equations: ui + vj = cij, for each basic xij

​

​

​

​

​

​

​

​

​

As Table 5.13 shows, the starting solution has six basic variables, which leads to six equations in seven unknowns. To solve these equations, the method of multipliers calls for setting any of the multiplier equal to zero. We will arbitrarily set u1 = 0, and then solve for the remaining variables as shown in the following table:

Transportation Algorithm

Next, we use ui and vj to evaluate the nonbasic variables by computing ui + vj - cij, for each nonbasic xij The results of these evaluations are shown in the following table:

​

​

​

​

​

​

​

​

As Table 5.13 shows, the starting solution has six basic variables, which leads to six equations in seven unknowns. To solve these equations, the method of multipliers calls for setting any of the multiplier equal to zero. We will arbitrarily set u1 = 0, and then solve for the remaining variables as shown in the following table:

Transportation Algorithm

The preceding information, together with the fact that ui + vj - cij = 0 for basic xij, is actually equivalent to computing the z-row of the simplex tableau, as the following summary shows:

​

​

​

​

​

​

​

Because the transportation model minimizes cost, the entering variable is the one having the most positive coefficient in the z-row—namely, x31 is the entering variable

Transportation Algorithm

The preceding information, together with the fact that ui + vj - cij = 0 for basic xij, is actually equivalent to computing the z-row of the simplex tableau, as the following summary shows:

​

​

​

​

​

Transportation Algorithm

​

​

​

​

Iteration #1

Transportation Algorithm

​

​

​

​

Iteration #2

Transportation Algorithm

​

​

​

​

Example 2: find the optimal solution for the following transportation problem. Use northwest corner method to find the starting solution (i.e, initial feasible solution)

The Assignment Model

• The classical assignment model deals with matching workers (with varying skills) to jobs.
• The goal is to determine the minimum cost assignment of workers to jobs.
• The general assignment model with n workers and n jobs is represented in Table 5.18.

​

​

​

​

​

​

​

​

The Assignment Model

​

• The element cij represents the cost of assigning worker i to job j( j = 1, 2, …,n ).

​

• There is no loss of generality in assuming that the number of workers and the number of jobs are equal, because we can always add fictitious workers or fictitious jobs to satisfy this assumption.

The Assignment Model

​

• The assignment model is a special case of the transportation model where workers represent sources and jobs represent destinations.
• The supply (demand) amount at each source (destination) exactly equals 1.
• The cost of “transporting” worker i to job j is cij. In effect, the assignment model can be solved directly as a regular transportation model (or as a regular LP).
• The fact that all the supply and demand amounts equal 1 has led to the development of a simple solution algorithm called the Hungarian method.

Hungarian method

Step 1. Determine pi, the minimum cost element of row i in the original cost matrix, and subtract it from all the elements of row i, i = 1, 2, 3.

​

Step 2. For the matrix created in step 1, determine qj, the minimum cost element of column j, and subtract it from all the elements of column j, j = 1, 2, 3.

​

Step 3. From the matrix in step 2, attempt to find a feasible assignment among all the resulting zero entries.

3a. If such an assignment can be found, it is optimal.

3b. Else, additional calculations are needed

Hungarian method

Example: Joe Klyne’s three children, John, Karen, and Terri, want to earn some money for personal expenses. Mr. Klyne has chosen three chores for his children: mowing the lawn, painting the garage door, and washing the family cars. To avoid anticipated sibling competition, he asks them to submit individual (secret) bids for what they feel is fair pay for each of the three chores. Table 5.19 summarizes the bids received. The children will abide by their father’s decision regarding the assignment of chores. The assignment problem will be solved by the Hungarian method.

Hungarian method

Hungarian Method

Hungarian method

Example:

Hungarian method

Example:

Hungarian method