# optimization question

Minimize $x_1+6x_2-x_3$ subject to $7x_1+x_2-x_3=6$, $3x_1+x_2+2x_3\leq 6$, $x_1,x_2\in\mathbb{R_+}$.

I first tried to represent $x_3$ in terms of $x_1$ and $x_2$, so $x_3=7x_1+x_2-6$, substituting this into the cost function: $\min\{x_1+6x_2-7x_1-x_2+6\}\iff \min\{-6x_1+5x_2+6\}$ subject to $3x_1+x_2+2(7x_1+x_2-6)\leq 6\iff 17x_1+3x_2\leq 18$; I'm kind of stuck here. Any pointers?

-
What is the domain of your variables? $\mathbb{Z}$ or $\mathbb{R}$ or something more exotic? –  m_l Apr 19 '12 at 15:11
sorry -- it's $\mathbb{R}$. –  Emir Apr 19 '12 at 16:28

Disclaimer: Optimization is certainly not my field of expertise. That being said, this particular example can be solved by some multivariate calculus, I think.

I assume that linear programming will solve this in the blink of an eye, but I know next to nothing about it, so here is a very basic approach:

The graph of the function $$(x_1,x_2) \mapsto -6x_1+5x_2+6$$ you are trying to minimize is a plane with non-vanishing slope (i.e. the gradient has no zeroes). So there can't be a minimum in the domain defined by $x_1, x_2 > 0$, $17x_1+3x_2 < 18$. Thus, the minimum (which exists, because $x_1, x_2 \ge 0$, $17x_1+3x_2 \le 18$ defines a compact subset of $\mathbb{R}^2$) must lie on the boundary of said domain. You can easily parametrize the boundary (it is the union of three straight lines), plug the parametrization into the original function and solve the resulting one dimensional problem.

Note that the answer to your simplified problem is obvious (make $x_1$ as big as possible, $x_2$ as small as possible). I did all this hokum to provide a more or less formal proof that this is indeed the correct answer.

-