11.7 Chapter Summary & Review
Chapter Summary
This chapter introduced transportation models, a specialized class of linear programming problems aimed at minimizing the cost of distributing goods from multiple supply points (e.g., distribution centres) to multiple demand points (e.g., markets). The discussion began by emphasizing the strategic importance of timely product delivery and the role of distribution centres (DCs) in optimizing logistics and reducing transportation costs.
Transportation models are built upon four key components:
- Supply capacities at each source,
- Demand requirements at each destination,
- Transportation costs between each source-destination pair, and
- Decision variables representing the quantity of goods shipped along each route.
The chapter distinguished between balanced models — where total supply equals total demand — and unbalanced models, which require adjustment through the introduction of dummy supply or demand nodes to ensure feasibility.
Three widely used methods for generating an initial basic feasible solution were presented:
- North-West Corner Method – a simple, cost-agnostic approach,
- Least Cost Method – which prioritizes allocations based on minimum cost, and
- Vogel’s Approximation Method (VAM) – which incorporates opportunity cost to produce more efficient starting solutions.
Each method was illustrated with detailed examples, showing how allocations are made and how total transportation costs are computed.
The chapter then addressed the need to optimize the initial solution. This process begins with degeneracy testing to ensure the solution is structurally sound for optimization. Two optimization techniques were introduced:
- The Stepping Stone Method, which evaluates cost-saving opportunities through closed loops, and
- The Modified Distribution Method (MODI), which uses dual variables to systematically assess and improve the solution.
Worked examples demonstrated how to apply these methods and interpret the results, culminating in the identification of the optimal transportation plan.
Finally, the chapter concluded by showing how the transportation problem can be formulated and solved as a Linear Programming Problem (LPP), providing a foundation for more advanced analytical approaches.
Exercises
1. Define a transportation model and explain its main components.
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 centers) 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.
2. What is the difference between a balanced and an unbalanced transportation model? How can an unbalanced model be converted to a balanced one?
Balanced Transportation Model:
A transportation model is balanced when the total supply equals the total demand:
∑Supply = ∑Demand
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.
3. Transportation Problem: Initial Feasible Solution Using the North-West Corner Method
A company operates two warehouses and serves three markets. The supply, demand, and unit transportation costs are as follows:
| M1 | M2 | M3 | Supply | |
| W1 | 4 | 6 | 8 | 100 |
| W2 | 5 | 3 | 7 | 150 |
| Demand | 80 | 120 | 50 | 250 |
- Is this problem balanced?
- Find an initial feasible solution using the North West Corner method.
- Calculate the total transportation cost for your solution.
Solutions
-
- 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.
- Initial Feasible Solution Using the North-West Corner Method
Step-by-step allocation:-
W1 → M1:
Allocate min (100, 80) = 80 units
→ W1 remaining: 20 units; M1 satisfied -
W1 → M2:
Allocate min (20, 120) = 20 units
→ W1 exhausted; M2 remaining: 100 units -
W2 → M2:
Allocate min (150, 100) = 100 units
→ W2 remaining: 50 units; M2 satisfied -
W2 → M3:
Allocate min (50, 50) = 50 units
→ W2 exhausted; M3 satisfied
-
- Total Transportation Cost
- W1 → M1: 80×4 = 320
- W1 → M2: 20×6 = 120
- W2 → M2: 100×3 = 300
- W2 → M3: 50×7 = 350
- Total Cost: 320 + 120 + 300 + 350 = $1,090
- Is the problem balanced?
4. Applying the Least Cost Method
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: 360 + 320 + 210 + 160 = $1,050
✅ 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.
5. What is Vogel’s Approximation Method (VAM), and why does it often yield a better 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:
- For each row and column, calculate the penalty: the difference between the two lowest transportation costs.
- Identify the row or column with the highest penalty.
- Allocate as much as possible to the lowest-cost cell in that row or column.
- 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.
6. How do you test a transportation model solution for degeneracy, and why is it important?
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.
7. A transportation problem has 3 supply points and 4 demand points. What is the minimum number of positive allocations required in a non-degenerate solution?
Minimum number of positive allocations = r + c – 1 = 3 + 4 – 1 = 6
8. Explain the Stepping Stone Method and its role in finding the optimal transportation solution.
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.
9. In the Mega Farms example, what were the total transportation costs obtained by the three initial solution methods? Which method gave the lowest cost?
- 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.
10. Why might an initial feasible solution not be optimal, and what methods can be used to optimize it?
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
