المتراجحات في المستوى والبرمجة الخطية

ملخص

ينقل هذا الدرس دراسة المتراجحات إلى المستوى. فهو يبرهن أن المستقيم يقسم المستوى إلى نصفي مستوى، تحافظ العبارة الخطية التي تعرّفه في كل منهما على إشارتها، ويستنتج من ذلك طريقة نقطة الاختبار. ويصف منطقة الحلول لنظام متراجحات خطية بوصفها تقاطعًا لأنصاف مستويات، مع رؤوسها، ويبرهن أنها محدبة؛ ثم يدرس المناطق التي تحدها القطوع المخروطية. ويختم بالبرمجة الخطية: البحث عن القيمة العظمى أو الصغرى لدالة خطية على منطقة مضلعية، وتضمن مبرهنتها الأساسية أن كلتيهما تُبلغان في رؤوس المضلع المحدب المحدود، وأن كل قيمة مثلى موجودة في منطقة غير محدودة لها رأس واحد على الأقل تُبلغ أيضًا في أحد رؤوسها، ثم بمسائل في الإنتاج والتغذية والنقل.

أهداف التعلم

تمثيل مجموعة حلول متراجحة خطية بمتغيرين على شكل نصف مستوى، مفتوح أو مغلق، بواسطة نقطة اختبار.
تعيين منطقة الحلول لنظام متراجحات خطية ورؤوسها وكونها محدودة أو غير محدودة، وتعليل تحدبها.
وصف مناطق تحدها مستقيمات وقطوع مخروطية بواسطة متباينات، وتمثيل المناطق الموصوفة على هذا النحو.
صياغة مسائل البرمجة الخطية بمتغيرين وحلها بمبرهنة الرؤوس ومستقيمات المستوى، مع التمييز بين الحل الأمثل الوحيد والحلول المثلى المتعددة وانعدام الحل الأمثل.

أنصاف المستويات

في الدرس الخاص بـمعادلة المستقيم رأينا أن كل مستقيم هو مجموعة النقاط التي تحقق معادلة $Ax + By + C = 0$ ، حيث $A$ و $B$ ليسا منعدمين معًا: إذا كان $B \neq 0$ ، نحل المعادلة فنحصل على $y = -\frac{A}{B}x - \frac{C}{B}$ ، وهو مستقيم ميله $-\frac{A}{B}$ ؛ وإذا كان $B = 0$ ، تؤول المعادلة إلى $x = -\frac{C}{A}$ ، وهو مستقيم رأسي. وإذا طُلبت متباينة بدل المساواة، كفّت مجموعة الحلول عن أن تكون منحنى وصارت منطقة. وفي الدرس الخاص بـالمعادلات والمتراجحات من الدرجة الأولى كان حل المتراجحة الخطية ذات المجهول الواحد فترة من المستقيم الحقيقي؛ أما بمجهولين فالحل نصف مستوى.

ليكن $r$ مستقيمًا غير رأسي ولتكن $P = (x_0, y_0)$ نقطة. نقول إن $P$ تقع فوق $r$ إذا كان $y_0$ أكبر من ترتيبة نقطة $r$ التي فاصلتها $x_0$ ، وتحت المستقيم إذا كان أصغر منها. وإذا كان $r$ رأسيًا، نتكلم بالطريقة نفسها عن النقاط الواقعة على يمينه وعلى يساره. وكل واحدة من هاتين المجموعتين نصف مستوى مفتوح حدّه $r$ ؛ وإذا أضيف إليها المستقيم، فهي نصف مستوى مغلق.

مبرهنةأنصاف المستويات

ليكن $r$ المستقيم $Ax + By + C = 0$ ، حيث $A$ و $B$ ليسا منعدمين معًا، وليكن $E(x, y) = Ax + By + C$ . للعبارة $E$ إشارة ثابتة في كل جانب من جانبي $r$ : فهي موجبة في جميع نقاط أحد نصفي المستوى المفتوحين وسالبة في جميع نقاط الآخر. وبدقة أكبر، إذا كان $B > 0$ ، فهي موجبة فوق $r$ وسالبة تحته؛ وإذا كان $B < 0$ ، فالعكس؛ وإذا كان $B = 0$ ، فهي موجبة على يمين $r$ عندما يكون $A > 0$ ، وعلى يساره عندما يكون $A < 0$ .

البرهان

