1. **Stating the problem:** We want to solve the linear programming problem: Maximize $$Z = 4x_1 + 3x_2 + 2x_3$$ subject to constraints: $$4x_1 + 3x_2 + 3x_3 \leq 30$$ $$3x_1 + 4x_2 - x_3 \geq 20$$ $$3x_2 + x_3 = 10$$ with $$x_1, x_2, x_3 \geq 0$$ 2. **Convert inequalities to equalities with slack/surplus variables:** Let $$s_1 \geq 0$$ be slack for first constraint: $$4x_1 + 3x_2 + 3x_3 + s_1 = 30$$ For second constraint, rewrite $$\geq$$ as: $$3x_1 + 4x_2 - x_3 - s_2 = 20$$ with surplus variable $$s_2 \geq 0$$ Third constraint is equality: $$3x_2 + x_3 = 10$$ 3. **Set up initial tableau for dual simplex method:** We want a basic feasible solution with all basic variables $$\geq 0$$ but possibly infeasible for primal. Choose basis variables: $$s_1, s_2, x_3$$ From constraints: $$s_1 = 30 - 4x_1 - 3x_2 - 3x_3$$ $$s_2 = 3x_1 + 4x_2 - x_3 - 20$$ $$x_3 = 10 - 3x_2$$ Substitute $$x_3$$ into $$s_1, s_2$$: $$s_1 = 30 - 4x_1 - 3x_2 - 3(10 - 3x_2) = 30 - 4x_1 - 3x_2 - 30 + 9x_2 = -4x_1 + 6x_2$$ $$s_2 = 3x_1 + 4x_2 - (10 - 3x_2) - 20 = 3x_1 + 4x_2 - 10 + 3x_2 - 20 = 3x_1 + 7x_2 - 30$$ 4. **Check feasibility of basic variables:** At $$x_1 = 0, x_2 = 0$$: $$s_1 = 0$$ $$s_2 = -30 < 0$$ So $$s_2$$ is negative, infeasible for primal, suitable for dual simplex. 5. **Dual simplex pivot:** Choose leaving variable with most negative RHS: $$s_2$$ Look at coefficients in $$s_2$$ row for non-basic variables $$x_1, x_2$$: $$3x_1 + 7x_2$$ Calculate ratios of objective coefficients to pivot column coefficients: Objective coefficients for $$x_1, x_2$$ are 4 and 3 respectively. Ratios: For $$x_1$$: $$\frac{4}{3} = 1.333$$ For $$x_2$$: $$\frac{3}{7} \approx 0.429$$ Choose variable with smallest ratio: $$x_2$$ enters basis. 6. **Pivot on $$x_2$$ in $$s_2$$ row:** Express $$x_2$$ from $$s_2$$ row: $$7x_2 = 30 - 3x_1 + s_2$$ $$x_2 = \frac{30 - 3x_1 + s_2}{7}$$ Substitute into other equations and objective function, update tableau. 7. **Update $$s_1$$ and $$x_3$$:** $$s_1 = -4x_1 + 6x_2 = -4x_1 + 6 \times \frac{30 - 3x_1 + s_2}{7} = -4x_1 + \frac{180 - 18x_1 + 6s_2}{7} = \frac{-28x_1 + 180 - 18x_1 + 6s_2}{7} = \frac{180 - 46x_1 + 6s_2}{7}$$ $$x_3 = 10 - 3x_2 = 10 - 3 \times \frac{30 - 3x_1 + s_2}{7} = 10 - \frac{90 - 9x_1 + 3s_2}{7} = \frac{70 - 90 + 9x_1 - 3s_2}{7} = \frac{-20 + 9x_1 - 3s_2}{7}$$ 8. **Check feasibility again:** At $$x_1 = 0, s_2 = 0$$: $$s_1 = \frac{180}{7} > 0$$ $$x_3 = \frac{-20}{7} < 0$$ So $$x_3$$ is negative, infeasible. 9. **Next pivot:** Leaving variable: $$x_3$$ Look at coefficients of non-basic variables in $$x_3$$ row: $$x_1$$ coefficient: $$\frac{9}{7} > 0$$ $$s_2$$ coefficient: $$-\frac{3}{7} < 0$$ Only $$x_1$$ can enter basis. 10. **Pivot on $$x_1$$ in $$x_3$$ row:** Express $$x_1$$: $$9x_1 = 20 + 3s_2 + 7x_3$$ $$x_1 = \frac{20 + 3s_2 + 7x_3}{9}$$ Substitute into $$s_1$$ and $$s_2$$ and objective function. 11. **Update $$s_1$$:** $$s_1 = \frac{180 - 46x_1 + 6s_2}{7} = \frac{180 - 46 \times \frac{20 + 3s_2 + 7x_3}{9} + 6s_2}{7}$$ Simplify numerator: $$180 - \frac{920 + 138s_2 + 322x_3}{9} + 6s_2 = \frac{1620 - 920 - 138s_2 - 322x_3 + 54s_2}{9} = \frac{700 - 84s_2 - 322x_3}{9}$$ So: $$s_1 = \frac{700 - 84s_2 - 322x_3}{63}$$ 12. **Check feasibility at $$s_2 = 0, x_3 = 0$$:** $$s_1 = \frac{700}{63} > 0$$ $$x_1 = \frac{20}{9} > 0$$ $$x_3 = 0$$ All basic variables $$\geq 0$$, feasible. 13. **Calculate objective value:** $$Z = 4x_1 + 3x_2 + 2x_3$$ Substitute $$x_1 = \frac{20}{9}, x_2 = \frac{30 - 3x_1}{7} = \frac{30 - 3 \times \frac{20}{9}}{7} = \frac{30 - \frac{60}{9}}{7} = \frac{30 - \frac{20}{3}}{7} = \frac{\frac{90}{3} - \frac{20}{3}}{7} = \frac{70/3}{7} = \frac{10}{3}$$ $$x_3 = 0$$ So: $$Z = 4 \times \frac{20}{9} + 3 \times \frac{10}{3} + 0 = \frac{80}{9} + 10 = \frac{80}{9} + \frac{90}{9} = \frac{170}{9} \approx 18.89$$ --- **Answer:** The optimal solution using dual simplex is: $$x_1 = \frac{20}{9}, x_2 = \frac{10}{3}, x_3 = 0$$ with maximum $$Z = \frac{170}{9} \approx 18.89$$. --- 14. **For question (3):** Given $$x_3$$ is non-basic (set to zero), find bounds on $$c_3$$ so that basis does not change. 15. **Reduced cost for $$x_3$$:** In optimal tableau, reduced cost $$\bar{c}_3 = c_3 - z_3$$ must satisfy $$\bar{c}_3 \leq 0$$ for maximization to keep $$x_3$$ non-basic. 16. **Calculate $$z_3$$:** From final tableau, objective coefficients for basic variables are: $$c_B = [4, 3, 0]$$ for $$x_1, x_2, s_1$$ (assuming slack variables zero cost) Calculate $$z_3 = c_B \cdot y_3$$ where $$y_3$$ is column of $$x_3$$ in final tableau. 17. **From step 11, $$x_3$$ column coefficients in basis:** $$x_3$$ appears in $$s_1$$ row with coefficient $$-\frac{322}{63}$$, in $$x_1$$ and $$x_2$$ rows zero. So: $$z_3 = 0 \times (-\frac{322}{63}) = 0$$ 18. **Therefore, reduced cost:** $$\bar{c}_3 = c_3 - 0 = c_3$$ To keep $$x_3$$ non-basic, $$\bar{c}_3 \leq 0$$ **Answer:** $$c_3 \leq 0$$ to keep $$x_3$$ non-basic and basis unchanged.