4
$\begingroup$

How can I linearize $\min(x_1,x_2,x_3)$ in a maximization linear programming problem? Please help me. I've tried many things but I didn't solve.. My LP equations are as follows:

Objective function is: maximize $z=\min(x_1,x_2,x_3)$

Constraints:

$0.6 x_1 + 0.8 x_2 \leq 4500 \times 20$

$0.2 x_2 \leq 4500 \times 3$

$0.3 x_2 \leq 4500 \times 6$

$0.4 x_1 + 0.6 x_2 \leq 4500 \times 10$

$0.3 x_1 \leq 4500 \times 5$

$\endgroup$
  • 1
    $\begingroup$ Did you draw the lines/area coming from those inequalities? $\endgroup$ – Sigur Dec 9 '12 at 0:56
  • $\begingroup$ No, but I don't need this since I will solve the problem in GAMS. I just need to linearize the objective function. Please help me $\endgroup$ – John Dec 9 '12 at 0:57
  • $\begingroup$ I don't know what is GAMS. $\endgroup$ – Sigur Dec 9 '12 at 1:00
  • $\begingroup$ Don't you know how to linearize z=min(x1,x2,x3) ? I do not need the solution of the problem but the linearization of z=min(x1,x2,x3) my friend ? Thank you for your care. $\endgroup$ – John Dec 9 '12 at 1:03
3
$\begingroup$

How you implement min($x_1, x_2, x_3$) in an LP solver depends on what you are trying to do with it. Since you are maximizing it you can do the following

$$ {\rm maximize } \ z $$ subject to $$ z \le x_1 \\ z \le x_2 \\ z \le x_3 $$ $z$ will take the value of min($x_1, x_2, x_3$) in any optimal solution.

$\endgroup$
  • $\begingroup$ Shouldn't z consist of x1,x2 or x3 in an LP? I thought that situation but I didn't implement this solution's code. $\endgroup$ – John Dec 9 '12 at 2:00
-1
$\begingroup$

assume $y=\min\{x_1,x_2,x_3\}$

Now we need to maximize $y$

since value of $y$ can either be $x1$, $x2$ or $x3$, we can safely add the following constraints:

$$x_1\geq y \qquad x_2 \geq y \qquad x_3\geq y$$

or

$$x_1-y\geq 0 \qquad x_2-y \geq 0 \qquad x_3-y\geq 0$$

now solve the problem.

$\endgroup$
  • 2
    $\begingroup$ I wish I understood the purpose of giving a hint to a three-year-old question. But I guess I never will. $\endgroup$ – user228113 Nov 21 '15 at 20:28
  • $\begingroup$ Viraj, welcome to Math.SE. You will find that MathJax and $\LaTeX$ can be used to post mathematical expressions. $\endgroup$ – hardmath Nov 21 '15 at 20:35

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.