Given the following set:
$$ -x_1 + x_2 = 4$$
$$ x_1 – 2x_2 + x_3 <= 6 $$
$$ x_3 >= 1 $$
$$ x_1,x_2,x_3 >= 0 $$
Without drawing the feasible region can I know if it is bounded or unbounded?
Is it possible to know if the feasible region is unbounded without drawing it
linear programming
Related Solutions
You said that in two dimensions you would simply draw the feasible set and then visually check where the vertices are. We can do the same for higher dimensions without drawing anything. You will have observed that the vertices of the feasible set are where two constraints intersect. And this observation we can use to find the vertices of higher dimensional polyhedra. We have to intersect all combinations of(in this case) 3 constraints with each other and check if the point of intersection is feasible. If it is feasible, then it is a vertex.
For example, if we intersect the two hyperplanes $x_1-x_2+x_3 =1$ with $x_1-2x_2=4$ and $x_1=0$ we obtain the following system of equations:
$$ \left[\begin{array}{rrr|r} 1 & 0 & 0 & 0 \\ 1 & -1 & 1 & 1 \\ 1 & -2 & 0 & 4 \\ \end{array} \right] $$ Solving it yields the point (0,-2,-1). However, this point is not feasible for $x_2\geq 0$, so we can discard it.
Next, we intersect $x_1-x_2+x_3 =1$ with $x_1-2x_2=4$ and $x_2=0$ and obtain (4,0,-3) as a solution. Since this point violates $x_3\geq 0$, we can also discard it.
Then we intersect $x_1-x_2+x_3 =1$ with $x_1-2x_2=4$ and $x_3=0$ and find (-2,-3,0), which violates $x_1 \geq 0$. So far, we haven't been lucky.
Next, we intersect $x_1-x_2+x_3 =1$ with $x_1=0$ and $x_2=0$ and obtain (0,0,1) as a candidate for a vertex. It is feasible for all the nonnegativity constraints but we also have to check whether it is feasible for $x_1-2x_2\leq4$ as well. Plugging it in yields $0-0 = 0 \leq 4$ so the constraint holds. We have found our first vertex!
Now, we intersect $x_1-x_2+x_3 =1$ with $x_1=0$ and $x_3=0$ and obtain (0,-1,0), which again violates a nonnegativity constraint ($x_2 \geq 0$).
Intersecting $x_1-x_2+x_3 =1$ with $x_2=0$ and $x_3=0$ results in (1,0,0) which is cleary nonnegative. Moreover, $1-2\cdot 0 = 1 \leq 4$ holds as well. Hence, we have found a second vertex.
We now intersect the constraint $x_1-2x_2=4$ with $x_1=0$ and $x_2=0$ and find that there is no solution.
We then intersect $x_1-2x_2=4$ with $x_1=0$ and $x_3=0$ and obtain (0,-2,0), which is infeasible for $x_2 \geq 0$.
As the next combination we intersect $x_1-2x_2=4$ with $x_2=0$ and $x_3=0$ and obtain (4,0,0), which is nonnegative but violates $4-0+0 = 4 \leq 1$.
Lastly, we intersect $x_1=0$ with $x_2=0$ and $x_3=0$ and, trivially, obtain the origin, which also satisfies the other two constraints. Thus, (0,0,0) also is a vertex.
The vertices we have found are (0,0,0),(0,0,1),(1,0,0).
In standard format, we get the system: \begin{equation*} \begin{alignedat}{2} -x_1 & {}+{} & x_2&{}+{}&x_3& &&= 2\\ -x_1&{}+{}&2x_2& &&{}+{}&x_4\ &=6 \end{alignedat} \end{equation*} with all variables positive. The matrix of the system is: $$A=\begin{pmatrix}-1&1&1&0\\ -1&2&0&1\end{pmatrix}.$$ Any extreme direction $d$ can be obtained as: $$d=\begin{pmatrix}-B^{-1}a_j\\e_j\end{pmatrix},$$ where $B$ is a $2\times 2$ invertible submatrix of $A$, $a_j$ is the $j$th column of $A$, not in $B$, such that $B^{-1}a_j\leq0$ and $e_j$ is the canonical vector with a one in the position of the column $a_j$.
For example, let $B=\begin{pmatrix}1&0\\0&1\end{pmatrix}$, invertible submatrix of $A$. We have that $B^{-1}a_1=\begin{pmatrix}-1\\-1\end{pmatrix}\leq0$. The canonical vector $e_1$ has a one in the position of $a_1$, i. e., $e_1=\begin{pmatrix}1\\0\end{pmatrix}$. Therefore, we get the direction $$d=\begin{pmatrix}1\\0\\1\\1\\\end{pmatrix},\ \text{writing }-B^{-1}a_1\text{ in the position of }B\text{ and }e_1\text{ in the left entries.}$$ In our original system, by erasing the variables $x_3$ and $x_4$, we get the extreme direction $\begin{pmatrix}1\\0\end{pmatrix}$.
Best Answer
A polyhedron is unbounded if there exists a point $x$ and a direction $d$ such that $x + \alpha d$ is in the polyhedron for all $\alpha \geq 0$. Denote the polyhedron as $Ax \leq b$, then $x$ and $d$ need to satisfy $A(x+\alpha d) \leq b$ for all $\alpha \geq 0$. That is equivalent to finding $x$ and $d$ such that $Ax \leq b$ and $Ad \leq 0$.