Gyenge kettősség

A gyenge kettősség egy olyan koncepció az optimalizálásban , amely kimondja, hogy a kettősség rés mindig nagyobb vagy egyenlő nullával. Ez azt jelenti, hogy az elsődleges probléma (a minimalizálási probléma) megoldása mindig nagyobb vagy egyenlő, mint a kapcsolódó kettős probléma megoldása . Ez a kifejezés az erős kettősséggel áll szemben , amely csak bizonyos feltételek mellett teljesül [1] .

Használat

Sok közvetlen kettős [2] közelítési algoritmus a gyenge dualitás elvén alapul [3] .

Gyenge dualitástétel

Közvetlen feladat:

Maximalizálja a feltételek mellett ;

\mathbf {c} ^{T}\mathbf {x}

A\mathbf {x} \leqslant \mathbf {b} ,\mathbf {x} \geqslant 0

Kettős feladat:

Minimalizálja a tárgyat .

\mathbf {b} ^{T}\mathbf {y}

A^{T}\mathbf {y} \geqslant \mathbf {c} ,\mathbf {y} \geqslant 0

A gyenge dualitás tétele kimondja, hogy . $\mathbf {c} ^{T}\mathbf {x} \leqslant \mathbf {b} ^{T}\mathbf {y}$

Ugyanis, ha megvalósítható megoldás a lineáris programozás maximalizálásának közvetlen problémájára , és megvalósítható a lineáris programozás minimalizálásának kettős problémája, akkor a gyenge dualitás tétele a következőképpen fogalmazható meg: , ahol és a megfelelő együtthatói célfüggvények. $(x_{1},x_{2},....,x_{n})$ $(y_{1},y_{2},....,y_{m})$ ${\displaystyle \sum _{j=1}^{n}c_{j}x_{j}\leqslant \sum _{i=1}^{m}b_{i}y_{i))$ ${\displaystyle c_{j))$ $kettős$

Bizonyíték: $\mathbf {c} ^{T}\mathbf {x} =\mathbf {x} ^{T}\mathbf {c} \leqslant \mathbf {x} ^{T}A^{T}\mathbf {y} \leqslant \mathbf {b} ^{T}\mathbf {y}$

Általánosítások

Általánosabb esetben, ha megvalósítható megoldás a primális maximalizálási problémára, és megvalósítható megoldás a duális minimalizálási problémára, a gyenge dualitásból következik, hogy , hol és a primális, illetve a duális problémák célfüggvényei. $x$ $y$ $f(x)\leqslant g(y)$ $f$ $g$

Lásd még

Konvex programozás

Jegyzetek

↑ Boţ, Grad, Wanka, 2009 , p. egy.
↑ A primál-duális algoritmus egy olyan algoritmus, amely a primális és a duális problémákat egyidejűleg oldja meg.
↑ Gonzalez, 2007 , p. 2.

Irodalom

Radu Ioan Boţ, Sorin-Mihai Grad, Gert Wanka. Kettősség a vektoroptimalizálásban . - Berlin: Springer-Verlag, 2009. - P. 1. - ISBN 978-3-642-02885-4 . - doi : 10.1007/978-3-642-02886-1 .
Teofilo F. Gonzalez. Közelítő algoritmusok és metaheurisztikák kézikönyve . - CRC Press, 2007. - S. 2-12. — ISBN 9781420010749 .