El teorema de corte máximo de flujo-min es uno de los teoremas más famosos de optimización discreta, aunque es muy sencillo probar el uso de la teoría de la dualidad de la programación lineal. ¿Hay otros ejemplos de teoremas famosos que también son corolarios de dualidad LP, o dualidad de optimización convexa? El lema de Farkas y el teorema de separación de hiperplanos serían otros candidatos, aunque a mí me parecen más declaraciones equivalentes.
Respuestas
¿Demasiados anuncios?
Para profundizar en el comentario de M. Winter: El teorema minimax de Von Neumann para juegos de suma cero para dos personas puede considerarse como una consecuencia de la dualidad LP, aunque su primera prueba del teorema no hizo explícita esta conexión.
Thomas Kalinowski
Puntos
2553
El teorema de Konig y el teorema matrimonial de Hall son famosos y se desprenden de la dualidad LP (junto con un argumento de integralidad).
Void
Puntos
111
Bondareva-Shapley_theorem es bastante famoso en una teoría de juegos. En términos más modernos, une la descripción habitual y dual del permutoedro generalizado.
