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

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

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

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

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

Минимизировать

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

по отношению к переменным

x{\displaystyle x}

и

y,{\displaystyle y,}

подлежит

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

и

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

Здесь допустимым множеством является множество пар (x, y), в которых значение x равно не менее 1 и не более 10, а значение y равно не менее 5 и не более 12. Заметим , что допустимый набор задач отделен от

целевой функции, которая определяет критерий оптимизации и которая в приведенном выше примере является

x2+y4.{\displaystyle x^{2}+y^{4}.}

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

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

Выпуклое допустимое множество

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

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

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

Нет осуществимого набора

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

неосуществимой.

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

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

Допустимые множества могут быть ограниченными или неограниченными. Например, допустимое множество, определенное набором ограничений {x ≥ 0, yНапротив, допустимое множество, образованное множеством ограничений {x ≥ 0, y ≥ 0, x + 2y

В задачах линейного программирования с n переменными необходимым. Но недостаточным условием ограничения допустимого множества является то. Что число ограничений должно быть не менее

n + 1 (как показано в приведенном выше примере).

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

Кандидатское решение

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

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

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

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

В случае генетического алгоритмакандидатами на решение являются индивиды в популяции . Эволюционирующие с помощью алгоритма[2]

Исчисление

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

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

В-третьих, решение-кандидат может быть локальным оптимумом, но не глобальным.

При взятии антидивативов одночленов вида

xn,{\displaystyle x^{n},}

решение кандидата с использованием квадратурной формулы Кавальери было бы

1n+1xn+1+C.{\displaystyle {\tfrac {1}{n+1}}x^{n+1}+C.}

таким решением кандидата фактически правильным за исключением тех случаев когда

n=1.{\displaystyle n=-1.}

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

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

выпуклого простого многоугольника, если она ограничена. В алгоритме. Который последовательно проверяет допустимые точки. Каждая тестируемая точка. В свою очередь. Является решением-кандидатом.

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