0

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?

gt6989b
  • 54,422
mathcomp guy
  • 478

2 Answers2

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.

gt6989b
  • 54,422
  • thanks yes I deduced that as well upon further inspection. One item I thought this related to was in the proof for a secant line to be above a convex function whereby $f(x\lambda + (1-\lambda)x1) <= \lambda f(x) + (1-\lambda)f(x1)$ where $\lambda \in [0,1]$. Is the $\lambda$ derivation that any value in a set $[a,b]$ can be computed by $ax + b(1-x)$ where $ x \in [0,1]$. I'm not sure how this was deduced but I suspect it's similar to normalizing the set by dividing by b in similar fashion to the above? – mathcomp guy Feb 03 '20 at 18:19
  • Also is this true for any relationship in $R^n$ say if there were 3 products each with production capacity a,b,c then would the equation be $1/aP1 + 1/bP2 + 1/cP3 <= 1$ that would define the convex set? – mathcomp guy Feb 03 '20 at 18:35
  • @PEBguy the the update for your last question, don't understand the first one – gt6989b Feb 03 '20 at 18:40
0

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.

trancelocation
  • 32,243