modelos de redes: problemas de la ruta más corta · costo ,a entre el punto de partida o nodo...

Modelos de Redes: Problemas de Modelos de Redes: Problemas de la Ruta mla Ruta máás cortas corta

M. En C. Eduardo Bustos FarM. En C. Eduardo Bustos Farííasas

Problemas de la Ruta mProblemas de la Ruta máás cortas cortaSe trata de encontrar la ruta de menor distancia, o Se trata de encontrar la ruta de menor distancia, o costo ,a entre el punto de partida o nodo inicial y el costo ,a entre el punto de partida o nodo inicial y el destino o nodo terminal.destino o nodo terminal.

DefiniciDefinicióón del Probleman del Problema

-- Se tienen n nodos, partiendo del nodo inicial 1 y terminando en Se tienen n nodos, partiendo del nodo inicial 1 y terminando en el nodo final n.el nodo final n.-- Arcos Arcos bibi--direccionales conectan los nodos i y j con distancias direccionales conectan los nodos i y j con distancias mayores que cero, mayores que cero, ddijij

-- Se desea encontrar la ruta de mSe desea encontrar la ruta de míínima distancia que conecta el nima distancia que conecta el nodo 1 con el nodo n.nodo 1 con el nodo n.

Investigación de Operaciones

M. En C. Eduardo Bustos Farías 3

EJEMPLO 1EJEMPLO 1

Ruta mRuta máás cortas corta

LineasLineas FairwayFairway VanVan

Determine la ruta mas corta entre Seattle y El Paso Determine la ruta mas corta entre Seattle y El Paso para la siguiente red de carreteras.para la siguiente red de carreteras.

Salt Lake City

1 2

3 4

56

7 8

910

11

1213 14

15

1617 18 19

El Paso

Seattle

Boise

Portland

Butte

Cheyenne

Reno

Sac.

Bakersfield

Las VegasDenver

Albuque.

KingmanBarstow

Los Angeles

San Diego Tucson

Phoenix

599

691497180

432 345440

102

452

621

420

526

138

291280

432

108

469207

155114

386403118

425 314

602

SEA.SEA.Salt Lake City

1 2

3 4

56

7 8

9

1011

1213 14

15

1617 18 19

El Paso

Seattle

Boise

Portland

Butte

Cheyene

Reno

Sac.

Bakersfield

Las VegasDenver

Albuque.

KingmanBarstow

Los Angeles

San Diego Tucson

Pheonix

599

691497180

432 345

440

102

452

621

420

526

138

291

280

432

108

469207

155114

386403

118

425 314

BUT599

POR

180

497BOI

599

180

497POR.POR.

BOI432

SAC602

+

+

=

=

612

782

BOI

BOIBOI.BOI.

345SLC+ =

842

BUT.BUT.SLC

420

CHY.691

+

+

=

=

1119

1290

SLC.

SLCSLC.

SAC.SAC.

Una representación del algoritmo de Dijkstra’s

… Y de esta manera hasta cubrir toda la red..



EJEMPLO 2EJEMPLO 2

Ruta mRuta máás cortas corta



Una empresa distribuidora surte a 7 supermercados con Una empresa distribuidora surte a 7 supermercados con distintas ubicaciones. distintas ubicaciones. Los administradores desean conocer la distancia mLos administradores desean conocer la distancia máás corta s corta a cada uno de ellos, asa cada uno de ellos, asíí como las distancias (como las distancias (KmKm))



SOLUCISOLUCIÓÓN N CON WINQSBCON WINQSB



MMéétodo tabulartodo tabular

2

3

1

4

7

0

6

5

8

7

1

6

1 1

1

3

2

3

3



EJEMPLO 3EJEMPLO 3

RUTA MRUTA MÁÁS CORTAS CORTA



ENCONTRAR LA RUTA MÁS CORTA ENTRE O Y T.LOS NÚMEROS SOBRE LOS ARCOS SE MIDEN ENMILLAS.



SOLUCISOLUCIÓÓNN



(2, 0)



(2, O)

(4,O)



(2, O)

(5,O)

(4,O)



(2, O)*

(5,O)(2,A)(4,A)*

(4,O)*



(2, O)*

(5,O)(2,A)(4,A)*

(7,A)

(3,B)

(4,O)*



(2, O)*

(4,O)*

(5,O)(2,A)(4,A)*

(7,A)(8,B)*

(3,B)(7,B)*



(2, O)*

(4,O)*

(5,O)(2,A)(4,A)*

(7,A)(8,B)*

(3,B)(7,B)*

(7,E)



(2, O)*

(4,O)*

(5,O)(2,A)(4,A)*

(7,A)(8,B)*

(3,B)(7,B)*

(7,E)(13,D)*

LA RUTA MÁS CORTA REQUIERE 13 MILLAS.



Forma tabularForma tabular



EJEMPLO 4EJEMPLO 4




SoluciSolucióónn



310



(0,1)* (110,1)* (110,2) (160,3) (455,1) (610,1)(185,1)* (295,2)* (310,2) (420,2)*(455,2) (565,2)

(235,3) (420,3) (360,3) (545,3)(160,4) (455,4) (235,4) (530,4)*

(160,5) (580,5)



EJEMPLO 5EJEMPLO 5




El costo de un automEl costo de un automóóvil cuesta 12,000 vil cuesta 12,000 ddóólares, el costo de mantenimiento depende lares, el costo de mantenimiento depende de la edad del auto al inicio del ade la edad del auto al inicio del añño (ver o (ver tabla). tabla). Con la finalidad de evitar el costo de Con la finalidad de evitar el costo de mantenimiento alto, se da como cuota inicial mantenimiento alto, se da como cuota inicial de un nuevo que es valorado de acuerdo a su de un nuevo que es valorado de acuerdo a su edad (ver tabla). edad (ver tabla). La preocupaciLa preocupacióón es minimizar el costo neto n es minimizar el costo neto incurrido en los princurrido en los próóximos 5 aximos 5 añños.os.



PRECIO DE MANTENIMIENTO

ANUALEDAD DEL AUTO PRECIO DEL AUTO POR

COTA INICIAL

2000 1 70004000 2 60005000 3 20009000 4 100012000 5 50



SOLUCISOLUCIÓÓNN



La red tendrLa red tendríía {1,2,3,4,5,6} seis nodos el nodo i a {1,2,3,4,5,6} seis nodos el nodo i corresponde al inicio del acorresponde al inicio del añño i; para i < jo i; para i < jEl arco (i, j) corresponde a la compra del auto nuevo El arco (i, j) corresponde a la compra del auto nuevo al inicio del aal inicio del añño i y conservarlo hasta el inicio del ao i y conservarlo hasta el inicio del añño o j.j.La longitud del arco (i, j): llamado La longitud del arco (i, j): llamado CiCi, j es el costo , j es el costo neto total incurrido por ser el dueneto total incurrido por ser el dueñño y tener el auto o y tener el auto desde el inicio del adesde el inicio del añño i hasta el principio del ao i hasta el principio del añño j, si o j, si se compra un auto nuevo al inicio del ase compra un auto nuevo al inicio del añño i y se da o i y se da como adelanto al inicio del acomo adelanto al inicio del añño jo j



En miles de pesos:En miles de pesos:C12C12 == 22 ++ 1212 –– 77 = 7 = 7 C13C13 == 22 ++ 44 ++ 66 = 12 = 12 C14C14 == 22 ++ 44 ++ 55 ++ 1212

–– 22 = 21 = 21 C15C15 =2 + 4=2 + 4 + 5+ 5 ++ 99 ++ 1212 –– 1 = 31 1 = 31 C16C16 =2+=2+ 44 +5+5 +9+9 ++ 1212 + 12 = 44 + 12 = 44 C23C23 == 22 ++ 1212 –– 77 == 7 7 C24C24 == 22 ++ 44 ++ 1212 –– 66

== 1212C25C25 =2+=2+ 4+4+ 55 ++ 1212–– 22 = 21= 21C26C26 =2=2 ++ 44 +5+5 +9+9 +12+12 –– 1 = 311 = 31



(0,1)*(0,1)* (7,1)*(7,1)* (12,1)*(12,1)* (21,1)(21,1) (31,1)(31,1) (44,1)(44,1)

(7,2)(7,2) (12,2)(12,2) (21,2)(21,2) (31,2)(31,2)

(7,3)(7,3) (12,3)(12,3) (21,3)(21,3)

(19,2)*(19,2)* (7,4)(7,4) (12,4)(12,4)

(24,3)*(24,3)* (7,5)(7,5)

(31,4)*(31,4)*



2



SOLUCISOLUCIÓÓNN



SOLUCION EN EL TORA :SOLUCION EN EL TORA :

RUTA1RUTA1----------------------------------------------------------------------------------------------------------------------*** SHORTEST ROUTE SOLUTION ****** SHORTEST ROUTE SOLUTION ***Node 12:Node 12:Shortest distance = 10.000000Shortest distance = 10.000000Optimal Path:Optimal Path:N1 N1 -- N2 N2 -- N5 N5 -- N9 N9 -- N12N12



EJERCICIO PARA RESOLVEREJERCICIO PARA RESOLVER



Una empresa desea saber cuantos metros de Una empresa desea saber cuantos metros de cable utilizarcable utilizaráá para enlazar 12 computadoras.para enlazar 12 computadoras.



EJERCICIO PARA RESOLVEREJERCICIO PARA RESOLVER



La empresa de transportes La empresa de transportes ““EmtrafesaEmtrafesa”” Trujillo ofrece Trujillo ofrece las salidas diarias Trujillolas salidas diarias Trujillo--Chiclayo, TrujilloChiclayo, Trujillo--Lima, Lima, TrujilloTrujillo--Piura, actualmente basados en un anPiura, actualmente basados en un anáálisis de lisis de mercado desea incorporar la ruta Tumbes mercado desea incorporar la ruta Tumbes ––TacnaTacnaincluyendo distritos aledaincluyendo distritos aledañños. os. La siguiente red representa las rutas disponibles de La siguiente red representa las rutas disponibles de Tumbes Tumbes ––TacnaTacna. . Asimismo cada rama las distancias en millas entre Asimismo cada rama las distancias en millas entre ééstas dos ciudades. stas dos ciudades. Y cada nodo los distritos aledaY cada nodo los distritos aledañños para llegar a su os para llegar a su destino. destino. Determinar las rutas mas cortas entre la ciudad de Determinar las rutas mas cortas entre la ciudad de Tumbes (nodo 1) y la ciudad de Tacna (nodo 15).Tumbes (nodo 1) y la ciudad de Tacna (nodo 15).

modelos de redes: problemas de la ruta más corta · costo ,a entre el punto de partida o nodo...

Documents