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

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

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

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

Непрерывная задача оптимизации

Стандартная форма непрерывной задачи оптимизации — ^[1], где ${\begin{align}&{\underset {x}{\operatorname {minimize} }}&&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{align}}$

$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)$ — это множество допустимых решений;
Для заданного примера $x$ $и$ допустимого решения $y$ для $x$ $m (x, y)$ обозначает меру y , которая обычно является положительным действительным числом .
$g$ — целевая функция, которая может быть либо $min$ , либо $max$ .

Цель состоит в том, чтобы найти для некоторого экземпляра $x$ оптимальное решение , то есть допустимое решение $y$ с $m(x,y)=g\left\{m(x,y'):y'\in f(x)\right\}.$

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

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

Смотрите также

Задача подсчета (сложность) – Тип вычислительной задачи
Оптимизация дизайна
Вариационный принцип Экленда – теорема, утверждающая, что существуют почти оптимальные решения некоторых задач оптимизации.
Функциональная задача – Тип вычислительной задачи
Проблема с перчатками
Исследование операций – дисциплина, касающаяся применения передовых аналитических методов.
Удовлетворение – когнитивная эвристика поиска приемлемого решения – не обязательно находить оптимальное, достаточно найти «достаточно хорошее» решение.
Задача поиска – тип вычислительной задачи, представленной бинарным отношением.
Полубесконечное программирование – задача оптимизации с конечным числом переменных и бесконечным числом ограничений или бесконечным числом переменных и конечным числом ограничений.

Ссылки

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

Внешние ссылки

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