Embed Size (px)
Citation preview
Modelos de Otimização em Redes
Socorro RangelDMAp
Departamento de Matemática Aplicada
e-mail: [email protected]
http://www.ibilce.unesp.br/#!/departamentos/matematica-aplicada/docentes/
Empresa de Produtos de Madeira
Problemas:
•Transporte, localização, roteamento,
entre outros.
(Wagner,1986)
Problema do Transporte
O Presidente, Antônio Castor, da Companhia Ramos de Carvalho quer
distribuir da melhor maneira possível os recursos de madeira disponíveis em
suas reservas florestais. A madeira extraída deve ser enviada para os depósitos
situados nos estados de São Paulo, Bahia, Minas Gerais e Rio de Janeiro. Para
a próxima safra, foi feita uma estimativa de qual seria a produção de cada
reserva e a demanda de cada depósito.
Determinar um plano
de distribuição da
madeira que minimize
o custo total de
transporte.
Reservas Depósitos
Problema do Transporte
elementos conhecidos:
– custo de transporte entre cada combinação reserva
– oferta de madeira em cada reserva
– demanda por madeira em cada depósito
elementos desconhecidos
– quanto enviar de cada reserva para cada depósito
objetivo
– Fazer o transporte da madeira ao menor custo possível
restrições
– distribuir toda a madeira disponível nas reservas, atendendo a
demanda dos depósitos.
Restrições de oferta
Toda a safra da reserva i deve ser enviada para algum dos depósitos 1,2,3 ... n
Restrições de destino
O depósito j deve receber madeira das reservas 1,2,3, ... ou m suficientes para
atender a demanda:
Construção do Modelo:
Variáveis e Restrições
Variáveis de decisão:
Precisamos decidir quanto remeter de cada reserva i para cada depósito j:
= número de caminhões com carga total enviados da reserva i para o
depósito jijx
miOxxx iinii ,...2,1,...21 ==+++
njDxxx jnjjj ,...2,1,...21 ==+++
Modelo de Otimização Linear
Função Objetivo fazer o transporte da madeira ao menor custo possível.
O modelo é então:
:a sujeito
min1 1
∑∑= =
=
n
i
m
j
ijij xcz
miOxxx iinii ,...,2,1,...21 ==+++
njmix
njDxxx
ij
jmjjj
,...,1;,...,1,0
,...,2,1,...21
==≥
==+++
Problema do Transporte: Formato MPL
Solução enviada para
planilha do EXCEL
Leitura de dados em
planilha do EXCEL
Problema do Transporte: Formato LP
\ transp.lp
\ Generated with the MPL Modeling System
\ Constraints: 7, Variables: 12, Nonzeros: 24, Density: 29 %
\
MINIMIZE
Custo_To: 464 x11 + 513 x12 + 654 x13 + 867 x14 + 352 x21 + 416 x22
+ 690 x23 + 791 x24 + 995 x31 + 682 x32 + 388 x33 + 685 x34
SUBJECT TO
of_1: x11 + x12 + x13 + x14 = 75
of_2: x21 + x22 + x23 + x24 = 125
of_3: x31 + x32 + x33 + x34 = 100
dm_1: x11 + x21 + x31 = 80
dm_2: x12 + x22 + x32 = 65
dm_3: x13 + x23 + x33 = 70
dm_4: x14 + x24 + x34 = 85
END
Solução do Problema do Transporte
Se Oi e Dj são inteiros então
xij é inteiro.
Matriz de restrições é
Totalmente Unimodular
(determinante = 1,-1, ou 0)
O Problema da Designação
:a sujeito
min1 1
∑∑= =
=
n
i
m
j
ijij xcz
mixxx inii ,...,2,1,1...21 ==+++
.,...,1,,0
,...,2,1,1...21
mjix
mjxxx
ij
mjjj
=≥
==+++
Fazendo m = n , Oi =1 e Dj = 1, no
modelo do transporte, temos:
TarefasPessoas
O Problema da Designação
Solução: emparelhamento
(matching) de menor custo.
Fazendo m = n , Oi =1 e Dj = 1, no
modelo do transporte, temos:
:a sujeito
min1 1
∑∑= =
=
n
i
m
j
ijij xcz
mixxx inii ,...,2,1,1...21 ==+++
.,...,1,,0
,...,2,1,1...21
mjix
mjxxx
ij
mjjj
=≥
==+++
TarefasPessoas
Problema de Localização
elementos conhecidos:
– custo de transporte no percurso entre cada combinação reserva, depósito
– potencial de oferta de madeira em cada reserva
– demanda por madeira em cada depósito
– custo fixo de instalação de cada reserva
–custo variável de manutenção de cada percurso.
elementos desconhecidos
–que reservas deverão ser instaladas, e quanto enviar de cada reserva
instalada para cada depósito
objetivo a ser alcançado:
– definir as reservas a serem instaladas e fazer o transporte da madeira ao
menor custo possível
restrições
– distribuir a madeira disponível nas reservas instaladas, atendendo a
demanda dos depósitos.
O que muda no modelo do transporte considerado anteriormente?
Construção do Modelo:
Variáveis
Variáveis de decisão:
= 1 se a reserva i for instalada, 0 c.c.
Precisamos decidir também quanto remeter de cada reserva i para cada depósito j:
= número de unidades enviadas da reserva i para o depósito j
Restrições de oferta
Só hverá oferta de material na reserva i se esta estiver instalada (yi=1), caso
contrário (yi=0), a oferta de material é zero. As restrições de oferta devem
então ser modificadas para:
ijx
iy
miyOxxx iiinii ,...2,1,...21 =≤+++
Construção do Modelo:
Objetivo
Função Objetivo
• Além dos custos de transporte:
temos que considerar no custo total:
• o custo de instalação das reservas
• o custo de manutenção das estradas
A nova função objetivo será dada por:
∑∑= =
m
i
n
j
ijij xf1 1
∑∑= =
m
i
n
j
ijij xc1 1
∑=
m
i
ii yF1
+= ∑∑= =
m
i
n
j
ijij xcz1 1
min +∑=
m
i
ii yF1
∑∑= =
m
i
n
j
ijij xf1 1
Modelo de otimização inteiro misto:
Problema de Localização Capacitado
Formulação I
∑∑= =
=
4
1
4
1
mini j
ijij xcz +∑=
m
i
ii yF1
+∑∑= =
m
i
n
j
ijij xf1 1
Sujeito a:
miyOxxx iiinii ,...,2,1,...21 =≤+++
njmix
miy
njDxxx
ij
i
jmjjj
,...,1;,...,1inteira,0
,...,1,1/0
,...,2,1,...21
==≥
==
==+++
Problema de Localização Capacitado
Problema de Localização Capacitado
Problema de Localização Capacitado
Problema de Localização Capacitado
Problema de Localização Capacitado
Problema de Localização Capacitado
Para Saber Mais
1. Arenales, M., Armentano, V., Morabito, R. E Yanasse, H.-
Pesquisa Operacional, Elsevier, 2007.
2. Boaventura, P. O., Grafos : teoria, modelos, algoritmos,
Edgard Blucher, ; 2001.
3. Rangel, S. Introdução à construção de modelos de
otimização linear e inteira. 2. ed. São Carlos-SP: Sociedade
Brasileira de Matemática Aplicada e Computacional-
SBMAC, 2012. v. único. 82 p. (disponível em
http://www.sbmac.org.br/arquivos/notas/livro_18.pdf)
4. H. M. Wagner, Pesquisa Operacional, 1986, Prentice Hall
do Brasil Ltda, 2ª. Edição
5. Wolsey, L., Integer Programming, Ed. John Wiley & Sons,
1998.
