Baixe o app para aproveitar ainda mais
Prévia do material em texto
Introdução à Programação Inteira Pesquisa Operacional 1 Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini Tipos de programação inteira (PI) • Problemas puros: todas as variáveis são inteiras • Problemas mistos: algumas variáveis de decisão são inteiras • Problemas boleanos: variáveis somente podem assumir os valores inteiros no intervalo [0, 1] Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 2 Programação inteira • A todo o problema de PI existe um problema de PL correspondente no qual as restrições de não-‐fracionariedade são removidas (ou relaxadas) • Alguns resultados seguem: – Espaço de soluções viáveis do PI estão conTdas no espaço de soluções viáveis do PI relaxado – Valor óTmo de z do PI é no máximo tão bom quanto o valor óTmo do PI relaxado Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 3 Abordagem para solução de PI • Resolver seus problemas correspondentes PL “relaxados” arredondando as variáveis de decisão para o maior ou menor inteiro mais próximo • Dois possíveis efeitos do arredondamento: – Valores arredondados inviáveis no PI – Soluções resultantes altamente sub óTmas Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 4 Método Branch-‐and-‐Bound para solução de problemas PI puros max z = 8X1 + 5X2 s.a (1) X1 + X2 ≤ 6 (2) 9X1 + 5X2 ≤ 45 (3) X1, X2 ≥ 0 (4) X1, X2 inteiros Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 5 Branch-‐and-‐Bound é operacionalizado em 5 passos • Passo 1: Comece resolvendo o PI relaxado – Se a solução óTma for inteira, esta é a solução – Caso contrário, esta solução será o limite superior da solução óTma inteira • A solução óTma do PIR dado anteriormente é: Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 6 X1 = 15/4 X2 = 9/4 Z1* = 165/4 Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 7 X1 X2 max z = 8X1 + 5X2 s.a (1) X1 + X2 ≤ 6 (2) 9X1 + 5X2 ≤ 45 (3) X1, X2 ≥ 0 (4) X1, X2 inteiros 5 5 10 (1) (2) z SP1 Pto óTmo Passo 1: resolver PI relaxado X1 = 15/4 X2 = 9/4 Z1* = 165/4 Passo 2 -‐ Desdobramento • Escolha uma variável de decisão fracionária em z* do PIR: – Por exemplo, X1 = 15/4 • PI admite valores de X1 ≤ 3 ou X1 ≥ 4, mas não em 3 < X1 < 4 Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 8 Crie dois subproblemas a parTr de X1 • SP2: SP1 + restrição X1 ≥ 4 • SP3: SP1 + restrição X1 ≤ 3 • SP = subproblema • O problema designado por SP1 é o próprio problema de PI em estudo, relaxado das restrições de não-‐fracionariedade Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 9 Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 10 X1 X2 5 5 10 (1) (2) z SP2 = SP1 + X1 ≥ 4 Passo 3 – Dividir o espaço de soluções SP3 = SP1 + X1 ≤ 3 max z = 8X1 + 5X2 s.a (1) X1 + X2 ≤ 6 (2) 9X1 + 5X2 ≤ 45 (3) X1, X2 ≥ 0 (4) X1, X2 inteiros X1 ≥ 4 X1 ≤ 3 Passo 3 • Escolha qualquer SP listado no passo anterior e resolva como se fosse um problema de PL: – Por ex., SP2, solução óTma z*=41, X1=4 e X2=9/5 • Resultados obTdos até agora podem ser apresentados na forma de uma árvore hierárquica Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 11 Árvore hierárquica de solução do problema Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 12 SP1 X1 = 3,75 X2 = 2,25 Z1* = 41,25 SP2 X1 = 4 X2 = 9/5 Z2* = 41 SP3 X1 = ? X2 = ? Z3* = ? Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 13 X1 X2 5 5 10 (1) (2) z Pto óTmo SP2 Pto óTmo SP3 X1 = 4 X2 = 9/5 Z2* = 41 X1 = ? X2 = ? Z3* = ? max z = 8X1 + 5X2 s.a (1) X1 + X2 ≤ 6 (2) 9X1 + 5X2 ≤ 45 (3) X1, X2 ≥ 0 (4) X1, X2 inteiros Passo 4 – Resolver novo PL Passo 4 • Repita o procedimento no Passo 3 usando o SP2 com a variável de decisão fracionária X2 = 9/5 • Subproblemas resultantes: – SP4: SP2 + restrição X2 ≥ 2 – SP5: SP2 + restrição X2 ≤ 1 • Tem-‐se dois problemas que podem ser resolvidos: SP4 e SP5 Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 14 Escolha um SP para resolução Por exemplo: SP4 • SP4 não apresenta soluções viáveis, não podendo, assim, gerar uma soluçãoóTma para o problema de PI: – Assim, diz-‐se que este nodo da árvore foi terminado • Dentre os SPs não resolvidos, escolhe-‐se o mais recente, SP5: – Solução vem apresentada na árvore do problema a seguir Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 15 Árvore hierárquica de solução do problema Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 16 SP1 X1 = 3,75 X2 = 2,25 Z1* = 41,25 SP2 X1 = 4 X2 = 9/5 Z2* = 41 SP3 X1 = ? X2 = ? Z3* = ? SP5 X1 = 40/9 X2 = 1 Z5* = 40,555 SP4 Inviável! Passo 3 -‐ Novamente Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 17 X1 X2 5 5 10 (1) (2) z Pto óTmo SP5 SP4 X1 = 40/9 X2 = 1 Z4* = 40,555 Não apresenta soluções viáveis (nodo terminado) max z = 8X1 + 5X2 s.a (1) X1 + X2 ≤ 6 (2) 9X1 + 5X2 ≤ 45 (3) X1, X2 ≥ 0 (4) X1, X2 inteiros Repita procedimento em (3) usando SP5 e variável fracionária X1 • Subproblemas restantes 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 • Solução óTma para SP7 vem dada na árvore a seguir Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 18 Passo 3 -‐ Novamente Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 19 X1 X2 5 5 10 (1) (2) z Pto óTmo SP6 Pto óTmo SP7 X1 = ? X2 = ? Z6* = ? max z = 8X1 + 5X2 s.a (1) X1 + X2 ≤ 6 (2) 9X1 + 5X2 ≤ 45 (3) X1, X2 ≥ 0 (4) X1, X2 inteiros X1 = 4 inteiro X2 = 1 inteiro Z7* = 37 1ª Solução candidata! SP7 gera a primeira solução candidata para PI • A solução só possui valores inteiros para a variável de decisão – Pode ser interpretada como solução candidata ou um limite inferior no valor óTmo do problema de PI Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 20 Problemas SP3 e SP6 ainda não foram resolvidos • Escolhe-‐se SP6 (+recente), com solução dada na árvore a seguir: – Solução de SP6 é inteira e melhor do que aquela obTda para SP7 – Assim termina-‐se nodo da árvore em SP7 (idenTfica-‐se o nodo terminado por um x ou escrevendo solução excluída) e atualiza-‐se o limite inferior da árvore; novo LI = 40) Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 21 Passo 3 -‐ Novamente Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 22 X1 X2 5 5 10 (1) (2) z Pto óTmo SP6 Pto óTmo SP7 X1 = 5 X2 = 0 Z6* = 40 max z = 8X1 + 5X2 s.a (1) X1 + X2 ≤ 6 (2) 9X1 + 5X2 ≤ 45 (3) X1, X2 ≥ 0 (4) X1, X2 inteiros X1 = 4 X2 = 1 Z7* = 37 ÚlTmo SP a ser resolvido é SP3 • Solução de SP3 é z*= 39, onde X1=X2=3: – Trata-‐se de uma solução candidata com z*< LI • Assim, o nodo SP3 é terminado e SP6 é idenTficado como a solução óTma para o problema de PI Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 23 Árvore hierárquica de solução do problema (final) Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 24 SP1 X1 = 3,75 X2 = 2,25 Z1* = 41,25 SP2 X1 = 4 X2 = 9/5 Z2* = 41 SP3 X1 = 3 X2 = 3 Z3* = 39 SP5 X1 = 40/9 X2 = 1 Z5* = 40,555 SP4 Inviável! SP7 X1 = 4 X2 = 1 Z7* = 37 SP6 X1 = 5 X2 = 0 Z6* = 40 Z3* > LI = Z5* (solução excluída) Z7* > LI = Z5* Solução óTma do PLI X X X Aspectos importantes do Branch-‐and-‐ bound para PIs puros • Sempre que não for necessário desdobrar um subproblema, ele deve ser terminado • Critérios uTlizados para terminação são: – SP não possui soluções viáveis – SP gera uma solução óTma contendo somente valores inteiros – SP apresenta um valor de z* menor (em problemas de PI do Tpo Maximização) que o limite inferior atual Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 25 Mais aspectos • A regra “úlTmo a entrar, primeiro a sair”, que indica qual SP deve ser trabalhado dentre vários candidatos força o analista a trabalhar um mesmo ramo da árvore até o final: – Existem outras regras possíveis • Quando um SP apresenta solução óTma com duas ou mais variáveis de decisão fracionárias, trabalhe com aquela representar maior ganho na função obje3vo Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini26 Método Branch-‐and-‐bound para solução de PIs mistos • Modifique o algoritmo anterior da seguinte maneira: – Desdobre somente variáveis de decisão restritas à não-‐fracionariedade – Considere a solução óTma de um SP como sendo candidata à solução óTma do problema de PI quando esta atender às restrições de não-‐ fracionariedade Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 27 Exercício 1 – PI misto • Min z = 4X1 + 5X2 s.a: X1 + 4X2 ≥ 5 3X1 + 2X2 ≥ 7 X1, X2 ≥ 0 X1 inteiro Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 28 Exercício 2 – PI misto • Max z = 2X1 + X2 s.a: 5X1 + 2X2 ≤ 8 X1 + X2 ≤ 3 X1, X2 ≥ 0 X1 inteiro Dep Engenharia de Produção -‐ UFRGS -‐ Daniel Zini 29
Compartilhar