Optimización en Redes

Vista previa del material en texto

Optimización en Redes 
Cristián García-Campo 
Universidad de los Andes 
Optimización 
2° semestre 2018 
Optimización–Prof. Cristian García-Campo 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Contexto 
Los modelos de redes son representaciones gráficas resumidas en una unidad 
denominada GRAFO que contiene la interacción de 3 elementos gráficos: Nodos, 
Arcos y Flujos. Esta representación gráfica se traduce en un modelo de PM que 
puede ser resuelto utilizando las técnicas que aprendimos anteriormente en el curso 
La optimización de modelos de redes tiene un amplio uso en la industria del 
transporte, telecomunicaciones, finanzas, servicios básicos (electricidad, agua, gas), 
recursos humanos, etc. 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Contexto 
Existe una serie de problemas que usualmente pueden Modelarse Utilizando Redes 
( o Grafos ) entre los más comunes se encuentran: 
 
 
Problema del transporte 
Problema de asignación 
Problema del camino más corto 
Problema del Flujo máximo 
Problema de Flujo de costo mínimo 
Planificación de Proyectos 
El problema del agente viajero TSP 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Ejemplo 
Problema del transporte 
Un distribuidor que tiene m depósitos con un abastecimiento de productos Li en ellos, debe 
enviar dichos productos a n centros geográficamente dispersos, cada uno con una demanda de 
clientes dada Dj, la cual debe ser cubierta. 
El objetivo es determinar el mínimo costo posible de transporte dados los costos Cij por unidad 
de transportar entre el depósito i y el centro de demanda j. 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Definiendo: 
 
Xij: cantidad de bienes (o personas, etc) transportadas desde el 
nodo i al nodo jc 
 
𝑀𝑖𝑛 𝑐𝑖,𝑗
𝑗𝑖
∗ 𝑥𝑖,𝑗 
Sujeto a: 
 𝑥𝑖,𝑗
𝑗
≤ 𝑠𝑖 𝑝𝑎𝑟𝑎 𝑖 = 1,2, …𝑛 
 𝑥𝑖,𝑗
𝑖
≥ 𝐷𝑖 𝑝𝑎𝑟𝑎 𝑖 = 1,2, …𝑛 
𝑥𝑖,𝑗 ≥ 0 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Ejemplo 
Problema de asignación 
Se tienen un grupo n de “hombres” aplicando para n “tareas”, o n “trabajos” aplicando a n 
“máquinas” y el costo Cij de asignar el hombre (o trabajo) i a la tarea (o máquina) j es conocido. 
El objetivo es asignar una tarea a cada hombre (o un trabajo a una máquina) de tal forma de 
alcanzar el costo total mínimo posible. 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Definiendo: 
 
Xij: 
•1 si la tarea (o trabajo) i es asignada al hombre j (o máquina), 
• 0 en caso contrario 
 
La forma genérica del problema de asignación es: 
𝑀𝑖𝑛 𝑐𝑖,𝑗
𝑗𝑖
∗ 𝑥𝑖,𝑗 
Sujeto a: 
 𝑥𝑖,𝑗
𝑗
= 1 ∀𝑖 
 𝑥𝑖,𝑗
𝑖
= 1 ∀𝑗 
𝑥𝑖,𝑗 ∈ 0,1 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Ejemplo 
Problema del camino más corto 
Determinar la mejor manera de cruzar una red para encontrar la forma más económica posible 
desde un origen a un destino dado. Existe un costo Cij asociado con cada arco (i a j) en la red. 
Formalmente, el problema del camino más corto (CC) es encontrar el camino más corto desde el 
nodo de comienzo 1 hasta el nodo final m. 
 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Definiendo: 
 
Xij: 1 si el tramo ij pertenece al camino más corto, 0 en caso contrario. 
 
La forma genérica del camino más corto: 
𝑀𝑖𝑛 𝑐𝑖,𝑗
𝑗𝑖
∗ 𝑥𝑖,𝑗 
Sujeto a: 
 𝑥𝑖,𝑗
