iopertivab

1

Unidad 2

Programacin Lineal

Aplicaciones

2

El objetivo general es encontrar el mejor plan de distribucin, es

decir, la cantidad que se debe enviar por cada una de las rutas desde

los puntos de suministro hasta los puntos de demanda.

El mejor plan es aquel que minimiza los costos totales de envo,

produzca la mayor ganancia u optimice algn objetivo corporativo.

Se debe contar con:

i) Nivel de oferta en cada fuente y la cantidad de demanda

en cada destino.

ii) Costo de transporte unitario de mercadera desde cada

fuente a cada destino.

2.1 Modelo de Transporte

3

Tambin es necesario satisfacer ciertas restricciones:

1. No enviar ms de la capacidad especificada desde cada punto de

suministro (oferta).

2. Enviar bienes solamente por las rutas vlidas.

3. Cumplir (o exceder) los requerimientos de bienes en los puntos

de demanda.


4


Esquemticamente se podra ver como se muestra en la siguiente

figura Destinos Fuentes

1 1

2 2

n m

s2

sm

d2

s1 d1

dn

.

.

.

.

.

.

Xij: cantidad transportada desde la fuente i al destino j

C11, X11

Cmn, Xmn

Cij: Costo del transporte unitario desde la fuente i al destino j

donde

Grficamente: Para m fuentes y n destinos

5

Modelo general de PL que representa al modelo de Transporte

ox

dx

sx

xcZ

ij

j

m

i

ij

i

n

j

ij

m

i

n

j

ijij

1

1

1 1

j=1,2,...,n

i=1,2,...,m

El modelo implica que al menos la oferta debe ser igual a la demanda

para toda i y j

minimizar

s a


6

Modelo general de PL que representa al modelo de Transporte

Modelo de transporte equilibrado: Oferta = Demanda

i

n

j

ij Sx1

j=1, 2, 3,....,n j

m

i

ij Dx1

i=1, 2, 3,....,m

0ijxpara toda i y j


Solucin del Modelo de

Transporte


8

Algoritmos Especficos

2.1.1 Regla de la esquina noroeste (MEN)

2.1.2 Mtodo por aproximacin de Vogel (MAV)

2.1.3 Mtodo del costo mnimo (MCM)

2.1.4 Mtodo del paso secuencial y

2.1.5 DIMO (mtodo de distribucin modificada)


9

Descripcin de los algoritmos

La regla de la esquina noroeste, el mtodo de aproximacin

de Vogel y el mtodo del costo mnimo son alternativas para

encontrar una solucin inicial factible.

El mtodo del escaln y el DIMO son alternativas para

proceder de una solucin inicial factible a la ptima.

Por tanto, el primer paso es encontrar una solucin inicial

factible, que por definicin es cualquier distribucin de

ofertas que satisfaga todas las demandas


10

Descripcin de los algoritmos

Una vez obtenida una solucin bsica factible, el algoritmo

procede paso a paso para encontrar un mejor valor para la

funcin objetivo.

La solucin ptima es una solucin factible de costo mnimo

Para aplicar los algoritmos, primero hay que construir una

tabla de transporte.


11

Tabla Inicial

Destinos

Origen 1 2 3 4 n Ofertas

1 C11 C12 C13 C14 .... C1n

2 C21 C22 C23 C24 .... C2n

3 C31 C32 C33 C34 .... C3n

... .... ..... .... .... ....

m Cm1 Cm2 Cm3 Cm4 .... Cmn

Demanda


12

Tabla Inicial del Ejemplo

Plantas

Puertos 1 2 3 4 Oferta

1 12 13 4 6

500

2 6 4 10 11

700

3 10 9 12 4

800

Demanda 400 900 200 500 2000


13

2.1.1 Regla de la esquina Noroeste

Se inicia el proceso desde la esquina izquierda superior

Se ubican tantas unidades como sea posible en la ruta

Cantidad de Unidades = Mnimo(disponibilidad, demanda)

Las siguientes asignaciones se hacen o bien recorriendo hacia la

derecha o bien hacia abajo.

Las demandas se satisfacen recorriendo sucesivamente de

izquierda a derecha y las ofertas se destinan recorriendo de

arriba hacia abajo.


14

Primera asignacin

Plantas


1 12 13 4 6

400 100 500

2 6 4 10 11

700

3 10 9 12 4

800

Demanda 0 400 900 200 500 2000


15

Hasta cuarta asignacin

Plantas


1 12 13 4 6

400 100 100 500

2 6 4 10 11

700 0 700

3 10 9 12 4

100 700 800

Demanda 0 400 0 900 200 500 2000


16

Esquina Noroeste: Solucin final factible

Plantas


1 12 13 4 6

400 100 100 500

2 6 4 10 11

700 0 700

3 10 9 12 4

100 200 500 0 800

Demanda 0 400 0 900 200 500 2000

Valor FO: 400*12+100*13+700*4+100*9+200*12+500*4= $14.200


17

2.1.2 Mtodo de aproximacin de

Vogel (MAV) MAV usa informacin de costos mediante el concepto de costo

de oportunidad para determinar una solucin inicial factible.

Seleccionar en una fila la ruta ms barata y la que le sigue.

Hacer su diferencia (penalidad), que es el costo adicional por

enviar una unidad desde el origen actual al segundo destino y

no al primero.

En nuestro caso, para el puerto1, C13 y C14; Penalidad = 6 - 4

MAV asigna un costo de penalidad por no usar la mejor ruta

en esta fila.


18

2.1.2 Mtodo de aproximacin de Vogel

Lo anterior se repite para cada fila y cada columna, esto es,

determinar todas las penalidades

Los pasos iterativos de MAV son los siguientes:

1. Identificar la fila o columna con la mxima penalidad.

2.Colocar la mxima asignacin posible a la ruta no usada que

tenga menor costo en la fila o columna seleccionada en el punto

1 (los empates se resuelven arbitrariamente)

3. Reajustar la oferta y demanda en vista de esta asignacin.

4. Eliminar la columna en la que haya quedado una demanda 0 (o

la fila con oferta 0), de consideraciones posteriores.

5. Calcular los nuevos costos de penalidad.


19


El MAV contina aplicando este proceso en forma sucesiva

hasta que se haya obtenido una solucin factible.

Los resultados obtenidos se muestran en las siguientes tablas


20


Plantas

Puertos 1 2 3 4 Oferta Penalidades

1 12 13 4 6 2

500

2 6 4 10 11 2

700

3 10 9 12 4 5

800

Demanda 400 900 200 500 2000

Penalidades 4 5 6 2

Calculadas todas las penalidades, la mayor

corresponde a la columna 3 (penalidad = 6)

Paso 1: Identificar mxima penalidad (fila o columna)

Paso 0: Clculo de penalidades


21


Paso 2: Asignacin de unidades (MIN(oferta,demanda))

Paso 3:Reajuste de oferta y demanda

Plantas


1 12 13 4 6

200 300 500

2 6 4 10 11

700

3 10 9 12 4

800

Demanda 400 900 0 200 500 2000


22


Paso 4: Eliminar columna (fila) con demanda (oferta) 0

Plantas


1 12 13 4 6

200 300 500

2 6 4 10 11

700

3 10 9 12 4

800

Demanda 400 900 0 200 500 2000


23


Paso 5: Calcular los nuevos costos de penalidad

Plantas

Puertos 1 2 3 4 Oferta Penalidades

1 12 13 4 6 6

200 300 500

2 6 4 10 11 2

700

3 10 9 12 4 5

800

Demanda 400 900 0 200 500 2000

Penalidades 4 5 2


24


Repitiendo los pasos anteriores, finalmente se llega a la siguiente

solucin

Plantas


1 12 13 4 6

200 300 300 500

2 6 4 10 11

700 0 700

3 10 9 12 4

400 200 200 600 800

Demanda 400 900 0 200 200 500 2000

Es solucin factible? m + n - 1 = 6? SI

Costo: 200*4+300*6+700*4+400*10+200*9+200*4 = $12.000


25

2.1.3. Mtodo del Costo Mnimo

1. Dada una tabla de transporte

2. Asignar la mayor cantidad de unidades a la variable

(ruta) con el menor costo unitario de toda la tabla.

3. Tachar la fila o columna satisfecha.

4. Ajustar oferta y demanda de todas las filas y columnas

5. Si hay ms de una fila o columna no tachada repetir

los puntos 2, 3 y 4

Algoritmo

Fundamento

Asignar la mayor cantidad de unidades a una ruta

disponible de costo mnimo


26

2.1.3. Mtodo del Costo Mnimo (cont.)

Ejemplo: Aplicar MCM a la tabla de transporte

Plantas


1 12 13 4 6

500

2 6 4 10 11

700

3 10 9 12 4

800

Demanda 400 900 200 500 2000

Unidades a asignar = MIN(200,400) = 200

Existen tres rutas costo mnimo. Elijamos la 1_3 Paso 2


27


Paso 3: Tachar fila o columna (columna 3)

Plantas


1 12 13 4 6

200 300 500

2 6 4 10 11

700

3 10 9 12 4

800

Demanda 400 900 0 200 500 2000

An quedan ms de una fila o columna sin tachar. Ir a paso 2

Ajustar ofertas y demandas (fila 1 y columna 3)

Paso 5

Paso 4


28


Paso 4: Tachar ajustar fila 3 y columna 4

Plantas


1 12 13 4 6

200 300 500

2 6 4 10 11

700

3 10 9 12 4

500 300 800

Demanda 400 900 0 200 0 500 2000

An quedan ms de una fila o columna sin tachar. Ir a paso 2 Paso 5

Paso 2: Ruta de costo menor -> 3_4 ( 2_2)

Unidades = MIN(500,800) = 500

Paso 3: Tachar columna 4


29




1 12 13 4 6

200 300 500

2 6 4 10 0

700 0 700

3 10 9 12 4

500 300 800

Demanda 400 200 900 0 200 0 500 2000


Paso 2: Ruta de costo menor -> 2_2

Unidades = MIN(700,900) = 300

Paso 3: Tachar fila2


30




1 12 13 4 6

200 300 500

2 6 4 10 0

700 0 700

3 10 9 12 4 100

200 500 300 800

Demanda 400 200 900 0 200 0 500 2000



Unidades = MIN(200,300) = 200

Paso 3: Tachar columna 2


31




1 12 13 4 6

200 300 500

2 6 4 10 0

700 0 700

3 10 9 12 4 100 0

100 200 500 300 800

Demanda 300 400 200 900 0 200 0 500 2000



Unidades = MIN(400,100) = 100

Paso 3: Tachar fila 3


32




1 12 13 4 6 0

300 200 300 500

2 6 4 10 0

700 0 700

3 10 9 12 4 100 0

100 200 500 300 800

Demanda 300 400 200 900 0 200 0 500 2000

Queda slo una fila sin tachar. Terminar Paso 5


Unidades = MIN(300,300) = 300

Paso 3: Tachar fila 1 columna 1 (slo una de ellas)


33


Comparacin de los resultados

Es solucin factible? m + n - 1 = 6? SI

Costo: 300*12+200*4+700*4+100*10+200*9+500*4 = $12.000

Mtodo Rutas Costo

MEN 6 $14.200

MAV 6 $12.000

MCM 6 $12.000

Los tres mtodos entregan soluciones bsicas factibles,

pero ninguno asegura que la solucin sea ptima.

Conclusin


34

2.1.4. Mtodo de Pasos Secuenciales

Este mtodo comienza con una solucin inicial factible.

En cada paso se intenta enviar artculos por una ruta que

no se haya usado en la solucin factible actual, en tanto

se elimina una ruta usada actualmente.

En cada cambio de ruta debe cumplirse que:

1. La solucin siga siendo factible y

2. Que mejore el valor de la funcin objetivo

El procedimiento termina cuando no hay cambio de rutas

que mejoren el valor de la funcin.

Fundamento


35

2.1.4. Mtodo de pasos secuenciales (cont..)

Usar la solucin actual (MEN, MAV o MCM) para crear una

trayectoria nica del paso secuencial. Usar estas trayectorias

para calcular el costo marginal de introducir a la solucin

cada ruta no usada.

Si todos los costos marginales son iguales o mayores que

cero, terminar; se tendr la solucin ptima. Si no, elegir la

celda que tenga el costo marginal ms negativo (empates se

resuelven arbitrariamente)

Usando la trayectoria del paso secuencial, determine el

mximo nmero de artculos que se pueden asignar a la ruta

elegida en el punto 2 y ajustar la distribucin adecuadamente.

Regrese al paso 1

Algoritmo

1

2

3

4


36


a) Ponga un signo + en la celda de inters no ocupada

b) Ponga un signo - en una celda usada de la misma fila

c) Ponga un + en una celda usada de la misma columna

El proceso contina alternando los signos + y - tanto en las filas

como en las columnas hasta que se obtenga una sucesin de

celdas (trayectoria) que satisfagan dos condiciones

1. Hay un signo + en la celda desocupada original de inters, y

2. Cualquier fila o columna que tenga un signo + debe tener

tambin un signo - y viceversa.

Algoritmo Paso 1


37


Algoritmo Paso 1

Plantas


1 12 13 4 6

400 100 100 500

2 6 4 10 11

700 0 700

3 10 9 12 4

100 200 500 0 800

Demanda 0 400 0 900 200 500 2000

Solucin bsica factible obtenida aplicando el mtodo de la Esquina Noroeste


38


Algoritmo Paso 1

Plantas


1 12 13 4 6

400 100 - + 100 500

2 6 4 10 11

700 0 700

3 10 9 12 4

100 + 200 - 500 0 800

Demanda 0 400 0 900 0 200 0 500 2000

Trayectoria 1: +C13-C12+C32-C33


39


Algoritmo Paso 1

Plantas


1 12 13 4 6

400 100 - + 100 500

2 6 4 10 11

700 0 700

3 10 9 12 4

100 + 200 - 500 0 800

Demanda 0 400 0 900 0 200 0 500 2000

1: +(4)-(13)+(9)-(12)= -12 2: +(6)-(13)+(9)-(4) = -2

3: +(6)-(4)+(13)-(12)= 3 4: +(10)-(4)+(9)-(12) = 3

5: +(11)-(4)+(9)-(4) = 12 6: +(10)-(9)+(13)-(12)= 2

Costos de las Trayectorias


40


Algoritmo Paso 2

1: +(4)-(13)+(9)-(12)= -12 2: +(6)-(13)+(9)-(4) = -2

3: +(6)-(4)+(13)-(12)= 3 4: +(10)-(4)+(9)-(12) = 3

5: +(11)-(4)+(9)-(4) = 2 6: +(10)-(9)+(13)-(12)= 2

La solucin factible NO es ptima !!

Se selecciona la trayectoria 1 (costo marginal ms negativo)


41


Algoritmo Paso 3 (Generacin de la nueva tabla)

Cuntas unidades se pueden asignar a la ruta elegida?

Accin Ruta Unidades disponibles en

celdas decrecientes

Aumentar 1 unidad 1_3

Disminuir 1 unidad 1_2 100

Aumentar 1 unidad 3_2

Disminuir 1 unidad 3_3 200


42


Algoritmo

Plantas


1 12 13 4 6

400 - 100 + 100 500

2 6 4 10 11

700 0 700

3 10 9 12 4

200 + 100 - 500 0 800

Demanda 0 400 0 900 0 200 0 500 2000

Paso 3 (Generacin de la nueva tabla)

Costo: $13.000


43


Algoritmo Paso 4

Volver al Paso 1:

Para cada trayectoria evaluar costo marginal

Plantas


1 12 13 4 6

400 100 100 500

2 6 4 10 11

700 0 700

3 10 9 12 4

200 100 500 0 800

Demanda 0 400 0 900 0 200 0 500 2000


44


Algoritmo Paso 2: Eleccin de CMg menor

Plantas


1 12 13 4 6

400 +12 100 +10 100 500

2 6 4 10 11

-9 700 +3 +12 0 700

3 10 9 12 4

-10 200 100 500 0 800

Demanda 0 400 0 900 0 200 0 500 2000

La celda ms negativa es c 31 (-10) y la trayectoria es:

C31 C33 + C13 C11


45



Cuntas unidades se pueden asignar a la ruta elegida?

Accin Ruta Unidades disponibles en

celdas decrecientes

Aumentar 1 unidad 31

Disminuir 1 unidad 33 100

Aumentar 1 nidad 13

Disminuir 1 unidad 11 400


46



Costo: $12.000

Plantas


1 12 13 4 6

300 200 100 500

2 6 4 10 11

700 0 700

3 10 9 12 4

100 200 500 0 800

Demanda 0 400 0 900 0 200 0 500 2000


47


Algoritmo Paso 4

Volver al Paso 1:

Para cada trayectoria evaluar costo marginal Plantas


1 12 13 4 6

300 200 100 500

2 6 4 10 11

700 0 700

3 10 9 12 4

100 200 500 0 800

Demanda 0 400 0 900 0 200 0 500 2000


48


Algoritmo Paso 2: Determinar costos marginales

Todas rutas son no negativas (positivas o cero)

Solucin factible ptima!!! $12.000

Compare esta solucin con la obtenida con MAV y MCM ...?

Plantas


1 12 13 4 6

300 +2 200 0 100 500

2 6 4 10 11

+1 700 +13 +12 0 700

3 10 9 12 4

100 200 +10 500 0 800

Demanda 0 400 0 900 0 200 0 500 2000


49

2.1.5. Mtodo de Distribucin Modificada (DIMO)

Algoritmo

1. Usar la solucin actual (NE, MAV o MCM) y las siguientes

operaciones (a) y (b) para determinar el costo marginal de enviar

material para cada una de las rutas no usadas.

Asociar a cada fila un ndice ui y a cada columna un ndice vj

a) Hacer u1 = 0. Encuntrese los ndices de las filas u2, ..., um y los

ndices de las columnas v1, ...., vn tales que cij = ui + vj para cada

celda usada.

b) Sea eij = cij - (ui+vj) para cada celda no usada; eij ser el costo

marginal de introducir la celda (ruta) i, j a la solucin.

Los pasos 2 a 4 son los mismos que en el mtodo secuencial.


50


Aplicar el algoritmo al problema en estudio y

comparar resultados obtenidos con los mtodos

anteriores

Comentar resultados

Qu explica que existan dos soluciones

ptimas factibles?


51


Aplicacin

Costo por

Ruta en uso motor ($) Ecuacin

11 12 u1 + v1 = 12

12 13 u1 + v2 = 13

22 4 u2 + v2 = 4

32 9 u3 + v2 = 9

33 12 u3 + v3 = 12

34 4 u3 + v4 = 4

Plantas


1 12 13 4 6

400 100 100 500

2 6 4 10 11

700 0 700

3 10 9 12 4

100 200 500 700 800

Demanda 0 400 0 900 200 500 2000

Paso 0: Asociar ndices

ui

vj


52


Paso1.a) Solucionar la ecuacin

Existen 6 ecuaciones y siete variables entonces se hace u1 = 0

(puede ser cualquiera) y se determina el resto de los ndices

v1 = 12 v2 = 13 u2 = - 9 u3 = -4 v3 = 16 v4 = 8

Paso 1.b) Calcular los costos marginales para cada celda no usada.

eij = cij - (ui + vj)


53


Costos marginales para las celdas no usadas.


1) e13 = c13 - (u1 + v3)= 4 - (0 + 16) = -12

2) e14 = c14 - (u1 + v4)= 6 - (0 + 8) = -2

3) e21 = c21 - (u2 + v1)= 6 - (-9 + 13) = 2

4) e23 = c23 - (u2 + v3)= 10 - (-9 + 16) = 3

5) e24 = c24 - (u2 + v4)= 11 - (-9 + 8) = 12

6) e31 = c31 - (u3 + v1)= 10 - (-4 + 12) = 2


54


Plantas


1 12 13 4 6

400 100 -12 -2 100 500

2 6 4 10 11

2 700 3 12 0 700

3 10 9 12 4

2 100 200 500 700 800

Demanda 0 400 0 900 200 500 2000

Paso 2: Prueba de Optimalidad.

Hay costos negativos por lo tanto no es ptima

La ruta de reasignacin es: +C13 -C33 +C32 -C12 (ms negativo, -12)


55


Paso 3: Asignacin de unidades a la ruta elegida.

Unidades disponibles a mover:

Disminuir 1 unidad C12 100


Plantas


1 12 13 4 6

400 100 100 500

2 6 4 10 11

700 0 700

3 10 9 12 4

200 100 500 700 800

Demanda 0 400 0 900 200 500 2000


56


Vuelta al Paso 1:

Costo por


11 12 u1 + v1 = 12

13 4 u1 + v3 = 4

22 4 u2 + v2 = 4

32 9 u3 + v2 = 9

33 12 u3 + v3 = 12

34 4 u3 + v4 = 4


Se hacer u1 = 0 y se determina el resto de los ndices

v1 = 12 v2 = 1 v3 = 4 v4 = -4 u2 = 3 u3 = 8

Paso 1.b) Calcular los costos marginales para cada

celda no usada. eij = cij - (ui + vj)


57




1) e12 = c12 - (u1 + v2)= 13 - (0 + 1) = 12

2) e14 = c14 - (u1 + v4)= 6 - (0 - 4) = 10

3) e21 = c21 - (u2 + v1)= 6 - (3 + 12) = -9

4) e23 = c23 - (u2 + v3)= 10 - (3 + 4) = 3

5) e24 = c24 - (u2 + v4)= 11 - (3 - 4) = 12

6) e31 = c31 - (u3 + v1)= 10 - (8 + 12) = -10


58



Hay costos negativos por lo tanto no es ptima

La ruta de reasignacin es: +C31 -C33 +C13 -C11

Plantas


1 - 12 13 + 4 6

400 19 100 1 100 500

2 6 4 10 11

0 700 3 12 0 700

3 + 10 9 - 12 4

-1 200 100 500 700 800

Demanda 0 400 0 900 200 500 2000


59


Paso 3: Asignacin de unidades a la ruta elegida.

Unidades disponibles a mover:



Plantas


1 12 13 4 6

300 200 100 500

2 6 4 10 11

700 0 700

3 10 9 12 4

100 200 500 700 800

Demanda 0 400 0 900 200 500 2000


60


Vuelta al Paso 1:


u1 = 0 y se determina el resto de los ndices

v1 = 12 v2 = 11 v3 = 4 v4 = 6 u2 = - 7 u3 = -2

Paso 1.b) Calcular los costos marginales para cada

celda no usada. eij = cij - (ui + vj)

Costo por


11 12 u1 + v1 = 12

13 4 u1 + v3 = 4

22 4 u2 + v2 = 4

31 10 u3 + v1 = 10

32 9 u3 + v2 = 9

34 4 u3 + v4 = 4


61




1) e12 = c12 - (u1 + v2)= 13 - (0 + 11) = 2

2) e14 = c14 - (u1 + v4)= 6 - (0 + 6) = 0

3) e21 = c21 - (u2 + v1)= 6 - (-7 + 12) = 1

4) e23 = c23 - (u2 + v3)= 10 - (-7 + 4) = 13

5) e24 = c24 - (u2 + v4)= 11 - (-7 + 6) = 12

6) e33 = c33 - (u3 + v3)= 12 - (-2 + 4) = 10


62



No hay costos negativos por lo tanto es ptima

VO = 300*12+200*4+700*4+100*10+200*9+500*4=$12.000

Plantas


1 12 13 4 6

300 0 200 0 100 500

2 6 4 10 11

1 700 13 12 0 700

3 10 9 12 4

100 200 10 500 700 800

Demanda 0 400 0 900 200 500 2000

Ver Transporte RPG Equilibrio


63

2.1.6. Modelo de Transporte: Situaciones Especiales

1. Solucin en problemas de maximizacin de transporte

2. El caso en que la oferta excede a la demanda.

3. Eliminacin de rutas inaceptables.

4. Degeneracin en problemas de transporte.

5. Propiedades especiales del modelo de transporte


64


1. Solucin en problemas de maximizacin de transporte.

a) Se utilizan los beneficios marginales en lugar de los costos.

Se asignar unidades a la celda que tenga el mayor valor

marginal y el procedimiento concluir cuando todas las rutas

tengan valores marginales negativos.

b) Convertir la tabla de beneficios en una tabla de costo: Se

busca el beneficio mayor, en cada celda se le resta al mayor

el beneficio de la celda. Ejemplo:


65


Tabla de beneficios

14 19 12

17 19 15

16 20 11

6 1 8

3 1 5

4 0 9

2

3

Destinos

Fu

en

tes

1 2 3

1

Destinos

1 2 3

Fu

en

tes

1

2

3

Mayor = 20

Tabla de costo


66


2. El caso en que la oferta excede a la demanda.

Se utiliza un destino ficticio en la tabla de transporte. Se

considera como nulo el costo de enviar una unidad a dicho

destino desde cada una de las fuentes (orgenes).

Si la demanda es mayor que la oferta el problema no tiene

solucin factible, sin embargo el administrador podra

abastecer toda la demanda que sea posible a un costo

mnimo.

Se utiliza un origen ficticio. El costo de abastecer cualquier

destino desde dicho origen ser cero. Sin embargo podra

haber un cargo por orden no cubierta.

Ver Transporte RPG (O>D) y (O

67


3. Eliminacin de rutas inaceptables.

Se asocia a una ruta no aceptable un costo lo suficientemente

alto para que no sea atrayente la ruta en cuestin. El costo M

Por ejemplo: producir en abril para vender en febrero del mismo

ao.

4. Degeneracin en problemas de transporte.

Se dice que un problema se degenera cuando hay menos de

m + n - 1 rutas ocupadas. Esto puede ocurrir cuando

simultneamente se satisface una demanda y se agota una

oferta.

Ver Transporte RPG (inaceptable)


68


5. Propiedades especiales del modelo de transporte

Todo problema de transporte es posible resolverlo mediante

algoritmos que usan slo la adicin y la sustraccin.

Si todas las ofertas y demandas tienen valores enteros en un

problema de transporte, los valores ptimos de las variables

de decisin sern tambin enteros.


69

Ejercicios

Suponer que se tienen tres fbricas M1, M2 y M3 que producen

39, 48 y 33 toneladas respectivamente, de un cierto producto

que debe llevarse a cuatro destinos, D1, D2, D3 y D4, los cuales

requieren 40, 37, 18 y 25 toneladas.

Los costos estn dados por la siguiente tabla:


1

D1 D2 D3 D4

M1 2 3 1 2

M2 1 4 7 6

M3 8 9 4 5

70

Planificacin de la produccin:


2

Periodo Capacidad de Produccin

Mxima (unidades)

Demanda a

satisfacer

Costo de

Produccin ($)

Costo de

Almacenaje ($)

1 1200 900 15 1.2

2 800 800 18 1.4

3 1100 1000 17 1.1

4 900 700 20 1.5

Cunto hay que producir en cada periodo para satisfacer la

demanda al mnimo costo (tanto de produccin como de

almacenaje)?.

Supuesto: No existe inventario inicial ni final.

Plantear el problema usando el modelo de transporte.

Encuentre las respuestas usando Solver.

71

Situacin:

Asignar m trabajos (o trabajadores) a n mquinas.

Un trabajo i (=1, 2, 3 ,...,m) cuando se asigna a la mquina

j (=1,2,....,n) incurre en un costo cij.

El objetivo es asignar los trabajos a las mquinas uno a uno

al menor costo.

La formulacin de este problema puede considerarse como

un caso especial del modelo de transporte.

2.2 Modelo de Asignacin

72

Descripcin

Los trabajos representan las fuentes y las mquinas los

destinos

La oferta disponible en cada fuente es 1 como tambin

lo es la demanda en cada destino.

cij es el costo de transportar (asignar) el trabajo i a la

mquina j

El costo puede representar tambin caractersticas de

competencia de cada trabajador

73

Descripcin

En el caso que un trabajo no deba ser asignado

(porque no cumple con los requisitos) a una mquina

(actividad) en particular, este costo debe tener un

valor alto (M)

En el caso de existir desequilibrio, esto es, ms

trabajos que mquinas o ms mquinas que trabajos,

hay que equilibrar con mquinas o trabajos figurados

(ficticios), logrando de esta forma que m = n

74

Expresin matemtica del modelo

0, si el i-simo trabajo no se asigna a la j-sima mquina

1, si el i-simo trabajo se asigna a la j-sima mquina Xij =

Mquina 1 2 .. n

C11 C12 .. C1n

C21 C22 .. C2n

.. .. .. ..

Cn1 Cn2 .. Cnn

1

2

..

n

Trabajo

1

1

..

1

1 1 .. 1

75

Por lo tanto el modelo est dado por:

minimizar z =

n

i

n

j

ijij xc1 1

sujeto a 11

n

j

ijx i=1,2, ...,n

11

n

i

ijx j=1,2,..n

xij = 0 bien 1

76

Ejemplo:

La gerencia general de RPG (ejemplo de transporte) con sede

en Bruselas, este ao, como parte de su auditora anual, decidi

que cada uno de sus cuatro vicepresidentes visite e inspeccione

cada una de sus plantas de ensamblaje durante las primeras dos

semanas de junio. Las plantas estn ubicadas en Leipzig

(Alemania), Nancy (Francia, Lieja (Blgica) y Tilburgo

(Holanda).

Para decidir a que vicepresidente enviar a una planta

determinada, se asignaron puntos (costos) a cada uno de ellos

de acuerdo a su experiencia, habilidades lengusticas, tiempo

que durar la inspeccin y otros. Estos datos se muestran en la

siguiente tabla:

77

Ejemplo

PLANTA

Leipzig (1) Nancy(2) Lieja (3) Tilburgo(4)

Finanzas (F) (1) 24 10 21 11

Mercadotecnia(M) (2) 14 22 10 15

Operaciones (O) (3) 15 17 20 19

Personal(P) (4) 11 19 14 13

Plantear el modelo de PL

78

Ejemplo: Modelo de PL

MIN Z = 24 X11 + 10 X12 + ... + 14 X43 + 13 X44

sujeto a:

a) Oferta X11 + X12 + X13 + X14 = 1

X21 + X22 + X23 + X24 = 1

X31 + X32 + X33 + X34 = 1

X41 + X42 + X43 + X44 = 1

b) Demanda X11 + X21 + X31 + X41 = 1

X12 + X22 + X32 + X42 = 1

X13 + X23 + X33 + X43 = 1

X14 + X24 + X34 + X44 = 1

c) No negatividad Xij >= 0 i=1,...,4, j=1,....,4

79

Mtodos de Solucin

Existen varias formas de obtener la solucin:

a) Listar todas las alternativas posibles con sus costos y seleccionar

la de menor costo (algoritmo exhaustivo)

b) Mtodo Hngaro: mtodo iterativo

a) Listar todas las alternativas:

Cuntas alternativas posibles existen?

- El primer trabajo se puede asignar de n formas formas posibles

- El segundo de n-1 formas

- El ltimo slo de 1 forma

En total existen n! formas de hacer la asignacin completa

80

Mtodo Hngaro:

Paso 0: Construir la matriz de asignacin

Para obtener la solucin ptima cada nueva matriz de asignacin

debe satisfacer:

Propiedad 1: Todos los nmeros son no negativos

Propiedad 2: Cada fila y cada columna tiene al menos una celda con un valor cero

Paso 1:

a) Reduccin de filas: Restar el costo menor de cada fila a la fila correspondiente y/o

b) Reduccin de columnas: Restar el costo menor de cada columna a la columna correspondiente

Con esto se crea una nueva matriz con las propiedades 1 y 2

81

Mtodo Hngaro:

Paso 2: Determinar si la matriz es reducida (Prueba de Optimalidad).

Trazar el menor nmero de lneas rectas sobre las filas y columnas

para cubrir todos los ceros.

Si el nmero de rectas es igual al nmero de filas o columnas se dice

que esta matriz es reducida.

Si la matriz no es reducida pasar al paso 3, sino pasar al paso 4

82

Mtodo Hngaro:

Paso 3: Movimiento

De todas las celdas no cruzadas identifique una con el menor

valor y haga lo siguiente:

a) Restar el valor a cada celda no cruzada

b) Sumar el valor a cada celda de interseccin de rectas

Volver al paso 2

83

Mtodo Hngaro:

Paso 4: Solucin ptima (Asignacin)

Primero se asigna a las que tengan slo una alternativa, se van

marcando y as sucesivamente

Determinar el costo: Se suman todos los costos correspondientes

a las asignaciones (o sumar todos los pi y qj).

Qu valor se obtiene al sumar todos los valores que se restaron

en las reducciones de filas y columnas?

84

Ejemplo: Aplique el mtodo Hngaro al ejemplo

1 2 3 4 pi

F 24 10 21 11

M 14 22 10 15

O 15 17 20 19

P 11 19 14 13

qj

Paso 0: Matriz de Asignacin

Nota: En negrita los menores de cada fila

85

Paso 1: Reduccin de filas y columnas

1 2 3 4 pi

F 14 0 11 1 10

M 4 12 0 5 10

O 0 2 5 4 15

P 0 8 3 2 11

qj 1

1 2 3 4 pi

F 14 0 11 0 10

M 4 12 0 4 10

O 0 2 5 3 15

P 0 8 3 1 11

qj 1

86

Paso 2: Determinar si la matriz es reducida

1 2 3 4 pi

F 14 0 11 0 10

M 4 12 0 4 10

O 0 2 5 3 15

P 0 8 3 1 11

qj 1

No es reducida: slo tres rectas (para ser reducida deben ser 4)

Ir al paso 3

87

Paso 3: Movimiento (Seleccionar el menor: restar a las no tachadas, sumar a las intersecciones)

1 2 3 4 pi

F 14 0 11 0 10

M 4 12 0 4 10

O 0 2 5 3 15

P 0 8 3 1 11

qj 1

1 2 3 4 pi

F 15 0 12 0 10

M 4 11 0 3 10

O 0 1 5 2 15

P 0 7 3 0 11

qj 1 + 1

Volver al paso 2 !!

88

Iteracin paso 2:

1 2 3 4 pi

F 15 0 12 0 10

M 4 11 0 3 10

O 0 1 5 2 15

P 0 7 3 0 11

qj 1 + 1

Se tachan todos los ceros con cuatro rectas, por tanto es ptima

Ir al paso 4 !!

89

Paso 4: Asignacin

1 2 3 4 pi

F 15 0 12 0 10

M 4 11 0 3 10

O 0 1 5 2 15

P 0 7 3 0 11

qj 1 + 1

Costo = c12 + c23 + c31 +c44

= 10+10+15+13 = 48

ji qpCosto

=10 + 10 + 15 + 11 + 1 + 1 = 48

Ver Asignacin RPG

90

Modelo de Asignacin: Otras consideraciones

El modelo de asignacin de RPG es un modelo de minimizacin

en el cual el nmero de vicepresidentes es igual al nmero de

plantas, y todas las asignaciones posibles son aceptables.

Consideremos ahora modelos tipo asignacin donde no todas las

condiciones anteriores se cumplen. En particular se considerarn

situaciones en las que:

1 Hay una desigualdad entre el nmero de personas por

asignar y el nmero de destinos que requieren personas

asignadas.

2 Hay un modelo de maximizacin

3 Existen asignaciones inaceptables

91


1. Ofertas y demandas desiguales

a) Oferta mayor que la demanda

Suponer que el presidente de RPG quiere auditar a la planta de

Tilburgo, por tanto tendr que decidir cual de los cuatro

vicepresidentes debe asignar a cada una de las tres plantas

restantes.

Solucin: Se elimina la restriccin que requera un

vicepresidente para Tilburgo. El resultado de este cambio es que

la holgura para uno de los cuatro vicepresidentes ser 1 en la

nueva solucin ptima

Ver Asignacin RPG (O>D)

92


1. Ofertas y demandas desiguales

b) Demanda mayor que la oferta

Suponer que el vicepresidente de Personal tiene que viajar a

Illinois durante la primer semana de junio, por lo tanto no puede

participar en la auditora en Europa.

Solucin: Se agrega un vicepresidente ficticio (igual al modelo

de transporte) para obtener una solucin factible, pero es claro

que una de las plantas quedar sin auditar.

93


2. Hay un modelo de maximizacin

La respuesta de asignacin es un beneficio y no un costo

Ejemplo: Suponga que RPG tiene que asignar vendedores a sus

territorios de venta.

Existen cuatro personas bien capacitadas listas para ser

asignadas y tres territorios requieren un nuevo vendedor. Uno

de los vendedores no ser asignado.

En este caso la asignacin de un vendedor cualquiera a un

territorio se mide por el incremento marginal esperado en la

contribucin de dicha asignacin a las ganancias.

94


2. Hay un modelo de maximizacin

La matriz de ganancia es la siguiente

Contribucin del

Vendedor\a

Territorio

1

Territorio

2

Territorio

3

A 40$ 30$ 20$

B 18$ 28$ 22$

C 12$ 16$ 20$

D 25$ 24$ 27$

Ver Asignacin Vendedores RPG

95


3. Situaciones con asignaciones inaceptables

Ejemplo: Suponga que el presidente de RPG no tiene

el menor deseo de que el vicepresidente de

Operaciones realice una auditora a la Planta Nancy.

Solucin: Asignar un costo arbitrariamente alto a esta

ruta, de tal modo que al restar de l cualquier

nmero finito se obtiene siempre un valor mayor que

otros nmeros relevantes

Ver Asignacin RPG inaceptable

96

2.3 Modelo de Transbordo Este modelo permite que las unidades no vayan

directamente desde un origen a un destino, sino

que pasen por nodos intermedios o transitorios.

Cada origen, punto intermedio y destino final se representan

como nodos y se conectan a travs de arcos dirigidos

Restriccin en cada nodo transitorio:

suma flujos entrantes = suma flujos saliente

Tambin se puede representar por medio de una matriz donde un

mij = 1 cuando existe un enlace directo entre el nodo i y el nodo

j; y mij = 0 cuando no hay enlace directo entre estos nodos

97

Modelo de Transbordo: Algoritmo

Inicializacin: Encuentre un plan de embarque factible que

satisfaga todas las restricciones de suministro y demanda, al

mismo tiempo que mantiene un equilibrio en todos los nodos

de transbordo.

Prueba de Optimalidad: Pruebe el plan de embarque actual

para ver si es ptimo, es decir, si es el plan que incurre en los

costos totales mnimos. Si es as, detngase con la solucin

ptima, sino vaya al paso 3.

Movimientos: Use el hecho de que el plan de embarque

actual no es ptimo para crear un nuevo plan de embarque

factible con menos costo total que el actual. Vaya al paso 2.

1

2

3

98

Consideraciones:

Los pasos del algoritmo son anlogos a los del algoritmo de

pasos sucesivos (escaln).

Tanto los nodos origen como los destinos pueden ser a su vez

nodos de transbordo.

Al igual que el modelo de transporte, puede haber desequilibrio,

en ese caso se agregan fuentes o destinos ficticios con costo cero.

El numero total del sistema est dado por el total de la oferta o de

la demanda.

A cada nodo de transbordo se asigna un suministro (demanda)

igual a su suministro (demanda) original (cero, si no coincide

originalmente con un destino) ms el total de unidades del

sistema. Esto permite que todas las unidades puedan pasar por un

empalme dado.

99

Ejemplo 1:

Determnese un programa de embarque que cubra todas las

demandas a un costo mnimo total para los datos

correspondientes al siguiente grafo (costo en $).

3 4

2 4

3

7 2

1 3 5

2 4 6

+95 -30

+70

+15

-30 -45

8

100

Solucin

Los sitios 1 y 2 son orgenes

Los sitios 5 y 6 son destinos

El sitio 3 es origen y empalme

El sitio 4 es destino y empalme

La oferta es mayor que la demanda por tanto se requiere un

destino ficticio que demande 75 unidades

Agregar 180 unidades a cada empalme (oferta y demanda)

El costo de las unidades que van de un empalme (como origen)

a l mismo (como destino) y de cualquier origen al sitio ficticio

es cero.

A las rutas no permitidas se les asocia un valor relativamente

alto (por 1.000)

101

La tabla inicial es:

3 4 5 6 F Oferta

1 95

3 1000 8 1000 0

2 70

2 7 1000 1000 0

3 195

0 3 4 4 0

4 180

1000 0 1000 2 0

Demanda 180 210 30 45 75

Or

genes

Destinos

102

La tabla final es:

3 4 5 6 F Oferta

1 20 75 95

3 1000 8 1000 0

2 70 70

2 7 1000 1000 0

3 90 30 30 45 195

0 3 4 4 0

4 180 180

1000 0 1000 2 0

Demanda 180 210 30 45 75

Destinos

Or

genes

Costo = 20*3+75*0+70*2+90*0+30*3+30*4+45*4+180*0=$590

103

Ejemplo 2:

Una corporacin necesita transportar 70 unidades de un producto, del sitio 1 a

los sitios 2 y 3 en cantidades de 45 y 25 unidades, respectivamente. Las tarifas

cij (en miles de pesos por unidad) de carga area entre los sitios comunicados

por carguero se dan en la tabla, en la cual las lneas punteadas indica que no hay

servicio disponible. Determnese un programa de embarque que asigne el

nmero requerido de artculos a cada destino, a un costo mnimo de transporte.

Ningn embarque requiere de vuelo directo, se permiten los envos empleando

puntos intermedios.

1 2 3 4

1 .... 38 56 34

2 38 ... 27 ...

3 56 27 ... 19

4 34 ... 19 ...

104

Ejemplo 3:

1

2

3

4

5 7

6

8

9

10

11

100

200

150

120

80

70

110

2

3

4

4 4

5

5

6

6

6

7

7

7

8

8

Nodos de transbordo

105

Planteamiento del modelo PL :

Plantear el modelo de PL para el ejemplo mostrado en el

grafo anterior.

106

2.4. Modelos de Redes

2.4.1 Teora de Grafos

2.4.2 Modelo de la Ruta ms corta

2.4.3 Modelo del rbol Expandido Mnimo

2.4.4 Problema del Flujo Mximo

107

2.4.1 Introduccin a la Teora de Grafos

Grafo no dirigido:

Un grafo no dirigido G consiste en un conjunto V de vrtices

(o nodos) y un conjunto E de lados (ramas o enlaces) tales que

cada lado e E est asociado a un par no ordenado de vrtices v y w. Si un lado e est asociado a un nico par de vrtices v y

w, entonces e= (v,w) o e=(w,v).

Grafo dirigido:

Un grafo dirigido (o digrafo) G consiste en un conjunto V de

vrtices (o nodos) y un conjunto E de lados (o ramas) tales que

cada lado e E est asociado a un par ordenado de vrtices. Si un lado e est asociado a un par ordenado nico de vrtices v y

w, se escribe e = (v,w).

108


Se dice que un lado e = (v,w) de un grafo (dirigido o no dirigido) es

incidente en v y w. Se dice que los vrtices v y w son incidentes

en e y tambin son vrtices adyacentes.

Si G es un grafo (dirigido o no dirigido) con un conjunto de vrtices

V y un conjunto de lados E, se escribe G = (V,E)

Nodo (Vrtice):

Un crculo de una red utilizada para representar una planta,

almacn o tienda.

Nodo de Suministro:

Nodo desde le cual los productos se van a enviar.

109


Nodo de demanda:

Nodo que va a recibir los productos para cumplir con una

demanda conocida.

Nodo de transbordo:

Nodo que recibe productos desde otros nodos para su

distribucin.

Arco (enlace):

Lnea de una red que conecta un par de nodos. Se le utiliza para

representar una ruta vlida desde el nodo origen al nodo de

distribucin.

110


Arco dirigido:

Indica el sentido de movimiento de los productos.

Camino:

Una secuencia de nodos en una red unidos por arcos (dirigidos o

no dirigidos)

Trayectoria (lazo):

Es un camino cerrado (ciclo) donde el primer nodo es a su vez el

ltimo.

111


Representacin Matricial

i) Matriz de Adyacencia

ii) Matriz de costo (beneficio)

Representacin de un grafo:

Un grafo se puede representar matemticamente como:

a) Una matriz

b) Una lista enlazada

c) rbol

112

2.4.1 Introduccin a la Teora de Grafos (cont.)

Matriz de Adyacencia:

Para un grafo G, es una matriz A de dimensin NxN,

donde A[i,j] es verdadero (1) si, y slo si, existe un arco

que vaya del vrtice i al vrtice j. En ausencia de arco

directo se representa generalmente por 0.

Ejemplo: Dado el siguiente grafo encontrar su matriz de

adyacencia

113


2

3 4

1

1 2 3 4

1 1 1

2 1

3 1

4 1

114


Matriz de Costo:

Para un grafo G etiquetado, es una matriz C de dimensin

NxN, donde A[i,j] es el costo (valor de la etiqueta) si, y

slo si, existe un arco que vaya del vrtice i al vrtice j.

En ausencia de arco directo se representa generalmente

por infinito (costo extremadamente alto, para la

simulacin se hace uso de un valor fuera de contexto).

Ejemplo: Dado el siguiente grafo encontrar su matriz de costo

115


2

3 4

1

1 2 3 4

1 10 15

2 12

3 20

4 5

10

15 20 12

5

116


Para un grafo no dirigido, tanto la matriz de adyacencia

como la matriz de costo son simtricas, esto es:

A[i,j] = A[j,i]

C[i,j] = C[j,i]

117

Ejemplo Introductorio

Seymour Miles es el gerente de distribucin de Zigwell. Zigwell

distribuye sus motores oruga en cinco estados del medio oeste. Por lo

regular, Seymour Miles tiene 10 aparatos E-9 in situ en lo que

designaremos como local 1. Estos tractores deben ser enviados a los

dos locales de construccin ms importantes designados como 3 y 4.

Se necesitan tres E-9 en el local 3 y siete en el local 4. Debido a

itinerarios arreglados con anterioridad, relativos a la disponibilidad de

conductores, los tractores solo pueden ser distribuidos de acuerdo con

las rutas alternativas que se muestran en el grafo de la figura.

La figura tiene un nmero +10 en el nodo 1, esto significa que hay 10

aparatos E-9 disponibles (oferta). Los indicadores -3 y -7 asociados a

los locales 3 y 4, respectivamente, denotan los requerimientos

(demandas) de stos.

118

1 2 4

5

3

c12

c34

c24

c25 c54

u43

c53

c23

+10

-3

-7

Rutas alternativas para el destino 3

1-2-3, 1-2-4-3, 1-2-5-4-3, 1-2-5-3

u12

u23 u34

c43

u53

c54 u25

u24

119

Los costos cij son unitarios. Por ejemplo el costo de

recorrer el arco (5,3) es c53 por cada tractor.

Debido a los acuerdos sostenidos con los conductores,

Zigwell debe cambiarlos en cada local que se encuentre

sobre la ruta. Las limitaciones en la disponibilidad de

conductores ocasionan que haya una cota superior en el

nmero de tractores que pueden recorrer cualquier arco

dado.

Por ejemplo: u53 es la cota superior o capacidad en el arco

(5,3).

El problema de Sygmour consiste en encontrar un plan de

embarque que satisfaga la demanda y las restricciones de

capacidad a costo mnimo.

120

El problema en particular se conoce como modelo

de transbordo con capacidades.

Expresar el problema como un PL

a) Variables de decisin

xij = nmero total de E-9 que se enviarn a travs

del arco (i,j).

= flujo del nodo i al nodo j

121

b) Funcin Objetivo

MIN Z =C12X12+C23X23+C24X24+C25X25+C34X34+C43X43+C53X53+C54X54

la red (i,j) de artodos los cx ijij cos ,0

c) Restricciones

s a

+ X12 = 10

- X12+X23+X24+X25 = 0

-X23 -X43 -X53 +X34 = -3

-X24 +X43 -X34 -X54 = -7

-X25 +X53 +X54 = 0

Balance

de

flujo

122

Matriz Incidencia nodo-arco

a r c o

Nodo (1,2) (2,3) (2,4) (2,5) (4,3) (5,3) (3,4) (5,4) LD

1 +1 0 0 0 0 0 0 0 10

2 -1 +1 +1 +1 0 0 0 0 0

3 0 -1 0 0 -1 -1 +1 0 -3

4 0 0 -1 0 +1 0 -1 -1 -7

5 0 0 0 -1 0 +1 0 +1 0

123

Formulacin General del Modelo de Transbordo con Capacidades

Xij denotan el flujo del nodo i al nodo j a lo largo del arco que

conecta esos nodos.

Lj representa la oferta en el nodo j

ijij ijxc

s.a.

minimice

njLxx jk kjk jk ,....,2,1,

la red (i,j) de artodos los cx ijij cos ,0

124

Resolver para las siguientes capacidades y costos Capacidad

de\a Sitio 1 Sitio 2 Sitio 3 Sitio 4 Sitio 5

Sitio 1 10

Sitio 2 4 3 3

Sitio 3 2

Sitio 4 4

Sitio 5 3 5

Costo Unitario

de\a Sitio 1 Sitio 2 Sitio 3 Sitio 4 Sitio 5

Sitio 1 $100

Sitio 2 $45 $50 $20

Sitio 3 $60

Sitio 4 $85

Sitio 5 $10 $55

Ver transbordo con capacidades

125


Se pueden dar dos casos para representar la red:

Como grafo no dirigido

Como grafo dirigido

Situaciones:

a

b

Cualquiera que sea el caso corresponde

a grafos ponderados (con peso)

126


Considernse todos los nodos que estn directamente

conectados con el origen. Etiquetarlos con la distancia al

origen y su nodo predecesor. Etiquetas temporales,

[distancia, nodo].

De entre todos los nodos con etiquetas temporales,

escoger el que tenga la distancia menor y se marca como

permanente. Si todos estn con etiquetas permanentes se

va al paso cuatro.

a) Algoritmo: Grafo no dirigido

1

2

127

2.4.2 Modelo de la Ruta ms corta (GND)

Todo nodo que no tenga etiqueta permanente, tendr etiqueta

temporal o estar sin etiqueta. Sea L el ltimo nodo con

etiqueta permanente. Considernse todas las etiquetas de los

vecinos de L (directamente conectados a L mediante un

arco). Para cada uno de estos nodos calclese la suma de su

distancia a L. Si el nodo en cuestin no est etiquetado,

asgnese una etiqueta temporal que conste de esta distancia y

de L como predecesor. Si el nodo en cuestin ya tiene

etiqueta temporal, cmbiese slo si la distancia recin

calculada es menor que la componente de distancia de la

etiqueta actual. En este caso, la etiqueta contendr esta

distancia y a L como predecesor. Regresar al paso 2

3

Algoritmo:

128


Las etiquetas permanentes indican la distancia ms corta entre

el nodo origen a cada nodo de la red. Tambin indican el

nodo predecesor en la ruta ms corta hacia cada nodo. Para

encontrar el camino ms corto de un nodo dado, comincese

en l y retroceda al nodo anterior. Continuar con el recorrido

hasta llegar al origen.

Algoritmo:

4

129


Ejemplo: Para el siguiente grafo encontrar la distancia ms corta

desde el nodo H al resto de los nodos.

H

1 2

3

4

5

6

7

8

4

1

1

1

1

2

2 7

6

3

3 3

130


Solucin:

H

1 2

3

4

5

6

7

8

4

1

1

1

1

2

2 7

6

3

3 3

(8,H)

(4,H)

(5,1)

(6,3) (8,2)

(6,3)

(9,4)

(9,7)

1:Ver ejemplo 1 Ruta mas corta 2: Hacer problema 19 gua 2 (Ejemplo 2 Ruta mas corta

131

A

7

1

3

B

C

D

E

F

G

1

4

2

10 8

10

5

7 4

3

Para su prctica y ejercitacin neuronal

132

2.4.2 Modelo de la Ruta ms corta (GD)

Es una tcnica exhaustiva, esto es, prueba todas las alternativas

posibles.

Opera a partir de un conjunto S de vrtices cuya distancia ms

corta desde el origen ya es conocida. Inicialmente S contiene slo

el nodo de origen. En cada paso se agrega algn vrtice restante v

a S, cuya distancia desde el origen es la ms corta posible.

Para cada paso del algoritmo, se utiliza una matriz D para registrar

la longitud del camino ms corto a cada vrtice.

b) Algoritmo de Dijkstra

133

2.4.2 Modelo de la Ruta ms corta (GD) Algoritmo de Dijkstra INICIO

0) V = {1, 2, 3, 4, ..., n}

1) S = {1} // nodo 1 se supone que es el origen

2) Para i=2 Hasta n Hacer

3) Di = C1i

4) Para i=1 Hasta n-1 Hacer

5) Elegir un vrtice w en V-S tal que Dw sea un mnimo

6) agregar w a S

7) Para cada vrtice v en V-S Hacer

SI ((Dw+Cwv)

134

2.4.2 Modelo de la Ruta ms corta (GD) Algoritmo de Dijkstra

Ejemplo: Aplicar el algoritmo al siguiente grafo dirigido

10 100

60

50

30

10

2

1

3 4

5

20

135


Inicial

0) V = {1, 2, 3, 4, 5}

1) S = {1}

2)

3) D2 = 10, D3 = inf, D4=30, D5 = 100

4) Iterar 4 veces

5) Seleccionar nodo con distancia ms corta de V-S,

En el ejemplo es el nodo 2

Iteracin S w D2 D3 D4 D5

Inicial {1} -- 10 inf 30 100

136


6) Agregar el nodo 2 a S : S = {1,2}

7) Iterar |V-S|, (V-S = {3,4,5})

D3=mnimo(D3,D2+C23) =mnimo(inf,10+50) = 60

D4=mnimo(D4,D2+C24) =mnimo(30,10+inf) = 30

D5=mnimo(D5,D2+C25) =mnimo(100,10+inf) = 100


Inicial {1} -- 10 inf 30 100

1 {1,2} 2 10 60 30 100

137

2.4.2 Modelo de la Ruta ms corta (GD) Algoritmo de Dijkstra 2a Iteracin

V-S = {3,4,5}

5) w = 4

6) S = {1,2,4}

7) Iterar |V-S| V-S = {3,5}

D3=mnimo(D3,D4+C43) =mnimo(60,30+20) = 50

D5=mnimo(D5,D4+C45) =mnimo(100,30+60) = 90


Inicial {1} -- 10 inf 30 100

1 {1,2} 2 10 60 30 100

2 {1,2,4} 4 10 50 30 90

138


V-S = {3,5}

5) w = 3

6) S = {1,2,4,3}

7) Iterar |V-S| (V-S = {5})

D5=mnimo(D5,D3+C35) =mnimo(90,50+10) = 60


Inicial {1} -- 10 inf 30 100

1 {1,2} 2 10 60 30 100

2 {1,2,4} 4 10 50 30 90

3 {1,2,4,3} 3 10 50 30 60

139


V-S = {5}

5) w = 5

6) S = {1,2,4,3,5}

7) Iterar |V-S| (V-S = {})


Inicial {1} -- 10 inf 30 100

1 {1,2} 2 10 60 30 100

2 {1,2,4} 4 10 50 30 90

3 {1,2,4,3} 3 10 50 30 60

4 {1,2,4,3,5} 5 10 50 30 60

Tabla Final

140

Cul es el camino?

Para conocer el camino hay que incluir otra matriz P de

vrtices, tal que Pv contenga el vrtice inmediato anterior a v

en el camino ms corto.

Se asigna a Pv valor inicial 1 para todo v 1

La matriz P se actualiza despus de la lnea 8.

Si Dw + Cwv < Dv en la lnea 8, despus se hace Pv = w

Al trmino de la corrida del algoritmo, el camino a cada vrtice

puede encontrarse regresando por los vrtices predecesores de

la matriz P

141

Cul es el camino?

Para el ejemplo, la matriz P debe tener los valores

P2 =1, P3 = 4, P4 = 1, P5 = 3

Para encontrar el camino ms corto del vrtice 1 al 5, se siguen

los predecesores en orden inverso.

3 es el predecesor de 5



142

Problema de los caminos ms cortos entre

todos los pares de nodos

Para visualizar el problema se emplea un grafo dirigido G =

(V,A) en el que cada arco v w tiene un costo no negativo

Cv,w. El problema consiste en encontrar el camino de longitud

ms corta (menor costo) entre v y w para cada par ordenado de

vrtices (v,w).

Algoritmo de Floyd

Se utiliza una matriz A, donde Aij = Cij para toda i j, si no

existe camino directo entre i y j se supone que Cij = inf. Cada

elemento de la diagonal se hace cero.

143

Problema de los caminos ms cortos entre todos los pares de nodos

Despus se hacen n iteraciones en la matriz A.

Al final de la k-sima iteracin Aij tendr por valor la longitud

ms pequea de cualquier camino que vaya desde el vrtice i

hasta el vrtice j y que no pase por un vrtice mayor que k.

Esto es, i y j, los vrtice extremos del camino, pueden ser

cualquier vrtice, pero todo vrtice intermedio debe ser menor

o igual a k.

En la k-sima iteracin se aplica la siguiente frmula para

calcular A k-1Aij

kAij = min

k-1Aik + k-1Akj

144


Para calcular Aij, se compara k-1Aij, el costo de ir de i a j sin

pasar por k o cualquier otro nodo con numeracin mayor, con

k-1Aik + k-1Akj, el costo de ir primero de i a k y despus de k a j,

sin pasar a travs de un vrtice mayor que k. Si el paso por el

vrtice k produce un camino ms econmico que el de k-1Aij, se

elige ese costo para kAij.

k-1Aij

i

k

j

145


Algoritmo de Floyd // Se supone que se cuenta con la matriz de costo C

0) INICIO

1) Desde i = 1 Hasta N

2) Desde j = 1 Hasta N

3) Aij Cij

4) Desde i = 1 Has ta N

5) Aii = 0

6) Desde k = 1 Hasta N



9) SI (Aik + Akj < Aij)

10) Aij = Aik + Akj

11) FIN

146


Recuperacin de caminos para el Algoritmo de Floyd

Cuando es de inters conocer el camino ms corto

entre dos vrtices, hay que consignarlo en una matriz

P, donde Pij tiene el vrtice k que permiti a Floyd

encontrar el valor menor de Aij. Si Pij es cero, el

camino de i a j es directo.

147


Algoritmo de Floyd Modificado

0) INICIO



3) Aij Cij

3) Pij 0

4) Desde i = 1 Has ta N

5) Aii = 0

6) Desde k = 1 Hasta N



9) SI (Aik + Akj < Aij)

10) Aij Aik + Akj

10) Pij k

11) FIN

148


Ejemplo: Aplique Floyd al grafo ponderado mostrado en la

figura

1 2 3

2

8

3

2

5

149


Solucin:

Tabla Inicial

Nodos 1 2 3

1 0 8 5

2 3 0 inf

3 inf 2 0

0Aij

150


Solucin:

Despus de la primera iteracin

1Aij

Nodos 1 2 3

1 0 8 5

2 3 0 8

3 inf 2 0

151


Solucin:

Despus de la segunda iteracin

2Aij

Nodos 1 2 3

1 0 8 5

2 3 0 8

3 5 2 0

152


Solucin:

Despus de la tercera iteracin

3Aij

Nodos 1 2 3

1 0 7 5

2 3 0 8

3 5 2 0

153

2.4.3 Modelo de rbol extensin mnima

Un rbol es un grafo que tiene sus n nodos (vrtices)

conectados (conexo) con n-1 arcos (aristas), no

existiendo ciclos (caminos cerrados)

Definicin 1

Definicin 2 Un rbol de expansin de costo mnimo es aquel en que

todos los enlaces tienen longitudes (costos) mnimas

154

Algoritmo para el problema del rbol de expansin mnima.

Mtodo Grfico

Se selecciona un nodo cualquiera y se conecta al

nodo ms cercano a ste.

Se identifica el nodo no conectado ms cercano a

un nodo conectado y se conectan estos dos nodos

Empates se deciden en forma arbitraria. Los

empates indican que existen soluciones

alternativas para la construccin.

1

2

Nota:

155

H

1 2

3

4

5

6

7

8

4

1

1

1

1

2

2 7

6

3

3 3

Ejemplo: Encontrar el AEM para el siguiente grafo

156

H

1 2

3

4

5

6

7

1

1

1

1

Solucin :

2

2

4

157

Algoritmo tabular

Paso Accin

0 Se construye la tabla de costos de enlaces

1 Se comienza arbitrariamente con cualquier nodo. Se designa a

este nodo como conectado y se pone una marca al lado de la

fila correspondiente al nodo. Se tacha el ndice de la columna

que corresponde a l.

2 Considerando todas las filas marcadas, buscar el mnimo en las

columnas cuyo ndice an no haya sido tachado encerrndolo

en un crculo. Designndose de esta manera el nuevo nodo

conectado. Se tacha el ndice de la columna y pone una marca

en la fila correspondiente a este nodo. Se repite este paso hasta

que todos los nodos estn conectados.

3 Los nodos encerrados en crculo identifican el rbol.

158

Aplicacin Algoritmo tabular

Nodo H 1 2 3 4 5 6 7

H 4 7 8

1 4 6 1

2 6 1 2

3 1 1 1

4 7 1 3 3 2

5 2 3 3

6 3 3 1

7 8 2 1

Tabla inicial

159


Inicio: Nodo H

Nodo H 1 2 3 4 5 6 7

* H 4 7 8

* 1 4 6 1

2 6 1 2

3 1 1 1

4 7 1 3 3 2

5 2 3 3

6 3 3 1

7 8 2 1

a)

b)

160


Nodo 1

Nodo H 1 2 3 4 5 6 7

* H 4 7 8

* 1 4 6 1

2 6 1 2

* 3 1 1 1

4 7 1 3 3 2

5 2 3 3

6 3 3 1

7 8 2 1

a)

b)

c)

161


Nodo H 1 2 3 4 5 6 7

* H 4 7 8

* 1 4 6 1

* 2 6 1 2

* 3 1 1 1

* 4 7 1 3 3 2

* 5 2 3 3

* 6 3 3 1

* 7 8 2 1

Tabla final

a)

b)

c)

162

H

1 2

3

4

5

6

7

1

1

1

1

Arbol de expansin mnima :

2

2

4

163

2.4.4 Problema del Flujo Mximo

En este problema hay un solo nodo fuente (nodo de

entrada) y un solo nodo destino (nodo de salida), y el

resto son nodos de transbordo. El problema consiste en

encontrar la mxima cantidad de flujo total (petrleo,

gas, efectivo, mensajes, trnsito, etc.) en una unidad de

tiempo.

La cantidad de flujo por unidad de tiempo en cada arco

est limitada por las restricciones de capacidad.

Este problema se puede representar como una red

dirigida y conexa.

Descripcin

164

Para cada nodo interno debe cumplirse que:

flujo que sale del nodo = flujo que entra al nodo

En trminos formales, siendo 1 la fuente y n el destino el problema consiste en:

MAX f

f si i = 1

sujeto a si i = n

0 en otro caso

0 xij uij, para todos (i,j) de la red

xij : flujo por unidad de tiempo por el arco (i,j)

uij : capacidad del arco (i,j)

f : flujo total a travs de la red

Descripcin

fxxj

ji

j

ij

165

Considrese la i-sima restriccin, para algn

valor fijo de i, La suma se considera sobre

toda j para la cual el arco (i,j) con i fijo,

pertenezca a la red. Entonces, ser el flujo

total que sale del nodo i. En forma semejante, la

suma se considera sobre toda j para la cual

exista el arco (j,i) en la red, (i fijo). De modo que

es el flujo que entra al nodo i

Descripcin

j

ijx

j

jix

j

ijx

166

Antes de hacer la presentacin formal del

algoritmo, revisemos el siguiente ejemplo.

Algoritmo

6

6

6

2

4

4

3

2

1

6

1

2

3

4

5

167

Grafo inicial: Inicializacin delos flujos en cada nodo Algoritmo

Consideremos un camino desde el nodo 1 al nodo 6

Ejemplo: 1-2-5-6

4

0

0

0

0

0

0

0

0

6

4

1

6

2

3

2

6

0

2

3

4

5

6 1

168

Se dice que la cantidad de flujo a lo largo de dicho

recorrido es factible si:

No excede la capacidad de ningn arco del camino

Con excepcin de los nodos 1 y 6, el flujo en cada nodo

debe satisfacer la condicin de conservacin

1

2

La cantidad mxima que puede fluir desde la fuente a lo

largo de un camino es igual a la menor de las

capacidades de los arcos de dicho camino

Al asignar un flujo a un arco nos atendremos a las reglas:

1

2

Se reduce la capacidad en la direccin del flujo (cantidad de flujo)

Se aumenta la capacidad en sentido opuesto (cantidad de flujo)

169

Ejemplo: Considerar el arco 1-2

Asignar dos unidades a este arco:

Aplicando las reglas 1 y 2 se tiene

Se gener una capacidad ficticia en la direccin 2-1

Enviar una unidad de 2 a 1

1 2 (2 )

2 2

1 2 4 0

1 2 (1 )

1 3

170

Algoritmo

Inicializar cada nodo del grafo con capacidades uij en

la direccin del flujo y cero en la direccin opuesta.

Encontrar cualquier camino de la fuente a destino que

tenga capacidad de flujo positiva, si no los hay, se

habr encontrado la solucin ptima.

Sea cmin la capacidad mnima de flujo entre los arcos

seleccionados en el paso 1, se aumenta el flujo

existente a travs de la red al enviar un flujo adicional

cmin para todos los arcos del camino.

Para todos los arcos del camino, disminyanse las

capacidades en la direccin del flujo y aumntese las

capacidades en la direccin opuesta en cmin. Volver al

paso 1

Inicial

1

2

3

171

Aplicar el algoritmo al grafo del ejemplo:

4

0

0

0

0

0

0

0

0

6

4

1

6

2

3

2

6

0

2

3

4

5

6 1

Paso Inicial

172

Iteracin 1:

4

0

0

0

0

0

0

0

0

6

4

1

6

2

3

2

6

0

2

3

4

5

6 1

Elegir arbitrariamente el camino 1-3-5-6

cmin = MIN(6,4,2)=2; actualizando la red se tiene

4

2

2 2

0

2

2 2

173

Iteracin 2:

4 0

0

0

0

0

0

0

0

6

4

1

2

2

3

2

2

0

2

3

4

5

6 1

4

2 0

2

2 6

Elegir arbitrariamente el camino 1-2-4-6

cmin = MIN(4,6,6)=4; actualizando la red se tiene

4 0

6 4

6 4

2

6

2 2

174

Iteracin 3:

4 0

0

0

0

0

2

0

0

6

4

1

0

2

1

2

0

0

2

3

4

5

6 1

2

4

0

2

2

8

Elegir arbitrariamente el camino 1-3-2-4-6

cmin = MIN(4,3,2,2)=2; actualizando la red se tiene

4 0

6

4

6 6

2

8

2 2

4

2

3

0

2

6

2

4 6

6

175

Clculo de la cantidad de flujo en cada arco

Se determina comparando la capacidad inicial de cada arco

con la capacidad inicial. Para cada arco la regla es:

Si la capacidad final es menor que la capacidad inicial,

calcular la diferencia. Esta es la cantidad del flujo a travs

del arco.

Ejemplo: Arco 3-5

Inicial

Final 2 2 3 5

0 4 3 5

Final < inicial entonces el flujo es 4-2=2

176

Aplicando la regla anterior a todos los arcos se tiene el

siguiente grafo:

6

6

6

2

4

2

8

2

8

4

1

2

3

4

5

177

Unidad 3

Administracin de Proyectos

PERT y CPM

178

3 Administracin de Proyectos (PERT y CPM)

1. Cundo sera lo ms pronto que el proyecto pudiera estar

terminado?

2. Para cumplir con este tiempo de conclusin, qu tareas son

crticas, en el sentido de que un retraso en cualquiera de esas

tareas provoca un retraso en la conclusin del proyecto?

