Modelos de Otimização em Redes - ibilce.unesp.br · Problema de Localização elementos...

Modelos de Otimização em Redes

Socorro RangelDMAp

Departamento de Matemática Aplicada

e-mail: socorro@ibilce.unesp.br

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.