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!
Given the model,
$$\text{min } z=x_1+2x_2+x_3$$
Subject to,
$$-x_1+x_2+x_3=3$$ $$2x_1+x_2-x_3=1$$ $$x_1,x_2, x_3\ge0$$
Let’s convert it to standard form:
$$\text{min }z-x_1-2x_2-x_3-Ma_1-Ma_2=0$$
Subject to,
$$-x_1+x_2+x_3+a_1=3$$ $$2x_1+x_2-x_3+a_2=1$$ $$x_1,x_2, x_3, a_1, a_2\ge0$$
Next, let’s put this into a tableau:
We’ll need to solve for our initial basic variables by getting rid of the big Ms for the $a_1$ and $a_2$ variables, and then solve this model via the simplex method, then we’ll get following:
The two solutions we get from the simplex method are the only ones that are basic feasible solutions due to the fact that we are limited to two basic variables for the constraints (as you can only have as many basic variables as you have constraints). Thus, (0, 2, 1) and (4, 0, 7) are the only two basic solutions for the model that exist on extreme points, with (0, 2, 1) as the optimal solution with $z=5$.
It was mentioned in a comment above that the point $(2, 1, 4)$ is a solution of the model, however it is not an extreme point of the model. An interesting fact to keep in mind is this:
The reason for this is further explained here.
The collection of points we have are $(0,0,0)$, $(0,1,0)$, $(0,2,1)$, and $(4,0,7)$
The collection of directions we have are: $$d_1 = (0,0,1) \text{$\qquad$} d_2 = (1,0,0)$$ $$d_3 = (1,\frac{1}{2},0) \text{$\qquad$} d_4 = (0,\frac{1}{2},0)$$ $$d_5 = (1,4,\frac{2}{3}) \text{$\qquad$} d_6 = (0,4,\frac{2}{3})$$ $$d_7 = (2,1,\frac{3}{7}) \text{$\qquad$} d_8 = (4,0,\frac{7}{2})$$
Then, we can take any combination of extreme points and directions and do the following:
$$\begin{bmatrix}4 & 0 & 0\\0 & 2 & 1\\7 & 2 & 1\end{bmatrix} \begin{bmatrix}\lambda_1 \\ \lambda_2 \\ \lambda_3\end{bmatrix} + \begin{bmatrix}1 & 0 & 0\\0 & 0 & \frac{1}{2}\\0 & 1 & 0\end{bmatrix} \begin{bmatrix}l_3 \\ l_2 \\ l_3 \end{bmatrix} = \begin{bmatrix}2 \\ 1 \\ 4\end{bmatrix} $$
and if we let $\lambda_1 = \lambda_2 = l_3 = 0$, $\lambda_3 = 1$, $l_2 = 4$, and $l_1 = 2$, we’ll get the point $(2, 1, 4)$.
Of course, this isn’t the only way to find interior points of a model, and thus if guessing points or the above isn’t your fancy, there’s the option of interior-point methods