Why do I get different inequalities from the same linear programming system?

52 Views Asked by At

This is from section 7.1 of Dasgupta's Algorithm book:img

I attempt to arrive at the optimal solution by using the existing inequalities.

$$x_2 \leq 300$$ $$x_1 + x_2 + x_3 \leq 400$$ $$4x_2 + 12x_3 \leq 2400$$ $$\Rightarrow x_1 + 6x_2 + 13x_3 \leq 3100$$

However if I take another route, it gets me another value:

$$7x_1 + 7x_2 + 7x_3 \leq 2800$$ $$-(6x_1 \leq 1200)$$ $$2x_2 + 6x_3 \leq 1200$$ $$-(3x_2 \leq 900)$$ $$\Rightarrow x_1 + 6x_2 + 13x_3 \leq 1900$$

Suppose I do not know the optimal value is 3100, I'd be inclined to think that two acquired inequalities are both valid. That means I should keep the the tighter bound of 1900, and ditch the first one.

What does all mean? What have I done wrong? Is this an indication that substitution is not the way to acquire the optimum in linear programming?