Topper Copies

Solve the following problem | From \ To | 1 | 2 | 3 | 4 | Supply | |---|---|---|---|---|---| | 1 | 21 | 16 | 25 | 13 | 11 | | 2 | 17 | 18 | 14 | 23 | 13 | | 3 | 32 | 27 | 18 | 41 | 19 | | Demand | 6 | 10 | 12 | 15 | 43 |

Aryan Yadav, AIR 31, 2025

Using Vogel's method to find IBFS $\Rightarrow$

| | 1 | 2 | 3 | 4 | |---|---|---|---|---| | 1 | 21 × | 16 × | 25 × | 13 (11) | | 2 | 17 (6) | 18 (3) | 14 × | 23 (4) | | 3 | 32 × | 27 (7) | 18 (12) | 41 × |

$3+4-1 = 6$ Basic variables

(Non degenerate)

| | 1 | 2 | 3 | 4 | $u_i$ | |---|---|---|---|---|---| | 1 | 21 | 16 | 25 | 13 (11) | $-10$ | | 2 | 17 (6) | 18 (3) | 14 | 23 (4) | 0 | | 3 | 32 | 27 (7) | 18 (12) | 41 | 9 | | $v_j$ | 17 | 18 | 9 | 23 | |

Each $D_{ij} \leq 0 \Rightarrow$ optimality reached

Each non basic var has $D_{ij} \neq 0$

$\Rightarrow$ Optimal soln is unique

Optimal Allocation $\Rightarrow$

| | 1 | 2 | 3 | 4 | |---|---|---|---|---| | 1 | 0 | 0 | 0 | 11 | | 2 | 6 | 3 | 0 | 4 | | 3 | 0 | 7 | 12 | 0 |

(Each cell shows allocation)

Cost $= 11 \times 13 + 6 \times 17 + 3 \times 18 + 4 \times 23 + 7 \times 27 + 12 \times 18$

Cost $= 796$