2
$\begingroup$

I have the following linear programming problem:

  1. Convert the following problems to standard form: $$\begin{align} \text{a)}&\text{minimize}&x+2y+3z\\ & \text{subject to}&2\le x+y\le 3\\ & &4\le x+z \le 5\\ & &x\ge 0, \,\,\,y\ge0\,\,\,z\ge0.\\ \\ \text{b)}&\text{minimize}&x+y+z\\ & \text{subject to}&2\le x+y\le 3\\ & &x\ge 1, \,\,\,y\ge2\,\,\,z\ge1.\\ \end{align}$$

Here is my attempted solution:

$(1a)$ First I note that: $x+y \ge 2, x+y \leq 3, x+y\ge 4, x+y \leq 5$ with $x,y,z \ge 0$. I transform the equation into standard form by selecting two surplus and two slack variables $a, b, c, d$. So I get:

$$\text{minimize} \;\;\; x+2y+3z$$ $$\text{subject to} \;\;\; x+y + a= 3$$ $$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; x+y - b= 2$$ $$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; x+y + c= 5$$ $$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; x+y - d= 4$$ $$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; x \ge 0, \;\; y \ge 0, \;\; z \ge 0, \;\; a \ge 0, \;\; b \ge 0, \;\; c \ge 0, \;\; d \ge 0 \;\;.$$

$(1b)$ I do a change of variables by setting $a = x-1, b=y-2, c=z-1$. Then I formulate the problem in terms of variables $a, b$ and $c$ :

$$\text{minimize} \;\;\; a+b+c+4$$ $$\text{subject to} \;\;\; a+2b + 3c= 2$$ $$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; a \ge 0, \;\; b \ge 0, \;\; c \ge 0, \;\;.$$

Now this problem is equivalent with the original problem and by solving the optimal values for $a, b$ and $c$ I can solve the values for $x, y$ and $z$.

I would appreciate if someone can correct my mistakes if any exist :) I'm new with linear and nonlinear programming and want verification whether I have understood the basic concepts or not :)

Thank you!

$\endgroup$
  • 1
    $\begingroup$ Please, one problem per question only. $\endgroup$ – Ataraxia Aug 23 '13 at 8:54
  • $\begingroup$ Oh, sorry about that. I tried to optimize :) $\endgroup$ – jjepsuomi Aug 23 '13 at 9:03
  • $\begingroup$ Can't fault a person for trying to optimize :) It's discouraged for a number of reasons. It's acceptable if all the problems are related in some way (and it's preferable if you tie them all together with a single question). $\endgroup$ – Ataraxia Aug 23 '13 at 9:09
  • $\begingroup$ aah, I get it. Thank you :) I will keep that in mind. Should I edit my question then to include only one and make two separate ones also? $\endgroup$ – jjepsuomi Aug 23 '13 at 9:18
  • $\begingroup$ Yea, that would be best. And you're quite welcome. $\endgroup$ – Ataraxia Aug 23 '13 at 9:23
1
$\begingroup$

@jjepsuomi $(1a)$: I think your third and fourth lines of constraints should be something like $x + z + c=5$ and $x+z-d=4$ instead.

Cheers!

$\endgroup$
  • $\begingroup$ thank you for your help =) $\endgroup$ – jjepsuomi Apr 16 '15 at 13:14

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.