02052nam a2200193 a 450000100080000000500110000800800410001910000190006024500940007926000160017330000110018950001140020052014350031465000230174965000250177265300170179765300160181465300280183010063531998-05-28       1998    bl uuuu  m   00u1 u    #d1 aNARCISO, M. G.  aA relaxação lagrangeana/surrogate e algumas aplicações em otimização combinatória.  a1998.c1998  a121 f.  aTese (Doutorado em Computação Aplicada) - Instituto Nacional de Pesquisas Espaciais, São José dos Campos.  aA relaxação lagrangeana tem sido empregada há muito tempo, com grande sucesso, como auxiliar no desenvolvimento de métodos para a busca de soluções ótimas aos problemas da Otimização Combinatória. Outra relaxação conhecida e empregada, neste contexto, e a relaxação surrogate. Esta relaxação, embora fornece em geral limites melhores que a lagrangeana, nao tem sido empregada frequentemente devido a dificuldade inerente de solução do problema relaxado. Este trabalho tem como objetivo mostrar como informações locais podem melhorar a perfórmance do emprego de relaxações lagrangeanas quando aplicadas em conjunto com métodos subgradientes. Uma versão surrogate da relaxação lagrangeana proporciona uma otimização local, que ira refletir em todas as interações de um método subgradientes. Esta nova forma de uso de informações locais pode ser vista também como uma nova relaxação, denominada neste trabalho de relaxação lagrangeana/surrogate ou simplesmente lagsur. Esta nova proposta foi aplicada ao problema generalizado de atribuição (PGA) e ao problema do caixeiro viajante (PCV) e os resultados obtidos foram melhores do que os obtidos com a relaxação lagrangeana em termos de tempo de execução, principalmente quando as instancias tem grandes dimensões. Além de ganhar em tempo, a relaxação lagsur obteve limites tão bons quantos os fornecidos pela relaxação  lagrangeana.  alinear programming  aProgramação Linear  aComputação  aComputation  aRelaxação lagrangeana