io7 flujo maximo

Redes Flujo máximo 2012 \Apuntes de clase \ Ismael Véliz Vilca - 1

1 6.4 MODELO DE FLUJO MÁXIMO

VER video

Imagine una red de oleoductos que transportan crudo desde los pozos hasta las refinerías.

En las distancias intermedias adecuadas están instaladas estaciones de bombeo, para

mover el crudo por la red. Cada segmento de tubo tiene un flujo (o capacidad) máximo de

crudo. Un Segmento de tubo puede ser uni o bidireccional, dependiendo de su diseño. Un

segmento unidireccional tiene una capacidad finita en una dirección, y capacidad cero en

la dirección opuesta. La figura 6.27 muestra una red de oleoductos. ¿Cómo se puede

determinar la capacidad máxima de la red entre los pozos y las refinerías?

La solución del problema propuesto requiere convertir la red en una que tenga una sola

fuente y un solo "sumidero" o destino. Este requerimiento se llena usando arcos

unidireccionales de capacidad infinita, como indican los arcos de línea interrumpida en la

figura 6.27.

FIG 6.27 Red capacitada que une pozos y refinerías pasando por estaciones de bombeo


Dado el arco (i, j) con / < j, se usa la notación para representar las

capacidades de flujo en las dos direcciones, ij y j i, respectivamente. Para eliminar

ambigüedades se pone a a en el arco junto al nodo i, y ¡ se coloca junto al nodo j,

como se ve en la figura 6.28.

FIGURA 6.28 Flujos en arco: Cij de i y Cij de j i

6.4.1 Enumeración de cortes

Un corte define a un conjunto de arcos que, cuando se eliminan de la red, causan una

interrupción total del flujo entre los nodos fuente y sumidero. La capacidad de corte es

igual a la suma de las capacidades de los arcos correspondientes. Entre todos los cortes

posibles en la red, el que tenga la capacidad menor permite el flujo máximo en la red.

Ejemplo 6.4-1

Se tiene la red de la figura 6.29. En los arcos respectivos se indican las capacidades

bidireccionales, con la convención de la figura 6.28. Por ejemplo, para el arco (3,4), el

límite de flujo es 10 unidades de 3 a 4 y 5 unidades de 4 a 3.

FIGURA 6.29- Ejemplos de corles en redes de flujo

En la figura 6.29 se ilustran tres cortes, cuyas capacidades se calculan en la tabla siguiente.


Nota.- se cortamos con una línea imaginaria por ejemplo el punto 2 va a cortar los arcos (1,3)(1,4)(2,3)(2,5) = en el arco (1,4) fluye de 1 4 =10 y de 4 a 1 0 total de flujo máximo =110

No se puede decir cuál es el flujo máximo en la red, a menos que se enumeren todos

los cortes posibles. La única información que se puede obtener de la enumeración parcial

de los tres cortes es que el flujo máximo en la red no puede ser mayor que 60 unidades.

Desafortunadamente, enumerar todos los cortes no es una tarea sencilla, y entonces se

hace necesario desarrollar el eficiente algoritmo en la sección 6.4.2.

6.4.2 Algoritmo de flujo máximo (ver el libro de taha para ver el programa)

El algoritmo de flujo máximo se basa en determinar rutas de irrupción que tengan

flujo neto positivo entre los nodos fuente y sumidero. Cada ruta comunica parte o

todas las capacidades de sus arcos al flujo total en la red.

Considérese el arco (i, j) con capacidades iniciales . A medida que

partes de esas capacidades contribuyen al flujo en el arco, se actualizan los residuales (o

capacidades remanentes). La red con los residuales actualizados se llama red residual.

Se usará la notación (Cij ,Cji) para representar esos residuales.

Para un nodo j que recibe flujo del nodo i, se define una etiqueta [Aj,i), donde aj es el

flujo del nodo i al nodo j. Los pasos del algoritmo se resumen como sigue.

Paso 1. Para todos los arcos (i.j) se iguala la capacidad residual con la capacidad inicial;

esto es, . Sea a{ = ∞ y se etiqueta el nodo fuente 1 con

[∞o, --]. Se iguala i = 1 y se prosigue en el paso 2.

Paso 2. Determinar S¡, el conjunto de nodos j no etiquetados que se pueden alcanzar

directamente desde el nodo i, con arcos con residuales positivos (esto es. Cij> 0

para toda j Є S¡). Si S1 ≠θ, ir al paso 3. En caso contrario ir al paso 4.

Paso 3. Determinar k Є S1, tal que

Corte Arcos Asociados Capacidad 1 (1,2),(1,3),(1,4) 22+30+10 60

2(1,3),(1,4),(2,3),(2,5) 30+10+40+30 110

3 (2,5),(3,5),(4,5) 30+20+20 70


Igualar ak = cik y etiquetar el nodo k* con [ak, i]. Si k = n, el nodo de sumidero se ha

etiquetado, y se ha encontrado una ruta de irrupción; ir al paso 5. En caso

contrario, igualar i = k y seguir en el paso 2.

Paso 4. (Retroceso). Si i = 1, no hay otras irrupciones posibles; ir al paso 6. En caso

contrario, sea r el nodo que se ha etiquetado inmediatamente antes del nodo

actual i y quitar i del conjunto de nodos adyacentes a r. Igualar i = r y continuar en

el paso 2.

Paso 5. (Determinación de la red residual). Sea Np = (1, k¡, k2,..., n); se definen los

nodos de la p-ésima ruta de irrupción del nodo fuente 1 al nodo sumidero n.

Entonces el flujo máximo por la ruta se calcula como

fP = mín{a,, ak1, ak2,..., an)

La capacidad residual de cada arco a lo largo de la ruta de irrupción se

disminuye en fp unidades en la dirección del flujo y se aumenta fp unidades en la

dirección contraria; esto es, para los nodos i y j en la ruta, el flujo residual se

cambia del actual (cij cji ) a

a) (Cij-Fp, Cij +Fp ) si el flujo va de i a j

b) B) Cij +Fp ,Cji –fp ) si el flujo va de j a i

Se reinstalan todos los nodos que se hayan eliminado en el paso 4. Poner i = 1 y regresar

al paso 2 para intentar una nueva ruta de irrupción.

Paso 6. (Solución)

a) Si se han determinado m rutas de irrupción, el flujo máximo en la red es

F = A+f2+ ••• +fm„

b) Como los residuales inicial y final del arco (i, j) se obtienen con (C’ij,C’ji) y,(Cij,Cji

respectivamente, el flujo óptimo en el arco (i, j) se calcula como sigue: sea

Si α > 0, el flujo óptimo de i a j es α . Si β > 0,

el flujo óptimo de i a j es βp. (Es imposible que tanto α y β sean positivos.)1

Se invoca el proceso de retroceso del paso 4 cuando el algoritmo llega a un "punto ciego"

por descuido, en un nodo intermedio, antes de poder realizar una irrupción. El ajuste del

flujo en el paso 5 se puede explicar con la red de flujo sencilla de la figura 6.30. La red a)

obtiene la primera ruta de irrupción N1 = ( 1,2, 3,4) con su flujo máximo f1, = 5. Así, los

residuales de cada uno de los arcos (1,2), (2,3) y (3,4) se cambian de (5,0) a (0,5), según

1 *N. del R.T.: Por otro lado, si (β > 0, el flujo óptimo de j a i es β


el paso 5. La red b) proporciona ahora la segunda ruta de irrupción N2= {1, 3, 2,4) con f2 =

5. Después de hacer los ajustes necesarios de flujo, se obtiene la red c), donde ya no son

posibles más irrupciones. Lo que sucedió en la transición de b) a c) no es más que una

cancelación de un flujo antes comprometido en la dirección 23. El algoritmo puede

"recordar" que se había comprometido antes un flujo de 2 a 3 sólo porque se ha

aumentado la capacidad en la dirección contraria de 0 a 5 (de acuerdo con el paso 5).

FIGURA 6.30 Uso del residual para calcular el flujo máximo

Resolver con tora

Ejemplo 6.4-2


Determinar el flujo máximo en la red del ejemplo 6.4-1 (Figura 6.29). La figura 6.31

muestra un resumen gráfico de las iteraciones del algoritmo. El lector encontrará útil

comparar la descripción de las iteraciones con el resumen gráfico.


Figura 6.31 Iteraciones del algoritmo de flujo máximo del ejemplo 6-4-2

Iteración 1. Igualar los residuales iniciales (cij,cjii) a las capacidades iniciales (C’ij ,y, C’ji,).

Paso 1. Igualara a1 = ∞ y etiquetar el nodo 1 con [∞ , —]. Poner i = 1.

Paso 2. S1={2, 3, 4} (≠θ ).

Paso 3. k=3 porque c13 = máx{c12, c13,c14} = máx {20, 30, 10} = 30. Tomar a3 = C13 =

30 y etiquetar el nodo 3 con [30, 1 ]. Igualar i = 3 y repetir el paso 2.

Paso 2. S3 = (4, 5).

Paso 3. k = 5 y as = c35 = máx{10, 20} = 20. Etiquetar el nodo 5 con [20, 3].

