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

Проблема поиска наилучшего возможного решения

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

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

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

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

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

$${\displaystyle {\begin{aligned}&{\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{aligned}}}$$

• f  : ℝ n → ℝ — целевая функция , которую необходимо минимизировать по вектору n -переменных x ,
• g _i ( x ) ≤ 0 называются ограничениями -неравенствами.
• h _j ( x ) = 0 называются ограничениями равенства , а
• м ≥ 0 и р ≥ 0 .

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

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

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

• Я — набор экземпляров;
• для данного экземпляра x ∈ I f ( x ) — множество допустимых решений ;
• учитывая экземпляр x и допустимое решение y x , m ( x , y ) обозначает меру y , которая обычно является положительным действительным числом .
• g — целевая функция, равная min или max .

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

$${\displaystyle m(x,y)=g\left\{m(x,y'):y'\in f(x)\right\}.}$$

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

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

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

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

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

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

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

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