En matemáticas aplicadas , la dualidad débil es un concepto en optimización que establece que la brecha de dualidad es siempre mayor o igual a 0. Eso significa que la solución al problema dual (minimización) es siempre mayor o igual que la solución a un primal asociado. problema . Esto se opone a la fuerte dualidad que solo se mantiene en ciertos casos. [1]
Usos
Muchos algoritmos de aproximación primal-dual se basan en el principio de dualidad débil. [2]
Teorema de la dualidad débil
El problema primordial :
- Maximizar c T x sujeto a A x ≤ b , x ≥ 0;
El problema dual ,
- Minimizar b T y sujeto a A T y ≥ c , y ≥ 0.
El teorema de la dualidad débil establece c T x ≤ b T y .
Es decir, si es una solución factible para el programa lineal de maximización primaria y es una solución factible para el programa lineal de minimización dual, entonces el teorema de dualidad débil se puede establecer como , dónde y son los coeficientes de las respectivas funciones objetivo.
Prueba: c T x = x T c ≤ x T A T y ≤ b T y
Generalizaciones
De manera más general, si es una solución factible para el problema de maximización primordial y es una solución factible para el problema de minimización dual, entonces la dualidad débil implica dónde y son las funciones objetivo para los problemas primarios y duales, respectivamente.
Ver también
Referencias
- ^ Boţ, Radu Ioan; Grad, Sorin-Mihai; Wanka, Gert (2009), Duality in Vector Optimization , Berlín: Springer-Verlag, p. 1, doi : 10.1007 / 978-3-642-02886-1 , ISBN 978-3-642-02885-4, MR 2542013.
- ^ González, Teófilo F. (2007), Manual de algoritmos de aproximación y metaheurísticas , CRC Press, p. 2-12, ISBN 9781420010749.