3. Es posible acelerar ciertas tareas para terminar todo el proyecto

ms pronto?. Si es as, qu tareas sern stas y cul sera el

costo adicional?

Todo proyecto debe ser comprobado y controlado, dado que ste

tiene involucrado numerosas tareas interrelacionadas.

A travs de algunas tcnicas se puede responder a preguntas como:

179

Tcnica de Evaluacin de Proyectos (PERT,

Program Evaluation and Review Technique): Mtodo

utilizado para administrar proyectos en que los

tiempos requeridos para terminar las tareas

individuales son inciertos (probabilsticos).

Mtodo de la Ruta Crtica (CPM, Critical Path

Method): Mtodo utilizado para administrar

proyectos en que los tiempos requeridos para

terminar las tareas individuales se conocen con

relativa certeza (determinsticos).

180

3.1 Desarrollo de la Red de Proyectos

1. Identifique las tareas individuales que componen el proyecto

2. Obtenga una estimacin del tiempo de conclusin de cada

tarea.

3. Identifique las relaciones entre las tareas. Qu tareas deben

concluirse antes de que otras puedan iniciarse?

4. Dibuje un diagrama de red de proyecto para reflejar la

informacin de los pasos 1 y 3

Para determinar el tiempo de conclusin de un proyecto puede

usar los siguientes pasos:

181

Ejemplo:

Traslado de las oficinas de una ciudad a otra

El directorio ha fijado un plazo mximo de 22

semanas para la mudanza

Actividad DescripcinPrdecesoras

inmediatasTiempo Recursos

A Elegir local de oficinas -

B Crear el plan financiero y de -

CDeterminar requerimientos

de personalB

D Diseo de local A, C

E Construir el interior D

F Elegir personal a mudar C

GContratar nuevos

empleadosF

HMudar registros, personal

clave, etc.F

IHacer arreglos finacieros de

la organizacinB

J Entrenar personal nuevo H, E, G

182

Construccin del diagrama de Red:

1

2

3

4

A

B C

Cmo agregamos la actividad D?. Sus

predecesoras inmediatas son A y C,

adems C es predecesora directa de F

183

Actividades Ficticias (figurada):

Es una actividad artificial que no requiere tiempo y que se

incluye en una red de proyecto para asegurar la relacin de

precedencia correcta entre ciertas tareas.

Generalmente se representan por lneas segmentadas.

Se usan slo para reflejar las relaciones de precedencia

adecuadas

2

4

A

C

184

Volviendo al ejemplo: Agregando el resto de las actividades a la red finalmente se tiene

1

2

3

4

5

6 7

8

A

B C

D

E

F

G

H

I

J

185

Siguiendo con el ejemplo: G y H tienen como predecesora inmediata F, adems ambas son predecesoras de J, agregar actividad ficticia.

1

2

3

4

5

6 7

8

A

B C

D

E

F

G

H

I

J

9

Red Final

Fic

186

Ruta Crtica: Dar cumplimiento al plazo lmite Se requiere de las estimaciones de tiempo de cada actividad (supuestos)

Actividad DescripcinPrdecesoras

inmediatasTiempo Recursos

A Elegir local de oficinas - 3

BCrear el plan financiero y de

organizacin- 5

CDeterminar requerimientos

de personalB 3

D Diseo de local A, C 4

E Construir el interior D 8

F Elegir personal a mudar C 2

GContratar nuevos

empleadosF 4

HMudar registros, personal

clave, etc.F 2

IHacer arreglos finacieros de

la organizacinB 5

J Entrenar personal nuevo H, E, G 3

187

Retomando el ejemplo: Agregando los tiempos a las actividades

1

2

3

4

5

6 7

9

A

B C

D

E

F

G

H

I

J

(3)

(5)

(3)

(4)

(8)

(2)

(4)

(2)

(5)

(3)

8 Fic

188

Clculo de la ruta crtica: Tiempo de trmino del proyecto

Definiciones

Tiempo de inicio ms inmediato: El tiempo

ms cercano en que una tarea posiblemente

pueda iniciarse (TI)

Tiempo de trmino ms breve: El tiempo ms

corto en el que una tarea posiblemente pueda

concluir (TT)

189

Reglas a cumplir: Dado que en el proyecto existen tareas predecesoras es necesario conocer cuando termina

una y cuando empieza la otra:

Regla

1. Para calcular el TI de una tarea se debe conocer los TT de cada

tarea predecesora inmediata

2. El TI ms inmediato de una tarea de la que se conocen los

tiempos de trmino ms breves de todas sus tareas

predecesoras inmediatas es el mximo de todos esos tiempos

de trmino ms breves.

3. Tiempo de trmino ms breve = (tiempo de inicio ms

inmediato) + (tiempo de tarea(t))

190

Pasos para determinar los TI y TT ms inmediatos:

Paso

0

1

Identificar el nodo de inicio de la red del proyecto

Calcule y escriba en cada arco saliente

a) TI ms cercano, esto es, 0

b) El TT ms breve de acuerdo a la regla 3

TT ms breve = (TI ms inmediato) + (t)

= 0 + t

Seleccionar cualquier nodo donde todos los arcos

entrantes han sido etiquetados con sus TI y TT

191

Pasos para determinar los TI y TT ms inmediatos:

Paso

2

Para el nodo seleccionado en el paso 1 calcule y registre

en cada arco saliente

a) El TI ms breve de acuerdo a la regla 2

TI ms breve = MAXIMO(TT de los arcos entrantes)

b) El TT ms breve de acuerdo a la regla 3

TT ms breve = TI ms inmediato + t

192

Clculo de TI y TT:

1

2

3

4

5

6 7

9

D[8,12]

8

Fic

193

Identificacin de las tareas crticas:

Para identificar las tareas crticas hay que realizar un

recorrido hacia atrs hasta el inicio del proyecto,

analizando cada tarea.

1. ltimo Tiempo de trmino: Lo ms tarde que puede

concluirse una tarea, en tanto permita que el proyecto se

complete lo ms pronto posible

2. ltimo tiempo de inicio: Lo ms tarde que pueda

iniciarse una tarea, pero finalizando dentro de su tiempo

de trmino.

3. Tarea sucesora: Una tarea para la que la tarea de inters

es una predecesora

194


Para calcular el ltimo tiempo de trmino (UTT) de una

tarea particular, debe conocer los ltimos tiempos de

inicio (UTI) de cada tarea sucesora inmediata.

Respecto a una tarea de la que se conocen los ltimos

tiempos de inicio de todas sus tareas sucesoras

inmediatas, el ltimo tiempo de trmino (UTT) de esa

tarea es el mnimo de los ltimos tiempos de inicio de

todas las tareas sucesoras inmediatas

UTI = UTT- t

Regla

4

5

6

195

Identificacin de las tareas crticas: Pasos para calcular los ltimos tiempos de inicio y trmino

0

1

2

3

Identificar el final del proyecto. Calcular y escribir en cada arco

entrante:

a) ltimo tiempo de trmino del proyecto

b) ltimo tiempo de inicio (Regla 6): UTI=UTT-t

Seleccione un nodo, cuyos arcos salientes hayan sido etiquetados

todos con sus UTI y UTT

Para el nodo seleccionado (paso 1) calcule y escriba lo siguiente

a) UTT= MIN(UTI arcos salientes), (regla 5)

b) UTI=UTT - t (regla 6)

Repetir pasos 1 y 2 hasta cubrir toda la red del proyecto

196

Identificacin de las tareas crticas: Clculo de UTT y UTI para cada actividad

Iteracin 2

Actividad ficticia UTT = 20

UTI = 20-0 = 20

Actividad I UTT = 23

UTI = 23-5 = 18

Nodo 7 Actividad E UTT = 20

UTI = 20-8 = 12

UTT = 20

UTI = 20-2 = 18

Iteracin 1

Actividad H

Nodo 9 Actividad J UTT = 23

UTI = 23-3 = 20

197

1

2

3

4

5

6 7

9 8

Identificacin de las tareas crticas: Clculo de UTT y UTI para cada actividad . Finalmente se tiene

D[8,12]

[8,12]

[5,8

]

Fic

198


Holgura: Es la cantidad de tiempo que puede demorar una actividad sin afectar la fecha de trmino del proyecto.

El valor de la holgura para cada actividad est dada por:

holgura = TI - UTI = TT - UTT

Ejemplo:

Actividad C: TI = 5, UTI = 5, TT = 8, UTT = 8

Holgura = 5 - 5 = 8 - 8 = 0

Actividad I: TI = 5, UTI = 18, TT = 10, UTT = 23

La actividad C tiene holgura 0, por tanto no puede retrasarse, en cambio la actividad I tiene 13 semanas de holgura que permite retrasar su inicio.

199


Resumen de los tiempos de las actividades del proyecto:

Actividad Tiempo Inicio Trmino Inicio Trmino Holgura

A 3 0 3 5 8 5

B 5 0 5 0 5 0

C 3 5 8 5 8 0

D 4 8 12 8 12 0

E 8 12 20 12 20 0

F 2 8 10 14 16 6

G 4 10 14 16 20 6

H 2 10 12 18 20 8

I 5 5 10 18 23 13

J 3 20 23 20 23 0

Tiempo ms prximo de: Tiempo ms lejano de:

Tiempo de ejecucin del proyecto: 23 semanas

200


Actividad crtica es aquella que tiene holgura cero

Ruta crtica es una secuencia de tareas (actividades) crticas que

conecta el principio del proyecto con el fin

En nuestro ejemplo:

Actividades crticas: B, C, D, E y J

Ruta crtica: Nodos 1-3-2-5-7-9

Actividades B-C-D-E-J

201

Formas de Reducir la duracin del proyecto:

1. Anlisis Estratgico

Aqu el analista se pregunta: Este proyecto tiene que

desarrollarse en la forma progr

iopertivab

Documents

Transcript of iopertivab