Solve the following transportation problem | From \ To | 1 | 2 | 3 | Supply | |---|---|---|---|---| | 1 | 2 | 7 | 4 | 5 | | 2 | 3 | 3 | 1 | 8 | | 3 | 5 | 4 | 7 | 7 | | 4 | 1 | 6 | 2 | 14 | | Demand | 7 | 9 | 18 | 34 |
Aryan Yadav, AIR 31, 2025
Balanced T P
Using vogels method to get IBFS
| Allocations | 1 | 2 | 3 | |---|---|---|---| | 1 | 2 (3) | 7 (2) | 4 | | 2 | 3 | 3 | 1 (8) | | 3 | 5 | 4 (7) | 7 | | 4 | 1 (4) | 6 | 2 (10) |
No. of Basic vars = 6 = 4 + 3 - 1
Non degenerate proceding with
MODI Method $\Rightarrow$
| | 1 | 2 | 3 | $u_i$ | |---|---|---|---|---| | 1 | $2^{(3)}$ | $7^{(2)}$ | 4 | 0 | | 2 | 3 | 3 | $1^{(8)}$ | -2 | | 3 | 5 | $4^{(7)}$ | 7 | -3 | | 4 | $1^{(4)}$ | 6 | $2^{(10)}$ | -1 | | $v_j$ | 2 | 7 | 3 | |
[?] $D_{ij} = u_i + v_j - c_{ij}$
$2^{+\theta}$ - $7^{-\theta}$
$3^{+\theta}$ - $1^{-\theta}$ ; $\theta = 2$
$1^{-\theta}$ - $2^{+\theta}$
New table $\Rightarrow$
| | 1 | 2 | 3 | $u_i$ | |---|---|---|---|---| | 1 | $2^{(5)}$ | 7 | 4 | 2 | | 2 | 3 | $3^{(2)}$ | $1^{(6)}$ | 0 | | 3 | 5 | $4^{(7)}$ | 7 | 1 | | 4 | $1^{(2)}$ | 6 | $2^{(12)}$ | 1 | | $v_j$ | 0 | 3 | 1 | |
Each $\Delta_{ij} \leq 0$ $\Rightarrow$ optimality
Also $\Delta_{ij} = 0$ only For Basic vars $\Rightarrow$ Unique sol$^n$
Optimal Allocation is:
| FROM \ TO | 1 | 2 | 3 | |---|---|---|---| | 1 | 5 | 0 | 0 | | 2 | 0 | 2 | 6 | | 3 | 0 | 7 | 0 | | 4 | 2 | 0 | 12 |
(Each Cell Shows Allocation)
Cost $= 5\times 2 + 3\times 2 + 6\times 1 + 7\times 4 + 2\times 1 + 12\times 2$
$= 76$