Autor
Juan G. Villegas
Profesor Facultad de Ingeniería
De manera complementaria al análisis de sensibilidad, la teoría de dualidad nos brinda información adicional para entender la estructura del modelo de optimización que se ha resuelto y del sistema que dicho modelo representa. En particular, el problema dual nos dirá cuáles son las restricciones (de recursos, demanda, etc.) que hacen que la solución óptima sea una y no otra. Así mismo, la solución óptima del problema dual nos indicará el aporte marginal que tendría una modificación en los lados derechos de las restricciones. Aquí veremos entonces los fundamentos matemáticos de la dualidad en programación lineal, los cuales se seguirán ilustrando con el ejemplo de DJO que nos sirvió para discutir la intuición y los principios del análisis de sensibilidad.
La exposición de este tema se basa, principalmente, en Salazar (2001, secciones 5.1 y 5.2) y Rardin (2017, secciones 6.4 a la 6.9). Así mismo, Tovey (2020) es una muy buena fuente para un abordaje moderno de la optimización lineal desde la perspectiva de la dualidad.
Continuando con nuestro ejemplo y su solución óptima x^\ast=\left(x_c,x_r\right)=(40,0) de utilidad $100000, ahora nos haremos preguntas de este estilo:
- Si tuviese que aumentar la capacidad de alguno de los procesos, ¿de cuál lo haría?
- ¿Cuánto pagaría por aumentar la capacidad de producción de cada proceso?
El proceso fue formulado de la siguiente manera:
max\ {utilidad=2500x_c+1600x_r}+0s_1+0s_2+0s_3
Sujeto a:
| 5x_c+9x_r+s_1=\ 320 | (Extrusión) |
| x_c+2x_r+s_2=\ 300 | (Corte) |
| 12x_c+15x_r+s_3=480 | (Empaque) |
| x_c,\ x_r,\ s_1,\ s_2,s_3\geq0 | Dominio de las variables de decisión |
Gráficamente podemos identificar a simple vista cuál es la restricción activa en la solución óptima (la restricción de empaque). Esto indica cuál es el recurso que limita la capacidad de DJO para tener mayores ganancias, mientras que en las restricciones de extrusión y empaque hay holgura. Veámoslo:
Figura 1. Ejemplo de región factible DJO
Así mismo, podemos encontrar algebraicamente las holguras al reemplazar los valores de x_c^ \ast y x_r^ \ast en las restricciones del problema de optimización y despejarlas en cada una.
| 5x_c^\ast+9x_r^\ast=5\left(40\right)+9\left(0\right)=200\le\ 320\rightarrow s_1^\ast=120 | (Extrusión) |
| x_c^\ast+2x_r^\ast=40+2\left(0\right)=40\le\ 300\rightarrow s_2^\ast=260 | (Corte) |
| 12x_c^\ast+15x_r^\ast=12\left(40\right)+15\left(0\right)=480=480\rightarrow s_3^\ast=0 | (Empaque) |
Este resultado indica que de estos dos recursos (extrusión y empaque) no necesitamos una mayor disponibilidad para mejorar la utilidad de la compañía, de hecho, nos sobra bastante. Por el contrario, si quisiéramos saber cuánto pagar por una hora más del proceso de empaque, necesitaríamos información adicional.
Identificar este hecho gráficamente solo es posible en dos dimensiones. Para problemas de mayor dimensión el proceso puede ser complejo. En este caso, el problema dual que trataremos en esta sección es la herramienta de la optimización (lineal) que nos servirá para identificar las restricciones activas y qué tan sensible es la solución óptima en su función objetivo a cambios en el lado derecho de todas las restricciones.
La teoría que permite derivar el problema dual y sus propiedades está basada en los multiplicadores de Lagrange para la optimización con múltiples variables, la cual está por fuera del alcance de este curso; sin embargo, si quiere profundizar en este tema le recomendamos la sección de ¿De dónde viene la dualidad?, al finalizar este recurso. Así mismo, el libro de Tovey (2020) es una buena referencia para profundizar al respecto.
Antes de continuar con esta sección, resuelva los problemas primal y dual de la sección anterior con el software de optimización que prefiera, ¿nota algo particular? ¿Ese resultado no es fortuito? Que las funciones objetivo óptimas coincidan es una propiedad de la dualidad. A continuación, veremos los principales teoremas de dualidad.
Ahora sí apliquemos este mismo concepto de dualidad a nuestro ejemplo para resolver las preguntas con las que abrimos esta sección:
- Si tuviese que aumentar la capacidad de alguno de los procesos, ¿de cuál lo haría?
- ¿Cuánto pagaría por aumentar la capacidad de producción de cada proceso?
Recordando el valor de las variables básicas en la solución óptima, tenemos: x^\ast=\left(x_c,\ x_r,\ s_1,\ s_2,s_3\right)=(40,0,120,260,0)
| max\ {utilidad=2500x_c+1600x_r}+0s_1+0s_2+0s_3 | |
| Sujeto a: | |
| 5x_c+9x_r+s_1=\ 320 | (Extrusión) |
| x_c+2x_r+s_2=\ 300 | (Corte) |
| 12x_c+15x_r+s_3=480 | (Empaque) |
| x_c,\ x_r,\ s_1,\ s_2,s_3\geq0 | Dominio de las variables de decisión |
Lo cual significa que la base óptima es B=\left[\begin{matrix}5&1&0\\1&0&1\\12&0&0\\\end{matrix}\right] y \ \ B^{-1}=\left[\begin{matrix}0&0&\frac{1}{12}\\1&0&-\frac{5}{12}\\0&1&-\frac{1}{12}\\\end{matrix}\right]
Con esta base óptima podemos calcular las variables duales con la definición: w^\ast=c_B B^{-\mathbf{1}}=\left[\begin{matrix}2500&0&0\\\end{matrix}\right]\left[\begin{matrix}0&0&\frac{1}{12}\\1&0&-\frac{5}{12}\\0&1&-\frac{1}{12}\\\end{matrix}\right]=\left[\begin{matrix}0&0&\frac{2500}{12}\\\end{matrix}\right]=[w_{extrusion\ }\ w_{corte}\ w_{empaque}]
Esto nos lleva a concluir que:
- El recurso en el que se requiere mayor capacidad para aumentar la utilidad de DJO es el proceso de empaque, en el cual no se tiene holgura en la solución óptima.
- Por cada hora de este recurso determinante podríamos pagar hasta $208.33, que es el aumento que se espera en la utilidad de la compañía. Si pagáramos un valor mayor, el aumento en la función objetivo no sopesaría lo que habríamos pagado por aumentar la capacidad.
- Por el contrario, en los otros dos procesos tenemos holgura, lo que significa que no es necesario aumentar su capacidad; los valores de cero en las variables duales nos indican este hecho. Es decir, aumentar el lado derecho no cambiará la solución óptima (a menos que dicho cambio anule por completo la holgura, algo que vimos en la sección de análisis de sensibilidad).
Para terminar, notemos que en las restricciones en las que teníamos holgura mayor que cero de los procesos de extrusión y empaque (respectivamente: s_1=120,\ s_2=260) la variable dual fue cero. Nuevamente, este no es un resultado fortuito, por el contrario, se le conoce como holgura complementaria, donde las holguras óptimas del problema primal multiplicadas por las variables duales dan cero. Es decir, si la restricción es activa en la solución óptima, su variable dual es mayor que cero; pero si hay holgura, su variable dual es cero.
Junto con la holgura complementaria hay dos propiedades adicionales de dualidad, conocidas como el teorema fundamental de dualidad y las condiciones de optimalidad de Karush-Khun-Tucker, que no discutiremos en este curso. Para estudiarlas, sugerimos la bibliografía en la que se basó esta sección o los textos de la bibliografía del curso: Salazar (2001, secciones 5.1.2 y 5.1.4).
En resumen, el teorema fundamental de dualidad dice que primal y dual pueden ser:
El software de optimización actual incluye instrucciones que permiten conocer automáticamente los valores de las variables duales y las holguras de las restricciones. 1
Los siguientes videotutoriales presentan ejemplos de la implementación computacional de este análisis en Solver de Excel y en un modelador algebraico. Así mismo, se incluye un cuaderno de Colab con el análisis de dualidad en Pyomo .
- Para el ejemplo de DJO, realice el análisis de dualidad que hicimos en este material, usando para ello el software de optimización descrito en los dos videotutoriales. De esta manera obtendrá automáticamente los resultados que obtuvimos en este documento de manera analítica.
-
Para el ejemplo que resolvió en un ejercicio anterior usando el método
simplex, realice la implementación computacional y luego realice el análisis de
dualidad usando el Solver de Excel y un modelador algebraico. Aquí le recordamos
el texto del ejemplo:
Top Brass Trophy Company fabrica trofeos de campeonato para ligas deportivas juveniles. Por el momento están planificando la producción para los deportes de fin de año: fútbol y baloncesto. Cada trofeo de fútbol tiene una base de madera y una placa grabada, una pelota de latón en la parte superior y tiene una ganancia de $12. Los trofeos de baloncesto son similares, excepto que una cesta de bronce está en la parte superior y la ganancia unitaria es de solo $8.
Dado que el trofeo de fútbol tiene una forma asimétrica, su base requiere 4 pies cuadrados de madera; mientras que la base del de baloncesto requiere solo 2 pies cuadrados de madera. En este momento hay 1000 balones de fútbol de latón en inventario, 1500 cestas de baloncesto en latón, 1750 placas y 4800 pies cuadrados de madera.
Jensen, S. (2005). An Introduction to Lagrange Multipliers. http://www.slimy.com/~steuard/teaching/tutorials/Lagrange.html
Prawda, J. (1981). Métodos y modelos de investigación de operaciones (Vol. 1). Editorial Limusa.
Rardin, R. L. (2017). Optimization in operations research. Upper Saddle River, NJ: Prentice Hall.
Salazar González, J. J. (2001). Programación matemática. Diaz de Santos.
Tovey, C. A. (2020). Linear Optimization and Duality: A Modern Exposition. Chapman and Hall/CRC.