Область допустимых решений
В теории оптимизации допустимая область, допустимое множество, пространство поиска или пространство решений — это множество всех возможных точек (значений переменных) задачи оптимизации, которые удовлетворяют ограничениям задачи. Эти ограничения могут включать неравенства, равенства и требование целочисленности решения . Область допустимых решений является начальной областью поиска кандидатов в решение задачи, и эта область во время поиска может сужаться.
Например, возьмём задачу
Минимизировать x 1 2 + x 2 4 {displaystyle x_{1}^{2}+x_{2}^{4}}с ограничениями на переменные x 1 {displaystyle x_{1}} и x 2 {displaystyle x_{2}}
1 ≤ x 1 ≤ 10 {displaystyle 1leq x_{1}leq 10}и
5 ≤ x 2 ≤ 12. {displaystyle 5leq x_{2}leq 12.}В этом случае область допустимых решений представляет собой множество пар (x1, x2), для которых значение x1 не меньше 1 и не больше 10, а значение x2 не меньше 5 и не больше 12. Заметим, что множество допустимых решений рассматривается отдельно от целевой функции, которая определяет критерий оптимизации и которая в вышеприведённом примере равна x 1 2 + x 2 4 . {displaystyle x_{1}^{2}+x_{2}^{4}.}
Во многих задачах допустимая область решений включает ограничение, по которому одна и более переменных должны быть неотрицательными. В задачах чисто целочисленного программирования множество допустимых решений состоит из целых чисел (или некоторого подмножества). В задачах линейного программирования область допустимых решений является выпуклым политопом — областью в многомерном пространстве, границы которого образованы гиперплоскостями.
Удовлетворение ограничений — это процесс поиска точки в области допустимых решений.
Связанные определения
При ограничениях в виде неравенств точка может быть либо внутренней точкой (допустимой точкой), либо граничной точкой (допустимой точкой), либо внешней точкой (недопустимой точкой). Активным, или связывающим, ограничением называется такое, которое в данной точке превращается в равенство. Некоторые алгоритмы могут использовать понятие активного ограничения для построения более эффективного алгоритма (см. метод переменного базиса.
Если для задачи не существует допустимой точки, задача называется недопустимой.
Условный оптимум представляет собой локальный оптимум, лежащий на границе допустимой области.
Выпуклая область допустимых решений
Выпуклая область допустимых решений — это множество решений, в котором отрезок, соединяющий два допустимых решения, содержит только допустимые точки и не проходит через какую-либо недопустимую точку. Выпуклое множество допустимых решений возникает во многих типах задач, включая задачи линейного программирования, и представляют определённый интерес, поскольку, если задача заключается в оптимизации выпуклой целевой функции, в общем случае такую задачу проще решить на выпуклом множестве решений, и любой локальный оптимум будет также глобальным оптимумом.
Отсутствие допустимых решений
Если ограничения задачи оптимизации совместно противоречивы, не существует точки, которая бы удовлетворяла всем ограничениям, а тогда область допустимых решений пуста. В этом случае задача не имеет решений и говорят, что она недопустима.
Ограниченные и неограниченные области допустимых решений
Множество допустимых решений может быть ограниченным или неограниченным. Например, множество допустимых решений, определяемое ограничениями {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)).
