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?Seg煤n su portafolio, la compa帽铆a DJO produce 煤nicamente dos tipos de perfiles extruidos: perfiles cuadrados y perfiles redondos. Los perfiles cuadrados tienen una utilidad neta de $2.5 por metro, mientras que los perfiles redondos ofrecen una utilidad neta de $1.6. DJO tiene el monopolio del mercado, as铆 que se espera vender todo lo que est茅 en capacidad de producir. El proceso de fabricaci贸n de los perfiles tiene tres etapas b谩sicas: extrusi贸n, corte y empaque. La producci贸n de 1000 metros de perfil cuadrado requiere 5 horas de extrusi贸n, 1 hora de corte y 12 horas en empaque. Por su parte, para producir los mismos 1000 metros del perfil redondo se requieren 9 horas de extrusi贸n, 2 horas de corte y 15 de empaque. La disponibilidad de cada uno de los procesos es: 320 horas de extrusi贸n, 300 horas de corte y 480 horas de empaque.
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贸nGr谩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.