Возможная область

редактировать

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

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

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

Например, рассмотрим задачу

Minimize

x 2 + y 4 {\ displaystyle x ^ {2} + y ^ {4}}

{\ displaystyle x ^ {2} + y ^ {4}}

относительно переменных $x {\ displaystyle x}$ $x$ и $y, {\ displaystyle y,}$ $y,$

при условии

1 ≤ x ≤ 10 {\ displaystyle 1 \ leq x \ leq 10 }

{\ displaystyle 1 \ leq x \ leq 10}

5 ≤ y ≤ 12. {\ displaystyle 5 \ leq y \ leq 12. \,}

{ \ displaystyle 5 \ leq y \ leq 12. \,}

Здесь допустимый набор - это набор пар (x, y), в которых значение x составляет не менее 1 и не более 10, а значение y - от 5 до 12. Обратите внимание, что возможный набор задачи отделен от целевой функции , которая устанавливает критерий как оптимизированный и который в приведенном выше примере равен $x 2 + y 4. {\ displaystyle x ^ {2} + y ^ {4}.}$ ${\ displaystyle x ^ {2} + y ^ {4}.}$

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

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

Содержание

1 Выпуклый допустимый набор
2 Нет допустимого набора
3 Ограниченные и неограниченные допустимые множества
4 Возможное решение
- 4.1 Генетический алгоритм
- 4.2 Исчисление
- 4.3 Линейное программирование
5 Ссылки

Выпуклый допустимый набор

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

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

Нет допустимого набора

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

Ограниченные и неограниченные допустимые множества

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

Возможные наборы могут быть ограниченными или неограниченными. Например, допустимое множество, определенное набором ограничений {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)).

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

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

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

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

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

Исчисление

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

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

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

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

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

Ссылки