• Author / Uploaded
• joe

Citation preview

INVESTIGACION DE OPERACIONES II

OPTIMIZACIÓN DE REDES Catedrático Titular,. Adriana Monserrat Gómez Ramos

Equipo

Rolando López

Carlos Cruz

Alexis Canuto

José Mata

Eduardo Lozano

Carlos Trujillo

página 2

TERMINOLOGÍA

INTRODUCCIÓN La mayor parte de los modelos de optimización de redes son casos particulares de modelos de programación lineal y pueden ser formalizados a partir del modelo de Flujo de Costo Mínimo, estos modelos se aplican en la administración de problemas de transporte, logística, comunicación y seguimiento de proyectos de finanzas, recursos humanos o mercadeo. En algunos problemas de optimización puede ser útil representar el problema a través de una gráfica, para entender los modelos de redes se utiliza una terminología apropiada que se muestra a continuación, esta terminología no está estandarizada ni lo estará pues un concepto se puede describir de diferentes maneras. página 4

GRÁFICA O RED

Arco: Los arcos se etiquetan para dar nombres a los nodos en sus puntos terminales, por ejemplo, AB es el arco entre los nodos A y B (se pone primero el nodo de donde viene) • LA RED TIENE 12 LÍNEAS LLAMADAS DE DIFERENTES FORMAS COMO ARCOS, RAMAS, ARISTAS O LIGADURAS ESTAS REPRESENTAN LOS 12 CAMINOS EXISTENTES EN LA RED. POR LOS ARCOS DE UNA RED PUEDEN EXISTIR ALGÚN TIPO UN FLUJO QUE PASA POR ELLOS

Nodos

Arcos

Flujo

Cruceros Aeropuertos Puntos de conmutación Estaciones de bombeo Centros de Trabajo

Caminos Líneas de espera Cables, canales

Vehículos Aviones Mensajes

Tuberías

Fluidos

Rutas de manejo

Trabajos

LOS ARCOS DE UNA RED PUEDEN TENER UN FLUJO DE ALGUN TIPO. página 7

A

B

EL FLUJO A TRAVÉS DE DEL ARCO SE PERMITE ÚNICAMENTE EN UNA DIRECCIÓN (TAL COMO UNA CALLE DE UN SOLO SENTIDO),Y ESTÁ SE INDICA CON UNA CABEZA DE FLECHA AL FINAL DE LA LÍNEA QUE REPRESENTA EL ARCO

ARCO NO DIRIGIDO CUANDO EL FLUJO SE PERMITE EN AMBAS DIRECCIONES

PARA DISTINGUIR ENTRE LOS DOSTIPOS DE ARCOS CON FRECUENCIA LOS ARCOS NO DIRIGIDOS SE NOMBRAN LIGADURAS.

RED DIRIGIDA TODOS LOS ARCOS ESTAN DIRIGIDOS

RED NO DIRIGIDA TODOS LOS ARCOS DE LA RED NO ESTAN DIRIGIDOS

Una red no dirigida se puede convertir en una red dirigida, si se desea, cambiando cada arco no dirigido por un par de arcos dirigidos en direcciones opuestas

A

B

TRAYECTORIA ENTRE DOS NODOS:ES UNA SUCESIÓN O SERIE DE ARCOS DISTINTOS QUE CONECTAN ESTOS NODOS. POR EJEMPLO DOSPOSIBLE TRAYECTORIAS QUE CONECTAN A LOS NODOS O Y F SONLASUCESIÓN DEARCOS. A O

D

B C

A F

E

O

D B

C

OB-BD-DF Ó (O→B→D→F), Y VICEVERSA. OC-CB-BE-ED-DF Ó (O→C→B→E→D→F), Y VICEVERSA.

F

E

TRAYECTORIA NO DIRIGIDA DEL NODO I AL NODO J PUEDE SER HACIA O DESDE EL NODO J ALGUNAS VECES UNA TRAYECTORIA DIRIGIDA TENDRA ALGUNOS ARCOS DIRIGIDOS, CON FRECUENCIA UNA TRAYECTORIA NO DIRIGIDA TENDRA ALGUNOS ARCOS DIRIGIDOS AL NODO J Y OTROS DESDE I: TRAYECTORIA DIRIGIDA DEL NODO I AL NODO J CUANDO LA SUCESIÓN DE ARCOS CUYA DIRECCION ES FACTIBLE A TRAVEZ DE ESTA . LA TRAYECTORIA DIRIGIDA TAMBIEN SATISFACE LA DEFINICION DE TRAYECTORIA AB-BC-CE ES UNA TRAYECTORIA DIRIGIDA DEL NODO A AL NODO E .

página 11

CICLO

TRAYECTORIA QUE UNE A UN NODO CONSIGO MISMO ES DECIR, COMIENZA Y TERMINA EN EL MISMO NODO. EN UNA RED DIRIGIDA UN CICLO PUEDE SER DIRIGIDO O NO DEPENDIENDO SI LA TRAYECTORIA EN CUESTION ES DIRIGIDA O NO. POR EL CONTRARIO AB-BC-AC ES UN CICLO NO DIRIGIDO PUESTO QUE LA DIRECCION DEL ARCO AC ES OPUESTA AL DE LOS ARCOS AB Y BC. (COMO UNA TRAYECTORIA DIRIGIDA TAMBIEN ES NO DIRIGIDA, UN CICLO DIRIGIDO ES UN CICLO NO DIRIGIDO , PERO EN GENERAL EL INVERSO NO ES CIERTO) página 12

UNA RED CONECTADA CUANDO ES POSIBLE LLEGAR A CUALQUIER NODO DESDE OTRO SIGUIENDO LA SECUENCIA DE ARCOS EN LA QUE NO IMPORTA LA DIRECCION

1

3

2

5

4

página 13

ARBOL DE EXPANSION SUBCONJUNTO CONECTADO DE UNA RED QUE COMPRENDE TODOS LOS NODOS PERO NINGUN CICLO.

1

3 2

5

1

4

3 2

1

3 2

5

4

5 4 página 14

PROBLEMA DE LA RUTA MAS CORTA • ESTE TIPO DE PROBLEMAS BUSCA ENCONTRAR LA RUTA MÁS CORTA ENTRE DOS NODOS DE UNA RED, EN LA CUAL LA LONGITUD O ARCO TIENE UN COSTO POSITIVO Y ASÍ MINIMIZAR EL COSTO TOTAL. ESTE TIPO DE PROBLEMAS ES FUNDAMENTAL EN ÁREAS COMO INVESTIGACIÓN DE OPERACIONES, CIENCIA DE LA COMPUTACIÓN E INGENIERÍA. • TRATA DE ENCONTRAR LA RUTA DE MENOR DISTANCIA O COSTO ENTRE EN PUNTO DE PARTIDA O EL NODO INICIAL Y EL DESTINO O NODO TERMINAL.

página 15

EL POR QUÉ DE SU IMPORTANCIA ES: • APLICACIONES PRÁCTICAS COMO EL ENVÍO DE ALGÚN MATERIAL ENTRE DOS PUNTOS ESPECÍFICOS DE FORMA EFICIENTE, ECONÓMICA O RÁPIDA. • AL SER APLICADOS A UNA RED CON CARACTERÍSTICAS ESPECIFICAS COMO ACÍCLICA Y COSTOS POSITIVOS, LOS RESULTADOS QUE ARROJA SON EXACTOS A UN TIEMPO Y COSTO RAZONABLES. • SE PUEDE USAR COMO INICIO EN UN ESTUDIO DE MODELOS COMPLEJOS DE REDES, QUE ES CUANDO NO SE CONOCE LA ESTRUCTURA DE LA RED. • SE UTILIZA COMO SUBPROBLEMAS EN LA SOLUCIÓN DE PROBLEMAS COMBINATORIOS Y REDES, RESULTAN AUXILIARES PARA ENCONTRAR UNA BUENA SOLUCIÓN.

RUTA MÁS CORTA EN PROGRAMACIÓN LINEAL SE PUEDE PLANTEAR COMO EL ENVÍO DE UNA UNIDAD DE FLUJO DEL NODO ORIGEN AL NODO DESTINO AL MÍNIMO COSTO. SE PUEDEN PRESENTAR DE DIFERENTES FORMAS: • PARA QUE EXISTA SOLUCIÓN, DEBE EXISTIR UNA TRAYECTORIA. ADEMÁS DE QUE NO EXISTEN CIRCUITOS NEGATIVOS. • DEBE EXISTIR RUTAS DEL NODO ORIGEN A LOS NODOS DE LA RED. • ENTRE CADA PAR DE NODOS DEBE EXISTIR AL MENOS UNA TRAYECTORIA.

EL ALGORITMO DE LA RUTA MÁS CORTA CONSTA DE LOS SIGUIENTES ELEMENTOS: • NODO ORIGEN, COMIENZA DE LA RUTA. • ARCO, LÍNEA QUE UNE LOS NODOS. • NODO ADYACENTE, NODOS CONECTADOS POR UN ARCO. • NODO DESTINO, FINALIZA LA RUTA. • ETIQUETAS, ESTAS NOS VAN INDICANDO LA LONGITUD DE UN ARCO OTRO Y DE QUÉ NODO VIENE, SE REPRESENTA ENTRE CORCHETES [DISTANCIA DEL NODO, NODO DEL QUE PARTE] página 18

EJEMPLOS DE APLICACIONES DE LA RUTA MAS CORTA • • • •

REEMPLAZO DE EQUIPO RUTA MAS CONFIABLE ACERTIJO DE LAS TRES JARRAS ALGORITMO DE LA RUTA MAS CORTA

página 19

REEMPLAZO DE EQUIPO RENTCAR ESTA DESARROLLANDO UNA POLITICA DE REEMPLAZO PARA SU FLOTILLA DE AUTOMOVILES EN UN HORIZONTE DE PLANEACION DE 4 AÑOS, AL INICIO DE CADA AÑO, UN AUTOMOVIL SE REEMPLAZARA O SE CONSERVARA EN OPERACIÓN DURANTE UN AÑO MAS . UN AUTOMOVIL DEBE ESTAR EN EL SEVICIO 1 A 3 AÑOS. LA SIGUIENTE TABLA PROPORCIONA EL COSTO DE REEMBOLSO COMO UNA FUNCION DEL AÑO EN EL QUE SE ADQUIERE UN AUTOMOVIL Y LOS AÑOS DE OPERACIÓN.

Equipo adquirido al inicio del año

Costo de reembolso ($) para años en operación

1

2

3

1

4000

5400

9800

2

4300

6200

8700

3

4800

7100

4

4900

página 21

página 22

RUTA MAS CONFIABLE

I.Q. SMART VA EN AUTO DIARIAMENTE AL TRABAJO. HABIENDO COMPLETADO UN CURSO DE ANLISIS DE REDES , SMART ES CAPAZ DE DETERMINAR LA RUTA MAS CORTA AL TRABAJO , POR DESGRACIA LAS RUTAS SELECCIONADAS ESTA FUERTEMENTE PATRULLADA POR LA POLICIA Y CON TODAS LAS MULTAS PAGADAS POR EXCESO DE VELOCIDAD, LA RUTA MAS CORTA PUEDE NO SER LA MEJOR OPCION POR LO TANTO HA DECIDIDO ELEGIR UNA RUTA.

1-3-5-7 ES (.9)(.3)(.25)=.0675 página 23

log (.9)= -.04576 , log (.3)= -.52288, log (.25)= -.60206

log a1+log a2+log a3= -1.1707 (.9)(.3)(.25)= .0675

10^-1.1707= .0675

=6.75% página 24

ACERTIJO DE LAS TRES JARRAS UNA JARRA DE 8 GALONES ESTA LLENA DE LIQUIDO, DADO QUE HAY 2 JARRAS VACÍAS DE 5 Y 3 GALONES DIVIDA LOS 8 GALONES DE LÍQUIDOS EN DOS PARTES IGUALES UTILIZANDO SOLO LAS TRES JARRAS. SE DEFINE UN NODO MEDIANTE UN SUBÍNDICE TRIPLE QUE REPRESENTA LAS CANTIDADES DE LIQUIDO EN LAS JARRAS DE 8,5 Y 3 GALONES RESPECTIVAMENTE. ESTO QUIERE DECIR QUE LAS RED SE INICIA CON EL NODO (8,0,0) Y TERMINA CON LA SOLUCIÓN DESEADA (4,4,0). SE GENERA UN NUEVO NODO A PARTIR DEL NODO ACTUAL DECANTANDO LIQUIDO DE UNA JARRA A OTRA .

página 26

ALGORITMO DE LA RUTA MAS CORTA

EL ALGORITMO DE LA RUTA MÁS CORTA CONSISTE, SI ES NECESARIO DECIRLO, EN UNA MODALIDAD DE PROBLEMAS DE REDES, EN LA CUAL SE DEBE DETERMINAR EL PLAN DE RUTAS QUE GENERE LA TRAYECTORIA CON LA MÍNIMA DISTANCIA TOTAL, QUE UNA UN NODO FUENTE CON UN NODO DESTINO, SIN IMPORTAR EL NÚMERO DE NODOS QUE EXISTAN ENTRE ESTOS.

página 27

ALGORITMO DE LA RUTA MÁS CORTA - EJEMPLO UN MINERO HA QUEDADO ATRAPADO EN UNA MINA, LA ENTRADA A LA MINA SE ENCUENTRA UBICADA EN EL NODO 1, SE CONOCE DE ANTEMANO QUE EL MINERO PERMANECE ATRAPADO EN EL NODO 9, PARA LLEGAR A DICHO NODO HAY QUE ATRAVESAR UNA RED DE TÚNELES QUE VAN CONECTADOS ENTRE SÍ. EL TIEMPO DE VIDA QUE LE QUEDA AL MINERO SIN RECIBIR AUXILIO ES CADA VEZ MENOR Y SE HACE INDISPENSABLE HALLAR LA RUTA DE ACCESO AL NODO 9 MÁS CORTA. LAS DISTANCIAS ENTRE NODOS DE LA MINA SE ENCUENTRAN EN LA SIGUIENTE GRÁFICA DADAS EN CIENTOS DE METROS. FORMULE UN MODELO DE TRANSBORDO Y RESUELVA MEDIANTE CUALQUIER PAQUETE DE HERRAMIENTAS DE INVESTIGACIÓN OPERATIVA QUE PERMITA ESTABLECER LA RUTA MÁS CORTA PARA PODER ASÍ AUXILIAR AL MINERO.

página 28

VARIABLES DE DECISIÓN EL NOMBRE DE LAS VARIABLES EN ESTE CASO POCO IMPORTA, DADO QUE DE SER ESCOGIDA PARA LA SOLUCIÓN BÁSICA ESO SIGNIFICA SIMPLEMENTE QUE SERÁ EMPLEADA COMO RUTA PARA IR A RESCATAR AL MINERO, SIN EMBARGO NADA TIENE DE MALO EL QUE SE LE PUEDA ASOCIAR CON EL ENVÍO DE UNIDADES DESDE LA ENTRADA DE LA MINA HACIA EL MINERO, POR ENDE PUEDE SUGERIRSE ESTE COMO NOMBRE DE LAS VARIABLES. "CANTIDAD DE UNIDADE ENVIADAS DESDE EL NODO I HACIA EL NODO J".

X12 = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 2 X13 = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 3 X23 = Cantidad de unidades enviadas desde el nodo 2, hacia el nodo 3 X24 = Cantidad de unidades enviadas desde el nodo 2, hacia el nodo 4 X32 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 2 X34 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 4 X35 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 5 X46 = Cantidad de unidades enviadas desde el nodo 4, hacia el nodo 6 X47 = Cantidad de unidades enviadas desde el nodo 4, hacia el nodo 7 X54 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 4

página 30

RESTRICCIONES RESTRICCIONES DEMANDA

DE

OFERTA

Y

HAY QUE RECORDAR QUE EL OBJETIVO DE ESTE MODELO ES LA CONSECUCIÓN DE UN PLAN DE RUTA QUE NOS PERMITA ENCONTRAR AL MINERO LO MÁS PRONTO POSIBLE AL RECORRER LA DISTANCIA MÍNIMA POSIBLE, POR ENDE LA CLAVE PARA PLANTEAR EL MODELO COMO SI FUESE DE TRANSBORDO ES ESTABLECER UNA DEMANDA Y OFERTA IGUAL A LA UNIDAD (1).

página 31

FUNCIÓN OBJETIVO ZMIN = 4X12 + 2X13 + 2X23 + 7X24 + 4X32 + 9X34 + 6X35 + 1X46 + 5X47 + 2X54 + 4X56 + 3X57 + 2X58 + 1X67 + 5X69 + 4X76 + 3X78 + 5X79 + 2X87 + 7X89 NGRESANDO LOS DATOS A WINQSB

página 32

SOLUCIÓN OBTENIDA MEDIANTE WINQSB

LA RUTA MÁS CORTA PARA RESCATAR AL MINERO TIENE COMO DISTANCIA TOTAL 1600 METROS (DADO QUE LAS DISTANCIAS ESTABAN DADAS EN CIENTOS DE METROS) Y ES TAL COMO SE MUESTRA EN LA SIGUIENTE GRÁFICA.

EJEMPLO • Reemplazo de equipo RENTCAR ESTA DESARROLLANDO UNA POLITICA DE REEMPLAZO PARA SU FLOTILLA DE AUTOMOVILES EN UN HORIZONTE DE PLANEACION DE 4 AÑOS, AL INICIO DE CADA AÑO, UN AUTOMOVIL SE REEMPLAZARA O SE CONSERVARA EN OPERACIÓN DURANTE UN AÑO MAS . UN AUTOMOVIL DEBE ESTAR EN EL SEVICIO 1 A 3 AÑOS. LA SIGUIENTE TABLA PROPORCIONA EL COSTO DE REEMBOLSO COMO UNA FUNCION DEL AÑO EN EL QUE SE ADQUIERE UN AUTOMOVIL Y LOS AÑOS DE OPERACIÓN.

página 35

Costo de reembolso ($) para años en operación

Equipo adquirido al inicio del año

1

2

3

1

4000

5400

9800

2

4300

6200

8700

3

4800

7100

4

4900

página 36

página 37

1

I1

2

3

4

T1-I2

T2-I3

T3-I4

5

T4-I5 página 38

Equipo adquirido al inicio del año 1 2 3 4

Costo de reembolso ($) para años en operación 1 2 3 4000 5400 9800 4300 6200 8700 4800 7100 4900

página 39

RUTAS a) b) c) d) e)

1-2-3-4-5= $18,000 1-2-4-5= $15,100 1-2-5= $12,700 1-4-5= $14,700 1-3-5= $12,500

LA SOLUCION INDICA QUE UN AUTOMOVIL ADQUIRIDO AL INICIO DE AÑO 1 (NODO 1) DEBE REEMPLAZARSE DESPUES DE 2 AÑOS AL INICIO DEL AÑO 3 (NODO 3). EL AUTOMOVIL DE REEMPLAZO SE MANTENDRA ENTONCES EN SERVICIO HASTA FINALES EL AÑO 4. EL COSTO TOTAL DE ESTA POLITICA DE REEPLAZO ES DE $12,500 ($5,400 + $7,100) página 40

PARA OBTENER EL VALOR FINAL DE CADA RUTA SE SUMA EL COSTO DE REEMPLAZO DE LOS ARCOS EN LOS QUE SE PASARA EJEMPLOS

RUTA 1-2-3-4-5 (4,000+4,300+4,800+4,900 = 18,000) RUTA 1-2-4-5 (4,000+6,200+4,900 = 15,100) RUTA 1-2-5 (4,000+8,700 = 12,700)

RUTA 1-4-5 (9,800+4,900 = 14,700) RUTA 1-3-5 (5,400+7,100 = 12,500) página 41

TECNOLOGICO NACIONAL DE MEXICO

Investigación de operaciones II

Equipo #1 página 42