Слабка двоїстість
Слабка двоїстість — це концепція в оптимізації, яка стверджує, що розрив двоїстості завжди більший або дорівнює нулю. Це означає, що розв'язок прямої задачі (задачі мінімізації) завжди більший або дорівнює розв'язку пов'язаної двоїстої задачі. Цей термін протиставляється сильній двоїстості, яка виконується лише за певних умов[1].
Використання
ред.Багато прямодвоїстих[2] апроксимаційних алгоритмів засновані на принципі слабкої двоїстості[3].
Теорема про слабку двоїстість
ред.Пряма задача:
- Максимізувати за умови ;
Двоїста задача:
- Мінімізувати за умови .
Теорема про слабку двоїстість стверджує, що .
А саме, що якщо — допустимий розв'язок прямої задачі максимізації лінійного програмування, а — допустимий розв'язок двоїстої задачі мінімізації лінійного програмування, то теорему слабкої двоїстості можна сформулювати так: , де і — коефіцієнти відповідних цільових функцій.
Доведення:
Узагальнення
ред.У загальнішому випадку, якщо — допустимий розв'язок прямої задачі максимізації, а — допустимий розв'язок двоїстої задачі мінімізації, зі слабкої двоїстості випливає, що , де і — цільові функції для прямої і двоїстої задач відповідно.
Див. також
ред.Примітки
ред.- ↑ Boţ, Grad, Wanka, 2009, с. 1.
- ↑ Прямодвоїстий алгоритм — це алгоритм одночасного розв'язування прямої і двоїстої задач.
- ↑ Gonzalez, 2007, с. 2.
Література
ред.- Radu Ioan Boţ, Sorin-Mihai Grad, Gert Wanka. Duality in Vector Optimization. — Berlin : Springer-Verlag, 2009. — С. 1. — ISBN 978-3-642-02885-4. — DOI:
- Teofilo F. Gonzalez. Handbook of Approximation Algorithms and Metaheuristics. — CRC Press, 2007. — С. 2-12. — ISBN 9781420010749.