• Author / Uploaded
• Daniel Diaz Torres

• Categories
• La investigación de operaciones
• Vector Euclidiano
• Matriz (Matemáticas)
• Archivo de computadora
• Sistema de coordenadas Cartesianas

Citation preview

Departamento de Estadística e Investigación Operativa

Universidad de Valladolid

Notas sobre el programa AMPL (Notas 2: dirigidas a los alumnos de 2º curso) Índice

Parte I: Conjuntos. 1. Conjuntos simples e índices. 2. Conjuntos de pares ordenados. 3. Algunas formas de dar una matriz. 4. Conjuntos de n-uplas. 5. Expresiones. 6. Ejercicios.  Del problema del transporte.  Del problema de la dieta.  Del problema de producción.  Del problema de flujo con coste mínimo.  Del problema del camino más corto.  Del problema de flujo máximo. Parte II. Otros comandos. 1. El comando LET. 2. El comando FOR. 3. Ejercicios.  Del problema del CPM.  Del problema del PERT. 4. Otros ejercicios. Parte III. El problema del transporte. Algunas alternativas. Parte IV: El problema del transporte con cotas Parte V: El problema de flujo con coste mínimo. Parte VI: El problema de la mochila.

Fichero AMPL-2010-11-02.doc

Página 1 de 37

Departamento de Estadística e Investigación Operativa

Universidad de Valladolid

Parte I: Conjuntos. Para lo que sigue puede ser útil disponer de ficheros en los que se dan ejemplos de modelos concretos ya elaborados. En la página de www.ampl.com se dispone de algunos ejemplos en “Examples from the AMPL book”. Para descargarlos, seguir uno de los siguientes procedimientos: A. Primero:  En la parte alta pinchar en BOOK.  El la columna de la izquierda pinchar en examples.  Pinchar en by filename. B. Segundo de búsqueda:  En la parte alta pinchar en EXAMPLES.  En el apartado “Examples from the AMPL book” pinchar en by filename. Nota: Para las explicaciones que siguen es útil repasar el Problema del transporte ya que se adapta muy bien a las necesidades asociadas.

1. Conjuntos simples e índices. A. Conjuntos simples definidos explícitamente. El tipo más sencillo de conjunto está definido explícitamente mediante sus elementos como sucesión de caracteres. Así podemos definir en el archivo .mod dos conjuntos mediante las declaraciones: set ORIGENES; set DESTINOS; y en el archivo de datos ( xxx.dat) especificar sus elementos del siguiente modo: set ORIGENES:= orig1 orig2 orig3 ; set DESTINOS:= dest1,dest2,dest3,dest4; Esta forma de definición de conjuntos suele hacerse sólo para conjuntos pequeños, donde, además, se quiere conservar el nombre de los elementos. (Nota: En este caso, la especificación de los datos también puede hacerse en el fichero .mod). B. Conjuntos simples definidos implícitamente. Índices. Los tipos de conjuntos más utilizados son los conjuntos de números, y generalmente van a corresponder a los conjuntos de índices de un modelo. Por ejemplo, para definir un conjunto de 12 elementos con nombre orígenes, basta declarar: set ORIGENES:= 1..12; Aunque la anterior declaración es válida, es más conveniente declarar en el modelo de la forma: param m; set ORIGENES:= 1..m; y en el fichero de datos especificar: param m:=12; De esta forma se logra una separación más efectiva entre el modelo y los datos. (Nota: En este caso, la especificación de los datos también puede hacerse en el fichero .mod). Nota: Cuando en la definición de un conjunto interviene un periodo distinto de 1, esto puede indicarse mediante la cláusula by, indicando el periodo. Por ejemplo, en lugar de poner: set QUINQUENIOS:={1990, 1995, 2000, 2005, 2010, 2015, 2020}; es más conveniente poner: set QUINQUENIOS:=1990..2020 by 5;

2. Conjuntos de pares ordenados. A partir de conjuntos simples es posible formar conjuntos compuestos. El más sencillo de todos ellos es el producto cartesiano o conjunto de pares ordenados. Es útil para manejar matrices de datos como cij o variables con dos índices como xij. Hay varias formas de manejar tales situaciones.

Fichero AMPL-2010-11-02.doc

Página 2 de 37

Departamento de Estadística e Investigación Operativa

Universidad de Valladolid

A. Forma implícita completa sin nombre (se consideran todos los pares ordenados): no se da nombre explícitamente al nuevo conjunto, pero se definen parámetros o variables sobre dicho conjunto. Por ejemplo: param coste {ORIGENES,DESTINOS}>=0; # indica el coste unitario del transporte var flujo {ORIGENES,DESTINOS}>=0; # indica la cantidad a transportar Este método se usa en el ejemplo que más adelante veremos. B. Forma explícita completa con nombre (se consideran todos los pares ordenados): se da nombre explícitamente al nuevo conjunto y, en su caso, se definen parámetros o variables sobre dicho conjunto. Por ejemplo: set RUTAS:={ORIGENES, DESTINOS}; param coste {RUTAS}>=0; # indica el coste unitario del transporte var flujo {RUTAS}>=0; # indica la cantidad a transportar C. Forma explícita incompleta (no se consideran todos los pares ordenados): se da nombre explícitamente al nuevo conjunto y, en su caso, se definen parámetros o variables sobre dicho conjunto. Por ejemplo: set RUTAS within {ORIGENES, DESTINOS}; param coste {RUTAS}>=0; # indica el coste unitario del transporte var flujo {RUTAS}>=0; # indica la cantidad a transportar Más adelante, en el fichero de datos se explicitará quienes son los elementos del conjunto RUTAS.

3. Algunas formas de dar una matriz. A. Usando A del apartado anterior y el formato1. # fichero matriz_sin_f1.mod # usamos el formato 1 param m; param n; set FILAS:=1..m; set COLUMNAS:=1..n; param valores_matriz{FILAS,COLUMNAS};

# fichero matriz_sin_f1.dat param m:=3; param n:=4; param 1 1 5 2 5 3 6

valores_matriz: 2 3 4:= 2 3 8 8 9 11 7 3 12;

# fichero matriz_sin_f1.run # include D:\users\redes\matriz_sin_f11.run; reset; model D:\users\redes\matriz-sin_f1.mod; data D:\users\redes\matriz_sin_f1.dat; option solver cplex; solve; display valores_matriz;

Resultado valores_matriz := 11 5 12 2 13 3 14 8

Fichero AMPL-2010-11-02.doc

Página 3 de 37

Departamento de Estadística e Investigación Operativa

21 22 23 24 31 32 33 34 ;

Universidad de Valladolid

5 8 9 11 6 7 3 12

B. Usando A del apartado anterior y el formato2. # fichero matriz_sin_f2.mod # usamos el formato 2 set FILAS; set COLUMNAS; param valores_matriz{FILAS,COLUMNAS}; # fichero matriz_sin_f2.dat # usamos el formato 2 set FILAS:= fila1 fila2 fila3; set COLUMNAS:= col1 col2 col3 col4; param valores_matriz: col1 col2 col3 col4:= fila1 5 2 3 8 fila2 5 8 9 11 fila3 6 7 3 12; # fichero matriz_sin_f2.run # usamos el formato 2 # include D:\users\redes\matriz_sin_f2.run; reset; model D:\users\redes\matriz_sin_f2.mod; data D:\users\redes\matriz_sin_f2.dat; option solver cplex; solve; display valores_matriz;

Resultado valores_matriz := valores_matriz := fila1 col1 5 fila1 col2 2 fila1 col3 3 fila1 col4 8 fila2 col1 5 fila2 col2 8 fila2 col3 9

Fichero AMPL-2010-11-02.doc

Página 4 de 37

Departamento de Estadística e Investigación Operativa

fila2 col4 fila3 col1 fila3 col2 fila3 col3 fila3 col4 ;

Universidad de Valladolid

11 6 7 3 12

C. Usando B del apartado anterior y el formato1. # fichero matriz_con_f1.mod # usamos el formato 1 param m; param n; set FILAS:=1..m; set COLUMNAS:=1..n; set MATRIZ:={FILA, COLUMNAS}; param valores_matriz{MATRIZ}; Los ficheros .dat y punto run son los dados en A de este apartado.

D. Usando B del apartado anterior y el formato2. # fichero matriz_con_f1.mod # usamos el formato 1 set FILAS; set COLUMNAS; set MATRIZ:={FILA, COLUMNAS}; param valores_matriz{FILAS,COLUMNAS}; Los ficheros .dat y punto run son los dados en B de este apartado.