𝑗
= 1 𝑝𝑎𝑟𝑎 𝑖 = 𝑛𝑜𝑑𝑜 𝑜𝑟𝑖𝑔𝑒𝑛 
 𝑥𝑗,𝑚
𝑗
= 1 𝑝𝑎𝑟𝑎 𝑚 = 𝑛𝑜𝑑𝑜 𝑓𝑖𝑛𝑎𝑙 
 𝑥𝑗,𝑖
𝑗
− 𝑥𝑖,𝑗
𝑗
= 0 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑖 = 𝑛𝑜𝑑𝑜 𝑖𝑛𝑡𝑒𝑟𝑚𝑒𝑑𝑖𝑜 
𝑥𝑖,𝑗 ∈ 0,1 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Ejemplo 
Problema del Flujo máximo 
En una red con flujo de capacidades en los arcos, determinar el flujo máximo posible proveniente de l origen 
de forma tal de saturar las capacidades de flujos de los arcos. 
Considere una red con m nodos y n arcos con un flujo simple de bienes. Denote el arco de flujo (i a j) como Xij. 
Asociamos cada arco a una capacidad de flujo, Kij. Encontrar el flujo total máximo en la red, F, del nodo 1 al 
nodo m. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
En algunas rutas los flujos pueden tomar ambas direcciones. La capacidad que puede ser enviada a una 
dirección en particular también es mostrada en cada ruta. En la figura los arcos son no dirigidos, y junto a 
cada nodo se presenta la capacidad máxima de salida de cada nodo desde cada nodo vecino. 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Definiendo: 
 
Xij: cantidad de bienes (o personas, etc) transportadas a través del tramo i-j. 
 
La forma genérica del problema de flujo máximo es: 
𝑴𝒂𝒙 𝑭 
Sujeto a: 
 𝑥𝑖,𝑗
𝑗
− 𝐹 = 0 𝑝𝑎𝑟𝑎 𝑖 = 𝑛𝑜𝑑𝑜 𝑑𝑒 𝑜𝑟𝑖𝑔𝑒𝑛 
 𝑥𝑗,𝑚
𝑗
− 𝐹 = 0 𝑝𝑎𝑟𝑎 𝑚 = 𝑛𝑜𝑑𝑜 𝑓𝑖𝑛𝑎𝑙 
 𝑥𝑗,𝑖
𝑗
− 𝑥𝑖,𝑗
𝑗
= 0 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑖 = 𝑛𝑜𝑑𝑜 𝑖𝑛𝑡𝑒𝑟𝑚𝑒𝑑𝑖𝑜 
𝑥𝑖,𝑗 ≤ 𝐾𝑖,𝑗 
𝑥𝑖,𝑗 ≥ 0 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Ejemplo 
Problema de Flujo de costo mínimo 
Es el caso más general, pues Considera: 
1) Flujos en las redes con capacidades. 
2) costo por flujo hacia un arco. 
3) Permite múltiples orígenes y destinos. 
El problema es minimizar el costo total sujeto a la disponibilidad y la demanda de 
algunos nodos, y de la capacidad superior de flujo a través de cada arco. 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Definiendo: 
Xij: cantidad de bienes (o personas, etc) transportadas a través del tramo i-j. 
La forma genérica del problema de costo mínimo es: 
 
𝑀𝑖𝑛 𝑐𝑖,𝑗
𝑗𝑖
∗ 𝑥𝑖,𝑗 
Sujeto a: 
 𝑥𝑗,𝑖
𝑗
+ 𝑂𝑖 = 𝑥𝑖,𝑗
𝑗
+ 𝐷𝑖 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑖 
𝑥𝑖,𝑗 ≤ 𝐾𝑖,𝑗 
𝑥𝑖,𝑗 ≥ 0 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Ejemplo 
Planificación de Proyectos 
El Método de Camino (o trayectoria) Crítico (MCC) intenta analizar la planificación de 
proyectos. Esto posibilita un mejor control y evaluación del proyecto. 
 
