# Find all basic feasible solutions & find optimal solution for the given linear programming problem

Consider the problem: $$\text{min}\,x_{1}+2x_{2}+x_{3} \\ \text{subject to}\, \\ -x_{1}+x_{2}+x_{3} = 3 \\ 2x_{1} +x_{2} - x_{3} = 1, \\ x_{1},x_{2},x_{3} \geq 0$$

I need to find all basic feasible solutions of this problem.

Since there are two equations and three variables, we need to set $3-2 = 1$ variable equal to $0$ in order to get a basic solution.

• First, set $x_{1}:=0$, then we have $$x_{2} + x_{3} = 3 \\ x_{2} - x_{3} = 1$$ which has $x_{2} = 2$ and $x_{3} = 1$ as a solution, so my basic solution in this case is $\begin{pmatrix} 0 \\ 2 \\ 1\end{pmatrix}$
• Next, set $x_{2}:=0$, then we have $$-x_{1} + x_{3} = 3 \\ 2x_{1} - x_{3} = 1$$ which has $x_{1}=4$ and $x_{3}=7$ as a solution, so my basic solution in this case is $\begin{pmatrix}4 \\ 0 \\ 7 \end{pmatrix}$
• Finally, set $x_{3}:=0$, then we have $$-x_{1} + x_{2} = 3 \\ 2x_{1} + x_{2} = 1$$ which has $\displaystyle x_{1} = -\frac{2}{3}$ and $\displaystyle x_{2} = \frac{7}{3}$ as a solution, so my basic solution in this case is $\begin{pmatrix}-\frac{2}{3} \\ \frac{7}{3} \\ 0 \end{pmatrix}$

However, since $\displaystyle -\frac{2}{3} < 0$, $\begin{pmatrix}-\frac{2}{3} \\ \frac{7}{3} \\ 0 \end{pmatrix}$ while basic, is not feasible.

Therefore, I have only two basic feasible solutions here: $\begin{pmatrix} 0 \\ 2 \\ 1\end{pmatrix}$ and $\begin{pmatrix} 4 \\ 0 \\ 7 \end{pmatrix}$

I've never done one of these problems before, so I don't really know if what I did is correct...could somebody please tell me if it is, and if not, what would be the correct way to go about it?

After this, I need to find the optimal solution. Would this entail just substituting these two vectors into the objective function and seeing which one gives me the smallest output, or is there something more complicated that I need to do?

Thank you for your time and patience!

• when you consider $x_1$ free, give it the minimum allowed value (that is 0) and solve the system for $x_2$ and $x_3$. You will get $x_2=2$, $x_3=1$, that is the basic feasible solution $x^{\top}=(0,2,1)$. – Marcello Sammarra Oct 15 '17 at 20:39
• @MarcelloSammarra thanks! I figured that out myself and just re-posted my question to reflect my updated understanding of the problem. – ALannister Oct 15 '17 at 20:49
• @MarcelloSammarra actually, I think I figured out the whole thing - when I get a chance, I'll post an answer. – ALannister Oct 16 '17 at 16:53
• $x^T =(2,1,4)$ is also a solution to the problem. It's objective value is even lower than the one of $(4,0,7)^T$. – YukiJ Apr 19 '18 at 9:54