Basic primal and dual solution. Feasible? Why?

Question

Questions

---

Attempt

I managed to solve (c) but I have trouble understanding (d) any directions would be incredibly useful.

Answer 1

$$ \begin{array}{cc} \begin{array}{rr} \min\quad c^Tx & \\ \text{s.t.} \quad Ax&=b \\ x &\ge 0 \end{array} & \qquad \begin{array}{rr} \max\quad b^Ty & \\ \text{s.t.} \; A^Ty&\le c \\ y & \text{free} \end{array} \\ {\cal (P)} & \qquad {\cal (D)} \end{array} $$

The last four columns of $A$ is in the current basis.

$$A=\begin{pmatrix} 2&0&0&2&1&1\\ -1&2&1&-2&2&3\\ -1&2&2&0&1&-2\\ 1&-2&-1&1&0&1 \end{pmatrix},\; B=\begin{pmatrix} 0&2&1&1\\ 1&-2&2&3\\ 2&0&1&-2\\ -1&1&0&1 \end{pmatrix},\\ B^{-1}=\begin{pmatrix} 9/5 & -1/5 & -7/5 & -4 \\ 4/5 & -1/5 & -2/5 & -1 \\ -8/5 & 2/5 & 9/5 & 4 \\ 1 & 0 & -1 & -2 \end{pmatrix},\; b=\begin{pmatrix}3\\-1\\2\\0\end{pmatrix},\; c=\begin{pmatrix}0 \\ 4 \\ 10 \\ 5 \\ 5 \\ 0 \end{pmatrix} $$

The primal basic solution $x_B$ satisfies $Bx_B=b$, so

$$x_B=B^{-1}b= \begin{pmatrix} 9/5 & -1/5 & -7/5 & -4 \\ 4/5 & -1/5 & -2/5 & -1 \\ -8/5 & 2/5 & 9/5 & 4 \\ 1 & 0 & -1 & -2 \end{pmatrix} \begin{pmatrix}3\\-1\\2\\0\end{pmatrix} = \begin{pmatrix} 14/5 \\ 9/5 \\ -8/5 \\ 1 \end{pmatrix}. $$

The primal basic solution is $(0,0,14/5 , 9/5 , -8/5 , 1)^T$. By complementary slackness, the 3^rd-6^th dual constraints are equalities: $B^T y = c_B := (c_3,\dots,c_6)^T$, so $$y = (B^{-1})^T c_B =\begin{pmatrix} 9/5 & 4/5 & -8/5 & 1 \\ -1/5 & -1/5 & 2/5 & 0 \\ -7/5& -2/5& 9/5 & -1 \\ -4 & -1 & 4 & -2 \end{pmatrix} \begin{pmatrix} 10 \\ 5 \\ 5 \\ 0 \end{pmatrix} = \begin{pmatrix} 14 \\ -1 \\ -7 \\ -25 \end{pmatrix} $$ $$c^T x = \begin{pmatrix} 0 \\ 4 \\ 10 \\ 5 \\ 5 \\ 0 \end{pmatrix}^T \begin{pmatrix} 0 \\ 0 \\ 14/5 \\ 9/5 \\ -8/5 \\ 1 \end{pmatrix} = 29 \\ b^T y = \begin{pmatrix} 3\\-1\\2\\0 \end{pmatrix}^T \begin{pmatrix} 14 \\ -1 \\ -7 \\ -25 \end{pmatrix} = 29 $$

The corresponding dual solution is $y=(14, -1, -7, -25)^T$. The primal basic solution not feasible as $x_5 =-8/5 < 0$.