PO UND 09 - PROGRAMAÇÃO LINEAR INTEIRA

Prévia do material em texto

03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 1/22
PROGRAMAÇÃO LINEAR
INTEIRA
APRESENTAÇÃO
Olá!
Os problemas de programação linear inteira (PLI) estão relacionados, frequentemente, ao
fato de algumas ou todas as variáveis de decisão terem de se restringir a valores inteiros.
Há, também, muitas aplicações que envolvem decisões sim-ou-não que podem ser
representadas por variáveis binárias (0-1). Por causa desses fatores, a programação inteira
se tornou uma das técnicas de pesquisa operacional (PO) mais amplamente u�lizadas.
Nesta Unidade de Aprendizagem, você vai conhecer caracterís�cas importantes da
programação linear inteira, suas principais aplicações e os algoritmos mais u�lizados para
resolver problemas de PLI.
Bons estudos.
Ao �nal desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:
Iden�ficar as caracterís�cas gerais da programação linear inteira.
Determinar a alocação de recursos a a�vidades.

03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 2/22
Descrever uma programação linear inteira.
DESAFIO
Você trabalha em uma confeitaria que produz dois �pos de bolos: chocolate e creme. Cada
lote de bolos de chocolate é vendido com um lucro de R$ 3,00, e cada lote de bolos de
creme é vendido com um lucro de R$ 1,00. Contratos com várias lojas impõem que sejam
produzidos no mínimo 10 lotes de bolos de chocolate por dia e que o total de bolos
fabricados nunca seja menor que 20. O mercado só é capaz de consumir até 40 lotes de
bolos de creme e 60 de chocolate. As máquinas de preparação dos bolos disponibilizam
180 horas de operação, sendo que cada lote de bolos de chocolate consome 2 horas de
trabalho, e cada lote de bolos de creme, 3 horas.
Você é responsável pela estratégia de vendas, e seu gerente solicitou que você determine
o esquema de produção que maximize os lucros com a venda dos bolos.
INFOGRÁFICO
O branch-and-bound (B&B) é o mais confiável dos dois algoritmos de solução para
programação linear inteira (PLI). Na verdade, pra�camente todos os códigos comerciais de
resolução de problemas de PLI são baseados em B&B. Veja no infográfico um resumo desse
algoritmo.
CONTEÚDO DO LIVRO
Programação Linear Inteira (PLI) são programações lineares nas quais algumas ou todas as
variáveis estão restritas a valores inteiros (ou discretos). Quando estudamos PLI,
precisamos destacar três áreas: aplicação, teoria e cálculo. Veja no capítulo Programação



03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 3/22
Linear Inteira, do livro "Pesquisa Operacional", algumas aplicações que demonstram a
ampla u�lização de PLI na prá�ca.
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 4/22
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 5/22
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 6/22
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 7/22
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 8/22
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 9/22
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 10/22
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 11/22
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 12/22
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 13/22
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 14/22
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 15/22
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 16/22
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 17/22
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 18/22
DICA DO PROFESSOR
Nesse vídeo, você vai ver como encontrar a solução ó�ma para a maximização da receita
da venda de móveis de uma fábrica, por intermédio de programação linear inteira,
u�lizando o so�ware Lindo.
Conteúdo disponível na plataforma virtual de ensino. Con�ra!
EXERCÍCIOS
1) Com relação à programação linear inteira (PLI), marque a alterna�va correta:
a) PLI são programações lineares nas quais qualquer variável pode, ou não, assumir
valores inteiros.
b) Os algoritmos de PLI apresentam uma vantagem, que é a sua consistência na
resolução de problemas com valores inteiros.
c) Em geral, as aplicações de PLI possuem apenas uma categoria, que é a categoria
transformada.
d) As variáveis são naturalmente inteiras e podem assumir valores binários (0 ou 1)
ou discretos gerais. Essa é uma caracterís�ca da categoria transformada.
e) Em PLI, na categoria transformada, o problema original, que pode ou não
envolver quaisquer variáveis inteiras, é intratável anali�camente.


03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 19/22
2) Quanto a aplicações de programação linear inteira (PLI), analise as alterna�vas a
seguir e marque a afirma�va correta.
a) Os problemas de cobertura são os relacionados a decisões sobre o inves�mento
ou não em projetos individuais.
b) Os problemas de orçamento de capital em geral estão relacionados a instalações
que oferecem serviços sobrepostos a várias localidades.
c) Os problemas de cobertura abordam situações em que a a�vidade econômica
implica em dois �pos de custos: uma taxa inicial “fixa” e um custo variável.
d) Há modelos de problemas de restrições ou-ou e se-então, em que a
transformação não muda a natureza de “ou” ou de “dependência” das restrições.
e) Os problemas de carga fixa são caracterizados pelas variáveis xj, j = 1,2,...,n são
binárias. Os coeficientes do lado esquerdo das restrições são 0 ou 1. O lado direito
de cada restrição é da forma (≥ 1). A função obje�vo minimiza c1x1 + c2x2 + ... +
cnxn, em que cj > 0 para todo j = 1, 2, ..., n.
3) Com relação aos algoritmos de programação inteira, marque a alterna�va correta:
a) Para todo problema de PLI existe um problema de programação linear
correspondente no qual as restrições de não fracionariedade são man�das.
b) Uma possível abordagem para a solução de problemas de PLI é resolver seusproblemas correspondentes “relaxados” sem arredondar as variáveis de decisão
para o maior ou menor inteiro mais próximo.
c) Dois métodos gerais foram desenvolvidos para gerar as restrições especiais na
etapa 3: o método branch-and-bound (B&B) e o método de planos de corte.
d) Os métodos branch-and-bound (B&B) e de planos de corte são
consistentemente efe�vos em termos computacionais.
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 20/22
e) O algoritmo de corte, ao contrário do algoritmo B&B, não começa na solução
con�nua ó�ma da PL.
4) O método de solução de problemas de programação linear inteira (PLI) u�lizando o
branch-and-bound (B&B) é operacionalizado em cinco passos. Com relação a esses
passos, marque a alterna�va correta: 
a) O passo 1 é a escolha de uma variável de decisão fracionária em z* do PIR.
b) O passo 2 é escolher um SP.
c) O passo 3 é resolver o PLI relaxado.
d) O passo 4 é repe�r o passo 3 usando SP2 e a variável de decisão fracionária x1.
e) O passo 5 é repe�r o passo 3 usando SP5 e a variável de decisão fracionária x1.
5) Ainda sobre aspectos gerais que envolvem a programação linear inteira (PLI), marque
a alterna�va correta:
a) Nos problemas de PLI, não há a necessidade de algumas ou todas as variáveis de
decisão terem de se restringir a valores inteiros.
b) Há poucas aplicações que envolvem decisões sim-ou-não.
c) A programação linear inteira é uma das técnicas de pesquisa operacional (PO)
menos u�lizadas.
d) Problemas de PLI são muito mais fáceis pelo fato de não haver restrição de
inteiros; portanto, os algoritmos disponíveis para programação inteira são, em
geral, consideravelmente mais eficientes que o método simplex.
e) O progresso na capacidade de resolver alguns problemas de PLI se deve a uma
combinação de três fatores: melhorias impressionantes nos algoritmos de PLI,
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 21/22
melhorias notáveis nos algoritmos de programação linear usados internamente nos
algoritmos de PLI e a grande aceleração no desenvolvimento dos computadores.
NA PRÁTICA
Veja a aplicação prá�ca da programação linear inteira (PLI):
Carlos é dono de uma pequena fábrica de pães e u�liza uma única máquina para processar
três tarefas. O empresário possui clientes grandes, que cobram multa caso a entrega seja
feito com atraso. Sendo assim, ele precisa calcular a sequência que resulte na multa
mínima por atraso para o processamento das três tarefas.
Conteúdo disponível na plataforma virtual de ensino. Con�ra!
SAIBA +
Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do
professor:
Programação linear - soluções inteiras
Conteúdo disponível na plataforma virtual de ensino. Con�ra!
Simulação e técnicas da computação evolucionária aplicadas a problemas de programação
linear inteira mista.
Conteúdo disponível na plataforma virtual de ensino. Con�ra!
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à pesquisa operacional. 9. ed. Porto Alegre:
AMGH, 2012. 1028p


03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15300159 22/22
Conteúdo disponível na plataforma virtual de ensino. Con�ra!