How can I solve this LP problem:

Maximize p=x subject to :

x+y <=30

x-2y <= 0

2x+y >=30

x>=0 , y>=0

using simplex method?

  • 1
    $\begingroup$ use the 2-phase simplex method. $\endgroup$ – Paul Slevin May 1 '12 at 1:33

I am guessing you are asking how to write the LP in 'standard form'?

The general idea here is if you have a constraint of the form $a_1 x_1 + \cdots + a_n x_n \leq 0$, then you replace this constraint by an equality constraint of the form $a_1 x_1 + \cdots + a_n x_n = -s$, where $s$ is a new variable (called a slack variable) with the constraint $s \geq 0$. It is easy to see that these are equivalent (as long as you now optimize over the new variables as well).

So, your problem would become:

Maximize p=x subject to :

$$x+y = 30-s_1$$

$$x-2y = -s_2$$

$$2x+y = 30+s_3$$

$$x \geq 0 , y\geq 0$$ $$s_1 \geq 0 , s_2\geq 0, s_3 \geq 0$$

  • $\begingroup$ But should I add an artificial variable to 2x+y >=30 ? something like 2x+y - s3 + Z1 =30 ? $\endgroup$ – Binarylife Apr 30 '12 at 3:44
  • 1
    $\begingroup$ No. The $s_3$ slack variable already allows you to replace the $\geq$ by $=$. Note the sign on $s_3$, which is different to the sign on $s_1, s_2$. $\endgroup$ – copper.hat Apr 30 '12 at 4:09
  • $\begingroup$ aha , I see, thanks:) $\endgroup$ – Binarylife Apr 30 '12 at 4:15

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.