Задача оптимизации

редактировать

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

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

Содержание

  • 1 Задача непрерывной оптимизации
  • 2 Задача комбинаторной оптимизации
  • 3 См. Также
  • 4 Ссылки
  • 5 Внешние ссылки

Задача непрерывной оптимизации

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

минимизировать xf (x) subjecttogi (x) ≤ 0, i = 1,…, mhj (x) = 0, j = 1,…, p {\ displaystyle {\ begin {выровнено} {\ underset {x} {\ operatorname {Minimum}}} f (x) \\ \ имя оператора {subject \; to} g_ {i} (x) \ leq 0, \ quad i = 1, \ dots, m \\ h_ {j} (x) = 0, \ quad j = 1, \ dots, p \ end {align}}}{\ 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 {align}}}

где

  • f: - это целевая функция, которая должна быть минимизирована по вектору x n переменных,
  • gi( x) ≤ 0 называются неравенством ограничениями
  • hj(x) = 0 называются ограничениями равенства, а
  • m ≥ 0 и p ≥ 0.

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

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

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

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

m (x, y) = g {m (x, y ′) ∣ y ′ ∈ f (x)}. {\ displaystyle m (x, y) = g {\ bigl \ {} m (x, y ') \ mid y' \ in f (x) {\ bigr \}}.}{\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 или меньше ребер?» На эту проблему можно ответить простым «да» или «нет».

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

См. Также

Ссылки

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

Последняя правка сделана 2021-06-01 13:36:21
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте