# How to show optimal value of linear program is unbounded?

The problem is given as $$\begin{equation*} \text{minimize} \hspace{.8em} -x_1-3x_2\\ \text{subject to} \hspace{.8em} x_1-2x_2 \le 4\\ \hspace{2 cm} -x_1+x_2 \le 3 \\ \hspace{2 cm} x_1,x_2\geq 0. \end{equation*}$$ Graphically it's clear that the solution is unbounded but how do i show this analytically? i have converted it into the form $$\begin{equation*} \text{minimize} \hspace{.8em} C^{\top}x\\ \text{subject to} \hspace{.8em} Ax=b\\ \hspace{2 cm} x_1,x_2 \ge 0 \end{equation*}$$ Where $$C^{\top}=[-1~-3~~ 0~ ~0~ ~0], b=[4~~3]^{\top}$$ and $$A=\begin{pmatrix}1&-2&1&0\\-1&1&0&1\end{pmatrix}$$ , Now i think i have to find a vector $$d$$ s.t cost is unbounded for $$x_{*}+\alpha d$$, so how do i choose $$d$$ and $$x_{*}$$ ? or there's any other way ?

• Try $d=(1,1)^T$ for the upper version and multiply it with a positive scalar Commented Mar 21, 2020 at 10:03

you can pick $$x_*=(4,0)^T$$ and pick $$d=(2,1)^T$$. Note that $$(2,1)$$ is orthogonal to $$(1,-2)$$ which is the normal direction of the first inequality.
$$\lim_{\alpha \to \infty}-(4+2\alpha)-3\alpha \to -\infty$$
$$(4+2\alpha)-2(\alpha)\le 4$$ $$-(4+2\alpha)+\alpha=-4-\alpha\le -4\le -3$$ $$4+2\alpha \ge 0, \alpha \ge 0$$
• so $d, x_{*}$ has to be picked inside the feasible region right ? Commented Mar 21, 2020 at 10:09
• visualizing $2$ dimensions should be easier =) so yup, the version without slack variable Commented Mar 21, 2020 at 10:57