11.10 Chapter Summary & Review

A transportation model is a specialized form of a linear programming problem designed to determine the most cost-efficient way to distribute goods from multiple supply points (e.g., factories or distribution centres) to multiple demand points (e.g., retail outlets or markets), while satisfying supply and demand constraints.

Main Components:

• Supply Points:
  Locations where goods are available for shipment. Each supply point has a fixed supply capacity.
• Demand Points:
  Locations where goods are required. Each demand point has a specific demand that must be fulfilled.
• Transportation Costs:
  The unit cost of transporting goods from each supply point to each demand point. These costs form the basis of the objective function to be minimized.
• Decision Variables:
  Represent the quantity of goods shipped from the supply point to the demand point. These are the variables to be determined in the optimization process.

Balanced Transportation Model:

A transportation model is balanced when the total supply equals the total demand:

[latex]\sum Supply = \sum Demand[/latex]

This condition ensures that all goods can be distributed without surplus or shortage.

Unbalanced Transportation Model:

A model is unbalanced when:

• Total Supply ≠ Total Demand

This can occur in two ways:

• Supply exceeds demand: There is surplus capacity.
• Demand exceeds supply: There is a shortfall in available goods.

Balancing an Unbalanced Model:

To convert an unbalanced model into a balanced one:

• If Supply < Demand:
  Introduce a dummy demand point with demand equal to the surplus. Assign zero transportation cost from all supply points to this dummy destination.
• If Demand > Supply:
  Introduce a dummy supply point with supply equal to the shortfall. Assign zero transportation cost from this dummy source to all demand points.

This transformation ensures that the model satisfies the balance condition, allowing it to be solved using standard transportation algorithms.

1. Is the problem balanced?
   • Total Supply = 100 (W1) + 150 (W2) = 250 units
   • Total Demand = 80 (M1) + 120 (M2) + 50 (M3) = 250 units.  Yes, the problem is balanced.
2. Initial Feasible Solution Using the North-West Corner Method
   Step-by-step allocation:
   1. (W1/M1): Remaining: 20 units; M1 satisfied
   2. (W1/M2): Allocate min (20, 120) = 20 units
      → W1 exhausted; M2 remaining: 100 units
   3. (W2/M2): Allocate min (150, 100) = 100 units
      → W2 remaining: 50 units; M2 satisfied
   4. (W2/M3): Allocate min (50, 50) = 50 units
      → W2 exhausted; M3 satisfied
3. Total Transportation Cost
   • (W1/M1): [latex]80 \times 4 = 320[/latex]
   • (W1/M2): [latex]20 \times 6 = 120[/latex]
   • (W2/M2): [latex]100 \times 3 = 300[/latex]
   • (W2/M3): [latex]50 \times 7 = 350[/latex]
   • Total Cost: [latex]320 + 120 + 300 + 350 = \$1,090[/latex]

Method Overview:

The Least Cost Method generates an initial feasible solution by prioritizing allocations to the lowest-cost cells first. The steps are:
1. Identify the cell with the lowest transportation cost.
2. Allocate as much as possible to that cell.
3. Adjust supply and demand; eliminate satisfied rows or columns.
4. Repeat with the next lowest-cost cell.

Application to the Problem:

1. (W2/M2) (Cost = 3):
   Allocate min (150, 120) = 120 units
   → W2 remaining: 30; M2 satisfied
2. (W1/M1) (Cost = 4):
   Allocate min 100, 80) = 80 units
   → W1 remaining: 20; M1 satisfied
3. (W2/M3) (Cost = 7):
   Allocate min (30, 50) = 30 units
   → W2 exhausted; M3 remaining: 20
4. (W1/M3) (Cost = 8):
   Allocate the remaining 20 units
   → W1 exhausted; M3 satisfied

Total Transportation Cost

• (W2/M2): 120 × 3 = 360
• (W1/M1): 80 × 4 = 320
• (W2/M3): 30 × 7 = 210
• (W1/M3): 20 × 8 = 160
  Total Cost: [latex]360 + 320 + 210 + 160 = \$1,050[/latex]

The Least Cost Method yields a lower total cost than the North-West Corner Method, demonstrating its efficiency in generating a more cost-effective initial solution.

Vogel’s Approximation Method (VAM) is a heuristic used to generate an initial feasible solution for a transportation problem. It improves cost efficiency by incorporating the concept of opportunity cost into the allocation process.

Steps:

1. For each row and column, calculate the penalty: the difference between the two lowest transportation costs.
2. Identify the row or column with the highest penalty.
3. Allocate as much as possible to the lowest-cost cell in that row or column.
4. Adjust supply and demand, eliminate satisfied rows/columns, and repeat the process.

By considering the cost of not choosing the next-best alternative, VAM often produces a lower total transportation cost than simpler methods like the North-West Corner or Least Cost Method.

A transportation solution is degenerate if the number of positive allocations N is less than r + c − 1, where:

• r = number of supply points (rows)
• c = number of demand points (columns)

Degeneracy Test:

• If N = r + c − 1: the solution is non-degenerate and suitable for optimization.
• If N < r + c −1: the solution is degenerate and must be adjusted (e.g., by inserting a zero allocation in an unoccupied cell) to proceed with optimization.

Importance:

Degeneracy can disrupt optimization methods like Stepping Stone or MODI, which rely on a specific number of basic variables. Testing ensures the solution structure is valid for further improvement.

Minimum number of positive allocations = r + c – 1 = 3 + 4 – 1 = 6

The Stepping Stone Method is an optimization technique used to evaluate whether a current transportation solution can be improved.

How it works:

• For each unoccupied cell, construct a closed loop by connecting it to occupied cells through horizontal and vertical moves.
• Assign alternating + and − signs to the loop cells and calculate the net cost change.
• If the net cost is negative, reallocating along the loop will reduce the total cost.

This process is repeated until no negative net costs remain, indicating that the optimal solution has been reached.

• North-West Corner Method: $1,760
• Least Cost Method: $1,160
• Vogel’s Approximation Method (VAM): $1,140

VAM produced the lowest total transportation cost, demonstrating its effectiveness in generating a near-optimal initial solution.

Initial feasible solutions are constructed using allocation rules that do not necessarily minimize total cost. As a result, they may overlook more efficient shipping routes.

Optimization Methods:

• Stepping Stone Method: Evaluates unoccupied cells for potential cost-saving reallocations.
• Modified Distribution Method (MODI): Uses dual variables to systematically assess opportunity costs and guide reallocation.

These methods refine the initial solution to achieve the minimum possible transportation cost, ensuring true optimality