ayuda 3.2

OPTIMIZACION DE REDES 1

CICLO 2015-III Módulo:2Unidad: II Semana: 3.2

Gabriel Percy Michhue Vela

Unidad I IOPTIMIZACIÓN DE REDES

2

ORIENTACIONES• Cuando Usted estudie; contraste y relacione

la información recién adquirida con su conocimiento y experiencia anterior. Para ello es útil que revise los resúmenes, esquemas, cuadros comparativos o mapas conceptuales elaborados previamente en su texto.

• Recuerde que la Investigación Operativa se aprende practicando, utilice un block para repetir los ejercicios.

3

Gráfica de Actividades1

Cálculo de Ruta Crítica2

Algoritmo de la Ruta Crítica3

Ejercicios4

CONTENIDOS TEMÁTICOS

• En la estimación de tiempo de tres enfoques, el tiempo para completar una actividad se asume que siguen una distribución Beta.

• El tiempo promedio de terminación de una actividad se define como:

t = (a + 4m + b)/6

• La Varianza del tiempo de terminación de una actividad se define como:

2 = ((b-a)/6)2

Tiempos Inciertos de Actividad

a = tiempo optimista b = tiempo pesimista m = tiempo más probable

Tiempos Inciertos de Actividad• En la estimación de tiempo de tres enfoques, el

camino crítico es determinado como si los tiempos promedios para las actividades fuesen tiempos fijos.

• El tiempo de terminación total del proyecto se asume que tiene una distribución normal con media igual a la suma de los tiempos promedios de las actividades que están a lo largo de la ruta crítica y la varianza es igual a la suma de las varianzas a lo largo de la ruta crítica.

t = (a + 4m + b)/6 2 = ((b-a)/6)2a = tiempo optimista b = tiempo pesimista m = tiempo más probable

Ejemplo: ABC Asociados • Considere el siguiente proyecto:

Predec. Tiempo(Hr) Tiempo(Hr) Tiempo(Hr) Actividad Inmed. Optimista Más probable Pesimista A -- 4 6 8 B -- 1 4.5 5 C A 3 3 3 D A 4 5 6 E A 0.5 1 1.5 F B,C 3 4 5 G B,C 1 1.5 5 H E,F 5 6 7 I E,F 2 5 8 J D,H 2.5 2.75 4.5 K G,I 3 5 7

Ejemplo: ABC Asociados•

t = ( a + 4m + b)/6 2 = ((b-a)/6)2

Actividad Tiempo Esperado Varianza A 6 4/9

B 4 4/9 C 3 0 D 5 1/9 E 1 1/36 F 4 1/9 G 2 4/9 H 6 1/9 I 5 1 J 3 1/9 K 5 4/9

Actividad con Tiempos Esperados y Varianzas

Act. Opt prob Pes. A 4 6 8 B 1 4.5 5 C 3 3 3 D 4 5 6

E 0.5 1 1.5 F 3 4 5 G 1 1.5 5 H 5 6 7 I 2 5 8 J 2.5 2.75 4.5 K 3 5 7

a = tiempo optimista b = tiempo pesimista m = tiempo más probable

Ejemplo: ABC Asociados• Red del Proyecto

E

Start

A

H

D

F

J

I

K

Finish

B

C

G

t = (a + 4m + b)/6

Example: ABC Asociados• Earliest/Latest Times and Slack

Actividad ES EF LS LF Holgura A 0 6 0 6 0 *

B 0 4 5 9 5 C 6 9 6 9 0 * D 6 11 15 20 9 E 6 7 12 13 6 F 9 13 9 13 0 * G 9 11 16 18 7 H 13 19 14 20 1 I 13 18 13 18 0 * J 19 22 20 23 1 K 18 23 18 23 0 *

• Determinando la Ruta Crítica

– Una ruta crítica es una ruta de actividades, desde el nodo de Inicio hasta nodo Final, con tiempos de holgura 0.

– Ruta Crítica: A – C – F – I – K

– El tiempo de terminación del proyecto es igual a la cuantía máxima de las actividades de tiempos más temprano de acabado.

– Duración del Proyecto: 23 horas

Ejemplo: ABC Asociados

Ejemplo: ABC Asociados• Ruta Crítica (A-C-F-I-K)

E

Start

A

H

D

F

J

I

K

Finish

B

C

G

0 60 60 60 6

9 139 139 139 13

13 1813 1813 1813 18

9 119 1116 1816 18

13 1913 1914 2014 20

19 2219 2220 2320 23

18 2318 2318 2318 23

6 76 712 1312 13

6 96 96 96 9

0 40 45 95 9

6 116 1115 2015 20

Ejemplo: ABC Asociados• Probabilidad que el proyecto esté terminado dentro

de 24 hrs2 = 2

A + 2C + 2

F + 2I + 2

K

= 4/9 + 0 + 1/9 + 1 + 4/9 = 2 = 1.414

z = (24 - 23)/(24-23)/1.414 = .71

De la tabla de Distribución Normal Estandar: P(z < .71) = .5 + .2611 = .7611

Tabla de Distribución Normal

Actividad Descripción Precedente(s) Duración A Selección de música --

----

A, BBB

C, FB

E, HE, H

C, D, F, JK

21141413181714111012119

B Aprendizaje de la música C Elaboración de copias y compra de librosD Pruebas E Ensayos F Ensayos individuales G Renta de candelabros H Compra de velas I Instalación y decoración de candelabrosJ Compra de artículos decorativos K Instalación de artículos decorativos L Programación final

APRENDIENDO A GRAFICAR Construya el diagrama de flechas que comprenda las actividades A, B, C,…y L que satisfagan las siguientes relaciones:

El diagrama de flechas resultante se muestra en la gráfica de actividades. Las actividades ficticias D1 y D2 se usan para establecer relaciones de precedencia correctas. D3 se utiliza para identificar las actividades E y H con eventos finales únicos. Los eventos del proyecto están numerados de tal manera que su orden ascendente indica el sentido de progreso en el proyecto.

Actividad Descripción Precedente(s) Duración

A Selección de música ------

A, BBB

C, FB

E, HE, H

C, D, F, JK

21141413181714111012119

B Aprendizaje de la música C Elaboración de copias y compra de librosD Pruebas E Ensayos F Ensayos individuales G Renta de candelabros H Compra de velas I Instalación y decoración de candelabrosJ Compra de artículos decorativos K Instalación de artículos decorativos L Programación final

Actividad Precedente(s) Duración

A ------

A, BBB

C, FB

E, HE, H

C, D, F, JK

21141413181714111012119

B C D E F G H I J K L


A --A, B

C, D, F, JK

2113119

D K L

54Total Tiempo

de duración del Proyecto

CÁLCULOS DE RUTA CRÍTICA

Actividad Descripción Precedente(s) Duración

A Pronostico del volumen de ventas ----ACD

B, EE, F

107532114

B Estudio de mercado competitivo

C Diseño de articulo e instalaciones

D Elaboración de Programas de producciónE Estimación de costos de producción F Fijación del precio de ventas

G Elaboración del Presupuesto

CÁLCULOS DE RUTA CRÍTICA


A ----ACD

B, EE, F

1075321

14

B C D E F G

Total Tiempo de duración

del Proyecto

DETERMINACIÓN DE LA RUTA CRÍTICA

13

USO DE MS-PROJET PARA GRAFICAR LA RED DE ACTIVIDADES

MS Project, es una herramienta útil para la administración de proyectos, permitiendo controlar de una manera rápida y eficaz un proyecto.

Se conoce como gráfica de Gantt. Este tipo de diagrama se usa mucho en la práctica para mostrar la programación de un proyecto, ya que las barras muestran los tiempos de inicio y terminación de las actividades.

USO DE MS-PROJET PARA GRAFICAR LA RED DE ACTIVIDADES

USO DE MS-PROJET PARA GRAFICAR LA RED DE ACTIVIDADESSe puede elegir entre varios tipos de vistas con la barra de herramientas que se encuentra a la izquierda de la pantalla. La preestablecida es la gráfica de Gantt. El diagrama PERT muestra la red del proyecto. Al inicio los cuadros de las actividades están alineados de izquierda a derecha, pero se pueden mover como se desee. La figura muestra la red de proyecto después de colocar los cuadros en la misma forma vertical que en la figura. Observemos que cada cuadro proporciona información relevante de la actividad.

OPTIMIZACIÓN EN REDES• EN ALGUNOS PROBLEMAS DE

OPTIMIZACIÓN PUEDE SER ÚTIL REPRESENTAR EL PROBLEMA A TRAVÉS DE UNA GRÁFICA: ruteo de vehículos, distribución de producto, programa de actividades en un proyecto, redes de comunicación, etc.

• MODELOS DE REDES: algoritmos especiales

GRÁFICA• ES UN CONJUNTO DE NODOS (N) Y

ARCOS (A) QUE CONECTAN LOS NODOS. NOTAMOS G=(N,A)

• LOS NODOS SE NUMERAN : 1,2,...,n• LOS ARCOS SE DENOTAN (i,j)

indicando que une el nodo i al nodo j

i

j

CONCEPTOS BÁSICOS• Un arco (i,j) es dirigido si conecta i

con j pero no j con i.

• Una gráfica G=(N,A) es dirigida si sus arcos están dirigidos. En una gráfica no dirigida (i,j) y (j,i) representan el mismo arco ( no dirigido).

i

j

CONCEPTOS BÁSICOS

Gráfica no dirigida

Gráfica dirigida

4

3

2

6

5

7

Nodos

Arcos nodirigidos

1

14

3

2

6

5

7

Nodos

Arcos dirigidos

CONCEPTOS BÁSICOS• Un Camino o Ruta del nodo i al

nodo j es una secuencia de arcos que unen el nodo i con el nodo j: (i,i1), (i1,i2), (i2,i3),...,(ik,j). Ruta de k arcos.

• Un Ciclo es un camino que une un nodo consigo mismo:(i,i1), (i1,i2), (i2,i3),...,(ik,i)

CONCEPTOS BÁSICOS

14

3

2

6

5

71

CAMINO DE 4 A 7

CICLO

CONCEPTOS BÁSICOS• UNA SUBGRÁFICA G’=(N’,A’) DE UNA

GRÁFICA G=(N,A) es un conjunto de nodos y arcos de G: N’ N y G’ G.

• UNA GRÁFICA G=(N,A) ES CONEXA si para cada par de nodos i,j N existe un camino que conecte el nodo i con el nodo j.

GRAFICA G: Conexa

SUBGRÁFICA G’: conexa

SUBGRAFICA G: no conexa

CONCEPTOS BÁSICOS• UN ÁRBOL de una gráfica G=(N,A) es una

subgráfica G’=(N’,A’) de G que es conexa y no contiene ciclos. Si el Árbol contiene todos los nodos de G (N’=N) se dice que es un Árbol Generador.

GRAFICA G

ÁRBOL GENERADOR DE G

ÁRBOL DE G

CONCEPTOS BÁSICOS• Una RED es una gráfica con uno o mas

valores asignados a los nodos y/o a los arcos:Nodos: (ai)demanda, oferta, eficiencia,

confiabilidad.Arcos: (cij) costo, distancia, capacidad

Ejemplos: representar a través de una red : red de agua potable, red de comunicación, red logística.

PROBLEMAS Y MODELOS DE REDES

• PROBLEMAS: encontrar la ruta más corta de la planta al centro de distribución pasando por ciudades intermedias. Problemas de transbordo. Política de reemplazo de equipo.

• MODELO de la RUTA MÁS CORTA: dada una red dirigida G=(N,A) con distancias asociadas a los arcos (cij), encontrar la ruta más corta del nodo i al nodo j, donde i,jN

• PROBLEMAS: transportar la mayor cantidad de producto posible a través de una red de distribución: ductos, tráfico vehicular.

• MODELO de FLUJO MÁXIMO: dada una red dirigida G=(N,A) con capacidades en los arcos (cij) encontrar la mayor cantidad de flujo total de un nodo fuente a un nodo destino


• PROBLEMAS: programar las actividades de un proyecto y determinar el tiempo requerido para terminar el proyecto así como las actividades “críticas”

• MODELO: CPM, PERT (RUTA MAS LARGA)


• PROBLEMAS: redes de comunicaciones. Conectar todos los nodos con el mínimo costo.

• MODELO DEL ÁRBOL GENERADOR MINIMAL: dada una red conexa no dirigida G=(N,A) con costos cij en cada arco (i,j) A, encontrar el Árbol Generador de costo mínimo


• Problema del Agente Viajero: encontrar el camino más corto saliendo de un nodo y regresando al mismo.

• MODELO DEL AGENTE VIAJERO: encontrar un ciclo en una red (dirigida o no dirigida ). Un (camino) ciclo que no repite nodos es un (camino) o ciclo Hamiltoniano.

• NO SIEMPRE EXISTE


OTROS CASOS ESPECIALES• RED PLANA: que puede representarse en

el plano sin cruzar arcos. Útil en ruteo• CICLO DE EULER: UN CICLO QUE

INCLUYE CADA ARCO SOLO UNA VEZ. (Solo existe en una gráfica si esta tiene un número par de arcos incidentes en cada vértice (Euler). Útil en ruteo.

OTRAS APLICACIONES A II• LAYOUT: distribución física de instalaciones• MANUFACTURA CELULAR: separa

componentes en familias de partes y máquinas en células de manufactura

• PROGRAMACIÓN DE LA PRODUCCIÓN EN EL TIEMPO

RED DE FLUJO DE COSTO MÍNIMO

Los problemas de transporte, transbordo, camino mas corto, flujo máximo, red de proyectos(CPM) son casos especiales del modelo de FLUJO DE COSTO MÍNIMO EN UNA RED y pueden resolverse con una forma especial del Simplex .

MCNFP: Minimum Cost Network Flow

arcocadaparaUx

nodocadaparabxxas

x

x

ijij

j kikiij

ij

ij

L

.

c min

j)(i, arco elen capacidad desuperior cotaU

j)(i, arco elen capacidad deinferior cotaLsalida)-(entrada i nodo elen neto flujob

j)(i, arco elen ación transportde unitario costoc

j) (i, arco elen flujo de unidades de número

ij

arcos los todosij

ij

ij

i

ij

ALGORITMO DE DIJKSTRAEncuentra la ruta mas corta de un nodo de la red (nodo origen) a cualquier otro nodo, cuando los costos en los arcos (distancias) son no negativos. Los nodos se marcan con marcas Temporales y Permanentes, comenzando por el nodo origen. Un nodo tiene una marca Permanente si se ha encontrado la menor distancia a ese nodo. Un nodo j tiene marca temporal si existe el arco (i, j) y el nodo i tiene marca Permanente.

La marca del nodo j es de la forma [uj,i]=[ui+cij,i], donde ui es la distancia mas corta del nodo origen al nodo i con marca Permanente y cij el costo del arco (i,j). Los nodos que no pueden alcanzarse directamente a partir de un nodo con marca Permanente tendrán marca Temporal igual a .

ALGORITMO DE DIJKSTRA

Sea i=1 el nodo origen• Paso 0: marcar el nodo origen con [0,0], i=1, P={1},

T={2,3,…n}.• Paso 1: j marcar [uj,,i]=[ui+cij,i].Si el nodo j tiene

marca temporal [uj,k] y ui+cij<uj reemplazar [uj,k] por [ui+cij,i].

• Paso 2:hallar kT tal que cik=min{cij,jT}, hacer, T=T-{k}, P=P+{k}. Marcar el nodo k en forma permanente. Si T=Ø parar, sino pasar al Paso 1.

ALGORITMO DE DIJKTRA’S

EJEMPLOLos nodos de la red representa las estaciones de transbordo de un sistema de transporte en una ciudad. Los arcos representan las rutas posibles y las distancias representan el tiempo de recorrido que depende de las paradas. El origen está en el nodo 1 y en el nodo 6 se encuentra el final del recorrido. Se quiere encontrar la ruta mas corta del origen a cada nodo de transbordo y en particular la ruta mas corta al destino final.

RED

1

4

2

5

3

6

3

2

10

1

92

3

4

8 6

4

3

1

SOLUCIÓN

NODO 1 2 3 4 5 6 T={1,2,3,4,5,6},P={}Iter 1 [0,0]p T={2,3,4,5,6},P={1}Iter 2 [0,0]p [3,1] [2,1]p T={2,3,5,6},P={1,4}Iter 3 [0,0]p [3,1]p [2,1]p [6,4] T={3,5,6},P={1,4,2}Iter 4 [0,0]p [3,1]p [13,2] [2,1]p [6,4]p T={3,6},P={1,4,2,5}Iter 5 [0,0]p [3,1]p [8,5]p [2,1]p [6,4]p T={6},P={1,4,2,5,3}Iter 6 [0,0]p [3,1]p [8,5]p [2,1]p [6,4]p [11,3]p T={},P={1,4,2,4,3}

SOLUCIÓNPara determinar la ruta mas corta desde el nodo origen a cualquier otro nodo se procede como sigue:

• Partiendo del nodo terminal escogido (k) buscar en la marca el nodo adyacente [uk,j], es decir el nodo j. Proceder de igual manera hacia atrás en la red. La distancia mínima es uk

SOLUCIÓN En el ejemplo, la ruta más corta del

nodo origen al nodo 6 tiene una distancia igual a 11 y la ruta es:1,4,5,3,6.La ruta mas corta al nodo 3 es:1, 4,5,3 con distancia igual a 8

EJEMPLO: reemplazo de equipo

Se desea determinar la política óptima de sustitución de equipo para cierto horizonte de tiempo, de 2000 a 2005. Al principio de cada año se toma una decisión acerca de si se debe mantener el equipo en operación o si se debe reemplazar. La tabla muestra la estrategia posible de reemplazo y el costo de reemplazo del equipo en función del año en el que se adquiere.

EJEMPLO: continua

Año de adquisición

Costo de reemplazo por años de operación

1 2 3 4 5 2000 100 200 340 700 2001 150 300 400 500 2002 200 2003 80 150 2004 120

EJEMPLO: reemplazo de equipo Cada arco de la red indica una

compra en el año i (nodo i) y su sustitución en el año j (nodo j).

1 2 3 4 5100 150 200 680 120

700340

200

150

300

400500

EJEMPLO: continua

ÁRBOL GENERADOR MINIMALEn una red de n nodos un árbol generador es un conjunto de n-1 arcos que conecta todos los nodos y no contiene ciclos.

El algoritmo GLOTÓN (Greedy method) parte de un nodo cualquiera y conecta cada vez el nodo que se encuentra a menor distancia de cada nodo conectado

ALGORITMO

• Notemos C el conjunto de nodos conectados y NC el conjunto de nodods no conectados de la red.

• Paso 0: comenzar en cualquier nodo de la red y colocar ese nodo en N. Los restantes nodos estarán en NC.

• Paso 1: escoger el nodo de NC mas cercano a un nodo de C. Colocar ese nodo en C y quitar de NC. Repetir hasta que NC=

EJEMPLO: Una pequeña empresa cuenta con 5 computadoras que deben ser conectadas en red. Se desea determinar la longitud mínima de cableado requerido para realizar esta conexión. Las distancias se muestran en la tabla.

DISTANCIA ENTRE CADA OFICINA NODOS 1 2 3 4 5

1 0 1 4 6 2 2 1 0 3 X 2 3 4 3 0 5 2 4 6 X 5 0 4 5 2 2 2 4 0

EJEMPLO: continua

3

2

5

1

4

ayuda 3.2

Documents