En el contexto de las relaciones de dualidad en Programación Lineal, los teoremas de dualidad fuerte y dualidad débil constituyen importantes resultados teóricos que contribuye a la comprensión y resolución de modelos de optimización lineales. En el siguiente artículo ilustraremos su utilización haciendo uso de un ejemplo sencillo para fines académicos que por supuesto puede ser extendido a problemas de mayor tamaño.
Consideremos los siguientes problemas Primal (P) y Dual (D) en su formato matricial:
Lo anterior no constituye una pérdida de generalidad dado que el problema primal puede ser de maximización o de minimización con la consecuente incidencia en la interpretación de los resultados.
Teorema de Dualidad Débil
El Teorema de Dualidad Débil establece que si x є IRn, es una solución factible del problema Primal P) y ∏ є IRm, una solución factible del problema Dual D), entonces:
Es decir, en el formato descrito anteriormente, el valor que reporta una solución factible del problema dual de minimización al ser evaluada en su respectiva función objetivo, representa una cota superior del valor óptimo del problema primal de maximización.
Análogamente, una solución factible del problema primal de maximización al ser evaluada en dicha función objetivo representa una cota inferior del valor óptimo del problema dual de minimización. En conclusión: V(P)<=V(D).
En general si el problema primal tiene un dominio de soluciones factibles no acotado sin solución óptima (es decir, es un problema no acotado) el respectivo problema dual resultará ser infactible (y viceversa).
Para corroborar el Teorema de Dualidad Débil consideraremos un problema primal y su respectivo dual: (si tienes dudas respecto a las relaciones de dualidad te recomendamos leer previamente el artículo Cómo pasar de Primal a Dual y viceversa).
Una representación gráfica realizada con Geogebra del problema primal permite apreciar que el dominio de factibilidad es no acotado y su solución óptima se encuentra en el vértice C donde X1=2/5 y X2=6/5 con valor óptimo V(P)=16/5.
Notar adicionalmente que cualquier par ordenado que pertenece al área achurada es factible, por ejemplo X1=2 y X2=2 es una Solución Básica Factible para el problema primal con V(P)=8 (cota superior del valor óptimo del problema dual de maximización).
En cuanto al problema dual su dominio de factibilidad es acotado y su solución óptima se encuentra en el vértice C con Y1=2/5 e Y2=2/5 y valor óptimo V(D)=16/5. Adicionalmente existen otros puntos factibles como el origen (Y1=0 e Y2=0) con V(D)=0 lo cual permite corroborar que cualquier solución factible del problema dual al ser evaluada en la función objetivo (de minimización) genera una cota inferior del valor óptimo del problema primal de minimización.
Teorema de Dualidad Fuerte
Si un problema (Primal) de Programación Lineal tiene una solución óptima, entonces el correspondiente problema Dual también tiene una solución óptima, y los respectivos valores en la función objetivo son idénticos.
En consecuencia, del Teorema de Dualidad Fuerte se deduce que ambos problemas (primal y dual) al ser evaluados en sus respectivas soluciones óptimas (en caso de existir) proveen idéntico valor óptimo, es decir, V(P)=V(D). Es más, resulta suficiente resolver uno de ellos y luego utilizar las propiedades del Teorema de Holguras Complementarias para encontrar la solución óptima (y valor óptimo) de su problema equivalente. En nuestro ejemplo V(P)=16/5=V(D).
El método de multiplicadores de Lagrange (el cual es generalizado por las condiciones de optimalidad de Karush-Kuhn-Tucker) permite abordar la resolución de modelos de programación no lineal que consideran restricciones de igualdad. En este sentido y como resulta natural, el dominio de soluciones factibles considerará exclusivamente aquellas soluciones que permiten verificar el cumplimiento de la igualdad de dichas restricciones. Por el contrario, un problema de optimización que considera inecuaciones como restricciones, sólo requiere que éstas se cumplan y no necesariamente se deberá forzar el cumplimiento de ellas en igualdad (activas).
En general las condiciones de Lagrange se aplican a un problema que tiene la siguiente estructura:
Que da origen a la función Lagrangiana asociada a dicho problema:
Consideremos el siguiente problema de Programación No Lineal restringido que nos permitirá ilustrar la aplicación del método de Lagrange.
Notar que el problema adopta la estructura estándar previamente descrita y considera una única restricción de igualdad. No se incluye en particular condiciones de no negatividad, que en caso de estar presentes justificarían la aplicación del Teorema de Karush-Kuhn-Tucker.
En este contexto, un mínimo local para el problema propuesto debe satisfacer las condiciones necesarias de primer orden de Lagrange:
Que da origen al siguiente sistema de ecuaciones:
Donde la resolución es trivial y corresponde a x1=2, x2=2 y λ1=-4. Notar que el multiplicador de Lagrange asociado a una restricción de igualdad es libre de signo, en consecuencia la solución propuesta satisface las condiciones necesarias de primer orden.
Adicionalmente se cumplen las condiciones de segundo orden pues:
Es positiva definida (función objetivo estrictamente convexa y restricción lineal que define un conjunto convexo). Luego, el problema es convexo y en consecuencia x1=2 y x2=2 es mínimo global y solución óptima del problema. Este resultado por cierto es consistente con la representación gráfica del problema, donde la solución óptima corresponde al punto A, donde la restricción (color naranjo) es tangente a la curva de nivel que representa a la circunferencia de menor radio que intercepta el dominio de soluciones factibles.
Las condiciones de optimalidad establecidas en el Teorema de Karush Kuhn Tucker (KKT) permiten abordar la resolución de modelos de Programación No Lineal que consideran tanto restricciones de igualdad (ecuaciones) como desigualdad (inecuaciones).
En términos comparativos las condiciones de KKT son más generales que el Método de Lagrange el cual se puede aplicar a problemas no lineales que consideran exclusivamente restricciones de igualdad.
En el siguiente artículo mostraremos cómo utilizar el Teorema de Karush Kuhn Tucker para resolver un problema de Programación No Lineal con 2 variables de decisión.
Sin pérdida de generalidad un modelo de Programación No Lineal se puede representar a través del siguiente formato:
Luego podemos reescribir cualquier problema en dicha estructura manteniendo la equivalencia de la representación matemática. Para ejemplificar lo anterior consideremos el siguiente modelo de optimización no lineal que resulta de interés su resolución.
El problema anterior se puede representar gráficamente a través del software Geogebra de modo de encontrar su solución óptima (x1=2 y x2=1) en el par ordenado etiquetado con la letra “C” en el gráfico a continuación, con valor óptimo V(P)=2.
El conjunto de factibilidad corresponde al área achurada. Adicionalmente se puede observar que en la solución óptima se encuentran activas las restricciones 1 y 3 (el resto de las restricciones por cierto se cumple pero no en igualdad).
Por supuesto la resolución mediante el Método Gráfico es sólo referencial y se ha utilizado en este caso para corroborar los resultados a obtener en la aplicación del teorema. En este contexto el problema en su forma estándar es simplemente:
Notar que sólo fue necesario cambiar la forma de las restricciones de no negatividad (esto se puede hacer multiplicando por -1 cada una de ellas). Cabe destacar que en este caso en particular el problema no considera restricciones de igualdad.
Luego las condiciones necesarias de primer orden de Karush Kuhn Tucker (KKT) están dadas por:
Por ejemplo, si en las condiciones generales anteriores consideramos el problema no restringido (asumiendo que todas las restricciones son inactivas) la solución óptima por simple inspección es x1=3 y x2=2, que corresponde a la coordenada “E” de la gráfica anterior y que se puede observar no es una solución factible para el problema.
De este modo la circunferencia de menor radio que intercepta el conjunto de factibilidad es precisamente aquella que pasa por la coordenada “C” donde las restricciones 1 y 3 se cumplen en igualdad, razón por la cual las cuales activaremos de forma simultanea:
Al calcular los gradientes respectivos se obtiene:
Lo cual da origen al siguiente sistema de ecuaciones:
Reemplazando x1=2 y x2=1 podemos despejar los valores de los multiplicadores los cuales cumplen con las condiciones de no negatividad:
Adicionalmente se puede verificar que x1=2 y x2=1 satisface las restricciones omitidas (2, 4 y 5) por lo cual se puede afirmar que dicha solución cumple las condiciones necesarias de primer orden de Karush Kuhn Tucker (KKT).
A continuación verificamos el cumplimiento de las condiciones de segundo orden de KKT, en particular lo que tiene relación con la convexidad del problema. Para ello calculamos la Matriz Hessiana o de segundas derivadas de la función objetivo y las restricciones activas.
El primer determinante de la Matriz Hessiana es D1=8/3>=0 y el segundo determinante es D2=(8/3)*(8/3)=(64/9)>=0. Se concluye que el problema es convexo y por tanto x1=2 y x2=1 es mínimo local y global para el problema. La resolución computacional de este problema con AMPL corrobora los resultados alcanzados:
Ejercicio Resuelto Teorema de Karush Kuhn Tucker (KKT)
Un asesor financiero está evaluando la compra de acciones de firmas de cierto sector industrial. Desea minimizar la variación de la cartera resultante compuesta por acciones de dos firmas, pero también quiere tener un tasa de retorno de al menos un 9%. Después de obtener datos históricos sobre la variación y rendimientos de ambos instrumentos, desarrolla el siguiente modelo de optimización no-lineal:
Donde x e y representan la proporción de dinero invertida en cada acción. Formule explícitamente todas las condiciones de optimalidad del Teorema de Karush-Kuhn-Tucker para este problema y úselas para determinar la cartera óptima. Justifique adecuadamente su respuesta. Analice todos los posibles casos.
Respuesta:
Según el Teorema de Weierstrass, el problema admite solución óptima pues tiene una función objetivo continua y un dominio de soluciones factibles cerrado y acotado (que se puede apreciar incluso geométricamente). En este sentido el dominio de soluciones factibles son los puntos en la recta que unen los pares ordenados etiquetados con las letras A y B, donde:
y
Más aún es fácil ver que la Matriz Hessiana de la función objetivo es positiva definida y por ende es una función (estrictamente) convexa.
Como las restricciones son lineales, y la función objetivo es estrictamente convexa, resulta que es problema propuesto es un problema convexo.
Lo anterior (que el problema sea convexo) implica que las condiciones de optimalidad de Karush-Kuhn-Tucker son necesarias y suficientes para hallar la solución óptima del mismo.
Las condiciones del Teorema de Karush-Kuhn-Tucker para este problema son:
Al considerar el esquema de activación de restricciones, siempre debe estar activa la ecuación x+y =1 y lo que cabe entonces es no activar ninguna inecuación o a lo sumo activar una de ellas.
Los diferentes casos que se podrían llegar a analizar son:
i) Ninguna inecuación activa.
Tomamos μ1=0, μ2=0, μ3=0 y resolvemos:
0.32x + 0.20y + λ1 = 0
0.18y + 0.20x + λ1 = 0
x + y = 1
Cuya solución resulta ser: x=-0.2 e y=1.2 que es infactible.
ii) Activando sólo la inecuación 0.11x + 0.08y ≥ 0.09.
Cuya solución resulta ser: x=1/3 e y=2/3 con multiplicadores λ1=0,04444453 y μ1=1,777777502, con lo cual tenemos un punto que cumple con todas las condiciones del teorema.
iii) Activando sólo la inecuación x≥0.
Tomamos μ1=0, μ3=0 y resolvemos:
0.32x + 0.20y + λ1 – μ2 = 0
0.18y + 0.20x + λ1 = 0
x + y = 1
x = 0
Cuya solución resulta ser: x=0 e y=1 con multiplicadores λ1=-0.18 y μ2 = 0.02 pero no verifica 0.11x + 0.08y = 0.08 ≥ 0.09.
iv) Activando sólo la inecuación y≥0.
Tomamos μ1=0, μ2=0 y resolvemos:
0.32x + 0.20y + λ1 = 0
0.18y + 0.20x + λ1 – μ3 = 0
x + y = 1
y = 0
Cuya solución resulta ser: x=1 e y=0 con multiplicadores λ1=-0.32 y μ3=-0.12 y este último no cumple con la no-negatividad.
En consecuencia, la solución óptima es aquella obtenida en el caso ii) pues el problema es convexo: x=1/3 e y=2/3. Dicha solución corresponde al par ordenado etiquetado con la letra A en la gráfica anterior. El valor óptimo es 0.102222 y se obtiene simplemente al evaluar la solución óptima en la función objetivo.
A diferencia de la Programación Lineal donde sus distintas aplicaciones corresponden a problemas de optimización convexos (situación que facilita la resolución computacional), en Programación No Lineal no existen garantías a priori que permita garantizar que un modelo en particular será un problema convexo.
Es decir, una aplicación de Programación No Lineal puede ser un problema convexo o un problema no convexo.
En este artículo abordaremos a través de un ejemplo sencillo las dificultades prácticas y algorítmicas asociadas a la resolución de un modelo de Programación No Lineal no convexo.
Consideremos el siguiente modelo matemático no lineal con restricciones:
Una primera aproximación a su resolución consiste en graficar la función anterior utilizando Geogebra:
Se puede observar que la función es no convexa, constatándose adicionalmente la presencia de mínimos locales (por ejemplo los Puntos B y C) y mínimo global (Punto A).
En este sentido la expectativa que debiéramos tener al implementar este problema computacionalmente es obtener la solución óptima para un valor de x en el intervalo entre [4,5] (por simple inspección) lo que corresponde al Punto A de la gráfica anterior.
Una alternativa de resolución computacional para este problema es utilizar AMPL como lenguaje de programación matemática y MINOS 5.5 como solver de resolución. El código de la implementación y los resultados alcanzados se muestra a continuación:
La solución óptima encontrada por el algoritmo corresponde a x=1 (Punto C) lo que permite alcanzar un valor en la función objetivo igual a cero: f(1)=0. Claramente según nuestro gráfico esta solución corresponde sólo a un mínimo local aun cuando el programa sugiere que es el mínimo global del problema.
Otra alternativa de resolución consiste en la utilización de Solver. En primera instancia el algoritmo converge a la solución x=1 con f(1)=0.
Sin embargo, si manualmente editamos el valor de la celda color amarillo B3 (variable de decisión) a “2” y reoptimizamos con Solver se obtiene lo siguiente:
Se alcanza ahora una nueva solución con x=2,45608774 con f(2,45608774)=-1,41869663 lo que corresponde al Punto B de nuestro gráfico y que si bien corresponde a un mínimo local provee un valor menor en la función objetivo al ser comparado con el Punto C. En este contexto resulta razonable considerar el valor “4” para la celda cambiante como punto de partida para una nueva reoptimización:
Ahora obtenemos lo que correspondería al mínimo global del problema (Punto A) con solución óptima x=4,64443285 y valor óptimo f(4,64443285)=-3,63143221.
Finalmente hemos resuelto el problema con What’sBest! donde en el siguiente tutorial de nuestro canal de Youtube mostramos los detalles de la implementación:
Luego de reoptimizar sobre la solución local alcanzada en primera instancia se obtiene el mínimo global del problema (Punto A):
Conclusiones: Las principales dificultades enfrentadas al intentar resolver un modelo de Programación No Lineal no convexo es no tener la certeza si la solución obtenida a través de una herramienta computacional corresponde a un mínimo local o mínimo global.
Con las herramientas presentadas en este artículo fue necesario reoptimizar sobre soluciones obtenidas en primera instancia para encontrar la solución óptima del problema. Cabe destacar que en este ejemplo al disponer de una representación gráfica del problema sabíamos de antemano cuál era la solución del problema lo cual nos permitía contrastar los resultados computacionales. En este sentido claramente un modelo de mayor complejidad (por ejemplo, un mayor número de variables de decisión y/o restricciones) una aproximación intuitiva no tiene sentido práctico.
En este contexto una de las principales áreas actuales de desarrollo de la Investigación de Operaciones es proveer de métodos numéricos de resolución que permita abordar de forma eficiente la complejidad de esta categoría de problemas de optimización.
Los pasos a seguir son muy sencillos y los detallamos a continuación:
Paso 1: Abrir el programa Geogebra y en el Menú “Vista” seleccionar “Hoja de Cálculo”.
Paso 2: Copiar y Pegar los datos a granel en la planilla (Columna A) que desplegara el programa en la esquina superior derecha. En el ejemplo utilizaremos los mismos datos (40) del artículo anterior.
Paso 3: En el Menú seleccionar el icono con barras azules (con forma de histograma) y en las opciones que se desplegaran seleccionar “Análisis Una Variable”.
Paso 4: Se desplegara la ventana “Fuente de Datos” donde se podrán observar los valores ingresados en la Columna A. Luego seleccionar “Analiza”. Importante: Si los datos de la Columna A no aparecen en la ventana de “Fuente de Datos” debes posicionarte sobre la letra A de la planilla de cálculo y repetir el Paso 2 y 3. La imagen a continuación muestra cómo se deberían visualizar los datos de la Columna A antes de proceder con el Paso 4.
Paso 5:Listo!. Ya hemos generado un histograma con Geogebra. Se puede observar que existe una barra que se puede desplazar para ajustar la cantidad de clases que tiene el histograma según lo que nos parezca razonable. En la imagen a continuación hemos seleccionado 6 clases para mostrar la consistencia de los resultados con lo obtenido previamente con Excel y Easyfit. Notar adicionalmente que en el eje vertical se considera por defecto la frecuencia absoluta (“n”).
Finalmente se puede obtener de forma muy sencilla un resumen de las estadísticas de los datos proporcionados a granel seleccionando el icono “Muestra Estadísticas” (símbolo de sumatoria). Adicionalmente existen otras opciones interesantes que permiten generar un Diagrama de Caja o Diagrama de Tallo y Hojas. Te proponemos el desafío para que lo puedas revisar directamente!
y 