Se obtuvo una irrupción. Ir al paso 5.

Paso 5. La ruta de irrupción se determina con las etiquetas comenzando en el nodo

5 y terminando en el nodo 1; esto es, (5) [20, 3] (3) [30, 1] (1). Así,

N1 = {1, 3, 5} y f1, = mín{a1,a3,a5} = {∞ , 30, 20} = 20. Las capacidades

residuales a lo largo de la ruta N1 son

(c13, c31) = (30 - 20, 0 + 20) = (10, 20)

(C35, c53) = (20 - 20, 0 + 20) = (0, 20)

Iteración 2.

Paso 1. • Poner a1 = ∞ y etiquetar el nodo 1 con [∞ , —]. Igualar i = 1.

Paso 2. S1 = (2,3,4).

Paso 3. k = 2 y a2 = c12 = máx(20, 10, 10) = 20. Poner i = 2 y repetir el paso 2.

Paso 2. S2={3,5).

Paso 3. k = 3 y a3 = c23=40. Etiquetar el nodo 3 con [40, 2]. Poner i = 3 y repetir el paso 2.

Paso 2. S3 = (4) (observe que c35 = 0; en consecuencia el nodo 5 no puede incluirse en

S4).


Paso 3. k = 4 y a4 = c34 = 10. Etiquetar el nodo 4 con [ 10, 3]. Igualar i' = 4 y repetir el

paso 2.

Paso 2. 54 = [5] (observe que los nodos 1 y 3 ya se han etiquetado y en consecuencia

no se pueden incluir en S4)

. Paso 3. k = 5 y as = c45 = 20. Etiquetar el nodo 5 con [20,4). Se ha logrado la irrupción.

Ir al paso 5.

Paso 5. N2 = {1,2, 3,4, 5) y f2 = mín{ ∞ , 20,40, 10, 20) = 10. Los residuales a lo largo de

la ruta N2 son

(c12,c21)=(20-10,0+10)=(10,10)

(c23,c32)=(40-10,0+10)=(30,10)

(c34,c43)=(20-10,510)=(0,15)

(c45,c34)=(20-10,0+10)=(10,10)

Iteración 3.

Paso 1. Poner a, =∞ y etiquetar el nodo 1 con [∞ , —]; poner i = 1

Paso 2. S1 = (2,3,4).

Paso 3. k = 2 y a2 = cl2 = máx( 10, 10, 10) = 10 (aunque los empates se rompen en forma

arbitraria, TORA selecciona siempre el nodo empatado que tenga el índice menor;

usaremos esta convención en el ejemplo). Etiquetar el nodo 2 con [10, 1]. Poner i = 2 y

repetir el paso 2.

Paso 2. S2={3,5).

Paso 3. k = 3 y a3 = c23 = 30. Etiquetar el nodo 3 con [30, 2]. Poner i = 3 y repetir el

paso 2.

Paso 2. S3 = 0 (porque cM = c35 = 0). Ir al paso 4 para retroceder.

Paso 4. La etiqueta [30, 2] en el nodo 3 da el nodo inmediato anterior r = 2. Sacar el

nodo 3 de más consideraciones en esta iteración, tachándolo. Repetir el paso 2

con i = r = 2.

Paso 2. S2 = {5}; nótese que el nodo 3 se ha eliminado en el paso de retroceso.

Paso 3. k = 5 y a5 = c25 = 30. Etiquetar el nodo 5 con [30, 2] . Se ha logrado la irrupción;

proseguir en el paso 5.

Paso 5. N3 = {1, 2,5} y c5 = mín(oo, 10, 30) = 10. Los residuales a lo largo de la trayec-

toria de N3 son '

(c,2, c21) = (10 - 10, 10 + 10) = (0, 20)

(C25,. C52) = (30 - 10, 0 + 10) = (20, 10)


Iteración 4. En esta iteración se obtiene N4= (1, 3, 2, 5) con f4=10 (¡compruébelo!).

Iteración 5. En esta iteración se obtiene N5= [ 1,4,5) con/5 = 10 (¡compruébelo!).

Iteración 6. Todos los arcos que salen del nodo 1 tienen residuales cero. En

consecuencia no hay más irrupciones posibles. Pasaremos al paso 6 para determinar la

solución.

Paso 6. El flujo máximo en la red es F =f1+f2 + ... +f5 = 20 + 10 + 10 + 10 + 10 = 60

unidades. El flujo en los distintos arcos se calcula restando los últimos residuales

(cij,cji,) en las iteraciones 6 de las capacidades iniciales (C’ j;, C’;/), como se ve en la

tabla

Arco (C’ij,C’ji)-(Cij,Cji Flujo Dirección(1,2) (20, 0) - (0, 20) = (20, -20) 20 12(1.3) (30, 0) - (0, 30) = (30, -30) 30 13(1.4) (10, 0)-(0, 10) =(10, -10) 10 14(2,3) (40, 0) - (40, 0) = (0, 0) 0 —(2,5) (30, 0) - (10, 20) = (20, -

20)20 25

(3,4) (10.5) -(0, 15) = (10. -10) 10 34(3,5) (20, 0) - (0, 20) = (20, -20) 20 35(4.5) (20, 0) - (0, 20) = (20, -20) 20 45

Puede usted usar TORA para resolver el modelo de flujo máximo en una forma automa-

tizada, o para producir las iteraciones que se describieron arriba. Partiendo del menú

SOLVE/ MODIFY (resolver/modificar), seleccione solve Probiem (resolver problema).

Después de especificar el formato de los resultados, pase a la pantalla de resultados y

seleccione Máximum FIOWS (flujos máximos) o iterations (iteraciones). La figura 6.32

muestra las dos primeras iteraciones del ejemplo 6.4-2 (archivo ch6ToraMaxFlowEx6-4-

2.txt).


FIGURA 6.32 Iteraciones de flujo máximo para el ejemplo 6.4-2 con TORA

Las mismas iteraciones con Excel

ITERACION 1DE\A 1 2 3 4 5 flujo flujo acum RUTA

1 20 30 10 0 30 1,32 0 40 0 30 3 0 0 10 20 20 54 0 0 5 20 5 0 0 0 0

Flujo 20 20 1,3,5ITERACION 2DE\A 1 2 3 4 5 flujo flujo acum RUTA

1 20 10 10 0 20 1,22 0 40 0 30 40 33 20 0 10 0 10 44 0 0 5 20 20 55 0 0 20 0

Flujo 10 30 1,2,3,4,5ITERACION 3DE\A 1 2 3 4 5 flujo flujo acum RUTA

1 10 10 10 0 10 1,22 10 30 0 30 30 5


3 20 10 0 0 4 0 0 15 10 5 0 0 20 10


1 0 10 10 0 10 1,32 20 30 0 20 20 3 20 10 0 0 10 24 0 0 15 10 5 0 10 20 10

Flujo 10 50 1,3,2,5ITERACION 5DE\A 1 2 3 4 5 flujo flujo acum RUTA

1 0 0 10 0 10 1,42 20 40 0 10 3 30 0 0 0 4 0 0 15 10 10 55 0 20 20 10


1 0 0 0 0 10 2 20 40 0 0 3 30 0 0 0 4 10 0 15 0 10 5 0 20 20 20

Flujo 0 60

Iteracion Camino seleccionado flujo Flujo flujo acum1 1,3,5 30,20 20 202 1,2,3,4,5 20,40,10,20 10 303 1,2,3,2,5 10,30,20 10 40


4 1,3,2,5 10,10,20 10 505 1,4,5 10.1 10 60

SOLUCION CON WINQSB


SOLUCION DE FLUJO MAXIMO CON POMS

Pruebe que el flujo de 1 a 40 el flujo es 20


Pruebe que no hay flujo de 4 1 1 y el El flujo de 4 a 3 es 5

Programa con visual c++ modo consola

// *** otros.hvoid iniciarVector(int A[], int n) { for (int i=1;i<=n;i++) A[i]=0;}void rellenarVector(int A[], int n) { for (int i=1;i<=n;i++) A[i]=1;}int menorVector(int A[], int nc){ int menor=100,i; for (i=1;i<=nc;i++) if (A[i]<menor) menor=A[i]; return menor; }void imprimirVector( int A[], int nc){ printf("\n"); int i;

for ( i=1; i<=nc;i++) printf(" %d ", A[i]);}

void impMatriz(int A[][maximo], int nf,int nc) { int fila,col; for ( fila=1;fila<=nf;fila++) {printf("\n "); for (col=1;col<=nc;col++) printf("%4d",A[fila][col]); } }int ElemMayor( int D[][maximo], int C[],int nfila, int nc){ int col, emay=0,mayor=-99; for ( col=1; col<=nc;col++) if ( C[col]==1&& D[nfila][col]>mayor) { mayor=D[nfila][col]; emay=col; } return emay;}

// *** flujo maximo#include <conio.h>#include <stdio.h> const int maximo=6;


#include "otros.h"

