ࡱ> 130 bjbjUU = ??  1111 = 1,hIIIIII_ k6TsIIssIIssssIIsssssIld1ss0,ssss8ssssssssssss,sssssssssssss :DISSERTAO Ttulo: Algoritmos para uma Variante do Problema da rvore Geradora Mnima Generalizado com Prmios nos Vrtices RESUMO O Problema da rvore Geradora Mnima Generalizado (PAGMG) pode ser modelado sobre um grafo G conexo, no direcionado e ponderado cujos vrtices esto divididos em componentes. O objetivo do PAGMG encontrar uma rvore T que cubra exatamente um vrtice de cada componente de G, de forma que a soma dos custos das arestas de T seja mnima. A verso at Least do PAGMG, L-PAGMG, objetiva encontrar uma rvore T que cubra pelo menos um vrtice de cada componente de G. O PAGMG com Coleta de Prmios (CP-PAGMG), baseado no PAGMG, objetiva minimizar a diferena do custo total das arestas utilizadas pela soma total dos prmios coletados nos vrtices selecionados. Considerando as verses do PAGMG apresentadas, pode-se afirmar que estas so anlogas a muitos problemas na vida real. No entanto, elas ainda no se aplicam a algumas classes de problemas mais especficos, como por exemplo problemas em que exigido um prmio (ou capacidade) mnimo para cada componente. Dessa forma, observou-se a necessidade de definir problemas que sejam mais especficos e que possam representar ainda mais problemas da vida real. Com este intuito, este trabalho prope uma nova variante para o PAGMG com Prmios nos Vrtices (PAGMG-P). Sua definio baseada no L-PAGMG, com a caracterstica adicional de que existe um prmio no negativo associado a cada vrtice e cada componente possui um prmio mnimo a ser adquirido. No foram encontrados trabalhos sobre o PAGMG-P na literatura. Dessa forma, este trabalho prope formulaes matemticas, mtodos heursticos e exatos e instncias do problema para analisar o desempenho dos mtodos. As duas formulaes matemticas propostas foram baseadas em formulaes da literatura; a primeira formulao foi baseada no L-PAGMG enquanto a segunda no CP-PAGMG. A segunda formulao gerou melhores resultados, tanto em tempo computacional quanto em custo da soluo encontrada. As metaheursticas implementadas foram GRASP e ILS, e ambas utilizaram o VND como mtodo de aprimoramento. Os resultados alcanados com o ILS se sobressaram tanto no custo da soluo encontrada quanto no tempo de execuo. O mtodo exato proposto utiliza os resultados das metaheursticas como entrada. Esse mtodo alcanou os melhores resultados entre os algoritmos propostos quando a metaheurstica utilizada foi a ILS. So apresentados testes computacionais que ilustram a eficincia do mtodo proposto. Palavras-chave: Metaheursticas. Programao Matemtica. Problema da rvore Geradora Mnima Generalizado. ABSTRACT The Generalized Minimum Spanning Tree Problem (GMSTP) can be modeled in a weighted and undirected graph G whose vertices are divided into components. GMSTP aims to find a tree T that covers exactly one vertex in each component of G, minimizing the sum of edges costs. The GMSTP at Least version, L-GMSTP, aims to find a tree T that covers at least one vertex in each component of G. The Prize-Collecting GMSTP (PC-GMSTP), based on GMSTP, aims to minimize the difference between the sum of the selected edge costs and the sum of the collected prizes in the selected vertices. We notice that these versions of the GMSTP can model many problems in real life. However, they still do not apply to some classes of more specific problems, such as problems that require a minimum prize (or capacity) in each component. Therefore, we notice the need to define problems that are more specific and that may represent more problems in real life. In order to reach this goal, we propose a new GMSTP variant with prizes in the vertices (P-GMSTP). This new problem is based on the L-GMSTP variant, with the additional feature that there is a non-negative prize associated to each vertex and each component has a minimum prize to be collected. We did not find any studies about P-GMSTP in the literature. Thus, we propose mathematical formulations, exact and heuristic algorithms and instances for this variant. The two mathematical formulations proposed were based on formulations in the literature; the first formulation was based on L-PAGMG and the second formulation was based on the PC-PAGMG. The second formulation produced the best results. Furthermore, a GRASP and an ILS metaheuristics were implemented, and both used the VND as an improvement method. The achieved results with the ILS have excelled both in cost of the solution found as at run time. The proposed exact method uses the results of the metaheuristics as input. This method achieved the best results among the proposed algorithms when the ILS metaheuristic was used. Computational experiments are presented to illustrate the efficiency of the methods proposed. Keywords: Metaheuristics. Mathematical Programming. Generalized Minimum Spanning Tree Problem. }b d   U V [ce'F   пппппппЮЙo.h? h~5CJOJQJ\^JaJmH sH "h~CJOJQJ^JaJmH sH (h? h~CJOJQJ^JaJmH sH  h~5CJOJQJ\^JaJ h~6CJOJQJ]^JaJh~CJOJQJ^JaJ hh~CJOJQJ^JaJ h~5CJOJQJ\^JaJ  ~ [de     $`a$gd? $a$gd? $`a$$a$$a$gd? $a$;0P:pX/ =!"#$% Dpn  666666666666666666666666666666666666666666 6666666666 666666666666 6666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~$OJPJQJ^J_HmHnHsHtHP`P XNormald!B*CJ_HaJmHphsHtHHH X0 Heading 1$$x@&CJ(aJ(HH X0 Heading 2$$hx@&CJ aJ RR X0 Heading 3$$@P@&B*CJaJphCCCRR X0 Heading 4$$P@&B*CJaJphfffJJ X0 Heading 5$$P@& B*phfffPP X0 Heading 6$$P@&6B*]phfffDA D 0Default Paragraph FontRiR 0 Table Normal4 l4a (k ( 0No List `/` FaHeading 1 Char+5B*CJ KH OJPJQJ\^JaJ phb/b FaHeading 2 Char-56B*CJOJPJQJ\]^JaJph\/\ FaHeading 3 Char'5B*CJOJPJQJ\^JaJph\/!\ FaHeading 4 Char'5B*CJOJPJQJ\^JaJphb/1b FaHeading 5 Char-56B*CJOJPJQJ\]^JaJphT/AT FaHeading 6 Char5B*OJPJQJ\^Jph8>8 X0Title $$<CJ4aJ4X/aX Fa Title Char+5B*CJ KHOJPJQJ\^JaJ phHJH X0Subtitle $$@B*CJaJphfffT/T Fa Subtitle Char!B*CJOJPJQJ^JaJphPK![Content_Types].xmlj0Eжr(΢Iw},-j4 wP-t#bΙ{UTU^hd}㨫)*1P' ^W0)T9<l#$yi};~@(Hu* Dנz/0ǰ $ X3aZ,D0j~3߶b~i>3\`?/[G\!-Rk.sԻ..a濭?PK!֧6 _rels/.relsj0 }Q%v/C/}(h"O = C?hv=Ʌ%[xp{۵_Pѣ<1H0ORBdJE4b$q_6LR7`0̞O,En7Lib/SeеPK!kytheme/theme/themeManager.xml M @}w7c(EbˮCAǠҟ7՛K Y, e.|,H,lxɴIsQ}#Ր ֵ+!,^$j=GW)E+& 8PK!Ptheme/theme/theme1.xmlYOo6w toc'vuر-MniP@I}úama[إ4:lЯGRX^6؊>$ !)O^rC$y@/yH*񄴽)޵߻UDb`}"qۋJחX^)I`nEp)liV[]1M<OP6r=zgbIguSebORD۫qu gZo~ٺlAplxpT0+[}`jzAV2Fi@qv֬5\|ʜ̭NleXdsjcs7f W+Ն7`g ȘJj|h(KD- dXiJ؇(x$( :;˹! I_TS 1?E??ZBΪmU/?~xY'y5g&΋/ɋ>GMGeD3Vq%'#q$8K)fw9:ĵ x}rxwr:\TZaG*y8IjbRc|XŻǿI u3KGnD1NIBs RuK>V.EL+M2#'fi ~V vl{u8zH *:(W☕ ~JTe\O*tHGHY}KNP*ݾ˦TѼ9/#A7qZ$*c?qUnwN%Oi4 =3ڗP 1Pm \\9Mؓ2aD];Yt\[x]}Wr|]g- eW )6-rCSj id DЇAΜIqbJ#x꺃 6k#ASh&ʌt(Q%p%m&]caSl=X\P1Mh9MVdDAaVB[݈fJíP|8 քAV^f Hn- "d>znNJ ة>b&2vKyϼD:,AGm\nziÙ.uχYC6OMf3or$5NHT[XF64T,ќM0E)`#5XY`פ;%1U٥m;R>QD DcpU'&LE/pm%]8firS4d 7y\`JnίI R3U~7+׸#m qBiDi*L69mY&iHE=(K&N!V.KeLDĕ{D vEꦚdeNƟe(MN9ߜR6&3(a/DUz<{ˊYȳV)9Z[4^n5!J?Q3eBoCM m<.vpIYfZY_p[=al-Y}Nc͙ŋ4vfavl'SA8|*u{-ߟ0%M07%<ҍPK! ѐ'theme/theme/_rels/themeManager.xml.relsM 0wooӺ&݈Э5 6?$Q ,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}|$b{P8g/]QAsم(#L[PK-![Content_Types].xmlPK-!֧6 +_rels/.relsPK-!kytheme/theme/themeManager.xmlPK-!Ptheme/theme/theme1.xmlPK-! ѐ' theme/theme/_rels/themeManager.xml.relsPK]    _GoBack  +?  `~o&XW @ @@UnknownG*Ax Times New Roman5Symbol3. *Cx Arial7@Cambria7.@CalibriACambria Math"SS!0$P  `!xx DISSERTAOHelioHelioOh+'0|  8 D P\dlt DISSERTAOHelioNormal_WordconvHelio2Microsoft Office Outlook@^в@(d@(d՜.+,0 hp|    DISSERTAO Title !"#$%&')*+,-./2Root Entry F!td41TableWordDocument= SummaryInformation( DocumentSummaryInformation8(CompObjy  F'Microsoft Office Word 97-2003 Document MSWordDocWord.Document.89q  F#Documento do Microsoft Office Word MSWordDocWord.Document.89q