Por ejemplo, queremos saber ¿Cuánto tiempo durará el proyecto?, ¿Cuándo se estará 
listo para comenzar una tarea en particular? ¿Qué tareas deben ser aceleradas de forma 
tal de terminar el proyecto antes? La ruta crítica será la de máxima duración. Es similar al 
problema de camino más corto, pero busca el camino más Largo. 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Definiendo: 
 
Xij: 1 si el tramo ij pertenece a la ruta crítica, 0 en caso contrario. 
 
La ruta crítica de un proyecto se obtiene de: 
𝑀𝑎𝑥 𝑑𝑖,𝑗
𝑗𝑖
∗ 𝑥𝑖,𝑗 
Sujeto a: 
 𝑥𝑖,𝑗
𝑗
= 1 𝑝𝑎𝑟𝑎 𝑖 = 𝑛𝑜𝑑𝑜 𝑑𝑒 𝑜𝑟𝑖𝑔𝑒𝑛 
 𝑥𝑗,𝑖
𝑗
= 1 𝑝𝑎𝑟𝑎 𝑖 = 𝑛𝑜𝑑𝑜 𝑓𝑖𝑛𝑎𝑙 
 𝑥𝑗,𝑖
𝑗
− 𝑥𝑖,𝑗
𝑗
= 0 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑖 = 𝑛𝑜𝑑𝑜 𝑖𝑛𝑡𝑒𝑟𝑚𝑒𝑑𝑖𝑜 
𝑥𝑖,𝑗 ∈ 0,1 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Ejemplo 
El problema del agente viajero TSP 
Un vendedor debe visitar las ciudades 1, 2,..n, y su viaje comienza y debe finalizar en 
Ciudad Hogar. dij es el costo (o distancia, o riesgo, etc) de viajar de la ciudad i a la ciudad 
j. El problema es determinar una ruta óptima para viajar por todas las ciudades de tal 
forma que el costo sea mínimo. 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Definiendo: 
Xij: 1 si el tramo ij pertenece a la ruta del vendedor viajero, 0 en caso contrario. 
 
La forma genérica del problema del vendedor viajero: 
𝑀𝑖𝑛 𝑑𝑖,𝑗
𝑗𝑖
∗ 𝑥𝑖,𝑗 
Sujeto a: 
 𝑥𝑖,𝑗
𝑗
= 1 ∀𝑖 
 𝑥𝑗,𝑖
𝑗
= 1 ∀𝑖 
𝑥𝑖,𝑗 ∈ 0,1 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Ejemplo 
Modelación en Redes 
Una red con N nodos puede tener fácilmente N(N-1)/2 arcos no direccionales y N! 
posibles soluciones. Este problema crece factorialmente a medida que crece N lo que lo 
convierte en uno de los problemasmás difíciles de computar. ( Problema NP-Completo o 
NP-Hard ) 
 
Uno de los problemas del Milenio, que tiene una recompensa de 1 millón de dólares para 
quien lo resuelva, esta asociado a los problemas de tipo NP-Completo 
 
Aquí un articulo de Wikipedia que podría parecerles interesante: 
 
https://es.wikipedia.org/wiki/Problemas_del_milenio 
 
 
https://es.wikipedia.org/wiki/Problemas_del_milenio
https://es.wikipedia.org/wiki/Problemas_del_milenio
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Problema 
Construya un Modelo de PM que represente y sea capaz de resolver el Problema de 
Flujo de costo mínimo representado en el siguiente GRAFO ( Utilice la notación 
ampliada) 
 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Construya un Modelo de PM que represente y sea capaz de resolver el Problema de 
Flujo de costo mínimo representado en el siguiente GRAFO ( Utilice la notación 
ampliada) 
 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Problema 
