Возможный регион

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

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

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

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

Вариант решения

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

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

Генетический алгоритм

В случае генетического алгоритма кандидатами на решение являются особи в популяции, развиваемые алгоритмом.

Исчисление

В исчислении оптимальное решение ищется с использованием теста первой производной : первая производная оптимизируемой функции приравнивается к нулю, и любые значения переменных выбора, которые удовлетворяют этому уравнению, рассматриваются как возможные решения (в то время как те, которые не исключаются из числа кандидатов). Существует несколько причин, по которым возможное решение может не оказаться реальным решением. Во-первых, он может дать минимум, когда ищут максимум (или наоборот), а во-вторых, он может дать не минимум и не максимум, а, скорее, седловую точку или точку перегиба , в которой происходит временная пауза в локальном подъеме. или происходит падение функции. Такие возможные решения можно исключить с помощью теста второй производной , удовлетворение которого достаточно для того, чтобы возможное решение было, по крайней мере, локально оптимальным. В-третьих, возможное решение может быть локальным , но не глобальным оптимумом .

При первообразных одночленов вида взятии $x^{n},$ возможным решением с использованием квадратурной формулы Кавальери будет ${\tfrac {1}{n+1}}x^{n+1}+C.$ Это возможное решение на самом деле правильно, за исключением случаев, когда $n=-1.$

Линейное программирование

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

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