البرمجة غير الخطية: الأساليب والتمارين - رياضيات - 2025

في البرمجة غير الخطية هي عملية تحسين وظيفة التي تعتمد على العديد من المتغيرات المستقلة، والتي بدورها تخضع لقيود.

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

الشكل 1. مشكلة البرمجة غير الخطية (NLP). حيث G هي الوظيفة (غير الخطية) للتحسين في المنطقة الخضراء ، التي تحددها القيود. المصدر: F. Zapata.

وبالتالي لا يمكن استخدام إجراءات وأساليب البرمجة الخطية.

على سبيل المثال ، لا يمكن استخدام طريقة Simplex المعروفة ، والتي تنطبق فقط عندما تكون الوظيفة الهدف والقيود كلها مجموعات خطية من المتغيرات في المشكلة.

طرق البرمجة الخطية

بالنسبة لمشاكل البرمجة غير الخطية ، الطرق الرئيسية المستخدمة هي:

1.- طرق الرسم.

2.- مضاعفات لاجرانج لاستكشاف حدود منطقة الحل.

3.- حساب التدرج لاستكشاف النهايات الدالة الهدف.

4.- طريقة الخطوات التنازلية لإيجاد نقاط الانحدار الفارغة.

5.- الطريقة المعدلة لمضاعفات لاغرانج (بشرط كاروش-كوهن-تاكر).

مثال على حل بطريقة رسومية

مثال على الحل بالطريقة الرسومية هو الذي يمكن رؤيته في الشكل 2:

الشكل 2. مثال على مشكلة غير خطية ذات قيود غير خطية وحلها الرسومي. المصدر: F. Zapata.

تمارين

- التمرين 1 (طريقة الرسم)

يعتمد ربح G لشركة معينة على المبلغ المباع للمنتج X والمبلغ المباع للمنتج Y ، بالإضافة إلى أن الربح يتحدد بالصيغة التالية:

ع = 2 (س - 2) ² + 3 (ص - 3) ²

من المعروف أن المقدار X و Y لهما القيود التالية:

X≥0 ؛ Y≥0 و X + Y ≤ 7

حدد قيم X و Y التي تنتج أقصى ربح.

الشكل 3. يمكن نمذجة ربح الشركة رياضيًا للعثور على أقصى ربح باستخدام البرمجة غير الخطية. المصدر: Pixabay.

المحلول

في هذه المشكلة ، تكون الوظيفة الموضوعية غير خطية ، في حين أن المتباينات التي تحدد القيود هي. هذه مشكلة برمجة غير خطية.

لحل هذه المشكلة ، سيتم اختيار الطريقة الرسومية.

أولاً ، سيتم تحديد منطقة الحل ، والتي يتم توفيرها من خلال القيود.

مثل X≥0 ؛ Y≥0 ، يجب إيجاد الحل في الربع الأول من المستوى XY ، ولكن نظرًا لأنه يجب أيضًا أن يكون صحيحًا أن X + Y ≤ 7 ، يكون الحل في النصف السفلي من الخط X + Y = 7.

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

من ناحية أخرى ، يمكن أيضًا تمثيل الكسب G في المستوى الديكارتي ، نظرًا لأن معادلته هي معادلة القطع الناقص مع المركز (2،3).

يظهر الشكل البيضاوي في الشكل 1 لقيم مختلفة لـ G. وكلما زادت قيمة G ، زاد الكسب.

هناك حلول تنتمي إلى المنطقة ، ولكنها لا تعطي قيمة G القصوى ، بينما توجد حلول أخرى ، مثل G = 92.4 ، خارج المنطقة الخضراء ، أي منطقة الحل.

بعد ذلك ، تتوافق القيمة القصوى لـ G ، بحيث تنتمي X و Y إلى منطقة الحل مع:

G = 77 (أقصى ربح) ، والذي يُعطى لـ X = 7 و Y = 0.

ومن المثير للاهتمام ، أن الحد الأقصى للربح يحدث عندما تكون كمية مبيعات المنتج Y صفرًا ، بينما يصل مبلغ المنتج X إلى أعلى قيمة ممكنة.

- التمرين 2 (الطريقة التحليلية: مضاعفات لاغرانج)

أوجد الحل (x، y) الذي يجعل الدالة f (x، y) = x ² + 2y ² كحد أقصى في المنطقة g (x، y) = x ² + y ^2-1 = 0.

المحلول

من الواضح أنها مشكلة برمجة غير خطية ، نظرًا لأن كلا من الوظيفة الموضوعية f (x ، y) والقيود g (x ، y) = 0 ، ليست مجموعة خطية من المتغيرات x و y.

سيتم استخدام طريقة مضاعفات لاجرانج ، والتي تتطلب أولاً تحديد دالة لاجرانج L (س ، ص ، λ):

L (x، y، λ) = f (x، y) - λ g (x، y) = x ² + 2y ² - (x ² + y ^2-1)

حيث λ هي معلمة تسمى مضاعف لاغرانج.

لتحديد القيم القصوى للدالة الموضوعية f ، في منطقة الحل المحددة بواسطة التقييد g (x، y) = 0 ، اتبع الخطوات التالية:

- أوجد المشتقات الجزئية لدالة لاغرانج L ، بالنسبة إلى x ، y ، λ.

- معادلة كل مشتق إلى الصفر.

وهنا تسلسل هذه العمليات:

1. ∂L / ∂x = 2x - 2λx = 0
2. ∂L / ∂y = 4y - 2λy = 0
3. ∂L / ∂λ = - (س ² + ص ^2-1) = 0

حلول النظام الممكنة

الحل المحتمل لهذا النظام هو λ = 1 بحيث يتم استيفاء المعادلة الأولى ، وفي هذه الحالة y = 0 بحيث يتم استيفاء المعادلة الثانية.

هذا الحل يعني أن x = 1 أو x = -1 ليتم استيفاء المعادلة الثالثة. بهذه الطريقة ، تم الحصول على حلين S1 و S2:

S1: (س = 1 ، ص = 0)

S2: (س = -1 ، ص = 0).

البديل الآخر هو أن λ = 2 بحيث تتحقق المعادلة الثانية ، بغض النظر عن قيمة y.

في هذه الحالة ، الطريقة الوحيدة لاستيفاء المعادلة الأولى هي x = 0. بالنظر إلى المعادلة الثالثة ، هناك حلان محتملان فقط ، سنسميهما S3 و S4:

S3: (س = 0 ، ص = 1)

S4: (س = 0 ، ص = -1)

لمعرفة أي من هذه الحلول يزيد من الوظيفة الهدف أو أي منها ، ننتقل إلى التعويض في f (x ، y):

S1: f (1، 0) = 1 ² + 2.0 ² = 1

S2: f (-1 ، 0) = (-1) ² + 2.0 ² = 1

S3: و (0 ، 1) = 0 ² + 2.1 ² = 2

S4: f (0، -1) = 0 ² + 2 (-1) ² = 2

نستنتج أن الحلول التي تزيد من قيمة f ، عندما تنتمي x و y إلى المحيط g (x ، y) = 0 هي S3 و S4.

أزواج القيم (x = 0 ، y = 1) و (x = 0 ، y = -1) تعظم f (x ، y) في منطقة الحل g (x ، y) = 0.

- التمرين 3 (تدرج لاغي)

ابحث عن حلول (س ، ص) لوظيفة الهدف:

و (س ، ص) = س ² + 2 ص ²

يجب أن يكون الحد الأقصى في المنطقة g (x، y) = x ² + y ^2-1 ≤ 0

المحلول

يشبه هذا التمرين التمرين 2 ، لكن منطقة الحل (أو التقييد) تمتد إلى المنطقة الداخلية للمحيط g (x ، y) = 0 ، أي للدائرة g (x ، y) ≤ 0. وهذا يشمل للمحيط والمنطقة الداخلية.

تم بالفعل تحديد الحل على الحدود في التمرين 2 ، لكن المنطقة الداخلية لا تزال بحاجة إلى استكشاف.

للقيام بذلك ، يجب حساب التدرج اللوني للدالة f (x ، y) وضبطه مساويًا للصفر ، لإيجاد القيم القصوى في منطقة الحل. هذا يعادل حساب المشتقات الجزئية لـ f بالنسبة إلى x و y على التوالي وجعلها تساوي صفرًا:

∂f / ∂x = 2 x = 0

∂f / y = 4 ص = 0

نظام المعادلات هذا له الحل الوحيد (x = 0، y = 0) الذي ينتمي إلى الدائرة g (x، y) ≤ 0.

استبدال هذه القيمة في نتائج الدالة f:

و (0 ، 0) = 0

في الختام ، القيمة القصوى التي تأخذها الوظيفة في منطقة الحل هي 2 وتحدث عند حدود منطقة الحل ، للقيم (x = 0 ، y = 1) و (x = 0 ، y = -1).

المراجع

1. Avriel، M. 2003. البرمجة غير الخطية. دوفر للنشر.
2. بازرعة. 1979. البرمجة غير الخطية. جون وايلي وأولاده.
3. Bertsekas، D. 1999. البرمجة غير الخطية: الطبعة الثانية. أثينا العلمية.
4. Nocedal، J. 1999. التحسين العددي. Springer-Verlag.
5. ويكيبيديا. البرمجة غير الخطية. تم الاسترجاع من: es.wikipedia.com