المنطقة الممكنة

في مجال التحسين الرياضي وعلوم الحاسوب ، تُعرف المنطقة الممكنة أو المجموعة الممكنة أو فضاء الحلول بأنها مجموعة جميع النقاط الممكنة (مجموعات قيم متغيرات الاختيار) لمسألة تحسين تُحقق قيود المسألة ، بما في ذلك المتباينات والمعادلات والقيود العددية . ^{[ 1 ]} هذه هي المجموعة الأولية للحلول المرشحة للمسألة، قبل تضييق نطاقها .

على سبيل المثال، لننظر في مشكلة تقليل الدالة${\displaystyle x^{2}+y^{4}}$فيما يتعلق بالمتغيرات${\displaystyle x}$و${\displaystyle y,}$رهناً بـ${\displaystyle 1\leq x\leq 10}$و${\displaystyle 5\leq y\leq 12.\,}$هنا، تُعرَّف المجموعة الممكنة بأنها مجموعة الأزواج ( س ، ص ) التي تكون فيها قيمة س أكبر من أو تساوي 1 وأصغر من أو تساوي 10، وقيمة ص أكبر من أو تساوي 5 وأصغر من أو تساوي 12. وتختلف المجموعة الممكنة للمسألة عن دالة الهدف ، التي تحدد المعيار المراد تحسينه، وهو في المثال أعلاه${\displaystyle x^{2}+y^{4}.}$

في العديد من المسائل، تعكس المجموعة الممكنة قيدًا يقضي بأن يكون متغير واحد أو أكثر غير سالب. في مسائل البرمجة العددية البحتة ، تكون المجموعة الممكنة هي مجموعة الأعداد الصحيحة (أو مجموعة جزئية منها). أما في مسائل البرمجة الخطية ، فتكون المجموعة الممكنة متعدد السطوح محدبًا : منطقة في فضاء متعدد الأبعاد تتكون حدودها من مستويات فائقة، وزواياها هي رؤوس .

إرضاء القيود هو عملية إيجاد نقطة في المنطقة الممكنة.

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

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

قد تكون المجموعات الممكنة محدودة أو غير محدودة . على سبيل المثال، المجموعة الممكنة المحددة بمجموعة القيود { x ≥ 0, y ≥ 0} غير محدودة، لأنه في بعض الاتجاهات لا يوجد حد للمسافة التي يمكن قطعها مع البقاء ضمن المنطقة الممكنة. في المقابل، المجموعة الممكنة المحددة بمجموعة القيود { x ≥ 0, y ≥ 0, x + 2 y ≤ 4} محدودة، لأن مدى الحركة في أي اتجاه محدود بالقيود.

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

إذا كانت مجموعة الحلول الممكنة غير محدودة، فقد يوجد حل أمثل أو لا، وذلك بحسب تفاصيل دالة الهدف. على سبيل المثال، إذا كانت منطقة الحلول الممكنة محددة بمجموعة القيود { x ≥ 0, y ≥ 0}، فإن مسألة تعظيم x + y لا يوجد لها حل أمثل، إذ يمكن تحسين أي حل مرشح بزيادة x أو y ؛ أما إذا كانت المسألة هي تصغير x + y ، فسيكون هناك حل أمثل (وتحديدًا عند ( x , y ) = (0, 0)).

في مجال التحسين وفروع أخرى من الرياضيات ، وفي خوارزميات البحث (وهو موضوع في علوم الحاسوب )، يُعدّ الحل المرشح أحد الحلول الممكنة ضمن نطاق الحلول الممكنة لمسألة معينة. ^{[ 2 ]} لا يشترط أن يكون الحل المرشح حلاً محتملاً أو معقولاً للمسألة ، بل هو ببساطة ضمن المجموعة التي تُحقق جميع القيود ؛ أي أنه يقع ضمن مجموعة الحلول الممكنة . غالبًا ما تُضيّق خوارزميات حلّ أنواع مختلفة من مسائل التحسين نطاق الحلول المرشحة إلى مجموعة فرعية من الحلول الممكنة، حيث تبقى نقاطها كحلول مرشحة بينما تُستبعد الحلول الممكنة الأخرى من قائمة الحلول المرشحة.

تُسمى فضاء جميع الحلول المرشحة، قبل استبعاد أي نقاط ممكنة، بالمنطقة الممكنة، أو مجموعة الحلول الممكنة، أو فضاء البحث، أو فضاء الحلول. ^{[ 2 ]} وهي مجموعة جميع الحلول الممكنة التي تُحقق قيود المسألة. وتحقيق القيود هو عملية إيجاد نقطة في مجموعة الحلول الممكنة.

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

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