Redes Practica 05 W403 W405 W459 Ampl

Práctica 5A.
Problemas de Flujo Máximo, Winston página 403, ejemplo 3, formato 2.

ENUNCIAD0.

Sunco Oil quiere enviar (por hora) la máxima cantidad de petróleo por un oleoducto desde el nodo so al nodo si, el petróleo tiene que pasar por algunas, o por todas, las estaciones 1, 2 y 3. Los arcos de la Fig. 6 representan oleoductos de diferentes diámetros. En la Tabla 5 se muestra el máximo númerode barriles de petróleo (millones de barriles por hora) que se pueden bombear por cada arco. Cada uno de estos números se llama capacidad de arco. Plantee un PL que se pueda utilizar para determinar el máximo número de barriles de petróleo que se pueden mandar de so a si.




Arco Capacidad

(So,1) 2
(So,2) 3
(1,2) 3
(1,3) 4
(3,Si) 1
(2,Si) 2


Variables de decisión:

xij= millones de barrilesde petróleo que pasarán por hora por el arco i,j del oleoducto.

Para que un flujo sea factible, tiene que ocurrir:
0<= flujo a través de cada arco <= capacidad del arco
Flujo que entra en el nodo i = Flujo que sale del nodo i (salvo en nodos 1 y m)
X0= cantidad de petróleo que entra en el pozo.


Formulación:
Maximizar z =x0
s.a: Restricciones de capacidad:
X(So,1)<=2X(So,2)<=3
X(1,2)<=3
X(2,Si)<=2
X(1,3)<=4
X(3,Si)<=1
Restricciones de flujo:
X0= X(So,1) + X(So,2)
X(So,1)= X(1,2) + X(1,3)
X(1,2)= X(2,Si)
X(2,3)= X(3,Si)
X(3,Si) + X(2,Si) = X0

Formulación general:
Restricciones de los nodos intermedios:


Siendo (k,j), (i,j) un flujo factible

Restricción asociada al nodo fuente:

En este caso, el flujo máximo del nodo fuente sería 2Restricción asociada al nodo pozo:




Resolución por AMPL

Fichero Prac5A.mod

### Práctica 5A
# Problema del libro de Winston, página 402.
# Problema de Flujo máximo con formato 2.
# Fichero prac5A.mod

param m;

set NODOS:=1..m;
set ARCOS within {NODOS,NODOS};

param cota_sup {ARCOS}; # Flujo q puede pasar como máximo por los arcos

var x {(i,j) in ARCOS}>=0,<=cota_sup[i,j]; # Representa q x el nodotiene que pasar mas de 0 y menos de cota_sup
var flujo_max;

# Funcion objetivo
maximize objetivo: flujo_max;

# Restricciones asociadas a los nodos intermedios
subject to res_trasbordo{k in NODOS: k>1 and k (sum{(k,j) in ARCOS} x[k,j])-(sum{(i,k) in ARCOS} x[i,k])=0;

# Restricciones asociadas al nodo 1
subject to res_nodo_1: sum{(i,j) in ARCOS: i=1} x[1,j]=flujo_max;

# Restriccionesasociadas al nodo ultimo
subject to res_nodo_m: sum{(i,j) in ARCOS: j=m} x[i,m]=flujo_max;

Fichero Prac5A.dat

### Practica 5A
# Problema del libro de Winston, página 402.
# Problema FLUJO máximo con formato 2.
# Fichero practica5A.dat

param m:=5;

param: ARCOS: cota_sup:=
1 2 2
1 3 3
2 3 3
2 4 4
3 5 2
4 5 1;








Fichero Prac5A.run

### Práctica 5A
# Problema dellibro de Winston, página 402.
# Problema de Flujo máximo con formato 1.
# Fichero prac5b.run

reset;
model F:\Redes\prac5a.mod;
data F:\Redes\prac5a.dat;
option solver cplex;
solve;
display objetivo;
display x;

Salida por pantalla

CPLEX 8.0.0: optimal solution; objective 3
2 dual simplex iterations (1 in phase I)
objetivo = 3

x :=
1 2 2
1 3 1
2 3 1
2 4 1
3 5 2
4 5 1
;
Práctica 5B.Problemas de Flujo Máximo, Winston página 405, ejemplo 5, formato 2.

ENUNCIAD0.

Cinco actores y cinco actrices se encuentran en un baile. La meta del organizador es juntar a cada mujer con un hombre de manera que se maximice el número de personas que son compatibles. En la Tabla 7 se describe la compatibilidad de los actores. Dibuje una red que permita presentar el problema de maximizar elnúmero de parejas compatibles como un problema de flujo máximo.


Loni Meryl Katharine Linda Victoria
Anderson Streep Hepburn Evans Principal
Kevin Costner ----- C ----- ----- -----
Burt Reynolds C ----- ----- ----- -----
Tom Selleck C C ----- ----- -----
Michael Jackson C C ----- ----- C
Tom Cruise ----- ----- C C C








Formulación:

Xij= el hombre i está emparejado con la mujer...

Leer documento completo

Regístrate para leer el documento completo.