Given the following non-standard LP problem :
I'm asked to check if the solution $x=(3,-1,0,2)$ is optimal without using the Simplex Algorithm.
At first sight it seemed like a very difficult problem compared to the ones I'm used to. After reviewing everything we've done in the class I had some ideas.
First of all, we can use some duality theorems such as the strong complementary slackness one. However, this requires me to reach a solution for the dual problem. Even finding the dual (at least to my knowledge) seems like a mess. We'll have to get rid of the equality and the variables which take values in $\mathbb{R}$ and use two variables for each of them.
I tried getting rid of the extra $x_4$ variable using the equality and this way I got rid of the equality as well. Am I allowed to do this? It makes sense, since the equality has to stand for all solutions...
After removing $x_4$ and the equality I constructed a dual problem. However, the $x_1,x_2\in\mathbb{R}$ still makes me worry if I'm allowed to find the dual problem before transforming it to a standard form (with non-negativities).
I'm also aware of a theorem stating that if a primal slack variable is non-zero then the corresponding dual variable is zero. Also, if a prime variable is non-zero, the corresponding dual slack variable is zero. This could help me get the solutions of the dual problem with which I can test for strong complementary slackness. But still, given $x_1,x_2\in\mathbb{R}$ I'm not sure any of my ideas is correct.
Any tips on the solution?
Edit-my solution
After some comments I gave the solution a shot. Following the rules of converting a primal problem to a dual problem , we get:
$$\begin{align} \text{min} \quad &s=5y_1+8y_2+y_3 \\ \text{s.t.} \quad & y_1+3y_2=6 \\ & 2y_1+y_2+y_3=1 \\ &y_1-y_2+y_3\ge -1 \\ &y_1+y_3\ge -1 \end{align}$$
Now, since $x_1$ is non-zero, then slack variable $y_4=0$.
Similary, $x_2\ne0\implies y_5=0$.
$x_4\ne0\implies y_7=0$.
Now, looking for the slack variable solutions of the prime problem we get: $x_5=2$ , $x_6=0$, $x_7=0$
Which translates to : $y_1=0$
So, until now we have :
x$=\begin{bmatrix}3&-1&0&2&2&0&0\end{bmatrix}$
y$=\begin{bmatrix}0&y_2&y_3&0&0&y_6&0\end{bmatrix}$
Now, solving the dual problem with the above partially found solution we can deduce that :
y$=\begin{bmatrix}0&2&-1&0&0&2&0\end{bmatrix}$
Now for the final comparison, if the solution is optimal, the two objective functions should give the same value . $z_1=15$ and $z_2=15$ so the solution is optimal
You are allowed to substitute out $x_4$, as you did (though I don't think you have to in order to solve this problem).
You can and should formulate the dual. You do not need to convert to standard form first, if you have learned the rules for formulating duals of non-standard LPs. If you haven't, you can convert to standard form first but it will add a few steps for you.
Now, you can infer something about the optimal dual values (if your solution $x$ is indeed optimal) using complementary slackness. What is it? Can you use that to simplify the dual problem enough to get an easy dual solution? And do that dual solution and your given primal solution satisfy complementary slackness? If so, your primal solution is optimal.
There are a few nice worked examples of problems like this one here.