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

📅 آخر تحديث: ٢ أغسطس ٢٠٢٦
✍️ نُشر في: ٢ أغسطس ٢٠٢٦
📷 يحتوي على 7 صور
الموسوعة الحرة

في الرياضيات ، تُعرف البرمجة غير الخطية ( NLP )، أو التحسين غير الخطي [ 1 ] ، بأنها عملية حل مسائل التحسين التي لا تكون فيها بعض القيود معادلات خطية ، أو تكون فيها دالة الهدف غير خطية . وتتمثل مسألة التحسين في حساب القيم القصوى (العظمى، والصغرى، أو النقاط الثابتة) لدالة الهدف على مجموعة من المتغيرات الحقيقية المجهولة ، وذلك بشرط استيفاء نظام من المعادلات والمتباينات ، والتي تُسمى مجتمعةً بالقيود . وهي فرع من فروع التحسين الرياضي يُعنى بالمسائل غير الخطية.

التعريف والمناقشة

ليكن n و m و p أعدادًا صحيحة موجبة. ولتكن X مجموعة جزئية من R n (عادةً ما تكون مجموعة مقيدة بصندوق)، ولتكن f و g i و h j دوالًا حقيقية القيمة على X لكل i في { 1 ، ...، m } ولكل j في { 1 ، ...، p }، مع كون واحدة على الأقل من f و g i و h j غير خطية.

تُعدّ مسألة البرمجة غير الخطية مسألة تحسين من الشكل التالي:

تقليل و(x)رهناً بـ زأنا(x)≤0 لكل أنا∈{1،...،م}حج(x)=0 لكل ج∈{1،...،ص}x∈X.{\displaystyle {\begin{aligned}{\text{تقليل }}&f(x)\\{\text{بشرط }}&g_{i}(x)\leq 0{\text{ لكل }}i\in \{1,\dotsc ,m\}\\&h_{j}(x)=0{\text{ لكل }}j\in \{1,\dotsc ,p\}\\&x\in X.\end{aligned}}}

توجد عدة احتمالات تبعاً لمجموعة القيود:

  • المشكلة الممكنة هي تلك التي يوجد لها على الأقل مجموعة واحدة من القيم لمتغيرات الاختيار التي تفي بجميع القيود.
  • المسألة غير القابلة للحل هي تلك التي لا يوجد فيها مجموعة من قيم متغيرات الاختيار التي تحقق جميع القيود. أي أن القيود متناقضة فيما بينها، ولا يوجد حل؛ ومجموعة الحلول الممكنة هي المجموعة الفارغة .
  • المسألة غير المحدودة هي مسألة قابلة للحل، حيث يمكن تحسين دالة الهدف بحيث تكون أفضل من أي قيمة محدودة معطاة. وبالتالي، لا يوجد حل أمثل، لأنه يوجد دائمًا حل قابل للحل يحقق قيمة أفضل لدالة الهدف من أي حل مقترح.

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

توجد بعض الحالات الخاصة للبرمجة غير الخطية التي لها طرق حل متخصصة:

قابلية التطبيق

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

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

طرق لحل برنامج غير خطي عام

الأساليب التحليلية

في ظل قابلية التفاضل وشروط القيد ، توفر شروط كاروش-كون-تاكر (KKT) الشروط اللازمة ليكون الحل أمثل. إذا كانت بعض الدوال غير قابلة للتفاضل، تتوفر صيغ تفاضلية جزئية لشروط كاروش-كون-تاكر (KKT) . [ 2 ]

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

الأساليب العددية

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

  • إجراءات الرتبة الصفرية - تستخدم فقط قيم دالة الهدف ودوال القيود عند النقطة الحالية؛
  • إجراءات الرتبة الأولى - استخدم أيضًا قيم تدرجات هذه الدوال؛
  • الروتينات من الدرجة الثانية - استخدم أيضًا قيم مصفوفات هيسيان لهذه الدوال.

من الناحية النظرية، فإن إجراءات الدرجة الثالثة (وما فوقها) ممكنة، ولكنها لا تستخدم عمليًا، نظرًا لارتفاع الحمل الحسابي وقلة الفائدة النظرية.

متفرع ومحدود

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

التطبيقات

