12.6 Chapter Summary & Review
Summary
This chapter explores linear programming (LP) as a mathematical optimization tool for maximizing profit or minimizing cost under resource constraints. It explains the core components of a Linear Programming Problem (LPP)—the objective function, decision variables, constraints, and non-negativity conditions—and introduces the standard form for representing problems. Methods for solving LPPs include the graphical method (for two-variable problems) and the Simplex method (for larger problems), both of which systematically identify optimal solutions within the feasible region. A practical bakery example demonstrates how LP can guide production decisions to maximize profit, while Excel Solver is introduced as a user-friendly software application for solving LP models efficiently.
The chapter also connects LP to transportation models, showing how problems of distributing goods from multiple supply sources to multiple demand destinations can be optimized using the Simplex method in Excel Solver. It compares approaches to finding initial solutions, such as the North-West Corner, Least Cost, and Vogel’s Approximation Methods, and covers optimization tools like the Stepping Stone and MODI methods. Finally, it highlights real-world applications of LP in product mix decisions, diet planning, and manufacturing resource allocation, emphasizing its role in improving efficiency, reducing costs, and supporting data-driven business decisions.
OpenAI. (2025). ChatGPT. [Large language model]. https://chat.openai.com/chat
Prompt: Please take the chapter content in this document attached and summarize the key concepts into no more than two paragraphs. Reviewed by authors.
Exercises
Exercise 1: Define a transportation model and its key components.
Answer:
A transportation model is a type of linear programming formulation used to minimize the cost of distributing goods from multiple supply sources to various demand destinations, subject to supply and demand constraints.
Key Components:
- Supply Points (e.g., factories or warehouses) with fixed capacities.
- Demand Points (e.g., markets or retailers) with fixed requirements.
- Transportation Costs per unit between each supply-demand pair.
- Decision Variables representing the quantity shipped along each route.
Exercise 2: Convert an unbalanced transportation problem into a balanced one.
Solution:
Since the total supply (200) exceeds the total demand (180), the problem is unbalanced. To balance it, introduce a dummy demand point with a requirement of 20 units and zero transportation cost from all supply points.
Exercise 3: Solve using the North-West Corner Method.
Problem Data:
• Supply: A (100), B (100)
• Demand: X (80), Y (60), Z (40)
• Costs:
• A → X/Y/Z: 4 / 6 / 8
• B → X/Y/Z: 5 / 3 / 7
Solution:
• A → X: 80 units (A: 20 remaining)
• A → Y: 20 units (Y: 40 remaining)
• B → Y: 40 units (B: 60 remaining)
• B → Z: 40 units (B: 20 remaining, unused)
Total Cost:
(80×4) + (20×6) + (40×3) + (40×7) = $840
Exercise 4: Solve the same problem using the Least Cost Method.
• B → Y: 60 units (cost = $3; B: 40 remaining)
• A → X: 80 units (A: 20 remaining)
• B → Z: 40 units (B: 0 remaining)
• A → Z: 20 units (A: 0 remaining)
Total Cost:
(60×3) + (80×4) + (40×7) + (20×8) = $820
Exercise 5: Explain Vogel’s Approximation Method (VAM).
Answer:
VAM calculates a penalty for each row and column by finding the difference between the two lowest costs. The highest penalty indicates the greatest opportunity cost. Allocation is made to the lowest-cost cell in that row or column, and the process repeats until all supply and demand are satisfied.
Exercise 6: Test for degeneracy in a 3×3 transportation problem with 4 allocations.
Answer:
Degeneracy occurs when the number of allocations is less than m+n−1, where m is the number of rows and n is the number of columns.
Here, 4 < (3+3−1) = 5, so the solution is degenerate.
To resolve this, introduce a zero-quantity allocation in an unused cell to maintain feasibility.
Exercise 7: Optimize a solution using the Stepping Stone Method.
Given:
Initial cost = $840 (from Question 3)
Optimization Steps:
• Evaluate unused route A → Z
• Closed loop: A-Z → B-Z → B-Y → A-Y → A-Z
• Net cost change: +8 −7 +3 −6 = −2
• Reallocate 20 units along the loop
New Total Cost:
$840 − (20×2) = $800
Exercise 8: When would you use the MODI method over the Stepping Stone method?
Answer:
The MODI (Modified Distribution) method is preferred for larger transportation problems because it is computationally more efficient. It uses dual variables to calculate improvement indices directly, avoiding the need to trace closed loops for each unused cell.
Exercise 9: Case Study: Mega Farms Distribution
Problem Data:
- Warehouses: W1 (50 tons), W2 (70 tons)
- Markets: M1 (40), M2 (30), M3 (50)
- Costs:
- W1 → M1/M2/M3: 2 / 3 / 4
- W2 → M1/M2/M3: 5 / 1 / 3
Solution Using VAM:
- Initial penalties: W1 = 1, W2 = 2; M2 = 2 (highest)
- Allocate W2 → M2: 30 units (W2: 40 remaining)
- Allocate W1 → M1: 40 units (W1: 10 remaining)
- Allocate W1 → M3: 10 units (M3: 40 remaining)
- Allocate W2 → M3: 40 units
Total Cost:
[latex](30 \times 1) + (40 \times 2) + (10 \times 4) + (40 \times 3) = \$270[/latex]
Exercise 10: Why Are Transportation Models Critical in Supply Chain Management?
Transportation models play a vital role in supply chain management by enabling firms to:
- Minimize logistics and distribution costs, which directly improve profit margins.
- Optimize the use of available resources, such as transportation capacity and warehouse inventory.
- Ensure timely and efficient delivery of goods to meet customer demand.
- Enhance overall competitiveness by supporting data-driven decision-making in logistics planning.
These models provide a structured approach to solving complex distribution problems, making them indispensable tools in modern supply chain operations.
