1. **State the problem:** We are given a transportation problem with factories F1, F2, F3 supplying units to warehouses W1, W2, W3, W4. The costs per unit and supplies/demands are provided. A feasible solution with allocations is given, and we must: (i) Test optimality of the solution using the MODI method. (ii) If not optimal, find the optimal solution. (iii) Determine the minimum transportation cost. 2. **Data summary:** Cost matrix (C) per unit: $$ \begin{array}{c|cccc} & W1 & W2 & W3 & W4 \\ \hline F1 & 12 & 6 & 20 & 25 \\ F2 & 6 & 11 & 15 & 12 \\ F3 & 9 & 15 & 17 & 7 \end{array} $$ Supply vector: $$[F1:800, F2:600, F3:1000]$$ Demand vector: $$[W1:400, W2:500, W3:700, W4:800]$$ Allocations matrix (X): $$ \begin{array}{c|cccc} & W1 & W2 & W3 & W4 \\ \hline F1 & 300 & 500 & 0 & 0 \\ F2 & 100 & 0 & 500 & 0 \\ F3 & 0 & 0 & 200 & 800 \end{array} $$ 3. **Step 1: Compute the initial transportation cost:** Total cost $Z = \sum C_{ij} X_{ij}$ From allocations: - F1 to W1: $12 \times 300 = 3600$ - F1 to W2: $6 \times 500 = 3000$ - F2 to W1: $6 \times 100 = 600$ - F2 to W3: $15 \times 500 = 7500$ - F3 to W3: $17 \times 200 = 3400$ - F3 to W4: $7 \times 800 = 5600$ Sum: $$Z = 3600 + 3000 + 600 + 7500 + 3400 + 5600 = 23700$$ 4. **Step 2: Apply MODI Method to test optimality:** We define potentials $u_i$ for rows (factories) and $v_j$ for columns (warehouses) such that for every allocated cell $(i,j)$: $$ u_i + v_j = C_{ij} $$ Set $u_1 = 0$ (arbitrary): Allocated cells: - $(F1, W1): u_1 + v_1 = 12 \Rightarrow 0 + v_1 = 12 \Rightarrow v_1=12$ - $(F1, W2): u_1 + v_2 = 6 \Rightarrow 0 + v_2 =6 \Rightarrow v_2=6$ - $(F2, W1): u_2 + v_1 = 6 \Rightarrow u_2 + 12 =6 \Rightarrow u_2 = -6$ - $(F2, W3): u_2 + v_3 = 15 \Rightarrow -6 + v_3=15 \Rightarrow v_3=21$ - $(F3, W3): u_3 + v_3=17 \Rightarrow u_3 + 21=17 \Rightarrow u_3=-4$ - $(F3, W4): u_3 + v_4=7 \Rightarrow -4 + v_4=7 \Rightarrow v_4=11$ 5. **Step 3: Calculate opportunity cost (reduced cost) for non-allocated cells:** For each non-allocated cell $(i,j)$, $$ ext{Opportunity cost }=C_{ij} - (u_i + v_j) $$ - $(F1, W3): 20 - (0 + 21) = -1$ - $(F1, W4): 25 - (0 + 11) = 14$ - $(F2, W2): 11 - (-6 + 6) = 11$ - $(F2, W4): 12 - (-6 + 11) = 7$ - $(F3, W1): 9 - (-4 + 12) = 1$ - $(F3, W2): 15 - (-4 + 6) = 13$ 6. **Step 4: Check optimality:** If all opportunity costs $\\geq 0$, solution is optimal. Here, $(F1, W3)$ has negative opportunity cost $-1$ indicating solution is not optimal. 7. **Step 5: Improve solution by allocating units through closed loop adjustment:** We choose cell $(F1, W3)$ to enter the basis. Constructing a loop alternating + and - signs: Path: - Start: (F1, W3) [+] - Down to (F2, W3) [-] - Left to (F2, W1) [+] - Up to (F1, W1) [-] - Back to (F1, W3) to close loop 8. **Step 6: Find minimum allocation in cells with minus signs:** Cells with minus signs: (F2, W3) = 500 units, (F1, W1) = 300 units Minimum is $\theta = 300$ 9. **Step 7: Update allocations along the loop:** Add $\theta$ to cells with plus signs and subtract from cells with minus signs: - (F1, W3): 0 + 300 = 300 - (F2, W3): 500 - 300 = 200 - (F2, W1): 100 + 300 = 400 - (F1, W1): 300 - 300 = 0 10. **Step 8: New allocations matrix:** $$ \begin{array}{c|cccc} & W1 & W2 & W3 & W4 \\ \hline F1 & 0 & 500 & 300 & 0 \\ F2 & 400 & 0 & 200 & 0 \\ F3 & 0 & 0 & 200 & 800 \end{array} $$ 11. **Step 9: Calculate new total transportation cost:** - F1 to W2: $6 \times 500 = 3000$ - F1 to W3: $20 \times 300 = 6000$ - F2 to W1: $6 \times 400 = 2400$ - F2 to W3: $15 \times 200 = 3000$ - F3 to W3: $17 \times 200 = 3400$ - F3 to W4: $7 \times 800 = 5600$ Sum: $$Z = 3000 + 6000 + 2400 + 3000 + 3400 + 5600 = 23400$$ Cost reduced from 23700 to 23400. 12. **Step 10: Repeat MODI method to check if this new solution is optimal:** Set $u_1=0$. Allocate potentials: - (F1, W2): $0 + v_2 = 6 \Rightarrow v_2=6$ - (F1, W3): $0 + v_3=20 \Rightarrow v_3=20$ - (F2, W1): $u_2 + v_1=6$ - (F2, W3): $u_2 + 20=15 \Rightarrow u_2= -5$ - So, $u_2 + v_1=6 \Rightarrow -5 + v_1=6 \Rightarrow v_1=11$ - (F3, W3): $u_3 + 20=17 \Rightarrow u_3 = -3$ - (F3, W4): $u_3 + v_4=7 \Rightarrow -3 + v_4=7 \Rightarrow v_4=10$ Check opportunity costs for non-allocated: - (F1, W1): $12 - (0 + 11)=1$ - (F1, W4): $25 - (0 + 10)=15$ - (F2, W2): $11 - (-5 + 6)=10$ - (F2, W4): $12 - (-5 + 10)=7$ - (F3, W1): $9 - (-3 + 11)=1$ - (F3, W2): $15 - (-3 + 6)=12$ All non-allocated have $\\geq 0$, so solution is optimal. **Final answer:** Optimal allocations: $$ \begin{array}{c|cccc} & W1 & W2 & W3 & W4 \\ \hline F1 & 0 & 500 & 300 & 0 \\ F2 & 400 & 0 & 200 & 0 \\ F3 & 0 & 0 & 200 & 800 \end{array} $$ Minimum transportation cost: $$ \boxed{23400} $$