Problemas de Decisão em Redes

Slide 1 Problemas de Decis˜ao em Redes Transparˆencias de apoio `a lecciona¸c˜ao de aulas te´oricas Vers˜ao 2 c °2001, 1997 Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 1 Slide 2 Problemas de Fluxos em Redes Slide 3 Problemas de fluxos em redes Rede: Conjunto de pontos (v´ertices) ligados por linhas ou canais (ramos ou arcos). Objectivo: Enviar um certo tipo de bem a partir de certos pontos e receber esses bens noutros pontos. Exemplos: •linhas de comunica¸c˜ao •redes de estradas, comboios ou de avi˜oes •redes de g´as, electricidade ou ´agua Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 2 Slide 4 Problemas de Transportes Slide 5 O problema da distribui¸c˜ao de frigor´ıficos Um fabricante de frigor´ıficos tem 3 f´abricas, de onde abastece 3 clientes (distribuidores). No in´ıcio de cada mˆes recebe de cada cliente a informa¸c˜ao sobre o n´umero de frigor´ıficos que pretende para esse mˆes. Esses frigor´ıficos ter˜ao que ser produzidos nas v´arias f´abricas, atendendo `a capacidade de produ¸c˜ao de cada uma delas. O custo de transportar um frigor´ıfico de cada f´abrica para cada cliente ´e conhecido. O problema consiste em determinar que f´abrica(s) deve(m) abastecer cada cliente, e em que quantidades, de forma a que, respeitando as capacidades de produ¸c˜ao das f´abricas e satisfazendo as necessidades dos clientes, o custo total de transporte seja minimizado. Formule este problema considerando que as capacidades de produ¸c˜ao s˜ao iguais em todas as f´abricas (20 frigor´ıficos) e que as necessidades dos clientes s˜ao de 10, 30 e 20 frigor´ıficos. Os custos unit´arios de transporte s˜ao os indicados na tabela seguinte (em milhares de escudos): Clientes 123 1243 F´abricas 2152 3116 Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 3 Slide 6 Modelo xij – quantidade a transportar da f´abrica ipara o cliente j min 2x11 + 4x12 + 3x13 +x21 + 5x22 + 2x23 +x31 +x32 + 6x33 suj. a: x11 +x12 +x13 ≤20 x21 +x22 +x23 ≤20 x31 +x32 +x33 ≤20 x11 +x21 +x31 ≥10 x12 +x22 +x32 ≥30 x13 +x23 +x33 ≥20 x11, x12, x13, x21, x22, x23, x31, x32, x33 ≥0 Slide 7 Estrutura de um Problema de Transportes (PT) •origens onde existe um bem ou servi¸co dispon´ıvel (em quantidades limitadas); •destinos onde esse bem ou servi¸co ´e necess´ario; •existem, e s˜ao conhecidos, custos unit´arios de “transportar” entre cada origem e cada destino; •o objectivo ´e determinar a pol´ıtica ´optima de transportes, isto ´e, aquela que satisfazendo as necessidades e respeitando as disponibilidades, minimiza o custo total de transporte. Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 4 Slide 8 Modelo do PT xij – quantidade a transportar da origem ipara o destino j; cij – custo de transportar uma unidade da origem ipara o destino j; di– disponibilidade na origem i; nj– necessidade no destino j. min X iX j cijxij suj. a: X j xij ≤di,∀i(restri¸c˜oes da oferta) X i xij ≥nj,∀j(restri¸c˜oes de procura) xij ≥0 Slide 9 Distribui¸c˜ao de frigor´ıficos – a rede de transportes Disponibilidades d1= 20 d2= 20 d3= 20 Pidi= 60 Origens Destinos 1 2 3 1 2 3 2 4 3 1 5 2 1 1 6 Necessidades n1= 10 n2= 30 n3= 20 Pjnj= 60 Disponibilidades totais =Procura total ¤ £ ¡ ¢ Problema na forma “standard” Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 5 Slide 10 Forma “standard” de um PT Poferta = Pprocura m Tudo o que est´a nas origens ´e transportado para os destinos. ⇓ As restri¸c˜oes s˜ao satisfeitas nas igualdades. Somando •as equa¸c˜oes das restri¸c˜oes da oferta •as equa¸c˜oes das restri¸c˜oes da procura obt´em-se a mesma equa¸c˜ao! X iX j xij =Pidi& iguais X jX i xij =Pjnj% — Equa¸c˜oes linearmente dependentes −→ h´a uma equa¸c˜ao a mais Conclus˜ao: Num PT na forma “standard” s´o ´e necess´ario considerar node origens + node destinos -1 equa¸c˜oes. Slide 11 Resolu¸c˜ao de um PT •modelo de PT ´e um modelo de PL ⇒m´etodo Simplex; •s˜ao problemas com uma estrutura particular ⇒desenvolvimento de um algoritmo espec´ıfico, que tira partido dessas particularidades, baseado no Simplex e noutros conceitos de PL avan¸cada. Quadro para o algoritmo de transportes 2 4 3 1 5 2 1 1 6 10 30 20 20 20 20 1 2 3 12 3 Destinos O r i g e n s ⇔Formula¸c˜ao como um PT Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 6 Slide 12 Gera¸c˜ao de uma solu¸c˜ao inicial (i) Regra dos custos m´ınimos Slide 13 Gera¸c˜ao de uma solu¸c˜ao inicial (ii) Regra do canto NW Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 7 Slide 14 Solu¸c˜oes iniciais (b´asicas) degeneradas 2 4 3 1 5 2 1 1 6 10 10 -- -- 20 -- -- -- 20 •Apenas 4 vari´aveis diferentes de zero. •n + m - 1 = 5 vari´aveis b´asicas necess´arias. Logo, teremos que “promover” uma vari´avel nula a b´asica. (Solu¸c˜ao b´asica degenerada) Regra para escolha da vari´avel nula que ser´a considerada b´asica: O grafo representativo das vari´aveis b´asicas ter´a que ser uma ´arvore e conexo Logo, poderemos tomar x13,x23,x31 ou x32, mas n˜ao x21. 1 2 3 1 2 3 x11 Slide 15 Algoritmo de transportes (i) 1 – C´alculo dos custos marginais Para cada vari´avel b´asica xij definem-se dois custos (os custos marginais) que somados d˜ao o custo unit´ario de transporte dessa vari´avel b´asica, cij. O custo de transportar uma unidade de ipara jpode ser entendido como a soma de 2 custos: •ui(custo de despacho em i) •vj(custo de recep¸c˜ao em j) ´ E necess´ario arbitrar um destes custos para uma das vari´aveis b´asicas (normalmente arbitra-se 0 para o custo do canto superior esquerdo). 2 4 3 1 5 2 1 1 6 2 3 5 021 10 10 0 -- 20 -- -- -- 20 Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 8 Slide 16 Algoritmo de transportes (ii) 2 – C´alculo das diferen¸cas Para todas as vari´aveis n˜ao b´asicas calcula-se um ∆ij =cij −[ui+vj]. Entrar´a na base a vari´avel n˜ao b´asica com ∆ij mais negativo (problema de minimiza¸c˜ao). Ao entrar na base esta vari´avel deixa de valer 0 passando a valer Θ, positivo. O valor das vari´aveis b´asicas altera-se de forma a respeitarem-se disponibilidades e necessidades. O valor de Θ ser´a tal que nenhuma vari´avel venha negativa. 2 4 3 -2 1 5 -2 2 2 3 5 021 10 10 0 -- 20 -- -- -- 20 -4 1 -6 1 6 − 2 4 3 -2 1 5 -2 2 2 3 5 021 10 10-θ0+ θ -- 20 -- -- θ20 - θ -4 1 -6 1 6 θ = 10 Slide 17 Continuando a resolver... 2 6 4 3 -8 1 5 -8 2 2 9 5 0 -4 1 10-θ-- 10+θ θ20-θ-- -- 10+θ10 - θ -4 1 1 6 θ = 10 2 -2 4 3 1 5 0 2 2 1 -3 041 0-θ θ 20 10+θ10-θ-- -- 20 -- 4 1 1 8 6 θ = 0 2 2 4 3 1 5 -2 2 0 1 -3 0 4 3 -- 0+θ 20 −θ 10 10-θ θ -- 20 -- 4 1 1 6 6 θ = 10 0 2 4 3 1 2 5 2 2 1 -1 021 -- 10 10 10 -- 10 -- 20 -- 2 1 1 6 6 Solução óptima x12 = 10, x13 = 10, x21 = 10, x23 = 10, x32 = 20 Custo ´optimo = 10 ×4 + 10 ×3 + 10 ×1 + 10 ×2 + 20 ×1 = 120 Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 15 Slide 29 Algoritmo de aplica¸c˜ao do m´etodo h´ungaro Metodologia: Subtrair custos suficientemente elevados `as v´arias linhas e colunas de modo a que a afecta¸c˜ao ´optima seja encontrada por inspec¸c˜ao. Algoritmo: 1. subtrair a cada linha o menor elemento dessa linha; 2. subtrair a cada coluna o menor elemento dessa coluna; 3. riscar as linhas e colunas em que algum dos elementos vale zero usando o menor n´umero de riscos poss´ıvel (Sugest˜ao: riscar primeiro as linhas ou colunas com maior n´umero de zeros ainda n˜ao riscados costuma resultar!); 4. se o n´umero de linhas e colunas riscadas for igual a n(n´umero de itens a afectar), encontrou-se a afecta¸c˜ao ´optima: ela ´e constitu´ıda por nzeros independentes; 5. sen˜ao, selecciona-se o menor elemento n˜ao riscado e subtrai-se a todos os elementos n˜ao riscados e adiciona-se a todos os elementos que est˜ao no cruzamento de dois riscos. Volta-se ao ponto 3. Slide 30 Layout fabril Uma f´abrica possui 4 locais (1,2,3,4) para receber 3 m´aquinas novas (A,B,C). O local 4 ´e demasiado pequeno para conter a m´aquina A. O custo de manipula¸c˜ao dos materiais que s˜ao processados nas m´aquinas, em centenas de escudos/hora, envolvendo cada m´aquina e as respectivas posi¸c˜oes, ´e o seguinte: 1 2 3 4 A 5 1 3 X B 3 1 4 3 C 3 3 4 2 O objectivo ´e determinar que local ocupar´a cada uma das novas m´aquinas, de forma a minimizar o custo total de manipula¸c˜ao dos materiais. Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 16 Slide 31 Resolu¸c˜ao do problema de layout fabril 1 2 3 4 A513∞ B 3 1 4 3 C 3 3 4 2 F 0 0 0 0 1 2 3 4 A 4 0 2 ∞ B 2 0 3 2 C 1 1 2 0 F 0 0 0 0 3 riscos <4 1 2 3 4 A 2 0 0 ∞ B 0 0 1 0 C 1 3 2 0 F 0 2 0 0 4 riscos Solu¸c˜ao ´optima Solu¸c˜oes ´optimas: {A2, B1, C4, F3} ou {A3, B2, C4, F1} Custo: 6 Slide 32 Asa de Luxo Lda. A empresa de transportes Asa de Luxo comprou 3 novos pequenos avi˜oes. Ap´os um estudo de mercado foram identificados 4 poss´ıveis destinos para os novos voos a estabelecer: Monte Carlo, Ilhas Can´arias, Biarritz e as Ilhas Gregas. Para cada um dos destinos foi estimado o lucro que cada avi˜ao proporcionaria: Destino A1A2A3 Monte Carlo 8 11 10 Ilhas Can´arias 10 9 9 Biarritz 9 4 8 Ilhas Gregas 6 7 5 (lucros em M$) Numa reuni˜ao, o administrador da Asa de Luxo (que possui um apartamento em Biarritz) decidiu que Biarritz seria necessariamente o destino de um dos 3 avi˜oes. Por outro lado, o Director de Marketing considerou que, por uma quest˜ao de estrat´egia, se deveria atingir o maior n´umero poss´ıvel de destinos, n˜ao enviando mais do que um avi˜ao para cada destino. O respons´avel pela manuten¸c˜ao chamou a aten¸c˜ao para o facto de os avi˜oes A1eA3n˜ao poderem aterrar nas Ilhas Gregas. Decida que avi˜ao deve seguir para cada destino e ganhe uma viagem gr´atis para um destino `a sua escolha (oferecida pela Asa de Luxo, obviamente!) Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 17 Slide 33 Resolu¸c˜ao do problema da Asa de Luxo Lda. Problema de maximiza¸c˜ao ⇒calcular o complemento para o m´aximo (neste caso 11) de todos os elementos da matriz e resolver o problema como se fosse de minimiza¸c˜ao. MC IC B IG A18 10 9 6 A211 9 4 7 A310 9 8 5 F 0 0 0 0 MC IC B IG A13 1 2 5 A20 2 7 4 A31 2 3 6 F 11 11 11 11 MC IC B IG A13 1 2 ∞ A20 2 7 4 A31 2 3 ∞ F 11 11 ∞11 ··· Slide 34 Bibliografia •Ferreira, Jos´e Ant´onio Soeiro (1995). Apontamentos de Investiga¸c˜ao Operacional 1. FEUP. •Hillier, Frederick S. e Lieberman, Gerald (1995). Introduction to Operations Research, Mc Graw-Hill. •Oliveira, Jos´e Fernando (1996). Apontamentos de Investiga¸c˜ao Operacional 1. FEUP. Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 18 Slide 35 Problemas de Fluxo M´aximo Slide 36 Problemas de Fluxo M´aximo Defini¸c˜ao: Dada uma rede, com um n´o de entrada e um n´o de sa´ıda, com capacidades associadas a cada ramo, pretende-se saber qual ´e o fluxo m´aximo, de um certo bem, que se pode enviar da entrada para a sa´ıda. Modelo: xij – fluxo que passa no ramo (i, j), de ipara j cij – capacidade do ramo (i, j) N´o 1 – N´o de entrada N´o t– N´o de sa´ıda max X j x1j=X i xit suj. a: X i xik =X j xkj,∀k(equil´ıbrio de fluxos nos n´os) xij ≤cij,∀i,j (restri¸c˜oes de capacidade) xij ≥0,∀i,j Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 19 Slide 37 Algoritmo de fluxo m´aximo 1. injectar um fluxo nulo no n´o de entrada; 2. capacidades iniciais dos ramos = capacidade total dos ramos; 3. determinar um caminho n˜ao saturado (capacidade 6= 0) entre o n´o de entrada e o n´o de sa´ıda; se n˜ao existir, foi encontrada a SOLUC¸ ˜ AO ´ OPTIMA; 4. somar ao fluxo de entrada um fluxo igual `a capacidade do caminho seleccionado; 5. alterar as capacidades dos ramos do caminho seleccionado, diminuindo-lhes o fluxo injectado; 6. voltar ao ponto 3. Notas: •caminho – conjunto de ramos, unindo o n´o de entrada ao n´o de sa´ıda e que n˜ao passa duas vezes pelo mesmo n´o; •capacidade de um caminho – menor capacidade dispon´ıvel de entre todos os ramos que fazem parte do caminho; •caminho saturado – caminho com capacidade nula; Slide 38 Exemplo de um problema de fluxo m´aximo Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 20 Slide 39 E se os caminhos fossem saturados por outra ordem? Aparentemente n˜ao h´a nenhum caminho n˜ao saturado entre a entrada e a sa´ıda e o fluxo “m´aximo” deu menor do que no caso anterior... N˜ao ´e este um algoritmo de optimiza¸c˜ao? Slide 40 Fluxos “negativos” De facto o exemplo anterior n˜ao est´a completamente resolvido (at´e `a optimalidade) porque existe ainda um caminho n˜ao saturado. Para se encontrar este caminho n˜ao saturado ´e necess´ario considerar o conceito de fluxo “negativo”, isto ´e, fluxo que atravessa os ramos no sentido contr´ario `a sua orienta¸c˜ao. Uma das restri¸c˜oes apresentadas no modelo do problema de fluxo m´aximo impunha que todos os fluxos fossem positivos ou nulos (xij ≥0). E de facto, na solu¸c˜ao final tal ter´a sempre que acontecer. No entanto, essa solu¸c˜ao final obt´em-se pela adi¸c˜ao dos v´arios fluxos que vamos injectando na rede. Alguns desses fluxos poder˜ao atravessar algum ramo no sentido contr´ario ao indicado, devendo nesse caso ser contabilizados como negativos. O resultado final (soma de todos os fluxos que foram injectados nesse ramo) ´e que ter´a que ser positivo ou nulo. No fundo um fluxo “negativo” mais n˜ao ´e do que deixar de fazer passar fluxo por esse ramo. Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 21 Slide 41 Fluxos “negativos” Observando a rede deste ponto de vista conclui-se que o caminho 1-3-2-4 n˜ao est´a saturado: •O ramo 1-3 tem uma capacidade de 2. •O ramo 2-3, visto do lado do n´o 2, est´a saturado. No entanto visto do lado do n´o 3, que ´e o lado que nos interessa visto o caminho o precorrer de 3 para 2, tem uma capacidade de 3, que ´e o fluxo que o atravessa de 2 para 3. •O ramo 2-4 tem uma capacidade de 1. Ent˜ao a capacidade do caminho ´e 1 e ´e poss´ıvel injectar mais uma unidade de fluxo na rede: Consegue-se ter a certeza se uma rede est´a na situa¸c˜ao de fluxo m´aximo atrav´es da rela¸c˜ao entre fluxo m´aximo e cortes m´ınimos. Slide 42 Fluxos m´aximos e cortes m´ınimos Defini¸c˜ao: Um corte numa rede com n´o de entrada Se n´o de sa´ıda T´e um conjunto de arcos cuja remo¸c˜ao separa a rede em duas partes, XeY, uma contendo Se outra contendo T. Acapacidade de um corte ´e a soma das capacidades dos arcos do corte, que est˜ao dirigidos de Xpara Y. Um corte m´ınimo ´e um corte com a menor capacidade poss´ıvel. Valor de qualquer fluxo ≤Capacidade de qualquer corte Valor do fluxo m´aximo ≤Capacidade de qualquer corte Valor do fluxo m´aximo ≤Capacidade de um corte m´ınimo Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 22 Slide 43 Teorema do Fluxo M´aximo–Corte M´ınimo Teorema: O valor do fluxo m´aximo ´e igual `a capacidade do corte m´ınimo. Demonstra¸c˜ao: Seja uma rede na situa¸c˜ao de fluxo m´aximo. Seja Xo conjunto de n´os que pode ser atingido a partir de Satrav´es de um caminho n˜ao saturado, e seja Yo conjunto dos restantes n´os. T∈Yporque sen˜ao T∈Xe n˜ao se estava numa situa¸c˜ao de fluxo m´aximo. Considere-se o corte composto pelos ramos com uma extremidade em Xe outra em Y. Todos os arcos dirigidos de um n´o Vem Xpara um n´o Wem Yest˜ao saturados, pois caso contr´ario Wpertenceria a Xe n˜ao a Y. Qualquer arco dirigido de Ypara Xter´a fluxo nulo pois caso contr´ario isso seria um retorno de fluxo de Ypara Xque, se fosse anulado, aumentaria o fluxo que efectivamente chega a T, o que contraria a hip´otese inicial de a rede estar na situa¸c˜ao de fluxo m´aximo. Ent˜ao, a capacidade do corte, que ´e igual ao fluxo de Xpara Y, ´e igual ao fluxo na rede, que ´e m´aximo. Slide 44 Aplica¸c˜ao de cortes a redes de fluxos Uma rede est´a ent˜ao na situa¸c˜ao de fluxo m´aximo se existir um corte m´ınimo, isto ´e que separa a entrada da sa´ıda da rede e que s´o atravessa ramos orientados da entrada para a sa´ıda saturados e ramos orientados da sa´ıda para a entrada com fluxo nulo. Nesta rede n˜ao existe um corte com essas propriedades. O corte constitu´ıdo pelos ramos 2-4 e 3-4 ´e um corte m´ınimo. Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 23 Slide 45 Exerc´ıcio Determine a quantidade m´axima de um produto que pode ser enviada atrav´es da rede seguinte, entre a origem e o destino 4. Existem limita¸c˜oes nas quantidades que podem atravessar cada arco, encontrando-se as respectivas quantidades m´aximas representadas junto a cada arco. Considere que esse produto se encontra dispon´ıvel na origem 0 em quantidade ilimitada. Em que arco(s) aumentaria as quantidades m´aximas admiss´ıveis, de forma a conseguir aumentar a quantidade m´axima de produto que ´e poss´ıvel fazer passar pela rede? Slide 46 Exerc´ıcio Uma parte do ShopShopping vai ser constru´ıda imitando uma plataforma de explora¸c˜ao subaqu´atica: duas grandes c´upulas ligadas por um grande corredor. Para que a circula¸c˜ao de pessoas no centro comercial decorra de uma forma fluida, ´e necess´ario que este corredor n˜ao restrinja o fluxo m´aximo que pode atravessar a sec¸c˜ao subaqu´atica do centro comercial. Na figura seguinte representa-se esquematicamente a planta desta parte do ShopShopping. Entrada Saída Cúpula 1 Cúpula 2 1 2 3 2 1 2 3 54? 2 22 1 1 1 1 33 4 Em cada corredor est´a indicada a capacidade (em dezenas de pessoas por minuto) de circula¸c˜ao nesse corredor. O corredor de liga¸c˜ao entre as duas c´upulas est´a ainda por dimensionar, dado o seu elevado custo, crescente com o aumento de capacidade que se lhe queira atribuir. Note que por quest˜oes de seguran¸ca e fluidez de circula¸c˜ao os corredores funcionam como caminhos de sentido ´unico (ver setas na figura). Resolvendo este problema como de fluxo m´aximo indique qual deve ser a capacidade do corredor de liga¸c˜ao de forma a que o fluxo que atravessa as c´upulas seja m´aximo e o custo do corredor de liga¸c˜ao o menor poss´ıvel. Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 24 Slide 47 Bibliografia •Dolan, Alan e Aldous, Joan (1993). Networks and Algorithms: an introductory approach. John Wiley and Sons. •Oliveira, Jos´e Fernando (1996). Apontamentos de Investiga¸c˜ao Operacional 1. FEUP. •Taha, Hamdy A. (1997). Operations Research, an Introduction. Prentice Hall. Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 31 Slide 59 ´ Arvore de Suporte de Comprimento M´ınimo Minimal Spanning Tree Slide 60 ´ Arvore de 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. Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 32 Slide 61 Algoritmo 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; Repetir 2. at´e que todos os n´os estejam ligados entre si. Slide 62 Algoritmo guloso – Exemplo 5 4 5 3 6 33 4 13 2 5 4 5 4 5 3 6 33 4 13 2 5 4 5 4 5 3 6 33 4 13 2 5 4 5 4 5 3 6 33 4 13 2 5 4 5 4 5 3 6 33 4 13 2 5 4 5 4 5 3 6 33 4 13 2 5 4 123 456 Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 33 Slide 63 Circuitos Eulerianos Slide 64 Circuitos Eulerianos – O problema das Pontes de K¨onigsberg O rio Pregel banha a cidade de K¨onigsberg, na Pr´ussia Oriental, e rodeia a ilha de Kneiphof. A ligar os v´arios pontos das margens, havia 7 pontes dispostas como se representa na figura. No seu passeio dominical, os habitantes da cidade procuravam voltar ao ponto de partida, passando uma s´o vez por todas as pontes. Leonard Euler estudou o problema e demonstrou a sua impossibilidade em 1736. Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 34 Slide 65 Circuitos Eulerianos Defini¸c˜ao de Circuito Euleriano: Um Circuito Euleriano, ´e um caminho finito em que o n´o inicial coincide com o n´o final e que passa uma ´unica vez por todos os arcos da rede. •grafo orientado: Circuito •grafo n˜ao orientado: Ciclo Teorema de Euler: Um grafo admite um circuito euleriano se e s´o se for conexo e o n´umero de v´ertices de grau impar for zero. (o grau de um v´ertice, corresponde ao n´umero de arcos incidente no v´ertice) Slide 66 Problema do Carteiro Chinˆes “Chinese Postman Problem (CPP)” Problema (Kwan, 1962): Definir circuitos que se aproximem do Circuito Euleriano ideal (repetindo arcos em n´umero m´ınimo ou de modo a tornar m´ınimo o aumento de percurso). Redes de distribui¸c˜ao linear: •recolha de lixo numa cidade; •distribui¸c˜ao domicili´aria do correio; •inspec¸c˜ao peri´odica de redes de energia, de telefones . . . Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 35 Slide 67 Circuitos Hamiltonianos Slide 68 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 de um passatempo imaginado pelo islandˆes Hamilton (1859), no qual se procurava encontrar um caminho que percorresse 20 cidades de todo o mundo, representadas pelos v´ertices de um dodecaedro de madeira, voltando ao ponto inicial. Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 36 Slide 69 Problema do Caixeiro Viajante “Travelling Salesman Problem (TSP)” Problema: 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. Trata-se da pesquisa do circuito hamiltoniano mais curto num grafo de n+ 1 v´ertices. O n´umero de solu¸c˜oes poss´ıveis ´e n!. •Algoritmos conducentes `a solu¸c˜ao ´optima, baseiam-se por exemplo em “Branch and Bound” (Little, 1963) e s˜ao pouco eficientes. •Algoritmos que levam a solu¸c˜oes quase ´optimas, baseiam-se em regras heur´ısticas (Cicero-Ruggiero, 1972) e s˜ao muito eficientes. Slide 70 Problema do Caixeiro Viajante (TSP) — Modelo Vari´aveis de decis˜ao xij =   1 se a cidade jseguir imediatamente a cidade i 0 se n˜ao Fun¸c˜ao objectivo min n X i=1 n X j=1 dijxij Restri¸c˜oes Pn i=1 xij = 1 ∀j Pn j=1 xij = 1 ∀i Pi∈StPi∈¯ Stxij ≥1∀St⊂V(cidades) e ainda . . . restri¸c˜oes que eliminam Sub-tours . . . Jos´e Fernando Oliveira – FEUP Problemas de Decis˜ao em Redes 37 Slide 71 Bibliografia •Sousa, Jorge Pinho (1985). Apontamentos para as aulas pr´aticas de Investiga¸c˜ao Operacional. FEUP. Jos´e Fernando Oliveira – FEUP