Pesquisa Operacional
na Tomada de Decisões
Programação Inteira
2ª Edição
Capítulo 6
© Gerson Lachtermacher,2005
Conteúdos do Capítulo
 Programação Inteira






Problema Relaxado
Solução Gráfica
Solução por Enumeração
Algoritmo de Branch-And-Bound
Solução Excel
Solução no Lindo
 Caso LCL Tecnologia S.A.
 Variáveis Binárias e Condições Lógicas
 Caso LCL Equipamentos S.A.
Capítulo 6
Programação Inteira
 São problemas de programação matemática em que a
função objetivo, bem como as restrições, são lineares,
porém uma ou mais variáveis de decisão podem apenas
assumir valores inteiros.
 Esse problema pode apresentar dois tipos básicos:


Programação Inteira Total - onde todas as variáveis de
decisão são do tipo inteiro.
Programação Inteira Mista - onde apenas uma parte das
variáveis são do tipo inteiro, enquanto outras são do tipo real
Capítulo 6
Programação Inteira
 A primeira idéia que pode vir à mente é resolver o
problema como se fosse um problema de programação
linear e arredondar os valores ótimos encontrados para
cada uma das variáveis de decisão inteiras.
 Para problemas de grande porte, isto geralmente gerará
uma solução aceitável (próxima do ótimo real) sem a
violação de nenhuma das restrições.
 Para problemas menores, esse tipo de procedimento
poderá nos levar a soluções inviáveis ou não ótimas.
Capítulo 6
Programação Inteira
Problema Relaxado
 A todo problema de programação inteira está associado
um problema com a mesma função-objetivo e as
mesmas restrições, com exceção da condição de
variáveis inteiras. A esse problema se dá o nome de
Problema Relaxado
Capítulo 6
Programação Inteira
Solução Gráfica
Max 18 x1 + 6 x2
s.t.
x1 + x2  5
(4)
(1)
(2)
(3)
42.8 x1 + 100 x2  800 (2)
20 x1 + 6 x2  142 (3)
30 x1 + 10 x2  135 (4)
x1 - 3 x2  0 (5)
x1 , x2  0
Capítulo 6
e inteiros
(1)
(5)
Programação Inteira
Solução Gráfica
Max 18 x1 + 6 x2
s. t . x1 + x2  5
42.8 x1 + 100 x2  800
20 x1 + 6 x2  142
30 x1 + 10 x2  135
x1 - 3x2  0
x1 , x2  0 e inteiros
Capítulo 6
x2
Solução Ótima para
LP Relaxado
(5,28 ; 5,74)
x1
Programação Inteira
Solução Gráfica
Solução Aproximada do
LP Relaxado Ótimo
x2
(5 ; 5)
(5,28 ; 5,74)
Solução Ótima para
LP Relaxado
(5,28 ; 5,74)
Solução Ótima
para Problema
Inteiro
x1
Capítulo 6
(6 ; 3)
Programação Inteira
LP Relaxado
 Em um problema de MAXIMIZAÇÃO, o valor ótimo da
função-objetivo, do Problema Relaxado, sempre
representa um limite superior ao respectivo Problema
Inteiro.
 Em um problema de MINIMIZAÇÃO, o valor ótimo da
função-objetivo, do Problema Relaxado, sempre
representa um limite inferior ao respectivo Problema
Inteiro.
Capítulo 6
Programação Inteira
LP Relaxado
 Nenhum ponto inteiro vizinho
ao ponto ótimo do problema
relaxado é necessariamente
viável.
 Mesmo que um dos vizinhos
seja viável.


Não é necessariamente o
ponto ótimo inteiro.
Não é obrigatoriamente uma
solução aceitável.
x2
Solução
Ótima para
LP Relaxado
Solução
Ótima para
Prog.Inteira
x1
Capítulo 6
Programação Inteira
Solução por Enumeração
 Uma idéia que pode resultar em uma solução para um
problema de programação inteira é a de se enumerar
todas as possíveis soluções.
 De forma exaustiva, o valor da função-objetivo é