void flujomaximo(int D[][maximo],int nf,int nc){int i,fila,col,k;

int pmax=0,emay=0,cont=0,ne=0,menorvalor=0,flujo=0;int A[8],B1[8],B2[8],C[8];//A= vector para almacenar el mayor valor// B1 = vector para almacenar el lugar del mayor fila (origen)// B2 = vector para almacenar el lugar del mayor columna ( destino)

// C = nodo que quedanfila=1;

for (k=1;k<=5;k++) { printf("\n***************** iteracion %d ", k);impMatriz(D,nf,nc);

iniciarVector(A,nc);iniciarVector(B1,nc);iniciarVector(B2,nc);rellenarVector(C,nc);fila=1;

emay=99; pmax=1;A[1]=emay; B1[1]=fila; B2[1]=pmax; cont=1; C[1]=0; for (fila=1;fila<=nc;) { pmax= ElemMayor( D,C,fila,nc); emay= D[fila][pmax]; if (emay<=0) { C[pmax]=0; fila=B1[cont];

printf("\n retroceso %d ",fila); C[pmax]=0; cont--; } else {cont++; A[cont]=emay; B1[cont]=fila; B2[cont]=pmax; C[pmax]=0; printf( "\n el nodo %d elemento maximo es %d = %d ir al nodo %d", fila,pmax,emay,pmax); fila=pmax; } if (pmax >=nc) { //printf("\n termina proceso ");

ne=cont;break;} } // calculo de las residuales //imprimirVector( A,ne); menorvalor= menorVector(A,ne);


flujo=flujo+menorvalor;printf("\n el flujo es %d",flujo);for (i=1;i<=ne;i++){ fila= B1[i]; col=B2[i]; D[fila][col]= D[fila][col]-menorvalor;D[col][fila]= D[col][fila]+menorvalor;} }getch();}int main(){ int D[maximo][maximo] ={0, 0, 0, 0, 0, 0,0, 0, 20, 30, 10, -99,0, 0, 0, 40, -99, 30,0, 0, 0, 0, 10, 20,0, 0, -99, 5, 0, 20,0, -99, 0, 0, 0, 0,};int n=5; flujomaximo(D,n,n);}


Module Module1 Sub iniciarVector(ByVal A() As Integer, ByVal n As Integer) Dim I As Integer For I = 1 To n A(I) = 0 Next End Sub Sub rellenarVector(ByVal A() As Integer, ByVal n As Integer) Dim I As Integer For I = 1 To n A(I) = 1 Next


End Sub Function menorVector(ByVal A() As Integer, ByVal nc As Integer) Dim menor As Integer = 100, i As Integer For i = 1 To nc If (A(i) < menor) Then menor = A(i) Next menorVector = menor End Function

Sub imprimirVector(ByVal A() As Integer, ByVal nc As Integer) Dim i As Integer Console.WriteLine() For i = 1 To nc Console.Write(" {0} ", A(i)) Next End Sub Sub impMatriz(ByVal A(,) As Integer, ByVal nf As Integer, ByVal nc As Integer) Dim fila As Integer, col As Integer For fila = 1 To nc Console.WriteLine() For col = 1 To nc Console.Write(A(fila, col).ToString.PadLeft(5)) Next Next End Sub

Function ElemMayor(ByVal D(,) As Integer, ByVal c() As Integer, ByVal nfila As Integer, ByVal nc As Integer) ReDim D(6, 6) REM ´'+++++++++++++++

Dim col As Integer, emay As Integer = 0, mayor As Integer = -99 For col = 1 To nc If (c(col) = 1 And D(nfila, col) > mayor) Then mayor = D(nfila, col) emay = col End If Next ElemMayor = emay End Function Sub flujomaximo(ByVal D(,) As Integer, ByVal nf As Integer, ByVal nc As Integer) Dim i As Integer Dim fila As Integer Dim col As Integer, k As Integer

Dim pmax As Integer = 0, emay As Integer = 0, cont As Integer = 0, ne As Integer = 0, menorvalor As Integer = 0, flujo As Integer = 0 Dim A(8) As Integer, B1(8) As Integer, B2(8) As Integer, C(8) As Integer '//A= vector para almacenar el mayor valor '// B1 = vector para almacenar el lugar del mayor fila (origen)


'// B2 = vector para almacenar el lugar del mayor columna ( destino) ' // C = nodo que quedan fila = 1 For k = 1 To 5 Console.WriteLine("***************** iteracion {0}", k) impMatriz(D, nf, nc) iniciarVector(A, nc) iniciarVector(B1, nc) iniciarVector(B2, nc) rellenarVector(C, nc) fila = 1 emay = 99 pmax = 1 A(1) = emay B1(1) = fila B2(1) = pmax cont = 1 C(1) = 0 For fila = 1 To nc pmax = ElemMayor(D, C, fila, nc) emay = D(fila, pmax) If (emay <= 0) Then C(pmax) = 0 fila = B1(cont) Console.WriteLine(" retroceso {0}", fila) C(pmax) = 0 cont = cont - 1 Else cont = cont + 1 A(cont) = emay B1(cont) = fila B2(cont) = pmax C(pmax) = 0 Console.WriteLine() Console.WriteLine(" el nodo {0}elemento maximo es {1} = {2} ir al nodo {1}", fila, pmax, emay, pmax) fila = pmax End If If (pmax >= nc) Then Console.WriteLine("n termina proceso ") ne = cont Exit For REM´en vez de break End If Next '// calculo de las residuales '//imprimirVector( A,ne); menorvalor = menorVector(A, ne) flujo = flujo + menorvalor Console.WriteLine("\n el flujo es {0}", flujo)


For i = 1 To ne fila = B1(i) col = B2(i) D(fila, col) = D(fila, col) - menorvalor D(col, fila) = D(col, fila) + menorvalor Next Next Console.ReadLine() End Sub

Sub Main() ' '*** flujo maximo Const maximo As Integer = 6 Dim D(maximo, maximo) As Integer D(0, 0) = 0 : D(0, 1) = 0 : D(0, 2) = 0 : D(0, 3) = 0 : D(0, 4) = 0 : D(0, 5) = 0 D(1, 0) = 0 : D(1, 1) = 0 : D(1, 2) = 20 : D(1, 3) = 30 : D(1, 4) = 10 : D(1, 5) = -99 D(2, 0) = 0 : D(2, 1) = 0 : D(2, 2) = 0 : D(2, 3) = 40 : D(2, 4) = -99 D(2, 5) = 30 D(3, 0) = 0 : D(3, 1) = 0 : D(3, 2) = 0 : D(3, 3) = 0 : D(3, 4) = 10 : D(3, 5) = 20 D(4, 0) = 0 : D(4, 1) = 0 : D(4, 2) = -99 : D(4, 3) = 5 : D(4, 4) = 0 : D(4, 5) = 20 D(5, 0) = 0 : D(5, 1) = -99 : D(5, 2) = 0 : D(5, 3) = 0 : D(5, 4) = 0 : D(5, 5) = 0 Dim n As Integer = 5 flujomaximo(D, n, n) Console.ReadLine() End Sub

End Module


Arreglar el programa y converitr en funcion personalidad

4 FLUJO MAXIMO Algoritmo de Ford-Fulkerson

El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar

el flujo, hasta que se alcance el flujo máximo. Es aplicable a los Flujos maximales. La idea

es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y

destino. Su nombre viene dado por sus creadores, L. R. Ford, Jr. y D. R. Fulkerson.

1. Sunco Oil quieres enviar la máxima cantidad posible de petróleo ( por hora) via

tubería del nodo so al nodo si mostrado en la figura. En su camino del nodo so hasta

nodo si, el petróleo debe pasar por alguna o todas las estaciones 1, 2 y 3 :los distintos

arcos representan tuberías de diferentes diámetros – El número máximo de barriles

( millones de barriles por hora ) que se bombea por cada arco se muestra en la tabla .

cada número se llama una capacidad de arco . Determinar el numero máximo de

barriles de petróleo por hora que puede enviarse de so a si

http://es.wikipedia.org/wiki/D._R._Fulkerson

http://es.wikipedia.org/w/index.php?title=L._R._Ford,_Jr.&action=edit&redlink=1

http://es.wikipedia.org/wiki/Flujo_maximal

http://es.wikipedia.org/wiki/Camino


Plantear como programación lineal

Max z= siso;Sujeto a:

x0=xso1+xs02 xso1+xs02-xo=0 ( restricciones de flujo de nodo s0)xso1 = x13+x23 xso1- x13+x23=0 ( restricciones de flujo de nodo 1)x23+xso2 = x2si x23+xso2 - x2si= 0 ( restricciones de flujo de nodo 2)x13=x3si x13-x23si= 0 ( restricciones de flujo de nodo 3)x3si=siso x3si-siso= 0 ( restricciones de flujo de nodo si)xso1<=2 ( capacidad de arco xs01)xso2<=3 (capacidad de arco xs02)x12<=3 (capacidad de arco x12)x13<=4 (capacidad de arco x13)x3si=1 (capacidad de arco x3si)x2si<=2 (capacidad de arco x2si)

También se podría maximizar la suma de las capacidades o solamente so

