1. Algorithm & Example-1
Algorithm
|
Column minima method Steps (Rule)
|
|
Step-1:
|
In this method, we allocate as much as possible in the lowest cost cell of the first Column, i.e. allocate `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 process for all uncrossed (unstriked) rows and columns until all supply and demand values are 0.
|
Example-1
1. Find Solution using Column minima 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 | | |
In `1^(st)` column, The smallest transportation cost is 19 in cell `S_1 D_1`
The allocation to this cell is min(7,5) = 5.
This satisfies the entire demand of `D_1` and leaves 7 - 5 = 2 units with `S_1`
Table-1
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19(5) | 30 | 50 | 10 | | 2 | | `S_2` | 70 | 30 | 40 | 60 | | 9 | | `S_3` | 40 | 8 | 70 | 20 | | 18 | | | | Demand | 0 | 8 | 7 | 14 | | |
In `2^(nd)` column, 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-2
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19(5) | 30 | 50 | 10 | | 2 | | `S_2` | 70 | 30 | 40 | 60 | | 9 | | `S_3` | 40 | 8(8) | 70 | 20 | | 10 | | | | Demand | 0 | 0 | 7 | 14 | | |
In `3^(rd)` column, 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-3
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19(5) | 30 | 50 | 10 | | 2 | | `S_2` | 70 | 30 | 40(7) | 60 | | 2 | | `S_3` | 40 | 8(8) | 70 | 20 | | 10 | | | | Demand | 0 | 0 | 0 | 14 | | |
In `4^(th)` column, The smallest transportation cost is 10 in cell `S_1 D_4`
The allocation to this cell is min(2,14) = 2.
This exhausts the capacity of `S_1` and leaves 14 - 2 = 12 units with `D_4`
Table-4
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19(5) | 30 | 50 | 10(2) | | 0 | | `S_2` | 70 | 30 | 40(7) | 60 | | 2 | | `S_3` | 40 | 8(8) | 70 | 20 | | 10 | | | | Demand | 0 | 0 | 0 | 12 | | |
In `4^(th)` column, The smallest transportation cost is 20 in cell `S_3 D_4`
The allocation to this cell is min(10,12) = 10.
This exhausts the capacity of `S_3` and leaves 12 - 10 = 2 units with `D_4`
Table-5
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19(5) | 30 | 50 | 10(2) | | 0 | | `S_2` | 70 | 30 | 40(7) | 60 | | 2 | | `S_3` | 40 | 8(8) | 70 | 20(10) | | 0 | | | | Demand | 0 | 0 | 0 | 2 | | |
In `4^(th)` column, The smallest transportation cost is 60 in cell `S_2 D_4`
The allocation to this cell is min(2,2) = 2.
Table-6
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19(5) | 30 | 50 | 10(2) | | 0 | | `S_2` | 70 | 30 | 40(7) | 60(2) | | 0 | | `S_3` | 40 | 8(8) | 70 | 20(10) | | 0 | | | | Demand | 0 | 0 | 0 | 0 | | |
Initial feasible solution is
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 (5) | 30 | 50 | 10 (2) | | 7 | | `S_2` | 70 | 30 | 40 (7) | 60 (2) | | 9 | | `S_3` | 40 | 8 (8) | 70 | 20 (10) | | 18 | | | | Demand | 5 | 8 | 7 | 14 | | |
The minimum total transportation cost `= 19 xx 5 + 10 xx 2 + 40 xx 7 + 60 xx 2 + 8 xx 8 + 20 xx 10 = 779`
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
|
