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

versão impressa ISSN 0101-7438 / versão online ISSN 1678-5142
Pesquisa Operacional, v.25, n.3, p.349-382, Setembro a Dezembro de 2005 349
MÉTODOS DO TIPO DUAL SIMPLEX PARA PROBLEMAS DE
OTIMIZAÇÃO LINEAR CANALIZADOS
Ricardo Silveira Sousa
Carla Taviane Lucke da Silva
Marcos Nereu Arenales *
Departamento de Matemática Aplicada e Estatística
Inst. de Ciências Matemáticas e de Computação (ICMC)
Universidade de São Paulo (USP)
São Carlos – SP [e-mail] [e-mail] [e-mail] * Corresponding author / autor para quem as correspondências devem ser encaminhadas
Recebido em 03/2004; aceito em 07/2005 após 1 revisão
Received March 2004; accepted July 2005 after one revision
Resumo
Neste artigo estudamos o problema de otimização linear canalizado (restrições e variáveis canalizadas, chamado formato geral) e desenvolvemos métodos do tipo dual simplex explorando o problema dual, o qual é linear por partes, num certo sentido não-linear. Várias alternativas de busca unidimensional foram examinadas. Experimentos computacionais revelam que a busca unidimensional exata na direção dual simplex apresenta melhor desempenho.
Palavras-chave: otimização linear; otimização linear por partes; método dual simplex.
Abstract
In this paper we study the linear optimization problem lower and upper constrained (i.e., there are lower and upper bounds on constraints and variables) and develop dual simplex methods that explore the dual problem, which is piecewise linear, in some sense nonlinear. Different one-dimensional searches were examined. Computational experiments showed that the exact one-dimensional search in the dual simplex direction has the best performance.
Keywords: linear optimization; linear piecewise optimization; simplex dual method.
Sousa, Silva & Arenales – Métodos do tipo dual simplex para problemas de otimização linear canalizados
350 Pesquisa Operacional, v.25, n.3, p.349-382, Setembro a Dezembro de 2005
1. Introdução
O