# Quod Erat Demonstrandum

## 2007/11/01

### [CE] Linear programming – system of inequalities

Filed under: HKCEE — johnmayhk @ 3:58 下午

1.

Just start teaching the solving of system of 2-variable linear inequalities. One F.5C student, Yeung, told me that “no solution for parallel lines", Oops, his comment was too brief but I understood him immediately. Let me refine his observation, as follows.

Consider a system of two 2-variable linear inequalities (x and y are real with no extra restriction), the system MAY have no solution only when two different corresponding straght lines are parallel to each other.

As for example,

$x + 2y < 1$
$2x + 4y > 4$

The two corresponding lines $x + 2y = 1$ and $2x + 4y = 4$ are parallel, and the system above has no solution.

In other words, the (two 2-variable linear inequalities) system MUST be solvable if the system is ‘corresponding to’ two non-parallel lines. Although it’s not something very striking, I appreciate the discovery, because it is totally orignated from a student himself. Now, could you show me the proof of Yeung’s observation?

[But, most of F.5C students were out of mood of attending the lesson that day, may be they thought that the content is TOO EASY.]

2.

To solve $Ax + By + C < 0$,
we draw $L: Ax + By + C = 0$, and
$L$ divides the x-y plane into 2 regions, namely $R_1$ and $R_2$.
Knowing that $P(x_1,y_1)$ lies on $R_1$ and
$P$ satisfies $Ax + By + C < 0$, that is
$Ax_1 + By_1 + C < 0$, then
$R_1$ is the required region.
That is, $R_1$ represents the solution to the inequality $Ax + By + C < 0$.

The question is: why we just try one point? Should we try another? Is it possible that there is another point $Q$ lying on $R_1$ but $Q$ does not satisfy the inequality $Ax + By + C < 0$? How to prove that “one point is enough for representing the whole region"?

Well, the first thing in my mind is the signed distance (有向距離) from a point to a line.

Additional Mathematics tells us that the distance between a point $P(x_1,y_1)$ and a line $L : Ax + By + C = 0$ is $|\frac{Ax_1 + By_1 + C}{\sqrt{A^2 + B^2}}|$. The absolute sign is for ensuring non-negative distance. How about getting rid of the absolute sign? The numerator $Ax_1 + By_1 + C$ may be positive, zero or negative. What is the significant geometric meaning of the positive and negative values obtained?

Just tell you the following.

If $Ax_1 + By_1 + C$ is positve, then $P$ and $O$ are at the different sides of $L$ (as shown)

If $Ax_1 + By_1 + C$ is negative, then $P$ and $O$ are at the same sides of $L$ (as shown)

Back to our questions, if $O$ does not lie on $L$, $O$ must lie on one of the regions $R_1$ and $R_2$. Suppose $O$ lies on $R_1$, then all the points on $R_1$ and $O$ are at the same side of $L$. Hence any point $Q(a,b)$ lying on $R_1$ will lead to the result $A(a) + B(b) + C < 0$. Hence one point is enough! It is impossible to have another point $T$ lying on $R_1$ such that $T$ does not satisfy $Ax + By + C < 0$.

Please complete the discussion when $O$ lies on $L$.

3.

F.5C students asked, ‘how about the case for 3 or more variables?’ To the best of my memory, we may use simplex method.