Is the Linear Program below unfeasible, unlimited or does it have an optimal solution? ...

58 Views Asked by At

Is the Linear Program below unfeasible, unlimited or does it have an optimal solution? Properly justify your answer, making use of the dual program if it makes sense – if it doesn't, justify why

\begin{align} max_{x_i}-x_1 + 5x_2 + 2x_3 - 7x_4 - x_5\\ x_2 + x_3 - x_4 \geq 13\\ x_1 - x_2 + 2x_4 + 2x_5 \leq 4\\ x_2,x_4,x_5 \geq 0 x_3 \geq -2\end{align}

I don't think there is a single viable solution, but I don't know how to continue. This is what i was able to do.

Primal \begin{align} max_{x_i}-x_1 + 5x_2 + 2x_3 - 7x_4 - x_5\\ x_2 + x_3 - x_4 \geq 13\\ -x_1 + x_2 - 2x_4 - 2x_5 \geq -4\\ x_2,x_4,x_5 \geq 0 x_3 \geq -2 \end{align}

Dual \begin{align} min_{y_1,y_2}13y_1 - 4y_2 \\ 0y_1 + y_2 \leq -1\\ y_1 + y_2 \leq 5\\ y_1 +0y_2 \leq 2\\ y_1 +2y_2 \leq -7\\ 0y_1 +2y_2 \leq -1\end{align}

$A = \begin{pmatrix}0&1&1&1&0\\-1&1&0&2&2\\ \end{pmatrix}$

$b = (13,-4)^T$

$x = (x_1,x_2,x_3,x_4,x_5)^T$

$y = (y_1,y_2)^T$

Thanks for the help.