Problemas de flujo de costo mínimo
http://www.academia.utp.ac.pa/humberto-alvarez/investigacion-de-
operaciones-1
Introducción
◼ El problema del flujo de costo mínimo ocupa un lugar
central entre los modelos de optimización de redes, tanto
porque abarca una clase tan amplia de aplicaciones
como porque puede resolverse de manera
extremadamente eficiente.
◼ Considera flujos a través de una red con capacidades
limitadas.
◼ La razón por la que el problema del flujo de costo
mínimo se puede resolver de manera tan eficiente es que
puede formularse como un problema de programación
lineal, de modo que pueda resolverse mediante el
método simplex.
. R. Alvarez A., Ph. D.
Las redes:
◼ Las redes están presentes
en diferentes lugares en la
vida real: redes de
transporte, flujo eléctrico y
comunicaciones, por
ejemplo.
H. R. Alvarez A., Ph. D.
Las redes:
◼ También son ampliamente
utilizadas para representar
problemas tales como
problemas de producción,
distribución, localización de
facilidades, etc.
H. R. Alvarez A., Ph. D.
Las redes:
◼ Las redes proveen una poderosa
ayuda visual y conceptual para
explicar las diferentes relaciones
entre componentes de un
sistema.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
Conceptos básicos
◼ Una red consiste en conjunto definido
de puntos y líneas que unen ciertos
pares de puntos.
◼ Se conoce como nodos (vértices) a
dichos nudos y como arcos a las
líneas que los unen.
◼ Se dice que un arco es dirigido si
permite flujo en una sola dirección,
de lo contrario se conoce como un
arco no dirigido o ligadura. Por
convención, el arco se denomina en
función a su dirección. Así, en la
figura el arco 3-2 indica que su
dirección se del nodo 3 al nodo 2 y no
viceversa. Una red que tiene
solamente arcos dirigidos se conoce
como red dirigida, de lo contrario se
conocerá como una red no dirigida.
Conceptos básicos
◼ Una trayectoria entre dos nodos es una sucesión de arcos distintos.
◼ Una trayectoria dirigida del nodo i al nodo j es una sucesión de
arcos cuya dirección es hacia el nodo j.
◼ Un ciclo es una trayectoria que comienza y termina en el mismo nodo.
En una red dirigida, un ciclo puede ser o no dirigido, según la
trayectoria en cuestión.
◼ Se dice que dos nodos están conectados si la red contiene al menos
una trayectoria no dirigida entre ellos.
◼ Una red conectada es una red en la que cada par de nodos está
conectado.
Conceptos básicos
◼ Una trayectoria entre dos nodos es una sucesión de arcos distintos.
2
3
1
◼ Una trayectoria dirigida del nodo i al nodo j es una sucesión de
arcos cuya dirección es hacia el nodo j.
3
1
2
Conceptos básicos
◼ Un ciclo es una trayectoria que comienza y termina en el mismo nodo.
En una red dirigida, un ciclo puede ser o no dirigido, según la
trayectoria en cuestión.
3 ▪ Se dice que dos nodos están
1 4 conectados si la red contiene
8 al menos una trayectoria no
2 dirigida entre ellos.
5 ▪ Una red conectada es una red
7 en la que cada par de nodos
6 está conectado.
Conceptos básicos
◼ La capacidad de un arco es la cantidad neta máxima de
flujo que puede circular en arco dirigido.
◼ Un nodo generador de flujo se conoce como nodo fuente
u origen.
◼ Un nodo fuente tiene la propiedad de que el flujo que sale
del nodo supera al que entra e él.
◼ Un nodo demanda o destino es aquel en el que el flujo
que llega excede al que sale.
◼ Un nodo de trasbordo o intermedio satisface la
conservación de flujo, o sea, el flujo que sale es igual al
que entra.
Árbol de expansión
◼ Un árbol es una red
conectada para algún
subconjunto de nodos que
no contiene ciclos.
◼ Un árbol de expansión, es
una red que conecta los n
nodos sin formar ciclos.
◼ El número mínimo de ramas
o arcos necesarios para
conectar todos los nodos es
n-1.
Árbol de expansión mínima
◼ Dado un grafo no conectado G = (V,E), con pesos ci,j
para todos los ejes en E, encontrar un árbol de
expansión GT = (VT, ET ) para un mínimo de peso.
◼ Dados los nodos de una red, se conocen los enlaces
potenciales y la distancia o peso positivo de cada uno.
◼ El problema consiste en diseñar una red con suficientes
enlaces de tal manera que exista un camino factible
entre cualquier par de nodos.
◼ El objetivo es encontrar dicho árbol de expansión de tal
menera que tenga el mínimo costo.
Formulación
H. R. Alvarez A., Ph. D.
Ejemplo
◼ La Administración de una reserva forestal necesita
determinar los caminos bajo los cuales se deben tender
las líneas telefónicas para conectar las estaciones de los
guardaparques con una longitud mínima de cables de
acuerdo a la figura siguiente:
Formulación y solución en MPL
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
Algoritmo de Kruskal
En una red conectada, no dirigida:
1. Elegir un nodo cualquiera
2. Unir este nodo a un nodo de distancia minima.
3. Seleccionar el siguiente nodo de distancia mínima,
siempre y cuando no forme un ciclo.
4. Continuar hasta formar el árbol con n-1 ramas y
que cubra todos los nodos.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
Problemas de flujo de costo
mínimo
Planteamiento del problema
◼ Son problemas de programación lineal con
ciertas estructuras especiales
◼ Permiten ser trabajados con algoritmos
especiales
◼ Aprovechan su estructura para aproximarlos a
redes
◼ Su estructura permite la solución de grandes
problemas de manera relativamente sencilla
H. R. Alvarez A., Ph. D.
Elementos de un problema de flujo
de costo mínimo
◼ Se tiene un número dado de fuentes y
destinos de transacciones
◼ Cada fuente y destino tiene una capacidad
máxima de envío y recibo
◼ Se pueden tener nodos intermedios
◼ Se tienen arcos que:
◼ Tienen una capacidad máxima de flujo
◼ Tienen un costo asociado a una unidad de flujo
H. R. Alvarez A., Ph. D.
Elementos de un problema de flujo
de costo mínimo
Arcos
Destinos
Fuentes
Nodos
H. R. Alvarez A., Ph. D.
Problemas típicos
◼ Costo Mínimo
◼ Ruta Más Corta
◼ Flujo máximo
◼ Asignación
◼ Transporte
◼ Trasbordo
◼ Problema del agente viajero
Formulación del problema de flujo de
costo mínimo:
◼ Considere una red dirigida y conectada,
donde esta incluye al menos un nodo
de oferta y otro de demanda:
◼ La variable de decisión será:
xij: será el flujo a través del arco i→j
H. R. Alvarez A., Ph. D.
Formulación General:
◼ Incluye la siguiente información:
cij: es el costo de enviar una unidad a través del arco i →j
uij: les la capacidad del arco i →j
bi: es el flujo generado en el nodo i
◼ El valor de bi depende de la naturaleza del nodo :
bi > 0, si i es un nodo de oferta
bi < 0, si i es un nodo de demanda
bi = 0, si i es un nodo de trasbordo
◼ El objetivo es minimizar el costo total de enviar el suministro
disponible a través de la red a fin de satisfacer una demanda
dada.
◼ En una solución factible, el flujo total generado en los nodos de
oferta iguala al flujo total consumido por los nodos de demanda.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
Una condición necesaria para la factibilidad de estos problemas es que:
En otras palabras, el flujo total generado en los nodos de suministro debe ser igual a la
demanda total
H. R. Alvarez A., Ph. D.
Ejemplo:
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
MPL formulation and solution
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
𝑀𝑖𝑛 𝑍 = 4𝑇𝐶 + 7𝑇𝐵 + 5𝐷𝐶 + 7𝐷𝐵 + 6𝐶𝑁 + 4𝐶𝐹 + 5𝐶𝑆 + 2𝐵𝑁 + 3𝐵𝐹 + 4𝐵𝑆
𝑆𝑢𝑗𝑒𝑡𝑜 𝑎:
𝑇𝐶 + 𝑇𝐵 ≤ 800
𝐷𝐶 + 𝐷𝐵 ≤ 700
𝐶𝑁 + 𝐶𝐹 + 𝐶𝑆 − 𝑇𝐶 − 𝐷𝐶 = 0
𝐵𝑁 + 𝐵𝐹 + 𝐵𝑆 − 𝑇𝐵 − 𝐷𝐵 = 0
−𝐶𝑁 − 𝐵𝑁 ≥ −450
−𝐶𝐹 − 𝐵𝐹 ≥ −350
−𝐶𝑆 − 𝐵𝑆 ≥ −300
∀ 𝑅𝑢𝑡𝑎𝑠 ≥ 0
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
Con un destino o demanda ficticio
H. R. Alvarez A., Ph. D.
El problema de Asignación
El problema de asignación
◼ Supóngase que se tienen n centros de trabajo
y n posibles asignaciones, cada una de las
cuales puede ser realizada por cualquiera de
los n centros de trabajo.
◼ Supóngase además que existe un costo
asociado ci,j que resulta de asignar un trabajo
i a un centro de trabajo j.
◼ En este caso, la asignación de cada trabajo se
realizará solamente a un solo centro de tal
manera que el costo total de la asignación de
los trabajos sea mínimo.
H. R. Alvarez A., Ph. D.
Formulación general
min .Z = C
i j
i, j X i, j
s.a. :
Xi
i, j =1 j = 1, 2, ..., n
Xj
i, j = 1 i = 1, 2, ..., n
1 si trabajo i se asigna a centro j
X i, j =
0 otra cosa
H. R. Alvarez A., Ph. D.
Solución
◼ Método fila columna – o método
Húngaro
◼ Método SIMPLEX o programación
entera binaria
H. R. Alvarez A., Ph. D.
El Método Húngaro
◼ La más conocida técnica de solución para el problema de asignación pura es el
método húngaro, desarrollado a partir de los trabajos de Köning y Egerváry en
1916
◼ Es un algoritmo de optimización combinatoria que resuelve el problema en
tiempo polinomial.
◼ Fue desarrollado y publicado por Harold Kuhn en 1955. Es por esto que se le
conoce también como el algoritmo de Kuhn-Munkres o el algoritmo de
asignación de Munkres
◼ Este método utiliza la propiedad de reducción de matrices para reducir la matriz
original de costo, hasta que los costos cij asociados con la asignación óptima,
sean cero y todos los otros costos sean no negativos.
H. R. Alvarez A., Ph. D.
Coefficientes de costos del problema
H. R. Alvarez A., Ph. D.
Ejemplo
◼ La administración de cierto restaurante ha
decidido dirigir diferentes clientes a diferentes
áreas de servicio. La administración sabe que
las diferentes combinaciones de
cliente/mesero hacen variar los costos de
servicio a causa de las características del
cliente y las habilidades de los diferentes
meseros. A continuación se tiene la
información de costos por cliente y mesero:
H. R. Alvarez A., Ph. D.
Costo por mesero
Costo de Meseros
Cliente 1 2 3
1 12.90 11.90 12.10
2 15.30 15.50 14.30
3 11.90 13.90 13.00
H. R. Alvarez A., Ph. D.
One formulation in MPL
H. R. Alvarez A., Ph. D.
Solución
H. R. Alvarez A., Ph. D.
Matriz de no-ceros en MPL
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
El problema de transporte
El Problema de Transporte
◼ Busca optimizar la satisfacción de
demandas de destinos a través de
oferta de orígenes.
◼ Se optimiza en base a:
◼ Distancias
◼ Tiempos
◼ Costos
H. R. Alvarez A., Ph. D.
Objetivo
◼ Su objetivo es el de analizar la manera
óptima de distribuir un producto desde un
grupo de orígenes o centros de suministros a
un grupo de centros de recibo o destinos de
tal manera que se minimice el costo total de
la política.
◼ Cada fuente tiene cierta capacidad de
suministro a ser distribuida, mientras que
cada destino tiene cierta capacidad de
demanda a ser satisfecha.
H. R. Alvarez A., Ph. D.
Supuestos:
◼ El Supuesto de los requerimientos: debe existir un balance
entre todo el suministro s de las diferentes fuentes y la
demanda total d de los destinos.
◼ La propiedad de la solución factible: en el problema de
trasnporte habrá una solución factible sí y solo sí s = d
◼ El supuesto de costos: el costo de distribuir unidades de
cualquier fuente a cualquier destino es directamente
proporcional al número de productos distribuídos.
◼ El modelo: cualquier problema puede ser visto como este caso
si puede ser descrito completamente en términos de una tabla
de parámetros que satisfaga tanto el supuesto de los
requirimientos como el de los costos.
H. R. Alvarez A., Ph. D.
Descripción
◼ Un conjunto A de m puntos de origen de
donde un bien es enviado. El punto i puede
suministrar hasta si unidades.
◼ Un conjunto de n puntos de demanda donde
llega un bien. Los puntos de demanda j
pueden recibir por lo menos dj bienes.
◼ Cada unidad enviada del punto i al punto j
incurre en un costo unitario cij.
H. R. Alvarez A., Ph. D.
Tabla de parámetros.
H. R. Alvarez A., Ph. D.
Formulación general
If Será un problema balanceado
H. R. Alvarez A., Ph. D.
La formulación general para el problema
balanceado
El requerimiento es que la demanda sea igual a la oferta. De otra
manera habrá que crear puntos de oferta o demanda ficticios.
H. R. Alvarez A., Ph. D.
Representación de la red
H. R. Alvarez A., Ph. D.
Solution
◼ Método simplex
◼ Algoritmo de transporte
◼ Tableau inicial
◼ Solución
◼ Prueba de optimalidad
◼ Redistribución de envios
H. R. Alvarez A., Ph. D.
Ejemplo: Se tiene la siguiente
red de distribución (Hillier)
Es necesario encontrar la política óptima de transporte
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
Solución
La red del sistema
H. R. Alvarez A., Ph. D.
Las ecuaciones
H. R. Alvarez A., Ph. D.
Solución: una formulación MPL
H. R. Alvarez A., Ph. D.
Solución: variables
H. R. Alvarez A., Ph. D.
Solución: restricciones
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
El problema de la ruta más corta
H. R. Alvarez A., Ph. D.
◼ Considera una red DIRIGIDA O NO DIRIGIDA
y conectada, con dos nodos llamados origen
y destino.
◼ Asociado con cada arco no dirigido hay una
distancia no negativa.
◼ El objetivo es encontrar la ruta más corta del
origen al destino.
Formulación
H. R. Alvarez A., Ph. D.
Ejemplo
MPL formulation
and solution
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
Todos los días, Ray Design debe transportar camas,
sillas y otros muebles de la fábrica al almacén; necesita
pasar por varias ciudades y Ray desea encontrar la ruta
con la distancia más corta. La red de carreteras se
muestra en la figura, donde la distancia está dada en
km.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
El problema del flujo máximo
H. R. Alvarez A., Ph. D.
El problema del flujo máximo
◼ Todo flujo a través de una red dirigida e interconectada se
origina en el nuede fuente y termina en el nodo destino.
◼ Todos los otros nodos serán nodos de trasbordo.
◼ El flujo a través del arco es permitido en una dirección, donde el
máximo flujo permitido está dado por la capacidad del arco.
◼ En la fuente, todos los arcos salen. En el destino, todos los
arcos llegan.
◼ El objetivo es maximizar el flujo total de la fuente al destino.
LP formulation
H. R. Alvarez A., Ph. D.
Ejemplo
1 2 3 4 5 6 7
1
2
3
4
5
6
7
Formulación y solución
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
PetroChem, una refinería de petróleo localizada en el río Mississippi al sur de Baton Rouge,
Luisiana, está diseñando una nueva planta para producir combustible diesel. La figura
muestra la red de los principales centros de procesamiento y la tasa del flujo existente (en
miles de galones de combustible). La gerencia de PetroChem busca determinar la cantidad
máxima de combustible que puede fluir a través de la planta, del nodo 1 al nodo 7.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
H. R. Alvarez A., Ph. D.
