Слабая двойственность

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

В прикладной математике, слабая двойственность - это концепция в оптимизации, которая утверждает, что разрыв двойственности всегда больше или равен 0. Это означает решение основной (минимизационной) проблемы. всегда больше или равно решению связанной двойной задачи. Это противоположно сильной двойственности, которая имеет место только в определенных случаях.

Содержание
  • 1 Использует
  • 2 Теорема слабой двойственности
    • 2.1 Обобщения
  • 3 См. Также
  • 4 Ссылки
Использует

Многие алгоритмы первично-дуального приближения основаны на принципе слабой двойственности.

Теорема слабой двойственности

Основная проблема :

Максимизировать cxпри условии A x≤ b, x≥ 0;

Двойная задача,

Минимизировать byпри условии A y≥ c, y≥ 0.

Теорема слабой двойственности утверждает cx≤ by.

А именно, если (x 1, x 2,..., Xn) {\ displaystyle (x_ {1}, x_ {2},...., x_ {n})}(x_ {1}, x_ {2},...., x_ {n}) - допустимое решение для простой программы максимизации линейной программы и (y 1, y 2,....., Ym) {\ displaystyle (y_ {1}, y_ {2},...., y_ {m})}(y_ {1}, y_ {2},...., y_ {m}) является допустимым решением для линейной программы двойной минимизации, тогда теорема слабой двойственности может быть сформулирована как ∑ j = 1 ncjxj ≤ ∑ i = 1 mbiyi {\ displaystyle \ sum _ {j = 1} ^ {n} c_ {j} x_ {j} \ leq \ sum _ {i = 1} ^ {m} b_ {i} y_ {i}}{\ displaystyle \ sum _ {j = 1} ^ {n} c_ {j} x_ {j} \ leq \ sum _ {i = 1} ^ {m} b_ {i} y_ {i}} , где cj {\ displaystyle c_ {j}}c_ {j} и b i {\ displaystyle b_ {i}}b_i - это коэффициенты соответствующих целевых функций.

Доказательство: cx= xc≤ xAy≤ by

Обобщения

В более общем смысле, если x {\ displaystyle x}x является допустимым решением для основной задачи максимизации и y {\ displaystyle y}y является допустимым решением проблемы двойной минимизации, тогда слабая двойственность подразумевает f (x) ≤ g (y) {\ displaystyle f (x) \ leq g (y)}{ \ displaystyle f (x) \ leq g (y)} где f {\ displaystyle f}fи g {\ displaystyle g}g - целевые функции для основной и двойственной задач. соответственно.

См. Также
Ссылки
Последняя правка сделана 2021-06-20 10:19:31
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте