PESQUISA

OPERACIONAL

Organizador:
Rodrigo Rodrigues
 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

Catalogação na publicação: Poliana Sanchez de Araujo – CRB 10/2094

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).
94 Pesquisa operacional

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.
 Programação linear inteira 95

Tabela1. Retornos esperados.

Desembolsos (milhões $)/ano

Retornos
Projeto 1 2 3 (milhões $)

1 5 1 8 20
2 4 7 10 40
3 3 9 2 20
4 7 4 1 15
5 8 6 10 30

Fundos 25 25 25
disponíveis
(milhões $)

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
96 Pesquisa operacional

$). 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 problemas de 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
 Programação linear inteira 97

Figura 1. Mapa de ruas do campus da universidade.

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).
98 Pesquisa operacional

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).
 Programação linear inteira 99

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.
100 Pesquisa operacional

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 ≤
 Programação linear inteira 101

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.
102 Pesquisa operacional

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”.
 Programação linear inteira 103

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).
104 Pesquisa operacional

1. Com relação à programação dois tipos de custos: uma taxa

linear inteira (PLI), marque inicial “fixa” e um custo variável.
a alternativa correta: d) Há modelos de problemas de
a) PLI são programações lineares restrições ou-ou e se-então,
nas quais qualquer variável pode, em que a transformação não
ou não, assumir valores inteiros. muda a natureza de “ou” ou de
b) Os algoritmos de PLI apresentam “dependência” das restrições.
uma vantagem, que é a sua e) Os problemas de carga fixa
consistência na resolução de são caracterizados pelas
problemas com valores inteiros. variáveis xj, j = 1,2,...,n são
c) Em geral, as aplicações de PLI binárias. Os coeficientes do
possuem apenas uma categoria, lado esquerdo das restrições
que é a categoria transformada. são 0 ou 1. O lado direito de
d) As variáveis são naturalmente cada restrição é da forma (≥
inteiras e podem assumir valores 1). A função objetivo minimiza
binários (0 ou 1) ou discretos c1x1 + c2x2 + ... + cnxn, em que
gerais. Essa é uma característica cj > 0 para todo j = 1, 2, ..., n.
da categoria transformada. 3. Com relação aos algoritmos de
e) Em PLI, na categoria programação inteira, marque
transformada, o problema a alternativa correta:
original, que pode ou a) Para todo problema de PLI existe
não envolver quaisquer um problema de programação
variáveis inteiras, é intratável linear correspondente no
analiticamente. qual as restrições de não
2. Quanto a aplicações de fracionariedade são mantidas.
programação linear inteira (PLI), b) Uma possível abordagem para
analise as alternativas a seguir e a solução de problemas de
marque a afirmativa correta. PLI é resolver seus problemas
a) Os problemas de cobertura correspondentes “relaxados”
são os relacionados a decisões sem arredondar as variáveis
sobre o investimento ou não de decisão para o maior ou
em projetos individuais. menor inteiro mais próximo.
b) Os problemas de orçamento c) Dois métodos gerais foram
de capital em geral estão desenvolvidos para gerar as
relacionados a instalações que restrições especiais na etapa 3: o
oferecem serviços sobrepostos método branch-and-bound (B&B)
a várias localidades. e o método de planos de corte.
c) Os problemas de cobertura d) Os métodos branch-and-bound
abordam situações em que a (B&B) e de planos de corte são
atividade econômica implica em consistentemente efetivos
 Programação linear inteira 105

em termos computacionais. algumas ou todas as variáveis

e) O algoritmo de corte, ao de decisão terem de se
contrário do algoritmo B&B, restringir a valores inteiros.
não começa na solução b) Há poucas aplicações que
contínua ótima da PL. envolvem decisões sim-ou-não.
4. O método de solução de problemas c) A programação linear
de programação linear inteira (PLI) inteira é uma das técnicas
utilizando o branch-and-bound de pesquisa operacional
(B&B) é operacionalizado em cinco (PO) menos utilizadas.
passos. Com relação a esses passos, d) Problemas de PLI são muito mais
marque a alternativa correta: fáceis pelo fato de não haver
a) O passo 1 é a escolha de restrição de inteiros; portanto,
uma variável de decisão os algoritmos disponíveis para
fracionária em z* do PIR. programação inteira são, em
b) O passo 2 é escolher um SP. geral, consideravelmente mais
c) O passo 3 é resolver eficientes que o método simplex.
o PLI relaxado. e) O progresso na capacidade de
d) O passo 4 é repetir o passo resolver alguns problemas de
3 usando SP2 e a variável PLI se deve a uma combinação
de decisão fracionária x1. de três fatores: melhorias
e) O passo 5 é repetir o passo impressionantes nos algoritmos
3 usando SP5 e a variável de PLI, melhorias notáveis nos
de decisão fracionária x1. algoritmos de programação
5. Ainda sobre aspectos gerais linear usados internamente nos
que envolvem a programação algoritmos de PLI e a grande
linear inteira (PLI), marque aceleração no desenvolvimento
a alternativa correta: dos computadores.
a) Nos problemas de PLI,
não há a necessidade de
106 Pesquisa operacional

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.
 Encerra aqui o trecho do livro disponibilizado para
esta Unidade de Aprendizagem. Na Biblioteca Virtual
da Instituição, você encontra a obra na íntegra.