Flujo de costo minimo

Flujo con costo m´ ınimo
Pablo De Caria, Laura P. Schaposnik M.
Facultad de Ciencias Exactas, Universidad Nacional de La Plata

3 de julio de 2007
Resumen En este trabajo estudiaremos los problemas de flujo en redes con costo m´ ınimo y veremos c´mo se peude aplicar el m´todo simplex para resolverlos. Comenzaremos con una breve o e introducci´n acerca de flujo en redes y luego analizaremosdistintos aspectos del problema o de flujo con costo m´ ınimo hasta estar en condiciones de analizar c´mo el m´todo simplex o e se puede adecuar a estos problemas particulares.

´ Indice
1. Introducci´n o 1.1. Grafos . . . . . . . . . . . . . . . . . . . 1.1.1. Conceptos b´sicos . . . . . . . . . a 1.1.2. Algunas propiedades . . . . . . . 1.2. M´todo simplex . . . . . . . . . . . . . . e 1.2.1.Algoritmo . . . . . . . . . . . . . 1.2.2. Algoritmo para variables acotadas 1.2.3. M´todo simplex dual . . . . . . . e 2. Problema de flujo con costo m´ ınimo 2.1. Propiedades de la matriz de incidencia A 2.1.1. Rango de A . . . . . . . . . . . . 2.2. Variables artificiales . . . . . . . . . . . . 2.3. Caracterizaci´n de una matriz b´sica . . o a 2.3.1. Vectores no b´sicos . . . . . . . . a . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 2 4 8 8 9 11 14 15 15 16 16 18 19 19 19 21 22 22

3. M´todo simplex para problemasde costo m´ e ınimo 3.1. Variables y valores del sistema . . . . . . . . . . . . 3.1.1. Variables b´sicas . . . . . . . . . . . . . . . a 3.1.2. Valores de zij − cij . . . . . . . . . . . . . . 3.1.3. Pivoteo y columna que sale . . . . . . . . . 3.2. Soluci´n b´sica factible inicial . . . . . . . . . . . . o a 1

3.3. Flujos acotados . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1.Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . 3.4. Algoritmo para guardar la informaci´n en el m´todo simplex o e 3.4.1. Procedimiento . . . . . . . . . . . . . . . . . . . . . . 3.4.2. Breve comentario sobre el algoritmo . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . .. . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

24 24 25 26 26 27

1.

Introducci´n o

Estudiaremos primero algunos conceptos b´sicos utilizados en la teor´ de grafos que nos a ıa ser´n de gran utilidad a lo largo del trabajo. a

1.1.

Grafos

Intuitivamente, un grafo es un conjunto de puntos junto con una familia de flechas que unenalgunos de ellos entre s´ Estos puntos son llamados v´rtices (nodos) y las flechas arcos. ı. e Estudiemos algunas ideas acerca de grafos. 1.1.1. Conceptos b´sicos a

Una red es un conjunto de puntos N={1,...,m} (llamados nodos) a los cuales se les asocia una serie de arcos dirigidos que los conectan de a pares. Por ejemplo, dados los nodos i y j, suele denotarse por (i, j) el arco dirigido de i aj. Vale hacer hincapi´ en el sentido de los arcos, porque e si nosotros quisi´ramos que sea posible el avance de j a i deber´ e ıamos tener tambi´n el par (j, i) e en la red. Un grafo G es un par (N, A) donde 1. N es un conjunto de v´rtices o nodos: N = {x1 , x2 , . . .}. e 2. A es una familia en N × N de arcos dada por A = {(i, j, ), (k, l), . . .} Llamamos grafo dirigido a un grafo cuyos arcos...