Attempt:
Let $x_5,x_6$ be slack variables so our system now looks like
\begin{align*}
\max \; \; \; & -x_1 – x_2 + 2 x_3 + x_4 \\
\text{subject to} \; \; \; & 2x_1 + x_2 + x_3 + x_4 – x_5 = 6 \\
& x_1 + 2 x_2 – 2x_3 + x_4 + x_6 = 4 \\
& x_i \geq 0, \; \; \; \; i=1,2,3,4,5,6
\end{align*}
We can write the constraints as $A {\bf x } = {\bf b}$ where
$$A = \begin{pmatrix}
2 & 1 & 1 & 1 & -1 & 0 \\
1 & 2 & -2 & 1 & 0 & 1 \\
\end{pmatrix} $$
Now, the requirement space is the set of all positive vectors ${\bf x} = (x_1,x_2,x_3,x_4,x_5,x_6)$ that satisfy the linear combination $\sum_{i=1}^6 {\bf a}_i x_i$ where ${\bf a}_i$ is the ith column of matrix $A$. In the figure below, we plot the vectors.
We see that the requirement space is the entire plane. As for part b), notice that as long as the vector ${\bf b}$ belongs to the cone generated by the vectors ${ \bf a }_i$, then the system is feasible. In our case, ${\bf b} = (6,4)^T$, and since the requirement space is the entire plane, then trivially we observe that the system must be feasible.
Is this correct so far? Im just trying to understand this concept. Im stuck with part c), how can I find an optimal solution?
Best Answer
The requirement space is the set of all nonnegative vectors ${\bf x} = (x_1,x_2,x_3,x_4,x_5,x_6)$ that satisfy the linear combination $\sum_{i=1}^6 {\bf a}_i x_i$ where ${\bf a}_i$ is the ith column of matrix $A$. Graphically, you can depict a combination of vectors as a cone. For example, the cone generated by $a_1$ and $a_2$ is:
Since the cone contains $b$, this combination of vectors has a feasible $x$ ($x_1=8/3$, $x_2=2/3$). The other combinations of vectors that contain $b$ are $(a_1,a_4)$, $(a_1,a_5)$, $(a_1,a_6)$, $(a_2,a_3)$, $(a_3,a_4)$ and $(a_3,a_6)$. If you find the $x$ for each of these combinations and compute the objective value for each of those $x$, the one with the largest objective value is optimal.
However, the question is flawed. There is no optimal solution, since $x=[0; 0; c; 0]$ is feasible to the original problem for any $c\geq 6$. The objective value is $2c$, which can grow arbitrarily large.