Programação Linear Inteira

Prévia do material em texto

Programação Linear Inteira 
APRESENTAÇÃO
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 utilizadas.
Nesta Unidade de Aprendizagem, você vai conhecer características importantes da programação 
linear inteira, suas principais aplicações e os algoritmos mais utilizados para resolver problemas 
de PLI.
Bons estudos.
Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:
Identificar as características gerais da programação linear inteira.•
Determinar a alocação de recursos a atividades.•
Descrever uma programação linear inteira.•
DESAFIO
Você trabalha em uma confeitaria que produz dois tipos 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, praticamente 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 interativo disponível na plataforma de ensino!
 
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 Linear Inteira, do 
livro "Pesquisa Operacional", algumas aplicações que demonstram a ampla utilização de PLI na 
prática.
Boa leitura. 
PESQUISA
OPERACIONAL
Organizador: 
Rodrigo Rodrigues
Catalogação na publicação: Poliana Sanchez de Araujo – CRB 10/2094
R696p Rodrigues, Rodrigo.
 Pesquisa operacional / Rodrigo Rodrigues. – 
 Porto Alegre : SAGAH, 2017.
 121 p. : il. ; 22,5 cm. 
 ISBN 978-85-9502-004-7
 1. Pesquisa operacional – Engenharia de 
 produção. I. Título. 
CDU 658.5
Programação linear inteira
Objetivos de aprendizagem
Ao final deste texto, você deve apresentar os seguintes aprendizados:
 � Identificar as características gerais da programação linear inteira.
 � Determinar a alocação de recursos a atividades.
 � Descrever uma programação linear inteira.
Introdução
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 
utilizadas.
Neste texto, você vai conhecer características importantes da pro-
gramação linear inteira, suas principais aplicações e os algoritmos mais 
utilizados para resolver problemas de PLI. 
Programação linear inteira: 
características gerais
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. 
Você vai ver algumas aplicações que demonstram a ampla utilização de PLI na 
prática. Vai ver, também, dois algoritmos proeminentes de PLI: branch-and-
-bound (B&B) e planos de corte. Dos algoritmos, o B&B é o mais eficiente
em termos de cálculo. Na realidade, praticamente todos os códigos comerciais 
têm suas raízes no B&B (TAHA, 2008).
Os algoritmos de PLI apresentam uma desvantagem, que é a sua falta de 
consistência na resolução de problemas com números inteiros. Embora seja 
comprovado teoricamente que esses algoritmos convergem em um número 
finito de iterações, sua implantação em computador (com seu inerente erro de 
arredondamento) é uma experiência diferente. Não se esqueça disso quando 
estudar os algoritmos PLI.
Programação linear inteira: 
recursos e aplicações
Em geral, as aplicações possuem duas categorias: direta e transformada. Na 
categoria direta, as variáveis são naturalmente inteiras e podem assumir valores 
binários (0 ou 1) ou discretos gerais. O problema pode consistir em determinar, 
por exemplo, se um projeto será ou não selecionado para execução (binário) 
ou achar o número ótimo de máquinas necessárias para executar uma tarefa 
(valor discreto geral). Na categoria transformada, o problema original, que pode 
ou não envolver quaisquer variáveis inteiras, é intratável analiticamente. Para 
transformá-lo em tratável, são usadas variáveis auxiliares inteiras (em geral, 
binárias). Segundo Taha (2008), a natureza “ou” das restrições é que torna o 
problema analiticamente intratável, porque todos os algoritmos matemáticos 
de programação matemática tratam apenas de restrições “e”. A situação é 
remediada usando variáveis binárias auxiliares para transformar as restrições 
“ou” em restrições “e” equivalentes.
Convencionou-se a definição de um problema inteiro puro como aquele que 
tem todas as variáveis inteiras. Caso trate de variáveis contínuas e inteiras, é 
um problema de programação inteira mista.
Orçamento de capital
O nosso viés, agora, é com relação a decisões sobre o investimento ou não 
em projetos individuais. A decisão é influenciada pelo orçamento limitado e 
pelas prioridades na execução dos projetos.
 � Exemplo 1: seleção de projeto
Em uma projeção de planejamento de três anos, cinco projetos estão sob 
avaliação. A Tabela 1 apresenta os resultados esperados para cada projeto e 
os investimentos anuais associados.
Pesquisa operacional94
Desembolsos (milhões $)/ano
Projeto 1 2 3
Retornos 
(milhões $)
1
2
3
4
5
5
4
3
7
8
1
7
9
4
6
8
10
2
1
10
20
40
20
15
30
Fundos 
disponíveis 
(milhões $)
25 25 25
Tabela1. Retornos esperados.
Quais projetos devem ser selecionados na projeção de três anos? O problema 
se reduz a uma decisão “sim-não” para cada projeto.
Definimos a variável binária xj, como:
 �
O problema de PLI é:
Maximizar z = 20x1 + 40x2 + 15x4 + 30x5
Sujeito a:
5x1 + 4x2 + 3x3 + 7x4 + 8x5 ≤ 25
x1 + 7x2 + 9x3 + 4x4 + 6x5 ≤ 25
8x1 + 10x2 + 2x3 + x4 + 10x5 ≤ 25
x1, x2, x3, x4, x5 = (0,1)
A solução inteira ótima, que pode ser obtida pelo Excel Solver ou outros 
programas, é x1 = x2 = x3 = x4 = 1, x5 = 0, com z = 95 (milhões $). A solução 
mostra que todos os projetos, com exceção do 5, devem ser selecionados.
É interessante comparar a solução contínua de PL com a solução de PLI. 
A PL ótima, obtida pela substituição de xj = (0,1) por 0 ≤ x ≤ 1 para todo j, dá 
como resultado x1 = 0,5789, x2 = x3 = x4 = 1, x5 = 0,7368 e z = 108,68 (milhões 
95Programação linear inteira
$). Não há sentido para a solução devido a duas das variáveis que assumem 
valores fracionários. Podemos arredondar a solução para o inteiro mais pró-
ximo, que dá x1 = x5 = 1. Contudo, a solução resultante é inviável porque as 
restrições são violadas. Mais importante, o conceito de arredondamento não 
tem sentido aqui, porque xj representa uma decisão “sim-não”.
Problema de cobertura
Nos problemasde cobertura, várias instalações oferecem serviços sobrepostos 
a várias localidades. O objetivo é identificar o número mínimo de instalações 
que atenderão às necessidades de cada localidade. Por exemplo, estações de 
tratamento de água podem ser construídas em vários locais, sendo que cada 
uma atenderia a um conjunto diferente de cidades. A sobreposição surge 
quando uma determinada cidade poderá ser atendida pelos serviços de mais 
de uma estação.
 � Exemplo 2: instalação de telefones de segurança
Outro exemplo apresentado por Taha (2008) é de um departamento de 
segurança de uma universidade que, para promover a segurança no campus, 
iniciou um processo de instalação de telefones de emergência em locais se-
lecionados. O departamento quer instalar o número mínimo de telefones, 
contanto que cada uma das principais ruas do campus seja atendida por, no 
mínimo, um telefone. A Figura 1 mostra o mapa do campus.
É conveniente colocar os telefones em cruzamentos de ruas, de modo que 
cada um atenda no mínimo duas ruas. A Figura 1 mostra que o leiaute das 
ruas requer um máximo de oito localizações de telefones.
Defina-se
 �
As restrições do problema requerem a instalação de, no mínimo, um telefone 
em cada uma das 11 ruas (A a K). Veja como fica o modelo:
Minimizar z = x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8
Pesquisa operacional96
Sujeito a
A solução ótima do problema requer instalar quatro telefones nos cru-
zamentos 1, 2, 5 e 7. Mais especificamente, os problemas de cobertura são 
caracterizados por:
1. As variáveis xj, j = 1,2,...,n são binárias.
2. Os coeficientes do lado esquerdo das restrições são 0 ou 1.
3. O lado direito de cada restrição é da forma (≥ 1).
Figura 1. Mapa de ruas do campus da universidade.
97Programação linear inteira
4. A função objetivo minimiza c1x1 + c2x2 + ... + cnxn, em que cj > 0 para 
todo j = 1, 2, ..., n. Nesse exemplo, cj = 1 para todo j. Se cj representar o 
custo de instalação no local j, então esses coeficientes podem assumir 
valores que não sejam 1. Variações do problema de cobertura incluem 
condições adicionais de lado.
Problema de carga fixa
O problema de carga fixa aborda situações em que a atividade econômica 
implica em dois tipos de custos: uma taxa inicial “fixa”, que deve ser incidida 
no início da atividade, e um custo variável, que é diretamente proporcional ao 
nível da atividade. Por exemplo, a preparação e o ajuste inicial das ferramentas 
de uma máquina, antes de iniciar a produção, implicam em um custo fixo de 
preparação independentemente da quantidade de unidades fabricadas. Uma vez 
concluída, o custo da mão de obra e do material é proporcional à quantidade 
produzida. Dado que F é a carga fixa, c é o custo unitário variável, e x é o 
nível de produção, a função custo é expressa como:
A função C (x) é intratável analiticamente porque envolve uma desconti-
nuidade em x = 0.
Restrições ou-ou e se-então
Usamos variáveis binárias, no problema de carga fixa, para lidar com descon-
tinuidade na função objetivo custo.
Em muitos modelos, as restrições não são satisfeitas ao mesmo tempo (ou-
-ou) ou são dependentes (se-então), novamente usando variáveis binárias. A 
transformação não muda a natureza de “ou” ou de “dependência” das restrições. 
Ela simplesmente usa um truque matemático para apresentá-las no formato 
desejado de restrições “e” (TAHA, 2008).
Pesquisa operacional98
Programação linear inteira: resolução 
de problemas por meio de algoritmos 
Problemas de PLI são muito mais difíceis do que seriam sem a restrição de 
números inteiros, por isso, os algoritmos disponíveis para programação inteira 
são, em geral, menos eficientes que o método simplex. Contudo, ao longo das 
últimas décadas houve progresso na capacidade de resolver alguns (mas não 
todos) problemas de PLI extensos, com dezenas ou até mesmo centenas de 
milhares de variáveis inteiras (HILLIER; LIEBERMAN, 2013).
Para todo problema de PLI existe um problema de programação linear 
correspondente no qual as restrições de não fracionariedade são removidas 
(ou relaxadas). Veja alguns resultados: 
 � Espaço de soluções viáveis do PLI ⊆ Espaço de soluções viáveis do 
PLI “relaxado”. 
 � Valor ótimo de z do PLI ≤ Valor ótimo do PI relaxado.
Uma possível abordagem para a solução de problemas de PLI é resolver seus 
problemas correspondentes “relaxados” e arredondar as variáveis de decisão 
para o maior ou menor inteiro mais próximo. No entanto, dois problemas 
podem resultar dessa abordagem: 
 � Os valores arredondados podem resultar em pontos inviáveis no PLI.
 � As soluções resultantes são altamente subótimas.
Os algoritmos de PLI são baseados na exploração do indiscutível sucesso 
computacional da PL. Segundo Taha (2008), a estratégia desses algoritmos 
envolve três etapas:
 � Etapa 1. Relaxe a região de soluções da PLI eliminando a restrição 
inteira imposta a todas as variáveis inteiras e substituindo qualquer 
variável binária y pela faixa contínua 0 ≤ y ≤ 1. O resultado da relaxação 
é uma PL normal.
 � Etapa 2. Resolva a PL e identifique a solução ótima contínua.
 � Etapa 3. Começando do ponto ótimo contínuo, adicione restrições 
especiais que modifiquem interativamente a região de soluções da PL 
de maneira que, a certa altura, resultará em um ponto extremo ótimo 
que satisfaça os requisitos inteiros.
99Programação linear inteira
Dois métodos gerais foram desenvolvidos para gerar as restrições especiais 
na etapa 3:
1. Método branch-and-bound (B&B)
2. Método de planos de corte
Embora nenhum dos dois métodos seja consistentemente efetivo em termos 
computacionais, a experiência mostra que o método B&B é muito mais bem-
-sucedido do que o método de plano de corte.
Método Branch-and-Bound para solução de 
problemas PLIs puros 
Considere o problema de PLI: 
Max z = 8x1 + 5x2 
s.a 
x1 + x2 ≤ 6 
9x1 + 5x2 ≤ 45 
x1 , x2 ≥ 0 x1 , x2 inteiros. 
O método de solução de problemas de PI utilizando o branch-and-bound 
(B&B) é operacionalizado em cinco passos, descritos a seguir.
1. Comece resolvendo o PLI relaxado. Se a solução ótima for inteira, esta 
é a solução do PLI. Quando esse não for o caso, a solução ótima do 
IPR (problema de programação inteira relaxado) é o limite superior da 
solução ótima do PLI. A solução ótima desse exemplo de IPR é: 
z* = 165/4 x1 = 15/4 x2 = 9/4
2. Escolha uma variável de decisão fracionária em z* do IPR, por exemplo, 
x1 = 15/4. O PLI admite valores de x1 ≤ 3 ou x1 ≥ 4, mas não em 3 < x1 
< 4. Crie dois subproblemas a partir de x1: SP2: SP1 + restrição x1 ≥ 4. 
SP3: SP1 + Restrição x1 ≤ 
Pesquisa operacional100
A sigla SP designa subproblema. O problema designado por SP1 é o próprio problema 
de PLI.
3. Escolha qualquer SP listado no passo anterior e resolva como se fosse 
um problema de programação linear. Digamos SP2, com solução ótima 
z* = 41, x1 = 4 e x2 = 9/5. Os resultados obtidos até agora podem ser 
apresentados na forma de uma árvore hierárquica.
4. Repita o procedimento em (3) usando o SP2 e a variável de decisão 
fracionária x2 = 9/5. Os subproblemas resultantes são: SP4: SP1 + x1 
≥ 4 + x2 ≥ 2 ou SP2 + x2 ≥ 2. SP5: SP1 + x1 ≥ 4 + x2 ≤ 1 ou SP2 + x2 
≤ 1. Temos três problemas que podem ser resolvidos: SP3, SP4 e SP5. 
Escolhemos entre eles um para resolução, por exemplo, SP4. SP4 não 
apresenta soluções viáveis, não podendo, assim, gerar uma solução 
ótima para o problema de PLI. Assim, diz-se que esse nodo da árvore 
foi terminado. Entre os SPs não resolvidos, escolhe-se o mais recente, 
SP5. Veja a solução na árvore do problema a seguir. 
101Programação linear inteira
5. Repita o procedimento em (3) usando SP5 e a variável de decisão fracio-
nária x1. Os subproblemas resultantes são: SP6: SP5 + x1 ≥ 5. SP7: SP5 
+ x1 ≤ 4. Três SPs podem ser resolvidos: SP3, SP6 e SP7. Escolhe-se, 
aleatoriamente, um dos mais recentes, SP7, por exemplo. A solução só 
possui valores inteiros para a variável de decisão, podendo ser inter-
pretada como uma solução candidata ou um limite inferior no valorótimo do problema de PLI.
O Solver pode ser usado para obter a solução dos diferentes subproblemas usando 
as opções adicionar/modificar/excluir na caixa de diálogo “Parâmetros do Solver”.
Pesquisa operacional102
Algoritmo de plano de corte
O algoritmo de corte, a exemplo do algoritmo B&B, também começa na solução 
contínua ótima da PL. Restrições especiais (denominadas corte) são adiciona-
das na região de soluções de uma maneira que resulta em um ponto extremo 
ótimo inteiro. Em geral, na resolução de um problema nesse método é feita 
sua representação em gráfico de como os cortes são usados para produzir uma 
solução inteira e, então, implementa-se a ideia algebricamente (TAHA, 2008).
Mesmo após anos de pesquisa, não há um código de computador que possa 
resolver problemas de PLI de modo consistente. Contudo, dos dois algoritmos 
de solução que vimos, o B&B é o mais confiável. Praticamente todos os 
códigos comerciais de resolução de problemas de PLI são baseados em B&B. 
Em geral, o método de planos de corte é difícil e incerto. 
Segundo Hillier e Lieberman (2013), esse progresso se deve a uma com-
binação de três fatores: melhorias impressionantes nos algoritmos de PLI, 
melhorias notáveis nos algoritmos de programação linear usados internamente 
nos algoritmos de PLI e a grande aceleração no desenvolvimento dos com-
putadores. Contudo, os algoritmos de PLI, ocasionalmente, também falharão 
na resolução de problemas bem menores (até mesmo como uma centena de 
variáveis inteiras). 
103Programação linear inteira
1. Com relação à programação 
linear inteira (PLI), marque 
a alternativa 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ística 
da categoria transformada.
e) Em PLI, na categoria 
transformada, o problema 
original, que pode ou 
não envolver quaisquer 
variáveis inteiras, é intratável 
analiticamente.
2. Quanto a aplicações de 
programação linear inteira (PLI), 
analise as alternativas a seguir e 
marque a afirmativa correta. 
a) Os problemas de cobertura 
são os relacionados a decisões 
sobre o investimento 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 
atividade econômica implica em 
dois tipos 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 objetivo 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 alternativa 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 mantidas.
b) Uma possível abordagem para 
a solução de problemas de 
PLI é resolver seus problemas 
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 efetivos 
Pesquisa operacional104
em termos computacionais.
e) O algoritmo de corte, ao 
contrário do algoritmo B&B, 
não começa na solução 
contínua ótima da PL.
4. O método de solução de problemas 
de programação linear inteira (PLI) 
utilizando o branch-and-bound 
(B&B) é operacionalizado em cinco 
passos. Com relação a esses passos, 
marque a alternativa 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 é repetir o passo 
3 usando SP2 e a variável 
de decisão fracionária x1.
e) O passo 5 é repetir 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 alternativa 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 utilizadas.
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, melhorias notáveis nos 
algoritmos de programação 
linear usados internamente nos 
algoritmos de PLI e a grande 
aceleração no desenvolvimento 
dos computadores.
105Programação linear inteira
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à pesquisa operacional. 9. ed. Porto Alegre: 
AMGH, 2013. E-book. 
TAHA, H. A. Pesquisa operacional: uma visão geral. São Paulo: Pearson Prentice Hall, 2008.
Leitura recomendada
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à pesquisa operacional. 9. ed. Port Alegre: 
AMGH, 2013. E-book. 
Pesquisa operacional106
Encerra aqui o trecho do livro disponibilizado para 
esta Unidade de Aprendizagem. Na Biblioteca Virtual 
da Instituição, você encontra a obra na íntegra.
 
DICA DO PROFESSOR
Nesse vídeo, você vai ver como encontrar a solução ótima para a maximização da receita da 
venda de móveis de uma fábrica, por intermédio de programação linear inteira, utilizando o 
software Lindo.
Conteúdo interativo disponível na plataforma de ensino!
EXERCÍCIOS
1) Com relação à programação linear inteira (PLI), marque a alternativa 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ística da categoria transformada.
E) Em PLI, na categoria transformada, o problema original, que pode ou não envolver 
quaisquer variáveis inteiras, é intratável analiticamente.
2) Quanto a aplicações de programação linear inteira (PLI), analise as alternativas a 
seguir e marque a afirmativa correta. 
Os problemas de cobertura são os relacionados a decisões sobre o investimento ou não em A) 
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 atividade econômica implica em 
dois tipos 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. 
Oscoeficientes do lado esquerdo das restrições são 0 ou 1. O lado direito de cada restrição 
é da forma (≥ 1). A função objetivo 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 alternativa 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 mantidas.
B) Uma possível abordagem para a solução de problemas de PLI é resolver seus problemas 
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 efetivos 
em termos computacionais.
E) O algoritmo de corte, ao contrário do algoritmo B&B, não começa na solução contínua 
ótima da PL.
4) O método de solução de problemas de programação linear inteira (PLI) utilizando o 
branch-and-bound (B&B) é operacionalizado em cinco passos. Com relação a esses 
passos, marque a alternativa 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 é repetir o passo 3 usando SP2 e a variável de decisão fracionária x1.
E) O passo 5 é repetir 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 alternativa 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 
utilizadas.
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, 
D) 
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, 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ática da programação linear inteira (PLI):
Carlos é dono de uma pequena fábrica de pães e utiliza 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.
SAIBA MAIS
Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do 
professor:
Programação linear - soluções inteiras
Conteúdo interativo disponível na plataforma de ensino!
Simulação e técnicas da computação evolucionária aplicadas a problemas de programação 
linear inteira mista.
Conteúdo interativo disponível na plataforma de ensino!
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à pesquisa operacional. 9. ed. Porto 
Alegre: AMGH, 2012. 1028p