El dual de un programa lineal dado (LP) es otro LP que se deriva del LP original (el primario ) de la siguiente manera esquemática:
- Cada variable en el LP primario se convierte en una restricción en el LP dual;
- Cada restricción en el LP primario se convierte en una variable en el LP dual;
- La dirección del objetivo se invierte: el máximo en el primario se vuelve mínimo en el dual y viceversa.
El teorema de la dualidad débil establece que el valor objetivo del LP dual en cualquier solución factible es siempre un límite del objetivo del LP primario en cualquier solución factible (límite superior o inferior, dependiendo de si se trata de un problema de maximización o minimización). De hecho, esta propiedad de delimitación es válida para los valores óptimos de los LP primarios y duales.
El teorema de la dualidad fuerte establece que, además, si el primario tiene una solución óptima, entonces el dual también tiene una solución óptima, y los dos óptimos son iguales . [1]
Estos teoremas pertenecen a una clase más amplia de teoremas de dualidad en optimización . El teorema de la dualidad fuerte es uno de los casos en los que la brecha de dualidad (la brecha entre el óptimo del primario y el óptimo del dual) es 0.
Construyendo el LP dual
Dado un LP primario, se puede utilizar el siguiente algoritmo para construir su LP dual. [1] : 85 El LP primordial se define por:
- Un conjunto de n variables:.
- Para cada variable , una restricción de signo : debe ser no negativa (), o no positivo (), o sin restricciones ().
- Una función objetiva:
- Una lista de restricciones m . Cada restricción j es:donde el símbolo antes del pueden ser cualquiera de los dos o o .
El LP dual se construye de la siguiente manera.
- Cada restricción primaria se convierte en una variable dual. Entonces hay m variables:.
- La restricción de signo de cada variable dual es "opuesta" al signo de su restricción primaria. Entonces ""se convierte en y ""se convierte en y ""se convierte en .
- La función de doble objetivo es
- Cada variable primaria se convierte en una restricción dual. Entonces hay n restricciones. El coeficiente de una variable dual en la restricción dual es el coeficiente de su variable primaria en su restricción primaria. Entonces cada restricción i es:, donde el símbolo antes del es similar a la restricción sobre la variable i en el LP primario. Entonces se convierte en "" y se convierte en "" y se convierte en "".
A partir de este algoritmo, es fácil ver que el dual del dual es el primario.
Formulaciones vectoriales
Si todas las restricciones tienen el mismo signo, es posible presentar la receta anterior de una manera más corta usando matrices y vectores. La siguiente tabla muestra la relación entre varios tipos de primarios y duales.
Primitivo | Doble | Nota |
---|---|---|
Maximizar c T x sujeto a A x ≤ b , x ≥ 0 | Minimizar b T y sujeto a A T y ≥ c , y ≥ 0 | Esto se denomina problema dual "simétrico". |
Maximizar c T x sujeto a A x ≤ b | Minimizar b T y sujeto a A T y = c , y ≥ 0 | Esto se denomina problema dual "asimétrico". |
Maximizar c T x sujeto a A x = b , x ≥ 0 | Minimizar b T y sujeto a A T y ≥ c |
Los teoremas de la dualidad
A continuación, suponga que el LP primario es "maximizar c T x sujeto a [restricciones]" y el LP dual es "minimizar b T y sujeto a [restricciones]".
Dualidad débil
El teorema de la dualidad débil dice que, para cada solución factible x del primario y cada solución factible y del dual: c T x ≤ b T y . En otras palabras, el valor objetivo en cada solución factible del dual es un límite superior en el valor objetivo del primario, y el valor objetivo en cada solución factible del primario es un límite inferior en el valor objetivo del dual. Esto implica:
max x c T x ≤ min y b T y
En particular, si el primario es ilimitado (desde arriba), entonces el dual no tiene una solución factible, y si el dual es ilimitado (desde abajo), entonces el primario no tiene una solución factible.
El teorema de la dualidad débil es relativamente sencillo de demostrar. Suponga que el LP primario es "Maximizar c T x sujeto a A x ≤ b , x ≥ 0". Supongamos que crear una combinación lineal de las restricciones, con coeficientes positivos, de manera que los coeficientes de x en las restricciones son al menos c T . Esta combinación lineal nos da un límite superior en el objetivo. Las variables y del LP dual son los coeficientes de esta combinación lineal. El LP dual intenta encontrar tales coeficientes que minimicen el límite superior resultante. Esto le da al LP "Minimizar b T y sujeto a A T y ≥ c , y ≥ 0". [1] : 81–83 Vea el pequeño ejemplo a continuación.
Fuerte dualidad
El teorema de la dualidad fuerte dice que si uno de los dos problemas tiene una solución óptima, también la tiene el otro y que los límites dados por el teorema de la dualidad débil son estrictos, es decir:
max x c T x = min y b T y
El teorema de la dualidad fuerte es más difícil de probar; las demostraciones suelen utilizar el teorema de la dualidad débil como subrutina.
Una prueba utiliza el algoritmo simplex y se basa en la prueba de que, con la regla de pivote adecuada, proporciona una solución correcta. La prueba establece que, una vez que el algoritmo simplex termina con una solución al LP primario, es posible leer desde el cuadro final, una solución al LP dual. Entonces, al ejecutar el algoritmo simplex, obtenemos soluciones tanto para el primario como para el dual simultáneamente. [1] : 87–89
Otra prueba usa el lema de Farkas . [1] : 94
Implicaciones teóricas
1. El teorema de la dualidad débil implica que encontrar una única solución factible es tan difícil como encontrar una solución óptima factible. Supongamos que tenemos un oráculo que, dado un LP, encuentra una solución factible arbitraria (si existe). Dado el LP "Maximizar c T x sujeto a A x ≤ b , x ≥ 0", podemos construir otro LP combinando este LP con su dual. El LP combinado tiene tanto x como y como variables:
Maximizar 1
sujeto a A x ≤ b , A T y ≥ c , c T x ≥ b T y , x ≥ 0, y ≥ 0
Si el LP combinado tiene una solución factible ( x , y ), entonces por dualidad débil, c T x = b T y . Entonces x debe ser una solución máxima del LP primario e y debe ser una solución mínima del LP dual. Si el LP combinado no tiene una solución factible, entonces el LP primario tampoco tiene una solución factible.
2. El teorema de la dualidad fuerte proporciona una "buena caracterización" del valor óptimo de un LP en el sentido de que nos permite probar fácilmente que algún valor t es el óptimo de algún LP. La prueba procede en dos pasos: [2] : 260–261
- Muestre una solución factible al LP primario con valor t ; esto prueba que el óptimo es al menos t .
- Muestre una solución factible al LP dual con valor t ; esto prueba que el óptimo es como máximo t .
Ejemplos de
Pequeño ejemplo
Considere el LP primario, con dos variables y una restricción:
La aplicación de la receta anterior da el siguiente LP dual, con una variable y dos restricciones:
Es fácil ver que el máximo del LP primario se alcanza cuando x 1 se minimiza a su límite inferior (0) y x 2 se maximiza a su límite superior bajo la restricción (7/6). El máximo es 4 · 7/6 = 14/3.
De manera similar, el mínimo del LP dual se alcanza cuando y 1 se minimiza a su límite inferior bajo las restricciones: la primera restricción da un límite inferior de 3/5 mientras que la segunda restricción da un límite inferior más estricto de 4/6, por lo que la el límite inferior real es 4/6 y el mínimo es 7 · 4/6 = 14/3.
De acuerdo con el teorema de la dualidad fuerte, el máximo del primario es igual al mínimo del dual.
Usamos este ejemplo para ilustrar la demostración del teorema de dualidad débil. Supongamos que, en el LP primordial, queremos obtener un límite superior en el objetivo. Podemos usar la restricción multiplicada por algún coeficiente, digamos. Para cualquier obtenemos: . Ahora siy , luego , entonces . Por lo tanto, el objetivo del LP dual es un límite superior en el objetivo del LP primario.
Ejemplo de granjero
Considere un agricultor que puede cultivar trigo y cebada con la provisión establecida de algo de tierra L , fertilizante F y pesticida P. Para cultivar una unidad de trigo, una unidad de tierra, unidades de fertilizante y deben usarse unidades de pesticida. De manera similar, para cultivar una unidad de cebada, una unidad de tierra, unidades de fertilizante y deben usarse unidades de pesticida.
El problema principal sería que el agricultor decidiera cuánto trigo () y cebada () para crecer si sus precios de venta son y por unidad.
Maximizar: | (maximizar los ingresos de la producción de trigo y cebada) | |
sujeto a: | (no se puede usar más tierra de la disponible) | |
(no se puede usar más fertilizante del disponible) | ||
(no se puede usar más pesticida del disponible) | ||
(no puede producir cantidades negativas de trigo o cebada). |
En forma de matriz, esto se convierte en:
- Maximizar:
- sujeto a:
Para el problema dual, suponga que y los precios unitarios para cada uno de estos medios de producción (insumos) son establecidos por una junta de planificación. El trabajo de la junta de planificación es minimizar el costo total de la adquisición de las cantidades establecidas de insumos y, al mismo tiempo, proporcionar al agricultor un piso sobre el precio unitario de cada uno de sus cultivos (productos), S 1 para el trigo y S 2 para la cebada. Corresponde al siguiente LP:
Minimizar: | (minimizar el costo total de los medios de producción como la "función objetivo") | |
sujeto a: | (el agricultor debe recibir no menos de S 1 por su trigo) | |
(el agricultor debe recibir no menos de S 2 por su cebada) | ||
(los precios no pueden ser negativos). |
En forma de matriz, esto se convierte en:
- Minimizar:
- sujeto a:
El problema principal tiene que ver con las cantidades físicas. Con todos los insumos disponibles en cantidades limitadas, y suponiendo que se conocen los precios unitarios de todos los productos, ¿qué cantidades de productos producir para maximizar los ingresos totales? El problema dual tiene que ver con los valores económicos. Con garantías mínimas para todos los precios unitarios de producción, y suponiendo que se conoce la cantidad disponible de todos los insumos, ¿qué esquema de precios unitarios de insumos establecer para minimizar el gasto total?
A cada variable en el espacio primario le corresponde una desigualdad a satisfacer en el espacio dual, ambos indexados por tipo de salida. A cada desigualdad a satisfacer en el espacio primario le corresponde una variable en el espacio dual, ambas indexadas por tipo de entrada.
Los coeficientes que limitan las desigualdades en el espacio primario se utilizan para calcular el objetivo en el espacio dual, cantidades de entrada en este ejemplo. Los coeficientes utilizados para calcular el objetivo en el espacio primario limitan las desigualdades en el espacio dual, precios unitarios de salida en este ejemplo.
Tanto el problema primario como el dual utilizan la misma matriz. En el espacio primario, esta matriz expresa el consumo de cantidades físicas de insumos necesarios para producir cantidades establecidas de productos. En el espacio dual, expresa la creación de los valores económicos asociados con los productos a partir de los precios unitarios de entrada establecidos.
Dado que cada desigualdad se puede reemplazar por una igualdad y una variable de holgura, esto significa que cada variable primaria corresponde a una variable de holgura dual, y cada variable dual corresponde a una variable de holgura primaria. Esta relación nos permite hablar de laxitud complementaria.
Programa inviable
Un LP también puede ser ilimitado o inviable. La teoría de la dualidad nos dice que:
- Si lo primordial no tiene límites, entonces lo dual es inviable;
- Si el dual es ilimitado, entonces el primario es inviable.
Sin embargo, es posible que tanto el dual como el primario sean inviables. Aquí hay un ejemplo:
Maximizar: | |
Sujeto a: | |
Aplicaciones
El teorema de flujo máximo y corte mínimo es un caso especial del teorema de dualidad fuerte: la maximización del flujo es el LP primario y la minimización del corte es el LP dual. Consulte el teorema de corte mínimo de flujo máximo # Formulación de programa lineal .
Se pueden demostrar otros teoremas relacionados con los gráficos utilizando el teorema de la dualidad fuerte, en particular, el teorema de Konig . [3]
El teorema de Minimax para juegos de suma cero se puede demostrar usando el teorema de dualidad fuerte. [1] : apartado 8.1
Algoritmo alternativo
A veces, uno puede encontrar más intuitivo obtener el programa dual sin mirar la matriz del programa. Considere el siguiente programa lineal:
Minimizar | |||
sujeto a | |||
Tenemos m + n condiciones y todas las variables son no negativas. Definiremos m + n variables duales: y j y s i . Obtenemos:
Minimizar | |||
sujeto a | |||
Dado que este es un problema de minimización, nos gustaría obtener un programa dual que sea un límite inferior del primario. En otras palabras, nos gustaría que la suma de todos los del lado derecho de las restricciones fuera la máxima con la condición de que para cada variable primaria la suma de sus coeficientes no exceda su coeficiente en la función lineal. Por ejemplo, x 1 aparece en n + 1 restricciones. Si sumamos los coeficientes de sus restricciones obtenemos a 1,1 y 1 + a 1,2 y 2 + ... + a 1, ;; n ;; y n + f 1 s 1 . Esta suma debe ser como máximo c 1 . Como resultado, obtenemos:
Maximizar | |||
sujeto a | |||
Tenga en cuenta que asumimos en nuestros pasos de cálculo que el programa está en forma estándar. Sin embargo, cualquier programa lineal puede transformarse a la forma estándar y, por lo tanto, no es un factor limitante.
Interpretaciones de la vida real
El teorema de la dualidad tiene una interpretación económica. Si interpretamos el LP primario como un problema clásico de "asignación de recursos", su LP dual puede interpretarse como un problema de "valoración de recursos". Consulte también el precio sombra .
El teorema de la dualidad también tiene una interpretación física. [1] : 86–87
Referencias
- ^ a b c d e f g Gärtner, Bernd; Matoušek, Jiří (2006). Comprensión y uso de la programación lineal . Berlín: Springer. ISBN 3-540-30697-8. Páginas 81–104.
- ^ Lovász, László ; Plummer, MD (1986), Teoría de emparejamiento , Annals of Discrete Mathematics, 29 , Holanda Septentrional, ISBN 0-444-87916-1, MR 0859549
- ^ AA Ahmadi (2016). "Lección 6: programación lineal y emparejamiento" (PDF) . Universidad de Princeton .