11.6 Finding the Optimal Solution: Minimizing Total Transportation Cost

A basic feasible solution—such as those obtained through the North-West Corner Method, Least Cost Method, or Vogel’s Approximation Method—serves as a starting point in solving a transportation problem. However, these methods do not guarantee optimality. To determine whether further cost reduction is possible, we must assess whether the current solution can be improved.

Step 1: Degeneracy Check

Before proceeding with optimization, it is essential to verify that the solution is non-degenerate. A transportation model is considered non-degenerate if the number of basic allocations equals (number of rows + number of columns − 1). If this condition is not met, the solution is degenerate, and special handling is required before optimization can proceed.

Step 2: Optimization Techniques

If the solution passes the degeneracy test, we can proceed to identify the optimal solution using one of the following methods:

• Stepping Stone Method:
  A trial-and-error approach that evaluates the opportunity cost of unused routes to determine whether reallocating shipments can reduce total cost.
• Modified Distribution Method (MODI or UV Method):
  A more systematic and efficient technique that uses dual variables (U and V) to compute opportunity costs and identify potential improvements.
• Linear Programming (LP):
  A mathematical formulation of the transportation problem that can be solved using the Simplex Method or specialized LP solvers.

These optimization methods will be explored in detail in the following sections, with step-by-step illustrations and examples.

Testing for Degeneracy in a Basic Feasible Solution

In the context of transportation models, a basic feasible solution is said to be degenerate if it does not contain the minimum required number of positive allocations to maintain a unique and solvable structure.

Degeneracy Condition:

Let:

• r = number of supply points (rows)
• c = number of demand points (columns)
• N = number of positive (non-zero) allocations in the solution

Then:

• If N=r+c−1N=r+c−1, the solution is non-degenerate and can proceed directly to optimization.
• If N<r+c−1N<r+c−1, the solution is degenerate, and special adjustments (such as introducing a very small allocation, often denoted by ε) are required to proceed with optimization methods like MODI or Stepping Stone.

Degeneracy can lead to computational difficulties or incorrect results if not properly addressed. Therefore, it is essential to perform this check before attempting to optimize any initial feasible solution

The model reflects a retail firm that supplies its stores in three cities through three DCs as shown in the following tableau.

Using the basic feasible solution, the firm’s current transportation cost is:

The total transportation cost based on the current allocation:

Total Cost = (150×6) + (50×9) + (150×10) + (50×7) + (200×10) = $5,200

This represents the total cost of the current basic feasible solution. The firm now seeks to determine whether this solution is optimal or if further cost reductions are possible.

Step 1: Degeneracy Testing

To assess whether the solution can be optimized, we must first test for degeneracy.

Let:

• N = number of basic (non-zero) allocations = 5
• r = number of supply points (rows) = 3
• c = number of demand points (columns) = 3

According to the degeneracy condition:

N = r + c – 1 = 3 + 3 – 1 = 5

Since N=r+c−1, the solution is non-degenerate, and we can proceed with optimization using methods such as the Modified Distribution Method (MODI) or the Stepping Stone Method.

Finding the Optimal Solution Using the Stepping Stone Method

The Stepping Stone Method is a systematic approach used to evaluate whether a basic feasible solution to a transportation problem can be improved. It does so by analyzing the impact of introducing a shipment into an unoccupied (empty) cell and tracing a closed loop through the tableau to assess the net change in total cost.

Despite the term “loop,” the structure formed is not circular in shape. Instead, it consists of a sequence of horizontal and vertical moves that connect occupied cells, forming a closed path that begins and ends at the same unoccupied cell.

Let us apply the Stepping Stone Method to our example. The following tableau illustrates one such loop identified in the initial solution.

// New image?

Steps in the Stepping Stone Method:

1. Identify All Unoccupied Cells:
   These are the potential candidates for improvement. Each unoccupied cell represents a possible new shipping route.
2. Construct a Closed Loop for Each Unoccupied Cell:
   Starting from the unoccupied cell, trace a path through alternating horizontal and vertical moves, connecting only occupied cells, and return to the starting point. The loop must alternate between adding and subtracting units.
3. Calculate the Net Cost Change for the Loop:
   Assign alternating plus (+) and minus (−) signs to the cells in the loop, starting with a plus at the unoccupied cell. Then compute the net change in cost by summing the products of unit costs and their respective signs.
4. Evaluate All Loops:

• • If all net cost changes are zero or positive, the current solution is optimal.
  • If any net cost change is negative, the solution can be improved. Select the loop with the most negative net cost, adjust the allocations accordingly, and repeat the process.

This method provides a clear and intuitive way to test for optimality and iteratively improve the solution. In the next section, we will demonstrate this process step-by-step using our transportation example.

In the previous tableau, we evaluated the opportunity cost of assigning a shipment to the unoccupied cell D3 → M2. The net cost change associated with this cell was −1, indicating a potential opportunity to reduce the total transportation cost by reallocating shipments through a closed loop.

Interpreting the Negative Opportunity Cost

A negative value (−1) suggests that the current solution could be improved by assigning units to the unoccupied cell D3 → M2. To explore this possibility, we construct a closed loop involving this cell and other occupied cells, following the Stepping Stone procedure.

Loop Construction:

The loop formed is as follows:

D3 → M2 → D2 → M2 → D2 → M3 → D3 → M3 → D3 → M2

