Reduced Cost and Optimality Worked Example
Reduced Cost and Optimality Worked Example
Problem
\[\min -3x_1-2x_2\]subject to
\[x_1+x_2+s_1=4,\] \[2x_1+x_2+s_2=5,\] \[x_1,x_2,s_1,s_2\ge0.\]Let
\[A=\begin{bmatrix} 1&1&1&0\\ 2&1&0&1 \end{bmatrix}, \quad b=\begin{bmatrix}4\\5\end{bmatrix}, \quad c=\begin{bmatrix}-3\\-2\\0\\0\end{bmatrix}.\]Basis $B={s_1,s_2}$
\[B=I, \quad c_B=(0,0)^T.\] \[\bar c^T=c^T-c_B^TB^{-1}A=(-3,-2,0,0).\]Since some reduced costs are negative, this basis is not optimal.
Basis $B={s_1,x_1}$
\[B=\begin{bmatrix}1&1\\0&2\end{bmatrix}, \quad x_B=\begin{bmatrix}3/2\\5/2\end{bmatrix}.\] \[\bar c=(0,-1/2,0,3/2).\]Still not optimal, because $\bar c_2=-1/2<0$.
Basis $B={x_2,x_1}$
\[x_2=3, \qquad x_1=1.\]Reduced costs:
\[\bar c=(0,0,1,1).\]All reduced costs are nonnegative, so the basis is optimal.
\[z^*=-3(1)-2(3)=-9.\]Exam checkpoint
For simplex questions in minimization form, negative reduced costs indicate possible improvement. Use $u=B^{-1}A_j$, apply the ratio test only to positive components of $u$, then update the basis.