Lista 1 - Modelagem de Problemas de Programação Inteira (EaD) parte-I

Prévia do material em texto

LISTA 1 
 
Centro Federal de Educação Tecnológica Celso Suckow da Fonseca 
Departamento de Engenharia de Produção 
Disciplina: Pesquisa Operacional II 
Tema: Modelagem de Problemas de Programação Inteira 
Professor: Ormeu Coelho da Silva Júnior 
 
1 – Cinco produtos podem ser produzidos em duas máquinas distintas, havendo custos de produção associados 
à alocação dos produtos às máquinas, como se vê a seguir. 
Tarefas 
Custo de Produção ($) 
Máquina 1 Máquina 2 
1 200 300 
2 250 200 
3 300 150 
4 450 250 
5 150 250 
Escreva um modelo de Programação Inteira para alocar os produtos às máquinas, minimizando o custo total de 
produção e atendendo às seguintes restrições: 
a) Os produtos 1 e 3 devem ser alocados à mesma máquina. 
b) Se o produto 1 ou 4 for alocado à máquina 1, o produto 2 também deve ser. 
c) Se o produto 5 for alocado a uma dada máquina o produto 2 não deve ser. 
d) Dentre os produtos 1, 2 e 4, pelo menos dois devem ser alocados à mesma máquina. 
 
2 – Uma empresa deseja descobrir qual seu mix ótimo de produção para elaborar seu plano de vendas. Ela 
produz fundamentalmente três produtos que consegue vender no mercado ao preço Ci, i = 1,2,3. Cada tonelada 
do produto i produzida implica em um consumo de capacidade produtiva de Ri horas, i = 1,2,3, sendo que a 
capacidade disponível de produção, K, igual 80 horas semanais. Há lotes mínimos e máximos que devem ser 
produzidos, caso a empresa opte por fazer uma dada ração. A tabela abaixo apresenta os dados do problema: 
Ração Preço de Venda 
(R$/ton) 
Consumo de capacidade 
(h/ton) 
Lote Mínimo 
(ton) 
Lote Máximo 
(ton) 
1 350 1,5 20 50 
2 250 1,1 10 40 
3 300 1,2 15 30 
Escreva um modelo de Programação Inteira Mista para determinar o plano semanal de produção que maximiza a 
receita de vendas. 
 
3 – Uma empresa precisa escolher onde instalar um ou mais armazéns de grande porte para atender às demandas 
de 4 regiões comerciais distintas. Além de definir quantos armazéns e onde serão instalados, também é preciso 
decidir quais armazéns atenderão quais regiões comerciais. Há 3 locais disponíveis para instalação dos armazéns 
e, em cada local 𝑖, há um custo de instalação/operação, 𝐹𝑖, cujos valores são mostrados no vetor 𝐹 abaixo. Entre 
cada local 𝑖 (𝑖 = A,B,C) e as regiões comerciais 𝑗 (j = 1,...,4) há custos de transporte 𝐶𝑖𝑗 que variam linearmente 
com a distância e a demanda. Ou seja, 𝐶𝑖𝑗 = 𝐷𝑖𝑗𝑉𝑗 . Considere uma taxa de transporte  = $1,5/ton.km. 
12 8 13 11
[ ] 13 14 15 9 em km
16 9 12 17
ijD
 
 
  
 
  
1.700
[ ] 1.550 em $
1.920
iF
 
 
  
 
  
50
50
( ) em ton.
150
100
jV
 
 
 
 
 
  
(a) Formule um programa binário para determinar em quais locais serão instalados os armazéns e qual a 
alocação de regiões comerciais aos armazéns, de modo a minimizar o custo total de configuração deste 
sistema logístico (isto é, a soma dos custos fixos de instalação e dos custos variáveis de transporte das 
demandas). 
(b) É possível declarar alguma da variáveis deste problema como contínua no intervalo [0,1] e mesmo assim 
garantir que há uma solução ótima na qual estas variáveis assumem valores inteiros? Justifique sua resposta. 
(c) Considere agora, que devido a limitações técnicas e financeiras, não se deseja que mais de duas fábricas 
sejam instaladas. Insira uma restrição no modelo elaborado para o item anterior de modo a garantir que isto 
aconteça. 
(d) Por fim, considere restrições de capacidade em cada armazém, expressas pelo total da demanda que pode 
ser distribuída a partir deles. Suponha, então, que estas capacidades são dados pelo vetor (Ki) e que as 
demandas de cada cidade são expressas no vetor (Vj). Altere o modelo proposto na letra (a) para representar 
esta nova situação. 
150
[ ] 150 em ton.
250
iK
 
 
  
 
  
OBS: 
(1) O problema apresentado no item (a) é um exemplo do Problema de Localização Facilidades Não-Capacitado 
(UFLP - Uncapacitated Facility Location Problem). 
(2) O problema apresentado no item (d) é um exemplo do Problema de Localização Facilidades Capacitado 
(CFLP - Capacitated Facility Location Problem). 
(3) Se as variáveis de alocação no CFLP forem definidas como binárias, dir-se-á que o problema considera 
alocação única, pois cada cliente poderá ser alocado a apenas uma facilidade. Por outro lado, se a integralidade 
requerida para estas variáveis for relaxada (isto é se elas forem consideradas contínuas no intervalo [0,1]), dir-se-á 
que o problema considera alocação múltipla, o que implica que a demanda de um dado cliente pode ser atendida 
por mais de uma facilidade. 
 
