DAS-9011
1 / 62
AMPL: A Mathematical Programming Language
Eduardo Camponogara
Departamento de Automação e Sistemas
Universidade Federal de Santa Catarina
DAS-9011: Métodos de Otimização
DAS-9011
Sumário
Introdução
Modelo LP Geral
Conjuntos
Variáveis e Parâmetros Bi-Dimensionais
Programação Inteira
Programação Não-Linear
Modelo AMPL do Problema de Fluxo em Redes
2 / 62
DAS-9011
Introdução
Sumário
Introdução
Modelo LP Geral
Conjuntos
Variáveis e Parâmetros Bi-Dimensionais
Programação Inteira
Programação Não-Linear
Modelo AMPL do Problema de Fluxo em Redes
3 / 62
DAS-9011
4 / 62
Introdução
Introdução
◮
AMPL é uma linguagem de alto nı́vel para especificação de
problemas de programação matemática.
◮
AMPL permite que o modelo seja especificado separadamente
dos dados
◮
É muito semelhante a forma que expressamos problemas
◮
O usuário fica livre da manipulação de dados
DAS-9011
Introdução
AMPL
5 / 62
DAS-9011
6 / 62
Introdução
AMPL
◮
AMPL precisa de um modelo em programação matemática,
que especifica variáveis, objetivo e restrições
◮
Também precisa de uma instância de dados
◮
Um modelo e um ou mais arquivos de dados são alimentados
ao software
◮
AMPL funciona como um compilador
DAS-9011
7 / 62
Introdução
Exemplo
◮
Uma companhia produz tinta em duas cores, azul e verde.
◮
Um litro de tinta azul custa R$ 10,00
◮
Um litro de tinta verde custa R$ 15,00
◮
A companhia possui uma fábrica e produz apenas uma cor de
cada vez
◮
Tinta azul é mais fácil de ser produzida. São produzidos 40
litros em uma hora
◮
Tinta verde é mais complicada. São produzidos 30 litros por
hora
DAS-9011
8 / 62
Introdução
Exemplo
◮
De acordo com estatı́sticas de mercado, a empresa pode
vender 860 litros de tinta verde e 1000 litros de tinta azul
◮
Em uma semana, a fábrica pode operar por 40 horas
◮
Tinta não pode ser armazenada
◮
Quantos litros de tinta, de cada cor, devem ser produzidos de
forma a maximizar o faturamento?
DAS-9011
9 / 62
Introdução
Formulação
max 10 azul + 15 verde
S.a :
(1/40)azul + (1/30)verde ≤ 40
0 ≤ azul ≤ 1000
0 ≤ verde ≤ 860
DAS-9011
Introdução
Modelo AMPL
## Exemplo 1
var azul; # litros azul
var verde; # litros verde
maximize lucro: 10*azul + 15*verde;
subject to tempo: (1/40)*azul + (1/30)*verde <= 40;
subject to limite azul: 0 <= azul <= 1000;
subject to limite verde: 0 <= verde <= 860;
10 / 62
DAS-9011
11 / 62
Introdução
Resolvendo no NEOS
◮
Arquivo com modelo “tinta.mod”
◮
Arquivo de comandos “tinta.cmd”
solve;
display lucro;
display azul, verde;
DAS-9011
Modelo LP Geral
Sumário
Introdução
Modelo LP Geral
Conjuntos
Variáveis e Parâmetros Bi-Dimensionais
Programação Inteira
Programação Não-Linear
Modelo AMPL do Problema de Fluxo em Redes
12 / 62
DAS-9011
13 / 62
Modelo LP Geral
Modelo LP Geral
◮
Foi relativamente fácil especificar o modelo anterior no
formato AMPL
◮
Contudo, se os problemas se tornam mais complexos, ou são
modificados frequentemente, as tarefas se tornam mais
complexas
◮
Por esta razão, tipicamente preferimos uma especificação
algébrica genérica para modelos de programação linear
DAS-9011
14 / 62
Modelo LP Geral
Modelo LP Geral
Dados:
◮
n = número de tintas
◮
t = tempo total disponı́vel
◮
pi = lucro por litro de tinta de cor i, i = 1, . . . , n
◮
ri = litros por hora da tinta de cor i, i = 1, . . . , n
◮
mi = demanda máxima da tinta de cor i, i = 1, . . . , n
◮
xi = litros produzidos de tinta de cor i, i = 1, . . . , n
DAS-9011
Modelo LP Geral
Modelo LP Geral
Variáveis:
xi = litros a serem produzidos de tinta de cor i, i = 1, . . . , n
15 / 62
DAS-9011
16 / 62
Modelo LP Geral
Modelo LP Geral
Objetivo:
max
n
X
i=1
p i xi
DAS-9011
17 / 62
Modelo LP Geral
Modelo LP Geral
Restrições:
n
X
(1/ri )xi ≤ t
i=1
0 ≤ xi ≤ mi , i = 1, . . . , n
DAS-9011
18 / 62
Modelo LP Geral
Modelo LP Geral
Modelo básico
◮
n = 2 e t = 40
◮
p1 = 10 e p2 = 15
◮
r1 = 40 e r2 = 30
◮
m1 = 1000 e m2 = 860
DAS-9011
Modelo LP Geral
Modelo AMPL
## Modelo – exemplo 2
param n;
param t;
param p{i in 1..n};
param r{i in 1..n};
param m{i in 1..n};
var tinta{i in 1..n};
maximize lucro: sum{i in 1..n} p[i]*tinta[i];
subject to tempo: sum{i in 1..n} (1/r[i])*tinta[i] <= t;
subject to capacidade{i in 1..n}: 0 <= tinta[i] <= m[i];
19 / 62
DAS-9011
Modelo LP Geral
Dados AMPL
## Exemplo 2 - Dados
param n := 2;
param t := 40;
param p := 1 10
2 15;
param r := 1 40
2 30;
param m := 1 1000
2 860;
20 / 62
DAS-9011
21 / 62
Modelo LP Geral
Dados AMPL – Outra Maneira
## Exemplo 2 – Outra forma de especificar dados
param n := 2;
param t := 40;
param:
p r m :=
1 10 40 1000
2 15 30 860;
DAS-9011
Conjuntos
Sumário
Introdução
Modelo LP Geral
Conjuntos
Variáveis e Parâmetros Bi-Dimensionais
Programação Inteira
Programação Não-Linear
Modelo AMPL do Problema de Fluxo em Redes
22 / 62
DAS-9011
23 / 62
Conjuntos
Conjuntos
◮
Nas seções acima, tivemos que lembrar que o ı́ndice 1 indicava
azul e 2 indicava verde
◮
Alternativamente, podemos utilizar nomes para referenciar as
tintas
DAS-9011
Conjuntos
Conjuntos
## Exemplo 2 – Modelo com conjuntos
set P;
param t;
param p{i in P};
param r{i in P};
param m{i in P};
var tinta{i in P};
maximize lucro: sum{i in P} p[i]*tinta[i];
subject to tempo: sum{i in P} (1/r[i])*tinta[i] <= t;
subject to capacidade{i in P}: 0 <= tinta[i] <= m[i];
24 / 62
DAS-9011
25 / 62
Conjuntos
Conjuntos
Comparando com a versão do modelo original, verificamos que eles
são similares. Contudo, há algumas diferenças:
◮
Em vez de definir o número de elementos n, simplismente
definimos o conjunto
◮
Em vez de indexar os parâmetros com ı́ndices 1 . . . n, usamos
os nomes dos membros do conjunto
DAS-9011
Conjuntos
Arquivo de Dados
## Exemplo 2 - Dados definidos por conjuntos
set P := azul verde;
param t := 40;
param p := azul 10
verde 15;
param r := azul 40
verde 30;
param m := azul 1000
verde 860;
26 / 62
DAS-9011
27 / 62
Conjuntos
Arquivo de Dados – Outra Forma
## Exemplo 2 - Outra forma de escrever os dados
set P := azul verde;
param t := 40;
param:
p r m :=
azul 10 40 1000
verde 15 30 860;
DAS-9011
Variáveis e Parâmetros Bi-Dimensionais
Sumário
Introdução
Modelo LP Geral
Conjuntos
Variáveis e Parâmetros Bi-Dimensionais
Programação Inteira
Programação Não-Linear
Modelo AMPL do Problema de Fluxo em Redes
28 / 62
DAS-9011
29 / 62
Variáveis e Parâmetros Bi-Dimensionais
Variáveis e Parâmetros Bi-Dimensionais
◮
Um modelo em programação matemática pode ter variáveis e
parâmetros bi-dimensionais
◮
Podemos escrever tais parâmetros em uma tabela
◮
AMPL permite que dados sejam especificados em tabelas
DAS-9011
30 / 62
Variáveis e Parâmetros Bi-Dimensionais
Variáveis e Parâmetros Bi-Dimensionais
Exemplo
◮
A fábrica de tintas agora tem três depósitos com tinta azul
◮
A cada semana, tinta deve ser distribuı́da a quatro clientes
◮
Para cada depósito e cliente, o custo de transporte de um litro
de tinta é diferente
◮
Os custos de transporte são dados na tabela a seguir
DAS-9011
31 / 62
Variáveis e Parâmetros Bi-Dimensionais
Tabela com Custos de Transporte
Depósito 1
Depósito 2
Depósito 3
Cliente 1
1
3
2
Cliente 2
2
5
2
Cliente 3
1
1
2
Cliente 4
3
4
2
DAS-9011
32 / 62
Variáveis e Parâmetros Bi-Dimensionais
Estoque de Tinta Azul
Depósito 1
Depósito 2
Depósito 3
Estoque
250
800
760
DAS-9011
33 / 62
Variáveis e Parâmetros Bi-Dimensionais
Demanda de Tinta Azul dos Clientes
Cliente
Cliente
Cliente
Cliente
1
2
3
4
Demanda
300
320
800
390
DAS-9011
Variáveis e Parâmetros Bi-Dimensionais
Modelo AMPL
## Exemplo 3 – Modelo
param depositos; # número de depósitos
param clientes; # número de consumidores
# Custo de transporte do depósito i
# para cliente j
param custo{i in 1..depositos, j in 1..clientes};
param estoque{i in 1..depositos}; # estoque depósito i
param demanda{j in 1..clientes}; # demanda cliente j
var qt{i in 1..depositos, j in 1..clientes};
34 / 62
DAS-9011
Variáveis e Parâmetros Bi-Dimensionais
Modelo AMPL
minimize Custo:
sum{i in 1..depositos, j in 1..clientes} custo[i,j]*qt[i,j];
subject to Estoque {i in 1..depositos}:
sum{j in 1..clientes} qt[i,j] = estoque[i];
subject to Demanda {j in 1..clientes}:
sum{i in 1..depositos} qt[i,j] = demanda[j];
subject to Positivo {i in 1..depositos, j in 1..clientes}:
qt[i,j]>=0;
35 / 62
DAS-9011
36 / 62
Variáveis e Parâmetros Bi-Dimensionais
Dados AMPL
## Exemplo 3 - Dados
param depositos := 3;
param clientes := 4;
param custo:
1
2
3
param estoque :=
1 250
2 800
3 760;
1
1
3
2
2
2
5
2
3
1
1
2
4 :=
8
4
2;
DAS-9011
37 / 62
Variáveis e Parâmetros Bi-Dimensionais
Observações
◮
Cuidado deve ser tomado ao se especificar dados
◮
Observe o ponto-e-vı́rgula após cada nome
◮
Note que o primeiro ı́ndice (depósito) está na linha, enquanto
o segundo ı́ndice (cliente) está na coluna
DAS-9011
Variáveis e Parâmetros Bi-Dimensionais
Modelo AMPL – Usando Conjuntos
## Exemplo 3 – Modelo com conjuntos
set Depositos;
set Clientes;
# Custo de transporte do depósito i
# para cliente j
param custo{i in Depositos, j in Clientes};
param estoque{i in Depositos}; # estoque depósito i
param demanda{i in Clientes}; # demanda cliente j
var qt{i in Depositos, j in Clientes} >= 0;
38 / 62
DAS-9011
Variáveis e Parâmetros Bi-Dimensionais
Modelo AMPL – Usando Conjuntos
minimize Custo:
sum{i in Depositos, j in Clientes} custo[i,j]*qt[i,j];
subject to Estoque {i in Depositos}:
sum{j in Clientes} qt[i,j] = estoque[i];
subject to Demanda {j in Clientes}:
sum{i in Depositos} qt[i,j] = demanda[j];
39 / 62
DAS-9011
40 / 62
Variáveis e Parâmetros Bi-Dimensionais
Dados AMPL – Usando Conjuntos
## Exemplo 3 - Dados com conjuntos
set Depositos := Rio Fpolis Brasilia;
set Clientes := Petrobras Embraer UFSC USP;
param custo:
Petrobras
Rio
1
Fpolis
3
Brasilia 2
Embraer
2
5
2
UFSC
1
1
2
USP :=
3
4
2;
DAS-9011
41 / 62
Variáveis e Parâmetros Bi-Dimensionais
Dados AMPL – Usando Conjuntos
## Exemplo 3 - Dados com conjuntos
param estoque := Rio
250
Fpolis 800
Brasilia 760;
param demanda := Petrobras
Embraer
UFSC
USP
300
320
800
390;
DAS-9011
Programação Inteira
Sumário
Introdução
Modelo LP Geral
Conjuntos
Variáveis e Parâmetros Bi-Dimensionais
Programação Inteira
Programação Não-Linear
Modelo AMPL do Problema de Fluxo em Redes
42 / 62
DAS-9011
43 / 62
Programação Inteira
Programação Inteira
◮
Um modelo de programação matemática frequentemente
exige que algumas (ou todas) as variáveis sejam inteiras
◮
AMPL permite a especificação de variáveis inteiras
◮
Como ilustração, suponha que a empresa de tintas deseja
expandir a capacidade de armazenamento
◮
Contudo, esta expansão traz custos. Além dos custos de
transporte, a empresa terá um custo fixo para instalação de
um novo depósito.
DAS-9011
Programação Inteira
Localização de Instalações
As capacidades dos possı́veis depósitos são:
Depósito 1 550
Depósito 2 1100
Depósito 3 1060
Os custos de instalação destes depósitos são:
Depósito 1 500
Depósito 2 500
Depósito 3 500
44 / 62
DAS-9011
Programação Inteira
Modelo AMPLs
## Exemplo 4 – Instalação de depósitos
set Depositos;
set Clientes;
# Custo de transporte do depósito i
# para cliente j
param custo{i in Depositos, j in Clientes};
param estoque{i in Depositos}; # estoque depósito i
param custo fixo{i in Depositos}; # custo intalação depósito i
param demanda{j in Clientes}; # demanda cliente j
var qt{i in Depositos, j in Clientes} >= 0;
var abrir{i in Depositos} binary; # abrir[i]=1 se instala depósito i
# abrir[i]=0 se não instala depósito i
45 / 62
DAS-9011
Programação Inteira
Modelo AMPL – Usando Conjuntos
minimize Custo:
sum{i in Depositos, j in Clientes} custo[i,j]*qt[i,j] +
sum{i in Depositos} custo fixo[i]*abrir[i];
subject to Estoque {i in Depositos}:
sum{j in Clientes} qt[i,j] <= estoque[i]*abrir[i];
subject to Demanda {j in Clientes}:
sum{i in Depositos} qt[i,j] = demanda[j];
46 / 62
DAS-9011
47 / 62
Programação Inteira
Dados AMPL – Usando Conjuntos
## Exemplo 4 - Dados
set Depositos := Rio Fpolis Brasilia;
set Clientes := Petrobras Embraer UFSC USP;
param custo:
Petrobras
Rio
1
Fpolis
3
Brasilia 2
Embraer
2
5
2
UFSC
1
1
2
USP :=
3
4
2;
DAS-9011
48 / 62
Programação Inteira
Dados AMPL – Usando Conjuntos
## Exemplo 4 - Dados
param estoque := Rio
550
Fpolis 1100
Brasilia 1060;
param demanda := Petrobras
Embraer
UFSC
USP
300
320
800
390;
param custo fixo := Rio
500
Fpolis 500
Brasilia 500;
DAS-9011
Programação Não-Linear
Sumário
Introdução
Modelo LP Geral
Conjuntos
Variáveis e Parâmetros Bi-Dimensionais
Programação Inteira
Programação Não-Linear
Modelo AMPL do Problema de Fluxo em Redes
49 / 62
DAS-9011
50 / 62
Programação Não-Linear
Modelos Não-Lineares
◮
Muitos modelos de programação matemática incluem funções
não-lineares, na forma de restrições e objetivos.
◮
AMPL também pode fazer a interface com solvers de
programação não-linear, tais como Minos e Conopt.
◮
Como ilustração considere o modelo de otimização de
portofolio.
◮
Suponha que existe um conjunto A de investimentos.
◮
Conhecemos o retorno esperado R de cada um destes
investimentos para um perı́odo de T anos.
DAS-9011
51 / 62
Programação Não-Linear
Modelos Não-Lineares
◮
A partir destes dados, podemos calcular a matriz de
covariância dos investimentos.
◮
Desejamos maximizar o retorno esperado sujeito a uma taxa
de risco máxima.
◮
Desejamos minimizar o risco sujeito a um retorno mı́nimo
DAS-9011
Programação Não-Linear
Modelos Não-Lineares
## Exemplo 5 - Otimização Portofolio
set A; # investimentos
set T := 1984..1994; # anos
param s max default 0.00305;
# i.e., 5.522 por cento de desvio padrão no retorno
param R {T,A};
param media {j in A} := ( sum{i in T} R[i,j] )/card(T);
param Rt {i in T, j in A} := R[i,j] - media[j];
var share{A} >=0;
52 / 62
DAS-9011
53 / 62
Programação Não-Linear
Modelos Não-Lineares
## Exemplo 5 - Otimização Portofolio
minimize retorno: - sum{j in A} media[j]*share[j];
subject to limite risco:
sum{i in T} (sum{j in A} Rt[i,j]*share[j])2 / card(T) <= s max;
subject to total investimento:
sum{j in A} share[j] = 1;
DAS-9011
54 / 62
Programação Não-Linear
Modelos Não-Lineares
Observações
◮
A variável share indica a fração dos recursos utilizados em
cada investimento.
◮
A taxa de retorno esperada é:
X
mediaj sharej
j∈A
◮
O risco esperado é dado por:
P
X j∈A (Rtj ∗ sharej )2
i∈T
◮
card(T )
O problema de otimização de portofolio tem objetivo linear e
restrições quadráticas.
DAS-9011
55 / 62
Programação Não-Linear
Modelos Não-Lineares
## Exemplo 5 - Dados
set A := BR MES US LONG BONDS SP 500 BOVESPA;
param R:
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
BR MES
1.103
1.080
1.063
1.061
1.071
1.087
1.080
1.057
1.036
1.031
1.045
US LONG BONDS SP 500
1.159
1.061
1.366
1.316
1.309
1.186
0.925
1.052
1.086
1.165
1.212
1.316
1.054
0.968
1.193
1.304
1.079
1.076
1.217
1.100
0.889
1.012
BOVESPA :=
1.030
1.326
1.161
1.023
1.179
1.292
0.938
1.342
1.090
1.113
0.999;
DAS-9011
56 / 62
Programação Não-Linear
Modelos Não-Lineares
◮
Modelos não-lineares apresentam várias dificuldades e
sutilezas:
◮
◮
◮
◮
Violação das regiões nas quais as funções estão definidas
(valores vão para o ∞)
Múltiplos ótimos locais
Pontos estacionários
Vamos estudar otimização não-linear mais à frente
DAS-9011
57 / 62
Programação Não-Linear
Modelos Não-Lineares
◮
Muitas vezes, buscando encontrar melhores soluções somos
obrigados a otimizar a partir de diferentes pontos iniciais
◮
Isto pode ser especificado com a declaração opcional “:=”
◮
Escrevemos
x[A] >=0; := 0.25;
para inicializar o vetor com o valor 0.25
◮
O solver irá utilizar estes valores como ponto de partida
DAS-9011
Modelo AMPL do Problema de Fluxo em Redes
Sumário
Introdução
Modelo LP Geral
Conjuntos
Variáveis e Parâmetros Bi-Dimensionais
Programação Inteira
Programação Não-Linear
Modelo AMPL do Problema de Fluxo em Redes
58 / 62
DAS-9011
59 / 62
Modelo AMPL do Problema de Fluxo em Redes
Modelo AMPL
# Modelo AMPL para fluxo em redes custo mı́nimo
set NOS; # nós da rede
set ARCOS within {NOS, NOS}; # arcos da rede
param
param
param
param
b {NOS} default 0; # suprimento/consumo do nó i
c {ARCOS} default 0; # custo do arco (i,j)
l {ARCOS} default 0; # limite inferior do arco (i,j)
u {ARCOS} default Infinity; # limite superior do arco arc(i,j)
var x {ARCOS}; # fluxo no arco (i,j)
DAS-9011
Modelo AMPL do Problema de Fluxo em Redes
Modelo AMPL
# Modelo AMPL para fluxo em redes custo mı́nimo
minimize Custo: sum{(i,j) in ARCOS} c[i,j] * x[i,j];
# Flow Out(i) - Flow In(i) = b(i)
subject to equilibrio massa {i in NOS}:
sum{j in NOS: (i,j) in ARCOS} x[i,j]
- sum{j in NOS: (j,i) in ARCOS} x[j,i] = b[i];
subject to capacidade {(i,j) in ARCOS}:
l[i,j] <= x[i,j] <= u[i,j];
60 / 62
DAS-9011
61 / 62
Modelo AMPL do Problema de Fluxo em Redes
Dados AMPL
set NOS := 1 2 3 4;
set ARCOS := (1,2) (1,3) (2,3) (2,4) (3,4);
param b := 1
2
3
4
#
param:
1
1
2
2
3
5
-2
0
-3;
cost lower
c l
2
3 2
3
2 0
3
1 0
4
4 1
4
4 0
upper bound
u :=
5
2
2
3
3;
DAS-9011
62 / 62
Modelo AMPL do Problema de Fluxo em Redes
AMPL
◮
Fim!
◮
Obrigado pela participação