4

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$

Sigur
  • 6,416
  • 3
  • 25
  • 45
John
  • 41
  • 1
  • 2
  • 1
    Did you draw the lines/area coming from those inequalities? – Sigur Dec 09 '12 at 00:56
  • 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 – John Dec 09 '12 at 00:57
  • I don't know what is GAMS. – Sigur Dec 09 '12 at 01:00
  • 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. – John Dec 09 '12 at 01:03

2 Answers2

3

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.

David Nehme
  • 1,042
  • 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. – John Dec 09 '12 at 02:00
-1

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.

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