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


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


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


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


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


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


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


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


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}


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)


Gms 1TEMA 5 Redes


Gms 2TEMA 5 Redes


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

1 13 14 18 1

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

TEMA 5 Redes


ALGORITMO DE FLOYD PARA REDES NO DIRIGIDAS

TEMA 5 Redes


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


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


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


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

·


TEMA 5 Redes


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


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


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


TEMA 5 Redes

0

,0

1,...,2011

01

101:.

F

jiijkijx

nij

jixn

jijx

Fn

iinx

n

jFjxas

FZMax


TEMA 5 Redes


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

tema 5 redes 1.- conceptos bÁsicos. 5 redes.pdf · aplicación de este tipo de problemas es en...

Documents