Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
use the 2-phase simplex method. – Paul Slevin May 1 '12 at 1:33
up vote 3 down vote accepted

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$$

share|cite|improve this answer
But should I add an artificial variable to 2x+y >=30 ? something like 2x+y - s3 + Z1 =30 ? – Binarylife Apr 30 '12 at 3:44
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$. – copper.hat Apr 30 '12 at 4:09
aha , I see, thanks:) – Binarylife Apr 30 '12 at 4:15

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.