Проблема оптимизации

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

Проблемы оптимизации можно разделить на две категории в зависимости от того, являются ли переменные непрерывными или дискретными :

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

Проблема непрерывной оптимизации [ править ]

Стандартная форма из непрерывной задачи оптимизации является ^[1]

{\ displaystyle {\ begin {align} & {\ underset {x} {\ operatorname {minim}}} && f (x) \\ & \ operatorname {subject \; to} && g_ {i} (x) \ leq 0, \ quad i = 1, \ dots, m \\ &&& h_ {j} (x) = 0, \ quad j = 1, \ dots, p \ end {выровнено}}}

куда

$f : ℝ n \to ℝ$ - целевая функция, которую необходимо минимизировать по $n$ -переменному вектору $x$ ,
$g i (x) \leq 0$ называются ограничениями- неравенствами
$h j (x) = 0$ называются ограничениями равенства , а
$m \geq 0$ и $p \geq 0$ .

Если $m = p = 0$ , проблема является задачей неограниченной оптимизации. По соглашению стандартная форма определяет задачу минимизации . Задача максимизации можно лечить с помощью отрицания целевой функции.

Задача комбинаторной оптимизации [ править ]

Формально задача комбинаторной оптимизации $A$ - это четверка ^{[ необходима цитата ]} $(I, f, m, g)$ , где

$I$ - это набор экземпляров;
для случая $x \in I$ , $f (x)$ - множество возможных решений;
дала экземпляр $х$ и допустимое решение $у$ из $х$ , $т (х, у)$ обозначает меру из $Y$ , который обычно является положительным реальным .
$g$ - целевая функция, которая может быть $минимальной$ или $максимальной$ .

Цель состоит в том, чтобы найти то для некоторого экземпляра $х$ в оптимальное решение , то есть, допустимое решение $у$ с

{\ Displaystyle m (x, y) = g {\ bigl \ {} m (x, y ') \ mid y' \ in f (x) {\ bigr \}}.}

Для каждой задачи комбинаторной оптимизации существует соответствующая проблема решения, которая спрашивает, существует ли допустимое решение для некоторой конкретной меры $m 0$ . Например, если существует граф $G,$ содержащий вершины $u$ и $v$ , проблема оптимизации может заключаться в «поиске пути от $u$ к $v,$ который использует наименьшее количество ребер». Эта проблема может иметь ответ, скажем, 4. Соответствующая проблема с решением будет звучать так: «Есть ли путь от $u$ к $v,$ который использует 10 или меньше ребер?» На эту проблему можно ответить простым «да» или «нет».

В области приближенных алгоритмов алгоритмы предназначены для поиска почти оптимальных решений сложных проблем. Тогда обычная версия решения является неадекватным определением проблемы, поскольку она указывает только приемлемые решения. Несмотря на то, что мы могли бы ввести подходящие задачи решения, проблема более естественно характеризуется как проблема оптимизации. ^[2]

См. Также [ править ]

Проблема подсчета (сложность)
Оптимизация дизайна
Функциональная проблема
Проблема с перчаткой
Исследование операций
Удовлетворительно : не нужно искать оптимума, просто «достаточно хорошее» решение.
Проблема поиска
Полубесконечное программирование

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

^ Бойд, Стивен П .; Ванденберге, Ливен (2004). Выпуклая оптимизация (pdf) . Издательство Кембриджского университета. п. 129. ISBN 978-0-521-83378-3.
^ Аузиелло, Джорджио; и другие. (2003), Сложность и приближение (исправленное издание), Springer, ISBN 978-3-540-65431-5

Внешние ссылки [ править ]

«Как формирование трафика оптимизирует пропускную способность сети» . IPC . 12 июля 2016 . Проверено 13 февраля +2017 .

[1] Бойд, Стивен П .; Ванденберге, Ливен (2004). Выпуклая оптимизация (pdf) . Издательство Кембриджского университета. п. 129. ISBN 978-0-521-83378-3.

[Ausiello03-2] Аузиелло, Джорджио; и другие. (2003), Сложность и приближение (исправленное издание), Springer, ISBN 978-3-540-65431-5

[1]