This loop includes the following cells:

• D3 → M2 (unoccupied, starting point)
• D2 → M2 (occupied)
• D2 → M3 (occupied)
• D3 → M3 (occupied)

Allocation Adjustments:

We apply alternating +1 and −1 adjustments along the loop:

• +150 units to D3 → M2 (introducing a new shipment)
• −150 units from D2 → M2 (removing the same quantity)
• +150 units to D2 → M3 (reallocating supply)
• −150 units from D3 → M3 (reducing the original allocation)

This reallocation maintains the supply and demand balance while potentially reducing the total cost.

Updated Allocations:

• D3 → M2: 0 → 150
• D2 → M2: 150 → 0
• D2 → M3: 50 → 200
• D3 → M3: 200 → 50

// Perhaps a new image here?

New Total Transportation Cost:

Total Cost = (150×6) + (50×9) + (0×10) + (200×7) + (150×12) + (50×10)

Total Cost = 900 + 450 + 0 + 1400 + 1800 + 500 = $5,050

This revised solution results in a reduced transportation cost of $5,050, compared to the original $5,200—confirming that the previous solution was not optimal.

Finding the Optimal Solution Using the Modified Distribution (MODI) Method

The Modified Distribution Method (MODI) is a powerful optimization technique used to evaluate and improve a basic feasible solution in a transportation model. It relies on the use of dual variables—denoted as Ui for rows and Vj for columns—to calculate the opportunity cost of unoccupied cells and determine whether the current solution is optimal.

Let us apply the MODI method to the previously discussed transportation model.

Step 1: Assign Dual Variables Ui and Vj

For each occupied cell (i.e., a cell with a positive allocation), the cost Cij must satisfy the condition:

Cij = Ui + Vj

We begin by arbitrarily setting one of the dual variables to zero. Let U1=0. Using the occupied cells, we solve for the remaining Ui and Vj values.

From the allocations:

• U1=0
• S1D1 = 6 ⇒ 0 + V1 = 6 ⇒ V1 = 6
• S1D2 = 9 ⇒ 0 + V2 = 9 ⇒ V2 = 9
• S2D2 = 10 ⇒ U2 + 9 = 10 ⇒ U2 = 1
• S2D3 = 7 ⇒ 1 + V3 = 7 ⇒ V3 = 6
• S3D3 = 10 ⇒ U3 + 6 = 10 ⇒ U3 = 4

Step 2: Calculate Opportunity Costs for Unoccupied Cells

For each unoccupied cell, compute the opportunity cost:
dij = Cij − (Ui + Vj)

• d13 = 16 − (0 + 6) = 10
• d21 = 11 − (1 + 6) = 4
• d31 = 16 − (4 + 6) = 6
• d32 = 12 − (4 + 9) = −1

Step 3: Check for Optimality

If all dij ≥ 0, the current solution is optimal.
However, since d32 = −1, the solution is not optimal, and there is an opportunity to reduce the total cost by reallocating shipments.

Step 4: Improve the Solution via Pivoting

We construct a closed loop starting at the most negative cell, S3 → D2, and apply alternating ++ and −− adjustments along the loop:

// Replace image?

Loop:

S3 → D2 (+) → S2 → D2 (−) → S2 → D3 (+) → S3 → D3 (−)

Revised Allocations:

• S3 → D2: 0 → 150
• S2 → D2: 150 → 0
• S2 → D3: 50 → 200
• S3 → D3: 200 → 50

Updated Total Transportation Cost:

Total Cost = (150×6) + (50×9) + (0×10) + (200×7) + (150×12) + (50×10)

= 900 + 450 + 0 + 1400 + 1800 + 500 = 5,050

This confirms that the MODI method leads to the same improved solution previously obtained using the Stepping Stone Method, validating its effectiveness and accuracy

Finding the Optimal Solution Using Linear Programming

The transportation problem can also be formulated and solved as a Linear Programming Problem (LPP). This approach provides a rigorous mathematical framework for minimizing transportation costs while satisfying all supply and demand constraints.

Decision Variables

Let Xij represent the quantity of goods transported from supply point i (e.g., a distribution center) to demand point j (e.g., a market). Each Xij must be non-negative:
Xij ≥ 0 for all i,j

Objective Function

The goal is to minimize the total transportation cost, which is the sum of the products of unit costs and the corresponding decision variables:

Minimize Z = 6 X 11 + 9 X12 + 16 X13 + 11X21 + 10X22 + 7X23 + 16X31 + 12X32 + 10X33

Constraints

The model must satisfy both supply constraints (each source cannot ship more than its available supply) and demand constraints (each destination must receive its required quantity):

Supply Constraints:

X11 + X12 + X13 ≤ 200 (Supply from S1)

X21 + X22 + X23 ≤ 200 (Supply from S2)

X31 + X32 + X33 ≤ 200 (Supply from S3)

Demand Constraints:

X11 + X21 + X31 ≤ 150 (Demand at D1)

X12 + X22 + X32 ≤ 200 (Demand at D2)

X13 + X23 + X33 ≤ 250 (Demand at D3)

This formulation captures the essence of the transportation problem as a linear program. The solution to this LPP will yield the optimal allocation of shipments that minimizes total cost while respecting all constraints.

A detailed explanation of how to solve linear programming problems—using methods such as the Simplex Method or software-based solvers—is provided in the supplementary section of this chapter.