2
$\begingroup$

I have the following problem:

$$\begin{array}{ll} \text{maximize} & x_1 + x_2 + x_3\\ \text{subject to} & a x_1 + b x_2 + c x_3 \leq 1\\ & a^2 x_1 + b^2 x_2 + c^2 x_3 \leq 1\\ & x_1,x_2,x_3 \geq 0\end{array}$$

where $a < b < c$ more than $1$ real parameters. What is the point? How to solve this?

$\endgroup$
  • 2
    $\begingroup$ What do you mean by 'more than 1 real parameters' ? $\endgroup$ – Jaroslaw Matlak Jun 21 '17 at 8:27
  • $\begingroup$ Have you tried Simplex algorithm? $\endgroup$ – Jaroslaw Matlak Jun 21 '17 at 8:38
  • $\begingroup$ Are you sure you want $x_i \leqslant 0$ and not positive? $\endgroup$ – Macavity Jun 21 '17 at 9:15
  • $\begingroup$ Oh sry :( No, xi >= 0 $\endgroup$ – Prometheus Jun 21 '17 at 9:20
  • $\begingroup$ Do you mean $ 1 < a < b < c$? What do you mean by 'more than 1 real parameters' ? $\endgroup$ – Red shoes Jun 21 '17 at 9:25
3
$\begingroup$

Considering $1<a<b<c$ then we can see that $$a x_1 + b x_2 + c x_3 \leq a^2 x_1 + b^2 x_2 + c^2 x_3$$

Provided that $x_i \geq 0.$ This proves that the first constraint is redundant. So problem is equivalent to the following linear programin

$$\begin{array}{ll} \text{maximize} & x_1 + x_2 + x_3\\ \text{subject to} & a^2 x_1 + b^2 x_2 + c^2 x_3 \leq 1\\ & x_1,x_2,x_3 \geq 0\end{array}$$ A simple analysis reveals that maximum is attained where $x_1$ be as large as possible. Which is $x_1 = \frac{1}{a^2}$. So the optimal solution is $(\frac{1}{a^2}, 0 , 0).$

Other way of thinking about it is looking at its graph, or there are only three extreme points.

$\endgroup$
  • $\begingroup$ alternative to the simple analysis, check the corner points: $(1/a^2,0,0); (0,1/b^2,0); (0,0,1/c^2)$, since it is a linear programming problem... $\endgroup$ – farruhota Jun 21 '17 at 10:25
0
$\begingroup$

It seems that $a,b,c>1$ and $a,b,c \in \mathbb R$. Now apply the simplex alogrithm. To start I give you the initial tableau

$$\begin{array}{|c|c|c|c|c|c|c|} \hline x_1 & x_2 & x_3 & s_1 & s_2 &RHS \\ \hline -1 & -1 & -1 & 0 & 0 &0 \\ \hline a & b & c & 1& 0 & 1 \\ \hline \color{red}{a^2}& b^2& c^2 &0 &1 &1 \\ \hline\end{array}$$

The coefficients of the objective function are all equal. The simplex algorithm gives us free choice for the pivot column. I choose the first one ($x_1$). And the pivot row is the last one since $\min \left(\frac1a; \frac1{a^2}\right)=\frac1{a^2}$

$\endgroup$
  • $\begingroup$ considering OP's last comment , more than $1$, means $x_i >1$! which is weird. My personal question: Do you use software to produce Tableaus? Or is there any.. or website $\endgroup$ – Red shoes Jun 21 '17 at 9:37
  • $\begingroup$ Maybe, but I can´t believe it. Especially if I look at the original post. I don´t use any software. I have to type the whole MathJax code. You can click on the edit to see my.work $\endgroup$ – callculus Jun 21 '17 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.