Itesm

Optimización y Programación Lineal
Programación Lineal: Flujo Máximo
Departamento de Matemáticas

ITESM

Programación Lineal: Flujo Máximo

TC3001 - p. 1/8

Red de Transporte
Una Red deTransporte 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 ∈ V está en un camino s vt. El peso de cada lado debe ser no negativo y se considera la capacidad del lado. Si e ∈ E, c(e) = 0. / 16 s 13 4 v4 14 v1 10 9 v3 4 12 v2 7 20 t
Red de Transporte Un Flujo Ejemplo El problema MaxFlow LP Max Flow en LINGO ´ Aplicacion 1

Programación Lineal: Flujo Máximo

TC3001 - p. 2/8

Flujo en una Red
Un flujo f en una red de transporte (V, E, c) es una asignación a cada lado de lared e ∈ E de un valor numérico f (e) que satisface: 1. Restricción de capacidad: ∀e ∈ E: 0 ≤ f (e) ≤ c(e) 2. Conservación del flujo: ∀v ∈ V − {s, t}: f (x, v) =
(x,v)∈E (v,y)∈E

Red de Transporte UnFlujo Ejemplo El problema Max Flow LP Max Flow en LINGO ´ Aplicacion 1

f (v, y)

Esto es para cualquier nodo v, diferente de s y de t, el flujo total que llega al nodo v es igual flujo total quesale de v. El valor del flujo f se define como: |f | =
(s,v)∈E

f (s, v)

Esto es, el flujo total que sale de s.

Programación Lineal: Flujo Máximo

TC3001 - p. 3/8

Ejemplo de un flujo en unared
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 dellado. 12/12 v1 v2 11/16 15/20
Red de Transporte Un Flujo Ejemplo El problema Max Flow LP Max Flow en LINGO ´ Aplicacion 1

s

1/4

0/10 4/9

7/7

t

8/13

v4 11/14

v3

4/4

Aquí |f |= 19.

Programación Lineal: Flujo Máximo

TC3001 - p. 4/8

El problema
Dada una red de transporte (V, E, c) encontrar un flujo f con máximo valor |f |.
Red de Transporte Un Flujo Ejemplo El...