В теории оптимизации допустимая область , допустимое множество , пространство поиска или пространство решений — это множество всех возможных точек (значений переменных) задачи оптимизации, которые удовлетворяют задачи. Эти ограничения могут включать неравенства , равенства и требование целочисленности решения . Область допустимых решений является начальной областью поиска кандидатов в решение задачи, и эта область во время поиска может сужаться.

Например, возьмём задачу

Минимизировать ${\displaystyle x_{1}^{2}+x_{2}^{4}}$

с ограничениями на переменные ${\displaystyle x_{1}}$ и ${\displaystyle x_{2}}$

${\displaystyle 1\leq x_{1}\leq 10}$

и

${\displaystyle 5\leq x_{2}\leq 12.}$

В этом случае область допустимых решений представляет собой множество пар ( x ₁ , x ₂ ), для которых значение x ₁ не меньше 1 и не больше 10, а значение x ₂ не меньше 5 и не больше 12. Заметим, что множество допустимых решений рассматривается отдельно от целевой функции, которая определяет критерий оптимизации и которая в вышеприведённом примере равна ${\displaystyle x_{1}^{2}+x_{2}^{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)).