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