1
$\begingroup$

I'm struggling on determining when to assign an artifical variable a positive or a negative value. The example I have at hand is:

Max: $x_1+x_2$

St.

$$\begin{align}3x_1+2x_2\le5\\ x_1-x_2\le1\\ -2x_1-x_2\le7\\ x_1,x_2\ge0.\end{align}$$

I'm trying to determine how much to increase the right hand side of the third constraint so that my program becomes feasible.

So I would do

Max $x_1+x_2$

St.

$$\begin{align}3x_1+2x_2+x_3&\le5\\ x_1-x_2+x_4&\le1\\ -2x_1-x_2+x_5-a&\le-7\\ x_1\ge 0, x_2&\ge0\\ x_3,x_4,x_5&\le0.\end{align}$$

Should my a be negative because i want to increase the negative $7$? or should it be positive? How do i know when to use a positive artificial variable or negative?

$\endgroup$
2
  • $\begingroup$ No need to change the constraints. Answer: $x_1 = 0$ and $x_2 = 5/2$, giving the maximum sum $5/2$. $\endgroup$ Nov 4, 2015 at 18:07
  • $\begingroup$ All the constraints are $L \le R$ so you add a slack variable and make them equal $L + S = R$. For constraints of the form $L \ge R$ subtract a slack variable $L - S = R$ $\endgroup$
    – user186104
    Nov 4, 2015 at 20:17

1 Answer 1

0
$\begingroup$

There is no need to change the constraints.

Answer: $x_1 = 0$ and $x_2 = 5/2$, giving the maximum sum $5/2$.

Here's a figure showing the constraints:

enter image description here

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .