problemas de redes

Universidad Nacional de Colombia
Sede Medellín

Formulación de problemas
de optimización
de redes
Profesora: Patricia Jaramillo A. Ph.D
1

Una red
consiste en

Nodos

(Vértices)

Arcos

(ligaduras,
aristas o
ramas)
2

Nodos

Arcos

Flujo

Ciudades

Carreteras

Aeropuertos

Rutas aéreas.

Aviones

Puntos de
conmutación

Cables, canales

Mensajescalles

personas

Estaciones de
autobuses
sitios

Rutas de transporte
de mercancía

Vehículos

mercancía

3

Una red con n nodos podría tener tantos
arcos como n! /[(n-2)! 2!] = n(n-1)/2.
Si están dirigidos, este número pudiese ser
doble. Este enorme número de arcos
posibles es una de las razones del porque
existen soluciones de algoritmos
especiales para problemas de redesparticulares
4

Problemas típicos de redes
Los siguientes problemas no son aplicables exactamente
en problemas reales, pero sirven de base para
afrontar estos problemas configurando híbridos entre
ellos y complementándolos con objetivos o
restricciones adicionales:
1.
2.
3.
4.
5.
6.
7.

Problema del transporte
Problema de asignación
Problema del camino más corto
Problema delFlujo máximo
Problema de Flujo de costo mínimo
Planificación de proyectos
El problema del agente viajero TSP
5

1. Problema del transporte
El problema de transporte es aplicable a la
planificación logística de intercambio local
de bienes o personas, con el fin de tener
bajos costos y mejor calidad.

6

1. Problema del transporte
Un distribuidor que tiene m depósitos con unabastecimiento de productos Si 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.

7

1. Problema del transporte
En la figura se presentanvalores de Cij

8

1. Problema del transporte
Definiendo:
Xij: cantidad de bienes (o personas, etc)
transportadas desde el nodo i al nodo jc

9

1. Problema del transporte
La forma genérica del problema del transporte es:

Min ∑∑ Cij xij
i

Sujeto a:

j

∑ xij ≤ si

para i = 1,2,.....,m.

∑ xij ≥ D j

para j = 1,2,.....,n.

j

i

xij ≥ 0

10

2. Problema deAsignació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.

11

2. Problema de Asignación
En la figura sepresentan los valores de cij sobre los arcos

12

2. Problema de Asignación
Definiendo:
Xij:
• 1 si la tarea (o trabajo) i es asignada al
hombre j (o máquina),
• 0 en caso contrario

13

2. Problema de Asignación
La forma genérica del problema de asignación es:

Min ∑∑ Cij xij
i

Sujeto a:

j

∑ xij = 1

para i = 1,2,.....,n.

∑ xij = 1

para j = 1,2,.....,n.

j

ixij ∈ [ 0 ,1]
14

3. El Problema del Camino más Corto
Determinar la mejor manera de cruzar una red para encontrar la forma
mas 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.

15

3.El Problema del Camino más Corto
Definiendo:
• Xij: 1 si el tramo ij pertenece al camino
más corto, 0 en caso contrario

16

3. El Problema del Camino más Corto
La forma genérica del problema del camino más corto
es:

Min ∑∑ Cij xij
i

Sujeto a:

∑x

=1

∑x

=1

ij

j

para i = nodo origen

j

jm

para m= nodo final

j

∑x −∑x
ji

j

ij

=0

para...