Topper Copies

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$