Transportation Problem Lecture Notes

Introduction to Transportation Problem

• Definition: A transportation problem is a specific type of linear programming problem focused on minimizing the total transportation cost of goods moved from several sources to several destinations, considering supply and demand constraints.
• Phases:
  1. Finding the initial basic feasible solution.
  2. Optimization of that solution.

Phase 1: Finding the Initial Basic Feasible Solution

• Methods to Find Initial Basic Feasible Solution:
  1. Northwest Corner Cell Method
  2. Least Cost Method
  3. Vogel's Approximation Method (VAM)

Steps using Northwest Corner Cell Method:

1. Balancing the Problem: Check if the transportation problem is balanced (total supply equals total demand). If not, add dummy rows or columns to balance it.
2. Start from Northwest Corner: Allocate the minimum of supply or demand to the cell at the northwest corner.
3. Update Supply/Demand: Adjust supply and demand and cross out any exhausted row or column.
4. Repeat: Continue to the next northwest corner until all supplies and demands are met.

Example Problem

• A transportation model with 3 sources and 4 destinations.
• Supply: 250, 350, 400
• Demand: 200, 300, 350, 150
• Initial Allocation:
  • Allocate 200 to (1,1), leaving 50.
  • Allocate 50 to (1,2), exhausting row 1.
  • Allocate 250 to (2,2), exhausting row 2.
  • Allocate 100 to (3,2), leaving 250.
  • Allocate 250 to (3,3), exhausting column 3.
  • Allocate 150 to (3,4), exhausting column 4.
• Total Cost Calculation:
  • After allocation, calculate total transportation cost.
  • Example total cost = 3700.

Phase 2: Optimization using UV Method

• After obtaining the initial basic feasible solution, apply the UV method to optimize.
• Finding U and V Values:
  • Assign U1 = 0 (for the first row).
  • Use the equation: Ui + Vj = Cij (where Cij is the cell cost).
  • Fill U and V for allocated cells.

Steps to Find U and V:

1. Calculate U and V values for each allocated cell based on the costs.
2. Check if the number of allocated cells equals m + n - 1 (where m = number of rows, n = number of columns).
3. If conditions are met, proceed to calculate penalties for non-allocated cells.

Penalties and Looping:

• Calculate Penalties: For non-allocated cells, calculate: Pij = Ui + Vj - Cij.
• If the penalties yield non-positive values, optimality is reached.
• If there are positive penalties, choose the maximum positive value cell and create a closed loop through alternatives of allocations.

Making Adjustments:

• Update the allocation values based on the loop and proceed to find new U and V values.
• Recalculate the penalties.

Finalization

• Continue the process until all penalties are non-positive, signifying that the optimal solution is reached.
• Final Total Cost: After reaching optimality, calculate the final transportation cost.
  • Example total cost after optimization = 2450.

Conclusion

• The transportation problem is effectively solved using the two-phase method, ensuring minimized costs while satisfying supply and demand constraints.