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

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

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

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

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

Стандартная форма из непрерывной задачи оптимизации является ^[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]