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!
$\endgroup$ 4 Reset to default
