Métodos do tipo dual simplex para problemas de otimização linear canalizados, Notas de estudo de Administração Empresarial

Baixe Métodos do tipo dual simplex para problemas de otimização linear canalizados e outras Notas de estudo em PDF para Administração Empresarial, somente na Docsity! 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 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) x ≥ 0, 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: Maximizar ϕ(λ) = bTλ Sujeito a: ATλ ≤ c. (1.2) 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 22.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 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: Minimizar f(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 Podemos determinar o problema dual de (3.1) usando o problema equivalente (3.2). Para isto, definimos a função lagrangiana: L(x, y, λ) = cTx + λT(y – Ax) (3.3) L(x, y, λ) = (cT – λTA)x + λTy, λ∈ Rm. Considere o problema langrangiano: (x,y)h( ) min L( , , )=λ x y λ , d ≤ y ≤ e. (3.4) Segue diretamente da definição de (3.4) a clássica desigualdade: f(x) ≥ h(λ), para todo x factível e para todo λ∈Rm. Ou seja, h(λ) fornece um limitante inferior para f(x). Esta desigualdade motiva para o chamado problema dual lagrangiano, ou simplesmente problema dual, que consiste em determinar o melhor limitante inferior: Maximizar h(λ), λ∈Rm. Note que λ qualquer, como definido até agora, pode levar a limitantes inferiores triviais e sem interesse, isto é: h(λ) = – ∞. Assim, restringimos λ tal que o mínimo em (3.4) exista. Como x é irrestrito de sinal e y é canalizado, analisando (3.3), devemos escolher λ tal que: cT – λTA = 0 ou ATλ = c. (3.5) Com λ satisfazendo o sistema de equações lineares em (3.5), é possível expressar h(λ) por se resolver o problema de minimização em (3.4). Usando a restrição (3.5) em (3.3), temos: m T i i i 1 L( , , ) λ y . = = ∑x y λ λ y = Então, i i i i i m i i i i i id y ei 1 i/λ 0 i/λ 0 h( ) min L( , , ) min λ y λ d λ e . ≤ ≤= > < = = = +∑ ∑ ∑λ x y λ Sousa, Silva & Arenales – Métodos do tipo dual simplex para problemas de otimização linear canalizados 354 Pesquisa Operacional, v.25, n.3, p.349-382, Setembro a Dezembro de 2005 A soma de cada mínimo na expressão acima é válida, pois as variáveis yi são independentes. Se λi = 0, então yi pode assumir qualquer valor no intervalo [di, ei]. Assim, podemos explicitar a função objetivo dual como sendo: m i i i 1 h( ) h (λ ) = =∑λ em que i i ii i i i i e λ se λ 0 h (λ ) = d λ se λ 0. ≤  ≥ Ou seja, o problema dual é um problema de otimização onde a função objetivo é côncava linear por partes ilustrada na Figura 1. Figura 1 – Função objetivo dual linear por partes. Desta forma, tendo resolvido o problema de minimização que surge na definição da função dual (3.4), podemos explicitar o problema dual: i ii 1 T Maximizar h( ) h (λ ) Sujeito a : . m = = = ∑λ A λ c (3.6) 3.3 A estratégia dual simplex Note que o problema dual sempre será factível, pois posto (A) = n e λ é irrestrito de sinal. Portanto, se o problema dual tiver solução ótima, então existirá uma solução básica ótima. A definição de uma solução básica para um problema de otimização linear por partes, com a função objetivo separável como em (3.6), é uma simples extensão de definição de solução básica da otimização linear, bastando que as variáveis não básicas sejam fixadas em pontos de não-diferenciação (Cavichia & Arenales, 2000). No caso particular da função dual em (3.6), cada função hi é não diferenciável apenas em λi=0. Observe também que, enquanto di ei λi hi 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 355 uma solução básica factível é um vértice da região das soluções factíveis de um problema de otimização linear, uma solução básica de um problema de otimização linear por partes pode pertencer ao interior da região das soluções factíveis, de modo que a solução ótima pode ser um ponto interior. Em particular, a região das soluções factíveis de (3.6) consiste num subespaço afim de Rm (subespaço transladado) e, portanto, não tem vértices. Para a construção de uma solução básica para o problema (3.6), considere uma partição básica qualquer nas colunas de AT: AT = (BT, NT) (i.e., selecione uma sub-matriz inversível n×n de AT, denotada por BT, e denote por NT a sub-matriz n×(m-n) formada pelas colunas restantes de AT). Esta partição nas colunas de AT introduz uma partição no vetor de variáveis: λ=(λB, λN). O i-ésimo elemento de λB é denotado por iBλ (ou, também: λi , i∈B). A i-ésima coluna de B T é denotada por i T Ba e a k-ésima coluna de N T é denotada por k T Na . Assim, podemos escrever a solução geral do sistema de equações em (3.5): ( ) ( )T T T T T TB N B N.= ⇔ + = ⇔ = − -1 -1 A λ c B λ N λ c λ B c B N λ (3.7) Uma solução particular, chamada solução básica dual, associada à partição básica é dada por: B N ˆ ˆ ˆ        λ λ = λ , onde T T -1 TB Nˆ ˆ= e 0=λ c B λ . (3.8) Note que a solução definida em (3.8), independentemente da partição básica, satisfaz as restrições do problema dual e, portanto, é chamada dual factível. Para a solução básica dual, iB λ̂ pode ser positivo ou negativo (se nulo, é o caso de degeneração dual) e, portanto, para a avaliação da função dual h(λ) o valor de iBy fica determinado por: i i i i i B B B B B ˆd se λ 0 ŷ ˆe se λ 0.  ≥=  ≤ (3.9) Em caso de degeneração da solução dual, i.e., iB λ̂ 0= , iB y pode, a princípio, assumir qualquer valor no intervalo i iB B[d e ] que, por razões práticas, escolheremos i iB Bŷ = d ou i iB Bŷ = e . Deste modo, se escolhermos i iB Bŷ = d , então para efeito de desenvolvimentos futuros, a variável iB λ é vista como positiva (apesar de ter seu valor nulo). Assim, se a variável iBλ sofre um acréscimo, iBŷ não se altera conforme (3.8); caso contrário, um decréscimo em iBλ tornaria a variável negativa e, portanto, iBŷ deveria ser iBe . Observe também que a partição básica fornece uma partição nas equações de (3.2): B B N N x . =    = ⇔    =     y Bx yB y Nx yN Sousa, Silva & Arenales – Métodos do tipo dual simplex para problemas de otimização linear canalizados 358 Pesquisa Operacional, v.25, n.3, p.349-382, Setembro a Dezembro de 2005 Substituindo na expressão acima as componentes básicas da direção dual simplex dadas em (3.13) e a solução básica primal em (3.10), vem que: ( ) ( ) K k K k T T 1 B N N T N N ˆ ˆh( ) h( ) δ (- ) d ˆ ˆh( ) h( ) δ d . −= + + = + + λ λ y B a λ λ -a x (3.15) Em resumo, a perturbação da solução básica dual na direção dual simplex dada por (3.14), decorrente da estratégia dual simplex (3.12), promove uma variação da função objetivo dual dada por (3.15). Portanto, se K k T N N ˆ 0− >d a x , ou seja, se o limite inferior da k-ésima restrição primal for violado, a direção dual simplex é uma direção de subida. A expressão (3.15) é valida, desde que Bλ em (3.13) não sofra mudança de sinal, pois caso contrário, o coeficiente da função objetivo dual é alterado. Se i iB B λ̂ e η têm sinais opostos, então iB λ pode trocar de sinal com o crescimento de δ. Portanto, temos dois casos a considerar: Caso (i) Se iB λ̂ 0< e iBη 0> , então impondo que: i i i i B B B B λ̂ λ̂ δη 0, segue que: δ η + ≤ ≤ − ; Caso (ii) Se iB λ̂ 0> e 0 iBη < , então impondo que: i i i i B B B B λ̂ λ̂ δη 0, segue que: δ η + ≥ ≤ − . Assim, para que não haja mudança de sinal em iB λ devemos ter: i i B i B λ̂ δ δ η ≤ = − , para todo i=1,…,n, tal que iB λ̂ e iBη tenham sinais opostos. Seja po um índice básico tal que: p0 i i 0 0 B B B p Bp Bi Bi ˆ ˆ ˆλ λ λ δ min tal que 0 i 1,..., η η η n   = − = − − ≥ =     . (3.16) Para 0P 0 δ δ≤ ≤ temos que: ( )K kN Nˆ ˆh( ) h( ) δ d y .= + −λ λ Quando 0Pδ δ= temos de (3.13) e (3.16) que p0-ésima restrição básica torna-se nula: P0Bλ 0= , o que sugere uma redefinição da partição básica, em que 0B λ p torna-se não básica e K 0N P λ δ 0= > torna-se básica. A Figura 2 ilustra a situação. 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 359 Figura 2 – Gráfico da função dual no intervalo [0, 0Pδ ]. Obviamente, como as variáveis duais são irrestritas de sinal, o crescimento de δ não precisa ser limitado por ˆh( )λ . Para valores de P0δ δ> , a expressão da função dual se altera, mas a direção dual pode ainda ser de subida. Isto sugere uma busca na direção η para a escolha de δ. Esta busca é linear por partes, devido à característica da função objetivo dual. Considere que: 0ˆh( ) h( ) δh= +λ λ , onde ( )K K0 N Nˆh d y .= − Se dermos um pequeno acréscimo ao valor de 0P δ , ou seja, 0P δ δ ε,= + onde ε>0 e pequeno, então P0B λ troca de sinal. (Observe que p 00B P λ 0 para δ δ= = ). Analisaremos somente o caso (i): P0B λ̂ 0< e iB η 0> , o outro caso ( P0B λ̂ 0> e iB η 0< ) segue de maneira análoga. Então, note que para P00 δ δ< < a variável P0Bλ 0< e que para 0Pδ δ> a variável P0B λ 0> . Substituindo 0P δ δ ε= + em (3.14) temos: 0 0 P P 1 ˆ (δ ε) ˆ( δ ) ε ε , = + + = + + = + λ λ η λ λ η η λ λ η em que 0 1 P ˆ δ .= +λ λ η Observe que K 0 iN p Nλ δ ε e λ 0 .i k= + = ≠ Assim, a função objetivo dual pode ser expressa por: i i i i i i i k 0 n m n B B N N i 1 i 1 n 1 B B B N p i 1 ˆ ˆh( ) h (λ ) h (λ ) h( ) h (λ εη ) d (δ ε). − = = = = + = + + + ∑ ∑ ∑ λ λ h KNKN ŷd − δ δP0 Não há troca de sinal em λB Sousa, Silva & Arenales – Métodos do tipo dual simplex para problemas de otimização linear canalizados 360 Pesquisa Operacional, v.25, n.3, p.349-382, Setembro a Dezembro de 2005 Suporemos por simplicidade que i 1 Bλ 0, 0i p≠ ≠ , ou seja, que o mínimo em (3.16) ocorre somente para o índice p0 e apenas a variável P0Bλ se anula quando 0pδ δ= . Lembrando que p P P0 0 0 1 B B P0 B ˆλ λ δ η 0= + = e ε > 0 e pequeno, temos que: i i i P P 0 K0 0 0 n 1 B B B B B p N i 1 i p ˆˆh( ) y (λ εη ) h (εη ) (δ ε)d . = ≠ = + + + +∑λ Como p0B η 0> , pois estamos analisando o caso (i), temos que p p p p0 0 0 0 B B B Bh (ε ) εd ηη = . Logo, i i 0 K i i P P k0 0 0 n n 1 B B p N B B B B N i 1 i 1 i p ˆh( ) y (λ ) δ d ε y η d η d = = ≠    = + + + +      ∑ ∑λ (3.17) As seguintes igualdades são asseguradas: 0 i i 0 i i i 0 i i i 0 Ki n m n 1 P B B P B N N P N i 1 i 1 n 1 1 B B P N i 1 ˆ ˆˆ) h( ) h( δ ) h (λ δ η ) h (λ δ η ) h( ) h (λ ) δ d ; I − = = = = + = + + + = + ∑ ∑ ∑ λ λ η λ i i i i P0 P P P0 0 0 i i i i P0 P0 0 n n B B B B B B B B i 1 i 1 n n B B B B B B i 1 i 1 i p ˆ ˆ ˆ ˆ) y η y η y η y η ˆ ˆy η y η e η ; II = = = = ≠ = + − = − ∑ ∑ ∑ ∑ ( )( ) ( )i i K K K n 1T T T T 1 T B B B B B N B N i 1 ˆ ˆ ˆ ˆ ˆ) y ηIII − − = = = − = − = −∑ y η y B a a B y a x . Portanto, a expressão (3.17) pode ser reescrita usando (I), (II) e (III): P P P0 0 0 1 0 B B Bh( ) h( ) ε(h (e d )η )= + − −λ λ , em que K K T 0 N Nˆh d .= − +a x As expressões descritas anteriormente para a função dual são válidas desde que 0ε > e suficientemente pequeno. Analisaremos agora, qual o maior valor para o incremento ε, ou seja, determinaremos o tamanho do passo de modo que i 0 iB p B λ̂ (δ ε)η+ + não mude de sinal. Note que iB λ̂ tem o mesmo sinal de i i0B p B λ̂ (δ ε)η+ + , 0i p≠ . Assim, os valores de ε que promovem mudança de sinal em iB λ são dados por: i 0 i i 0 i i B p B B i p B B ˆ ˆλ δ η λ ε δ 0 η η + = − = − − > , 0i p≠ . 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 363 Para -1 Bˆ ˆx = B y temos que: ( )K KN Nˆ ˆh( ) h( ) δ .= + −λ λ y e Quando 0Pδ δ= temos que a p0-ésima restrição básica torna-se nula, enquanto que kNλ = -δ 0≤ , o que sugere uma redefinição da partição básica. Como já observado no caso a), o valor de δ pode ser maior do que 0Pδ pois as variáveis duais não têm restrição de sinal. Para analisar a função dual para valores além de 0Pδ consideramos 0pδ δ ε, ε 0= + > e suficientemente pequeno. Logo a nova solução dual é dada por: 0 B B P NN ˆ (δ ε) ˆ     = − +        λ η λ ηλ . Analogamente ao caso a), obtemos a seguinte expressão para a função dual: 0 P P P K K0 0 0 T P 1 1 0 B B B 0 N N ˆ ˆh( ) h( δ ) εh , onde h h (e d )η e h e .= − + = − − = −λ λ η a x A busca unidimensional é realizada da mesma forma que foi feita para o caso (a). Escolhido os índices para as variáveis que entra e sai da base, atualizamos B e N e repetimos o processo. Esta busca foi considerada na implementação do algoritmo, para a qual fizemos algumas alterações, que serão apresentadas na seção 4. Embora Maros (2003) tenha desenvolvido o algoritmo dual simplex para problemas com variáveis canalizadas, baseada na característica da função dual (linear por partes), o autor não considera a canalização nas restrições como fizemos, explorando as particularidades deste caso. 3.4 Algoritmo dual simplex com busca linear por partes Resumimos o método dual simplex com busca unidimensional linear por partes exata especializado para problemas no formato geral dado por (3.1): Passo 0: INICIALIZAÇÃO Determine uma partição básica nas colunas de AT = (BT, NT). Calcule a solução dual: B N ˆ ˆ ˆ        λ λ = λ com T T -1 TB Nˆ ˆ= e 0=λ c B λ . Calcule a solução primal: 1 Bˆ ˆ −=x B y , com i i i i i B B B B B ˆd se 0 ˆ ˆe se 0.  ≥=  ≤ λ y λ IT = 0. Passo 1: OTIMALIDADE Escolha um índice k, 1 ≤ k ≤ m-n que fornece a maior violação, ou seja, Sousa, Silva & Arenales – Métodos do tipo dual simplex para problemas de otimização linear canalizados 364 Pesquisa Operacional, v.25, n.3, p.349-382, Setembro a Dezembro de 2005 caso a): K k T N N ˆd 0− >a x (limite inferior violado), K k T 0 N N ˆh d= −a x ou caso b): k K T N Nˆ e 0>a x - (limite superior violado), k K T 0 N Nˆh e= a x - Se não existe tal índice, isto é, N Nˆ≤ ≤ T Nd a x e , então pare (a solução atual é ótima obtida na iteração IT.) Passo 2: DIREÇÃO DUAL SIMPLEX Determine as componentes básicas da direção dual simplex: ( ) K 1T T B N − = −η B a . Passo 3: TAMANHO DO PASSO Passo 3.1: PONTOS DE NÃO-DIFERENCIAÇÃO Encontre δi por: Caso a): i i i i B B i B B ˆ ˆλ λ δ tal que 0 , 1,..., η η i n   = − − ≥ =     ou Caso b): i i i i B B i B B ˆ ˆλ λ δ tal que 0 , 1,..., η η i n   = ≥ =     (suponha que são r valores de iδ ). Se r=0 então pare (ou seja, não existe nenhum delta, o dual não tem solução ótima finita e, portanto, o primal é infactível.) Senão Passo 3.2: BUSCA UNIDIMENSIONAL Ordene o vetor de δi de forma a obter: 0 1δ δ ... δ rp p p≤ ≤ ≤ . Determine r≤ tal que: h > 0 e 1h + ≤ 0, em que h0 > 0 é dado no passo 1. P P Bp+1 B B h = h -(e -d ) η . faça pδ δ= . Se hr+1 > 0 então pare ( ˆh( δ )η+ → ∞λ , isto é, o problema dual não tem solução ótima, logo o primal é infactível.) 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 365 Passo 4: ATUALIZAÇÃO Troque o p -ésimo índice básico pelo k-ésimo índice não básico e atualize as soluções primal e dual p kB N↔ . IT ← IT+1, repita o passo 1. Observe que o passo 1 do algoritmo, caso a otimalidade não seja encontrada, determina a variável que entra na base ( kN λ ) e o passo 3.2, determina a variável que sai da base ( Bλ p ), caso o problema primal não seja infactível. Note que quando se fixa 1= , o método não faz a busca unidimensional e, assim temos o método dual simplex padrão ou usual, que iremos denotar por SB. A este procedimento de busca unidimensional exata, definido no passo 3.2, denominamos busca completa com ordenação preliminar (BC_1). 4. Algumas Extensões da Busca Unidimensional Os métodos de busca para resolução de problemas de otimização, por exemplo, Maximizar Φ( ) Ω,∈ x x têm dois passos fundamentais: a partir de uma solução ˆ Ω∈x i) determinação da direção de busca em x̂ : d (normalmente direção de subida em x̂ ) e, ii) determinação do tamanho do passo: δ̂ tal que ˆˆ ˆΦ( δ ) Φ( )+ >x d x . Para a determinação do tamanho do passo, muitas vezes é colocado o sub-problema: ˆMaximizar (δ) ( δ ), δ 0.ϕ = Φ + ≥x d Entretanto, o esforço computacional para a resolução deste sub-problema pode ser grande e desnecessário, pois a direção de busca d é importante na solução x̂ e pode ser equivocada longe de x̂ , sugerindo que uma nova direção de busca seja determinada. Embora o sub- problema para a função dual linear por partes seja de fácil resolução (passo 3.2 do algoritmo dual simplex com busca unidimensional exata), resta ainda saber se uma busca inexata (i.e., o abandono da direção de busca antes que sub-problema seja resolvido) pode ser efetiva. Investigamos três procedimentos de busca. O primeiro é busca inexata, que é baseado na estrutura linear por partes da função objetivo, somente uma parcela dos pontos de não- diferenciação são examinados, o segundo é um procedimento de busca exata, avaliando os valores de hi para cada iδ e o último, busca inexata, adaptamos a clássica regra de Armijo, a qual apresenta um teste para evitar passos ‘muito grandes’. 4.1 Primeira modificação no procedimento de busca – Busca Parcial (BP) Este procedimento é feito realizando uma alteração muito simples no passo 3.2, que faz a ordenação do deltas, no algoritmo da secção 3.4. Neste caso escolheremos uma fração dos deltas ordenados, digamos αn, onde α é um parâmetro ajustável. Assim, determinamos o Sousa, Silva & Arenales – Métodos do tipo dual simplex para problemas de otimização linear canalizados 368 Pesquisa Operacional, v.25, n.3, p.349-382, Setembro a Dezembro de 2005 5. Experimentos Computacionais e Conclusões Daremos a seguir os resultados computacionais obtidos com o método dual simplex linear por partes com as modificações propostas na seção anterior e para o método dual simplex padrão, quando algumas comparações são realizadas para 3 tipos de estrutura na matriz A: densa, escada com 4 blocos e escada com 20 blocos. O algoritmo dual simplex linear por partes (seção 3.4) foi implementado utilizando a forma produto da inversa para resolver problemas no formato (3.1). Para cada tamanho (dimensão) do problema, que define um exemplar com m’ restrições e n variáveis (veja Figura 7), foram resolvidos 20 exemplares com os dados gerados uniformemente aleatórios nos seguintes intervalos: cj∈[-6, 0], aij∈[-1, 5] (para gerar exemplares factíveis, uma solução factível é gerada: ˆ jx ∈[0, 10]), di = 1 ˆ n ij j ij a x σ= −∑ , ei = 1 ˆ n ij j ij a x σ= +∑ , com σi∈[0 8]. Em média, 10% dos valores de σi foram gerados nulos, de modo que di=ei, isto é, restrições de igualdade (outros parâmetros foram utilizados sem que alterassem as conclusões). Os testes foram realizados em um Notebook Toshiba Satellite Celeron 650 MHz com 312 Mbytes de RAM. A linguagem C de programação foi utilizada, versão 5.01, com estrutura de dados alocada estaticamente. O tempo (em segundos) e o número de iterações, reportados a seguir, são as médias dos resultados da resolução dos 20 exemplares para cada tamanho do problema. Para a apresentação dos resultados, considere que BC_1 representa o método dual simplex com busca exata (completa) com ordenação preliminar, SB o método dual simplex padrão (usual), BP método dual simplex com busca inexata (parcial), BC_2 o método dual simplex com busca exata com ordenação em processo, AR o método dual simplex com a regra de Armijo (busca inexata) e m-n representa o número de restrições e n o número de variáveis. Para a regra de Armijo, utilizamos ε=0.2 (veja seção 4.3) que é um valor usual. Testamos outros valores, mas o desempenho foi pior. Lembre-se que os valores de δ devem ser ordenados, em ordem crescente, e indicam os pontos de não-diferenciabilidade de ˆh( δ )+λ η . A primeira questão que surge, é sobre a grandeza de r (comparada com n), pois isto pode levar a ordenações de vetores de dimensões elevadas para problemas de grande porte. Como a grandeza de r é influenciada pela esparsidade da matriz de restrições? Uma outra questão é sobre a grandeza de (comparada com r). Será necessário ordenar todo o vetor de pontos de não diferenciação? E, por último, compensa a busca unidimensional exata? Isto é, após um avanço na direção dual simplex, não seria melhor mudar de direção? Para responder estas questões, apresentamos os resultados. 5.1 Problemas densos Nesta seção apresentamos os resultados obtidos para problemas com quase 100% dos elementos das (m-n) restrições diferentes de zero. A Tabela 5.1 apresenta os resultados para o método dual simplex linear por partes com busca completa (BC_1) e método dual simplex padrão (SB). 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 369 Tabela 5.1 – Busca Completa_1 × Sem Busca – Problemas Densos. Iterações Tempo Exemplar (m-n)×n BC_1 SB BC_1 SB 1 100×100 133.2 419.3 0.08 0.22 2 200×100 205.0 653.7 0.19 0.52 3 300×100 235.5 785.8 0.32 1.01 4 200×200 301.3 914.7 1.08 3.02 5 300×200 389.6 1200.6 1.72 5.04 6 20×400 63.5 432.7 0.59 3.65 7 100×200 175.0 642.7 0.50 1.67 8 100×400 241.1 1150.3 2.40 10.03 9 200×400 401.2 1618.1 4.41 17.86 10 400×200 475.2 1481.4 2.49 7.71 11 400×400 622.8 1980.1 8.30 25.97 Média 294.8 1025.4 2.00 6.97 Da Tabela 5.1, observamos que a busca unidimensional completa faz reduzir consideravelmente o número de iterações com relação ao método dual simplex usual, em torno de 3.5. Observe que o tempo por iteração em média foi praticamente o mesmo para os dois métodos. No exemplar 6, em que o número de variáveis é muito maior do que o número de restrições, observamos a maior diferença no número de iterações. Portanto, testamos mais 4 exemplares com esta característica. Os resultados estão na Tabela 5.2. Tabela 5.2 – Busca Completa_1 × Sem Busca – Problemas Densos. Iterações Tempo Exemplar (m-n)×n BC_1 SB BC_1 SB 12 10×400 35.2 300.8 0.30 1.98 6 20×400 63.5 432.7 0.54 3.05 13 30×400 89.3 567.1 0.78 4.10 14 40×400 109.1 661.8 0.96 4.95 15 50×400 132.0 790.8 1.18 6.08 Média 85.8 550.6 0.75 4.03 Notamos da Tabela 5.2, que a maior diferença foi para o exemplar 12, em que o número de variáveis é 40 vezes o número de restrições. Esta diferença no número de iterações diminui à medida que o número de restrições aumenta. Apresentamos agora na Tabela 5.3 os resultados obtidos para o método com a busca unidimensional inexata (regra de Armijo – AR) descrito na seção 4.3, comparando com BC_1. Sousa, Silva & Arenales – Métodos do tipo dual simplex para problemas de otimização linear canalizados 370 Pesquisa Operacional, v.25, n.3, p.349-382, Setembro a Dezembro de 2005 Tabela 5.3 – Busca Completa_1 × Regra de Armijo – Problemas Densos. Iterações Tempo Exemplar (m-n)×n BC_1 AR BC_1 AR 1 100×100 133.2 171.2 0.08 0.09 2 200×100 205.0 285.3 0.19 0.25 3 300×100 235.5 341.2 0.32 0.44 4 200×200 301.3 494.9 1.08 1.64 5 300×200 389.6 751.4 1.72 3.13 6 20×400 63.5 107.6 0.59 0.85 7 100×200 175.0 225.8 0.50 0.57 8 100×400 241.1 342.3 2.40 3.09 9 200×400 401.2 562.0 4.41 5.85 10 400×200 475.2 924.5 2.49 4.72 11 400×400 622.8 1351.6 8.30 13.2 Média 294.8 505.2 2.00 3.07 Notamos que a clássica regra de Armijo foi muito inferior a busca completa, fazendo em média 70% mais iterações e gastando aproximadamente 53% mais tempo. No entanto a regra de Armijo apresenta desempenho melhor em relação ao método dual simplex padrão (veja Tabela 5.1), reduzindo, em média, o número de iterações pela metade. No método dual simplex com busca linear por partes, calculados os deltas, estes precisam ser ordenados. Este procedimento de ordenação pode consumir muito tempo, assim relatamos o tempo de ordenação para o método BC_1, apresentados na Tabela 5.4, em que TT indica o tempo de resolução e TO o tempo de ordenação para todas as iterações. Tabela 5.4 – Tempo Total × Tempo de Ordenação. Tempo Exemplar (m-n)×n TT TO 1 100×100 0.08 0.00 2 200×100 0.19 0.01 3 300×100 0.32 0.01 4 200×200 1.08 0.06 5 300×200 1.72 0.09 6 20×400 0.59 0.06 7 100×200 0.50 0.05 8 100×400 2.40 0.20 9 200×400 4.41 0.33 10 400×200 2.49 0.14 11 400×400 8.30 0.23 Média 2.00 0.10 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 373 Da Tabela 5.7, observamos para estes problemas densos, uma suave melhora no tempo computacional, para BC_2 em relação a BC_1, em que conseguimos uma redução no tempo (em média) em torno de 5%. Note que não apresentamos o número de iterações para BC_1, que é o mesmo para BC_2, pois ambas são buscas exatas. Lembre-se que o que muda da busca completa 1 para a busca completa 2, é o método de ordenação. No 2º caso é o método ‘bolha’ que parece ser melhor, pois é bem menor que r e não precisa ordenar todo o vetor. A seguir, a Figura 6 apresenta o desempenho computacional (tempo) dos quatro procedimentos de busca e do método dual simplex padrão, para os 11 exemplares de problemas densos que trabalhamos. 0 5 10 15 20 25 30 1 2 3 4 5 6 7 8 9 10 11 Exemplar Te m po SB AR BC_1 BP BC_2 Figura 6 – Tempo de Resolução – Problemas Densos. Observando a Figura 6, podemos dizer que de um modo geral, a busca completa com ordenação em processo (BC_2) foi um pouco melhor que a busca parcial (BP), que a busca completa com ordenação preliminar (BC_1) e principalmente, que a busca com a regra de Armijo (AR), ou seja, o tempo computacional foi favorável ao método dual simplex com busca linear por partes, utilizando o segundo procedimento de ordenação. E fica evidente a superioridade de se introduzir algum tipo de busca, pois o método dual simplex usual foi extremamente inferior em relação ao outros. 5.2 Problemas esparsos Nesta seção apresentamos os resultados obtidos para uma classe esparsa de problemas, para os quais a matriz de restrição é da forma escada. (Figura 7). Os coeficientes não nulos da matriz A estão confinados nos blocos (Figura 7 ilustra 4 blocos) e foram gerados conforme descrito na seção anterior, assim como os demais dados do problema. Sousa, Silva & Arenales – Métodos do tipo dual simplex para problemas de otimização linear canalizados 374 Pesquisa Operacional, v.25, n.3, p.349-382, Setembro a Dezembro de 2005                                 =A Figura 7 – Matriz A com 4 blocos. Nas Tabelas 5.8 e 5.10 estão os resultados obtidos para o método dual simplex com busca completa com ordenação preliminar (BC_1) e para o método dual simplex usual (SB) e nas Tabelas 5.9 e 5.11 estão os resultados para BC_1 e para a regra de Armijo (AR), com a matriz de restrições tendo 4 blocos e 20 blocos, respectivamente. O símbolo %NZ indica a porcentagem de elementos diferente de zero na matriz de restrições definida pelos blocos e CC indica o número de colunas em comum para cada 2 blocos, aproximadamente 20%. Tabela 5.8 – Busca Completa_1 × Sem Busca – Problemas Esparsos 4 Blocos. Iterações Tempo Exemplar CC %NZ (m-n)×n BC_1 SB BC_1 SB 1 5 28 100×101 128.9 374.2 0.09 0.19 2 5 28 200×101 209.5 615.1 0.21 0.54 3 5 28 300×101 259.6 793.1 0.37 1.06 4 11 29 200×203 343.2 1295.0 1.35 4.55 5 11 29 300×203 428.4 1747.6 2.06 7.71 6 23 29 20×403 20.2 101.8 0.21 0.93 7 11 29 100×203 93.2 248.7 0.41 0.96 8 23 29 100×403 95.6 335.7 1.27 4.72 9 23 29 200×403 221.6 666.8 5.53 18.44 10 11 29 400×203 522.8 2180.2 3.03 12.09 11 23 29 400×403 908.3 4284.8 15.56 65.66 Média 293.7 1149.3 2.73 10.60 0 0 I m’ n restrições variáveis m = m’+n 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 375 Podemos observar da Tabela 5.8, que na média o método dual simplex usual realizou 3.91 mais iterações do que o método dual simplex com a busca unidimensional completa e gastando 3.88 mais tempo. Note que a maior diferença para este caso, é observada para o exemplar 6, em que o número de variáveis é muito maior do que o número de restrições. Ou seja, mesmo para esta classe de problemas esparsos a busca unidimensional, faz uma diferença muito grande, apresentando um desempenho ainda melhor do que em problemas densos (veja Tabela 5.1). Observa-se com relação ao caso denso (veja Tabela 5.1), para os dois métodos, que se (m-n) > n, então o número de iterações cresce, caso contrário, decresce. Isto talvez seja explicado, pois podem ocorrer várias restrições redundantes para o caso denso, o que não deve acontecer para a estrutura escada. Note também nas Tabelas 5.1 e 5.7, como o número de restrições (m-n) tem maior impacto no número de iterações. Veja, por exemplo, os exemplares 9 e 10 da Tabela 5.1 (200×400 e 400×200, respectivamente). Entretanto, o tempo computacional é bem menor para o exemplar 10, pois as matrizes básicas são da ordem de 200×200 enquanto para o exemplar 9 as matrizes básicas são da ordem 400×400 (obviamente, essas matrizes 400×400 têm uma estrutura particular que poderia ser explorada). Na Tabela 5.9 estão os resultados para a busca completa (BC_1) e para a regra de Armijo (AR). Tabela 5.9 – Busca Completa_1 × Regra de Armijo – Problemas Esparsos 4 Blocos. Iterações Tempo Exemplar CC %NZ (m-n)×n BC_1 AR BC_1 AR 1 5 28 100×101 128.9 173.7 0.09 0.11 2 5 28 200×101 209.5 269.9 0.21 0.24 3 5 28 300×101 259.6 360.7 0.37 0.49 4 11 29 200×203 343.2 504.2 1.35 1.95 5 11 29 300×203 428.4 709.9 2.06 3.37 6 23 29 20×403 20.2 27.4 0.21 0.24 7 11 29 100×203 93.2 103.4 0.41 0.46 8 23 29 100×403 95.6 117.8 1.27 1.50 9 23 29 200×403 221.6 278.1 5.53 7.06 10 11 29 400×203 522.8 910.3 3.03 5.20 11 23 29 400×403 908.3 1639.5 15.56 25.59 Média 293.7 463.1 2.73 4.20 Observamos que a busca completa (BC_1) foi ainda muito superior à regra de Armijo, apesar da diferença ter diminuído em relação ao caso denso (veja Tabela 5.3). A busca fez em média 35% menos iterações do que a regra de Armijo. A Tabela 5.10 apresenta os resultados para a matriz de restrições tendo agora 20 blocos (problemas mais esparsos). Sousa, Silva & Arenales – Métodos do tipo dual simplex para problemas de otimização linear canalizados 378 Pesquisa Operacional, v.25, n.3, p.349-382, Setembro a Dezembro de 2005 O mesmo pode ser observado da Tabela 5.13 para o caso anterior (veja Tabela 5.12). Ou seja, para os dois casos esparsos (matrizes com 4 e 20 blocos) o tempo de ordenação foi insignificante em relação ao tempo total. Agora, nas Tabelas 5.14 e 5.15 são apresentados os resultados da busca completa com ordenação preliminar (BC_1) para as razões: r/n e /r, para os casos de 4 e 20 blocos da matriz de restrições, respectivamente. Tabela 5.14 – Número de Deltas e Número de Buscas – 4 blocos. Exemplar CC %NZ (m-n)×n r/n /r 1 5 28 100×101 0.51 0.22 2 5 28 200×101 0.49 0.27 3 5 28 300×101 0.54 0.22 4 11 29 200×203 0.49 0.22 5 11 29 300×203 0.50 0.24 6 23 29 20×403 0.13 0.62 7 11 29 100×203 0.17 0.65 8 23 29 100×403 0.17 0.53 9 23 29 200×403 0.17 0.53 10 11 29 400×203 0.49 0.98 11 23 29 400×403 0.50 0.98 Média 0.37 0.49 Observarmos da Tabela 5.14, que o número de deltas (r) diminuiu em relação ao caso denso (veja Tabela 5.5) e os testes indicam que esta fração tende a diminuir gradativamente. Para o caso em que o número de variáveis é maior do que o número de restrições, notamos que o número de deltas diminuiu significantemente. Observamos ainda que, para os exemplares maiores 10 e 11 a razão /r (observada somente para a primeira iteração) foi muito alta, ou seja, o número de buscas cresceu em relação ao caso denso. Tabela 5.15 – Número de Deltas e Número de Buscas – 20 blocos. Exemplar CC %NZ (m-n)×n r/n /r 1 1 5 100×101 0.06 0.33 2 1 5 200×101 0.49 0.43 3 1 5 300×101 0.50 0.46 4 2 5 200×202 0.05 0.20 5 2 5 300×202 0.46 0.43 6 5 6 20×405 0.03 0.30 7 2 5 100×202 0.03 0.33 8 5 6 100×405 0.04 0.25 9 5 6 200×405 0.04 0.25 10 2 5 400×202 0.50 0.86 11 5 5 400×405 0.06 0.11 Média 0.20 0.35 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 379 Da Tabela 5.15, notamos que o número de deltas diminuiu em relação ao caso de 4 blocos (Tabela 5.14), o que era de se esperar, pois este caso é muito mais esparso. Observa-se ainda que o número de deltas foi próximo de 50% do valor de n somente para os casos em que o número de restrições é maior do que o número de variáveis. Em relação à fração /r, observamos que foi muito pequena para os exemplares 6, 8 e 9, tendo em vista que o número de deltas foi muito pequeno. Em relação ao caso denso, temos que o número de deltas (i.e., r) diminuiu assim como a fração que determina a quantidade de deltas utilizados na busca (i.e., ). Diante destes resultados (Tabelas 5.14 e 5.15), utilizamos apenas a segunda modificação (veja Seção 4) na busca unidimensional para o caso de 4 e 20 blocos da matriz de restrições, já que o número de deltas foi pequeno. Os resultados são apresentados nas Tabelas 5.16 e 5.17. Tabela 5.16 – Busca Completa_1 × Busca Completa_2 – Problemas Esparsos 4 Blocos. Tempo Exemplar CC %NZ (m-n)×n BC_1 BC_2 1 5 28 100×101 0.09 0.08 2 5 28 200×101 0.21 0.19 3 5 28 300×101 0.37 0.35 4 11 29 200×203 1.34 1.25 5 11 29 300×203 2.13 2.02 6 23 29 20×403 0.21 0.22 7 11 29 100×203 0.42 0.41 8 23 29 100×403 1.30 1.30 9 23 29 200×403 5.58 5.59 10 11 29 400×203 3.07 2.96 11 23 29 400×403 15.05 14.44 Média 2.70 2.61 Neste caso o método dual simplex (BC_2) foi ligeiramente melhor do que o método dual simplex (BC_1). Note que a maior diferença é observada para o exemplar 11. Logo, é de se esperar que o procedimento (BC_2) tenha um desempenho mais promissor para problemas de grande porte. Notamos da Tabela 5.17 que na média houve um empate para os dois procedimentos de busca exata. Com uma ligeira vantagem para BC_2 na maioria dos exemplares, mas nada significante. Contudo, podemos observar que o procedimento BC_2 teve um bom desempenho para problemas densos e para problemas com a matriz A tendo 4 Blocos, no entanto esta vantagem não foi verificada para o caso mais esparso, ou seja, a matriz A com 20 blocos e com densidade em torno de 6%. Sousa, Silva & Arenales – Métodos do tipo dual simplex para problemas de otimização linear canalizados 380 Pesquisa Operacional, v.25, n.3, p.349-382, Setembro a Dezembro de 2005 Tabela 5.17 – Busca Completa_1 × Busca Completa_2 – Problemas Esparsos 20 Blocos. Tempo Exemplar CC %NZ (m-n)×n BC_1 BC_2 1 1 5 100×101 0.06 0.05 2 1 5 200×101 0.22 0.20 3 1 5 300×101 0.43 0.40 4 2 5 200×202 1.51 1.50 5 2 5 300×202 2.36 2.30 6 5 6 20×405 0.03 0.03 7 2 5 100×202 0.06 0.06 8 5 6 100×405 0.20 0.22 9 5 6 200×405 0.58 0.59 10 2 5 400×202 3.45 3.36 11 5 5 400×405 13.67 13.93 Média 2.05 2.05 Destacamos aqui, que há grandes possibilidades de tornar o método dual simplex linear por partes mais eficiente em termos do tempo computacional para problemas de grande porte, investindo-se na eficiência da resolução dos sistemas básicos utilizando a decomposição LU (Bartels & Goloub, 1969) com heurística de Markowitz (1957) e atualização da base (Reid, 1982), procedimentos muito utilizados na prática para resolução de problemas de grande porte e esparsos. O trabalho de Silva (2002) aborda detalhadamente estas técnicas. 6. Conclusões Neste artigo foi estudada a classe de problemas de otimização linear com restrições canalizadas (formato geral) sob a ótica da dualidade. O problema dual, embora possa ser linearizado, tem a função objetivo linear por partes. Métodos do tipo simplex (i.e., baseados na clássica estratégia simplex) foram desenvolvidos explorando a não-linearidade da função dual e chamados métodos tipo dual simplex linear por partes. Como nos métodos da otimização não-linear, surgiu a questão da busca unidimensional a ser feita na direção dual simplex. Experimentos computacionais revelam a importância da busca unidimensional, podendo reduzir o esforço computacional a 25% do critério usual de troca de bases do algoritmo dual simplex. A simplicidade da busca unidimensional faz também com que a busca exata apresente melhor desempenho do que buscas inexatas, como por exemplo, a regra de Armijo. O método dual simplex linear por partes com busca exata (o qual se mostrou mais eficiente) foi comparado com o pacote CPLEX 4.0 e CPLEX 7.5 (Sousa, 2000 e Silva, 2002). O número de iterações, quando comparado com o CPLEX 4.0, era da ordem de 46% menor. Entretanto, quando comparado com o CPLEX 7.5, os desempenhos em termos do número de iterações se equivalem. Sobre a importância de técnicas de ordenação mais elaboradas (ordenação de vetores surge na busca unidimensional), os experimentos computacionais revelam que é baixo o impacto