Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
use the 2-phase simplex method. –  Paul Slevin May 1 '12 at 1:33
add comment

1 Answer 1

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|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
1  
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
add comment

Your Answer

 
discard

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.