В прикладной математике, слабая двойственность - это концепция в оптимизации, которая утверждает, что разрыв двойственности всегда больше или равен 0. Это означает решение основной (минимизационной) проблемы. всегда больше или равно решению связанной двойной задачи. Это противоположно сильной двойственности, которая имеет место только в определенных случаях.
Многие алгоритмы первично-дуального приближения основаны на принципе слабой двойственности.
Основная проблема :
Двойная задача,
Теорема слабой двойственности утверждает cx≤ by.
А именно, если - допустимое решение для простой программы максимизации линейной программы и является допустимым решением для линейной программы двойной минимизации, тогда теорема слабой двойственности может быть сформулирована как , где и - это коэффициенты соответствующих целевых функций.
Доказательство: cx= xc≤ xAy≤ by
В более общем смысле, если является допустимым решением для основной задачи максимизации и является допустимым решением проблемы двойной минимизации, тогда слабая двойственность подразумевает где и - целевые функции для основной и двойственной задач. соответственно.