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

Эта статья в значительной степени или полностью основана на одном источнике . Соответствующее обсуждение можно найти на странице обсуждения . Пожалуйста, помогите улучшить эту статью , добавив ссылки на дополнительные источники. Источники:  «Возможный регион»  -  новости  · газеты  · книги  · ученый  · JSTOR ( ноябрь 2018 г. )

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

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

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

Например, рассмотрим проблему

Свести к минимуму ${\ displaystyle x ^ {2} + y ^ {4}}$

по переменным и${\ displaystyle x}$${\ displaystyle y,}$

при условии

${\ Displaystyle 1 \ Leq х \ Leq 10}$

и

${\ Displaystyle 5 \ Leq Y \ Leq 12. \,}$

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

Возможное решение [ править ]

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

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

Генетический алгоритм [ править ]

В случае генетического алгоритма возможные решения - это особи в популяции, развиваемые алгоритмом. ^[2]

Исчисление [ править ]

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

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

Линейное программирование [ править ]

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

Ссылки [ править ]