Inequalities for linear optimization confusion

Question

I am trying to understand Duality and while the author was leading up to the subject, he mentioned a few ways of lowering an upper bound that utterly confused me(and my understanding of inequalities.) Here was the LPP:

Maximize 3x + 2y subject to

4x + 2y <= 16

x + 2y <= 8

x + y <= 5

x,y >= 0

He started with stating we know 3x + 2y <= 4x + 2y <= 16 and therefor, 16 is an upper bound. This is logical to me-- he goes on to say we can multiply the constraint x + y <= 5 by 3 to get 3x + 3y <= 15 and sine y is nonnegative, 3x + 2y <= 3x + 3y and therefor 15 is a lower bound. Again, solid- but here is what confuses me.

He then says we can multiply 4x + 2y <= 16 by 1/2 to get 2x + y<= 8 and then add this to x + y <= 8 to get 3x + 2y <= 13 and therefor an upper bound is 13. This completely confused me because this seems like such an out there assumption that we can also conclude that 8 is an upper bound because of the initial multiplication. Is he making this assumption because he knows 4x + 2y <= 16 is the highest bound? The biggest problem I have with this is that he adds two constraints to create an upper bound and I just don't see the logic with that.

Please let me know the logical steps so I can figure this out and apply it-- I don't care how it works explicitly I want to know the intuition.

Answer 1

You can always add two inequalities if they are in the same direction (e.g., both $\le$ or both $\ge$).

And you can freely multiply an inequality by a positive constant.

You can also invoke transitivity (e.g., $f \le g$ and $g \le h$ implies $f \le h$).

But an inequality that asserts an upper bound for the objective function $3x+2y$ is an inequalty of the form $$3x + 2y \le \text{"some constant"}$$ so those are the ones the author is trying to achieve from the known constraints.

In particular, the newly obtained constraint $2x+y \le 8$ does not imply that $8$ is an upper bound for the objective function, since the $\text{LHS}$ is not $3x+2y$. But the new constraint is now part of the set of constraints, so can be used in combination with the others.

Thus, adding the constraints $2x+y \le 8$ and $x+y \le 5$ yields the inequality $3x+2y \le 13$, which has the objective function on the $\text{LHS}$, hence implies an upper bound of $13$ for the objective function.

Answer 2

You must know that $x$ and $y$ are just numbers.

In the first case the author says that $3x+2y\leq 4x+2y$ because this holds for any two non negative real numbers as $3x\leq 4x$ for all non negative real numbers.Similarly in the next argument as $x+y\leq 5$ it is sure that $3x+3y\leq 15$.As $2y\leq 3y$ for all non negative real numbers $3x+2y \leq 3x+3y$ also holds.

The third argument can be seen in a different way $3x+2y=(2x+y)+(x+y)={1/2(4x+2y)}+(x+y)$.

But as $4x+2y\leq 16$ we get $2x+y\leq 8$ and $x+y\leq 5$ So we get $3x+2y\leq 13$