PCC173 - Otimização em Redes€¦ · PCC173 - Otimização em Redes MarcoAntonioM.Carvalho Departamento de Computação Instituto de Ciências Exatas e Biológicas Universidade

PCC173 - Otimização em Redes

Marco Antonio M. Carvalho

Departamento de ComputaçãoInstituto de Ciências Exatas e Biológicas

Universidade Federal de Ouro Preto

10 de março de 2020

Marco Antonio M. Carvalho (UFOP) PCC173 10 de março de 2020 1 / 31

Avisos

Site da disciplina:I http://www.decom.ufop.br/marco/

Lista de e-mails:I [email protected]

Para solicitar acesso:I http://groups.google.com/group/pcc173


http://www.decom.ufop.br/marco/

[email protected]

http://groups.google.com/group/pcc173

Conteúdo

1 Modelagem de Problemas Clássicos

2 Exemplos de Modelagem de Problemas de PL Contínua

3 Exemplos de Modelagem de Problemas de PL Inteira com Possibilidadede Aproximação Contínua

4 Exemplos de Modelagem de Problemas de PL Inteira sem AproximaçãoContínua


Avisos


Modelagem de Problemas Clássicos

O Problema da Mochila 0-1Dadas uma mochila de capacidade W e uma lista de n itens distintos eúnicos (enumerados de 1 a n), cada um com um peso w1, w2, . . . , wn e umvalor v1, v2, . . . , vn, maximizar o valor carregado na mochila, respeitandosua capacidade.




Dados e VariáveisI Capacidade da mochila W ;I pesos wj , j = 1, 2, . . . , n;I valores vj , j = 1, 2, . . . , n;I variáveis de decisão xj , j = 1, 2, . . . , n.


Modelagem de Problemas


max z =

n∑j=1

vjxj

sujeito a :n∑

j=1

wjxj ≤W

xj ∈ {0, 1}, j = 1, 2, . . . , n


Modelagem de Problemas

O Problema da Mochila 0-1Consideremos a seguinte instância do Problema da Mochila 0-1:

Item x1 x2 x3 x4 x5

Peso 52 23 35 15 7Valor 100 60 70 15 8

Utilizando estes dados no modelo, temos:

max z =100x1 + 60x2 + 70x3 + 15x4 + 8x5

sujeito a :

52x1 + 23x2 + 35x3 + 15x4 + 7x5 ≤ 60

x1, x2, x3, x4, x5 ∈ {0, 1}



Bin PackingDados um conjunto Itens de objetos diferentes, cada um com volume wj , eum conjunto Caixas de caixas de volume V , empacotar todos os objetosminimizando o número de caixas.



Bin PackingDados um conjunto Itens de objetos diferentes, cada um com volume wj , eum conjunto Caixas de caixas de volume V , empacotar todos os objetosminimizando o número de caixas.

Dados e VariáveisI volume wj , ∀j ∈ Itens;I volume V das caixas;I yi indica a utilização da caixa i;I xij indica se o item j é colocado na caixa i.



Bin Packing

min∑

i ∈ Caixas

yi (1)

sujeito a : ∑i ∈ Caixas

xij = 1, ∀j ∈ Itens (2)∑j ∈ Itens

wjxij ≤ Viyi, ∀i ∈ Caixas (3)

xij ∈ {0, 1},∀i ∈ Caixas, ∀j ∈ Itens (4)yi ∈ {0, 1}, ∀i ∈ Caixas (5)



Bin PackingConsideremos a seguinte instância do Bin Packing : V = 1 e

Objeto 1 2 3 4 5 6 7Volume 0,2 0,5 0,4 0,7 0,1 0,3 0,8

Utilizando estes dados no modelo, temos:

min y1 + y2 + y3 + y4 + y5 + y6 + y7

sujeito a :

.

.

.

y1, y2, y3, y4, y5, y6, y7 ∈ {0, 1}


Modelagem de Problemas de PL Contínua

Exemplo 1Uma metalúrgica deseja maximizar sua receita bruta. A tabela abaixoindica a proporção de cada material na mistura para obtenção de umatonelada das ligas passíveis de fabricação.

O preço está cotado em Reais, e as restrições de disponibilidade estãoexpressas em toneladas.

Liga Especial de Liga Especial de DisponibilidadeBaixa Resistência Alta Resistência de Matéria Prima

