skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices

Métodos tipo dual simplex para problemas de otimização linear canalizados

Sousa, Ricardo Silveira

Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Ciências Matemáticas e de Computação 2005-09-30

Acesso online. A biblioteca também possui exemplares impressos.

  • Título:
    Métodos tipo dual simplex para problemas de otimização linear canalizados
  • Autor: Sousa, Ricardo Silveira
  • Orientador: Arenales, Marcos Nereu
  • Assuntos: Não Disponível; Not Available
  • Notas: Tese (Doutorado)
  • Descrição: 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.
  • DOI: 10.11606/T.55.2005.tde-21082015-135958
  • Editor: Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Ciências Matemáticas e de Computação
  • Data de criação/publicação: 2005-09-30
  • Formato: Adobe PDF
  • Idioma: Português
Links
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.