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