Determine the minimum transportation cost from the following matrix. WarehousesMarketSupplyIIIIIIIVM1635422M2592715M357868Demand71217945

Solution to the Transportation Problem

1. Problem Formulation and Feasibility Check

First, we verify if the transportation problem is balanced. A problem is balanced if the total supply equals the total demand.

Total Supply: $$S=22+15+8=45$$

Total Demand: $$D=7+12+17+9=45$$

Since Total Supply ($45$) = Total Demand ($45$), the problem is balanced. No dummy row or column is required.

The cost matrix $C_{ij}$, supply $S_i$, and demand $D_j$ are:

2. Initial Basic Feasible Solution (IBFS)

We use the Least Cost Method (LCM) to find the IBFS, as it generally yields a solution closer to the optimal one compared to the North-West Corner Rule. We allocate units to the cell with the lowest cost in the remaining sub-matrix, satisfying the smallest of the remaining supply or demand.

Step 1: The lowest cost in the entire matrix is 2 at cell $(M2,III)$.

• Supply at M2 = 15, Demand at III = 17.
• Allocate $\min (15,17)=15$ units to $(M2,III)$.
• M2 supply becomes 0 (row M2 is exhausted).
• Demand at III becomes $17-15=2$.

Step 2: The lowest cost in the remaining active cells (excluding M2) is 3 at cell $(M1,II)$.

• Supply at M1 = 22, Demand at II = 12.
• Allocate $\min (22,12)=12$ units to $(M1,II)$.
• Demand at II becomes 0 (column II is exhausted).
• Supply at M1 becomes $22-12=10$.

Step 3: The lowest cost in the remaining active cells is 4 at cell $(M1,IV)$.

• Supply at M1 = 10, Demand at IV = 9.
• Allocate $\min (10,9)=9$ units to $(M1,IV)$.
• Demand at IV becomes 0 (column IV is exhausted).
• Supply at M1 becomes $10-9=1$.

Step 4: The lowest cost in the remaining active cells is 5 at cell $(M1,I)$.

• Supply at M1 = 1, Demand at I = 7.
• Allocate $\min (1,7)=1$ unit to $(M1,I)$.
• Supply at M1 becomes 0 (row M1 is exhausted).
• Demand at I becomes $7-1=6$.

Step 5: The remaining cells are in Row M3. The lowest cost is 5 at cell $(M3,I)$.

• Supply at M3 = 8, Demand at I = 6.
• Allocate $\min (8,6)=6$ units to $(M3,I)$.
• Demand at I becomes 0 (column I is exhausted).
• Supply at M3 becomes $8-6=2$.

Step 6: The only remaining demand is at Market III (2 units). The only remaining supply is at M3 (2 units).

• Allocate 2 units to cell $(M3,III)$.
• Cost at $(M3,III)$ is 8.
• All supplies and demands are now satisfied.

Initial Allocation Table:

Number of Basic Variables ($m+n-1$): $m=3,n=4\Rightarrow 3+4-1=6$. We have 6 allocations: $(1,1),(1,2),(1,4),(2,3),(3,1),(3,3)$. The solution is non-degenerate.

3. Optimality Test using MODI (U-V) Method

We calculate the dual variables $u_i$ (for rows) and $v_j$ (for columns) such that $u_i+v_j=C_{ij}$ for all basic cells.

Let $u_1=0$.

1. From cell $(1,1)$: $u_1+v_1=6\Rightarrow 0+v_1=6\Rightarrow {\mathbf{v}}_1=6$
2. From cell $(1,2)$: $u_1+v_2=3\Rightarrow 0+v_2=3\Rightarrow {\mathbf{v}}_2=3$
3. From cell $(1,4)$: $u_1+v_4=4\Rightarrow 0+v_4=4\Rightarrow {\mathbf{v}}_4=4$
4. From cell $(3,1)$: $u_3+v_1=5\Rightarrow u_3+6=5\Rightarrow {\mathbf{u}}_3=-1$
5. From cell $(3,3)$: $u_3+v_3=8\Rightarrow -1+v_3=8\Rightarrow {\mathbf{v}}_3=9$
6. From cell $(2,3)$: $u_2+v_3=2\Rightarrow u_2+9=2\Rightarrow {\mathbf{u}}_2=-7$

Summary of Dual Variables: $u_1=0,u_2=-7,u_3=-1$ $v_1=6,v_2=3,v_3=9,v_4=4$

Now, we calculate the opportunity cost (or penalty) $P_{ij}=C_{ij}-(u_i+v_j)$ for all non-basic cells. If all $P_{ij}\ge 0$, the solution is optimal.

