Область допустимых решений

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

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

Замкнутая область допустимых решений задачи линейного программирования с тремя переменными является выпуклым многогранником.

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

Минимизировать ${\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}.}$

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

Удовлетворение ограничений — это процесс поиска точки в области допустимых решений.

Связанные определения

При ограничениях в виде неравенств точка может быть либо внутренней точкой (допустимой точкой), либо граничной точкой (допустимой точкой), либо внешней точкой (недопустимой точкой). Активным, или связывающим, ограничением называется такое, которое в данной точке превращается в равенство^[1]. Некоторые алгоритмы могут использовать понятие активного ограничения для построения более эффективного алгоритма (см. метод переменного базиса.

Если для задачи не существует допустимой точки, задача называется недопустимой.

Условный оптимум представляет собой локальный оптимум, лежащий на границе допустимой области^[1].

Выпуклая область допустимых решений

См. также: Выпуклое программирование

В задаче линейного программирования набор линейных ограничений образует выпуклую область допустимых решений. Для двух переменных эта область имеет форму выпуклого многоугольника.

Выпуклая область допустимых решений — это множество решений, в котором отрезок, соединяющий два допустимых решения, содержит только допустимые точки и не проходит через какую-либо недопустимую точку. Выпуклое множество допустимых решений возникает во многих типах задач, включая задачи линейного программирования, и представляют определённый интерес, поскольку, если задача заключается в оптимизации выпуклой целевой функции, в общем случае такую задачу проще решить на выпуклом множестве решений, и любой локальный оптимум^[англ.] будет также глобальным оптимумом^[англ.].

Отсутствие допустимых решений

Если ограничения задачи оптимизации совместно противоречивы, не существует точки, которая бы удовлетворяла всем ограничениям, а тогда область допустимых решений пуста. В этом случае задача не имеет решений и говорят, что она недопустима^[1].

Ограниченные и неограниченные области допустимых решений

Ограниченная область допустимых решений (сверху) и неограниченная (снизу). Нижняя область распространяется направо неограниченно.

Множество допустимых решений может быть ограниченным или неограниченным. Например, множество допустимых решений, определяемое ограничениями {x ≥ 0, y ≥ 0}, является неограниченным, поскольку в некоторых направлениях можно идти бесконечно, оставаясь в области допустимых решений. Для контраста множество допустимых решений, образованное ограничениями {x ≥ 0, y ≥ 0, x + 2y ≤ 4}, является ограниченным, поскольку движение в любом направлении ограничено. В задачах линейного программирования с n переменными необходимым, но не достаточным условием ограниченности области допустимых решений является наличие как минимум n + 1 ограничений.

Если множество допустимых решений является неограниченной, оптимальное решение может как существовать, так и не существовать, в зависимости от поведения целевой функции. Например, если множество определено ограничениями {x ≥ 0, y ≥ 0}, то задача оптимизации x + y не имеет решений, поскольку любой кандидат может быть улучшен путём увеличения x или y, а вот задача минимизировать x + y имеет оптимальное решение (а именно, в точке (x, y) = (0, 0)).

1. Д. Химмельблау. Прикладное нелинейное программирование. — Москва: «Мир», 1975. — С. 36.
2. Л.Р. Форд, Д.Р. Фалкерсон. Потоки в сетях. — Москва: «Мир», 1966. — С. 48.