تستخدم نجوى ملفات تعريف الارتباط لضمان حصولك على أفضل تجربة على موقعنا. معرفة المزيد حول سياسة الخصوصية لدينا.

فيديو: البرمجة الخطية والحل الأمثل

سوزان فائق

يوضح الفيديو تعريف البرمجة الخطية، وكيفية استخدامها لحساب القيم القصوى للدوال، وخطوات إيجاد الحل الأمثل باستخدام البرمجة الخطية، وأمثلة توضيحية.

١٤:٥٧

‏نسخة الفيديو النصية

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

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

يعني إيه الكلام ده؟ يعني بنشوف طريقة نوجد بيها القيم العظمى أو الصغرى. فيه أوقات بنحتاج القيم العظمى؛ زيّ مثلًا أعلى ربح. أو الصغرى اللي هي أقل تكلفة.

«لدالة» دي بنسميها دالة الهدف، اللي إحنا عايزين نوصل له. يعني مثلًا لو عايزين نوصل لأعلى ربح، أو أقل تكلفة. بنشوف علاقة بين متغيرين، ونحقق القيم العظمى والصغرى، تحت القيود اللي هيدّيها لنا. طيب «دالة الهدف» دي بتتكتب على شكل دالة في س وَ ص بتساوي أيّ رقم عدد حقيقي لا يساوي الصفر، مضروب في الـ س. زائد ب عدد حقيقي، مضروب في الـ ص. وده بيبقى شكل دالة الهدف، اللي إحنا عايزين نوصل لها. وبتبقى دالة خطية.

«تحت قيود معينة» القيود دي بنمثلها بمتباينة خطية. بنمثّلها على الرسم البياني. والقيود دي اللي بتتفرض علينا من المسألة. زي مثلًا إن إحنا بنشوف كمية الطلب على نوع معيّن من الملابس، أو طريقة الشحن، أو كفاءة المصنع. دي بتعمل لنا قيود في الدالة بتاعتنا. عشان نعرف نوصل لأعلى ربح أو أقل تكلفة، على حسب المسألة.

طيب، إزاي بنجيب القيمة العظمى أو الصغرى؟ بنرسم المتباينات، اللي هي القيود بتاعتنا. وبعدين نشوف القيمة العظمى والصغرى موجودة فين. ودي بتبقى على أحد رؤوس منطقة الحل للمتباينات اللي هنمثلها بيانيًّا.

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

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

المثال بيقول: مثِّل نظام المتباينات الآتي بيانيًّا. ثم حدّد إحداثيات رؤوس منطقة الحل. واوجد القيمة العظمى والقيمة الصغرى للدالة المعطاة في هذه المنطقة.

المتباينات عندنا: ص أكبر من أو يساوي تلاتة، وأصغر من أو يساوي ستة. والـ ص أصغر من أو يساوي تلاتة س زائد اتناشر. والـ ص أصغر من أو يساوي سالب اتنين س زائد ستة. والدالة اللي عندنا هتبقى دالة س وَ ص تساوي أربعة س ناقص اتنين ص.

خطوات الحل عندنا هتبقى أول خطوة هنمثّل المتباينات بيانيًّا، ونحدد إحداثيات الرؤوس. هنمثّل المتباينات بالشكل ده: الـ ص هتبقى التلاتة إلى ستة. وبعدين ص تساوي سالب اتنين س زائد ستة. وَ ص تساوي تلاتة س زائد اتناشر. يبقى منطقة الحل بتاعتنا هي المنطقة دي.

هنقرا إحداثيات النقط بتاعة التقاطعات، اللي هي رؤوس منطقة الحل. هنسمّي دي واحد، اتنين، تلاتة، أربعة. النقطة رقم واحد هتبقى سالب اتنين، وستة. النقطة رقم اتنين هتبقى سالب تلاتة، وتلاتة. النقطة رقم تلاتة هتبقى واحد ونص، وتلاتة. رابع نقطة اللي هو الرأس الرابع هتبقى صفر، وستة.

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

الجدول قدامنا. هنعوّض بالنقط اللي موجودة، سالب اتنين وستة. هنعوّض بيها في الدالة أربعة س ناقص اتنين ص؛ علشان نوجد قيمة الدالة س وَ ص. يبقى أربعة في سالب اتنين، ناقص اتنين في ستة. هتبقى قيمتها سالب عشرين. هنعوّض بباقى النقط. هنقارن بين القيم اللي موجود عندنا. هنشوف القيمة العظمى للدالة، اللي هي أكبر قيمة. والقيمة الصغرى أصغر قيمة.

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

المثال بيقول مثِّل نظام المتباينات الآتي بيانيًّا. ثم حدّد إحداثيات رؤوس منطقة الحل. واوجد القيمة العظمى والقيمة الصغرى للدالة المعطاة في هذه المنطقة.

المتباينات: اتنين ص زائد تلاتة س أكبر من أو يساوي سالب اتناشر. وَ ص أصغر من أو يساوي تلاتة س زائد اتناشر. وَ ص أكبر من أو يساوي تلاتة س ناقص ستة. والدالة اللي عندنا اللي هي دالة س وَ ص تساوي تسعة س ناقص ستة ص.

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

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

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

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

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

المثال بيقول: يبيّن الجدول أكبر وأقل عدد للأثواب المنتجة في اليوم الواحد، من المقاسين الكبير والصغير. وتكلفة إنتاج كل ثوب منها في أحد المصانع. استخدِم البرمجة الخطية لإيجاد عدد القطع التي يتطلّب إنتاجها من المقاسين؛ لتكون التكلفة أقلّ ما يمكن. إذا كان عدد الأثواب المطلوب إنتاجها في اليوم الواحد يساوي ألفين ثوب.

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

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

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

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

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