Analisis de redes

|
|
|
|
|
|
|
|

Unidad II
Análisis de Redes

Profesor:
RODRIGUEZ VAZQUEZ JUAN MANUEL

Alumna:
| |
Cortes Ayala María Isabel | 08320989 |
| |

A 03de Noviembre del 2010.
Índice

Unidad II Análisis de Redes
2.1 Problema de transporte 3
2.1.1 Método de la esquina noroeste. 3
2.1.2 Procedimiento de optimización. 5
2.2 Problema del camino máscorto 6
2.3 Problema del árbol expandido mínimo 8
2.4 Problema del flujo máximo 11
Algoritmo de Ford-Fulkerson 11
2.5 Ruta critica (PERT-CPM) 13
Bibliografía 16

UNIDAD II ANÁLISIS DE REDES
2.1 Problema de transporte
2.1.1 Método de la esquina noroeste.
    
Este requisito da origen a una ecuación dependiente, lo que significa que el modelo de transporte tiene sólo m + n –1ecuaciones independientes. Por lo tanto, como en el método simplex, una solución factible básica inicial debe incluir m + n – 1 variables básicas.
Normalmente, si el  modelo de transporte se formula como una tabla simplex, sería necesario utilizar variables artificiales para asegurar una solución básica inicial. Sin embargo, cuando se utiliza la tabla de transporte, una solución factible básica inicial sepuede obtener fácil y directamente. Presentamos un procedimiento llamado regla de la esquina noroeste para este fin.

| | Destino | |
| | 1 | 2 | 3 | 4 | Oferta |
Fuente | 1 | | 10 | | 0 | | 20 | | 11 | 15 |
| | X11 | X12 | X13 | X14 | |
| 2 | | 12 | | 7 | | 9 | | 20 | 25 |
| | X21 | X22 | X23 | X24 | |
| 3 | | 0 | | 14 | | 16 | | 18 | 5 |
| | X31 |X32 | X33 | X34 | |
Demanda | 5 | 15 | 15 | 10 |   |
    

El método de la esquina noroeste comienza con la asignación de la máxima cantidad admisible a través de la oferta y la demanda de la variable x11 (la de la esquina noroeste de la tabla). Después se tacha la columna (renglón) satisfecha, lo que indica que las variables restantes de la columna (renglón) tachada son iguales a cero. Si sesatisfacen una columna y un renglón al mismo tiempo, sólo una (una u otro) puede ser tachada. (Esta condición garantiza la ubicación automática de variables básicas cero, si las hay). Después de ajustar las cantidades de oferta y demanda de todos los renglones y columnas no tachados, la cantidad factible máxima se asigna al primer elemento no tachado de la nueva columna (renglón). El proceso secompleta cuando se deja sin tachar exactamente un renglón o una columna.

El procedimiento que se acaba de describir se aplica ahora en el ejemplo:

1.    x11 = 5, se tacha la columna 1. Por lo tanto, no se puede hacer otra asignación en la columna 1. La cantidad que falta en el renglón 1 son 10 unidades.
2.    x12 = 10, se tacha el renglón 1 y faltan 5 unidades en la columna 2.
3.    x22 =5, se tacha la columna 2 y faltan 20 unidades en el renglón 2.
4.    x23 = 15, se tacha la columna 3 y faltan 5 unidades en el renglón 2.
5.    x24 = 5, se tacha el renglón 2 y faltan 5 unidades en la columna 4.
6.   x34 = 5, se tacha el renglón 3 o la columna 4. Como sólo un renglón o una columna se mantienen sin tachar, el proceso llega a su fin.

La solución básica inicial resultante sepresenta a continuación.
Las variables básicas son x11 = 5, x22 =10, x23 =15, x24 =5 y x34 = 5. Las variables restantes son no básicas en el nivel cero. El costo de transporte asociado es:

5 x 10 +10 x 0 + 5 x 7+ 15 x 9 + 5 x 20 +5 x 18 = $410.

| 1 | 2 | 3 | 4 | |
1 | 5 | 10 | | | 15 |
2 | | 5 | 15 | 5 | 25 |
3 | | | | 5 | 5 |
| 5 | 15 | 15 | 10 | |

Cuando se satisfacenal mismo tiempo una columna y un renglón, la siguiente variable que se agregará a la solución básica estará necesariamente en el nivel cero. La siguiente tabla ilustra este aspecto.  La columna 2 y el renglón 2 se satisfacen simultáneamente.

| 1 | 2 | 3 | 4 | | |
1 | 5 | 5 | | | 10 | 5 |
2 | | 5 | 0 | | 5 | 0 |
3 | | | 8 | 7 | 15 | |
| 5 | 10 | 8 | 7 | 15 | |
| | 5 |...