Metodos do Tipo Dual Simplex Para Problemas de Otimização Linear Canalizados

Metodos do Tipo Dual Simplex Para Problemas de Otimização Linear Canalizados

(Parte 1 de 9)

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

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 rsouza@icmc.usp.br carla@icmc.usp.br arenales@icmc.usp.br

* 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 clássico problema de otimização linear (formato padrão):

Minimizar f(x) = cTx Sujeito a: Ax = b (1.1) em que A é uma matriz m×n, foi formalizado por George B. Dantzig em 1947 que, em seguida, desenvolveu também o método primal simplex para resolvê-lo. Desde então, um número grande de pesquisadores têm contribuído para o campo da otimização linear de diferentes maneiras, seja incluindo desenvolvimentos teóricos e computacionais, seja encontrando novas aplicações práticas.

Logo após a publicação do método primal simplex de Dantzig (1951), sua versão dual surgiu com Lemke (1954), que consiste numa especialização do método primal simplex para o problema dual:

Sujeito a:ATλ ≤ c. (1.2)

Maximizar ϕ(λ) = bTλ

Segundo Maros (2003), o método dual simplex tem atraído considerável interesse, devido à importante aplicação nos métodos de otimização linear inteiro misto, os quais resolvem uma seqüência de problemas de otimização linear, com característica de que uma solução básica dual factível de boa qualidade é sempre disponível para o problema seguinte da seqüência. Segundo Bixby (2001), testes computacionais mostram que o desempenho do método dual simplex pode ser superior ao método primal simplex.

É importante observar que a evolução das implementações computacionais dos resolvedores lineares teve um papel fundamental no progresso da Otimização Linear. Um exemplo disto é o pacote CPLEX, que vem sendo melhorado desde sua primeira versão lançada em 1988. Bixby (2001) relatou que a implementação do método dual simplex, na primeira versão do pacote CPLEX 1.0 rodado numa estação de trabalho UltraSparc de 300 MHz, resolvia um problema de 16223 restrições e 28568 variáveis, com 88340 elementos não nulos em 1217.4 segundos e, o mesmo método na última versão CPLEX 7.1 na mesma máquina, resolvia o mesmo problema em 2.6 segundos. Ou seja, um mesmo método pode se tornar 50 vezes mais rápido dependendo de sua implementação. Vale observar que esta relação de desempenho também foi obtida por Karmarkar (1984), que afirmou que o método de pontos interiores era 50 vezes mais rápido do que o método simplex. Obviamente, estruturas de dados adequadas são fundamentais para um bom desempenho de uma implementação computacional. A despeito disto, um mesmo método pode permitir um número grande de variantes, com desempenhos bastante diversos, como por exemplo, a regra de Dantizg normalizada (conhecida na literatura de língua inglesa por ‘steepest edge rule’. Veja Forrest & Goldfarb, 1992).

O objetivo principal deste trabalho consiste em desenvolver métodos tipo dual simplex para um formato geral de problemas de otimização linear (assim chamado em Vanderbei, 1997, o qual chamamos problemas canalizados) explorando o problema dual linear por partes (em certo sentido, não-linear), com buscas unidimensionais, exatas e inexatas. Em Vanderbei (1997), um método dual simplex para esta classe de problemas foi apresentado, baseado em tableau-simplex, em que se explorasse a natureza linear por partes do problema dual. Em

Sousa, Silva & Arenales – Métodos do tipo dual simplex para problemas de otimização linear canalizados

Pesquisa Operacional, v.25, n.3, p.349-382, Setembro a Dezembro de 2005 351 trabalhos futuros examinaremos o efeito da regra de Dantizg normalizada e certas estruturas de dados, para problemas esparsos de médio e grande porte.

A maioria dos problemas práticos de otimização linear incluem diversos tipos de restrições (limitantes inferiores e/ou superiores, igualdades, variáveis livres, etc.). Para resolver esses problemas, necessita-se de uma versão do algoritmo dual simplex que possa tratar todos os tipos de restrições eficientemente (Maros, 2003). Este trabalho, apresenta o algoritmo dual simplex especializado em resolver problemas canalizados, baseado na característica da função dual simplex, que é linear por partes. A principal característica deste método é que em uma iteração ele pode fazer um progresso equivalente a muitas iterações do dual simplex padrão.

O artigo está organizado da seguinte forma: Na seção 2 relatamos sobre a eficiência e a complexidade computacional do método simplex, na seção 3 é descrito o algoritmo dual simplex linear por partes (Arenales, 1984), e na seção 4 descrevemos algumas modificações para busca unidimensional utilizada no algoritmo. A seção 5 apresenta os primeiros experimentos computacionais. Finalmente na seção 6, temos as conclusões.

2. A Eficiência e a Complexidade Computacional do Método Simplex

A cada iteração do algoritmo simplex, a tarefa mais importante consiste na resolução dos sistemas básicos, que pode ser feito em O(m3) operações elementares. Assim, o esforço necessário para resolver (1.1), pelo algoritmo simplex pode ser medido pelo número de iterações.

