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 |

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[?]