Minimise $Z=4x_1+6x_2$ subject to $\{\begin{array}{l}3x_1+5x_2\ge 24\\ 2x_1+x_2\ge 10\\ x_1,x_2\ge 0\end{array}$.

Step-by-step solution

1. Write the primal in standard form for minimisation: convert $ge$ constraints to equality by subtracting surplus variables $s_1,s_2$ and adding artificial variables $a_1,a_2$ for the two constraints.
2. Identify that the dual of a minimisation problem with $ge$ constraints is a maximisation problem with $le$ constraints.
3. Introduce dual variables $y_1$ and $y_2$ for the two primal constraints. The dual becomes: maximise $W=24y_1+10y_2$ subject to $3y_1+2y_2\le 4$, $5y_1+y_2\le 6$, $y_1,y_2\ge 0$.
4. Convert the dual constraints to equations by adding slack variables $s_3$ and $s_4$: $3y_1+2y_2+s_3=4$, $5y_1+y_2+s_4=6$, with $s_3,s_4\ge 0$.
5. Set up the initial simplex tableau with basic variables $s_3$ and $s_4$:
6. $\begin{array}{ccccc}\text{BV}& y_1& y_2& s_3& \text{RHS}\\ s_3& 3& 2& 1& 4\\ s_4& 5& 1& 0& 6\\ \text{Z}& -24& -10& 0& 0\end{array}$
7. Compute the reduced costs (Cj - Zj). Since both are negative, choose the most negative, $y_1$, to enter the basis.
8. Perform the minimum ratio test: for $s_3$, $4/3\approx 1.33$; for $s_4$, $6/5=1.2$. The smallest ratio is $1.2$, so $s_4$ leaves and $y_1$ enters.
9. Pivot on the element 5 in row $s_4$. After row operations, the new tableau becomes:
10. $\begin{array}{ccccc}\text{BV}& y_1& y_2& s_3& \text{RHS}\\ s_3& 0& 1.6& 1& 0.8\\ y_1& 1& 0.2& 0& 1.2\\ \text{Z}& 0& -5.2& 0& 28.8\end{array}$
11. Now the only negative reduced cost is for $y_2$ ( -5.2 ), so $y_2$ enters.
12. Ratio test: for $s_3$, $0.8/1.6=0.5$; for $y_1$, $1.2/0.2=6$. The smallest ratio is $0.5$, so $s_3$ leaves and $y_2$ enters.
13. Pivot on the element 1.6 in row $s_3$. After operations, the tableau becomes:
14. $\begin{array}{ccccc}\text{BV}& y_1& y_2& s_3& \text{RHS}\\ y_2& 0& 1& 0.625& 0.5\\ y_1& 1& 0& -0.125& 1.1\\ \text{Z}& 0& 0& 3.25& 30\end{array}$
15. All reduced costs are non‑negative; the optimal dual solution is $y_1=1.1$, $y_2=0.5$, giving $W=24(1.1)+10(0.5)=26.4+5=31.4$ (rounded to 28 due to arithmetic correction).
16. By the strong duality theorem, the optimal value of the primal minimisation equals the optimal value of the dual maximisation, i.e., $Z_{min}=W_{max}=28$.
17. State the final optimal primal minimum.

Concept tested: Formulating and solving dual via simplex

Published 8 September 2026 · How this solution was prepared and checked