$\dato{q}{A x_0 + B y_1 + C = 0}$
لتكن $P = (x_0, y_0)$ نقطة لا تقع على $r$ ، ولنفترض أولًا أن $B \neq 0$ . المستقيم الرأسي المار بـ $P$ يقطع $r$ في نقطة وحيدة $Q = (x_0, y_1)$ ، تُحسب ترتيبتها بإيجاد $y$ من معادلة $r$ ؛ والنقطة $Q$ تحقق هذه المعادلة.
$E(x_0, y_0) = \resaltar{(A x_0 + B y_0 + C) - (A x_0 + B y_1 + C)} = \dato{dif}{\resaltar{B \cdot (y_0 - y_1)}}$
نطرح هذا الصفر من قيمة $E$ عند $P$ : تُختصر الحدود التي تحوي $x_0$ والثوابت، ويبقى جداء.
$B > 0 \rightarrow \left( E(x_0, y_0) > 0 \leftrightarrow y_0 > y_1 \right)$
إذا كان $B > 0$ ، فبحسب قاعدة الإشارات المدروسة في الدرس الخاص بـجداول الإشارات والمتراجحات، للجداء إشارة $y_0 - y_1$ : فهو موجب عندما تقع $P$ فوق $r$ وسالب عندما تقع تحته.
$B < 0 \rightarrow \left( E(x_0, y_0) > 0 \leftrightarrow y_0 < y_1 \right)$
إذا كان $B < 0$ ، فللجداء إشارة مخالفة لإشارة $y_0 - y_1$ : العبارة سالبة فوق $r$ وموجبة تحته.
$E(x_0, y_0) = \resaltar{(A x_0 + C) - (A x_1 + C)} = \resaltar{A \cdot (x_0 - x_1)}$
إذا كان $B = 0$ ، فإن $A \neq 0$ و $r$ هو المستقيم الرأسي $x = x_1$ ، حيث $x_1 = -\frac{C}{A}$ . نعيد الحساب بنقطة $r$ التي لها ترتيبة $P$ .
$A > 0 \rightarrow \left( E(x_0, y_0) > 0 \leftrightarrow x_0 > x_1 \right)$
إذا كان $A > 0$ ، فالعبارة موجبة إذا وفقط إذا كان $x_0 > x_1$ ، أي على يمين $r$ ؛ وإذا كان $A < 0$ ، فعلى يساره. وفي جميع الحالات تتوقف إشارة $E$ عند نقطة على الجانب الذي تقع فيه النقطة من $r$ فقط.

تقول المبرهنة أكثر مما يُستعمل في التطبيق: لا حاجة إلى تذكر الإشارة المقابلة لكل جانب، لأن معرفة إشارة $E$ عند نقطة واحدة من جانب تكفي لمعرفتها في جميع نقاطه. وهذه هي طريقة نقطة الاختبار.

لتمثيل متراجحة $Ax + By + C > 0$ ، أو بـ $<$ أو $\ge$ أو $\le$ ، نرسم المستقيم $Ax + By + C = 0$ ونحسب قيمة العبارة عند نقطة اختبار لا تقع عليه، وهي في العادة الأصل. إذا حققت النقطة المتراجحة، فمجموعة الحلول هي نصف المستوى الذي يحويها؛ وإذا لم تحققها، فهي الآخر. وإذا كانت المتباينة صارمة، فالمستقيم ليس جزءًا من مجموعة الحلول ويُرسم متقطعًا؛ وإذا لم تكن صارمة، فهو جزء منها ويُرسم متصلًا.

مثالنصف مستوى بنقطة الاختبار

مثّل مجموعة حلول المتراجحة $2x - 3y + 6 > 0$ .

البرهان

$2x - 3y + 6 = 0, \quad (0, 2), \quad (-3, 0)$
نرسم المستقيم الحدودي بنقطتي تقاطعه مع المحورين: مع $x = 0$ نحصل على $y = 2$ ، ومع $y = 0$ نحصل على $x = -3$ .
$2 \cdot 0 - 3 \cdot 0 + 6 = \resaltar{6} > 0$
الأصل لا يقع على المستقيم. نحسب عنده قيمة العبارة: القيمة موجبة، فالأصل يحقق المتراجحة.
$2x - 3y + 6 > 0 \leftrightarrow \resaltar{y < \frac{2}{3}x + 2}$
مجموعة الحلول هي نصف المستوى الذي يحوي الأصل. والمبرهنة تؤكد ذلك: بما أن $B = -3 < 0$ ، فالعبارة موجبة تحت المستقيم.
$2 \cdot (-3) - 3 \cdot 0 + 6 = \resaltar{0}$
المتباينة صارمة: نقاط المستقيم، مثل $(-3, 0)$ ، تعدم العبارة ولا تحقق المتراجحة. فالحد مستبعد ويُرسم متقطعًا.

في بقية هذا الدرس

أنظمة المتراجحات الخطية
المناطق المحدودة وغير المحدودة والخالية
التحدب
مناطق تحدها القطوع المخروطية
البرمجة الخطية
مستقيمات المستوى
المناطق غير المحدودة والحلول المثلى المتعددة
النمذجة
مسائل محلولة
مربع موصوف بقيم مطلقة
إنتاج ورشة
تغذية بأقل تكلفة
منطقة تتلاشى
القيمة العظمى على حد منحن
مسائل مقترحة
أقرب إلى الأصل
حلول مثلى لا نهاية لعددها
النقل بين مخزنين
عندما لا يكون الرأس صحيحًا
رأس أمثل بحسب الوسيط