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

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

Использует

Многие первично-дуальные аппроксимационные алгоритмы основаны на принципе слабой двойственности.^[2]

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

В первобытный проблема:

Максимизировать c^ТИкс при условии А Икс ≤ б, Икс ≥ 0;

В двойной проблема,

Свести к минимуму б^Ту при условии А^Ту ≥ c, у ≥ 0.

Теорема слабой двойственности утверждает c^ТИкс ≤ б^Ту.

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

Доказательство:c^ТИкс = Икс^Тc≤ Икс^ТА^Ту≤ б^Ту

Обобщения

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

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

• Выпуклая оптимизация

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