توجد العديد من برامج حل البرمجة غير الخطية، بما في ذلك البرامج مفتوحة المصدر:

  • تُنفذ مكتبة ALGLIB (واجهة برمجة تطبيقات C++، C#، Java، Python) العديد من حلول البرمجة غير الخطية من الدرجة الأولى والخالية من المشتقات
  • يتضمن NLopt (تنفيذ بلغة C/C++، مع العديد من الواجهات بما في ذلك Julia وPython وR وMATLAB/Octave)، العديد من حلول البرمجة غير الخطية
  • يحتوي SciPy (المعيار الفعلي لـ Python العلمي) على محلل scipy.optimize، والذي يتضمن العديد من خوارزميات البرمجة غير الخطية (من الدرجة الصفرية والدرجة الأولى والدرجة الثانية).
  • IPOPT (تنفيذ C++، مع العديد من الواجهات بما في ذلك C و Fortran و Java و AMPL و R و Python وما إلى ذلك) هو حل طريقة النقطة الداخلية (الرتبة الصفرية، واختياريًا الرتبة الأولى والثانية المشتقة).

تتضمن الحلول الخاصة SNOPT (المكتوبة بلغة Fortran، مع واجهات لـ C و C++ و Python و MATLAB).

أمثلة عددية

مثال ثنائي الأبعاد

المنطقة الزرقاء هي المنطقة الممكنة . يمثل تماس الخط مع المنطقة الممكنة الحل. هذا الخط هو أفضل خط كفاف يمكن تحقيقه (موضع ذو قيمة معينة لدالة الهدف).

يمكن تعريف مشكلة بسيطة (موضحة في الرسم التخطيطي) من خلال القيود x1≥0x2≥0x12+x22≥1x12+x22≤2{\displaystyle {\begin{aligned}x_{1}&\geq 0\\x_{2}&\geq 0\\x_{1}^{2}+x_{2}^{2}&\geq 1\\x_{1}^{2}+x_{2}^{2}&\leq 2\end{aligned}}} بهدف تحقيق أقصى قيمة ممكنة لدالة الهدف. و(x)=x1+x2{\displaystyle f(\mathbf {x} )=x_{1}+x_{2}} حيث x = ( x 1 , x 2 ) .

مثال ثلاثي الأبعاد

يمثل التماس بين السطح العلوي والفضاء المقيد في المركز الحل.

يمكن تعريف مشكلة بسيطة أخرى (انظر الرسم التوضيحي) من خلال القيود x12-x22+x32≤2x12+x22+x32≤10{\displaystyle {\begin{aligned}x_{1}^{2}-x_{2}^{2}+x_{3}^{2}&\leq 2\\x_{1}^{2}+x_{2}^{2}+x_{3}^{2}&\leq 10\end{aligned}}} بهدف تحقيق أقصى قيمة ممكنة لدالة الهدف. و(x)=x1x2+x2x3{\displaystyle f(\mathbf {x} )=x_{1}x_{2}+x_{2}x_{3}} حيث x = ( x 1 , x 2 , x 3 ) .

انظر أيضاً

مراجع

  1. ↑ ريتشارد دبليو. كوتل، موكوند ن. ثابا. التحسين الخطي وغير الخطي. سبرينغر نيويورك، 2017. https://www.springerprofessional.de/linear-and-nonlinear-optimization/12354648
  2. ↑ روسزتشينسكي، أندريه (2006). التحسين غير الخطي . برينستون، نيوجيرسي: مطبعة جامعة برينستون . الصفحات: xii+454. ISBN  978-0691119151MR 2199043 .​ 
  3. 1 2 نيميروفسكي وبن-تال (2023). "التحسين الثالث: التحسين المحدب" (PDF) .

للمزيد من القراءة

  • أفرييل، موردخاي (2003). البرمجة غير الخطية: التحليل والأساليب. دار نشر دوفر. ISBN 0-486-43227-0.
  • بازارا، مختار س. وشيتي، سي إم (1979). البرمجة غير الخطية: النظرية والخوارزميات. جون وايلي وأولاده. ISBN 0-471-78610-1.
  • بونان، ج.  فريدريك؛ جيلبرت، ج.  تشارلز؛ ليمارشال، كلود ؛ ساغاستيزابال، كلوديا  أ. (2006). التحسين العددي: الجوانب النظرية والعملية . Universitext (الطبعة الثانية المنقحة من ترجمة  الطبعة الفرنسية لعام 1997). برلين: Springer-Verlag. الصفحات:  xiv+490. doi : 10.1007/978-3-540-35447-5 . ISBN 3-540-35445-XMR 2265882 .​ 
  • لونبرغر، ديفيد ج .؛ يي، يينيو (2008). البرمجة الخطية وغير الخطية . السلسلة الدولية في بحوث العمليات وعلوم الإدارة. المجلد  116 (  الطبعة الثالثة). نيويورك: سبرينغر. الصفحات:  546+14. ISBN 978-0-387-74502-2MR 2423726 .​ 
  • نوسيدال، خورخي ورايت، ستيفن ج. (1999). التحسين العددي. سبرينغر. ISBN 0-387-98793-2.
  • يان برينكهاوس وفلاديمير تيخوميروف، التحسين: رؤى وتطبيقات ، 2005، مطبعة جامعة برينستون