E. Usando una descripción de la matriz como un conjunto de filas, donde cada columna es un parámetro sobre el conjunto de las filas. # fichero matriz3.mod set FILAS; param colum1{FILAS}; param colum2{FILAS}; param colum3{FILAS}; param colum4{FILAS}; # fichero matriz3.dat param:

FILAS: fila1 fila2 fila3

colum1 5 5 6

colum2 2 8 7

colum3 3 9 3

colum4:= 8 11 12;

# fichero matriz3.run # include D:\users\redes\matriz3.run; reset; model D:\users\redes\matriz3.mod; data D:\users\redes\matriz3.dat; # option solver cplex; # solve; printf"\n"; display colum1, colum2, colum3, colum4; Resultado : fila1 fila2 fila3

colum1 5 5 6

colum2 2 8 7

Fichero AMPL-2010-11-02.doc

colum3 3 9 3

colum4 8 11 12;

:=

Página 5 de 37

Departamento de Estadística e Investigación Operativa

Universidad de Valladolid

F. Usando una descripción de la matriz como un conjunto de columnas donde cada fila es un parámetro sobre el conjunto de las columnas. # fichero matriz4.mod set COLUMNAS; param fila1{COLUMNAS }; param fila2{ COLUMNAS }; param fila3{ COLUMNAS }; # fichero matriz4.dat param:

COLUMNAS: colum1 colum2 colum3 colum4

fila1 5 2 3 8

fila2 5 8 9 11

fila3:= 6 7 3 12;

# fichero matriz4.run # include D:\users\redes\matriz4.run; reset; model D:\users\redes\matriz4.mod; data D:\users\redes\matriz4.dat; # option solver cplex; # solve; printf"\n"; display fila1, fila2, fila3;

Resultado : fila1 colum1 5 colum2 2 colum3 3 colum4 8 ;

fila2 5 8 9 11

fila3 := 6 7 3 12

4. Conjuntos de n-uplas. De la misma forma que para pares, pueden definirse parámetros y variables con tres o más índices, definiendo primero los conjuntos simples y después el producto cartesiano. Así, por ejemplo, si se han definido tres conjuntos con nombres PRODUCTOS, PERIODOS y METODOS, y queremos definir una variable con tres índices xijk basta poner: var x {PRODUCTOS, PERIODOS,METODOS,}>=0; y del mismo modo para los parámetros.

5. Parámetros y expresiones. Los datos de un modelo se introducen en este mediante su declaración como parámetros. Son posibles varias situaciones: A. Parámetros unidimensionales. Basta una declaración del tipo: param m; B. Parámetros vectoriales. Se asocian a conjuntos simples. Si DESTINOS es un conjunto simple, basta una declaración del tipo: param demanda {DESTINOS}; Una alternativa válida es poner: param demanda {i in DESTINOS}; C. Parámetros matriciales. Se asocian a conjuntos de pares ordenados. Si RUTAS es un conjunto de pares ordenados, basta una declaración del tipo: param coste {RUTAS}; Alternativas válidas son: param coste {(i,j) in RUTAS};

Fichero AMPL-2010-11-02.doc

Página 6 de 37

Departamento de Estadística e Investigación Operativa

Universidad de Valladolid

param coste {i in ORIGENES , j in DESTINOS}; En este último caso se supone que ORIGENES y DESTINOS son conjuntos simples. Restricciones sobre parámetros. Cuando se declara un parámetro pueden añadirse restricciones sobre el mismo para que AMPL rechace valores inadecuados que puedan asignársele. Así, pueden declararse parámetros de la forma: param N>1, integer; param demanda {DESTINOS}>=0; param cota_sup{i in ORIGENES, j in DESTINOS}>=cota_inferior[i,j]; (en este último caso se supone que ya se conoce el parámetro cota_inferior declarado sobre el producto cartesiano {ORIGENES, DESTINOS}).

