points beneath a line equation

Question

In Linear Programming say in $R^2$ if you have a factory that can produce 2 products P1 and P2 and if 100% for P1 then it can produce 15 or 100% P2 it can produce 12 and assuming a linear relationship, often we are asked to find the convex set of points feasible for this linear relation. In this case the 2 linear points are (0,12) and (15,0) and thus the line equation for maximum production is $y = -4/5x + 12$.

My question is why is the equation for the convex set of feasible points $y/12 + x/15 \le 1$.

How is the above mathematically derived as it clearly works?

Answer 1

If you multiply your second inequality by $12$, you get $$ \frac{12}{12} y + \frac{12}{15} x \le 12 \iff y + \frac{4}{5}x \le 12, $$ so this is really the same equation, constraining your production as an upper bound.

UPDATE

If there were 3 products, you would be bounding by the plane passing through the points $(a,0,0), (0,b,0)$ and $(0,0,c)$, which would have the equation $$ \frac{x}{a} + \frac{y}{b} + \frac{z}{c} = 1 $$ and in general, you have a hyperplane like that, inducing the inequality with $\le 1$ instead.

Answer 2

The equation for the maximum production line comes from the so called intercept form of a line:

• $\frac x{x_0} + \frac y{y_0} = 1$

Surely you know that a line is determined by two points. In your case we have $x_0 = 15$ and $y_0 = 12$. If you plug in the coordinates of the points $(15,0)$ and $(0,12)$ into the corresponding equation $\frac x{15} + \frac y{12} = 1$, you will see that these points satisfy the equation.

Edit after comment:

The convex set of feasible points is the intersection of the half planes $x\geq 0, y \geq 0$ and the proper halfplane created by the line $\frac x{15} + \frac y{12} = 1$. Note, that all halfplanes are convex and the intersection of convex sets is convex.

To choose the proper side of the halfplane - which means choosing the proper relation sign - can be quickly done by using a test point which belongs to the feasible points and does not lie on the line in question.

Choosing $(0,0)$ gives $\frac 0{15} + \frac 0{12} = 0 \color{blue}{<}1$. Hence, the relation sign for the production restriction is $\frac x{15} + \frac y{12} \color{blue}{\leq} 1 $.

This method works because halfplanes are connected sets and, hence, a relation sign belongs to exactly one of the halfplanes. In other words, a restricion changes only the relation sign when crossing the line bordering the half planes.