sama


Flujo a Costo M¶³nimo
Queremos buscar una forma de distribuir °ujo por una red de modo de hacerlo al menor costo posible.
2.1. Simplex especializado a redes (Resumen)
Solución Básica, ¶ÁrbolGenerador.
cij = cij ¡ ¼i + ¼j ¼i; ¼j variables duales.
Condición de optimalidad:
Sean:
fij = Flujo por el arco ij.
lij = Cota m¶³nima para el °ujo por el arco ij.
uij = Cota máxima para el °ujopor el arco ij.
9=
; lij · fij · uij
Con esto las condiciones de optimalidad pueden resumirse como:
(1) cij = 0 8(i; j) basic.
(2) cij ¸ 0 8(i; j) no básico tal que fij = lij .
(3) cij · 0 8(i;j) no básico tal que fij = uij .
Luego, lo que tenemos que hacer es resolver (1) teniendo como incógnitas los ¼. Para
ello, requerimos asignar ¼r = 0 para algún r arbitrario. Con estos valores de ¼ivemos
si se cumplen las condiciones (2) y (3).
Variable que entra: (p,q) con máxima violación de optimalidad.
2Por ejemplo, hasta Abril de 1999, el clásico problema del vendedor viajero solo hab¶³asido resuelto para
13509 ciudades, lo cual demoro 4 meses en ser resuelto utilizando para ello 3 servidores, un total de 12
procesadores y 32 PCs.
IN34A: Optimizacion Pág. 2
Variable que sale: Alagregar el °ujo (p,q) en el ¶árbol generador formado por las
variables básicas, se formara un ciclo.
² Si fpq = lpq ) Aumentamos el °ujo por (p,q)
² Si fpq = upq ) Disminuimos el °ujo por (p,q)Luego se env¶³a °ujo hasta que:
i) Arco (r; s) en el sentido del °ujo se satura en cota superior urs ) (r; s) sale de la
base con valor urs.
ii) Arco (r; s) en el sentido contrario al °ujo alcanzala cota inferior lrs ) (r; s) sale
de la base con valor lrs.
iii) Arco (p; q) alcanza su otra cota)No hay cambio de base, solo cambian los valores
de los °ujos.
Notar que en cada iteración cambiantodos los valores de los °ujos que estaban involuta-
creados en la formación de un ciclo en el ¶árbol generador (recordar que siempre debe
cumplirse la restricción de conservación de °ujo en cada...