Aula 5
Programação Inteira
Curso de Administração
Prof: André Marques Cavalcanti
5. Programação Inteira Conceitos
Resolução gráfica e suas limitaçõesAlgoritmo branch-and-boundResolução de PI usando o Excel
Problemas de PLIProblemas de PLI
...)...,(
:onde e inteiros são ...,
)...,(
)...,(
)...,(
:a sujeito
)...,(max(min)
21121121
221121
21
2
1
21
212
211
21
niniiin
nnn
n
nnm
n
n
n
xcxaxaxaxxxg
xc...xcxc)...x,xf(x
xxx
b
b
b
xxxg
xxxg
xxxg
xxxfz
O PLI é aquele que tem uma ou mais variáveis de decisão inteiras. São apresentados em dois tipos básicos: Programação Inteira total: todas as variáveis de decisão são do tipo inteira; Programação Inteira mista: uma parte das variáveis de decisão são inteiras
Quando o problema envolve apenas duas variáveis de decisão, a solução ótima de um problema de PLI pode ser encontrado graficamente.
No caso de um PLI real o conjunto de soluções viáveis não incluiria a solução do problema relaxado
Considere o PLIConsidere o PLI
inteiros são ,
0,
2446
1242
:a sujeito
0,
2446
1242
:a sujeito
33max 33max
relaxado Problema
21
21
21
21
21
21
21
2121
xx
xx
xx
xx
xx
xx
xx
xxzxxz
PLI
x1
x2
21
21
3312
335,13
xxZ
xxZ
Considerações sobre a solução de um PLIConsiderações sobre a solução de um PLI
Pode acontecer que: Nenhum ponto inteiro vizinho ao ponto ótimo relaxado é necessariamente viável
Mesmo que um dos vizinhos seja viável, ele pode não ser necessariamente o ponto ótimo inteiro.
Uma outra forma é testar todas as soluções inteiras e selecionar aquelas que maximizam ou minimizam o problema.
Sabe-se que a solução ótima do problema relaxado é o limite superior da solução inteira (para maximização) e limite inferior para minimização
O algoritmo Branch and boundO algoritmo Branch and boundO algoritmo branch and bound é o procedimento mais utilizado para resolver PLI ou PLIM
Existem diversas variantes desse método para tratamento de tipos de problemas específicos.
A ideia geral é dividir o conjunto de soluções viáveis em subconjuntos sem interseções entre si, calculando o limite inferior e superior para cada subconjunto e eliminar certos subconjuntos de acordo com algumas regras preestabelecidas.
O Algoritmo:
Para um PLI o qual encontrou-se uma solução ótima xj, tal que x´j é não inteira, assim i1<x´j<i2, sendo i1 e i2 dois números inteiros não negativos consecutivos. Segui-se os
seguintes passos:
1- Criar dois novos modelos de programação inteira acrescentando ao problema inicial duas novas restrições xj>=i1 e xj=<i2
2- Encontra-se a solução ótima dos dois novos modelos de PL geral
3- Se algumas das soluções encontradas é não inteira, repete-se os procedimentos 1 e 2 até que não existam mais modelos com soluções ótimas não-inteiras
4- É considerada a solução ótima do problema aquela que leva a função objetivo ao seu maior valor (máx)
Aplicando o algoritmo Branch and boundAplicando o algoritmo Branch and bound
inteiros são ,
0,
2446
124
:a sujeito
33max
problema seguinte oResolver
21
21
21
21
21
xx
xx
xx
xx
xxz
(2,4; 2,4)
Da solução relaxada O limite superior é 14,4 para x1=2,4 e x2=2,4
(2,4; 2,4)
Busca-se a solução para a região de x1=<2 e x1>=3
2 3
Obtém-se x1=2 e x2=2,5 e x1=3 e x2=1,5
2,5
1,5
Árvore Branch-and-bound
X1=2,4 x2=2,4 LSA=14,4X1=2 x2=2,5
LSA=14,4X1=3 x2=1,5
LSA=14,4
x1=<2 X1>=3
inteiros são ,
0,2,
2446124
:a sujeito
33max
problema seguinte oResolver
21
21
21
21
21
21
xx
xxxx
xxxx
xxz
Obtém-se x1=2 e x2=2 e LSA =12
(2,0; 2,0)
Busca-se a solução para a região de x1=<2 e x2=<2
2 3 4
inteiros são ,
0,1,3
2446124
:a sujeito
33max
problema seguinte oResolver
21
21
21
21
21
21
xx
xxxx
xxxx
xxz
(3,33; 1,0)
Busca-se a solução para a região de x1>=3 e x2=<1
2 3 4
Árvore Branch-and-bound
X1=2,4 x2=2,4 LSA=14,4X1=2 x2=2,5
LSA=14,4X1=3 x2=1,5
LSA=14,4
x1=<2 X1>=3
inteiros são ,
0,3 e 2
2446124
:a sujeito
0,2,
2446124
:a sujeito
33max
problema seguinte oResolver
21
21
21
21
21
21
21
21
21
21
xx
xxxx
xxxx
xxxx
xxxx
xxz
Obtém-se x1=2 e x2=2 e SOL =12
(2,0; 2,0)
Busca-se a solução para a região de x1=<2 e x2=<2
2 3 4
(0; 3)
Busca-se a solução para a região de x1>=3 e x2=<1
2 3 4
Obtém-se x1=0 e x2=3 SOL=9
X1=2 x2=2 SOL=12
x2=<2 X2>=3
X1=0 x2=3 SOL=9
Árvore Branch-and-bound
X1=2,4 x2=2,4 LSA=14,4X1=2 x2=2,5
LSA=14,4X1=3 x2=1,5
LSA=14,4
x1=<2 X1>=3
inteiros são ,
0,2 e 3
2446124
:a sujeito
0,1,3
2446124
:a sujeito
33max
problema seguinte oResolver
21
21
21
21
21
21
21
21
21
21
xx
xxxx
xxxx
xxxx
xxxx
xxz
Obtém-se x1=3,33 e x2=1 e SOL =13
(3,33; 1)
Busca-se a solução para a região de x1>=3 e x2=<1
2 3 4
(3; 2)
Busca-se a solução para a região de x1>=3 e x2>=2
2 3 4
Obtém-se para x1=3 e x2=2 a solução é inviável
X1=2 x2=2 SOL=12
x2=<1 X2>=2
Inviável
Árvore Branch-and-bound
X1=2,4 x2=2,4 LSA=14,4X1=2 x2=2,5
LSA=14,4X1=3 x2=1,5
LSA=14,4
x1=<2 X1>=3
inteiros são ,
0,1 e 3
2446124
:a sujeito
0,1,2
2446124
:a sujeito
33max
problema seguinte oResolver
21
21
21
21
21
21
21
21
21
21
xx
xxxx
xxxx
xxxx
xxxx
xxz
Obtém-se x1=2 e x2=1 e SOL =12
(3; 1)
Busca-se a solução para a região de x1<=3 e x2=<1
2 3 4
(4; 0)
Busca-se a solução para a região de x1>=3 e x2=<1
2 3 4
Obtém-se para x1=4 e x2=0 SOL=12
X1=3,33 x2=1 SOL=13
x2=<1
X2>=2
InviávelX1=3 x2=1
SOL=12
X1<=3
X1=4 x2=0 SOL=12
X1>=4
Árvore Branch-and-bound
X1=2,4 x2=2,4 LSA=14,4X1=2 x2=2,5
LSA=14,4X1=3 x2=1,5
LSA=14,4
x1=<2 X1>=3
X1=3,33 x2=1 SOL=13
x2=<1
X2>=2
InviávelX1=3 x2=1
SOL=12
X1<=3
X1=4 x2=0 SOL=12
X1>=4
X1=2 x2=2,5 LSA=14,4
x1=<2
X1=2 x2=2 SOL=12
x2=<2 X2>=3
X1=0 x2=3
SOL=9
Como a solução x1=4 e x2=0 representa um único ponto no conjunto de soluções viáveis ele é tomado como a solução ótima
Observar que a árvore só possui ramos com soluções inteiras ou inviáveis isso finaliza o algoritmo
Observação: Inexistência de análise de sensibilidade.
Muitos softwares que resolvem PLI fazem parte do pacote de PL e realizam análise de sensibilidade independente que para o caso de PLI deve ser
desconsiderado.
Aplicação usando o Excel Aplicação usando o Excel A LCL tecnologia tem de planejar seus gastos em P&D para os próximos 5 anos.
A empresa pré-selecionou quatro projetos e deve escolher quais priorizar. Os dados relevantes ao problema encontram-se na tabela a seguir. Nela estão as disponibilidades de capital a ser alocado em cada um dos anos, bem como o
valor presente líquido de cada projeto. Como todos os projetos apresentam VPL positivo, todos seriam candidatos. Vale notar que existe uma limitação no valor a
ser investido anualmente
Capital requerido em mil R$Capital requerido em mil R$
ProjProj VPL(8%) VPL(8%) (Mil R$)(Mil R$)
Ano 1Ano 1 Ano2Ano2 Ano 3Ano 3 Ano 4Ano 4 Ano5Ano5
11 105,09105,09 7070 1515 00 2020 2020
22 128,00128,00 8080 2020 2525 1515 1010
33 136,14136,14 9090 2020 00 3030 2020
44 117,38117,38 5050 3030 4040 00 2020
Cap. disponívelCap. disponível 200200 7070 7070 7070 7070
Variável de decisão xi =0 ou xi=1
ModelandoModelando
binárias são ,...
7020201020
700301520
704002507030202015
20050908070
:a sujeito
38,11714,13650,12899,105max
41
4321
4321
4321
4321
4321
4321
xx
xxxx
xxxx
xxxxxxxx
xxxx
xxxxz
Outro exemploOutro exemploCaso LCL Equipamentos: A LCL equipamentos produz três tipos de Caso LCL Equipamentos: A LCL equipamentos produz três tipos de
furadeiras, que necessitam de tempos diferentes na linha de furadeiras, que necessitam de tempos diferentes na linha de montagem. Para que cada tipo de furadeira seja fabricado, um custo montagem. Para que cada tipo de furadeira seja fabricado, um custo de preparação da fábrica é incorrido (ajustes que devem ser efetuados de preparação da fábrica é incorrido (ajustes que devem ser efetuados na linha de montagem). Suponha que todas as furadeiras do mesmo na linha de montagem). Suponha que todas as furadeiras do mesmo tipo sejam produzidas de uma só vez (apenas uma preparação por tipo sejam produzidas de uma só vez (apenas uma preparação por tipo). Os dados relevantes à análise do problema encontram-se na tipo). Os dados relevantes à análise do problema encontram-se na tabela. Ache quantidades a serem fabricadas para maximizar o lucro tabela. Ache quantidades a serem fabricadas para maximizar o lucro do próximo mês.furadeirasdo próximo mês.furadeiras
TrimestreTrimestre Tipo1Tipo1 Tipo 2Tipo 2 Tipo 3 Tipo 3 Total disponívelTotal disponível
Montagem hMontagem h 22 33 2,52,5 600600
Pintura hPintura h 33 22 2,52,5 500500
Lucro unitário R$Lucro unitário R$ 5050 6060 6565
Preparação R$Preparação R$ 50005000 40004000 30003000
O modeloO modelo
0 xse 0
0 xse 1
600
500
006
6005,2 32 :a sujeito
300040005000656050max
1
1
33
22
11
321
321321
iy
yx
yx
yx
xxx
yyyxxxz