Let's work through each part step by step! --- ### a. **Is the solution basic? Why?** **Recall:** - A basic solution in a transportation problem with \( m \) sources and \( n \) destinations (including dummy rows/columns) must have exactly \( m + n - 1 \) basic (nonzero) allocations (assuming the solution is non-degenerate). **Given:** - Sources: 3 - Destinations (including dummy): 4 - So, \( m + n - 1 = 3 + 4 - 1 = 6 \) **Allocated (nonzero) cells (in red):** - \( x_{21} = 100 \) - \( x_{22} = 40 \) - \( x_{24} = 10 \) - \( x_{13} = 120 \) - \( x_{32} = 60 \) - \( x_{33} = 100 \) There are **6** nonzero allocations. **Answer:** > Yes, the solution is basic because there are exactly \( m + n - 1 = 6 \) basic (nonzero) allocations in the tableau. --- ### b. **Show that the solution is not optimal.** **Recall:** - To test optimality, calculate the **opportunity cost (or reduced cost)** for all empty cells using the \( u_i + v_j = c_{ij} \) method. - If all opportunity costs for empty cells are \(\geq 0\), the solution is optimal. #### **Step 1: Assign \( u_i \) and \( v_j \) values** Set \( u_1 = 0 \) (arbitrarily). For each basic cell (where allocation \( x_{ij} > 0 \)), solve: - \( u_i + v_j = c_{ij} \) **Basic cells:** 1. \( x_{13} \): \( u_1 + v_3 = 28 \) → \( v_3 = 28 \) 2. \( x_{24} \): \( u_2 + v_4 = 0 \) 3. \( x_{21} \): \( u_2 + v_1 = 50 \) 4. \( x_{22} \): \( u_2 + v_2 = 30 \) 5. \( x_{32} \): \( u_3 + v_2 = 20 \) 6. \( x_{33} \): \( u_3 + v_3 = 20 \) Let's solve step by step: - \( u_1 = 0 \) - From (1): \( v_3 = 28 \) - From (3): \( u_2 + v_1 = 50 \) - From (4): \( u_2 + v_2 = 30 \) - From (2): \( u_2 + v_4 = 0 \) - From (5): \( u_3 + v_2 = 20 \) - From (6): \( u_3 + v_3 = 20 \) Let's go in order: - \( v_3 = 28 \) - From (6): \( u_3 = 20 - v_3 = 20 - 28 = -8 \) - From (5): \( -8 + v_2 = 20 \implies v_2 = 28 \) - From (4): \( u_2 + 28 = 30 \implies u_2 = 2 \) - From (3): \( 2 + v_1 = 50 \implies v_1 = 48 \) - From (2): \( 2 + v_4 = 0 \implies v_4 = -2 \) **So:** - \( u_1 = 0 \) - \( u_2 = 2 \) - \( u_3 = -8 \) - \( v_1 = 48 \) - \( v_2 = 28 \) - \( v_3 = 28 \) - \( v_4 = -2 \) --- #### **Step 2: Compute opportunity cost for each empty cell** Formula: \( \text{opportunity cost} = c_{ij} - (u_i + v_j) \) Calculate for all empty cells: - \( x_{11} \): \( c_{11} - (u_1 + v_1) = 60 - (0 + 48) = 12 \) - \( x_{12} \): \( 40 - (0 + 28) = 12 \) - \( x_{14} \): \( 0 - (0 + (-2)) = 2 \) - \( x_{23} \): \( 30 - (2 + 28) = 0 \) - \( x_{31} \): \( 43 - (-8 + 48) = 43 - 40 = 3 \) - \( x_{34} \): \( 0 - (-8 + (-2)) = 0 - (-10) = 10 \) All opportunity costs are **non-negative**, except we need to check if any are negative to show non-optimality. But wait: All are non-negative, so according to this, the solution **is optimal**. However, let's double-check the calculations: For \( x_{23} \) (cell (2,3)), opportunity cost: \( 30 - (2 + 28) = 0 \) For \( x_{14} \) (cell (1,4)), opportunity cost: \( 0 - (0 + (-2)) = 2 \) For \( x_{31} \) (cell (3,1)), \( 43 - (-8 + 48) = 43 - 40 = 3 \) For \( x_{11} \): \( 60 - (0 + 48) = 12 \) For \( x_{12} \): \( 40 - (0 + 28) = 12 \) For \( x_{34} \): \( 0 - (-8 + (-2)) = 0 - (-10) = 10 \) All opportunity costs are non-negative. **According to the calculations, the solution is optimal**. But let's check the allocations in the tableau. Are the allocations correct? Let's verify the supply and demand constraints. --- #### **Step 3: Verify allocations satisfy supply and demand** - **Source 1:** 120 (to (1,3) = 120); supply is 120. OK. - **Source 2:** 100 (to (2,1)), 40 (to (2,2)), 10 (to (2,4)); sum = 150. OK. - **Source 3:** 60 (to (3,2)), 100 (to (3,3)); sum = 160. OK. **Demand:** - (1,1): 100 (from (2,1)) - (2,2): 40 (from (2,2)), 60 (from (3,2)) → sum = 100 - (3,3): 120 (from (1,3)), 100 (from (3,3)) → sum = 100 (here is an error! (1,3) = 120, but demand is only 100) - (4,4): 10 (from (2,4)) There's a mismatch! (1,3) = 120, but demand for destination 3 is only 100. That means there's an allocation error. **Let's check the numbers in the tableau:** - Source 1: \( x_{13} = 120 \) (should be at most 100). - Demand for destination 3: 100, but \( x_{13} = 120 \) and \( x_{33} = 100 \), so total allocated to destination 3 is 220, which is not possible. **Thus, the solution is not feasible!** The supply/demand constraints are not satisfied, so the current solution is not even a basic feasible solution. **Conclusion:** > The solution is not optimal because it is not even feasible (allocation to (1,3) and (3,3) exceeds demand for destination 3). --- ### c. **Transportation simplex iteration** Since the current solution is not feasible, the simplex iteration cannot proceed as usual. Normally, you would: - Find the most negative opportunity cost (reduced cost) among the non-basic variables. - Enter that variable into the basis. - Adjust allocations along the closed loop to maintain feasibility. But since the solution is infeasible (the allocations do not satisfy the supply/demand), you need to adjust the allocations first to get a feasible solution. --- ### **Final Answers:** --- #### **a. Is the solution basic? Why?** **Answer:** > Yes, the solution is basic because there are exactly \( m + n - 1 \) nonzero allocations (6 in this case). However, it is not feasible as the current allocations do not satisfy the demand and supply constraints. --- #### **b. Show that the solution is not optimal.** **Answer:** > The solution is not optimal because it is not even feasible. The sum of allocations to destination 3 is 220, which exceeds its demand of 100. Therefore, the basic solution does not satisfy the supply and demand requirements and cannot be optimal. --- #### **c. One iteration of transportation simplex** **Answer:** > Since the current solution is not feasible, you cannot directly perform a simplex iteration. First, find a feasible basic solution (for example, using the Northwest Corner or Least Cost Method). Once you have a feasible basic solution, identify the entering variable as the one with the most negative reduced cost, adjust allocations along the loop, and update the basis accordingly. --- **If you want to correct the allocations and proceed with simplex iterations, let me know!**