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

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

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

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

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

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

Возможное решение

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

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

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

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

Исчисление

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

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

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

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

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

Рекомендации