Capacidades de Arco para Sunco OilArco Capacidad(so,1) 2(so,2) 3(1,2) 3(1,3) 4(3,si) 1(2,si) 2


SO XSO1 XSO2 X12 X13 X2SI X3SI sumacantidad 3 2 1 0 2 1 2 11 Costo 0 0 0 0 0 0 0 DISP Nodo So -1 1 1 0 = 0 Nodo 1 -1 1 1 0 = 0 Nodo 2 -1 -1 1 0 = 0 Nodo 3 -1 1 0 = 0 Nodo Si 1 -1 -1 0 = 0 CAP MAX 999 2 3 3 4 1 2

Otra forma maximizando So

SO XSO1 XSO2 X12 X13 X2SI X3SI cantidad 3 2 1 0 2 1 2 Costo 0 0 0 0 0 0 0 DISP Nodo So -1 1 1 0 = 0 Nodo 1 -1 1 1 0 = 0 Nodo 2 -1 -1 1 0 = 0 Nodo 3 -1 1 0 = 0 Nodo Si 1 -1 -1 0 = 0 CAP MAX 999 2 3 3 4 1 2


Resolviendo con WINQSBComo es red de flujo con capacidad ( se resuelve como programación lineal)


2. Algoritmo de Ford-Fulkerson

a): red original b. Se agregan 3 unidades de flujo usando solo arcos directos ( s0-3-si)

c. se agregan dos unidades de flujo usando solo arcos directos (so-1-2-3-si)

d se agregan dos unidades de flujo usando una arco inverso (1,2) y se obtuvo un flujo

máximo de 7 ( so -2 -1 si)

3. Un conjunto de vías rápidas tiene las siguientes capacidades (miles de vehículos /hora)1. Determinar el flujo máximo de vehículos /hora que puedan para por el sistema


2. Cuantos vehículos/hora deben por cada vía para lograr el flujo máximo

iteraciónCamino seleccionado flujo

flujo acumulado

1 1,2,4,6 3 32 1,3,6 2 53 1,4,5,6 2 74 1,2,4,5,6 3 105 1,4,2,5,6 1 11

Arco C'ij c'ji cij cji = flujo Direc1,2 3 0 0 3 3 -3 3 1,21,3 6 0 1 5 5 -5 5 1,31,4 3 0 0 3 3 -3 3 1,42,4 2 2 3 1 -1 1 1 4,22,5 4 4 0 8 4 -4 4 2,53,4 3 3 0 6 3 -3 3 3,43,6 2 0 0 2 2 -2 2 3,64,5 2 2 0 2 2 0 2 4,54,6 3 0 0 3 3 -3 3 4,65,6 6 0 0 6 6 -6 6 5,6


4 La compañía estatal de petróleo cuenta con una red de oleoductos que utiliza para

transportar petróleo desde su refinería (fuente ) hasta diversos centros de

almacenamiento . Una parte de la red de oleoductos es la siguiente :

Como puede observarse, las capacidades de flujo son variables como resultado de los diversos diámetros de los ductos . En miles de galones por hora.

1. La empresa desea abastecer al almacén 7 ¿cuál es el flujo máximo con el cual puede abastecerlo?

2. ¿cuanto tiempo se requiere para satisfacer una demanda de 95,000 galones para el mismo almacén?

3. Si se presentará una ruptura o cierre en el ducto que va de 2-3 ¿ cúal será ahora el flujo máximo para el sistema ?

.4.3 Formulación del problema de flujo máximo con programación lineal


Se define xIJ como la cantidad de flujo en el arco (I', j) y sea cIJ la capacidad del mismo

arco. Se supone que s y t son los nodos inicial y terminal entre los cuales se debe

determinar el flujo máximo en la red capacitada (es decir, con sus capacidades).

Las restricciones del problema conservan el flujo de entrada y salida en cada nodo,

con excepción de los nodos inicial y terminal. La función objetivo maximiza el flujo total

"que sale" del nodo inicial s, o el flujo total "que entra" al nodo terminal t.

Max z =s0s.anodo(1) s0=x14+x13+x12 s0-x14-x13-x12=0nodo (2) x12=x23+x25; x12-x23-x25=0nodo (3) x13+x23=x34+x35; x13+x23-x34-x35=0nodo (4) x14+x34=x43+x45; x14+x34-x43-x45=0nodo (5) x25+x35+x45=s0; x25+x35+x45-s0=0;capacidadesx12<=20x13<=30x14<=10x23<=40x25<=30X34<=10X35<=20X43<=5X45<=20

Ejemplo 6.4-3 En el modelo de flujo máximo de la figura 6.29 (Ejemplo 6.4-2), s = 1 y t = 5. La tabla siguiente es un resumen del programa lineal correspondiente con dos funciones objetivo distintas, que dependen de si se maximiza la salida del nodo 1 (= z¡) o la entrada al nodo 5 (= z2).


1 2 3 4 5 6 7 8 9 10 variable S0 x12 x13 x14 x23 x25 x34 x35 x43 x45 cantidad 60 20 30 10 0 20 10 20 0 20 190 RESTRICCIONES SUMA = 0Nodo 1 -1 1 1 1 0 = 0Nodo 2 -1 1 1 0 = 0Nodo 3 -1 -1 1 1 0 = 0Nodo 4 -1 -1 1 1 0 = 0Nodo 5 1 -1 -1 -1 0 = 0CAP MINIMA 0 0 0 0 0 0 0 0 0 0 CAP MAXIMA 999 20 30 10 40 30 10 20 5 20


a solución óptima, usando cualquiera de las funciones objetivo es

X12 = 20, x13 = 30, .x14 = 10, x25 = 20, x34 = 10, x35 =20 ,x35=20

El flujo máximo asociado es s0=60.

Solución con WINQSB Forma 2


FLUJO MAXIMO APLICADO A BALANCE DE LINEA

Se tiene las siguientes actividades para fabricar un mueble cual es el flujo máximo

a) Si se desea fabricar 10 unidades la hora como debería ser el flujo

Nro Actividadtiempo min

1 Cortar 102 Soldar 203 Pinta 15

MAX so ( o la suma de flujo)

Sujeto a:

Nodo 1 So=cortars0-cortar=0;

Nodo 2 cortar=soldarcortar-soldar=0;

Nodo 3 soldar=pintar soldar-pintar=0

Nodo 4 pintar= so pintar-s0 =0


Agrupando estaciones

x12 x23 x34 TOTALcantidad 10 20 15 COSTO Costo 1 1 1 45 diferenciaE1 1 0 1 25 5E2 0 1 0 20 suma1 1 1 1 3 suma 1 1 1 3

Agrupar las estaciones


VARIABLE 1 2 3 4 5 6 7 8 9 TIEMPO 4 5 2 4 3 8 6 3 10 45 produccion 15 12 30 15 20 7.5 10 20 6 135.5 SUMA E1 1 0 0 0 0 1 0 1 0 15 E2 0 0 1 1 1 0 1 0 0 15 E3 0 1 0 0 0 0 0 0 1 15 suma1 1 1 1 1 1 1 1 1 1 45 15suma 1 1 1 1 1 1 1 1 1

Sepuede com flujo máximo

tiempo 450 TAREA TIEMPO PRECEDENCIA PREDUCCION/HORA

1 4 - 152 5 1 123 2 1 304 4 1 15

F1 0 0F2 0 0

5 3 1 206 8 2 7.5


7 6 3,4,5 108 3 6,7 209 10 8 6

SUMA 45

1 2 3 4 5 6 7 8 9

de\a 1 2 3 F1 F2 4 5 6 7

1 0 15 0 0 0 0 0 0 0

2 0 0 12 30 20 15 0 0 0

3 0 0 0 0 0 0 7.5 0 0

F1 0 0 0 0 0 0 0 0 0

F2 0 0 0 0 0 0 0 0 0

4 0 0 0 0 0 0 10 0 0

5 0 0 0 0 0 0 0 20 0

6 0 0 0 0 0 0 0 0 6

7 0 0 0 0 0 0 0 0 0

Resolviendo con tora da el siguiente resultado


EL flujo máximo es de 6 unidades hora ( mejorar el planteamiento) por ejemplo

considerar la precedencia en la agrupacion de estaciones

Resolviendo con WINQSB como problema de flujo máximo


Resolviendo como problema de programación lineal (como problema de red capacitada)


6.5 PROBLEMA DEL FLUJO CAPACITADO CON COSTO MÍNIMO

El problema de flujo capacitado con costo mínimo se basa en las hipótesis siguientes:

1. A cada arco se le asocia un costo de flujo unitario (no negativo).

2. Los arcos pueden tener límites inferiores positivos de capacidad.

3. Todo nodo en la red puede funcionar como fuente o como sumidero.

El nuevo modelo determina los flujos en los distintos arcos, que minimizan el costo total y

a la vez satisfacen las restricciones de flujo y las cantidades de oferta y demanda en los

nodos. Primero representaremos el modelo de red capacitada de flujo y su formulación

equivalente en programación lineal. Esta formulación es la base del desarrollo de un

