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.

發表迴響 »

仍無迴響。

RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

在 WordPress.com 建立免費網站或網誌.

%d 位部落客按了讚: