Según hemos abordado en artículos anteriores el Precio Sombra de una restricción representa la tasa de cambio del valor óptimo ante una modificación marginal del lado derecho de una restricción. Se entiende por «marginal» aquella modificación que no cambia la geometría del problema, es decir, que la nueva solución óptima se puede encontrar a través de la resolución del sistema de ecuaciones al que da origen las restricciones activas originales (previa actualización del parámetro que estamos modificando). En este contexto el precio sombra puede ser un valor positivo, negativo o cero y en particular nos referiremos a este último caso en este artículo.
Consideremos el siguiente modelo de Programación Lineal en 2 variables:
El problema anterior lo podemos resolver gráficamente utilizando Geogebra, que da origen a un problema con infinitas soluciones óptimas en el tramo de recta que une los vértices B y C y que se puede denotar de forma general por: (X,Y)=λ(0,60)+(1-λ)(10,45) con λ en el intervalo entre [0,1]. El valor óptimo en consecuencia es V(P)=1.200.
¿Cuáles son las restricciones activas en el óptimo?. Por ejemplo si consideramos el vértice B (solución óptima) las restricciones activas son 3X+2Y<=120 y X>=0, sin embargo si seleccionamos el vértice C (también solución óptima) las restricciones activas son 5X+2Y<=140 y 3X+2Y<=120. Dado lo anterior ¿aumentará el valor óptimo si se dispone de unidades adicionales del recurso que representa el lado derecho de la restricción 5X+2Y<=140?.
Para ello buscaremos mantener activas las restricciones del vértice C identificando la máxima variación (aumentando el valor del lado derecho) que conserve las restricciones activas originales (esto genera un desplazamiento paralelo de la restricciones que hemos representado con la línea color punteada color rojo) lo cual se alcanza en la coordenada (X,Y)=(40,0). De forma análoga para determinar la mínima variación para el lado derecho desplazamos en un sentido de decrecimiento la restricción buscando conservar las restricciones activas originales hasta la coordenada (X,Y)=(0,60) (línea punteada color naranjo).
Evaluamos en la fórmula para el cálculo del precio sombra obteniendo lo siguiente:
Por tanto el precio sombra de la restricción 1 (5X+2Y<=140) es cero lo cual indica que si aumenta o disminuye el valor del parámetro que representa su lado derecho (actualmente b1=140) en el intervalo entre [120,200]no se verá afectado el valor óptimo del problema. Lo anterior es consistente con lo obtenido a través del informe de confidencialidad de restricciones de Solver de Excel:
En general un precio sombra igual a cero significa que la modificación del parámetro que representa el lado derecho de la respectiva restricción (en un intervalo que conserva la geometría del problema) no tiene un impacto en el valor óptimo del problema. Sin embargo, existen casos especiales como los problemas de Programación Lineal que admiten infinitas soluciones (como el descrito en este artículo) donde una restricción con precio sombra igual a cero puede ser activa en uno de los vértices óptimo (el caso más usual es que una restricción con precio sombra igual a cero no sea activa en el óptimo).
En el siguiente artículo abordaremos cómo calcular un Intervalo de Confianza para un Pronóstico de Demanda, lo cual permite incorporar de forma explícita el impacto que tiene la incertidumbre en la planificación de las actividades comerciales y operacionales de una empresa.
Consideremos una serie histórica con la demanda de un producto para un periodo de 12 semanas. Se requiere desarrollar un intervalo de confianza del 95% para el Pronóstico de Demanda de la semana 13 utilizando el Método de Suavizamiento Exponencial Simple con α=0,3.
Para ello adoptaremos el supuesto que los errores del pronóstico se distribuyen normalmente lo cual es algo que por supuesto se puede verificar con una dedicación mayor de trabajo y para lo cual se puede utilizar un software de análisis estadístico como Easyfit.
En este contexto la tabla a continuación se muestra el pronóstico comenzando a contar de la semana 4 (esta es una decisión arbitraria dado que podría haber comenzado antes).
Notar que el primer pronóstico corresponde simplemente a la Media Móvil Simple de las primeras 3 semanas.
Luego el pronóstico de la semana 5 se obtiene de la aplicación de la siguiente fórmula: F5=F4+α(A4-F4) que al reemplazar se obtiene F5=1.775+0,3*(1.860-1.775)=1.800,5~1.801 (hemos aproximado éste y los otros pronósticos al entero más cercano según se puede apreciar en la fórmula de Excel utilizada):
Ahora necesitamos calcular la desviación estándar del error del pronóstico la cual se obtiene simplemente evaluando en los datos de la tabla anterior según se muestra a continuación:
Finalmente el intervalo de confianza de un 95% para el pronóstico de la semana 13 se obtiene: (notar que F13=1.766+0,3*(1.780-1.766)=1.770,2~1.770)
El resultado anterior es consistente con el proporcionado por la herramienta de Cálculos de Probabilidad de Geogebra donde para una distribución de probabilidad normal (recordar el supuesto de normalidad del error adoptado anteriormente) con media μ=1.770 (F13) y desviación estándar SF=71, el área achurada en color azul representa los valores contenidos en el intervalo de confianza de un 95% (% del área bajo la curva achurada).
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.
y 
