Feasible region

In mathematical optimization and computer science, a feasible region,feasible set, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, potentially including inequalities, equalities, and integer constraints.^[1] This is the initial set of candidate solutions to the problem, before the set of candidates has been narrowed down.

For example, consider the problem of minimizing the function ${\displaystyle x^{2}+y^{4}}$ with respect to the variables ${\displaystyle x}$ and ${\displaystyle y,}$ subject to ${\displaystyle 1\leq x\leq 10}$ and ${\displaystyle 5\leq y\leq 12.\,}$ Here the feasible set is the set of pairs (x, y) in which the value of x is at least 1 and at most 10 and the value of y is at least 5 and at most 12. The feasible set of the problem is separate from the objective function, which states the criterion to be optimized and which in the above example is ${\displaystyle x^{2}+y^{4}.}$

In many problems, the feasible set reflects a constraint that one or more variables must be non-negative. In pure integer programming problems, the feasible set is the set of integers (or some subset thereof). In linear programming problems, the feasible set is a convexpolytope: a region in multidimensional space whose boundaries are formed by hyperplanes and whose corners are vertices.

Constraint satisfaction is the process of finding a point in the feasible region.

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

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

قد تكون المجموعات الممكنة محدودة أو غير محدودة . على سبيل المثال، المجموعة الممكنة المحددة بمجموعة القيود { 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 ]} وهي مجموعة جميع الحلول الممكنة التي تُحقق قيود المسألة. وتحقيق القيود هو عملية إيجاد نقطة في مجموعة الحلول الممكنة.

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

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