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

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

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

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

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

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

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

при условии

${displaystyle 1leq xleq 10}$

и

${displaystyle 5leq yleq 12.,}$

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

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

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

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

Смотрите также: Выпуклая оптимизация

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

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

Нет возможного набора

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

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

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

Возможные наборы могут быть ограниченный или неограниченный. Например, допустимый набор, определенный набором ограничений {Икс ≥ 0, у ≥ 0} неограничен, потому что в некоторых направлениях нет ограничений на то, как далеко можно зайти и при этом оставаться в допустимой области. Напротив, допустимый набор, образованный набором ограничений {Икс ≥ 0, у ≥ 0, Икс + 2у ≤ 4} ограничено, потому что степень движения в любом направлении ограничена ограничениями.

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

Если допустимый набор не ограничен, оптимум может быть или не быть, в зависимости от специфики целевой функции. Например, если допустимая область определяется набором ограничений {Икс ≥ 0, у ≥ 0}, то проблема максимизации Икс + у не имеет оптимума, так как любое возможное решение может быть улучшено путем увеличения Икс или же у; но если проблема в свести к минимуму Икс + у, то есть оптимум (а именно при (Икс, у) = (0, 0)).

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

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

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

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

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

Исчисление

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

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

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

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

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

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

1. Бивис, Брайан; Доббс, Ян (1990). Теория оптимизации и устойчивости для экономического анализа. Нью-Йорк: Издательство Кембриджского университета. п. 32. ISBN  0-521-33605-8.
2. Уитли, Даррелл (1994). «Учебник по генетическому алгоритму» (PDF). Статистика и вычисления. 4 (2): 65–85. Дои:10.1007 / BF00175354.