# How do I solve a LP problem when constrains have different inequalties?

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?

-
use the 2-phase simplex method. – 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).

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

-
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