= Solution
At the current dual prices $(1,1)$, the new product has <reduced cost> $5-(1+2)=2>0$, so it can increase profit. Its transformed resource column is
$$
B^{-1}\begin{pmatrix}1\\2\end{pmatrix}
=\begin{pmatrix}3&-5\\-1&2\end{pmatrix}\begin{pmatrix}1\\2\end{pmatrix}
=\begin{pmatrix}-7\\3\end{pmatrix}.
$$
Increasing $x_4$ by $t$ changes the old <basic variables> to $x_1=9+7t$ and $x_3=3-3t$. Thus $x_3$ leaves at $t=1$, giving
$$
\boxed{(x_1,x_2,x_3,x_4)=(16,0,0,1),\qquad z_{\max}=53.}
$$
For a certificate, take dual prices $(1/3,7/3)$. They price the four products at $3,17/3,26/3,5$, respectively, each at least its profit. Their resource total is $33/3+18(7/3)=53$, equal to the achieved profit. <Weak duality> proves optimality, and the profit has increased by two.
Back to article page