calculado para todas as soluções viáveis e é escolhido
aquele que apresente o maior valor (no caso de
maximização) ou o menor valor (no caso de
minimização).
Capítulo 6
Programação Inteira
Solução por Enumeração
 O problema com essa tática de solução está no fato de
que ela só consegue ser aplicada a problemas pequenos.
 O número de combinações possíveis de soluções cresce
de forma exponencial, isto é de forma muito rápida.

Ex.: Um ILP com 100 variáveis de decisão do tipo binárias
(assumem 0 ou 1) terá até 2100 soluções viáveis, isto é, 1,27 x
1030 soluções possíveis.
Capítulo 6
Programação Inteira
Algoritmo de Branch-And-Bound
 Algoritmo de Branch-And-Bound é mais utilizado atualmente
para resolução de problemas do tipo ILP ou MILP.
 É uma metodologia geral para solução de ILP e MILP, e existem
diversas variantes para tratar diversos tipos de problemas
específicos.
 A idéia geral é a de se dividir o conjunto de soluções viáveis em
subconjuntos sem interseções entre si, calculando-se os limites
superior e inferior para cada subconjunto, e então eliminando
certos subconjuntos de acordo com regras pré estabelecidas.
Capítulo 6
Programação Inteira
Algoritmo de Branch-And-Bound
 Comparativamente ao LP correspondente, o IP levará
muito mais tempo para obter um valor ótimo. Isso está
ligado ao fato que diversos problemas de LP são
resolvidos sucessivamente para se obter a solução de
um IP.
 Se o problema for interrompido no meio do processo
uma solução aproximada do problema inteiro pode ser
gerada.
Capítulo 6
Programação Inteira
Algoritmo de Branch-And-Bound
 A solução obtida num problema IPL ou MIPL



Sem análise de sensibilidade.
 Deve ser efetuada alterando-se o problema e obtendo-se
nova solução.
Não provê informação similar ao preço de sombra.
Muitos softwares que realizam programação inteira são parte
integrante de pacotes de programação linear e produzem
análise de sensibilidade, independente desta não ter valor no
âmbito de programação inteira.
Capítulo 6
Usando Solver do Excel
Definindo Variáveis Inteiras e Binárias
Capítulo 6
Lindo
Variáveis Inteiras e Binárias
 Os comandos adicionais abaixo são colocados após o
comando END ao final das restrições:
 FREE <Variável> - Remove os limites de não
negatividade imposta a todas as variáveis por default.
 GIN <Variável> - Faz a <Variável> uma variável
inteira geral.
 INT <Variável> - Faz a <Variável> uma variável
inteira binária.
Capítulo 6
Problema de Orçamento de Capital
Caso LCL Tecnologia S/A
 A LCL Tecnologia S/A tem que planejar seus gastos em P&D. A
empresa pré-selecionou 4 projetos e deve escolher dentre esses
quais deve priorizar em função de restrições orçamentárias. Os
dados relevantes encontram-se na tabela abaixo.
Capital Requerido em mil R$
NPV(8%)
(mil R$)
Ano 1
Ano 2
Ano 3
Ano 4
Ano 5
$105.99
70
15
0
20
20
2
$128.90
3
$136.14
4
$117.38
Capital Disponível
80
90
50
200
20
20
30
70
25
0
40
70
15
30
0
70
10
20
20
70
Proj.
1
Capítulo 6
Caso LCL Tecnologia S/A
 Variáveis de Decisão
1 , se o projeto i for selecionad o

Xi  
 i  1,2,3,4
0 , se o projeto i não for selecionad o
 Função Objetivo = Maximizar o somatório NPV
Max 105.99 X 1 + 128.90 X 2 + 136.14 X 3 + 117.38 X 4
Capítulo 6
Caso LCL Tecnologia S/A
 Restrições Orçamentárias
