A Capitulo 5 Campus

Programação Inteira Exemplo

( BS ) Maximizar z = x1 +3 x2 sujeito a : x1

≤40 x2 ≤ 60 x2 ≥ 10

x1 + x2 ≥ 20 3 x1 + 2 x2 ≤180 x1≥ 0,x2 ≥ 0

Programação Inteira x2

Solução Gráfica 90

x1 =40

C

60 D

x2 =60

B

x1 + x 2 =20

3x1 + 2x 2 =180

20 E F O

x 1=10

A 20

40

60

x1

Programação Inteira Solução Exaustiva Pontos Examinados

Coordenadas (x1 ,x2)

Valor da função z= x1 + 3x2

A B C D E F

(40,10) (40,30) (20,60) (0,60) (0,20) (10,10)

70 130 200 180 60 40

Programação Inteira Outro Exemplo Maximizar z = x1 +19 x2 sujeito a : x1 + 20 x2 ≤50 x1 + x2 ≤ 20 x1 ,x2 variáveis inteiras

Programação Inteira O Problema da Mochila (PK) n ( PK ) Maximizar z = ∑ c j x j j =1

sujeito a : n

∑w x j =1

j

j

≤b

x j ≥ 0 e inteiro

Programação Inteira O Problema da Mochila Unidimensional n

( PKI ) Maximizar z = ∑ c j x j j =1

sujeito a : n

∑w x j =1

j

j

≤b

x j ∈ {0,1}

j = 1,..., n

Programação Inteira Exemplo Minimizar z = 7 x1 + 10 x2 + 12 x3 + 14 x4 sujeito a : 41x1 + 55 x2 + 60 x3 + 70 x4 ≤ 160

Programação Inteira x1

Árvore de Enumeração

X1 =3

x2 2

X 2=0

x3 6

X3 =0

X3 =1

7

X3 =0

x4 15

16

17

X4 =0

X4 =0

X4 =0

28

Z=21

29

Z=29

30

Z=17

31

Z=21

32

Z=27

33

Z=22

34

Z=26

35

Z=28

36

Z=24

37

Z=20

38

Z=28

39

Z=26

40

Z=24

X 2=1

X1=1

3

X 2=0

X 2=2

8

9

10

X3 =0

X 3=0 X 3=1

18

19

20

X 2=1 X 3=1 1

X1 =0

4

X 2=0

11

X 3=0 X 3=2

X 2=2

X1 =2

5

X 2=0

12

13

X 3=0 X 3=0

X 3=1 X 2=1

14

X 3=0

21

22

23 24

25

26 27

X4 =1

X 4=0 X 4=0 X 4=1 X 4=2 X 4=0 X 4=0

X 4=1 X 4=0

X 4=0

Programação Inteira Problemas Correlatos Subset-Sum Problem Mochila Múltipla 0-1 Mochila 0-1 Multidimensional Mochila Max_Min 0-1 Mochila de Escolha Múltipla Mochila Encapsulada Mochila Decomposta Mochila Multiperíodo

Programação Inteira Branch-and-Bound Maximizar z = 5 x1 + 8 x2 sujeito a : x1 + x2 ≤ 6 5 x1 + 9 x2 ≤ 45 x1 , x2 ∈ Z

+

Programação Inteira Branch-and-Bound Solução Contínua 9 x1 = 4

15 x2 = 4

1 Z= 41 4

Disjuntiva

 15  15 x2 ≥   + 1≥ 4 ou x2 ≤  ≤ 3  4  4

Programação Inteira Solução Gráfica

x2 Soluções Inteiras

A

z=5x1 +8x2

B 5x1 + 9x2 =45 x1 + x2 =6

O

C

x1

Programação Inteira Resultado da Divisão (Branch) x2

(P1 )

A B

(P2 ) O

C

x1

Programação Inteira Árvore de Branch

P0 x1 =2,25 x2 =3,75 z=41,25 x 2≤ 3,0

x2 ≥4,0

P1 x1 =3,0 x2 =3,0 z=39

P2 x1 =1,8 x2 =4,0 z=41 x1 ≥2,0

x 1≤ 1,0

P3 Inviável

P4 x1 =1,0 x2 =4,25 z=40,4 x2 ≥ 5,0 P5 x1 =0 x2 =5 z=40

x 1≤ 4,0 P6 x1 =1,0 x2 =4,0 z=37

Programação Inteira Programação Dinâmica Estágio n+1

Estágio n

Estado Estadonn

Decisão

Estado Estadon+1 n+1

Processo de Decisão

Programação Inteira Programação Dinâmica Princípio de Bellman: Uma política ótima apresenta a propriedade segundo a qual, a despeito das decisões tomadas para assumir um estado particular num certo estágio, as decisões restantes a partir deste estado devem constituir uma política ótima

Programação Inteira Exemplo - Caminho Mais Curto 8

B

E

6

9

4 5 A

5

8

F

J 12

7 3

5 I

13

9 D

H

10 8

C

6

3 11

G

Programação Inteira Exemplo - Caminho Mais Curto 4

2

3 8

B

E

6

9

4 5 A

5

H 8

F

J 12

7 3

5 I

13

9 D

6

10 8

C

1

3 11

G

Programação Inteira Exemplo - Caminho Mais Curto 14

14

2

E

E 8

17

17 F

J

H

H

10

F

I

J

J

13 3 G 8

5

5 I

I

5 8

8

8

12

G

8

8

6

9

H

1

1

5

5

Programação Inteira Exemplo - Caminho Mais Curto 22 B

22

14

8

B

E

3

14 E

6 H 17

15 C

15

F

J

17

5 C

8

F

11

G

7

I

9 D 19

G

D

8

19

8

Programação Inteira Exemplo - Caminho Mais Curto B

B

4

15 A

15

20 C

22

E

H 20

4

F

J

A

5

C

3

I 5 D

D

G 8

19

Programação Inteira Heurísticas

Procedimentos Procedimentos Aproximativos Aproximativos

Heurísticas Heurísticas

Relaxações Relaxações

Estocásticas Estocásticas

Clássicas Clássicas

Analógicas Analógicas

-Simulated -SimulatedAnneling Anneling -Tabu -TabuSearch Search .Clássica .Clássica .Reativa .Reativa -GRASP -GRASP

-Míopes -Míopes .Construtivas .Construtivas .Por .Poreconomia economia -Busca -Buscalocal local .Método .Métododescendente descendente .Método .Métodoaleatório aleatório -Particionamento/ -Particionamento/ Grupamento Grupamento

-Redes -RedesNeurinais Neurinais -Computação -ComputaçãoEvolutiva Evolutiva .Algoritmos .Algoritmosgenéticos genéticos .Scatter .ScatterSearch Search .Colônia .Colôniade deformigas formigas

Lagrangeana Lagrangeana

Linear Linear

-Subgradiente -Subgradiente -Ajuste -AjusteMúltiplo Múltiplo

-Dual -DualAscent Ascent

Programação Inteira Exercício Desafio Em um tabuleiro de xadrez (padrão 8 x 8) e vazio, sabendo-se que uma alocação em casa preta vale o dobro do que em casa branca, determine:  A localização ótima para 8 (oito) damas de modo que nenhuma delas seja ameaçada pelas demais.  Formule esse problema como um PPL e o solucione com o auxílio do Simplex.

Programação Inteira