0
$\begingroup$

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
    use the 2-phase simplex method.2012-05-01

1 Answers 1

3

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

  • 0
    But should I add an artificial variable to `2x+y >=30` ? something like `2x+y - s3 + Z1 =30` ?2012-04-30
  • 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$.2012-04-30
  • 0
    aha , I see, thanks:)2012-04-30