Coopedala es una Cooperativa Agrícola dedicada al desarrollo de la agricultura en la X 
Región de los Lagos y cuenta con 4 puntos de venta de forraje para animales ubicados 
en las comunas de Osorno, Llanquihue, Puerto Varas y Puerto Montt, a fin de proveer 
de mejor manera a sus puntos de venta, la empresa cuenta con 3 centros de acopio 
ubicados en los kilómetros 950, 999, y 1.030 de la ruta 5 sur, según el modelo de 
negocios no está permitido que un punto de venta abastezca a otro punto de venta, ni 
acumular productos de un período para otro. La demanda en toneladas por productos 
agrícolas en cada unos de los centros de venta se resume en la tabla N1, al igual que la 
capacidad de almacenamiento de sus 3 centros de acopio en toneladas, y el respectivo 
costo de transporte por tonelada. 
 
1) Construya un grafo que represente la situación logística de la empresa Coopedala. ¿ 
a cual de los 7 casos estudiados anteriormente se parece esta situación? 
 
2) Construya el Modelo Programación Matemática que permita minimizar los costos 
de transporte. 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
El problema anterior tiene solución X11= 600 X22=400 X23=500 X34=600 X14=100. 
Suponga ahora que este debe ser reformulado debido al hecho que el cliente de Puerto 
Montt inesperadamente modificó su pedido reduciéndolo de 700 ton a 500 ton . El 
problema surge del hecho de que los centros de distribución no pueden almacenar el 
exceso de oferta y lo que sobre debe ser desechado con un costo específico. 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Problema 
Chile Expreso es una empresa de logística que se dedica al transporte de encomiendas, para lo cual 
cuenta con 2 centros de acopio donde se reciben los productos y 5 oficinas comerciales las cuales 
entregan las encomiendas a los clientes. Los centros de acopio de encomiendas se encuentran ubicados 
en las comuna de Lampa en las 
inmediaciones del Aeropuerto SCL mientras que el segundo centro de acopio se localiza en la comuna de 
Independencia el cual recibe las encomiendas desde los puertos de Valparaíso y San Antonio. Las 
oficinas comerciales se encuentran ubicadas en las comunas de Quilicura, Providencia, La Reina, Stgo. 
Centro y Maipú Tanto los centros de acopio como las oficinas de ventas no pueden acumular 
encomiendas de un día para otro. 
El requerimiento de encomiendas para el día Jueves 5 de Mayo de 2016 indica lo siguiente: 200 
encomiendas llegarán vía aérea al centro de acopio de Lampa, mientras que 500 encomiendas llegarán 
vía terrestre al centro de acopio de Independencia. Los requerimientos de clientes para ese día son los 
siguientes: Providencia 150, La reina 125, Maipú 195, Quilicura 90, Stgo C. 140. La Matriz de costo de 
transporte calibrada para el día 5 de Mayo de 2016 indica los siguientes precios por ruta y no existe 
restricciones de capacidad de transporte por ruta. Asuma que el costo de transporte entre rutas no 
definidas por la matriz son suficientemente grande para no ser considerado en la solución óptima. 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Problema 
1) Construya el grafo que representa la situación 
logística de Chile Expreso. Considere un grafo con 
arcos direccionados. 
 
2) A partir del problema original y de la información 
obtenida a partir del Grafo construya un modelo de 
MP que permita encontrar la solución optima del 
problema. 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Analizamos la entrada y salida de flujos en los distintos nodos, esta información nos permitirá generar 
las restricciones del problema. 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Solución 
Optimización–Prof. Cristian García-Campo 
Optimización en Redes 
Bonus Track 
Encuentre, por inspección, el camino mas corto entre el nodo 1 y el nodo 6. Se le 
interesa profundizar en el tema averigüe sobre el algoritmo de Dijkstra. 
 
Optimización en Redes 
Cristián García-Campo 
Universidad de los Andes 
Optimización 
2° semestre 2018 
Optimización–Prof. Cristian García-Campo