En el siguiente artículo abordaremos un caso aplicado respecto a una situación real donde un sitio web de búsqueda de empleos en España desea determinar qué anuncios publicar en una zona preferente de exhibición dentro de su portal. Para ello será necesario formular y resolver un modelo de Programación Entera que corresponde a un caso particular del problema de asignación descrito en artículos anteriores.
Consideramos como premisa que existen más anuncios que espacios publicitarios y por tanto se debe decidir cuáles de ellos incorporar con el objetivo de maximizar el retorno de la asignación pero al mismo tiempo satisfacer una serie de criterios adicionales que se deseen imponer. Una representación de la situación descrita se resume en la tabla a continuación:
Por ejemplo el Aviso N°1 corresponde a un anuncio de trabajo en Madrid en la Categoría I, el cual fue publicado hace 15 días (antigüedad) y que provee un retorno estimado de 100 unidades monetarias. Por supuesto los datos son ficticios, no obstante, permite visualizar la extensión de esta problemática a una situación de esta naturaleza. Asumiremos adicionalmente que se desean cumplir las siguientes condiciones en la asignación:
Seleccionar un Máximo de 5 Anuncios (entre los 10 candidatos posibles).
El tiempo promedio de Publicación de los Anuncios que se seleccionen no debe superar los 7[días].
Por razones estratégicas se debe publicar al menos un Anuncio de Madrid.
Se impone un máximo de 2 Anuncios de la Categoría II.
Se impone un mínimo de 1 Anuncio de la Categoría I.
Se impone un mínimo de 1 Anuncio de la Categoría II.
Se impone un mínimo de 1 Anuncio de la Categoría III.
Un modelo de Programación Entera que permite encontrar una asignación para la situación descrita es el siguiente:
Variables de Decisión: Permite dar respuesta al problema de selección de anuncios publicitarios a incluir en la zona preferente. (i=1,…,10)
Función Objetivo: Maximizar el retorno total de la asignación, donde Ri es el retorno (en U.M.) asociadas al anuncio i.
Restricciones: Satisfacer las condiciones expuestas. Se detallan a continuación en el mismo orden en el que fueron detalladas. (Ti representa el tiempo de publicación (en días) del anuncio i).
Al implementar computacionalmente el problema con Solver de Excel se obtiene la siguiente solución óptima que otorga un valor óptimo de 465[U.M]. Con ello la empresa debería implementar los anuncios 1, 4, 5, 6 y 8.
El método de la Ruta Crítica conocida también por CPM por sus siglas en inglés (Critical Path Method) es una metodología de la Gestión de Proyectos que nos permite entre otros aspectos estimar la duración de un Proyecto. Para este propósito es necesario conocer las actividades que contempla el proyecto, su duración en una unidad de tiempo y el orden en el cuál deben ser realizadas (por ejemplo, algunas actividades se pueden desarrollar sólo cuando una o varias actividades previas o predecesoras han sido completadas).
Cómo obtener la Ruta Crítica de un Proyecto
El ejemplo a continuación muestra en detalle la aplicación del Método de Ruta Crítica a un proyecto que consta de 9 actividades cuyos tiempos estimados se encuentran en semanas. Adicionalmente en la columna “Predecesor” se establece el orden en el cual se deben realizar las distintas actividades, por ejemplo, la Actividad G se puede realizar una vez completada las Actividades D y F.
En este contexto resulta de utilidad desarrollar un Diagrama o Representación Gráfica del Proyecto donde cada nodo representa una actividad, el número al interior del paréntesis la duración de dicha actividad, y las flechas un camino o ruta consistente con las relaciones de precedencia.
Por ejemplo, la Actividad G tiene una duración estimada de 14 semanas y dicha actividad se puede iniciar una vez que hayan concluido sus predecesores, es decir, las Actividades D y F.
Se puede observar adicionalmente que las actividades iniciales son A y B y la actividad final es I.
Una actividad inicial es aquella que se puede comenzar inmediatamente y no existe ninguna otra actividad que le precede.
Una actividad final es una actividad que termina una ruta o camino del proyecto y en consecuencia no es predecesora de ninguna otra actividad del proyecto.
Por tanto la duración del proyecto estará determinado por aquella ruta o camino más largo que comenzando en una actividad inicial concluya en una actividad final. En nuestro ejemplo, un camino que comenzando en A (o en B) termine en I.
Luego, dado el tamaño reducido de este ejemplo es posible enumerar todas las posibilidades rutas o caminos que satisfacen la condición anterior:
La Ruta Crítica por tanto es A-E-F-G-I lo que determina que la duración del proyecto es de 26[sem].
Adicionalmente podemos estimar cuándo es lo más pronto que se puede comenzar cada actividad (inicio más cercano o IC – color rojo) y cuándo es lo más pronto que se puede terminar una actividad (término más cercano o TC – color azul).
Por ejemplo, para obtener el inicio más cercano y el término más cercano, en el caso de la Actividad A, éste será la semana 0 y 5, respectivamente. De la misma forma, lo más pronto que puede comenzar la Actividad C será en la semana 5 (tan pronto concluyo su predecesor que es la Actividad A) y lo más pronto que puede terminar es en la semana 9 (dado que la duración de la Actividad C es de 4 semanas) y así se continua el procedimiento desde el inicio hasta el final del proyecto.
En forma complementaria se puede obtener el tiempo más lejano en el cual se puede terminar una actividad sin atrasar el proyecto (término más lejano o TL – verde) y cuándo es lo más tarde que se puede comenzar una actividad sin retrasar el proyecto (inicio más lejano o IL – naranjo). Para obtener dichos tiempos retrocedemos desde la actividad final (I) hacia las actividades iniciales (A y B).
Por ejemplo, lo más tarde que puede terminar la Actividad H sin retrasar el proyecto es en la semana 24 (si termina más tarde de ello, entonces la Actividad I no se podrá iniciar en la semana 24 y por tanto el proyecto terminará más tarde que la semana 26). Naturalmente dado lo anterior, la Actividad H no podrá comenzar más tarde que la semana 12 si es que se desea terminar el proyecto en 26 semanas.
En este contexto se define el término Holgura (H) o Slack como el tiempo máximo que una actividad se puede retrasar en su inicio sin que esto afecte el tiempo estimado para terminar el proyecto como un todo:
Holgura = IL – IC = TL – TC
El siguiente diagrama muestra la ruta del proyecto con el cálculo de las holguras de cada una de las actividades. Se puede apreciar por ejemplo que la actividad B se puede retrasar un máximo de 6[sem] (su holgura) y aun así estar en condiciones de terminar el proyecto en 26[sem].
Adicionalmente las actividades que pertenecen a la ruta crítica tienen holgura igual a cero, lo que en este ejemplo en particular permite identificar una ruta única: A-E-F-G-I (notar que en general un proyecto puede tener más de una ruta o camino crítico).
Actualización: De forma de corroborar los resultados anteriores, a continuación se presenta una Carta Gantt del Proyecto obtenido a través del Método de Ruta Crítica (CPM). Con color rojo se destacan aquellas actividades que forman parte de la ruta crítica con holgura igual a cero.
¿Te gustaría disponer de un Apunte con ejercicios resueltos explicados de modo sencillo que te permita aprobar tu Examen de Programación Lineal?
El Libro de Apuntes de Programación Lineal que necesitas esta aquí y ha sido diseñado especialmente para aquellos alumnos que se encuentran cursando una cátedra inicial de Investigación de Operaciones (o Investigación Operativa) que buscan resolver de forma sencilla aquellas preguntas frecuentes relacionadas a los modelos de optimización lineales.
El material contenido en este Apunte es original, es decir, no ha sido tomado de libros o apuntes de terceros. Para ello hemos desarrollado una labor creativa en el diseño de los ejercicios que estamos seguros sabrás apreciar.
El Libro de Apuntes contiene los siguientes capítulos:
Desde Febrero de 2012 el Libro de Apuntes de Programación Lineal ha sido descargado por más de 57.000 100.000 usuarios de distintos países los cuales se han mostrados muy satisfechos por el material recibido. Esto ha permitido consolidar nuestro sitio web como una de las principales referencias sobre la Gestión de Operaciones e Investigación de Operaciones para estudiantes.
El Problema del Camino más Corto (o ruta más barata) consiste en encontrar una ruta o camino óptimo entre un nodo fuente y un nodo destino, los cuales están enlazados a través de una red con arcos que poseen un cierto atributo, el cual puede ser costo, distancia, tiempo, etc.
La Programación Entera permite abordar de forma eficiente este tipo de problemas, en especial cuando la cantidad de nodos y rutas posibles resulta ser un número significativo. Utilizar en estos casos un enfoque intuitivo de resolución es tedioso y de no ser exhaustivo no garantiza la identificación de la mejor alternativa o ruta.
Consideremos el siguiente diagrama donde los números asignados a cada uno de los arcos representan la distancia en kilómetros de un nodo a otro. Se desea encontrar la ruta con la distancia mínima para ir del nodo 1 al nodo 8.
El tamaño reducido de la red anterior permite encontrar el camino más corto simplemente enumerando las distintas alternativas que comenzando en el nodo 1 permita llegar al nodo 8. De esta forma las rutas posibles son:
Ruta 1-2-5-7-8: 4+8+17+9=38[km]
Ruta 1-3-4-7-8: 3+12+20+9=44[km]
Ruta 1-3-4-6-8: 3+12+2+22=39[km]
Ruta 1-3-4-8: 3+12+15=30[km]
Ruta 1-3-6-8: 3+4+22=29[km]
La ruta o camino más corto esta dada por la secuencia 1-3-6-8 con una distancia total de 29[km].
A continuación se formula un modelo de Programación Entera que permite extender este tipo de resultados a un problema de estas características:
Variables de Decisión:
Función Objetivo: Minimizar la distancia total en [km] dada por la siguiente expresión:
Restricciones:
La primera restricción (1) garantiza que sólo un nodo (entre el 2 y el 3) pueda ser el que se visita a continuación de comenzar en el nodo 1.
La restricción (2) determina que si se visito el nodo 2 después del nodo 1, entonces necesariamente el nodo 5 será visitado después del nodo 2.
La restricción (3) permite verificar que si el nodo 3 fue visitado luego del nodo 1, entonces a continuación se visita el nodo 4 o el nodo 6 (sólo uno de ellos).
La restricción (4) establece que si el nodo 5 fue visitado luego del nodo 2, entonces el nodo 7 debe ser visitado luego del nodo 5.
La restricción (5) garantiza que si el nodo 4 fue visitado luego del nodo 3, entonces a continuación se visita uno de los siguientes nodo: 7, 8 o 6.
La restricción (6) indica que si el nodo 6 fue visitado inmediatamente luego de estar en el nodo 3 o 4, a continuación se visita el nodo 8.
La restricción (7) determina que si el nodo 7 fue visitado inmediatamente luego de estar en el nodo 4 o 5, a continuación se visita el nodo 8.
Finalmente la restricción (8) asegura que ya sea el nodo 7, 4 o 6 sea el último en visitar previo a terminar la ruta en el nodo 8.
Al implementar en Solver el problema del Camino más Corto o Ruta Mínima anterior se alcanzan los siguientes resultados:
Donde se corrobora que la ruta más corta (solución óptima) corresponde al camino 1-3-6-8 con una distancia total de 29[km] (valor óptimo).
El tutorial a continuación disponible en nuestro canal de Youtube muestra en detalle la implementación y resolución computacional de este problema:
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 
