Flujo maximo

INSTITUTO TECNOLÓGICO Y DE ESTUDIOS SUPERIORES DE MONTERREY:

Campus León INSTITUTO TECNOLÓGICO Y DE ESTUDIOS SUPERIORES DE MONTERREY

Optimización y programación lineal:

Miguel Ubaldo Ortiz Candelas Optimización y programación lineal

Slide 3:

FLUJO MÁXIMO

Introducción:

Introducción Una Red de Transporte es un grafo dirigido con peso ( V,E,c ) donde hay dos vértices distinguidos: uno llamado fuente s y otro llamado sumidero t. Se asume que todo vértice del grafo V está en un camino . El peso de cada lado debe ser no negativo y se considera la capacidad del lado .

Introducción:

Introducción Una Red de Transporte es un grafo dirigido con peso ( V,E,c ) donde hay dos vértices distinguidos: uno llamado fuente s y otro llamado sumidero t. Se asume que todo vértice del grafo V está en un camino . El peso de cada lado debe ser no negativo y se considera la capacidad del lado .

Introducción:

Introducción Ya que se ha modelado una situación específica con una red de transporte, debemos analizar su alcance por medio del flujo máximo que puede soportar . Nos interesa saber cuál es la cantidad máxima que es posible suministrar con el sistema que se evalúa. Para esto veremos un algoritmo que nos ayudará a determinar este valor tan importante.

Ejemplo 1:

Ejemplo 1

Ejemplo 1:

Ejemplo 1

Ejemplo 1:

Ejemplo 1

Ejemplo 1:

Ejemplo 1 Cada lado tiene dos valores asignados, una alternativa es una fracción simulada: el número en el numerador representa el flujo en el lado; el valor en el denominador representa la capacidad del lado.

Ejemplo 1:

Ejemplo 1

Ejemplo 1:

Ejemplo 1 Dada una red de transporte ( V,E,c ) encontrar un flujo f con máximo valor. La formulación como LP es directa: Para cada lado se tiene una variable de decisión x e que representa el flujo en el lado e con restricciones Objetivo :

Ejemplo 1:

Ejemplo 1 Sujeto a para cada vértice v diferente de s y de t:

Ejemplo 1:

Ejemplo 1

Ejemplo 1:

Ejemplo 1 Max z = x 61 + x 64 Sujeto a x 61 + x 41 = x 12 + x 14 x 64 + x 14 + x 24 = x 41 + x 43 x 12 + x 32 = x 24 + x 25 x 43 = x 3 2 + x 35

Código LINGO:

Código LINGO MODEL : SETS : NODES/1..6/; ARCS(NODES,NODES)/ 6,2 6,4 1,2 1,4 2,4 2,5 3,2 3,5 4,1 4,3 5,6/: C,X; ENDSETS

Código LINGO:

Código LINGO DATA : C=16,13,12,10,9,20,7,4,4,14,1000; ENDDATA MAX =X(5,6); @FOR (ARCS(I,J): X(I,J) <= C(I,J) ); @FOR (NODES(I): @SUM (ARCS(J,I):X(J,I)) = @SUM (ARCS(I,J):X(I,J)) ); END

Código LINGO:

Código LINGO

Gracias:

Gracias Instituto Tecnológico y de Estudios Superiores de Monterrey, Campus León Optimización y Programación Lineal Mayo de 2011