Parámetros calculados. Normalmente, los parámetros son datos cuyos valores son especificados en el archivo de datos (es decir, en el archivo .dat) mediante el símbolo :=. Sin embargo, en algunas ocasiones hay parámetros que son calculados en el mismo modelo a partir de otros parámetros. Así, por ejemplo, si conocemos ya los datos asociados a dem[j] para cada valor de j en el conjunto PRODUCTOS, podemos declarar el nuevo parámetro: param suma_total := sum{j in PRODUCTOS} dem[j]; Expresiones. Para la construcción de modelos de optimización un operador muy utilizado es sum, que suma cierta expresión cuando se recorre los elementos de un conjunto, y corresponde a los sumatorios en modelos matemáticos. Así se pueden usar expresiones del tipo: sum {i in ORIGENES} oferta[i]; sum {j in DESTINOS} demanda [j]; sum {(i,j) in RUTAS} coste[i,j]; sum {i in ORIGENES, j in DESTINOS} coste[i,j]; Dos puntos (ver libro de AMPL (1993, p. 141, lin. -11). Detrás del comando param se ponen dos puntos para indicar: (i) que a continuación se van a varios parámetros (más de uno). (ii) el nombre de un conjunto. En este caso, detrás del nombre del conjunto se ponen dos puntos para indicar que detrás van los parámetros. Detrás de un parámetro matricial se ponen dos puntos (ver el problema del transporte).

6. Ejercicios sobre la teoría anterior. Ver: A. El problema del transporte (Winston(n) p. 360). B. El problema de la dieta (Winston p. ¿79?). C. El problema de flujo con coste mínimo (Winston(n) p. 450 y 466). D. El problema del camino más corto (Winston(n) p. 414). E. El problema de flujo máximo (Winston(n) p. 419).

Fichero AMPL-2010-11-02.doc

Página 7 de 37

Departamento de Estadística e Investigación Operativa

Universidad de Valladolid

Parte II: Otros comandos 1. El comando LET. A. Sirve para asignar o cambiar el valor de un parámetro ya declarado. B. Ejemplo para un parámetro simple. param a; let a:=5; display a; let a:=10; C. Ejemplo para un parámetro vectorial. Supongamos que se tiene declarado el conjunto DESTINOS y sobe el mismo los parametros oferta y demanda. Conocido este último, podemos poner: let {i in DESTINOS} ofera[i]:=demanda[i];

2. El comando FOR. A. Sirve para ejecutar repetidamente una serie de comandos (bucle) que se escribe entre llaves, es decir, en la forma {serie de comandos}. B. Ejemplo sencillo. for {i in 1..n} {serie de comandos}. C. Ejemplo si se tiene un conjunto simple cualquiera, llamémosle CONTADOR. for {i in CONTADOR} {serie de comandos}. D. Ejemplo más complejo. Supongamos que en un modelo hay un parámetro llamado tasa y queremos resolver el modelo para los siguientes valores de tasa: 8, 9, 10, 11 y 12. Puede hacerse lo siguiente: set VALORES:= 8 9 10 11 12; for {t in VALORES} {let tasa:=t; solve; display; }

3. Ejercicios. En la página Web del profesor pueden verse ejemplos sobre el problema del CPM y del PERT.

Fichero AMPL-2010-11-02.doc

Página 8 de 37

Departamento de Estadística e Investigación Operativa

Universidad de Valladolid

Parte III: El problema del transporte. Algunas alternativas. Algunas alternativas para expresar el problema del transporte por medio de cambios en los ficheros .mod y .dat, sin cambios significativos en los ficheros .run.

El problema del transporte (ver Winston(n) p. 360). m

Minimizar

z 

n

 c x

ij ij

i 1 j 1 n

sujeta a :

x



si

para i  1,..., m

x

 dj

para j  1,..., n

ij

j 1 m

ij

i 1

xij



0

para i  1,..., m, j  i,..., n

ALTERNATIVA 1 (formato 1). Nota: 1. Se dan nombres literarios a los conjuntos primitivos. 2. No se da nombre explícitamente al conjunto derivado (producto cartesiano). 1. Se dan nombres numéricos a los elementos de los conjuntos primitivos usando el comando param.

Fichero trans1.mod param m; param n;

# m es el número de orígenes # n es el número de destinos

set ORIGENES:=1..m; set DESTINOS:=1..n; param oferta{ORIGENES}>=0; param demanda{DESTINOS}>=0; param coste{ORIGENES,DESTINOS}>=0;

# ofertas es el vector de ofertas o disponibilidades (si). # demandas es el vector de demandas o requerimientos (dj) # costes es la matriz de costes unitarios (cij)

var flujo{ORIGENES,DESTINOS}>=0;

# flujo es la matriz de variables de decisión (xij)

check: sum{i in ORIGENES} oferta[i] >= sum {j in DESTINOS} demanda[j] ; minimize coste_total: sum {i in ORIGENES,j in DESTINOS} coste[i,j]*flujo[i,j]; # función objetivo subject to res_oferta{i in ORIGENES}: sum{j in DESTINOS}flujo[i,j] = demanda[j]; # restricciones asociadas a la demanda en cada destino

Fichero AMPL-2010-11-02.doc

Página 9 de 37

Departamento de Estadística e Investigación Operativa

Universidad de Valladolid

Fichero trans1.dat param m:=3; param n:=4; param oferta:= 1 35 2 50 3 40; param demanda:= 1 45 2 20 3 30 4 30; param coste: 1 2 1 8 6 2 9 12 3 14 9

3 10 13 16

4:= 9 7 5;

ALTERNATIVA para param coste: param coste:= 1 1 8 1 2 6 1 3 10 1 4 9 2 1 9 2 2 12 2 3 13 2 4 7 3 1 14 3 2 9 3 3 16 3 4 5; Fichero trans1.run reset; model D:\trans1.mod; data D:\trans1.dat; option solver cplex; solve; display coste_total; display flujo;

NOTA: Todos los ficheros . run necesarios para las alternativas que siguen son análogos al trans1.run cambiando coherentemente los ficheros .mod y .dat.

Fichero AMPL-2010-11-02.doc

Página 10 de 37

Departamento de Estadística e Investigación Operativa

Universidad de Valladolid

ALTERNATIVA 2 (formato 2). Nota: 1. Se dan nombres literarios a los conjuntos primitivos. 2. No se da nombre explícitamente al conjunto derivado (producto cartesiano). 3. Se dan nombres literarios a los elementos de los conjuntos primitivos. Fichero trans2.mod set ORIGENES; set DESTINOS; param oferta{ORIGENES}>=0; # ofertas es el vector de ofertas o disponibilidades (si). param demanda{DESTINOS}>=0; # demandas es el vector de demandas o requerimientos (dj) param coste{ORIGENES,DESTINOS}>=0; # costes es la matriz de costes unitarios (cij) var flujo{ORIGENES,DESTINOS}>=0;

# flujo es la matriz de variables de decisión n (xij)

check: sum{i in ORIGENES} oferta[i] >= sum {j in DESTINOS} demanda[j] ; minimize coste_total: sum {i in ORIGENES,j in DESTINOS} coste[i,j]*flujo[i,j]; # función objetivo subject to res_oferta{i in ORIGENES}: sum{j in DESTINOS}flujo[i,j] = demanda[j]; # restricciones asociadas a la demanda en cada destino Fichero trans2.dat #datos del problema de Winston p. 337 param: ORIGENES: oferta:= oporto 35 lisboa 50 faro 40; param: DESTINOS: demanda:= barcelona 45 valencia 20 murcia 30 almeria 30; param coste: barcelona valencia murcia oporto 8 6 10 lisboa 9 12 13 faro 14 9 16

almeria := 9 7 5;

ALTERNATIVA para param coste: param coste:= oporto barcelona 8 oporto valencia 6 oporto murcia 10 oporto almeria 9 lisboa barcelona 9 lisboa valencia 12 lisboa murcia 13 lisboa almeria 7 faro barcelona 14 faro valencia 9 faro murcia 16 faro almeria 5;

Fichero AMPL-2010-11-02.doc

Página 11 de 37

Departamento de Estadística e Investigación Operativa

Universidad de Valladolid

ALTERNATIVA 3 Nota: 1. Se dan nombres literarios a los conjuntos primitivos. 2. No se da nombre explícitamente al conjunto derivado (producto cartesiano). 3. Se dan nombres numéricos a los elementos de los conjuntos primitivos sin usar el comando param. Fichero trans3.mod Es igual al fichero trans2.mod. Fichero trans3.dat param: ORIGENES: oferta:= 1 35 2 50 3 40; param: DESTINOS: demanda:= 1 45 2 20 3 30 4 30; param coste: 1 2 3 4:= 1 8 6 10 9 2 9 12 13 7 3 14 9 16 5;

ALTERNATIVA 4 Nota: 1. Se dan nombres literarios a los conjuntos primitivos. 2. Se da nombre literario al conjunto derivado (producto cartesiano). 3. Se dan nombres numéricos a los elementos de los conjuntos primitivos usando el comando param. Fichero trans4.mod param m; # m es el número de orígenes param n; # n es el número de destinos set ORIGENES:=1..m; set DESTINOS:=1..n; set RUTAS:={ORIGENES,DESTINOS}; # alternativa set RUTAS:=ORIGENES cross DESTINOS ; param oferta{ORIGENES}>=0; param demanda{DESTINOS}>=0; param coste{RUTAS}>=0;

# ofertas es el vector de ofertas o disponibilidades (si). # demandas es el vector de demandas o requerimientos (dj) # costes es la matriz de costes unitarios (cij)

var flujo{RUTAS}>=0;

# flujo es la matriz de variables de decisión (xij)

check: sum{i in ORIGENES} oferta[i] >= sum {j in DESTINOS} demanda[j] ; minimize coste_total: sum {(i,j) in RUTAS} coste[i,j]*flujo[i,j];

# función objetivo

subject to res_oferta{i in ORIGENES}: sum{j in DESTINOS}flujo[i,j] = demanda[j]; # restricciones asociadas a la demanda en cada destino Fichero trans4.dat Es iguala al fichero trans1.dat

Fichero AMPL-2010-11-02.doc

Página 12 de 37

Departamento de Estadística e Investigación Operativa

Universidad de Valladolid

ALTERNATIVA 5. Nota: 1. Se dan nombres literarios a los conjuntos primitivos. 2. Se da nombre literario al conjunto derivado (producto cartesiano). 3. Se dan nombres literarios a los elementos de los conjuntos primitivos. Fichero trans5.mod set ORIGENES; set DESTINOS; set RUTAS:={ORIGENES,DESTINOS};

# alternativa set RUTAS:=ORIGENES cross DESTINOS ;

param oferta{ORIGENES}>=0; param demanda{DESTINOS}>=0; param coste{RUTAS}>=0;

# ofertas es el vector de ofertas o disponibilidades (si). # demandas es el vector de demandas o requerimientos (dj) # costes es la matriz de costes unitarios (cij)

var flujo{RUTAS}>=0;

# flujo es la matriz de variables de decisión n (xij)

check: sum{i in ORIGENES} oferta[i] >= sum {j in DESTINOS} demanda[j] ; minimize coste_total: sum {(i,j) in RUTAS} coste[i,j]*flujo[i,j];

# función objetivo

subject to res_oferta{i in ORIGENES}: sum{j in DESTINOS}flujo[i,j] = demanda[j]; # restricciones asociadas a la demanda en cada destino

Fichero trans5.dat Es igual al fichero trans2.dat

ALTERNATIVA 6. Nota: 1. Se dan nombres literarios a los conjuntos primitivos. 2. Se da nombre literario al conjunto derivado (producto cartesiano). 3. Se dan nombres numéricos a los elementos de los conjuntos primitivos sin usar el param.

Fichero trans6.mod Es igual al fichero trans2.mod.

Fichero trans6.dat Es igual al fichero trans3.dat.

Fichero AMPL-2010-11-02.doc

Página 13 de 37

Departamento de Estadística e Investigación Operativa

Universidad de Valladolid

ALTERNATIVA 7 Nota: 1. Se dan directamente nombres numéricos a los conjuntos primitivo. 2. Se da directamente nombre numérico al conjunto primitivo. 3. Se usan los parámetros m y n para expresar directamente los elementos de los conjuntos primitivos 4. Se usan los parámetros m y n para expresar directamente los elementos del conjunto derivado (producto cartesiano). Fichero trans7.mod param m; param n;

# m es el número de orígenes # n es el número de destinos

param oferta{1..m}>=0; # ofertas es el vector de ofertas o disponibilidades (si). param demanda{1..n}>=0; # demandas es el vector de demandas o requerimientos (dj) param coste{1..m,1..n}>=0; # costes es la matriz de costes unitarios (cij) var flujo{1..m,1..n}>=0;

# flujo es la matriz de variables de decisión n (xij)

check: sum{i in 1..m} oferta[i] >= sum {j in 1..n} demanda[j] ; minimize coste_total: sum {(i,j) in {1..m,1..n}} coste[i,j]*flujo[i,j]; # función objetivo # alternativa sum {i in 1..m, j in 1..n} coste[i,j]*flujo[i,j]; # función objetivo subject to res_oferta{i in 1..m}: sum{j in 1..n}flujo[i,j] = demanda[j]; # restricciones asociadas a la demanda en cada destino # Nota: en lugar de {i in 1..m} o {j in 1..n} vale {i in {1..m}} o {j in {1..n}} Fichero trans7.dat Es igual al fichero trans3.dat Fichero trans7.run Es análogo al trans1.run cambiando coherentemente los ficheros .mod y .dat.

RESUMEN

1 2 3 4 5 6 7

¿Se dan nombres literarios a los conjuntos primitivos? SI SI SI SI SI SI NO

Fichero AMPL-2010-11-02.doc

¿Se da nombre literario al conjunto derivado? NO NO NO SI SI SI NO

Los elementos de los conjuntos primitivos son Numéricos usando param Literarios Numéricos sin usar param Numéricos sin param Numéricos con param Numéricos usando param

Página 14 de 37

Departamento de Estadística e Investigación Operativa

Universidad de Valladolid

Parte IV: El problema del transporte con cotas m

Minimizar

z



 c x ij

i 1

sujeta a :

n ij

j 1 n

x



si

para i  1,..., m

x

 dj

para j  1,..., n

xij

 uij

para i  1,..., m, j  i,..., n

ij

j 1 m

ij

i 1

lij



ALTERNATIVA 1 (paralela a la Alternativa 3 de la Parte III). Fichero trans-c1.mod Nota: 1. Se dan nombres literarios a los conjuntos primitivos. 2. Se da nombre literarios al conjunto derivado (producto cartesiano). 3. Se dan nombres numéricos a los elementos de los conjuntos primitivos y se usa la instrucción param. 4. Las cotas se definen como restricciones funcionales sobre las variables. param m; # m es el número de orígenes param n; # n es el número de destinos set ORIGENES:=1..m; set DESTINOS=1..n; set RUTAS:={ORIGENES,DESTINOS}; # alternativa set RUTAS:=ORIGENES cross DESTINOS ; param oferta{ORIGENES}>=0; # ofertas es el vector de ofertas o disponibilidades (si). param demanda{DESTINOS}>=0; # demandas es el vector de demandas o requerimientos (dj) param coste{RUTAS}>=0; # costes es la matriz de costes unitarios (cij) param cota_inf{RUTAS}; # cota inferior de la variable flujo (lij =0; # costes es la matriz de costes unitarios (cij) param cota_inf{RUTAS}; # cota inferior de la variable flujo (lij = cota_inf[i,j], = sum {j in DESTINOS} demanda[j] ; minimize coste_total: sum {(i,j) in RUTAS} coste[i,j]*flujo[i,j];

# función objetivo

subject to res_oferta{i in ORIGENES}: sum{j in DESTINOS}flujo[i,j] = demanda[j]; # restricciones asociadas a la demanda en cada destino

Fichero trans-c2.dat Es igual al fichero Fichero trans-c1.dat

Nota: con ligeros cambios es posible obtener otras 6 alternativas paralelas a las dadas en la Parte III.

Fichero AMPL-2010-11-02.doc

Página 17 de 37

Departamento de Estadística e Investigación Operativa

Universidad de Valladolid

Parte V: El problema de flujo con coste mínimo. Problema de flujo con coste mínimo (PFCM). Ver Winston edición (2005) página 466 Fig. 66. DESCRIPCIÓN DEL PROBLEMA Teniendo en cuenta las referencias anteriores, se considera la red de la Figura 1 con: (i) Ofertas sobre los nodos dadas en la Tabla 1. (ii) Costes y cotas superiores dados en la Tabla 2. Se pide: (a) Formular el correspondiente problema de flujo con coste mínimo. (b) Usando AMPL resolver el problema formulado.

Figura 1

4 2

7

1

5 8

3 6 Tabla 1 Nodos 1 2 3 4 5 6 7 8

Fichero AMPL-2010-11-02.doc

Demandas 100 0 0 0 0 0 -25 -75

Página 18 de 37

Departamento de Estadística e Investigación Operativa

Universidad de Valladolid

Tabla 2 Arcos (1,2) (1,3) (2,3) (2,4) (2,5) (2,6) (3,5) (3,6) (4,7) (4,5) (5,7) (5,8) (6,7) (6,8) (7,8)

Costes ($) 15 10 5 10 10 5 25 8 45 30 10 10 30 15 45

Cotas 75 50 40 30 50 30 40 60 100 60 40 40 50 80 100

FORMULACIÓN MATEMÁTICA DEL PROBLEMA 

Variables de decisión: xij = número de unidades de flujo enviadas desde el nodo i al nodo j a través del arco (i,j).



Función objetivo: Minimizar z = 15x12 + 10 x13 + 5 x23 + 10 x24 + 10 x25 + 5 x26 + 25x35 + 8x36 + 30 x45 + 45 x47 + 10 x57 + 40 x58 + 30 x67 + 15 x68 + 45 x78 Esto es, minimizar el gasto total en el proceso de trasladar las unidades de flujo a través de cada arco (i,j).



Restricciones asociadas a los arcos: 0 0 0 0 0 0 0 0 0 0 0 0 0

x12  75 x13 50 x23  40 x24  30 x25  50 x26  30 x35  40 x36  60 x45  60 x47  100 x57  40 x58  40 x67  50

Arco (1,2) Arco (1,3) Arco (2,3) Arco (2,4) Arco (2,5) Arco (2,6) Arco (3,5) Arco (3,6) Arco (4,5) Arco (4,7) Arco (5,7) Arco (5,8) Arco (6,7)

Fichero AMPL-2010-11-02.doc

Página 19 de 37

Departamento de Estadística e Investigación Operativa

0  x68  80 0  x78  100

Universidad de Valladolid

Arco (6,8) Arco (7,8)

Restricciones asociadas a los nodos: {lo que sale}  {entra} = hay x12 + x13=100 x23 + x24 + x25 + x26  x12 = 0 x35 + x36  x13  x23 = 0 x45 + x47  x24 = 0 x57 + x58  x25  x35  x45 = 0 x67 + x68  x26  x36 = 0 x78  x47  x57  x67=  25 x58 x68=  75

(Nodo 1) (Nodo 2) (Nodo 3) (Nodo 4) (Nodo 5) (Nodo 6) (Nodo 7) (Nodo 8)

O, de un modo más resumido: Minimizar Sujeta a:

x

kj j :( k , j ) ARCOS



c x

ij ij ( i , j )ARCOS

x

ik i:( i , k ) ARCOS

 bk para cada nodo k.

0  xij  uij para cada arco (i,j). PROGRAMACIÓN DEL PROBLEMA EN AMPL USANDO EL FORMATO 0. Modelo explicito donde el fichero .mod incluye simultáneamente el modelo y los datos.

Fichero W466-66-f0-(2010).mod # Problema del libro de Winston, página 452 # Problema básico de flujo con coste mínimo con formato 0 # Fichero W466-66-f0-(2009).mod # Variables de decision var x12>=0, =0, =0, =0, =0, =0, =0, =0, =0, =0, =0, =0, =0, =0, =0, =0; param cota_sup{ARCOS}>=0; var x {(i,j) in ARCOS}>=0,=0; # Cota superior del flujo en el arco (i,j) param cota_sup{ARCOS}>=0; var x {(i,j) in ARCOS}>=0,=0; var x3 >=0; var x4 >=0; # Función objetivo maximize objetivo: 16000*x1+22000*x2+12000*x3+8000*x4; # Restricción subject to res: 5000*x1+7000*x2+4000*x3+3000*x4=0, integer; var x2 >=0, integer; var x3 >=0, integer; var x4 >=0, integer; # Función objetivo maximize objetivo: 16000*x1+22000*x2+12000*x3+8000*x4; # Restricción subject to res: 5000*x1+7000*x2+4000*x3+3000*x4=0, =0, =0, =0, =0 , integer; # Alternativa para el caso entero # var x{INVERSIONES} >=0 , =0 , integer; # var x{INVERSIONES} >=0 ,