1. Algorithm & Example-1
Algorithm
|
Least Cost Method (LCM) Steps (Rule)
|
|
Step-1:
|
Select the cell having minimum unit cost `c_(ij)` and allocate as much as possible, i.e. `min(s_i, d_j)`.
|
|
Step-2:
|
a. Subtract this `min` value from supply `s_i` and demand `d_j`.
b. If the supply `s_i` is 0, then cross (strike) that row and If the demand `d_j` is 0 then cross (strike) that column.
c. If min unit cost cell is not unique, then select the cell where maximum allocation can be possible
|
|
Step-3:
|
Repeat this steps for all uncrossed (unstriked) rows and columns until all supply and demand values are 0.
|
Example-1
Find Solution using Least Cost method
| D1 | D2 | D3 | D4 | Supply | | S1 | 19 | 30 | 50 | 10 | 7 | | S2 | 70 | 30 | 40 | 60 | 9 | | S3 | 40 | 8 | 70 | 20 | 18 | | Demand | 5 | 8 | 7 | 14 | |
Solution:
TOTAL number of supply constraints : 3
TOTAL number of demand constraints : 4
Problem Table is
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 | 30 | 50 | 10 | | 7 | | `S_2` | 70 | 30 | 40 | 60 | | 9 | | `S_3` | 40 | 8 | 70 | 20 | | 18 | | | | Demand | 5 | 8 | 7 | 14 | | |
The smallest transportation cost is 8 in cell `S_3 D_2`
The allocation to this cell is min(18,8) = 8.
This satisfies the entire demand of `D_2` and leaves 18 - 8 = 10 units with `S_3`
Table-1
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 | 30 | 50 | 10 | | 7 | | `S_2` | 70 | 30 | 40 | 60 | | 9 | | `S_3` | 40 | 8(8) | 70 | 20 | | 10 | | | | Demand | 5 | 0 | 7 | 14 | | |
The smallest transportation cost is 10 in cell `S_1 D_4`
The allocation to this cell is min(7,14) = 7.
This exhausts the capacity of `S_1` and leaves 14 - 7 = 7 units with `D_4`
Table-2
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 | 30 | 50 | 10(7) | | 0 | | `S_2` | 70 | 30 | 40 | 60 | | 9 | | `S_3` | 40 | 8(8) | 70 | 20 | | 10 | | | | Demand | 5 | 0 | 7 | 7 | | |
The smallest transportation cost is 20 in cell `S_3 D_4`
The allocation to this cell is min(10,7) = 7.
This satisfies the entire demand of `D_4` and leaves 10 - 7 = 3 units with `S_3`
Table-3
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 | 30 | 50 | 10(7) | | 0 | | `S_2` | 70 | 30 | 40 | 60 | | 9 | | `S_3` | 40 | 8(8) | 70 | 20(7) | | 3 | | | | Demand | 5 | 0 | 7 | 0 | | |
The smallest transportation cost is 40 in cell `S_2 D_3`
The allocation to this cell is min(9,7) = 7.
This satisfies the entire demand of `D_3` and leaves 9 - 7 = 2 units with `S_2`
Table-4
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 | 30 | 50 | 10(7) | | 0 | | `S_2` | 70 | 30 | 40(7) | 60 | | 2 | | `S_3` | 40 | 8(8) | 70 | 20(7) | | 3 | | | | Demand | 5 | 0 | 0 | 0 | | |
The smallest transportation cost is 40 in cell `S_3 D_1`
The allocation to this cell is min(3,5) = 3.
This exhausts the capacity of `S_3` and leaves 5 - 3 = 2 units with `D_1`
Table-5
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 | 30 | 50 | 10(7) | | 0 | | `S_2` | 70 | 30 | 40(7) | 60 | | 2 | | `S_3` | 40(3) | 8(8) | 70 | 20(7) | | 0 | | | | Demand | 2 | 0 | 0 | 0 | | |
The smallest transportation cost is 70 in cell `S_2 D_1`
The allocation to this cell is min(2,2) = 2.
Table-6
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 | 30 | 50 | 10(7) | | 0 | | `S_2` | 70(2) | 30 | 40(7) | 60 | | 0 | | `S_3` | 40(3) | 8(8) | 70 | 20(7) | | 0 | | | | Demand | 0 | 0 | 0 | 0 | | |
Initial feasible solution is
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 | 30 | 50 | 10 (7) | | 7 | | `S_2` | 70 (2) | 30 | 40 (7) | 60 | | 9 | | `S_3` | 40 (3) | 8 (8) | 70 | 20 (7) | | 18 | | | | Demand | 5 | 8 | 7 | 14 | | |
The minimum total transportation cost `= 10 xx 7 + 70 xx 2 + 40 xx 7 + 40 xx 3 + 8 xx 8 + 20 xx 7 = 814`
Here, the number of allocated cells = 6 is equal to m + n - 1 = 3 + 4 - 1 = 6
`:.` This solution is non-degenerate
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
