TEMA 5 Redes 1.- CONCEPTOS BÁSICOS. 5 redes.pdf · aplicación de este tipo de problemas es en...

M. Mocholí Modelización y Optimización 1

1.- CONCEPTOS BÁSICOS.Muchos problemas reales son susceptibles de ser

representados en forma de red, por este motivo comenzaremospor definir los conceptos básicos de redes y posteriormentealgunos problemas tipo, susceptibles de ser modelizados comouna red.

Una red es un conjunto de nodos N={1,2,…,n}conectados por una serie de arcos, representado por (i,j) el arcoque conecta el nodo i con el nodo j. Un ejemplo de red es unared de carreteras donde los nodos son las ciudades o pueblos ylas carreteras que los unen los arcos, aunque los arcos no tienenporqué representar necesariamente una ruta real, sino que comoveremos más adelante pueden indicar simplemente un orden deprecedencia en determinadas actividades que en este caso seríanlos nodos

TEMA 5 Redes

M. Mocholí Modelización y Optimización 2

Nodos círculosArcos (flechas) sólo es posible desplazarse en un solo sentidoAristas (líneas) es posible desplazarse en ambos sentidos (2,3), (5,6)Cada nodo podrá tener asociado un número bi que representará su:

oferta (bi<0) odemanda (bi>0)

xij representará la cantidad enviada desde el nodo i al nodo j.cij distancia del nodo i al nodo j o coste de enviar una unidad del nodo i al j

TEMA 5 Redes

1 7

2

3

4

5

6

M. Mocholí Modelización y Optimización 3

Red dirigida es una red donde sólo existen arcos, es decir, aquella en que el desplazamiento de un nodo a otro sólo es posible en un sentido.

Red no dirigida Cuando el desplazamiento entre dos nodos es posible en ambos sentidos (aristas)

TEMA 5 Redes

1 7

2

3

4

5

6

1 7

2

3

4

5

6

M. Mocholí Modelización y Optimización 4

Cadena es una sucesión de aristas adyacentes Ejemplo {(1,2),(4,2),(4,5)}

Camino (de i a j) es una sucesión de arcos {(i,k),(k,l),(l,m),….,(p,j)} en los que el nodo inicial de cada arco es el nodo final del arco que le precede. Ejemplo un camino entre el nodo 1 y el 7 es {(1,3),(3,6),(6,7)}.

todo camino es una cadena pero no toda cadena es camino

TEMA 5 Redes

1 7

2

3

4

5

6

M. Mocholí Modelización y Optimización 5

Circuito es un camino cerrado, es decir, aquel en el que el nodo inicial y final es el mismo

Ciclo es una cadena cerrada

todo circuito es ciclo, pero no al revés

TEMA 5 Redes

1 7

2

3

4

5

6

M. Mocholí Modelización y Optimización 6

Red conexa es aquella en que existe al menos una cadena que conectacada nodo con el resto de nodos

TEMA 5 Redes

1 7

2

3

4

5

6

Red no conexa

1 7

2

3

4

5

6

En adelante nos referiremos únicamente a redes conexas

M. Mocholí Modelización y Optimización 7

Árbol es una red conexa que no tiene ciclos.TEMA 5 Redes

M. Mocholí Modelización y Optimización 8

Camino más cortoEjemplo: determinar el camino más corto del nodo 1 a l 9 en la siguiente red

TEMA 5 Redes

1

72

3

4

5

6

8

98

6

6

6

5

8

88

9

7

7

9

Cij coste o distancia de desplazarse de i a j

XijЄ{0,1} indica si se va de i a j o no

M. Mocholí Modelización y Optimización 9

TEMA 5 Redes

1

72

3

4

5

6

8

98

6

6

6

5

8

88

9

7

7

9

Min Z=6x12+6x13+6x24+8x25+5x34+9x46+8x48+8x57+7x68+7x78+8x79+9x89s.a: -x12-x13 = -1

x12 - x24 - x25 = 0x13 - x34 = 0x24 + x34 - x46 - x48 = 0x25 - x57 = 0x46 - x68 = 0x57 - x78 - x79 = 0x48 + x68 + x78 - x89 = 0x79 + x89 = 1xijЄ{0,1}

M. Mocholí Modelización y Optimización 10