Cobre 0,5 0,2 16Zinco 0,25 0,3 11

Chumbo 0,25 0,5 15Preço de Venda 3.000 5.000



Exemplo 1As variáveis de decisão xi indicam quantas toneladas de cada liga serãoproduzidas (i = 1 indica baixa resistência e i = 2 indica alta resistência).

A função objetivo visa maximizar o preço de venda da produção das ligasde baixa e alta resistência.

As restrições são relativas à disponibilidade dos metais que compõem asligas.

Por fim, as variáveis não podem assumir valores negativos, portanto,adicionamos restrições de não-negatividade.



Exemplo 1

max 3000x1 + 5000x2 (1)sujeito a :

0, 5x1 + 0, 2x2 ≤ 16 (2)0, 25x1 + 0, 3x2 ≤ 11 (3)0, 25x1 + 0, 5x2 ≤ 15 (4)x1 ≥ 0 (5)x2 ≥ 0 (6)



Exemplo 2Em uma dieta para redução calórica, é necessário determinar asquantidades de certos alimentos que deverão ser ingeridos diariamente, demaneira que requisitos nutricionais sejam satisfeitos a custo mínimo.

A tabela abaixo expressa os requisitos nutricionais de alguns alimentos emtermos de vitaminas A, C e D, controlados por sua quantidade mínimanecessária.

Leite Carne Peixe Salada Requisito Nutricional(Litro) (kg) (kg) (100g) Mínimo

A 2 mg 2 mg 10 mg 20 mg 11 mgC 50 mg 20 mg 10 mg 30 mg 70 mgD 80 mg 70 mg 10 mg 80 mg 250 mg

Custo 2 reais 4 reais 1,50 real 1 real



Exemplo 2As variáveis de decisão xi indicam a quantidade de cada tipo de alimentoi ∈ {l-leite, c-carne, p-peixe, s-salada }, a ser consumida na dieta.

A função objetivo visa minimizar o custo associado aos alimentos.

As restrições são relativas aos requisitos nutricionais mínimos de cadavitamina.

Novamente, as variáveis não podem assumir valores negativos, portanto,adicionamos restrições de não-negatividade.



Exemplo 2

min 2xl + 4xc + 1, 5xp + xs (1)sujeito a :

2xl + 2xc + 10xp + 20xs ≥ 11 (2)50xl + 20xc + 10xp + 30xs ≥ 70 (3)80xl + 70xc + 10xp + 80xs ≥ 250 (4)xl ≥ 0, xc ≥ 0, xp ≥ 0, xs ≥ 0 (5)



Exemplo 3Um sitiante está planejando sua estratégia de plantio para o próximo ano,visando o maior lucro. Ele deseja cultivar trigo, arroz e milho e sabe deantemão qual é a produtividade de sua terra para cada uma das culturas,reportada na tabela abaixo.

Produtividade Lucro porem kg por m2 kg de produção

Trigo 0,2 10,8 centavosArroz 0,3 4,2 centavosMilho 0,4 2,03 centavos

Por falta de um local de armazenamento próprio, a produção máxima estálimitada a 60 toneladas. A área cultivável do sítio é de 200.000m2.Por fim, para atender as demandas do próprio sítio, é imperativo que seplante 400m2 de trigo, 800m2 de arroz e 10.000m2 de milho.



Exemplo 3As variáveis de decisão xi indicam a área em m2 a ser cultivada a culturado tipo i ∈{t-trigo, a-arroz, m-milho}.

A função objetivo visa maximizar o lucro com a produção, para tanto,multiplicamos a produtividade pelo lucro previsto.

As restrições são agrupadas em três conjuntos:

I Restrições associadas à demanda do sítio;I Restrições associadas à área total disponível;I Restrição associada ao armazenamento.




Exemplo 3

max 2, 16xt + 1, 26xa + 0, 812xm (1)sujeito a :

xt ≥ 400 (2)xa ≥ 800 (3)xm ≥ 10.000 (4)xt + xa + xm ≤ 200.000 (5)0, 2xt + 0, 3xa + 0, 4xm ≤ 60.000 (6)xa ≥ 0, xt ≥ 0, xm ≥ 0 (7)


Exemplos de Modelagem de Problemas de PL Inteira comPossibilidade de Aproximação Contínua

