Ingenieria industrial

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

(Vértices)

Nodos

(ligaduras, aristas o ramas)
2

Arcos

Nodos Ciudades Aeropuertos Puntos de conmutación Estaciones de autobuses sitios

Arcos Carreteras Rutas aéreas. Cables, canales

Flujo

Vehículos AvionesMensajes personas mercancía

calles Rutas de transporte de 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 redes particulares
4

Problemas típicos de redes
Lossiguientes 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 del Flujo máximo Problema de Flujo de costo mínimo Planificación deproyectos 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 un abastecimiento de productos Si en ellos, debe enviar dichos productos a n centrosgeográ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 presentan valores de Cij

8

1. Problema del transporte
Definiendo: Xij: cantidad debienes (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 j
Sujeto a:

∑ xij ≤ si
∑ xij ≥ D j
i

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

j

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

xij ≥ 0

10

2. 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.

11

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

12

2. Problema de Asignación
Definiendo: Xij: • 1 si latarea (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 j
Sujeto a:

∑ xij = 1
∑ xij = 1
i

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

j

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

xij ∈ [ 0 ,1]
14

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

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

Min ∑∑ Cij xij
i j

Sujeto a:

∑x

ij

=1

para i = nodo origen para m= nodo final

∑x
j j

j

jm

=1 =0

∑x −∑x
ji j

ij

para todo i = nodo intermedio

xij ∈ [ 0 ,1]

17

4. Problema del Flujo Máximo
En una red con flujo de capacidades en los arcos,...