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 |
Shoham Teberiwal, AIR 77, 2023
Demand = Supply
Vogel's approximation grid (unit cost in brackets, allocation beside it; supply and penalty $d$ on the right, demand and penalty below):
| | 1 | 2 | 3 | supply, $d$ | |---|---|---|---|---| | 1 | (2) 5 | (7) 0 | (4) 0 | 5 → 0, (2) | | 2 | (3) 0 | (3) 0 | (1) 8 | 8 → 0, (2) | | 3 | (5) 0 | (4) 7 | (7) 0 | 7 → 0, (2) | | 4 | (1) 2 | (6) 2 | (2) 10 | 14 → 0, (4) | | demand | 7 → 2 → 0 | 9 → 2 | 18 → 10 → 0 | | | $d$ | (1) | [?] (1) | [?] (2) | |
here we use combination of vogel's approximation and MODI method
d: difference of 2 lowest (highest struck out) values in cells (penalty) and choose highest d
Initial solution is
$v_1 = 1$ $v_2 = 6$ $v_3 = 2$
$1 = u_1$ $-1 = u_2$ $-2 = u_3$ $0 = u_4$
| | $v_1=1$ | $v_2=6$ | $v_3=2$ | |---|---|---|---| | $u_1$ | 5 | | | | $u_2$ | | $+x$ | $8-x$ | | $u_3$ | | 7 | | | $u_4$ | 2 | $2-x$ | $10+x$ |
$\Delta_{ij} = u_i + v_j - c_{ij}$
basic cells = 6 = (4+3 -1)
$\Delta_{11} = 0$ $\Delta_{23} = 0$ $\Delta_{32} = 0$ $\Delta_{4j} = 0$
$\Delta_{12} = 0$ $\Delta_{31} = -5$
$\Delta_{13} = -1$ $\Delta_{33} = -7$
$\Delta_{21} = -3$
$\Delta_{22} = 2$
$\Delta_{23} = 0$
$\therefore$ make $\Delta_{22} = 0$ using $x = 2$
$u_1 = 1$ $v_2 = 4$ $v_3 = 2$
| | | $v_2=4$ | $v_3=2$ | |---|---|---|---| | $u_1=1$ | 5 | | | | $u_2=-1$ | | 2 | 6 | | $u_3=0$ | | 7 | | | $u_4=0$ | 2 | | 12 |
$\Delta_{12} = 5 - 7 = -2$
$\Delta_{13} = -1$
$\Delta_{21} = -3$
$\Delta_{31} = -5$
$\Delta_{33} = 2 - 7 = -5$
$\Delta_{42} = 4 - 6 = -2$
$\Delta_{ij}$ for non-basic cells are negative
$\therefore$ optimality is achieved (MODI method)
Total cost = $(2 \times 5) + (2 \times 3) + (1 \times 6) + (4 \times 7) + (1 \times 2) + (2 \times 12)$
= 76 Rs
From 1 supply to 1 : 5 units from 2 supply to 2&3 : 2&6 units from 3 supply to 1&3 : 2&12 units at least cost = 7[?]