Apostila 2 - Pesquisa Operacional

Prévia do material em texto

Capítulo 2 Programação Linear Inteira 
Pesquisa Operacional I Jhoab Negreiros 
1
 
 
 
 
 
 
 
 
 
 
CAPÍTULO 4 
Programação Linear Inteira 
 
 
 
4.1 Introdução 
 
Programação linear inteira (PLI) são programações lineares nas quais algumas ou todas as 
variáveis estão restritas a valores inteiros. 
De maneira geral, o problema passível de solução por programação inteira deve apresentar 
as seguintes características: 
 
i. Função objetivo linear; 
ii. Restrições lineares; 
iii. Variáveis positivas; 
iv. Algumas ou todas variáveis inteiras. 
 
4.2 Algoritmo de branch-and-bound (B&B) 
 
O algoritmo de branch-and-bound (algoritmo de bifurcação e limite) é, decididamente, o 
mais eficiente em termos de cálculo para o problema de PLI. Na verdade, praticamente todos os 
códigos comerciais têm suas raízes no B&B. 
 Os passos a seguir com um exemplo numérico são utilizados para explicar os detalhes do 
algoritmo. 
 
Capítulo 2 Programação Linear Inteira 
Pesquisa Operacional I Jhoab Negreiros 
2
1. Resolva o problema de programação linear inteira relaxando suas variáveis, isto é, use a 
abordagem clássica como se as variáveis fossem contínuas. Examine a solução se as 
variáveis que deveriam ser inteiras observam efetivamente valores inteiros. Em caso 
positivo, o problema está resolvido. Se não, siga para o próximo passo; 
 
2. Se a solução obtida contém uma variável não-inteira, por exemplo, ��, então �� < �� < ��, 
onde �� e �� são inteiros consecutivos e não-negativos. Dois novos modelos de 
programação inteira são então criados acrescentando ao problema de programação inteira 
original ou a restrição �� ≤ �� ou �� ≥ ��; 
 
3. Se alguma das primeiras aproximações continuar a apresentar soluções não-inteiras, o 
problema de programação inteira originado por esta primeira aproximação torna-se 
candidato a uma bifurcação adicional; 
 
4. Se o problema for de maximização, a bifurcação continua até ser obtida uma primeira 
aproximação inteira (que é uma solução, não necessariamente ótima, do problema original). 
O valor da função objetivo corresponde a esta primeira aproximação inteira torna-se um 
limite inferior para o problema. Todos os modelos cujas primeiras aproximações, inteiras ou 
não, conduzam a valores da função objetivo menores que o limite inferior devem ser 
descartados. 
 
5. Se o problema for de minimização, o procedimento permanece o mesmo, exceto que os 
limites a serem utilizados deverão ser superiores e não mais inferiores. Assim, o valor da 
função objetivo a partir da primeira solução inteira torna-se o limite superior do problema, 
devendo ser eliminados os modelos com valores da função objetivo maiores que o limite 
superior corrente. 
 
Exemplo 1. A resolução para um problema de maximização (� = 3�� + 5��) é apresentado a 
seguir. �� = 8 �� = 6 Solução inteira �� = 2 Solução inteira �� = 3 com � inferior � = 34 � = 33 
 
�� = 8 �� = 6 �� = 4,25 �� = 2,25 �� = 3,25 �� = 4 � = 35,25 � = 34,25 � = 33,5 
 
 �� = 6,5 �� ≥ 7 �� = 3 Solução impossível � = 34,5 
 
Capítulo 2 Programação Linear Inteira 
Pesquisa Operacional I Jhoab Negreiros 
3
Exemplo 2. Maximizar o problema de programação linear inteira. 
Função objetivo: � = 5�� + 4�� 
Restrições:� �� + �� ≤ 510�� + 6�� ≤ 45��, �� �������� �ã! ��"���#�� 
 
 
 
 
 
 
 
 
 
4.3 Atividades 
Exercício 1. Uma máquina é usada para produzir produtos intercambiáveis. A máquina é capaz de 
fazer no máximo 20 unidades do produto 1 e 10 unidades do produto 2. Alternativamente, a 
máquina pode ser ajustada para produzir no máximo 12 unidades do produto 1 e 25 unidades do 
produto 2 por dia. A análise de mercado mostra que a máxima demanda diária dos dois produtos 
combinados é 35 unidades. Dado que os lucros unitários para os dois produtos respectivos são R$ 
10 e R$ 12, qual dos dois ajustes da máquina deve ser selecionado? Formule a questão como um 
problema de PLI e ache a solução ótima. 
 
Exercício 2. Uma fábrica produz três produtos. Os requisitos de mão-de-obra e matéria-prima para 
os três produtos são dados na tabela a seguir. 
Produto 
Mão-de-obra requerida Matéria-prima requerida 
por dia (hora/unidade) por dia (Kg/unidades) 
1 3 4 
2 4 3 
3 5 6 
Disponibilidade diária 100 100 
 
Os lucros por unidade para os três produtos são R$ 25, R$ 30 e R$ 45, respectivamente. Se a 
fábrica quiser mesmo fabricar o produto 3, seu nível de produção deve ser no mínimo de cinco 
unidades diárias. Formule a questão como um problema de PLI mista e ache o mix ótimo.