Planteamiento matemáticoTEMA 5 Redes

}1,0{

)3(1

)2(1,...,2

)1(1:.

·

1

1

1 1

11

1 1

ij

n

kkn

n

i

n

jKjik

n

jj

n

i

n

jijij

x

x

nKxx

xas

xcdMin

La restricción (1) obliga a tomar un arco con origen en el nodo 1 inicialLa restricción (3) obliga a elegir un arco final en el nodo finalLas ecuaciones (2) obligan a que si se llega a un nodo se salga de él y

no permiten salir de él si no se ha llegado.La condición de integridad (variables binarias), no es necesaria, dada la

unimodularidad de la matriz y que los términos independientes son enteros(valen 0 ó ±1)

M. Mocholí Modelización y Optimización 11

Gms 1TEMA 5 Redes

M. Mocholí Modelización y Optimización 12

Gms 2TEMA 5 Redes

M. Mocholí Modelización y Optimización 13

---- 34 VARIABLE X.L3 4 8 9

1 13 14 18 1

---- 34 VARIABLE Z.L = 28 DISTANCIA TOTAL

TEMA 5 Redes

M. Mocholí Modelización y Optimización 14

ALGORITMO DE FLOYD PARA REDES NO DIRIGIDAS

TEMA 5 Redes

M. Mocholí Modelización y Optimización 15

---- 33 PARAMETER D1 2 3 4 5 6

1 6 6 11 14 202 6 11 6 8 153 6 11 5 19 144 11 6 5 14 95 14 8 19 14 226 20 15 14 9 227 22 16 20 15 8 148 19 14 13 8 15 79 28 23 22 17 16 16

+ 7 8 91 22 19 282 16 14 233 20 13 224 15 8 175 8 15 166 14 7 167 7 88 7 99 8 9

TEMA 5 Redes

M. Mocholí Modelización y Optimización 16

PROBLEMA DEL FLUJO DE COSTE MÍNIMOEste problema es una generalización del problema del transporte contrasbordo.

Las cantidades de los nodos son la oferta (bi>0), nodos 1 y 2 o la demanda(bi<0). Las cantidades de los arcos (cij) son los costes de envío

TEMA 5 Redes

M. Mocholí Modelización y Optimización 17

Oferta =demanda

x13+x14 =100x24+x25 =200-x13+x36=0-x14 – x24 +x46 =0-x25 + x56 +x57 =0-x36 – x46 – x56 +x68+x69 =0-x36 – x46 – x56 +x68+x69 =0-x57 + x78 +x79 =0-x68-x78= -150-x69-x79= -150

Min Z= x13+ 4x14+ 5x24+2 x25+ 3x36+2 x46+3 x56+2 x57+ 3x68+4 x69+ 5x78+6 x79

TEMA 5 Redes

M. Mocholí Modelización y Optimización 18

Planteamiento matemáticoTEMA 5 Redes

restoelparayfinaleslosparademandainicialesnodosparaofertaib

ij

n

j

n

jijiij

n

i

n

jijij

x

nibxx

xcFMin

0,

1 1

1 1

0

,...,1

·

M. Mocholí Modelización y Optimización 19

TEMA 5 Redes

M. Mocholí Modelización y Optimización 20

---- 54 VARIABLE X.L FLUJO A TRAVES DEL ARCO IJ3 5 6 8 9

1 1002 2003 1005 2006 150 150

---- 54 VARIABLE CTE.L = 2450 COSTE TOTAL DE ENVIO

TEMA 5 Redes

M. Mocholí Modelización y Optimización 21

PROBLEMA DEL FLUJO DE MÁXIMO En este tipo de problemas se trata de obtener cual es la máxima cantidad que sepuede hacer circular a través de una red desde un origen a un destino. Laaplicación de este tipo de problemas es en redes eléctricas, oleoductos,gaseoductos, redes de agua potable, etc.

Se trata de transportar el máximo número de uds (Flujo) desde el nodo 1 al 6, lascantidades sobre los arcos son la capacidad máxima de cada uno de ellos

TEMA 5 Redes

M. Mocholí Modelización y Optimización 22

Max Fx12 + x13 = F

-x12 + x23 + x24 + x25 = 0-x13 – x23 + x35 = 0-x24 - x54 + x46 = 0-x25 - x35 + x54 + x56 = 0-x46 - x56 = -F0 ≤ x12 ≤ 20 0 ≤ x13 ≤ 180 ≤ x23 ≤ 3 0 ≤ x24 ≤ 12 0 ≤ x25 ≤ 80 ≤ x35 ≤ 15 0 ≤ x46 ≤ 100 ≤ x54 ≤ 5 0 ≤ x56 ≤ 22F ≥0

TEMA 5 Redes

M. Mocholí Modelización y Optimización 23

TEMA 5 Redes

0

,0

1,...,2011

01

101:.

F

jiijkijx

nij

jixn

jijx

Fn

iinx

n

jFjxas

FZMax

M. Mocholí Modelización y Optimización 24

TEMA 5 Redes

M. Mocholí Modelización y Optimización 25

---- 31 VARIABLE X.L2 3 4 5 6

1 20 122 3 10 73 154 105 22

---- 31 VARIABLE F.L = 32

TEMA 5 Redes