Question 1173008: The Candido PILI Delicacies has 3 stores (A, B, C) which supplies it's 3 provincial customers (D, E, F) with their best selling product. Below is a table showing the capacity of each store, the requirements of each customer, and the cost for shipping to each customer.
Store D E F CAPACITY
A 30 40 10 150
B 20 10 50 100
C 70 20 20 250
Demand 200 160 140
Find the optimal strategy and minimum cost of transporting their best selling product from store to customer.
Answer by CPhill(1987)   (Show Source):
You can put this solution on YOUR website! Let's solve this transportation problem using a common method, the Vogel's Approximation Method (VAM), followed by the Stepping Stone method to find the optimal solution.
**1. Vogel's Approximation Method (VAM)**
* **Calculate Penalties:** For each row and column, find the difference between the two smallest costs.
* Row A: 30 - 10 = 20
* Row B: 20 - 10 = 10
* Row C: 20 - 20 = 0
* Col D: 30 - 20 = 10
* Col E: 20 - 10 = 10
* Col F: 20 - 10 = 10
* **Allocate Based on Highest Penalty:** Choose the row or column with the highest penalty. Allocate as many units as possible to the cell with the lowest cost in that row or column.
* Row A has the highest penalty (20). Allocate to A-F (cost 10).
* Allocate 140 units to A-F (since F's demand is 140).
* A's capacity is now 10, and F's demand is 0.
* **Recalculate Penalties:** Remove the satisfied column/row and recalculate penalties.
* Row A: 40 - 30 = 10
* Row B: 20 - 10 = 10
* Row C: 70 - 20 = 50
* Col D: 30 - 20 = 10
* Col E: 20 - 10 = 10
* **Allocate Again:** Row C has the highest penalty (50). Allocate to C-E (cost 20).
* Allocate 160 units to C-E (since E's demand is 160).
* C's capacity is now 90, and E's demand is 0.
* **Continue Allocation:**
* Allocate 10 units to A-D. A capacity = 0, D demand = 190.
* Allocate 100 units to B-D. B capacity = 0, D demand = 90.
* Allocate 90 units to C-D. C capacity = 0, D demand = 0.
**Initial Solution (VAM):**
* A-D: 10
* A-F: 140
* B-D: 100
* C-D: 90
* C-E: 160
**Initial Cost:**
* (10 * 30) + (140 * 10) + (100 * 20) + (90 * 70) + (160 * 20) = 300 + 1400 + 2000 + 6300 + 3200 = 13200
**2. Stepping Stone Method (to Check Optimality)**
* We need to check if we can reduce the cost by shifting allocations.
* We'll use the Stepping Stone method to evaluate empty cells.
**Empty Cells:**
* A-E:
* B-E:
* B-F:
* C-F:
**Testing Empty Cells**
* A-E: A-E(+40) -> C-E(-20) -> C-D(+70) -> A-D(-30) = +60
* B-E: B-E(+10)-> C-E(-20) -> C-D(+70) -> B-D(-20)= +40
* B-F: B-F(+50) -> A-F(-10) -> A-D(+30) -> B-D(-20) = +70
* C-F: C-F(+20) -> A-F(-10) -> A-D(+30) -> C-D(-70) = -30
**Adjusting the Solution**
Because cell C-F has a negative value, we will shift allocation to this cell. We will allocate as much as possible, which is 0.
* We have to find a loop that will include C-F.
* C-F(+x)-> A-F(-x)-> A-D(+x) -> C-D(-x)
* We can allocate upto 0 in this case.
**Final Solution (Optimal):**
The first VAM solution is the optimal solution.
* A-D: 10
* A-F: 140
* B-D: 100
* C-D: 90
* C-E: 160
**Minimum Cost:** 13200
**Optimal Strategy:**
* Ship 10 units from Store A to Customer D.
* Ship 140 units from Store A to Customer F.
* Ship 100 units from Store B to Customer D.
* Ship 90 units from Store C to Customer D.
* Ship 160 units from Store C to Customer E.
**Minimum Cost:** 13200
|
|
|
