Step 1: Assign the initial basic feasible solution using the Vogel's Approximation Method (VAM)
1. Find the difference between the two smallest costs in each row and each column.
For row S1: 8-5 = 3; 6-5 = 1; 6-5 = 1; 8-5 = 3
For row S2: 7-4 = 3; 7-6 = 1; 5-4 = 1; 6-5 = 1
For row S3: 9-4 = 5; 6-4 = 2; 6-4 = 2; 8-4 = 4
For column D1: 5-4 = 1; 4-4 = 0; 8-5 = 3
For column D2: 8-4 = 4; 7-4 = 3; 4-4 = 0
For column D3: 7-6 = 1; 7-6 = 1; 6-6 = 0
For column D4: 6-6 = 0; 6-6 = 0; 6-6 = 0
For column D5: 5-4 = 1; 6-4 = 2; 4-4 = 0; 8-4 = 4
2. Select the largest difference in each row and each column.
The largest differences are:
Row S1: 3
Row S2: 3
Row S3: 5
Column D1: 1
Column D2: 4
Column D3: 1
Column D4: 0
Column D5: 4
3. Select the row or column with the largest difference and allocate as much as possible to the cell with the minimum cost in that row or column.
Starting with Row S3, we allocate to D1 (the smallest cost): 4 units
Updated matrix:
Destination
D1 D2 D3 D4 D5 SUPPLY
S1 5 8 6 6 3 8
S2 4 7 7 6 5 5
S3 0 4 6 6 4 5
DEMAND 0 4 5 4 8
4. Recalculate the penalties for the remaining cells:
For row S1: 3; 1; 1; 3
For row S2: 3; 2; 1;
For row S3: ; 1; 1; 4
For column D2: 3; 3;
For column D3: 1;
For column D4: 0;
For column D5: 4
5. Repeat steps 2 and 3 until all demands are satisfied:
Allocate 4 from S3 to D2
Updated matrix:
Destination
D1 D2 D3 D4 D5 SUPPLY
S1 5 8 6 6 3 8
S2 4 7 7 6 5 5
S3 0 0 6 6 4 1
DEMAND 0 0 5 4 8
Allocate 5 from S3 to D3
Updated matrix:
Destination
D1 D2 D3 D4 D5 SUPPLY
S1 5 8 6 6 3 8
S2 4 7 7 6 5 5
S3 0 0 1 6 4 0
DEMAND 0 0 0 4 8
Allocate 4 from S2 to D4 and allocate 1 from S1 to D5
Updated matrix:
Destination
D1 D2 D3 D4 D5 SUPPLY
S1 5 8 6 2 1 7
S2 0 7 7 2 4 1
S3 0 0 1 6 4 0
DEMAND 0 0 0 2 7
Allocate 2 from S1 to D4 and 1 from S2 to D1
Updated matrix:
Destination
D1 D2 D3 D4 D5 SUPPLY
S1 0 8 6 0 1 5
S2 1 7 7 0 4 0
S3 0 0 1 6 4 0
DEMAND 1 0 0 0 7
Finally, allocate the remaining demand from D1 to S1:
Updated matrix:
Destination
D1 D2 D3 D4 D5 SUPPLY
S1 1 8 6 0 0 0
S2 0 7 7 0 4 0
S3 0 0 1 6 4 0
DEMAND 0 0 0 0 7
Step 2: Test optimality using the Stepping Stone Method
Calculate the opportunity costs for each non-zero cell in the final solution:
S1-D2: 8 (basic cell)
S1-D3: 6 (basic cell)
S2-D2: 7 (basic cell)
S2-D3: 7 (basic cell)
S2-D5: 4 (basic cell)
S3-D3: 1 (non-basic cell)
S3-D4: 6 (basic cell)
S3-D5: 4 (basic cell)
Perform the Stepping Stone Method to test optimality.
1. Move one unit from the cell with opportunity cost of 1 (S3-D3) to an adjacent cell and check if the total cost decreases:
If moving from S3-D3 to S2-D3:
Destination
D1 D2 D3 D4 D5
S1 1 7 5 1 0
S2 0 7 8 0 2
S3 0 0 0 6 4
New total cost = 1*7 + 1*7 + 1*8 + 1*6 = 28
2. Move one unit from the cell with opportunity cost of 4 (S2-D5) to an adjacent cell and check if the total cost decreases:
If moving from S2-D5 to S1-D3 or S1-D4:
Destination
D1 D2 D3 D4 D5
S1 1 7 6 1 0
S2 0 7 7 0 3
S3 0 0 1 6 4
New total cost = 1*7 + 1*7 + 1*7 + 1*6 = 27
Since the total cost decreased, the new solution is optimal. The optimal shipping plan is as follows:
From S1 to D1: 1 unit
From S1 to D2: 7 units
From S1 to D3: 6 units
From S2 to D2: 7 units
From S2 to D3: 7 units
From S2 to D5: 3 units
From S3 to D3: 1 unit
From S3 to D4: 6 units
From S3 to D5: 4 units
Total cost = 1*5 + 7*8 + 6*6 + 7*7 + 3*5 + 1*9 + 6*6 + 4*4 = 240
The optimal total cost for shipping 22 loads of the product is 240 kilometers.
A manufacturer wants to ship 22 loads of his product as shown below. The matrix gives the kilometers from sources of supply to the destinations.
Destination
D1
D2
D3
D4
D5
SUPPLY
S1
5
8
6
6
3
8
S2
4
7
7
6
5
5
S3
8
4
6
6
4
9
DEMAND
4
4
5
4
8
Use VAM method to find initial solution and test optimality using steeping stone method.
1 answer