1. Algorithm & Example-1
Algorithm
|
Row minima method Steps (Rule)
|
|
Step-1:
|
In this method, we allocate as much as possible in the lowest cost cell of the first row, 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 Row 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)` row, 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-1
| | `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 | 70 | 20 | | 18 | | | | Demand | 5 | 8 | 7 | 7 | | |
In `2^(nd)` row, The smallest transportation cost is 30 in cell `S_2 D_2`.
The allocation to this cell is min(9,8) = 8.
This satisfies the entire demand of `D_2` and leaves 9 - 8 = 1 units with `S_2`
Table-2
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 | 30 | 50 | 10(7) | | 0 | | `S_2` | 70 | 30(8) | 40 | 60 | | 1 | | `S_3` | 40 | 8 | 70 | 20 | | 18 | | | | Demand | 5 | 0 | 7 | 7 | | |
In `2^(nd)` row, The smallest transportation cost is 40 in cell `S_2 D_3`.
The allocation to this cell is min(1,7) = 1.
This exhausts the capacity of `S_2` and leaves 7 - 1 = 6 units with `D_3`
Table-3
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 | 30 | 50 | 10(7) | | 0 | | `S_2` | 70 | 30(8) | 40(1) | 60 | | 0 | | `S_3` | 40 | 8 | 70 | 20 | | 18 | | | | Demand | 5 | 0 | 6 | 7 | | |
In `3^(rd)` row, The smallest transportation cost is 20 in cell `S_3 D_4`.
The allocation to this cell is min(18,7) = 7.
This satisfies the entire demand of `D_4` and leaves 18 - 7 = 11 units with `S_3`
Table-4
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 | 30 | 50 | 10(7) | | 0 | | `S_2` | 70 | 30(8) | 40(1) | 60 | | 0 | | `S_3` | 40 | 8 | 70 | 20(7) | | 11 | | | | Demand | 5 | 0 | 6 | 0 | | |
In `3^(rd)` row, The smallest transportation cost is 40 in cell `S_3 D_1`.
The allocation to this cell is min(11,5) = 5.
This satisfies the entire demand of `D_1` and leaves 11 - 5 = 6 units with `S_3`
Table-5
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 | 30 | 50 | 10(7) | | 0 | | `S_2` | 70 | 30(8) | 40(1) | 60 | | 0 | | `S_3` | 40(5) | 8 | 70 | 20(7) | | 6 | | | | Demand | 0 | 0 | 6 | 0 | | |
In `3^(rd)` row, The smallest transportation cost is 70 in cell `S_3 D_3`.
The allocation to this cell is min(6,6) = 6.
Table-6
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 | 30 | 50 | 10(7) | | 0 | | `S_2` | 70 | 30(8) | 40(1) | 60 | | 0 | | `S_3` | 40(5) | 8 | 70(6) | 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 | 30 (8) | 40 (1) | 60 | | 9 | | `S_3` | 40 (5) | 8 | 70 (6) | 20 (7) | | 18 | | | | Demand | 5 | 8 | 7 | 14 | | |
The minimum total transportation cost `= 10 xx 7 + 30 xx 8 + 40 xx 1 + 40 xx 5 + 70 xx 6 + 20 xx 7 = 1110`
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
|
