Linear problem with min of hyperbolic functions as the objective

71 Views Asked by At

I am trying to convert the problem below to linear programming problem and solve it with simplex algorithm. I am aware that converting max and min in goal function usually means adding proper constraints, however hyperbolic constraints are illegal in LPP. What am I missing here?

$$ \text{minimize} \left( \min\{\frac{1}{2x_1 + x_2}, \frac{1}{x_1 + x_2 + 1} \}\right) \\ x_1 + 2x_2 \leq 10 \\ x_1 + x_2 \leq 7 \\ x_1 \geq 2, x_2 \geq 0 $$

1

There are 1 best solutions below

0
On BEST ANSWER

Note that $x_1\ge 2 >1$ implies that $2x_1+x_2>x _1+x_2+1$, so $1/(2x_1+x_2)<1/(x_1+x_2+1)$, so you can replace the inner $\min$ with the first minimand. Because the denominator is positive, minimizing $1/(2x_1+x_2)$ is equivalent to maximizing $2x_1+x_2 $. Your solution $x=(7,0)$ is optimal for the resulting maximization LP, with objective value $14$, so the optimal objective value for the original problem is $1/14$.