# How can I solve a linear program with parameters?

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?

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

## 2 Answers

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.

• 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... – farruhota Jun 21 '17 at 10:25

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}$

• 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 – Red shoes Jun 21 '17 at 9:37
• 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 – callculus Jun 21 '17 at 9:43