70 X 1 + 80 X 2 + 90 X 3 + 50 X 4  200
- Ano 1
15 X 1 + 20 X 2 + 20 X 3 + 30 X 4  70
- Ano 2
25 X 2 + 40 X 4  70
- Ano 3
20 X 1 + 15 X 2 + 30 X 3  70
- Ano 4
20 X 1 + 10 X 2 + 20 X 3 + 20 X 4  70
- Ano 5
Capítulo 6
Caso LCL Tecnologia S/A
O Modelo
Max 105.99 X 1 + 128.90 X 2 + 136.14 X 3 + 117.38 X 4
st
70 X 1 + 80 X 2 + 90 X 3 + 50 X 4  200
- Ano 1
15 X 1 + 20 X 2 + 20 X 3 + 30 X 4  70
- Ano 2
25 X 2 + 40 X 4  70
- Ano 3
20 X 1 + 15 X 2 + 30 X 3  70
- Ano 4
20 X 1 + 10 X 2 + 20 X 3 + 20 X 4  70
- Ano 5
X 1; X 2 ; X 3 ; X 4  0
Capítulo 6
Caso LCL Tecnologia S/A
Solver do Excel
Capítulo 6
Caso LCL Tecnologia S/A
Solver do Excel
Capítulo 6
Caso LCL Tecnologia S/A
Solver do Excel
Capítulo 6
Variáveis Binárias e
Condições Lógicas
 As variáveis binárias também se prestam a selecionar
alternativas que sejam condicionais.
 No exemplo anterior imagine que não mais de um dos
projetos 1, 3 e 4 pudesse ser selecionado. Deveríamos
então adicionar: X 1 + X 3 + X 4  1
 Se apenas um dos projetos e apenas um dos projetos 1,
2 e 4 tivesse que ser escolhido obrigatoriamente,
deveríamos incluir: X 1 + X 2 + X 4  1
Capítulo 6
Variáveis Binárias e
Condições Lógicas
 Imagine agora que o projeto 1 dependa de uma
tecnologia que deve ser desenvolvida pelo projeto 2,
isto é, o projeto 1 só pode ser aprovado se e somente se
o projeto 2 for aceito. Deveríamos então incluir:
 X 1  0, X 2  0  nenhum dos projetos aceitos

 X 1  1, X 2  1  ambos os projetos aceitos
X 1 - X 2  0
 X 1  0, X 2  1  apenas o projeto 2 foi aceito
 X  1, X  0  inviável
2
 1
Capítulo 6
Caso LCL Equipamentos S.A.
 A LCL Equipamentos S.A. produz três tipos de furadeiras que
necessitam de tempos diferentes na linha de montagem. Para que
cada tipo de furadeira seja fabricada, um custo de preparação da
fabrica é incorrido. Suponha que todas as furadeiras do mesmo
tipo serão produzidas de uma só vez (apenas uma preparação por
tipo). Abaixo os dados relevantes à análise do problema.
Montagem
Pintura
Lucro Unitário
Preparação
Capítulo 6
Tipo 1
Tipo 2
Tipo 3
Total Disponível
2h/unid
3h/unid
R$50
R$5.000
3h/unid
2h/unid
R$60
R$4.000
2,5h/unid
2,5h/unid
R$65
R$3.000
600h
500h
Caso LCL Equipamentos S.A.
Variáveis Binárias
 Variáveis de Decisão
X i  Quantidade a ser produzida do produto i (i  1,2,3)
1, se X i  0
Yi  
i  1,2,3
 0, se X i  0
 Função Objetivo
Max 50 X1 + 60 X 2 + 65X 3 - 5000Y1 - 4000Y2 - 3000Y3
Capítulo 6
Caso LCL Equipamentos S.A.
Variáveis Binárias
 Restrições de Produção
2 X 1 + 3 X 2 + 2,5 X 3  600
3 X 1 + 2 X 2 + 2,5 X 3  500
 Restrições de ligação de Variáveis
X 1  600Y1
X 2  600Y2
X 3  600Y3
Obs : 600 é um nº que é grande o suficiente .
Capítulo 6
Caso LCL Equipamentos S.A.
Variáveis Binárias
=B7*B10
Capítulo 6
Caso LCL Equipamentos S.A.
Variáveis Binárias
Capítulo 6
Caso LCL Equipamentos S.A.
Variáveis Binárias
Capítulo 6