• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Thèse de Doctorat
DOI
10.11606/T.55.2005.tde-21082015-135958
Document
Auteur
Nom complet
Ricardo Silveira Sousa
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Carlos, 2005
Directeur
Jury
Arenales, Marcos Nereu (Président)
Costa, Geraldo Roberto Martins da
Oliveira, Aurelio Ribeiro Leite de
Perez, José Mario Martinez
Silva, Geraldo Nunes
Titre en portugais
Métodos tipo dual simplex para problemas de otimização linear canalizados
Mots-clés en portugais
Não disponível
Resumé en portugais
A otimização linear tem sido objeto de intenso estudo desde a publicação do método simplex de Dantzig em 1947, sendo revigorada a partir de 1984 com a publicação de um método de pontos interiores por Karmarkar, o qual demonstrou ser computacionalmente eficiente e com propriedade de convergência polinomial no estudo do pior caso. Embora muitas variantes do método simplex não tenham complexidade polinomial, elas apresentam um comportamento polinomial em termos do número de restrições do problema, para inúmeros problemas práticos, constituindo o chamado "folclore"' simplex. Nos últimos anos, tem crescido o interesse pela pesquisa sobre eficiência dos métodos tipo simplex. Há uma pergunta subjacente, que talvez constitua o maior desafio da atualidade na teoria da otimização linear: "E possível construir um algoritmo tipo simplex com complexidade polinomial? Além disso, eficiente do ponto de vista prático?"' A resposta a esta pergunta não deve ser trivial e talvez seja negativa, restando por enquanto a tarefa árdua da investigação da complexidade, caso a caso, dos métodos propostos. Neste trabalho aprofundamos a investigação sobre a versão mais utilizada dos métodos do tipo simplex: o método dual simplex, especializado para a forma geral (restrições canalizadas), cujo problema dual é linear por partes. A importância da forma geral não somente porque as demais formas são facilmente representadas nela, mas porque muitos problemas práticos surgem naturalmente desta maneira e técnicas de pré-processamento que buscam apertar limitantes levam a ela. Foram investigadas buscas unidimensional lineares por partes, como regras anti-ciclagem influenciam positivamente sobre o eleito 'estagnação' decorrente de soluções degeneradas, a regra de Dantzig normalizada e algumas técnicas de resolução de sistemas lineares, incluindo o método do gradiente bi-conjugado, que alimenta grande expectativa no aumento da eficiência computacional para resolução de problemas de grande porte.
Titre en anglais
Dual simplex type methods to two-bounded linear optimization problems
Mots-clés en anglais
Not available
Resumé en anglais
Linear optmization has been studied in-depth since 1947, when George Dantizg published lhe Simplex method. From 1984. research on linear optmization was enormously intensiíled because of the publication of the Interior Point method by Narendra Karmarkar, which showed to be computationally effieient for many large and sparse problems, and with polynomial time complexity. Although many variants of the Simplex method do not have polynomial time complexity, they perform well for a number of practical problems, presenting polynomial behaviour, and this constitutes a folklore of Simplex typc methods. Recently, the interest in the efficiency of Simplex methods has increased. There is an underlying question, which is perhaps the biggest challenge nowadays in the Optimization theory: ' i s it possible to build a time polynomial simplex tvpe algorithm, which is effieient from the computational point of view?" The answer to this question is certainly not trivial, and probably it is negative. One is faced with the hard task of investigating the complexity, one by one, of the proposed methods. In this vvork, we study the most used version of the simplex method: the Dual Simplex method, specialized for the general form (two sided constraints), whose dual is a linear piecewise optimization problem. The importance of the general form is not only because it can easily deal with other forms, but many important practical problems arise naturally in this way, and pre-processing techniques of tighting bounds lead to this form. The following aspeets were investigated: different piecewise linear line searching, the effect of stalling phenomena due to degenerate solutions and how anti-cyclic rules can inlluence it positivelv, the steepest edge rule, and some techniques to handle imbedded linear systems, including the iterativo bi-conjugated gradient method, in which an expectation arises to improve the computational performance for very large and sparse problems.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2015-08-21
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
Centro de Informática de São Carlos
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2022. Tous droits réservés.