Topper Copies

Minimize total transportation cost: costs from factories 1, 2, 3 (rows) to sites 1 to 4 (columns) are $\begin{pmatrix} 2 & 3 & 11 & 7 \\ 1 & 0 & 6 & 1 \\ 5 & 3 & 15 & 9 \end{pmatrix}$, demand $= 7, 5, 3, 2$, supply $= 6, 1, 10$.

Kush Motwani, AIR 11, 2023

demand $= 7, 5, 3, 2$

$\downarrow$

total demand $= 17$

supply $= 6, 1, 10$

$\Rightarrow$ total supply $= 17$

total supply = total demand

$\Rightarrow$ Balanced

Finding initial solution using Vogel's :

diff between min and 2nd min cost

[Vogel's table: the cost matrix with crossed-out entries and circled penalties and allocations, row differences on the left, column differences above, the demand column on the right and the supply row below]

$\downarrow$

Thus: IBFS:

| | 1 | 2 | 3 | 4 | |---|---|---|---|---| | 1 | 2 (1) | 3 (5) | 11 | 7 | | 2 | 1 | 0 | 6 (1) | 1 | | 3 | 5 (6) | 8 | 15 (2) | 9 (2) |

no of basis variables $= 6$

no of rows $= m = 3$

no of cols $= n = 4$

$\Rightarrow$ [ $m+n-1 = 6 =$ no of basis variables ]

$\Downarrow$

[ Non degenerate IBFS ]

Now: solving using u-v method :

[ Iteration 1 ]

| | 1 | 2 | 3 | 4 | u | |---|---|---|---|---|---| | 1 | 2 (1) | 3 (5) | 11 | 7 | $u_1 = 0$ | | 2 | 1 | 0 | 6 (1) | 1 | $u_2 = -9$ | | 3 | 5 (6) | 8 | 15 (2) | 9 (2) | $u_3 = -3$ | | v | $v_1 = 9$ | $v_2 = 15$ | $v_3 = 6$ | $v_4 = 5$ | |

Calculating $\Delta_{ij}$ for non basis variables

[ $\Delta_{ij} = u_i + v_j - c_{ij}$ ]

[ $\Delta_{13} = 15 - 3 - 11 = 1$ ]

$\Delta_{14} < 0, \Delta_{21} < 0, \Delta_{22} < 0, \Delta_{24} < 0, \Delta_{32} < 0$.

$\Rightarrow$ [ only $\Delta_{13} > 0$ ]

$\Rightarrow$ (1,3) will come in basis.

consider the closed cycle :

[ (1,1) will exit basis. ]

Iteration 2 :

| | 1 | 2 | 3 | 4 | u | |---|---|---|---|---|---| | 1 | 2 | 3 (5) | 11 (1) | 7 | $u_1 = 0$ | | 2 | 1 | 0 | 6 (1) | 1 | $u_2 = -9$ | | 3 | 5 (1) | 8 | 15 (1) | 9 (2) | $u_3 = -4$ | | v | $v_1 = 9$ | $v_2 = 15$ | $v_3 = 7$ | $v_4 = 5$ | |

Calculating $D_{ij}$ :

$D_{11} < 0,\ D_{14} < 0,\ D_{24} < 0,\ D_{32} < 0$

$D_{21} < 0,\ D_{22} < 0$,

$\downarrow$

$D_{ij} < 0\ \ \forall (i,j)$ not in basis

$\downarrow$

Optimal soln obtained

Factory 1 $\to$ 5 trucks to town 2

$\to$ 1 truck to town 3

Factory 2 $\to$ 1 truck to town 3

Factory 3 $\to$ 7 trucks to town 1

$\to$ 1 truck to town 3

$\to$ 2 truck to town 4

Min cost $= (15 + 35 + 15 + 6 + 11 + 18) \times$ (in 100s of rupees).

Min cost $= 100 \times 100$

$=$ Rs 10000

Hence solved