0
$\begingroup$

Convert the following model into an LP model. Note that you're not being asked to convert this to standard form.

$$\min z = \max (x_1, x_2, x_3, 2000)$$

s.t. $$-2x_1 + x_2 + x_3 \geq -4$$

$$3x_1 - 4x_2 + x_3 \leq 12$$

$x_i \geq 0$ for all $i$

I am having difficulty thinking through how to set up an objective function that isn't a formula, but selects the maximum of multiple variables. I've tried setting up the $\max(x_1, x_2, x_3, 2000)$ as a matrix and as another variable x4, but it doesn't make sense to me on paper. When I write the problem in Excel, I use =MAX(x1, x2, x3, 2000) as the objective function but I don't understand the algorithm I would use to solve this problem. I've researched several textbooks and am stuck on setting up an objective function that selects a single maximum value of several variables.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Welcome to SciComp.SE. Please don't just post (homework) problems verbatim; this is not the purpose of this forum (not to mention, quite rude). If there's a specific step you have difficulties with, feel free to ask about it, but tell us exactly where you have problems and what you have already tried. $\endgroup$ – Christian Clason Oct 17 '15 at 17:20
  • $\begingroup$ I have three LP textbooks in front of me but can't figure out how to write an objective function that selects the maximum of multiple choices, like the max (x1, x2, x3, 2000). When I set this up with Solver in Excel, i just use the =MAX() function, but I don't really understand what the LP model should look like. $\endgroup$ – riverrat Oct 17 '15 at 18:05
1
$\begingroup$

Hint: The value $\max(x_1,x_2)$ is the smallest value $t$ for which $t\geq x_1$ and $t\geq x_2$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks, Dirk. I did try writing it as: min t s.t. t >= x1, t >= x2, t >= x3, t>= 2000, -2x1 + x2 + x3 >= -4, 3x1 - 4x2 + x3 <= 12, xi >= 0 for all i But if I try to practically solve it, it seems that the objective function needs to be a formula based on the values of x1, x2, x3 if those are the variables I want the model to "change". $\endgroup$ – riverrat Oct 17 '15 at 18:29
  • $\begingroup$ You are doing it right. You define the new variable $y = [x_1,x_2,x_3,t]^T$ and use the objective $\min_y\, c^T y$ with $c=[0\ 0\ 0\ 1]^T$. After solving, just take the first three entries of $y$ and your values for $x_1,x_2,x_3$. $\endgroup$ – Dirk Oct 17 '15 at 18:48

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.