5 – Refaça a letra (d) do exercício 4 considerando a existência dos custos de movimentação e manuseio da carga 
nos armazéns. Os valores referentes a cada armazém estão definidos no vetor 𝐻. 
15
[ ] 15 em $/ton.
25
 
 
  
 
 
iH 
 
6 – A prefeitura de uma cidade pequena, do interior de Minas Gerais, deseja implantar 3 creches públicas para 
atender toda a demanda por este serviço, distribuída ao longo dos 8 bairros que compõe o município. Para fazer 
isso, a prefeitura dispõe de quatro terrenos nos quais seria possível instalar as creches, sendo que o custo de 
instalação esperado é o mesmo em qualquer um dos terrenos. Em cada bairro j há uma demanda 𝑉𝑗 (em milhares 
de habitantes) que deve ser integralmente atendida. A matriz de distâncias mínimas entre os bairros da cidade e o 
vetor de demandas são mostrados abaixo: 
 
Distâncias 
Dji (km) 
1 2 3 4 5 6 7 8 
1 0 1,3 2,3 1,4 2,8 3,3 2,7 2,7 
2 1,3 0 1 1,6 1,8 2,1 1,5 2,6 
3 2,3 1 0 0,6 0,8 2,3 1,7 1,6 
4 1,4 1,6 0,6 0 1,4 2,2 2,4 1,3 
5 2,8 1,8 0,8 1,4 0 1,6 1 0,9 
6 3,3 2,1 2,3 2,2 1,6 0 1,6 1,5 
7 2,7 1,5 1,7 2,4 1 1,6 0 1,4 
8 2,7 2,6 1,6 1,3 0,9 1,5 1,4 0 
 
População 
Vj (103 hab) 
6,4 7,5 8,8 6,9 9,8 11,9 8,2 7,7 
Sabendo-se que as creches podem ser instaladas nos bairros 1, 2, 5 e 7, formule um modelo de programação 
inteira para determinar a localização das três creches e a alocação dos bairros a elas, de modo que a minimizar a 
distância média que um usuário do sistema percorrerá em busca do serviço. 
 
7 – Resolva novamente o problema 6 assumindo que as crianças serão transportadas em um serviço municipal de 
vans escolares. Desta forma, o deslocamento entre pares de bairros deverá respeitar as mãos das ruas, fazendo 
com as distâncias nessa rede sejam assimétricas, isto, 𝐷𝑖𝑗 ≠ 𝐷𝑗𝑖. Os valores são mostrados na matriz abaixo. 
 
Distâncias 
Dji (km) 
1 2 3 4 5 6 7 8 
1 0,0 1,3 2,3 1,4 2,8 3,3 2,7 2,7 
2 2,1 0,0 1,0 1,6 1,8 2,1 1,5 2,6 
3 1,1 0,9 0,0 0,6 0,8 2,3 1,7 1,6 
4 1,6 2,5 3,5 0,0 1,4 2,2 2,4 1,3 
5 3,2 1,1 2,1 2,7 0,0 1,6 1,0 0,9 
6 3,8 1,8 2,8 3,3 0,7 0,0 1,6 1,5 
7 4,4 2,4 3,4 3,9 1,3 0,6 0,0 1,4 
8 4,7 2,7 3,7 4,2 1,6 0,9 2,5 0,0 
 
8 – Uma empresa precisa construir uma pequena linha de montagem para um novo produto. Este produto é 
constituído de 5 tarefas principais de montagem, entre as quais há relações de precedência. Os tempos médios de 
processamento de cada tarefa (em segundos) e suas relações de precedência são dados no grafo abaixo: 
 
Dada a demanda esperada para este produto, cada posto de trabalho deve ser capaz de executar suas tarefas em 
até 22 segundos (este valor é o tempo de ciclo da linha). Formule um modelo de programação inteira para 
minimizar o número de postos de trabalho (cada um com um trabalhador) necessários à montagem do produto 
no tempo de ciclo requerido. O modelo deve determinar ainda quais tarefas serão feitas em quais postos, de 
modo que nenhuma tarefa seja executada em mais de posto. 
 
OBS: Este é um caso do Problema de Balanceamento de Linha Simples do Tipo 1 (SALBP-1, Simple Assembly 
Line Problem - Type 1), no qual o objetivo é minimizar o número de postos de trabalho, garantindo a locação de 
todas as tarefas e respeitando o takt-time ( = tempo disponível/demanda) da linha. 
 
9 – Sabe-se que é possível balancear esta linhacom apenas 3 postos de trabalho. Busca-se agora qual o esquema 
de alocação de tarefas que suaviza a distribuição da carga de trabalho entre os 3 postos. Escreva um modelo de 
Programação Inteira Mista para isso. Lembre-se que a carga de trabalho de um posto é definida como a soma 
dos tempos das tarefas alocadas a ele. E suavizar a carga consiste em tornar as cargas dos postos o mais próximas 
o possível umas das outras. 
 
OBS: Este é um caso do Problema de Balanceamento de Linha Simples do Tipo 2 (SALBP-2, Simple Assembly 
Line Problem - Type 2), no qual se procura minimizar a máxima carga entre todos os postos, garantindo a alocação 
de todas as tarefas em um dado número de estações. Do ponto de vista prático, pode-se resolver um problema 
de balanceamento determinando o número mínimo de estações com uso do SALBP-1 e, posteriormente, usar o 
SALBP-2 para buscar uma alocação alternativa que suavize a carga. 
1 
8 
2 
9 
3 
12 
4 
7 5 
6