التحسين المقيد

في المسائل البسيطة جدًا، كدالة لمتغيرين تخضع لشرط مساواة واحد، يكون من الأنسب تطبيق طريقة التعويض. ^{[ 4 ]} وتتلخص الفكرة في استبدال الشرط في دالة الهدف لإنشاء دالة مركبة تتضمن تأثير الشرط. على سبيل المثال، لنفترض أن الهدف هو تعظيم${\displaystyle f(x,y)=x\cdot y}$رهناً بـ${\displaystyle x+y=10}$القيد يستلزم${\displaystyle y=10-x}$والتي يمكن استبدالها في دالة الهدف لإنشاء${\displaystyle p(x)=x(10-x)=10x-x^{2}}$. الشرط الضروري من الدرجة الأولى يعطي${\displaystyle {\frac {\partial p}{\partial x}}=10-2x=0}$والتي يمكن حلها لـ${\displaystyle x=5}$وبالتالي،${\displaystyle y=10-5=5}$.

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

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

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

إذا كانت جميع القيود الصارمة خطية وبعضها متباينات، ولكن دالة الهدف تربيعية، فإن المسألة تُصنف ضمن مسائل البرمجة التربيعية . وهي نوع من أنواع البرمجة غير الخطية. ويمكن حلها في وقت متعدد الحدود باستخدام طريقة القطع الناقص إذا كانت دالة الهدف محدبة ؛ وإلا فقد تكون المسألة صعبة الحل (NP-hard ).

يُعمم منهج كاروش-كون-تاكر (KKT) للبرمجة غير الخطية ، الذي يسمح بقيود المتباينات، طريقة مُضاعفات لاغرانج. ويمكن تطبيقه في ظل قابلية التفاضل والتحدب.

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

بافتراض أن الهدف هو تقليل التكلفة، فإن كفاءة هذه الخوارزميات تعتمد على كيفية تقييم التكلفة التي يمكن الحصول عليها من توسيع حل جزئي. في الواقع، إذا كان بإمكان الخوارزمية التراجع عن حل جزئي، فسيتم تخطي جزء من البحث. كلما انخفضت التكلفة المُقدَّرة، كانت الخوارزمية أفضل، لأن التكلفة المُقدَّرة المنخفضة من المرجح أن تكون أقل من أفضل تكلفة للحل الذي تم التوصل إليه حتى الآن.

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

يستخدم أحد أشكال هذا النهج المسمى طريقة هانسن أساليب الفترات . ^{[ 5 ]} وهي تطبق بشكل أساسي القيود المستطيلة.

إحدى طرق تقييم هذا الحد الأعلى لحل جزئي هي النظر في كل قيد مرن على حدة. لكل قيد مرن، يُفترض أن تكون القيمة القصوى الممكنة لأي قيمة مُسندة للمتغيرات غير المُسندة هي القيمة القصوى. مجموع هذه القيم هو حد أعلى لأن القيود المرنة لا يمكن أن تأخذ قيمة أعلى. وهو حد دقيق لأن القيم القصوى للقيود المرنة قد تُستنتج من تقييمات مختلفة: قد يكون القيد المرن أقصى لـ${\displaystyle x=a}$بينما يكون القيد الآخر أقصى بالنسبة لـ${\displaystyle x=b}$.

يمكن تكييف خوارزمية حذف المجموعات لتحسين القيود. يمكن بالفعل إزالة متغير معين من المسألة عن طريق استبدال جميع القيود المرنة التي تحتوي عليه بقيد مرن جديد. يتم حساب تكلفة هذا القيد الجديد بافتراض قيمة قصوى لكل قيمة للمتغير المحذوف. رسميًا، إذا${\displaystyle x}$المتغير المراد إزالته،${\displaystyle C_{1},\ldots ,C_{n}}$هي القيود المرنة التي تحتويها، و${\displaystyle y_{1},\ldots ,y_{m}}$هي متغيراتهم باستثناء${\displaystyle x}$، يتم تعريف القيد المرن الجديد على النحو التالي:

${\displaystyle C(y_{1}=a_{1},\ldots ,y_{n}=a_{n})=\max _{a}\sum _{i}C_{i}(x=a,y_{1}=a_{1},\ldots ,y_{n}=a_{n}).}$

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