¿Cuál sería una buena prueba informal / intuitiva para "dar en el blanco" sobre la dualidad LP? ¿Cuál es la mejor manera de mostrar que la función objetivo minimizada es realmente la mínima con una forma intuitiva de entender el límite?
La forma en que me enseñaron la Dualidad solo condujo a una comprensión que estoy seguro es compartida por MUCHAS personas que conozco: por cada problema de minimización correspondiente hay un problema de maximización equivalente que puede derivarse invirtiendo las restricciones de desigualdad. Período. Esta "conclusión" de la dualidad es lo que parece mantenerse pero no "por qué es así" (es decir, cómo / por qué hay un límite en la solución óptima).
¿Hay alguna forma de jugar con las desigualdades solo para 'mostrar' el límite inferior / superior en el óptimo que podría ser una motivación para la prueba?
Revisé el libro de Chvatal y algunos otros, pero no encontré nada que los novatos absolutos pudieran entender en LP. Lo más cercano que obtuve fue del libro de Vazirani sobre algoritmos, donde habla sobre 'multiplicar las desigualdades con algunos números mágicos que muestran el límite': no estoy seguro de cómo reproducir el efecto para un LP arbitrario.
fuente
Respuestas:
Por deseo de OP, aquí está la respuesta matemática. SE enlazo en mi comentario anterior.
Tal vez valga la pena hablar de dónde viene el dual en un problema de ejemplo. Esto llevará un tiempo, pero espero que el dual no parezca tan misterioso cuando hayamos terminado.
Suponga que tiene un problema primario como sigue.
Ahora, supongamos que queremos usar las restricciones del primal como una forma de encontrar un límite superior en el valor óptimo del primal. Si multiplicamos la primera restricción por , la segunda restricción por , y las sumamos, obtenemos para el lado izquierdo y para el lado derecho. Dado que la primera restricción es una igualdad y la segunda es una desigualdad, esto implica Pero como , también es cierto que , y entonces Por lo tanto, es un límite superior en el valor óptimo del problema primario.
Sin embargo, seguramente podemos hacerlo mejor que eso. En lugar de adivinar y como multiplicadores, dejemos que sean variables. Por lo tanto, estamos buscando multiplicadores e para forzar9 1 y1 y2
Ahora, para que se mantenga este par de desigualdades, ¿qué tiene que ser cierto sobre y ? Tomemos las dos desigualdades de una en una.y1 y2
La primera desigualdad :5x1−6x2≤y1(2x1−x2)+y2(x1+3x2)
Tenemos que rastrear los coeficientes de las variables y separado. Primero, necesitamos que el coeficiente total en el lado derecho sea al menos . Obtener exactamente sería genial, pero como , cualquier cosa mayor que también satisfaría la desigualdad para . Matemáticamente hablando, esto significa que necesitamos .x1 x2 x1 5 5 x1≥0 5 x1 2y1+y2≥5
Por otro lado, para garantizar la desigualdad para la variable , necesitamos que el coeficiente total en el lado derecho sea exactamente . Dado que podría ser positivo, no podemos ir por debajo de , y dado que podría ser negativo, no podemos ir por encima de (ya que el valor negativo para cambiaría la dirección de la desigualdad). Entonces, para que la primera desigualdad funcione para la variable , tenemos que tener .x2 x2 −6 x2 −6 x2 −6 x2 x2 −y1+3y2=−6
La segunda desigualdad :
Aquí tenemos que rastrear las variables e separado. Las variables provienen de la primera restricción, que es una restricción de igualdad. No importa si es positivo o negativo, la restricción de igualdad aún se mantiene. Por lo tanto, tiene restricciones en el signo. Sin embargo, la variable proviene de la segunda restricción, que es una restricción menor o igual que. Si multiplicáramos la segunda restricción por un número negativo que cambiaría su dirección y la cambiaría a una restricción mayor o igual. Para mantener nuestro objetivo de limitar el objetivo primordial, no podemos permitir que eso suceda. Entonces ely1 y2 y1 y1 y1 y2 y2 La variable no puede ser negativa. Por lo tanto, debemos tener .y2≥0
Finalmente, queremos hacer que el lado derecho de la segunda desigualdad sea lo más pequeño posible, ya que queremos el límite superior más ajustado posible en el objetivo primario. Por lo tanto, queremos minimizar .y1+9y2
Al poner todas estas restricciones en y juntas, encontramos que el problema de usar las restricciones de primal para encontrar el mejor límite superior en el objetivo primario óptimo implica resolver el siguiente programa lineal:y1 y2
Y ese es el dual.
Probablemente valga la pena resumir las implicaciones de este argumento para todas las formas posibles de primal y dual. La siguiente tabla está tomada de la p. 214 de Introducción a la Investigación de Operaciones , 8ª edición, por Hillier y Lieberman. Se refieren a esto como el método SOB, donde SOB significa Sensible, Odd o Bizarre, dependiendo de la probabilidad de encontrar esa restricción particular o restricción variable en un problema de maximización o minimización.
fuente
Al elaborar la respuesta de Mike y el comentario de Vazirani, obtienes el doble al considerar la forma general de una prueba de optimización para la solución del problema original. Suponga que tiene un problema de maximización dadas algunas desigualdades lineales, y sin pérdida de generalidad, suponga que está tratando de maximizar la variable . Dada una solución en la que , ¿cómo sabemos que es óptima? Una forma es tratar de obtener un límite en tomando combinaciones lineales de las desigualdades lineales. Algunas combinaciones lineales le dan un límite de la forma , y está tratando de obtener la mejor (mínima) posible. La dualidad débil indica quex x=B x x≤C C B≤minC , lo cual es obvio por definición. Estados dualidad fuerte que cuando es finito, entonces . Esto significa que si el máximo es entonces hay una "razón" por la que no puede ir más allá de , lo que funciona como una prueba de optimización.B B=minC B B
Este punto de vista es realmente útil a veces. Sea una función de conjunto ( toma un conjunto y genera un número real), y son dos conjuntos. Suponga que está tratando de derivar una desigualdad partir de un conjunto de desigualdades con respecto a la función (ese es un ejemplo de la vida real). Escribes un programa lineal en el que los valores de son las variables, es una restricción y el objetivo es minimizar . La solución a este programa es (supongamos que es la mejor opción posible), y la solución al dual le proporciona una prueba def f S,O f(S)≥(1−1/e)f(O) f f f(O)=1 f(S) minf(S)=1−1/e 1−1/e f(S)≥1−1/e .
Esto deja abierta la pregunta de por qué la fuerte dualidad realmente se mantiene. Hay dos pruebas de este hecho para la programación lineal, una que involucra el algoritmo simplex y la otra el lema de Farkas. El lema de Farkas es probablemente la forma "correcta" de entender la situación, reduciendo todo a un hecho geométrico intuitivo. Sin embargo, confieso que esta intuición se me pasa por la cabeza.
En situaciones más generales (digamos programación semidefinida), debe usar las condiciones más generales de Karush-Kuhn-Tucker (una forma de multiplicadores de Lagrange) para obtener el dual y las condiciones para una fuerte dualidad. Esto se trata en textos sobre optimización no lineal o convexa.
fuente