Since $P_{13}=-4$ is negative, the current solution is not optimal. We must enter cell $(1,3)$ into the basis.

4. Iteration 1: Improvement

Step 1: Form the Closed Loop Starting from the entering cell $(1,3)$, we form a closed loop using only basic cells and the entering cell. The signs alternate $+$ and $-$.

Loop: $(1,3)\to (1,1)\to (3,1)\to (3,3)\to (1,3)$

Step 2: Determine the Amount to Shift ($\theta$) $\theta =\min (\text{allocations at negative sign cells})=\min (1,2)=1$.

Step 3: Update Allocations

• $(1,3)=0+1=1$
• $(1,1)=1-1=0$ (Leaves basis)
• $(3,1)=6+1=7$
• $(3,3)=2-1=1$
• Other allocations remain unchanged: $(1,2)=12,(1,4)=9,(2,3)=15$.

New Allocation Table:

Basic cells: $(1,2),(1,3),(1,4),(2,3),(3,1),(3,3)$.

5. Optimality Test for Iteration 1

Recalculate $u_i$ and $v_j$ with $u_1=0$.

1. From $(1,2)$: $u_1+v_2=3\Rightarrow 0+v_2=3\Rightarrow {\mathbf{v}}_2=3$
2. From $(1,3)$: $u_1+v_3=5\Rightarrow 0+v_3=5\Rightarrow {\mathbf{v}}_3=5$
3. From $(1,4)$: $u_1+v_4=4\Rightarrow 0+v_4=4\Rightarrow {\mathbf{v}}_4=4$
4. From $(2,3)$: $u_2+v_3=2\Rightarrow u_2+5=2\Rightarrow {\mathbf{u}}_2=-3$
5. From $(3,3)$: $u_3+v_3=8\Rightarrow u_3+5=8\Rightarrow {\mathbf{u}}_3=3$
6. From $(3,1)$: $u_3+v_1=5\Rightarrow 3+v_1=5\Rightarrow {\mathbf{v}}_1=2$

Summary of Dual Variables: $u_1=0,u_2=-3,u_3=3$ $v_1=2,v_2=3,v_3=5,v_4=4$

Calculate $P_{ij}=C_{ij}-(u_i+v_j)$ for non-basic cells:

Since $P_{34}=-1$ is negative, the solution is still not optimal. Cell $(3,4)$ enters the basis.

6. Iteration 2: Improvement

Step 1: Form the Closed Loop Entering cell: $(3,4)$. Loop: $(3,4)\to (1,4)\to (1,3)\to (3,3)\to (3,4)$

Step 2: Determine the Amount to Shift ($\theta$) $\theta =\min (\text{allocations at negative sign cells})=\min (9,1)=1$.

Step 3: Update Allocations

• $(3,4)=0+1=1$
• $(1,4)=9-1=8$
• $(1,3)=1+1=2$
• $(3,3)=1-1=0$ (Leaves basis)
• Other allocations remain unchanged: $(1,2)=12,(2,3)=15,(3,1)=7$.

New Allocation Table:

Basic cells: $(1,2),(1,3),(1,4),(2,3),(3,1),(3,4)$.

7. Optimality Test for Iteration 2

Recalculate $u_i$ and $v_j$ with $u_1=0$.

1. From $(1,2)$: $u_1+v_2=3\Rightarrow 0+v_2=3\Rightarrow {\mathbf{v}}_2=3$
2. From $(1,3)$: $u_1+v_3=5\Rightarrow 0+v_3=5\Rightarrow {\mathbf{v}}_3=5$
3. From $(1,4)$: $u_1+v_4=4\Rightarrow 0+v_4=4\Rightarrow {\mathbf{v}}_4=4$
4. From $(2,3)$: $u_2+v_3=2\Rightarrow u_2+5=2\Rightarrow {\mathbf{u}}_2=-3$
5. From $(3,4)$: $u_3+v_4=6\Rightarrow u_3+4=6\Rightarrow {\mathbf{u}}_3=2$
6. From $(3,1)$: $u_3+v_1=5\Rightarrow 2+v_1=5\Rightarrow {\mathbf{v}}_1=3$

Summary of Dual Variables: $u_1=0,u_2=-3,u_3=2$ $v_1=3,v_2=3,v_3=5,v_4=4$

Calculate $P_{ij}=C_{ij}-(u_i+v_j)$ for non-basic cells:

All $P_{ij}\ge 0$. Therefore, the current solution is optimal.

8. Calculation of Minimum Transportation Cost

Using the final optimal allocation:

Total Cost $=36+10+32+30+35+6=149$.

The minimum transportation cost is 149.