Teorema Flujo Max - Corte Min

REDES DE OPTIMIZACION Y PROGRAMACION

LINEALINVESTIGACION DE OPERACIONES

REDES DE OPTIMIZACION

• LOS PROBLEMAS DE REDES SURGEN EN UNA GRAN VARIEDAD DE SITUACIONES.

• TRANSPORTE• COMUNICACIÓN• ELECTRICAS

• PREDOMINAN EN LA VIDA DIARIA

• LA REPRESENTACION DE REDES SE UTILIZA AMPLIAMENTE EN AREAS COMO PRODUCCION, FISTRIBUCION, PLANEACION, ETC.

• UNA REPRESENTACION DE REDES PROPORCIONA UN PANORAMA GENERAL

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.

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).

ij

CONCEPTOS BÁSICOS

• GRÁFICA NO DIRIGIDA

• GRÁFICA DIRIGIDA

14

3

2

6

5

7

• NODOS

• ARCOS NO DIRIGIDOS

1

14

3

2

6

5

7

• NODOS

• ARCOS DIRIGIDOS

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.

TEOREMA DE FLUJO MAXIMO Y CORTE

MINIMOINVESTIGACION DE OPERACIONES

FLUJO MAXIMO

• EN TÉRMINOS GENERALES, EL PROBLEMA DE FLUJO MÁXIMO SE PUEDE DESCRIBIR DE LA SIGUIENTE MANERA:

1) TODO FLUJO A TRAVÉS DE UNA RED CONEXA DIRIGIDA SE ORIGINA EN UN NODO, LLAMADO FUENTE, Y TERMINA EN OTRO NODO LLAMADO DESTINO.

2) LOS NODOS RESTANTES SON LOS NODOS DE TRASBORDO 3) SE PERMITE EL FLUJO A TRAVÉS DE UN ARCO SOLO EN LA DIRECCIÓN INDICADA

POR LA FLECHA, DONDE LA CANTIDAD MÁXIMA DE FLUJO ESTÁ DADA POR LA CAPACIDAD DEL ARCO. EN LA FUENTE, TODOS LOS ARCOS SEÑALAN HACIA AFUERA. EN EL DESTINO, TODOS SEÑALAN HACIA EL NODO.

4) EL OBJETIVO ES MAXIMIZAR LA CANTIDAD TOTAL DE FLUJO DE LA FUENTE AL DESTINO. ESTA CANTIDAD SE MIDE EN CUALQUIERA DE LAS DOS MANERAS EQUIVALENTES, ESTO ES, LA CANTIDAD QUE SALE DE LA FUENTE O LA CANTIDAD QUE ENTRA AL DESTINO.

APLICACIONES FLUJO MAXIMO

• 1. MAXIMIZAR EL FLUJO A TRAVÉS DE LA RED DE DISTRIBUCIÓN DE UNA COMPAÑÍA DESDE SUS FABRICAS HASTA SUS CLIENTES.

• 2. MAXIMIZAR EL FLUJO A TRAVÉS DE LA RED DE SUMINISTROS DE UNA COMPAÑÍA DE PROVEEDORES A LAS FABRICAS.

• 3. MAXIMIZAR EL FLUJO DE PETRÓLEO POR UN SISTEMA DE TUBERÍAS.

• 4. MAXIMIZAR EL FLUJO DE AGUA A TRAVÉS DE UN SISTEMA DE ACUEDUCTOS

• 5. MAXIMIZAR EL FLUJO DE VEHÍCULOS POR UNA RED DE TRANSPORTE.

CORTE

• CORTE (S, T) CORRESPONDIENTE A UNA RED DE FLUJO G = (V, E) ES UNA PARTICIÓN DE V EN S Y T = V – S TAL QUE S ∈S Y T ∈T ES DECIR, UN CORTE PRECISA UNA SERIE DE ARCOS CUYA DESTRUCCIÓN DE LA RED CAUSA UNA INTERRUPCIÓN COMPLETA DEL FLUJO ENTRE EL ORIGEN Y EL DESTINO. POR LO TANTO UN CORTE MÍNIMO ESTA DEFINIDO COMO SIGUE:

CORTE MINIMO

• ES UN CORTE CUYO PORTE ES MÍNIMO, ES DECIR, EL CORTE MÍNIMO EN UNA RED CORRESPONDE A LA CAPACIDAD MÍNIMA SOBRE LOS DEMÁS CORTES DE LA RED O SI DICHA CAPACIDAD DEL CORTE POSEE UN VALOR MENOR, ES IMPORTANTE ACOTAR QUE ESTE CORTE NOS MUESTRA LA MÍNIMA CAPACIDAD DEL CORTE EFECTUADO EN UN GRAFO.

TEOREMA DE FLUJO MAXIMO Y CORTE MINIMO

• SEA F UN FLUJO EN G Y SEA (P, P) UN CORTE EN G SI LA IGUALDAD SE CUMPLE ENTONCES EL FLUJO ES MÁXIMO Y EL CORTE ES MÍNIMO SI Y SOLO SI:

1) FI J = CI J PARA I ЄP, J Є P2) FIJ =0 PARA I Є P, J Є P

• EL VALOR DEL FLUJO MAXIMAL DE UNA RED ES IGUAL A LA CAPACIDAD DEL CORTE MINIMAL QUE SE PUEDE APLICAR A LA RED. • SE PUEDE OBTENER, POR TANTO EL CORTE MINIMAL DE UNA RED,

CONOCIENDO EL FLUJO MAXIMAL DE LA RED.

CONCLUSION

• DESPUÉS DE HABER TRATADO LOS TEMAS CONCLUIMOS CON QUE EL TEOREMA DE CORTE MÍNIMO SE EXPRESA DE LA SIGUIENTE MANERA: • SEAN DADOS UNA RED CAPACITADA G = (N, A), DOS NODOS:

ORIGEN (S) Y DESTINO (T), ENTONCES EL VALOR DEL FLUJO MÁXIMO DE S A T ES IGUAL A LA CAPACIDAD DEL CORTE MÍNIMO.• LOS CONCEPTOS AQUÍ TRATADOS ACERCA DE LOS TEOREMAS

VARÍAN UN POCO EN CUANTO A LOS DATOS QUE CONTIENEN YA QUE FUERON SACADOS DE DIFERENTES REFERENCIAS.