Optimização Combinatória: modelos e algoritmos: transparências de apoio à leccionação de aulas teóricas

Slide 1 Optimiza¸c˜ao Combinat´oria: Modelos e Algoritmos Transparˆencias de apoio `a lecciona¸c˜ao de aulas te´oricas Vers˜ao 1 c °2001 Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 1 Slide 2 Modelos de Optimiza¸c˜ao Combinat´oria Slide 3 Problemas de Optimiza¸c˜ao Instˆancia de um Problema de Optimiza¸c˜ao Uma instˆancia de um Problema de Optimiza¸c˜ao ´e um par (F, c), onde: F´e um conjunto qualquer (o dom´ınio das solu¸c˜oes admiss´ıveis) c´e a fun¸c˜ao custo, e corresponde a um mapeamento c:F → R A solu¸c˜ao ´optima ser´a um f∈ F tal que: ∀y∈F c(f)≤c(y) Um Problema de Optimiza¸c˜ao ´e um conjunto de Instˆancias de um Problema de Optimiza¸c˜ao (in Papadimitriou, Steiglitz pp.4) Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 2 Slide 4 Optimiza¸c˜ao Combinat´oria OC Problemas de Optimiza¸c˜ao com vari´aveis cont´ınuas Problemas Cont´ınuos Solu¸c˜ao: conjunto de n´umeros reais com vari´aveis discretas Problemas Combinat´orios Solu¸c˜ao: objecto pertencente a um conjunto finito ou ent˜ao infinito enumer´avel, por exemplo inteiros, conjuntos, permuta¸c˜oes ou grafos. Slide 5 Problema da Mochila “Knapsack Problem”KP Dados: •um conjunto de tipos de objectos em que cada tipo tem um valor e um peso associados •uma mochila com um limite de peso transport´avel Pretende-se encher a mochila, n˜ao ultrapassando o limite m´aximo de peso e maximizando o valor total dos objectos transportados. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 3 Slide 6 Problema da Mochila (KP) ´ Indices jtipo de objecto, j∈ {1,...,n}; Vari´aveis de decis˜ao xjn´umero de objectos do tipo ja colocar dentro da mochila Coeficientes wjpeso de cada um dos objectos do tipo j; cjvalor de cada um dos objectos do tipo j; blimite m´aximo de peso a transportar na mochila. Fun¸c˜ao objectivo max Z=Pn j=1 cjxj Restri¸c˜oes Pn j=1 wjxj≤b ∀jxj≥0inteiro Slide 7 Problema da Mochila 0–1 “0–1 Knapsack Problem”(0–1KP) Dados: •um conjunto de objectos diferentes em que cada objecto tem um valor e um peso associados •uma mochila com um limite de peso transport´avel Pretende-se encher a mochila, n˜ao ultrapassando o limite m´aximo de peso e maximizando o valor total dos objectos transportados. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 4 Slide 8 Problema da Mochila 0–1 (0–1KP) Modelo ´ Indices jobjecto, j∈ {1,...,n}; Vari´aveis de decis˜ao xj=       1 se objecto j for colocado na mochila 0 se n˜ao Coeficientes wjpeso do objecto j; cjvalor do objecto j; blimite m´aximo de peso a transportar na mochila. Fun¸c˜ao objectivo max Z=Pn j=1 cjxj Restri¸c˜oes Pn j=1 wjxj≤b ∀jxj∈ {0,1} Slide 9 Circuitos Hamiltonianos Defini¸c˜ao de Circuito Hamiltoniano: Um circuito diz-se Hamiltoniano, se passar uma e uma s´o vez por todos os v´ertices de uma rede. A designa¸c˜ao prov´em do islandˆes Hamilton que, em 1857 propˆos um jogo denominado “Around the World”. Nesse jogo, os v´ertices de um dodecaedro de madeira representavam as 20 cidades mais importantes do mundo na ´epoca. O objectivo do jogo consistia em encontrar um percurso atrav´es dos v´ertices do dodecaedro, com in´ıcio e fim no mesmo v´ertice (cidade) e que passasse por cada v´ertice (cidade) apenas uma vez. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 5 Slide 10 Problema do Caixeiro Viajante “Travelling Salesman Problem”(TSP) O problema do caixeiro viajante ´e um problema de optimiza¸c˜ao associado `a determina¸c˜ao dos circuitos hamiltonianos num grafo qualquer. Problema do Caixeiro Viajante: Pretende-se encontrar o caminho mais curto para um caixeiro viajante que sai de uma cidade, visita n outras cidades e volta `aquela de onde partiu, sem repetir nenhuma das cidades visitadas (Circuito Hamiltoniano mais curto). Slide 11 Problema do Caixeiro Viajante (TSP) Formula¸c˜ao de Dantzig-Fulkerson-Johnson Formula¸c˜ao do TSP como um problema de programa¸c˜ao bin´aria sobre um grafo G= (V, A), onde V´e o conjunto de v´ertices (cidades) e A´e o conjunto de arcos (percursos directos entre duas cidades) ´ Indices icidade, i∈ {1,...,n} jcidade, j∈ {1,...,n} Coeficientes dij custo associado ao percurso (arco) entre cidade ie cidade j. Vari´aveis de decis˜ao xij =       1 se o percurso directo (arco) de i para jestiver inclu´ıdo na solu¸c˜ao 0 se n˜ao Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 6 Slide 12 Problema do Caixeiro Viajante (TSP) Formula¸c˜ao de Dantzig-Fulkerson-Johnson (cont.) Fun¸c˜ao objectivo min n X i=1 n X j=1 dijxij Restri¸c˜oes Pn i=1 xij = 1 ∀j∈V Pn j=1 xij = 1 ∀i∈V Pi,j∈Sxij ≤ |S|−1∀S⊂V xij ∈ {0,1} ∀i,j∈V,i6=j |S|representa o n´umero de v´ertices do subgrafo S. Note-se que em S≡Vn˜ao est´a considerado em S⊂V. Slide 13 Problema do Caixeiro Viajante (TSP) Formula¸c˜ao de Dantzig-Fulkerson-Johnson Elimina¸c˜ao de subgrafos 1 2 3 45 6 1 2 3 45 6 1 2 3 45 6 1 2 3 45 6 S={1,3,4} x13 = 1 ≤ |S|−1 = 2 S={4,5,6} x45 +x56 +x64 = 3 £|S|−1 = 2 1 2 3 45 6 1 2 3 45 6 S={1,2,3} x23 +x31 = 2 ≤ |S|−1 = 2 S={4,5,6} x45 +x56 = 2 ≤ |S|−1 = 2 etc . . . Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 7 Slide 14 Cobertura de conjuntos “Set Covering” Dados: •um conjunto de clientes •um conjunto de armaz´ens •uma matriz de liga¸c˜oes clientes–armaz´ens •custos de abertura de cada um dos armaz´ens Pretende-se fornecer todos os clientes, minimizando os custos de abertura dos armaz´ens. Slide 15 Cobertura de conjuntos Modelo ´ Indices icliente, i∈ {1,...,m}; jarmaz´em, j∈ {1,...,n}; Vari´aveis de decis˜ao xj=   1 se armaz´em jfor aberto. 0 se n˜ao Coeficientes aij 1 se cliente ipode ser fornecido pelo armaz´em j, 0 se n˜ao; cjcusto associado `a abertura do armaz´em j. Fun¸c˜ao objectivo min Z=Pn j=1 cjxj Restri¸c˜oes ∀iPn j=1 aijxj≥1 ∀jxj∈ {0,1} Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 8 Slide 16 Parti¸c˜ao de conjuntos “Set Partitioning” Dados: •um conjunto de clientes •um conjunto de armaz´ens •uma matriz de liga¸c˜oes clientes–armaz´ens •custos de abertura de cada um dos armaz´ens Pretende-se fornecer todos os clientes, minimizando os custos de abertura dos armaz´ens. Cada cliente s´o pode ficar ligado a um armaz´em. Slide 17 Parti¸c˜ao de conjuntos “Set Partitioning” Modelo ´ Indices icliente, i∈ {1,...,m}; jarmaz´em, j∈ {1,...,n}; Vari´aveis de decis˜ao xj=   1 se armaz´em jfor aberto. 0 se n˜ao Coeficientes aij 1 se cliente ipode ser fornecido pelo armaz´em j, 0 se n˜ao; cjcusto associado `a abertura do armaz´em j. Fun¸c˜ao objectivo min Z=Pn j=1 cjxj Restri¸c˜oes ∀iPn j=1 aijxj= 1 ∀jxj∈ {0,1} Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 15 Slide 30 Classifica¸c˜ao dos problemas Problemas de decis˜ao (sup˜oem apenas uma resposta do tipo SIM ou N˜ AO). Exemplo: Para uma dada instˆancia do TSP h´a algum circuito cujo custo (distˆancia total percorrida) seja inferior a K? •Classe P– Conjunto de problemas de decis˜ao para os quais existe um algoritmo que corre em tempo polinomial. •Classe NP – Conjunto de problemas de decis˜ao para os quais n˜ao se conhece um algoritmo polinomial mas que que pode ser resolvido em tempo polinomial por uma abstrac¸c˜ao algor´ıtmica chamada “algoritmo n˜ao determin´ıstico”.a aIncorpora instru¸c˜oes do tipo “go to both label1, label2” originando um ´arvore de processos a correr em paralelo. O primeiro ramo que responder “SIM” p´ara a execu¸c˜ao e o algoritmo responde “SIM”. Se esse ramo tiver respondido ap´os um n´umero polinomial de passos, ent˜ao o algoritmo diz-se n˜ao-determin´ıstico Slide 31 Classifica¸c˜ao dos problemas (cont.) •Classe NP −completa – Sub-conjunto de problemas da classe NP aos quais qualquer outro problema da classe pode ser reduzido. Se qualquer problema da classe NP puder ser reduzido a um problema Pent˜ao diz-se que Ppertence `a classe NP −completa. Problemas de optimiza¸c˜ao (achar a melhor solu¸c˜ao) S˜ao naturalmente reduzidos a uma sequˆencia de problemas de decis˜ao: repete-se a pergunta, com valores sucessivamente mais exigentes, at´e a resposta ser n˜ao. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 16 Slide 32 Abordagens `a resolu¸c˜ao de Problemas de Optimiza¸c˜ao Combinat´oria T´ecnicas exactas — obtˆem e garantem uma solu¸c˜ao ´optima. Atingir a solu¸c˜ao ´optima pode ser dif´ıcil (muito demorado), ou mesmo imposs´ıvel (o tempo correspondente `a vida passada do sistema solar poderia n˜ao ser suficiente) e nem sequer ser especialmente importante para a aplica¸c˜ao concreta que se pretende resolver. ↓ T´ecnicas aproximadas ou m´etodos heur´ısticos — ou n˜ao obtˆem a solu¸c˜ao ´optima ou, se a obtˆem, n˜ao o sabem... Em compensa¸c˜ao s˜ao capazes de obter “boas” solu¸c˜oes muito rapidamente. Slide 33 Bibliografia •Goldbarg, Marco Cesar e Luna, Henrique Pacca (2000). Otimiza¸c˜ao Combinat´oria e Programa¸c˜ao Linear, Editora CAMPUS. •Golden, B.L. and Stewart, W.R. (1985). Empirical analysis of heuristics in The Traveling Salesman Problem, John Wiley & Sons, Inc.. •Nemhauser, George L. e Wolsey, Laurence A. (1988). Integer and Combinatorial Optimization John Wiley & Sons, Inc.. •Papadimitrio, Christus H. e Steiglitz, Kenneth (1982). Combinatorial Optimization – Algotithms and Complexity Prentice Hall, Inc.. •Sousa, Jorge Pinho (1991). Apontamentos de Optimiza¸c˜ao Combinat´oria. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 17 Slide 34 T´ecnicas exactas para resolu¸c˜ao de problemas de optimiza¸c˜ao Slide 35 T´ecnicas exactas •Enumera¸c˜ao expl´ıcita — por defini¸c˜ao de problema de Optimiza¸c˜ao Combinat´oria, gerando eavaliando todas as solu¸c˜oes admiss´ıveis ´e poss´ıvel obter a solu¸c˜ao ´optima. •Enumera¸c˜ao impl´ıcita — n˜ao se gerando todas as solu¸c˜oes admiss´ıveis, elas s˜ao no entanto consideradas e implicitamente avaliadas. Exemplos: M´etodo de pesquisa em ´arvore com enumera¸c˜ao e limita¸c˜ao (“branch and bound”); limites superiores e inferiores ao valor da solu¸c˜ao ´optima. •Formula¸c˜ao dos problemas em modelos de programa¸c˜ao inteira (vari´aveis de decis˜ao assumem valores no conjunto dos n´umeros inteiros), ou mesmo bin´aria (vari´aveis apenas com dois valores poss´ıveis: 0 ou 1), e consequente resolu¸c˜ao com algoritmos apropriados. Nota: Estas formula¸c˜oes podem tamb´em ser usadas para obter limites para o valor da solu¸c˜ao ´optima atrav´es de relaxa¸c˜oes. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 18 Slide 36 T´ecnicas exactas e relaxa¸c˜oes Relaxa¸c˜ao — N˜ao considera¸c˜ao de uma ou mais restri¸c˜oes do problema original PO, transformando-o num problema mais simples de resolver P R, sabendo-se que os valores ´optimos das fun¸c˜oes objectivo obedecem `a seguinte rela¸c˜ao (assumindo um problema de minimiza¸c˜ao): f? P R ≤f? P O (tradu¸c˜ao: ao tirar restri¸c˜oes a solu¸c˜ao s´o pode melhorar, ou ficar na mesma). Relaxa¸c˜ao linear – transforma¸c˜ao de um problema em n´umeros inteiros num problema com vari´aveis reais (deixa-se cair a restri¸c˜ao “e inteiros” ou “∈ N0”−→ utiliza¸c˜ao do m´etodo simplex para a sua resolu¸c˜ao em vez dos muito mais complexos (e extraordinariamente mais demorados) m´etodos de pesquisa em ´arvore). Slide 37 M´etodo de “branch and bound” Baseia-se na ideia de uma enumera¸c˜ao inteligente das solu¸c˜oes candidatas a solu¸c˜ao ´optima inteira de um problema, efectuando sucessivas parti¸c˜oes do espa¸co das solu¸c˜oes e cortando a ´arvore de pesquisa atrav´es da considera¸c˜ao de limites calculados ao longo da enumera¸c˜ao. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 19 Slide 38 Representa¸c˜ao gr´afica Considere-se o seguinte problema de Programa¸c˜ao Inteira: Maximizar: F= 3x+ 7y suj. a: x≤3.5 5x−4y≤10 4 7x+ 2y≤9 x , y ≥0e inteiras e a sua representa¸c˜ao gr´afica: y 7 6 5 4 3 2 1 5x - 4y = 10 x = 3.5 4/7x + 2y = 9 Max F = 3x + 7y 1 2 3 4 5 6 7 8 x Solu¸c˜ao ´optima inteira: x= 1 e y= 4. Slide 39 Resolu¸c˜ao da relaxa¸c˜ao linear Problema PL0: max F= 3x+ 7y suj. a: x≤3.5 5x−4y≤10 4 7x+ 2y≤9 x , y ≥0 5x - 4y = 10 x = 3.5 4/7x + 2y = 9 Max F = 3x + 7y y 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 x Solu¸c˜ao ´optima n˜ao inteira: x= 3.5 e y= 3.5; F= 35 Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 20 Slide 40 Ramifica¸c˜ao em x:x≤3 max F= 3x+ 7y suj. a: x≤3.5 5x−4y≤10 4 7x+ 2y≤9 x , y ≥0 x≤3 5x - 4y = 10 x = 3.5 4/7x + 2y = 9 Max F = 3x + 7y y 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 x x = 3 Solu¸c˜ao (n˜ao inteira): x= 3 e y= 3.6; F= 34.5 Slide 41 Ramifica¸c˜ao em x:x≥4 max F= 3x+ 7y suj. a: x≤3.5 5x−4y≤10 4 7x+ 2y≤9 x , y ≥0 x≥4 5x - 4y = 10 x = 3.5 4/7x + 2y = 9 Max F = 3x + 7y y 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 x x = 4 Sem solu¸c˜oes admiss´ıveis. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 21 Slide 42 Ramifica¸c˜ao em y:y≤3 max F= 3x+ 7y suj. a: x≤3.5 5x−4y≤10 4 7x+ 2y≤9 x , y ≥0 x≤3 y≤3 5x - 4y = 10 x = 3.5 4/7x + 2y = 9 Max F = 3x + 7y y 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 x x = 3 y = 3 Solu¸c˜ao (inteira): x= 3 e y= 3; F= 30 Obten¸c˜ao de um limite inferior ⇒ Solu¸c˜oes n˜ao inteiras com valor de F inferior ou igual a 30 n˜ao precisam de ser exploradas! Slide 43 Ramifica¸c˜ao em y:y≥4 max F= 3x+ 7y suj. a: x≤3.5 5x−4y≤10 4 7x+ 2y≤9 x , y ≥0 x≤3 y≥4 5x - 4y = 10 x = 3.5 4/7x + 2y = 9 Max F = 3x + 7y y 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 x x = 3 y = 4 Solu¸c˜ao (n˜ao inteira): x= 1.7 e y= 4; F= 33.2 Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 22 Slide 44 Ramifica¸c˜ao em x:x≤1 max F= 3x+ 7y suj. a: x≤3.5 5x−4y≤10 4 7x+ 2y≤9 x , y ≥0 x≤3 y≥4 x≤1 5x - 4y = 10 x = 3.5 4/7x + 2y = 9 Max F = 3x + 7y y 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 x x = 1 y = 4 x = 3 Solu¸c˜ao (n˜ao inteira): x= 1 e y= 4.2; F= 32.5 Slide 45 Ramifica¸c˜ao em x:x≥2 max F= 3x+ 7y suj. a: x≤3.5 5x−4y≤10 4 7x+ 2y≤9 x , y ≥0 x≤3 y≥4 x≥2 5x - 4y = 10 x = 3.5 4/7x + 2y = 9 Max F = 3x + 7y y 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 x x = 2 y = 4 x = 3 Sem solu¸c˜oes admiss´ıveis. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 23 Slide 46 Ramifica¸c˜ao em y:y≤4 max F= 3x+ 7y suj. a: x≤3.5 5x−4y≤10 4 7x+ 2y≤9 x , y ≥0 x≤3 y≥4 x≤1 y≤4 5x - 4y = 10 x = 3.5 4/7x + 2y = 9 Max F = 3x + 7y y 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 x x = 1 y = 4 x = 3 Solu¸c˜ao (inteira): x= 1 e y= 4; F= 31 Melhor solu¸c˜ao inteira at´e ao momento! Slide 47 Ramifica¸c˜ao em y:y≥5 max F= 3x+ 7y suj. a: x≤3.5 5x−4y≤10 4 7x+ 2y≤9 x , y ≥0 x≤3 y≥4 x≤1 y≥5 5x - 4y = 10 x = 3.5 4/7x + 2y = 9 Max F = 3x + 7y y 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 x x = 1 y = 4 x = 3 y = 5 Sem solu¸c˜oes admiss´ıveis. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 24 Slide 48 ´ Arvore de pequisa do “Branch-and-Bound” Slide 49 Limites Limites (inferiores e superiores): •tornam o algoritmo de “branch & bound” mais eficiente ao permitir descartar n´os da ´arvore de pesquisa ainda n˜ao completamente explorados, pela certeza de que nunca originar˜ao solu¸c˜oes melhores do que as que j´a temos. •permitem “medir a distˆancia” (em termos de valor da fun¸c˜ao objectivo) a que estamos da solu¸c˜ao ´optima. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 31 Slide 62 Exemplo – um problema (simples) de planeamento da produ¸c˜ao Dados – 6 per´ıodos e 8 encomendas. Objectivo – produzir o mais pr´oximo poss´ıvel da data de entrega. t123456 Ct452521 Capacidade dispon´ıvel Ctem cada per´ıodo t 123456t Ct 1 2 3 4 5 e12345678 qe11222333 de21312513 Encomendas e, com quantidades qee datas de entrega de 3 1 6 2 45 78 Slide 63 Exemplo – continua¸c˜ao Vari´aveis de decis˜ao: xet ∈ {0,1}que valem 1 se a encomenda e´e produzida no per´ıodo t. Restri¸c˜oes: •Cada encomenda tem que ser produzida uma e uma s´o vez: Ptxet = 1 •As capacidades dos per´ıodos tˆem que ser respeitadas: ∀tPeqe×xet ≤Ct Observa¸c˜ao: h´a encomendas que, dadas as respectivas quantidades e as capacidades dos per´ıodos, nunca poder˜ao ser produzidas em simultˆaneo. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 32 Slide 64 Exemplo – continua¸c˜ao Regras para a gera¸c˜ao de desigualdades v´alidas: 1. No per´ıodo 1 (capacidade 4) n˜ao se podem produzir simultaneamente duas encomendas com quantidades 2 e 3, ou 3 e 3. 2. Nos per´ıodos 2 e 4 (capacidade 5) n˜ao se podem produzir simultaneamente duas encomendas com quantidades 3. 3. Nos per´ıodos 3 e 5 (capacidade 2) n˜ao se podem produzir simultaneamente duas encomendas com quantidades 2, duas encomendas com quantidades 1 e 2, nem qualquer encomenda com quantidade 3. 4. No per´ıodo 6 (capacidade 1) apenas se podem produzir encomendas com quantidade 1. Slide 65 Exemplo – conclus˜ao Solu¸c˜ao da relaxa¸c˜ao linear do exemplo: 123456t Ct 1 2 3 4 5 3 1 6 2 4 5 7 8 7 5 8 3 Esta solu¸c˜ao viola uma desigualdade do tipo 1 e uma desigualdade do tipo 2. S˜ao ent˜ao desigualdades v´alidas: x41 +x71 ≤1 x64 +x84 ≤1 Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 33 Slide 66 Bibliografia •Alves, Jos´e Carlos (1989). Provas de Aptid˜ao Cient´ıfica e Capacidade Pedag´ogica. FEUP. •Carravilla, Maria Ant´onia (1996). Modelos e Algoritmos para o Planeamento Hier´arquico da Produ¸c˜ao – Aplica¸c˜oes a um Caso de Estudo, Tese de Doutoramento, FEUP. •Goldbarg, Marco Cesar e Luna, Henrique Pacca (2000). Otimiza¸c˜ao Combinat´oria e Programa¸c˜ao Linear, Editora CAMPUS. •Nemhauser, George L. e Wolsey, Laurence A. (1988). Integer and Combinatorial Optimization John Wiley & Sons, Inc.. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 34 Slide 67 Algoritmos para Resolu¸c˜ao Aproximada de Problemas de Optimiza¸c˜ao Combinat´oria Slide 68 T´ecnicas aproximadas para a resolu¸c˜ao de problemas de Optimiza¸c˜ao Combinat´oria M´etodos Heur´ısticos Tˆem como objectivo obter muito boas solu¸c˜oes de uma forma eficiente. N˜ao obtˆem a solu¸c˜ao ´optima, ou pelo menos n˜ao s˜ao capazes de garantir que a solu¸c˜ao boa que obtˆem ´e de facto a ´optima. Caracter´ısticas dos algoritmos heur´ısticos •Tempos de execu¸c˜ao “curtos” •Facilidade de implementa¸c˜ao •Flexibilidade •Simplicidade Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 35 Slide 69 Tipos de algoritmos heur´ısticos •Construtivos – Constroem uma solu¸c˜ao, passo a passo, segundo um conjunto de regras pr´e-estabelecido. •de Melhoramentos – Partem de uma solu¸c˜ao admiss´ıvel qualquer e procuram melhor´a-la atrav´es de sucessivas pequenas altera¸c˜oes. •Compostos – Tˆem primeiro uma fase construtiva e depois uma fase de melhoramentos. Estes tipos de heur´ısticas ser˜ao apresentados e exemplificados utilizando como caso de estudo o Problema do Caixeiro Viajante. Slide 70 Algoritmos (heur´ısticos) construtivos Constroem uma solu¸c˜ao, passo a passo, segundo um conjunto de regras pr´e-estabelecido. Estas regras est˜ao relacionadas com: •a escolha do sub-ciclo inicial (ou o ponto inicial) – inicializa¸c˜ao; •um crit´erio de escolha do elemento seguinte a juntar `a solu¸c˜ao – selec¸c˜ao; •a selec¸c˜ao da posi¸c˜ao onde esse novo elemento ser´a inserido – inser¸c˜ao. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 36 Slide 71 TSP – Vizinho mais pr´oximo 1. Inicializa¸c˜ao – Come¸car com um circuito parcial constitu´ıdo por uma cidade isozinha, escolhida arbitrariamente; 2. Selec¸c˜ao – Seja (1,...,k) o percurso parcial actual (k < n). Encontrar a cidade k+ 1, que ainda n˜ao faz parte do circuito e que est´a mais pr´oxima de k. 3. Inser¸c˜ao – Inserir k+ 1 no fim do circuito parcial. 4. Se todas as cidades est˜ao inseridas, PARAR, sen˜ao voltar a 2. Slide 72 Vizinho mais pr´oximo – exemplo 12 3 56 4 5 3 5 3 6 4 4 3 2 3 3 45 32 12 3 56 4 5 3 5 3 6 4 4 3 2 3 3 45 32 12 3 56 4 5 3 5 3 6 4 4 3 2 3 3 45 32 12 3 56 4 5 3 5 3 6 4 4 3 2 3 3 45 32 12 3 56 4 5 3 5 3 6 4 4 3 2 3 3 45 32Comprimento total do percurso: 19 Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 37 Slide 73 TSP – Inser¸c˜ao mais pr´oxima de cidade arbitr´aria 1. Inicializa¸c˜ao – Come¸car com um circuito parcial constitu´ıdo por uma cidade isozinha, escolhida arbitrariamente; Encontrar a cidade jtal que cij (distˆancia de iaj) ´e m´ınima e formar o circuito parcial (i, j). 2. Selec¸c˜ao – Dado um circuito parcial, seleccionar arbitrariamente uma cidade kainda n˜ao pertencente ao circuito parcial. 3. Inser¸c˜ao – Encontrar a aresta {i, j}no circuito parcial que minimiza cik +ckj −cij. Inserir kentre iej. 4. Se todas as cidades est˜ao inseridas, PARAR, sen˜ao voltar a 2. Slide 74 Inser¸c˜ao mais pr´oxima de cidade arbitr´aria – exemplo 12 3 56 4 5 3 5 3 6 4 4 3 2 3 3 45 32 12 3 56 4 5 3 5 3 6 4 4 3 2 3 3 45 32 12 3 56 4 5 3 5 3 6 4 4 3 2 3 3 45 32 12 3 56 4 5 3 5 3 6 4 4 3 2 3 3 45 32 12 3 56 4 5 3 5 3 6 4 4 3 2 3 3 45 32Comprimento total do percurso: 17 Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 38 Slide 75 TSP – Inser¸c˜ao mais pr´oxima 1. Inicializa¸c˜ao – Come¸car com um circuito parcial constitu´ıdo por uma cidade isozinha, escolhida arbitrariamente; 2. Selec¸c˜ao – Encontrar as cidades kej(jpertencendo ao circuito parcial ekn˜ao pertencendo) tal que ckj ´e minimizado. 3. Inser¸c˜ao – Encontrar a aresta {i, j}no circuito parcial que minimiza cik +ckj −cij. Inserir kentre iej. 4. Se todas as cidades est˜ao inseridas, PARAR, sen˜ao voltar a 2. Esta heur´ıstica tem a variante “Inser¸c˜ao mais distante” que substitui o passo de selec¸c˜ao por: 2. Selec¸c˜ao – Encontrar as cidades kej(jpertencendo ao circuito parcial ekn˜ao pertencendo) tal que ckj ´e maximizado. Slide 76 TSP – Inser¸c˜ao mais barata 1. Inicializa¸c˜ao – Come¸car com um circuito parcial constitu´ıdo por uma cidade isozinha, escolhida arbitrariamente; 2. Selec¸c˜ao – Encontrar as cidades k,iej(iejformando uma aresta do circuito parcial e kn˜ao pertencendo a esse circuito) tal que cik +ckj −cij ´e minimizado. 3. Inser¸c˜ao – Inserir kentre iej. 4. Se todas as cidades est˜ao inseridas, PARAR, sen˜ao voltar a 2. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 39 Slide 77 TSP – Inv´olucro convexoa 1. Inicializa¸c˜ao – Come¸car com um circuito parcial constitu´ıdo pelo inv´olucro convexo de todas as cidades; 2. Inser¸c˜ao – Para cada cidade kn˜ao inserida no circuito parcial, encontrar a aresta {i, j}do circuito parcial que minimiza cik +ckj −cij. 3. Selec¸c˜ao – De entre todos os trios {i, j, k}formados e avaliados no passo 2, determinar o trio {i?, j?, k?}tal que ci?k?+ck?j? ci?j?´e m´ınimo. 4. Inserir k?entre i?ej?. 5. Se todas as cidades est˜ao inseridas, PARAR, sen˜ao voltar a 2. aInv´olucro convexo do conjunto A– forma convexa que cont´em no seu interior ou fronteira todos os elementos do conjunto A Slide 78 TSP – Fus˜ao mais pr´oxima 1. Inicializa¸c˜ao – Come¸car com ncircuitos parciais constitu´ıdos, cada um, por uma cidade isozinha; 2. Selec¸c˜ao – Encontrar as cidades iek(ipertencendo a um circuito parcial Cekpertencendo a um outro circuito C0) tal que cik ´e minimizado. 3. Inser¸c˜ao – Sejam i,j,kelcidades tais que a aresta {i, j} ∈ C, {k, l} ∈ C0ecik +cjl −cij −ckl ´e minimizado. Inserir {i, k}} e{j, l}} e retirar {i, j}} e{k, l}}. 4. Se existir um ´unico circuito, PARAR, sen˜ao voltar a 2. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 40 Slide 79 O problema da ´arvore suporte de comprimento m´ınimo •Defini¸c˜oes (para grafos n˜ao orientados): –uma ´arvore ´e um grafo conexo que n˜ao cont´em ciclos; –um grafo diz-se conexo se existir uma cadeia (sequˆencia de ramos) ligando qualquer par de n´os entre si. •Problema: Determinar a ´arvore de comprimento total m´ınimo que suporte todos os n´os da rede (i.e. que ligue todos os n´os da rede) (“minimal spanning tree”). •Aplica¸c˜oes: –redes de comunica¸c˜oes; –redes de distribui¸c˜ao de energia. Slide 80 Algoritmo de Prim (guloso – “Greedy Procedure”) 1. Seleccionar um n´o arbitrariamente, e lig´a-lo ao n´o mais pr´oximo; 2. Identificar o n´o ainda isolado que esteja mais pr´oximo de um n´o j´a ligado, e ligar estes dois n´os; 3. Se todos os n´os estiverem ligados entre si, PARAR, sen˜ao voltar a 2. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP Optimiza¸c˜ao Combinat´oria: modelos e algoritmos 47 Slide 93 Bibliografia •Goldbarg, Marco Cesar e Luna, Henrique Pacca (2000). Otimiza¸c˜ao Combinat´oria e Programa¸c˜ao Linear, Editora CAMPUS. •Golden, B.L. and Stewart, W.R. (1985). Empirical analysis of heuristics in The Traveling Salesman Problem, John Wiley & Sons, Inc.. •Sousa, Jorge Pinho (1991). Apontamentos de Optimiza¸c˜ao Combinat´oria. Jos´e Fernando Oliveira, Maria Ant´onia Carravilla – FEUP