algoritmo simplex capacitado especial, para resolver el modelo de flujo en la red. La

sección termina con una presentación de una plantilla de hoja de cálculo, de la red

capacitada con costo mínimo

6.5.1 Representación en red


Se tiene una red capacitada G = (N, A), donde N es el conjunto de los nodos y A es el

conjunto de los arcos, y se definen

xij = cantidad de flujo del nodo / al nodo y

uij, (Iij:) = capacidad máxima (mínima) del arco (i,J)

Cij = costo de flujo unitario del nodo i al nodo j

f¡ = flujo neto en el nodo i

La figura 6.36 muestra las definiciones en el arco (i, j). La etiqueta [f.\ supone un valor

positivo (negativo) cuando hay una oferta o suministro neto (demanda) asociada al nodo i

FIGURA 6.36 Arco capacitado con flujo externo

Ejemplo 6.5-1 GrainCo abastece de maíz a tres granjas avícolas desde tres silos. Las

cantidades de oferta en los tres silos son 100, 200 y 50 mil bushels (1 bushel = 35.23

litros). GrainCo usa principal-mente ferrocarril para transportar su maíz a las granjas, a

excepción de tres rutas, en las que se usan camiones.

La figura 6.37 muestra las rutas disponibles entre los silos y las granjas. Los silos se re-

presentan con los nodos 1,,2 y 3, cuyas cantidades de suministro son [100], [200] y [50],

respectivamente. Las granjas se representan con los nodos 4,5 y 6, cuyas demandas son

[-150], [-80] y [-120], respectivamente. Las rutas permiten transbordos entre los silos. Los

arcos (1,4), (3, 4) y (4, 6) son de camiones, con capacidades mínimas y máximas. Por

ejemplo, la capacidad de la ruta (1,4) es de 50 a 80 mil bushels. En todas las demás rutas

se usan furgones, cuya capacidad máxima es prácticamente ilimitada. Los costos de

transporte, por bushel, se indican en sus arcos respectivos.


FIGURA 6.37 Red capacitada para el ejemplo 6.5-1

Solucion con programacion lineal

Minimizar z = 3x12+4x13+5x23+6x25+1x34+2x35+2x46+4x56SujetoNodo 1 100= x12+x13+x14x12+x13+x14=100Nodo 2= x12+200=x23+x25x12-x23-x25=-200-x12+x23+x25=200Nodo 3 = x13+x23+50=x35+x34 x13+x23-x35-x34=-50 -x13-x23+x35+x34=50Nodo 4 = x14+x34=x46+150 x14+x34-x46=150Nodo 5 = x35+x25=x56+80 x35+x25-x56=80Nodo 6 = x46+x56=120CapacidadesX14 >=50X14<=80X34>=70X34<=120X46>=100X46<=120

nombre Variable x12 x13 x14 x23 x25 x34 x35 x46 x56 cant 0 20 80 50 100 120 0 100 20 costo minimo costos unitarios 3 4 1 5 6 1 2 2 4 1410 restricciones TOTAL = Lado Derechonodo 1 1 1 1 100 = 100nodo 2 -1 1 1 150 = 200nodo 3 -1 -1 1 1 50 = 50nodo 4 -1 -1 1 -100 = -150nodo 5 -1 -1 1 -80 = -80nodo 6 -1 -1 -120 = -120Cap Minima 0 0 50 0 0 70 0 100 0 Cap Maxima 999 999 80 999 999 120 999 120 999


El problema no tiene solución por que exige que se pase 100 de arco 4 a 6 lo cual no es posible

1. Se fabrica un producto para satisfacer la demanda durante un horizonte de planeación

de 4 periodos, de acuerdo con los siguientes datos:

Periodo Unidades de demanda

Costo Unitario de producción ($)

Costo Unitario de retención ($)

1 100 24 12 110 26 23 95 21 14 125 24 2No se permite surtir pedidos atrasados. Represente el problema como modelo de red. 2.

En el problema 1, suponga que se permite surtir pedidos atrasados con una penalización

de $1.50 por unidad y por periodo. Formule el problema como modelo de red

6.5.2 Formulación con programación lineal

La formulación de un modelo de red capacitada como programa lineal es la base del

desarrollo del algoritmo símplex capacitado, que presentaremos en la sección siguiente. Al

usar la notación descrita en la sección 6.5.1, el programa lineal para la red capacitada es

Minimizar z =

sujeta a

La ecuación para el nodo j mide el flujo fj neto en el nodo j como sigue:

(Flujo que sale del nodo j) - (Flujo que entra al nodo j') =f¡

El nodo j funciona como fuente si.fj > 0 y como sumidero si fj<0.

Siempre se puede eliminar la cota inferior Iij, de las restricciones, mediante la sustitución

x¡¡= xij+Iij

La nueva variable de flujo, x'iy tiene un límite superior igual a u¡j-Iij. Además, el flujo neto

en el nodo i se vuelve fj-Iij y en el nodo j es fj+Iij. La figura 6.38 muestra la transformación

de la actividad (i, j) después de que ha salido por sustitución la cota inferior.


FIGURA 6.38 Eliminación de la cota inferior en los arcos

Ejemplo 6.5-2

Escriba el programa lineal para la red de la figura 6.37, antes y después de eliminar las

cotas inferiores por sustitución.

Las restricciones principales del programa lineal relacionan el flujo de entrada y salida

en cada nodo, y así se obtiene el siguiente programa lineal:

x12 x13 x14 x23 x25 x34 x35 x46 x56 dispminimizar 3 4 1 5 6 1 2 2 4 nodo1 1 1 1 100nodo 2 -1 1 1 200nodo 3 -1 -1 1 1 50nodo 4 -1 -1 1 -150nodo 5 -1 -1 1 -80nodo 6 -1 -1 -120cotas inferiores 0 0 50 0 0 70 0 100 0 cotas superiores 999 999 80 999 999 120 999 120 999

Observe el arreglo de los coeficientes de las restricciones. La columna asociada con la

variable Xij tiene exactamente un +1 en el renglón i y un —1 en el renglón j. El resto de

los coeficientes es 0. Esta estructura es característica de los modelos de flujo en red.

Las variables con cotas inferiores se sustituyen como sigue:

X14= x14+50

X34=x34+70

X46=x46+100

El programa lineal que resulta es

x12 x13 x14 x23 x25 x34 x35 x46 x56 dispminimizar 3 4 1 5 6 1 2 2 4 nodo1 1 1 1 50nodo 2 -1 1 1 200nodo 3 -1 -1 1 1 -20nodo 4 -1 -1 1 -130


nodo 5 -1 -1 1 -80nodo 6 -1 -1 -20cotas superiores 999 999 30 999 999 50 999 20 999

La red correspondiente, después de eliminar por sustitución las cotas inferiores, se ve en

la figura 6.39. Observe que la sustitución de la cota inferior se puede hacer en forma

directa en la figura 6.37, usando la sustitución de la figura 6.38 y sin necesidad de

expresar el problema primero como programa lineal.

FIGURA 6.39 Red del ejemplo 6.5-2 después de eliminar las colas inferiores por sustituciónEjemplo 6.5-3 (Programación de empleo)

Este ejemplo ilustra un modelo de red que al principio no satisface el requisito de "flujo en

nodo (es decir, que el flujo de salida del nodo menos el flujo de entrada al nodo es igual al

flujo neto del nodo), pero que se puede convertir con facilidad a esta forma mediante una

manipulación especial de las restricciones del programa lineal.

La agencia de empleo Tempo tiene un contrato para proporcionar trabajadores durante los

4 meses siguientes (de enero a abril) de acuerdo con el calendario siguiente:

Mes Ene Feb Mar AbrCantidad o número de trabajadores 100 120 80 170

Debido al cambio en la demanda podría ser más económico conservar más trabajadores que los necesarios

durante determinado mes. El costo de reclutar y mantener a un trabajador es función de su periodo de

empleo, como se ve en la tabla siguiente:

Duración del empleo (meses) 1 2 3 4


Costo por trabajador ($) 100 130 180 220Sea Xij = cantidad de trabajadores contratados al iniciar el mes i y despedidos al

iniciar el mes j

Por ejemplo, xl2 expresa la cantidad de trabajadores contratados en enero sólo durante 1

mes. Para formular el problema como programa lineal para el periodo de 4 meses, se

agrega mayo como mes ficticio (el mes 5) para que x45 defina la contratación en abril y

para abril. Las restricciones tienen en cuenta que la demanda para el periodo k se pueden

satisfacer para toda xij tal que i ≤ k < j. Si S¡≥s 0, es la cantidad sobrante de trabajadores

en el mes i, el programa lineal es

x12 x13 x14 x15 x23 x24 x25 x34 x35 x45 s1 s2 s3 s4 dispMininizar 100 130 180 220 100 130 180 100 130 100 Ene 1 1 1 1 -1 100Fe 1 1 1 1 1 1 -1 120Mar 1 1 1 1 1 1 -1 80Abr 1 1 1 1 -1 170

El programa lineal anterior no tiene la estructura especial (-1, +1) del modelo de flujo

en red (véase el ejemplo 6.5-2). Sin embargo, este programa lineal se puede convertir en

un modelo equivalente de red de flujo usando las siguientes manipulaciones aritméticas:

1. En un programa lineal de n ecuaciones, crear una nueva ecuación, la n + 1, multipli-

cando la ecuación n por -1.

2. Dejar sin cambio la ecuación 1.

3. Para i = 2, 3,..., n, reemplazar cada ecuación i con (ecuación /) — (ecuación i - 1).

La aplicación de estas manipulaciones al ejemplo de programación de empleo da

como resultado el siguiente programa lineal, cuya estructura se ajusta al modelo de flujo

en red:

x12 x13 x14 x15 x23 x24 x25 x34 x35 x45 s1 s2 s3 s4 dispMininizar 100 130 180 220 100 130 180 100 130 100 Ene 1 1 1 1 -1 100Fe -1 1 1 1 1 1 -1 20mar -1 -1 1 -1 1 -1 -40Abr -1 -1 1 1 -1 90Mayo -1 -1 -1 -1 1 -170


Al usar esta formulación, el modelo de programación de empleo se puede representar,

en forma equivalente, por la red de flujo con costo mínimo de la figura 6.40. En realidad,

como los arcos no tienen cotas superiores, el problema también se puede resolver como

un modelo de transbordo (véase la sección 5.5).

FIGURA 6.40 Representación del problema de programación de empleos como red

6.5.3 Algoritmo simplex de red capacitada

Este algoritmo se basa en los pasos exactos del método simplex normal, pero su objeto es

aprovechar la estructura especial en red del modelo de flujo con costo mínimo.

Ya que f¡ es el flujo neto en el nodo í, como se definió en el programa lineal de la sec-

ción 6.5.2, el algoritmo simplex capacitado estipula que la red debe satisfacer

La condición indica que toda la oferta en la red es igual a la demanda total. Siempre

se puede satisfacer este requisito agregando una fuente o un destino ficticios para

balancear, que se conectan con todos los demás nodos de la red con arcos de costo

unitario cero y capacidad infinita. Sin embargo, el balanceo de la red no garantiza que

haya una solución factible, porque eso depende de las restricciones de capacidades en

los arcos.

Ahora presentaremos los pasos del algoritmo capacitado. Es esencial estar

familiarizado con el método simplex y la teoría de la dualidad (Capítulos 3 y 4). También

ayudará el conocimiento del método simplex con cota superior (Sección 7.3).


Paso 0. Determinar una solución inicial básica factible (conjunto de arcos) para la red. Ir

al paso 1.

Paso 1. Determinar un arco (variable) de entrada con la condición de optimalidad del

método simplex. Si la solución es óptima, detenerse. En caso contrario ir al paso 2.

Paso 2. Determinar el arco (variable) de salida usando la condición de factibilidad del

método simplex. Determinar la nueva solución y continuar en el paso 1.

Una red con n nodos y flujo neto cero (es decir,f1, +f2 + ...+fn=0) consiste en n-1

ecuaciones independientes de restricción. Así, una solución básica asociada debe incluir n

— 1 arcos. Se puede demostrar que una solución básica siempre corresponde a un árbol

de expansión de la red (véase la sección 6.2).

El arco entrante (paso 1) se determina calculando zij-cij los coeficientes objetivo, para

todos los arcos no básicos actuales (/, j). Si Zij-Cij≤ 0 para todas i y j, la base actual (es

decir, la que se tiene en este momento) es óptima. En caso contrario se selecciona el arco

no básico con la cij-cij más positivo para entrar en la base.

El cálculo de los coeficientes objetivo se basa en la dualidad, exactamente como se hizo

con el modelo de transporte (véase la sección 5.3.4). Al aplicar el programa lineal definido

en la sección 6.5.2, sea wi la variable dual asociada con la restricción del nodo i; entonces,

el problema dual (excluyendo las cotas superiores) es

Maximizar z =

sujeta a Wi –wj ≤ cij (I,j) Є A

wi de signo no restringido, i = 1,2,..., n

Según la teoría de la programación lineal,

wi- Wj = c¡j, para el arco básico (i, j)

Ya que por definición el programa lineal original (Sección 6.5.2) tiene una restricción

redundante, se puede asignar un valor arbitrario a una de las variables duales (compárese

con el algoritmo de transporte, sección 5.3). Por comodidad se iguala w1 = 0. A

continuación se resuelven las ecuaciones (básicas) w¡- w¡ = cij para determinar los valores

duales restantes. De acuerdo con el método 2 de la sección 4.2.3, se sabe que el

coeficiente objetivo de la xij, no básica es la diferencia entre el lado izquierdo y el lado

derecho de la restricción dual correspondiente al dual; es decir,


Zij-Cij= w¡ - wj - c¡j

El único detalle que resta es demostrar cómo se determina la variable de salida. Lo

haremos con un ejemplo numérico.

Una solución factible

Nro Camino Q CU CT1 2,5 30 1 302 1,2 10 2 203 2,3 30 2 604 3,5 30 8 2405 1,4 30 5 150

total 500Iteración 0.

Paso 0. Determinación de una solución inicial básica factible: El árbol de expansión

factible inicial de la figura 6.44 (indicado con arcos de línea llena) se obtiene por

inspección. En el caso normal se usa una técnica de variable artificial para llegar a

esa solución (véanse los detalles en Bazaraa et al., 1990, págs. 440-446).

FIGURA 6.44 Red para la iteración 0

Costo en la solución factible inicial

Nro Camino Cant CU CT1 1,3 10 7 702 2,3 50 2 1003 3,5 60 8 4804 1,4 30 5 150

Total 800Z12-c12=0-(-5)-3=2

Z25-c25= -5-(-15)-1=9


Z45-c45=-5-(-15)-4=6

El arco(2,5) llega a la costa superior en 30

Sustituir x25= 30-x52

Reducir tanto X23 como X53 en 30

En la figura 6.44, la solución básica factible consiste en los arcos (línea llena) (1, 3), (1,4),

(2, 3) y (3,5), con los flujos factibles de 10, 30,50 y 60 unidades, respectivamente. Esto

deja los arcos (línea interrumpida) (1, 2), (2, 5) y (4, 5) para representar a las variables no

básicas. La notación x(c) en los arcos indica que se asigna un flujo de x unidades a un

arco con capacidad c. Los valores predeterminados para x y c son 0 e oo,

respectivamente.

Iteración 1.

Paso 1. Determinación del arco entrante: Se obtienen los valores duales resolviendo

las ecuaciones básicas actuales

w, =0

wi-wj-cy para(i,j) básicas

Así se obtienen

Arco (1, 3): w1-w3=7, por consiguiente w3 = -7

Arco (1,4): w1 - w4 = 5, por consiguiente w4 = -5

Arco (2, 3): w2 - w3 = 2, por consiguiente w2 = -5

Arco (3, 5): w3 — w5 = 8, por consiguiente w5 = —15

Ahora se calculan z¡j - cij para las variables no básicas, como sigue:

Arco(l, 2) : w1 - w2 - c12 = 0 - (-5) -3 = 2

Arco (2, 5) : w2 - w5 - c25 = (-5) - (-15) - 1 = 9

Arco (4, 5) : w4 - w5 - cA5 = (-5) - (-15) -4 = 6

Por lo anterior, el arco (2, 5) entra a la solución básica

Paso 2. Determinación del arco saliente: En la figura 6.44 se ve que el arco (2,5) forma

un bucle con los arcos básicos (2, 3) y (3, 5). De acuerdo con la definición del

árbol de expansión, ya no se puede formar otro bucle. Como el flujo en el arco

nuevo (2, 5) debe aumentar, se ajusta el flujo en los arcos del bucle con una

cantidad igual, para mantener la factibilidad de la nueva solución. Para lograrlo se

identifica el flujo positivo (+) en el bucle, con la dirección del arco entrante (es

decir, de 2 a 5). A continuación se asignan (+) o (—) a los arcos restantes del


bucle, dependiendo de si el flujo en cada uno es en o contra la dirección del flujo

del arco entrante. Estas convenciones de signo se muestran en la figura 6.44.

La determinación de la cantidad máxima de flujo en el arco entrante (2, 5) se basa en

dos condiciones:

1. El flujo nuevo en los arcos básicos actuales del bucle no puede ser negativo.

2. El flujo nuevo en el arco entrante no puede exceder su capacidad.

La aplicación de la condición 1 indica que los flujos en los arcos (2, 3) y (3, 5) no

puede disminuir en más de mín{50, 60) =50 unidades. La condición 2 estipula que el flujo

en el arco (2, 5) puede aumentar cuando mucho hasta la capacidad del arco (= 30

unidades). Entonces, el cambio máximo de flujo en el bucle es mín{30, 50) =30 unidades.

Los nuevos flujos en el bucle son entonces 30 unidades en el arco (2,5), 50 - 30 = 20

unidades en el arco (2,3) y 60 - 30 = 30 unidades en el arco (3, 5).

Debido a que ninguno de los arcos básicos actuales sale de la base a nivel cero, el

nuevo arco (2, 5) debe permanecer no básico en la cota superior. Sin embargo, para no

manejar arcos no básicos que están en el valor de su capacidad (o cota superior) se

implementará la sustitución

x25 = 30 - x52, 0 < x52 < 30

Esta sustitución se hace en las ecuaciones de flujo asociadas con los nodos 2 y 5 como

sigue. Se tiene que:

Ecuación actual del flujo en el nodo 2: 50 + xi2 = x23 + x25

Ecuación actual del flujo en el nodo 5: x2i + xi5 + x45 = 60

Entonces, la sustitución x25 = 30 - x52 da como resultado:

Nueva ecuación del flujo en el nodo 2: 20 + xn + x52 = x23

Nueva ecuación del flujo en el nodo 5: x35 + x45 = x52 + 30

En la figura 6.45 se ven los resultados de estos cambios. La dirección de flujo en el

arco (2, 5) queda invertida ahora a 5 —> 2 con *52 = 0, que era lo que se quena. También

la sustitución requiere cambiar el costo unitario del arco (5, 2) a —$1. Indicaremos esta

inversión de dirección en la red, etiquetando el arco con un asterisco.

Iteración 2. La figura 6.45 resume los nuevos valores de zij-cij(¡compruébelos!) y

muestra que el arco (4,5) entra a la solución básica. También define al bucle asociado

con el nuevo arco entrante, y asigna signos a sus arcos.

El flujo en el arco (4, 5) se puede aumentar en la cantidad mínima de

1. El aumento máximo permisible en el arco entrante (4, 5) =∞


El aumento máximo permisible en el arco (1,4) = 35 - 30 = 5 unidades

Entra el arco (4,5) en el nivel 5.

Sale el arco (1.4) en la cota superior.

Sustituir x14 = 35 – x41

Reducir tanto xí3 como x35 en 5.

FIGURA 6.45 -Red para la iteración 1

3. La disminución máxima permisible en el arco (1,3)= 10 unidades

4. La disminución máxima permisible en el arco (3, 5) = 30 unidades

Así, el flujo en el arco (4, 5) se puede aumentar a 5 unidades, con lo cual (4, 5) será

básico y forzará a que el arco básico (1, 4) sea no básico en su cota superior (= 35).

Al usar la sustitución x14 = 35 - x4l, la red cambia como se ve en la figura 6.46, con los

arcos (1, 3), (2, 3), (3, 5) y (4, 5) formando la solución (árbol de expansión) básica. La

inversión del flujo en el arco (1,4) cambia su costo unitario a —$5. También, convénzase

el lector de que la sustitución en las ecuaciones de flujo de los nodos 1 y 4 agregara 5

unidades de entrada en cada nodo.

Z12-C12= = 0 - (-5)-3 = 2

Z41-c41=-11-0-(-5) =-6

Z52-c52=-15-(-5)-(-l) = -9

Entra el arco (1,2) en el nivel 5.


Sale el arco (1,3) en el nivel 0.

Aumentar 5 a x23.


Iteración 3. Los cálculos de las nuevas Zij-Cij para los arcos no básicos (1,2), (4, 1) y (5,2)

se resumen en la figura 6.46, que muestra que el arco (1, 2) entra al nivel 5 y el arco (1, 3)

se vuelve no básico al nivel 0. La nueva solución se ve en la figura 6.47.

Iteración 4. Las nuevas Zij-Cij de la figura 6.47 muestran que la solución es óptima. Los

valores de las variables originales se obtienen por sustitución en reversa, como se ve en la

figura 6.47.



Solucion óptima Nro Camino Q CU CT

1 1,4 35 5 1752 4,5 5 4 203 2,5 30 1 303 1,2 5 3 154 2,3 25 2 505 3,5 25 8 200

total 490Solución del problema con Tora como Problema de programación línea


Solución con Excel

Min z =3x12+ 7x13+5x14 +2x23 +1x25 +8x35+ 4x45

Sujeto aNodo 1 40 = x14+x13+x12 x14+x13+x12=40Nodo 2 x12+50=x23+x25 x12-x23-x25=-50 -x12+x23+x25=50Nodo 3 x13+x23=x35 x13+x23-x35=0Nodo 4 x14=30+x15 x14-x15=30Nodo 5 x45+x35+x25=60Capacidad arco x12 X12<=MCapacidad arco x13 X13<=10Capacidad arco x14 X14<=35Capacidad arco x23 X23<=60Capacidad arco x25 X25<=30Capacidad arco x35 X35<=MCapacidad arco x45 X45<=M


Otra forma


nombre Variable x12 x13 x14 x23 x25 X35 x45 Cant 5 0 35 25 30 25 5 costo minimo costos unitarios 3 7 5 2 1 8 4 490 Restricciones TOTAL = D/R H/Enodo 1 1 1 1 40 = 40 0.00nodo 2 -1 1 1 50 = 50 0.00nodo 3 1 1 -1 0 = 0 0.00nodo 4 1 -1 30 = 30 0.00nodo 5 1 1 1 60 = 60 0.00cap 13 1 0 <= 10 10.00cap 14 1 35 <= 35 0.00cap 23 1 25 <= 60 35.00cap 25 1 30 <= 30 0.00

FIGURA 6.49 Solución del ejemplo 6.5-4 con Solver de Excel


Problema de hiller

MODELO DEL AGENTE VIAJERO

El problema del viajante (también conocido como problema del viajante de comercio o

por sus siglas en inglés: TSP) es uno de los problemas más famosos (y quizás el mejor

estudiado) en el campo de la optimización combinatoria computacional. A pesar de la

aparente sencillez de su planteamiento, el TSP es uno de los más complejos de resolver y

existen demostraciones que equiparan la complejidad de su solución a la de otros

problemas aparentemente mucho más complejos que han retado a los matemáticos desde

hace siglos.

Enunciado

Sean N ciudades de un territorio. El objetivo es encontrar una ruta que, comenzando y

terminando en una ciudad concreta, pase una sola vez por cada una de las ciudades y

minimice la distancia recorrida por el viajante. Es decir, encontrar una permutación P =

{c0,c2,...,cn − 1} tal que sea mínimo. La distancia entre cada

ciudad viene dada por la matriz D: NxN, donde d[x, y] representa la distancia que hay

entre la ciudad X y la ciudad Y

La solución más directa es la que aplica la fuerza bruta: evaluar todas las posibles combinaciones de recorridos y quedarse con aquella cuyo trazado utiliza la menor distancia. El problema reside en el número de posibles combinaciones que viene dado por el factorial del número de ciudades (N!) y esto hace que la solución por fuerza bruta sea impracticable para valores de N incluso moderados con los medios computacionales actualmente a nuestro alcance. Por ejemplo, si un ordenador fuese capaz de calcular la longitud de cada combinación en un microsegundo, tardaría algo más 3 segundos en resolver el problema para 10 ciudades, algo más de medio minuto en resolver el problema para 11 ciudades y 77.146 años en resolver el problema para sólo 20 ciudades.Por ejemplo las rutas posibles entre 12 ciudades son 479.001.600 combinaciones y el número de caminos individuales entre ciudades es el sumatorio desde 1 hasta 12-1, es decir, 66.Video ejemplo

Distancias en km entre ciudades

0 1 2 3 4 50 0 10 6 8 7 151 0 5 20 15 162 0 14 7 83 0 4 124 0 6

http://es.wikipedia.org/wiki/Factorial

http://es.wikipedia.org/wiki/Permutaci%C3%B3n

http://es.wikipedia.org/wiki/Combinatoria


Solución en winqsb


Ejemplo Se tiene la siguiente matriz de distancias

De\a 0 1 2 3 4 50 0 10 6 8 7 151 10 0 5 20 15 162 6 5 0 14 7 83 8 20 14 0 4 124 7 15 7 4 0 65 15 16 8 12 6 0

ITERACION 1


ITERACION 2

ITERACION 3


ITERACION 4


Iter N S DIF COSTO KMIN DIS DE A 1 2 3 4 5

1 0 1,2,3,4,5 entra 2 0 2 10 6 8 7 15 0,2 1,3,4,5 2 12

2 0 7 10 8 7 15 1 2 5 5 0 14 7 8

3 Entra 1 0,210+5-6 9 21

4 0,1,2 3,4,5 4 0 7 8 7 153 1 15 20 15 16

2 7 14 7 8

entra 4 0,17+15-10 12

0,2 7+7-6 8

1,27+15-5 17

29 0,4,2,1 3,5 8 8 15 4 4 6 16 20 16 8 14 8 entra 3 0,4 8+4-7 5

4,24+14-7 11

2,114+20-5 29

0,18+20-10 18

0,3,4,2,1 34

solo queda 5

inserta 5 0,325+12-8 29

3,412+6-4 14

4,2 6+8-7 7

2,18+16-5 19

0,115+16-10 21

0,3,4,5,2,1,0 41


ITERACION 5

Algoritmo

1. Comenzar de un nodo ejemplo el nodo 02. Buscar la ciudad mas cercana al grupo de ciudades escogidos3. Insertar esa ciudad en la secuencia correspondiente buscando el menor costo

marginal

Solución con WIn QSB


EJERCICIO SOBRE REDES

Arbol de expansión mínima Algoritmo de Kruskal

1. Comenzar en forma arbitraria en cualquier nodo con el más próximo ( menos distante

o costos)

2. Identificar el nodo no conectado que este más cerca o menos costoso de alguno de

los nodos conectado, deshacer los empates de forma arbitraria. Agregar este nodo al

conjunto de nodos conectados

3. Repetir eso hasta que se hayan conectado todos los nodos


1. Un centro de computo (CRC) debe instalar líneas especiales para comunicaciones a fin

de conectar a cinco usuarios satélite con un nueva computadora central , la compañía

telefónica local es la que instalara la nueva red de comunicaciones pero es una

operación costosa

Con el propósito de reducir costos , se busca que la longitud total (km) de estas lineas

sea al menor posible. La red para este problema es la siguiente

Iteración nodos Distancia1 3,4 102 4,6 203 3,5 304 4,1 305 1,2 20

SUMA 110Método tabular

1 2 3 4 5 61 0 20 40 30 50 402 20 0 40 3 40 0 10 30 4 30 10 0 205 50 40 30 0 406 40 20 40 0

3 4 6 1 2 5


2. Encontrar la ruta mínima por el método de DijkStra y Floyd

3. Resolver con Solver de Excel

O\D 1 2 3 41 0 4 2 52 4 0 99 13 2 1 0 24 5 1 2 0

ASIG 1 2 3 4 DISP

1 0 0 1 0 1 12 0 1 0 1 2 23 0 1 1 0 2 24 0 0 0 0.00 0.00 0

TOTAL 0 2 2 1 REQ 0 2 2 1 COSTO TOTAL 4

6 Agente viajero


Philadelfia Paint Company produce cinco colores de pintura cada mes al cambiar de uno a otro color , la maquina mezcladora debe limpiarse y prepararse para el siguiente color .Este tiempo de disposicion depende del color que acaba de producirse y del color que producirá a continuación . Los tiempos de disposición al cambiar entre todas las parejas de colores se muestran en la tabla 9.29 como gerente de departamento de producción debe determinar la secuencia en la cual producir los 5 colores con el fin de minimizar el tiempo de disposición total.Podría ser primero naranja y luego cambiar a rojoDe\A BLANCO AMARILLO NARANJA ROJO NEGROBlanco 0 150 120 11 110Amarillo 170 0 110 90 100Naranja 200 170 0 80 100Rojo 220 190 100 0 90Negro 300 210 180 130 0Encuentre la ruta mas corta

Red de flujoDe Wikipedia, la enciclopedia libreSaltar a: navegación, búsqueda Entendiendo una red de flujo como un grafo dirigido, donde la fuente es quien produce o inicia el traspaso de algún material o producto por los arcos, estos últimos, vistos como caminos o conductos y tomando en cuenta la ley de corrientes de Kirchoff, donde, la suma de flujos entrantes a un vértice debe ser igual a la suma de flujos saliendo del vértice.

EJERCICIOS A RESOLVER EN LA PRACTICA DE LABORATORIO y EN AULA

9.1 EJEMPLO PROTOTIPO______________________________________En fecha reciente se reservó el área de SEERVADA PARK para paseos y campamentos. No se permite la entrada de automóviles, pero existe un sistema de caminos angostos con curvas para tranvías y "jeeps" conducidos por los guardabosques. La figura 9.1 muestra este sistema de caminos (sin las curvas), en donde O es la entrada al parque; las otras letras representan la localización de las casetas de los guardabosques (y otras instalaciones de servicio). Los números son las distancias en millas de estos caminos sinuosos.El parque contiene un mirador a un hermoso paisaje en la estación T. Unos cuantos tran-vías transportan a los visitantes desde la entrada a la estación T y de regreso.En este momento el administrador del parque se enfrenta a tres problemas. Uno consiste en determinar qué ruta, desde la entrada del parque a la estación T, es la que tiene la distancia total más corta para la operación de los tranvías. (Éste es un ejemplo del problema de la ruta más corta que se estudiará en la sección 9.3.)El segundo problema reside en que deben instalarse líneas telefónicas subterráneas para establecer comunicación entre todas las estaciones (incluso la entrada). Como la instalación es cara y perturba la ecología, se instalarán líneas que siguen sólo los caminos necesarios para obtener comunicación entre cualquier par de estaciones. La pregunta es por dónde deben tenderse las líneas para lograr esto con el mínimo número total de millas

http://es.wikipedia.org/wiki/V%C3%A9rtice_(Teor%C3%ADa_de_grafos)

http://es.wikipedia.org/wiki/Leyes_de_Kirchhoff

http://es.wikipedia.org/wiki/Grafo#Grafo_dirigido

http://es.wikipedia.org/wiki/Fuente

http://es.wikipedia.org/wiki/Grafo#Grafo_dirigido

http://es.wikipedia.org/wiki/Red_de_flujo#p-search

http://es.wikipedia.org/wiki/Red_de_flujo#mw-head


de cable instalado. (Éste es un ejemplo del problema del árbol de mínima expansión que se analizará en la sección 9.4.)

El tercer problema se refiere a que, durante la temporada pico, hay más personas que quieren tomar el tranvía a la estación T de las que se pueden acomodar. Para evitar la perturbación indebida de la ecología y de la vida silvestre de la región, se ha impuesto un racionamiento estricto en el número de viajes al día que pueden hacer los tranvías en cada camino. (Estos límites difieren entre los caminos, como se verá con detalle en la sección 9.5.) Así, durante la temporada pico, se pueden seguir varias rutas, sin tomar en cuenta la distancia, para aumentar el número de viajes de tranvía diarios. La pregunta es cómo planear las rutas para los distintos viajes, de manera que se maximice el número total de viajes que se pueden hacer al día, sin violar los límites impuestos sobre cada camino. (Este es un ejemplo del problema de flujo máximo que se presentará en la sección 9.5.)

REDES

Ver EL video de árbol de expansión mínima Pág. 3

Ver el algoritmo de árbol de expansión mínima Pág. 6


Resolver árbol de expansión mínima como problema de transporte con Solver de Excel

Pág. 7

Solución del problema de árbol de expansión mínima con programación lineal Pág. 8

Resolver con winqsb Pág. 11

Ejercicio de Kruskal Pág 12

Resolver árbol de expansión mínima con POMS 14

Modelo del Árbol de Extensión Mínima pag 19

Problema 3. Si dan las ubicaciones de 5 pueblos (sus coordenadas X,Y) si quiere unir

por cable o (construir caminos ) 5 pueblos cual seria la mínima longitud de cable

resolverlo con Excel Pág 21 y luego con WinQsb

Ver el Programa de árbol de expansión mínima con C++ y OpenGl Pág 23 y Visual C++

RUTA MAS CORTA

Video de algoritmo de dijkstra Pág. 35

Resolver con tora y WinQsb

Resolver algoritmo de dijksta pag 40 y resolverlo con tora y winqsb Pág. 44

Video de algoritmo de floyd Pág 48 y resolverlo con iteraciones con Excel y también con

Tora

Resolver el ejercicio de la Pág.52 algoritmo de Floyd paso a paso con Excel Pág. 57

Pruebe el programa en c++ para encontrar la ruta mas corta para el algoritmo de Floyd

El mismo programa como una función personalizada de Excel pag 61

Programa en C++ y OpenGL Pág.65

Determinación de la ruta mas corta con Excel Pág. 72

Ruta mas corta con Poms Pág. 79

Resolver el problema de video de ruta mas corta con Solver de Excel Pág. 80

Ver video de flujo máximo Pág 1

Ejemplo 6.4-2 calculo de flujo máximo iteraciones Pág 9

Solución de flujo máximo con WinQsb y POMS Pág. 14

Solución de flujo máximo paso a paso con Excel Pág. 15

Flujo máximo con C++ Pág.16 16

Resolver problema de Sunco Pág 19 como programaciónn lineal con Excel Pág. 20 probar

con Winqsb

4. Algoritmo de Ford-Fulkerson Pág.23

5. 4.3 Formulación del problema de flujo máximo con programación lineal Pág 25


6. Flujo máximo aplicado a balance de línea Pág 28

6.5 Problema de flujo capacitado con costo mínimo Pág. 31

Red capacitada para distribución de agua Pág.35

Solución con Excel Poms , Tora y Winqsb Pág.46

Modelo del agente viajero Pág 49.

Video ejemplo Pág 50 y su solución con WinQsb pág 51

Resolver el problema de Philadelfia Paint Company Pág. 58

Tarea

Porbelma de redes para resolver y para resolver en laboratorio

Parte casa

Rede de libro de lhiller

Transporte asignación

Percpm

Laboratorio

Árbol de extensin minimo

Ruta minima

Flujo máximo con Excel

Perct cpm

Aplicaciones de simplex y redes 2 aplicaciones por grupo

Practica del dia 20 de noviembre del 2012

io7 flujo maximo

Documents