Exemplo 1Uma fábrica de móveis de madeira possui em seu portfólio escrivaninhas,mesas, armários e prateleiras. A composição de cada móvel é descrita natabela abaixo, que também apresenta o valor de revenda e a disponibilidadede cada material.

Consumo por unidade de produto (m2) Estoque (m2)Escrivaninha Mesa Armário Prateleira

Tábua 1 1 1 4 250Prancha 0 1 1 2 600Painel 3 2 4 0 500

Valor de Revenda 100 80 120 20

O problema consiste em maximizar a receita com a venda de móveis.



Exemplo 1As variáveis de decisão xi indicam a quantidade de ser produzida do móveldo tipo i ∈{1-escrivaninha, 2-mesa, 3-armário, 4-porta}.

A função objetivo visa maximizar o lucro com a produção.

As restrições são relacionadas à disponibilidade de material.




Exemplo 1

max 100x1 + 80x2 + 120x3 + 20x4 (1)sujeito a :

x1 + x2 + x3 + 4x4 ≤ 250 (2)x2 + x3 + 2x4 ≤ 600 (3)3x1 + 2x2 + 4x3 ≤ 500 (4)x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 (5)



Exemplo 2Um atleta pratica natação e ciclismo. Com um orçamento mensal de 70reais, o atleta pode dedicar, no máximo, 18 horas mensais e 80.000 caloriasà prática de esportes:I A natação custa 3 reais por sessão de 2 horas, e queima 1.500 calorias;I O ciclismo custa 2 reais por sessão de 2 horas e queima 1.000 calorias.

Considerando que o atleta gosta igualmente de ambos esportes, o problemaconsiste em programar seu treinamento de maneira a otimizar o número deseções.



Exemplo 2As variáveis de decisão xi indicam a quantidade de seções do esporte dotipo i ∈ {1-natação, 2-ciclismo}.

A função objetivo visa maximizar o número de seções de treinamento.

As restrições são relacionadas à disponibilidade de dinheiro, calorias etempo.




Exemplo 2

max x1 + x2 (1)sujeito a :

3x1 + 2x2 ≤ 70 (2)1.500x1 + 1.000x2 ≤ 80.000 (3)2x1 + 2x2 ≤ 18 (4)x1 ≥ 0, x2 ≥ 0 (5)


Exemplos de Modelagem de Problemas de PL Inteira semAproximação Contínua

Exemplo 1Um hospital trabalha com atendimento variável em demanda 24 horas pordia, segundo a tabela abaixo.

Turno Horário Número Mínimo de Enfermeiros1 08:00-12:00 502 12:00-16:00 603 16:00-20:00 504 20:00-00:00 405 00:00-04:00 306 04:00-08:00 20

A jornada de trabalho de um enfermeiro dura 8 horas consecutivas, excetono turno 5, cuja jornada é de apenas 4 horas. A remuneração para o turno4 possui uma gratificação de 50%. O problema consiste em minimizar ogasto com a mão de obra.



Exemplo 1As variáveis de decisão xi indicam a quantidade de enfermeiros que iniciamsua jornada no turno i.

A princípio, os enfermeiros recebem a mesma remuneração, o que nospermite minimizar o número de enfermeiros. Entretanto, deve-se ponderaros enfermeiros do turno 4 levando em consideração a gratificação querecebem e também os enfermeiros do turno 5, que recebem o dobro porhora de trabalho.

As restrições são relacionadas ao número mínimo de enfermeiros por turno.

As variáveis não podem assumir valores negativos ou contínuos, portanto,adicionamos restrições de não-negatividade e de integralidade.



Exemplo 1

min x1 + x2 + x3 + 1, 5x4 + 2x5 + x6 (1)sujeito a :

x6 + x1 ≥ 50 (2)x1 + x2 ≥ 60 (3)x2 + x3 ≥ 50 (4)x3 + x4 ≥ 40 (5)x5 ≥ 30 (6)x6 ≥ 20 (7)x1, x2, x3, x4, x5, x6 ∈ Z+ (8)


Dúvidas?


Documents

PCC173 - Otimização em Redes€¦ · PCC173 - Otimização em Redes MarcoAntonioM.Carvalho Departamento de Computação Instituto de Ciências Exatas e Biológicas Universidade