A questão da eficiência do método simplex sempre foi tema de pesquisa desde a sua publicação. No início, a convergência finita do método, garantida com regras que evitassem ciclos (repetições indefinidas de uma solução básica), era suficiente para os pesquisadores, mesmo que o número máximo de iterações pudesse ser muito grande. Um conjunto de relatos (a maioria informal e não publicado) sobre sua eficiência computacional para se resolver problemas práticos ou gerados de forma aleatória formou o chamado folclore do método simplex, o qual afirma que, na prática, o número de iterações requeridas é um polinômio de grau baixo em m (número de restrições). Veja Shamir (1987) para uma revisão deste folclore. Sousa (2000) realizou um estudo computacional para o problema de corte de peças em estoque, que envolve milhares de variáveis, e observou que o número de iterações é da ordem de m2, fornecendo uma classe de problemas práticos que reforça o folclore simplex.

A experiência computacional com um número grande de problemas resolvidos em vários anos (Dantzig, 1963; Murty, 1983; Shamir, 1987; Bazaraa et al., 1992) indicou que o número médio de iterações é uma função linear de m, que parece ser menor do que 3m.

No entanto, Klee & Minty (1972) apresentaram um exemplar, para o qual o método simplex com o critério de Dantzig para escolha da variável a entrar na base (i.e., menor custo relativo) necessita de 2n – 1 iterações (onde n é o número de variáveis), percorrendo todos os vértices da região factível do problema, a qual é definida como uma distorção do hipercubo m-dimensional e tem 2n vértices. Assim, o algoritmo simplex não pertence à classe de algoritmos com tempo polinomial. Variações do método simplex, mais tarde, também se mostraram ineficientes, do ponto de vista do estudo do pior caso, necessitando um número exponencial de iterações (Bertsimas & Tsitsiklis, 1997).

Sousa, Silva & Arenales – Métodos do tipo dual simplex para problemas de otimização linear canalizados

352 Pesquisa Operacional, v.25, n.3, p.349-382, Setembro a Dezembro de 2005

Portanto, a questão contínua aberta quanto à possibilidade da construção de um método do tipo simplex que seja polinomial, ou a prova definitiva de que é impossível construir um algoritmo do tipo simplex com complexidade polinomial. Segundo Shamir (1987), Terlaky & Zhang (1993) está é a questão aberta mais desafiante na teoria da otimização linear.

Um resultado interessante foi provado recentemente por Fukuda & Terlaky (1998). Eles provaram que partindo de qualquer base, existe uma seqüência pequena de pivôs contendo no máximo n passos, levando a base ótima. Este resultado indica que algoritmos polinomial podem existir.

3. O Problema de Otimização Linear com Restrições Canalizadas

A classe de problemas de otimização linear com restrições canalizadas é de grande interesse prático, pois representa vários problemas reais, tais como problemas de mistura, planejamento, etc., cujas restrições, ou parte delas, são definidas por limitantes tanto superiores como inferiores, decorrentes de tolerâncias de especificações técnicas, demanda, etc.

3.1 O problema primal

O problema de otimização linear com restrições canalizadas (ou, formato geral, conforme Vanderbei, 1997) é definido por:

Minimizar f(x) = cTx Sujeito a: d ≤ Ax ≤ e, (3.1) em que A∈ Rm× n; d, e ∈ Rm com di ≤ ei i=1,...,m; c, x ∈ Rn.

Suporemos, que posto (A) = n, isto é, suas colunas formam um conjunto de vetores de Rm linearmente independente. A dependência linear indicaria casos triviais de inexistência de soluções ótimas (f(x)→ -∞, admitindo-se que o problema seja factível), ou que o problema independe da variável cuja coluna é combinação linear das demais. Para ver isto, suponha que a n-ésima coluna seja combinação linear das demais: an = 1 j j aγ−=

∑. Considere a matriz elementar

Note que a matriz AE tem as n-1 primeiras colunas iguais à matriz A e a última coluna nula. Assim, considerando a identidade: Ax = (AE)(E-1x) e, com a mudança de variável y=E-1x, as restrições em (3.1) independem de yn. Com esta mudança de variável, a função objetivo f(x) = cTx = (cTE)y tem a coordenada de yn dada por: 1 n1 ccn jγ−=−+∑, que se for nula, então yn pode assumir qualquer valor em toda solução ótima, ou se for não nula, então f(x)→ -∞. Como xn = yn, podemos concluir que o problema ou não tem solução ótima, ou independe da variável xn.

Sousa, Silva & Arenales – Métodos do tipo dual simplex para problemas de otimização linear canalizados

Pesquisa Operacional, v.25, n.3, p.349-382, Setembro a Dezembro de 2005 353

Observe que o problema (3.1) contempla restrições que tipicamente ocorrem na prática, como por exemplo a condição de não negatividade ou a canalização das variáveis.. Consideramos, sem perda de generalidade, que as variáveis sejam canalizadas, isto é, existam restrições do tipo: di ≤ xi ≤ ei, de modo que a matriz A contém uma matriz identidade n×n e, portanto, posto(A)=n. Observe também que restrições de igualdade são representadas no formato geral (3.1) por: di = ei.

O problema (3.1) pode ainda ser rescrito no formato padrão (com variáveis canalizadas), por se definir y = Ax, então (3.1) é equivalente a:

Minimizarf(x) = cTx
Sujeito a:Ax – y = 0 (3.2)

d ≤ y ≤ e.

O formato equivalente (3.2) será empregado na construção do problema dual lagrangiano.

3.2 O problema dual

(Parte 1 de 9)

Comentários