• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

[en] EXTENSION OF THE METHOD OF HALL TO THE PROBLEM OF QUADRATIC ASSIGNEMENT / [pt] UMA EXTENSÃO DO MÉTODO DE HALL PARA O PROBLEMA DE APROPRIAÇÃO QUADRÁTICA

RUDERICO FERRAZ PIMENTEL 11 August 2009 (has links)
[pt] Neste trabalho desenvolveu-se um algoritmo que fornece soluções próximas da solução ótima para o problema de Apropriação Quadrática segundo a formulação particular de Koopmans e Beckmann (15). Em apêndice consta a listagem do programa desenvolvido em FORTRAN IV para a execução do algoritmo. A apresentação do problema encontra-se no capítulo 1 como algumas formulações e aplicações possíveis. Estuda-se também neste capítulo, as relações do problema de Apropriação Quadrática com o problema do Caixeiro Viajante visando facilitar a compreensão do capítulo seguinte. No capítulo 2 procura-se traçar o panorama das tentativas feitas para solucioná-lo e descreve-se sucintamente alguns dos métodos citados. O Algoritmo desenvolvido foi baseado em idéias apresentadas por Hall (11). No capítulo 3 procura-se resumi-las e no capítulo 4 descreve-se o algoritmo propriamente dito destacando-se alguns dos aspectos computacionais. Finalmente no capítulo 5 apresenta-se uma comparação entre os resultados obtidos pelo algoritmo proposto e os resultados obtidos por outros algoritmos para a resolução do mesmo problema. / [en] This work developes na algorithm that furnishes solutions that are almost optimal for the Quadratic Assignment problem as formulated by Koopmans and Beckmann. The presentation of the problem is in Chapter 1 as are some of the possible formulations and applications. This Chapter also studies the relationships between the following problems: Quadratic Assignment, Linear Assignment and Traveling Salesman problem. Chapter 2 presents a general view of the approaches used for it’s solution. The algorithm is based on the ideas presented by Hall. Chapter 3 is a summary of the Hall’s method. Chapter 4 is a detailed description of the algorithm and some of it’s computational aspects. Finally in chapter 5 comparisons are made between the results using the proposed algorithm and the results obtained using other algorithms.

Page generated in 0.0442 seconds