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.

Max: $ z = 10( x_1 + x_2)$

subject to constraints:

  1. $$ 2x_1 + 5x_2 \leq 16 $$
  2. $$ 6x_1 + 5x_2 \leq 30 $$

$$ x_1, x_2 \in \mathbb{Z^+} $$

I have the Integer Programming Problem as above. While solving it, My results come out to be:

$$ \pmatrix{ x_1 \\ x_2 } = \pmatrix{3 \\ 2} \text{ OR } \pmatrix{4 \\ 1} $$

But, in the constraint equation, if I subtract one from other; I get

$$ 4x_1 \leq 14 $$ or simply, $ x_1 \leq \dfrac{7}{2} = 3.5 $.

Now, as per this new outcome/restriction on $ x_1 $, I am thinking that my solution of the IPP was wrong.

Is my procedure to manipulate the constraint equations wrong?

From the graph, I do see that my solution is correct and my newer constraint $x_1 \leq 3.5$ is wrong. But, can someone explain why?

Graph

share|improve this question
2  
If $1 \le 3$ and $2 \le 3$, "subtracting" as you did, what do you get? –  Macavity Mar 19 '13 at 18:40
    
@Macavity Put it as a reply. =) It certainly is a better case than what Dan Brumleve has mentioned in the reply. –  hjpotter92 Mar 19 '13 at 18:42
    
OK. But I am sure it was a slip without attention. –  Macavity Mar 19 '13 at 18:44
add comment

5 Answers 5

up vote 2 down vote accepted

If $1 \le 3$ and $2 \le 3$, "subtracting" as you did, what do you get?

share|improve this answer
add comment

For some reason you use in this kind of problems the variables $\,x_1, x_2\,$ , whereas the whole world, and even some people in Jupiter, Vega and the third planet of Sirius, use the variables $\,x,y\,$...oh, well.

Anyway, it seems to be $\,x_1\,$ is your horizontal axis, but then

$$6x_1+5x_2=30\Longrightarrow \;\text{the intersection points with the axis are}\;\; (5,0)\;,\;\;(0,6)\,\,\text{and so this is your green line}$$

$$2x_1+5x_2=16\Longrightarrow \;\text{the intersection points with the axis are}\;\; (8,0)\;,\;\;\left(0,\frac{16}{5}\right)\,\,\text{and so this is your blue line}$$

The intersection point of the green and blue lines is given by:

$$-10x_2=-18\Longrightarrow x_2=\frac{9}{5}\,\,,\,\,\text{and thus}\;\;x_1=\frac{7}{2}$$

So the maximum-minimum values for the target function are on the target domain limited by the given lines and the axis on the first quadrant, so we must look at the values on the points of intersection of all these:

$$f(0,0)=0\\{}\\f(5,0)=50\\{}\\f\left(0\,,\,\frac{16}{5}\right)=32\\{}\\f\left(\frac{7}{2}\,,\,\frac{9}{5}\right)=5\cdot 7+2\cdot 9=53$$

And there up you have the maximum and minimum values of the target function.

share|improve this answer
add comment

If you want to substract you have to change sign for (-) such as your first inequality becomes $$-2x_1-5x_2\ge -16$$

share|improve this answer
add comment

Subtraction would have the effect of multiplying -1 which does have an effect on inequalities would be the point you may be missing here in deriving the new expression.

share|improve this answer
add comment

You cannot subtract inequalities. Consider $2 \lt 3$, $1 \lt 2$, but it is not true that $2-1 \lt 3-2$

share|improve this answer
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.