Tiago Tiburcio da Silva Um estudo sobre limites duais para o problema integrado de dimensionamento de lotes e sequenciamento da produção Dissertação de Mestrado Pós-Graduação em Matemática Instituto de Biociências, Letras e Ciências Exatas Rua Cristóvão Colombo, 2265, 15054-000 São José do Rio Preto - SP - Brasil Telefone: (17) 3221-2444 - Fax: (17) 3221-2445 Silva, Tiago Tiburcio da. Um estudo sobre limites duais para o problema integrado de dimensionamento de lotes e sequenciamento da produção / Tiago Tiburcio da Silva. -- São José do Rio Preto, 2015 119 f. : il., tabs. Orientador: Maria do Socorro Nogueira Rangel Dissertação (mestrado) – Universidade Estadual Paulista “Júlio de Mesquita Filho”, Instituto de Biociências, Letras e Ciências Exatas 1. Matemática. 2. Otimização matemática. 3. Métodos de relaxação (Matemática) 4. Problema de dimensionamento de lotes. 5. Algoritmos. I. Rangel, Maria do Socorro Nogueira. II. Universidade Estadual Paulista "Júlio de Mesquita Filho". Instituto de Biociências, Letras e Ciências Exatas. III. Título. CDU – 518.734 Ficha catalográfica elaborada pela Biblioteca do IBILCE UNESP - Câmpus de São José do Rio Preto Tiago Tiburcio da Silva Um estudo sobre limites duais para o problema integrado de dimensionamento de lotes e sequenciamento da produção Orientador: Profa. Dra. Maria do Socorro Nogueira Rangel Universidade Estadual Paulista ”Júlio de Mesquita Filho” Instituto de Biociências, Letras e Ciências Exatas Campus de São José do Rio Preto São José do Rio Preto 13 de agosto de 2015 Tiago Tiburcio da Silva Um estudo sobre limites duais para o problema integrado de dimensionamento de lotes e sequenciamento da produção Dissertação apresentada para obtenção do t́ıtulo de Mestre em Matemática, área de Análise Aplicada, junto ao Instituto de Biociências, Letras e Ciências Exatas da Universidade Estadual Paulista “Júlio de Mesquita Filho”, Campus de São José do Rio Preto. Banca Examinadora Profa. Dra. Maria do Socorro Nogueira Rangel Professor Doutor UNESP - São José do Rio Preto Orientador Prof. Dr. Silvio Alexandre de Araújo Professor Doutor UNESP - São José do Rio Preto Profa. Dra. Deisemara Ferreira Professor Doutor UFSCar - Sorocaba São José do Rio Preto, 13 de agosto de 2015. Aos meus amados pais, Abigail e Valdecir. À minha noiva Aline e amigos. Dedico. Agradecimentos A Deus, por sua infinita bondade e misericórida que tem tido comigo, e pelo rico dom da vida. A minha orientadora Socorro a quem eu devo meu ingresso no mundo acadêmico. Obrigado pelas conversas com quem tive o prazer de desfrutar, me esclarecendo questões sobre o meu trabalho, por me lembrar do frescor que é preciso ter na pesquisa acadêmica e na vida, e por seus preciosos conselhos pessoais. Tenho muito orgulhoso em ser seu orientando. Quando a procurei, no ińıcio da minha caminhada, tinha apenas uma intuição. Hoje tenho imensa admiração. Muito obrigado! Aos meus pais Abigail e Valdecir, e minha irmã Juliana por terem me ensinado que tudo é posśıvel. Não pouparam esforços para me ajudar, sempre ao meu lado, me apoiando, me incentivando, vibrando com minhas conquistas. Devo tudo à vocês. Sou grato a Deus por ter essa famı́lia linda e unida. A toda a minha famı́lia pelo incentivo e carinho ao longo de todos esses anos. A minha noiva Aline, por estar todo o tempo ao meu lado, incondicionalmente. Nos mo- mentos mais dif́ıceis, que não foram raros, sempre me fazendo acreditar que chegaria ao fim desta dif́ıcil, mas gratificante etapa. Sou grato por cada gesto carinhoso, cada sorriso, e ansioso por estar ao seu lado o resto da minha vida. Te Amo! Aos meus amigos desde a graduação Leonardo, Lidia, Cinthia, Mariana, Rafaella, Ana Maria, Luiz Fernando, em especial o Rafael. Por compartilharmos os sufocos das provas, trabalhos, aulas, mas por todos os momentos de alegria, felicidades e viagens que fizemos juntos. Aos amigos Well, Tavin. Muito obrigado! As companheiras da salinha da pós-graduação e grandes amigas Gislaine, Michelli, por todos os momentos de alegria, pelos conselhos e ajuda. Ao irmão que Deus me deu, Simão Pedro, por muitas e muitas vezes puxar minha orelha, me aconselhar na vida, por acreditar em mim, com seu jeito todo espivitado, e por todos os momentos de diversão e alegria que partilhamos. A todos os professores, colegas, pessoas e funcionários do IBILCE, em especial ao Getúlio e Thiago. Ao CNPq, pela credibilidade e apoio financeiro a este projeto. E finalmente a todos que contribúıram direta ou indiretamente na realização deste trabalho. Sintam-se todos agradecidos. i “Posso todas as coisas naquele que me fortalece” Filipenses 4.13 Resumo A Matemática está presente no nosso dia-a-dia seja pra dizer as horas, contar dinheiro, prever o tempo. Sob o aspecto empresarial ela também se faz presente na hora de tomar decisões, por exemplo. Muitas empresas de manufatura lidam com decisões diariamente no setor de produção, dimensionando lotes e sequenciando sua produção. Entretanto, o mais comum é to- mar essas decisões de forma independente, sendo que poderiam ser tomadas simultaneamente, pois agregariam melhores resultados. Neste trabalho integramos essas decisões utilizando um modelo matemático que agrega ao problema de dimensionamento de lotes, o sequenciamento da produção modelando a exclusão de subsequências através das restriçoes do tipo MTZ e MCF. Também estudamos essas duas formulações considerando a variável de preparo explicitamente e implicitamente resultando em quatro formulações matemáticas diferentes para o problema integrado de dimensionamento de lotes e sequenciamento da produção. Concluimos que a formulação MCF com variável de preparo expĺıcita é mais forte que as outras formulações estu- dadas e que as soluções das instâncias das formulações baseadas nas restrições do tipo MTZ são bastante influenciadas pelos planos de cortes e pré-processamento inclusos no solver CPLEX. Nosso objetivo é derivar limitantes primais e duais para o problema integrado de dimensio- namento de lotes e sequenciamento da produção. Para a obtenção dos limitantes primais foi proposta uma heuŕıstica gulosa. Para obter os limites duais foram estudadas a relaxação La- grangeana e a relaxação Lagrangeana/Surrogate e os métodos usados para resolução dos duais associados foram o Algoritmo de Subgradiente e Algoritmo de Volume. O método que obteve melhor desempenho foi o dual Lagrangeano/Surrogate resolvido pelo Algoritmo de Subgradi- ente para a formulação com restrições do tipo MTZ e variável expĺıcita de preparo. Palavras-Chave: problema integrado de dimensionamento de lotes e sequenciamento da produção, relaxação Lagrangeana, relaxação Lagrangeana/Surrogate. 1 Abstract Mathematics is present in our daily routine to tell time, count money, predict the weather. Many manufacturing companies deal with daily decisions in the manufacturing sector, lot-sizing and sequencing their production. However, the most usual is to take these decisions considering two independent problems, and not simultaneously, as it adds better results. In this work we integrate these decisions through a mathematical model that adds to the problem of lot sizing, sequencing decisions using constraints of the type MTZ and MCF. We also study these two formulations, considering the set up decisions explicitly and implicitly resulting in four different mathematical formulations for the integrated problem. We conclude that the MCF formulation with the explicit set up variable is stronger than the other formulations studied and the soluti- ons of the instances of formulations based on constraints of MTZ type are strongly influenced by the cutting planes and pre-processing included in the solver CPLEX. We aimed to derive primal and dual bounds for the integrated problem of lot sizing and sequencing of production. To obtain the primal bound we proposed a greedy heuristic. The dual bounds were obtained studying the Lagrangean and the Lagrangean / Surrogate relaxation and the methods used to solve the dual associates were the subgradient algorithm and Volume algorithm. The method with better performance was the dual Lagrangian / Surrogate solved by subgradient Algorithm for formulation with constraints MTZ type and explicit set up variable. Keywords: lot-sizing and scheduling problems, Lagrangean relaxation, Lagrangean/Surrogate relaxation. 1 Sumário Introdução 7 1 O Problema PIDS 9 1.1 Descrição do problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2 Modelos matemáticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2 Limitantes primais e duais para PI 18 2.1 Limitantes primais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2 Limitantes duais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2.1 Planos de corte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2.2 Relaxação Lagrangeana . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.3 Relaxação Surrogate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.2.4 Relaxação Lagrangeana/Surrogate . . . . . . . . . . . . . . . . . . . . . . 34 3 Solução do problema dual Lagrangeano 36 3.1 Conceitos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.2 Algoritmo do Subgradiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.3 Algoritmo de Volume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4 Relaxações para o PIDS 54 4.1 Uma heuŕıstica gulosa para o PIDS . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.2 Relaxação Lagrangeana para o PIDS . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2.1 Algoritmo de Subgradiente para resolução do Dual Lagrangeano . . . . . 58 4.2.2 Algoritmo de Volume para resolução do Dual Lagrangeano . . . . . . . . 58 4.3 Relaxação Lagrangeana/Surrogate para o PIDS . . . . . . . . . . . . . . . . . . 61 4.3.1 Algoritmo de Subgradiente para resolução do Dual Lagrangeano/Surrogate 63 5 Estudo computacional 66 5.1 Geração das Instâncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.2 Comparação entre os modelos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.3 Comparação entre os limites duais . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5.4 Considerações finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 2 SUMÁRIO 3 6 Conclusões e perspectivas futuras 87 A Modelos para o PIDS 96 A.1 Modelo MTZ1S1M (ver descrição na seção 1.2) . . . . . . . . . . . . . . . . . . . 96 A.2 Modelo MTZ1S1MP (ver descrição na seção 1.2) . . . . . . . . . . . . . . . . . . 97 A.3 Modelo MCF1S1M (ver descrição na seção 1.2) . . . . . . . . . . . . . . . . . . 98 A.4 Modelo MCF1S1MP (ver descrição na seção 1.2) . . . . . . . . . . . . . . . . . . 99 B Gráficos - instâncias dados14− 0 100 C Gráficos - instâncias dados18− 0 104 D Gráficos - instâncias dados22− 0 108 Lista de Figuras 1.1 Plano de produção e sequenciamento. . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2 Dados de uma instância do problema PIDS. . . . . . . . . . . . . . . . . . . . . 16 1.3 Plano de produção e sequenciamento. . . . . . . . . . . . . . . . . . . . . . . . . 17 1.4 Estoque da produção. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1 Conjuntos fact́ıveis Q, conv(Q) e conv(V), e soluções do problema inteiro, do problema dual Lagrangeano e da relaxação linear. . . . . . . . . . . . . . . . . . 25 2.2 Gráficos das funções Z(π, xi), i = 1, 2, . . . , 8. . . . . . . . . . . . . . . . . . . . . 28 2.3 Interpretação geométrica da relaxação Lagrangeana [62]. . . . . . . . . . . . . . 32 2.4 Comportamento da função Lagrangeano/Surrogate em função de t [64]. . . . . . 35 3.1 f(x) = |x|. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.2 Os elementos y1 e y2 são subgradientes de f em x, isto é, para todo z tem-se que f(z) ≥ f(x) + 〈yi, z − x〉, i = 1, 2. . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.3 Gráfico de f(x) = |x1|+ 2|x2|. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.4 Pseudocódigo do Método de Descida. . . . . . . . . . . . . . . . . . . . . . . . . 42 3.5 Pseudocódigo do Algoritmo de Subgradiente . . . . . . . . . . . . . . . . . . . . 43 3.6 Um passo do método de feixes em que foi gerado um ponto xk+1 com valor de f menor de f(xk). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.7 Pseudocódigo do Método de Feixes. . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.8 Pseudocódigo do Algoritmo de Volume . . . . . . . . . . . . . . . . . . . . . . . 52 3.9 Algoritmo para a escolha de α . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.1 Pseudocódigo para a heuŕıstica gulosa . . . . . . . . . . . . . . . . . . . . . . . . 57 4.2 Pseudocódigo do Algoritmo de Subgradiente para a formulação MTZ1S1MP - Dual Lagrangeano. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.3 Pseudocódigo do Algoritmo de Volume para a formulação MTZ1S1MP - Dual Lagrangeano. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.4 Pseudocódigo do Algoritmo de Subgradiente para a formulação MTZ1S1MP - Dual Lagrangeano/Surrogate. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.5 Algoritmo de busca unidimensional para o dual Lagrangeano/Surrogate. . . . . . 65 4 LISTA DE FIGURAS 5 B.1 Evolução dos iterados do dual Lagrangeano resolvido pelo Método de Subgradi- entes - Dados14-0 - Modelo MTZ1S1MP. . . . . . . . . . . . . . . . . . . . . . . 100 B.2 Evolução dos iterados do dual Lagrangeano/Surrogate resolvido pelo Método de Subgradientes - Dados14-0 - Modelo MTZ1S1MP. . . . . . . . . . . . . . . . . . 101 B.3 Evolução dos iterados do dual Lagrangeano resolvido pelo Algoritmo de Volume - Dados14-0 - Modelo MTZ1S1MP. . . . . . . . . . . . . . . . . . . . . . . . . . 101 B.4 Evolução dos iterados do dual Lagrangeano resolvido pelo Método de Subgradi- entes - Dados14-0 - Modelo MCF1S1MP. . . . . . . . . . . . . . . . . . . . . . . 102 B.5 Evolução dos iterados do dual Lagrangeano/Surrogate resolvido pelo Método de Subgradientes - Dados14-0 - Modelo MCF1S1MP. . . . . . . . . . . . . . . . . . 102 B.6 Evolução dos iterados do dual Lagrangeano resolvido pelo Algoritmo de Volume - Dados14-0 - Modelo MCF1S1MP. . . . . . . . . . . . . . . . . . . . . . . . . . 103 C.1 Evolução dos iterados do dual Lagrangeano resolvido pelo Método de Subgradi- entes - Dados18-0 - Modelo MTZ1S1MP. . . . . . . . . . . . . . . . . . . . . . . 104 C.2 Evolução dos iterados do dual Lagrangeano/Surrogate resolvido pelo Método de Subgradientes - Dados18-0 - Modelo MTZ1S1MP. . . . . . . . . . . . . . . . . . 105 C.3 Evolução dos iterados do dual Lagrangeano resolvido pelo Algoritmo de Volume - Dados18-0 - Modelo MTZ1S1MP. . . . . . . . . . . . . . . . . . . . . . . . . . 105 C.4 Evolução dos iterados do dual Lagrangeano resolvido pelo Método de Subgradi- entes - Dados18-0 - Modelo MCF1S1MP. . . . . . . . . . . . . . . . . . . . . . . 106 C.5 Evolução dos iterados do dual Lagrangeano/Surrogate resolvido pelo Método de Subgradientes - Dados18-0 - Modelo MCF1S1MP. . . . . . . . . . . . . . . . . . 106 C.6 Evolução dos iterados do dual Lagrangeano resolvido pelo Algoritmo de Volume - Dados18-0 - Modelo MCF1S1MP. . . . . . . . . . . . . . . . . . . . . . . . . . 107 D.1 Evolução dos iterados do dual Lagrangeano resolvido pelo Método de Subgradi- entes - Dados22-0 - Modelo MTZ1S1MP. . . . . . . . . . . . . . . . . . . . . . . 108 D.2 Evolução dos iterados do dual Lagrangeano/Surrogate resolvido pelo Método de Subgradientes - Dados22-0 - Modelo MTZ1S1MP. . . . . . . . . . . . . . . . . . 109 D.3 Evolução dos iterados do dual Lagrangeano resolvido pelo Algoritmo de Volume - Dados22-0 - Modelo MTZ1S1MP. . . . . . . . . . . . . . . . . . . . . . . . . . 109 D.4 Evolução dos iterados do dual Lagrangeano resolvido pelo Método de Subgradi- entes - Dados22-0 - Modelo MCF1S1MP. . . . . . . . . . . . . . . . . . . . . . . 110 D.5 Evolução dos iterados do dual Lagrangeano/Surrogate resolvido pelo Método de Subgradientes - Dados22-0 - Modelo MCF1S1MP. . . . . . . . . . . . . . . . . . 110 D.6 Evolução dos iterados do dual Lagrangeano resolvido pelo Algoritmo de Volume - Dados22-0 - Modelo MCF1S1MP. . . . . . . . . . . . . . . . . . . . . . . . . . 111 Lista de Tabelas 5.1 Parâmetros usados na geração das instâncias. . . . . . . . . . . . . . . . . . . . 67 5.2 Classes de instâncias [56]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.3 Resultados para as formulações MTZ1S1M e MTZ1S1MP (estratégia CPLEX). . 69 5.4 Planos de cortes gerados para instâncias dos modelos MTZ1S1M e MTZ1S1MP, aqui renomeadas por M1 e M2, respectivamente. . . . . . . . . . . . . . . . . . . 71 5.5 Limitante superior obtido antes da ramificação da árvore - Modelo MTZ1S1MP. 72 5.6 Resultados para as formulações MCF1S1M e MCF1S1MP (estratégia CPLEX). . 74 5.7 Planos de cortes gerados para instâncias dos modelos MCF1S1M e MCF1S1MP, aqui renomeadas por MCF e MCFP, respectivamente. . . . . . . . . . . . . . . . 75 5.8 Limitante superior obtido no nó raiz antes da ramificação da árvore - Modelo MCF1S1MP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.9 Limitantes superiores obtidos do CPLEX (Branch-and-bound - 3.600 segundos). 77 5.10 Comparações entre os Métodos - Modelo MTZ1S1MP - 600 segundos. . . . . . . 80 5.11 Comparações entre os Métodos - Modelo MTZ1S1MP - 3.600 segundos. . . . . . 81 5.12 Comparações entre os Métodos - Modelo MCF1S1MP- 600 segundos. . . . . . . 83 5.13 Comparações entre os Métodos - Modelo MCF1S1MP - 3.600 segundos. . . . . . 84 5.14 Valores dos GAPSU C - Modelo MTZ1S1MP - 3.600 segundos. . . . . . . . . . . . 85 5.15 Valores médios dos GAP SU C e seus respectivos desvios padrões. . . . . . . . . . . 86 5.16 Comparações entre os limitantes inferiores obtidos pelo dual lagrangeano/surrogate e a relaxação linear. . . . 86 6 Introdução Todos usam a Matemática todos os dias: tanto para dizer as horas, prever o tempo, contar dinheiro, como para auxiliar na tomada de decisões. Em situações mais complicadas surge a necessidade de uma teoria matemática para ajudar o ser humano a não só resolver os seus problemas, mas escolher, dentre diversas alternativas, a melhor delas. À este processo deno- minamos Otimização. A otimização, pode ser definida como: ”o conjunto de métodos capazes de determinar as melhores configurações posśıveis para a construção ou o funcionamento de sistemas de interesse para o ser humano” [75]. Sob o ponto de vista empresarial, a Otimização também é de grande valia. Grandes empresas hoje em dia, tem em seu ferramental, a Matemática, a Otimização, que muitas vezes auxiliam na identificação de problemas que a olho nu não são capazes de serem vistos, e os resolve de tal forma que os benef́ıcios consequentes dessa resolução eram inimagináveis. Mais especificamente, no setor de manufaturas, a indústria tem sido pressionada a tornar seus processos mais eficientes, posicionando-se frente à concorrência de uma forma mais agres- siva. As decisões de produção nesse setor de manufatura objetivam determinar o uso mais eficiente dos recursos para atender a produção dos itens requeridos pelos clientes. Estas de- cisões são tomadas geralmente em dois ńıveis: um ńıvel de dimensionamento de lotes e um ńıvel de programação [5]. No ńıvel de dimensionamento de lotes, o objetivo é determinar um plano de produção de curto prazo, ou seja, quanto de cada item produzir a fim de atender as demandas previstas, sob as condições e capacidades operacionais existentes. No ńıvel de programação, o objetivo é determinar a ordem em que os itens serão produzidos de modo a reduzir tempos e custos [84]. Na prática, essas decisões ainda são tomadas de forma independentes mas deveriam ser tomadas conjuntamente. Na teoria, diversos modelos foram formulados a fim de integrar as decisões sobre o sequenciamento da produção às decisões de dimensionamento de lotes [18], [19], [22], [43]. Uma proposta para integrar essas decisões, é o Problema Integrado de Dimensionamento de Lotes e Sequenciamento da Produção (PIDS), é utilizar as restrições de eliminação de subrotas do problema do caixeiro viajante na formulação matemática para o problema de dimensiona- mento de lotes, para obter o sequenciamento dos lotes. Neste trabalho usaremos duas propostas: a primeira acrescentando inequações de eliminação de subsequências propostas por Miller, Tuc- ker e Zemlin (MTZ) [63], e a segunda, é uma formulação do tipo Multi Commodity Flow (MCF), 7 LISTA DE TABELAS 8 introduzida por Claus [13]. Uma questão importante é como determinar limitantes primais e duais para as formulações apresentadas. Para tanto, propomos três métodos (dual Lagrange- ano resolvido pelo algoritmo de subgradiente, dual Lagrangeano resolvido pelo algoritmo de volume e dual Lagrangeano/Surrogate resolvido pelo algoritmo de subgradiente) para obtenção dos limitantes duais e uma heuŕıstica gulosa para os limitantes primais. A obtenção de bons limitantes é importante, por exemplo, quando não temos o CPLEX para resolução do problema. No Caṕıtulo 1, é apresentada uma breve revisão do PIDS e é proposta uma nova formulação em que é explicitada a variável de preparo. Nos Caṕıtulos 2 e 3, fazemos um estudo sobre limites duais e primais para problemas de otimização linear inteiro e a teoria envolvida para obtê-los. No Caṕıtulo 4, apresentamos uma heuŕıstica gulosa para determinar limitantes primais para o PIDS, e alguns métodos para determinar limitantes duais para o PIDS. No Caṕıtulo 5 testamos computacionalmente as técnicas desenvolvidas, e por fim, no Caṕıtulo 6 são apresentadas as conclusões e trabalhos futuros. Caṕıtulo 1 O Problema PIDS Neste caṕıtulo apresentamos uma descrição e a motivação do problema PIDS para este es- tudo, uma breve revisão bibliográfica, e apresentamos os modelos estudados, assim como uma reformulação destes modelos. 1.1 Descrição do problema As decisões de produção no setor de manufatura, por exemplo, objetiva determinar o uso mais eficiente dos recursos utilizados para atender a demanda dos itens requeridos pelos clientes. Estas decisões são tomadas geralmente em dois ńıveis: um ńıvel de dimensionamento e um ńıvel de programação dos lotes [5]. No ńıvel de dimensionamento, o objetivo é determinar um plano de produção, ou seja, quanto de cada item produzir a fim de atender as demandas previstas, sob as condições e capacidades operacionais existentes. No ńıvel de programação, o objetivo é ordenar essa produção de modo a reduzir tempos e custos de trocas entre os itens [84]. Na prática, essas decisões ainda são tomadas de forma independentes mas deveriam ser tomadas de forma conjunta. Como exposto por Wolosewicz et al [84], os modelos matemáticos para resolver os problemas de dimensionamento de lotes e sequenciamento da produção, con- sideram capacidade agregada, não garantindo que o plano de produção seja fact́ıvel quando levado ao ńıvel de programação. Se essa capacidade for superestimada, o plano de produção não representará a realidade em termos de recursos dispońıveis, causando atrasos e clientes não satisfeitos. Por outro lado, se a capacidade for subestimada, os itens serão produzidos num tempo menor, acarretando maior custo de estocagem. Se torna então muito importante lidar simultaneamente com estes dois problemas. Um outro exemplo em que é essencial esta integração, é quando as decisões de sequenci- amento não estão ligadas diretamente com os itens, mas sim com a sequência de produção de determinados materiais que serão utilizados para produzir um grupo de itens demandados. Neste caso podemos diminuir a quantidade de trocas, agrupando itens que usam o mesmo 9 CAPÍTULO 1. O PROBLEMA PIDS 10 material. O PIDS consiste em determinar quanto de cada item produzir e em que ordem serão produ- zidos, de modo a atender as demandas previstas e reduzir custos e tempos de produção, ou seja, determinar simultaneamente a quantidade a ser produzida em cada máquina, qual o peŕıodo e em que ordem. Várias são as técnicas propostas pelos pesquisadores para resolver o problema integrado de dimensionamento de lotes e sequenciamento da produção. Dauzère-Pérès e Lasserre [14] [15] formularam um modelo considerando problemas de sequenciamento e capacidade exata, e resolveram iterando entre o plano de dimensionamento e o de programação. Sikora, Chhajed e Shaw [74] abordaram o problema de forma separada, resolvendo o problema peŕıodo por peŕıodo, do primeiro ao último peŕıodo do horizonte de planejamento, sendo que em cada peŕıodo usaram uma heuŕıstica tipo Silver-Meal [73] para utilizar a capacidade o quanto for posśıvel. Algumas recentes revisões bibliográficas podem ser encontradas em Zhu e Wilhelm [87], e Jans e Degraeve [44] [40]. O problema integrado de dimensionamento de lotes e sequenciamento da produção com preparo dependente da sequência tem sido tratado frequentemente com modelos que subdividem o peŕıodo em subpeŕıodos [22]. Em muitos casos, esta estratégia condiz com a realidade, em que cada subpeŕıodo seria o peŕıodo de 1 dia, por exemplo, sendo que o peŕıodo seria 1 semana. O modelo proposto por Fleischmann e Meyr [22], tem sido utilizado para formular várias aplicações práticas: Araujo et al [3] [4] lidaram com problemas em pequenas fundições, explo- rando esquemas relax-and-fix [85] implementados em um horizonte rolante de planejamento; Araújo et al. [3] propôs variações para o método de busca local; Ferreira et al. [20] e Toledo et al. [77] trataram o problema em uma indústria de bebidas, onde sincronizam os estágios de preparação da bebida e o engarrafamento, sendo que Ferreira et al. [20] propõem várias estratégicas relax-and-fix e Toledo et al. [77] usam um algoritmo genético para sua resolução; Toso et al. [78] trataram o problema quanto a produção de compostos para alimentação animal propondo heuŕısticas relax-and-fix para sua resolução. Wolosewicz et al. [84] propôs um modelo para o problema integrado de dimensionamento de lotes e sequenciamento da produção com sequência fixa de operações nas máquinas, e o método de resolução proposto é uma heuŕıstica Lagrangeana. 1.2 Modelos matemáticos Wolosewicz et al [84] afirmam que os problemas de dimensionamento de lotes e sequenciamento da produção tem que ser lidados simultaneamente, e Clark et al [11] afirma que quando os modelos de dimensionamento de lotes são incorporados aos de sequenciamento da produção, há uma influência considerável na produção. O problema PIDS consiste em determinar simultaneamente a quantidade a ser produzida em cada máquina, qual o peŕıodo e em que ordem. CAPÍTULO 1. O PROBLEMA PIDS 11 O modelo MTZ1S1M proposto por Maldonado, Rangel e Clark [57] consiste em utilizar as restrições MTZ de eliminação de subrotas para eliminar subsequências não desejadas [63]. Já o modelo MCF1S1M, proposto em [58] utiliza as restrições tipo Multi Commodity Flow (MCF). Na descrição dos modelos, iremos considerar um problema com um total de J itens e T peŕıodos no horizonte de planejamento, e os ı́ndices i, j = 1, 2, . . . , J para representar os itens e t = 1, 2, . . . , T para representar os peŕıodos. Os parâmetros e variáveis de decisão utilizados para modelar o problema são apresentados em seguida: # Parâmetros: • hj : custo de estocar uma unidade do item j ; • gj : custo de atrasar uma unidade do item j ; • sij : custo de troca de produção de um item i para o item j ; • pj : tempo de produzir um item j ; • bij : tempo de troca de um item i para o item j ; • djt : demanda do item j no peŕıodo t ; • Ct : tempo total dispońıvel para produção dos itens no peŕıodo t (capacidade da máquina); # Variáveis de decisão: • xjt : quantidade produzida do item j no peŕıodo t ; • I+ jt : quantidade estocada do item j no peŕıodo t ; • I−jt : quantidade em atraso do item j no peŕıodo t ; • zijt : { 1, se há troca do item i para o item j no peŕıodo de tempo t ; 0, caso contrário. • ujt : ordem numérica em que o item j é produzido no peŕıodo t ; O modelo MTZ1S1M é descrito em (1.1)− (1.12). CAPÍTULO 1. O PROBLEMA PIDS 12 Min Z = ∑ j∈J ∑ t∈T (hjI + jt + gjI − jt) + ∑ t∈T ∑ i∈J ∑ j∈J j 6=i sijzijt (1.1) sujeito a: I+ j(t−1) + I−jt + xjt − I+ jt − I−j(t−1) = djt, ∀j,∀t (1.2)∑ j∈J pjxjt + ∑ i∈J ∑ j∈J j 6=i bijzijt ≤ Ct, ∀t (1.3) xjt ≤ Ct pj  J∑ i=i0 i6=j zijt  , ∀j,∀t (1.4) ∑ j∈J zi0jt ≥ J∑ i=i0 zikt, ∀k ∈ J ; k 6= i, ∀t (1.5) J∑ i=i0 i6=k zikt = J∑ j=i0 j 6=k zkjt, ∀k ∈ J, ∀t (1.6) J∑ j=i0 j 6=i zijt ≤ 1, ∀i = i0, 1, . . . , J, ∀t (1.7) ujt ≥ uit + 1− J(1− zijt), ∀i,∀j, i 6= j,∀t (1.8) 1 ≤ ujt ≤ J ∀j, t (1.9) xjt, I + jt , I − jt ≥ 0, zijt = 0/1, ∀i, j,∀t (1.10) I+ j0 = 0, ∀j (1.11) I−j0 = 0, ∀j (1.12) A função objetivo (1.1) minimiza custos de estoque, atraso e troca entre os itens. As restrições (1.2) são as restrições de balanceamento do estoque com a produção, garantindo que a demanda de cada item j em cada peŕıodo de tempo t seja atendida. As restrições (1.3) são as restrições de capacidade, ou seja, impedem que o tempo de produção ultrapasse a capacidade da máquina em cada peŕıodo t. As restrições (1.4) garantem que só haverá produção do item j no periodo t se a máquina estiver preparada para produzir o item j. As restrições (1.5)− (1.7) modelam o sequenciamento dos itens. As restrições (1.5) garantem que o item fantasma i0 é o primeiro a ser produzido em cada peŕıodo. Qualquer custo relacionado ao item i0 é considerado nulo e não interfere na solução do modelo (ver [16]). As restrições (1.6) nos dizem que sempre que um item k for produzido, então um item i anterior foi produzido e será produzido um item j depois de k, ou seja, estas restrições conservam o fluxo de produção. As restrições (1.7) nos asseguram que cada item é produzido no máximo uma vez por peŕıodo t. CAPÍTULO 1. O PROBLEMA PIDS 13 As restrições (1.8) e (1.9) são as restrições MTZ que eliminam subsequências, ou seja, não permitem que hajam subsequências desconexas no sequenciamento dos itens. As restrições (1.11) e (1.12) consideram que não há atraso nem estoque no ińıcio do horizonte de planeja- mento, e as restrições (1.10) são as restrições de domı́nio das variáveis. Oncan et al [66] analisaram e compararam diversas formulações para o Problema do Caixeiro Viajante (PCV). Eles chegaram a conclusão de que a relaxação linear do modelo quando usadas as restrições MTZ são ruins, enquanto que, quando usadas as restrições MCF a relaxaçao linear se aproxima muito do valor ótimo do problema PCV. As restrições MCF tem o papel de eliminar subsequências desconexas e tem ordem polinomial. A ideia principal das restrições MCF é assegurar que, sempre há um caminho do produto inicial s para qualquer outro produto r no peŕıodo de tempo t, obtendo assim o sequenciamento dos itens [12], [56]. Para descrever o modelo MCF1S1M, precisamos incluir uma nova variável: • mrijt = { 1, se o fluxo da commodity r flui do nó i0 para o nó r pelo arco (i,j); 0, caso contrário, onde r ∈ {1, 2, . . . , J}. Uma commodity pode ser entendida como uma mercadoria a ser distribúıda. A variável mrijt sendo 1, nos diz que se a commodity r é inclúıda na sequência de produção, então o item i precede o item j no sequenciamento, pois a commodity r passou pelo arco (i, j). Exemplo 1.2.1. Para enterdermos a variável mrijt, considere um peŕıodo t onde temos que produzir 5 itens e todos eles foram produzidos e sequenciados conforme a Figura 1.1. No ińıcio da produção temos todas as commodities dispońıveis, e elas irão fluir pelo circuito sendo depositas nos nós (itens) conforme são requisitadas. A commodity 1, por exemplo, irá sair do nó 0, fluir pelo nó 3 e será depositada no nó 1. Assim, teremos: m103t = m131t = 1, m115t = m154t = m142t = m120t = 0. CAPÍTULO 1. O PROBLEMA PIDS 14 Figura 1.1: Plano de produção e sequenciamento. O modelo MCF1S1M é descrito por (1.1)− (1.7), (1.11), (1.12) e (1.13)− (1.16). ∑ j∈J mri0jt − ∑ j∈J mrji0t = J∑ j=i0 j 6=r zjrt, ∀r,∀t (1.13) J∑ j=i0 j 6=r mrjrt − J∑ j=i0 j 6=r mrrjt = J∑ j=i0 j 6=r zjrt, ∀r,∀t (1.14) J∑ i=i0 i6=j mrijt = J∑ i=i0 i6=j mrjit, ∀r,∀t; j 6= r,∀t, (1.15) 0 ≤ mrijt ≤ zijt, ∀i, j = i0, 1, . . . , J, ∀r,∀t. (1.16) As restrições (1.13) garantem que todas as comodities sairão do nó inicial i0, ou seja, para algum j a commodity r atravessará o arco (i0, j), e que não existirão comodities dispońıveis quando incluirmos o último arco (k, i0), para algum item k. As restrições (1.14) garantem que a commodity r seja depositada em apenas um nó. As restrições (1.15) são as de conservação de fluxo, e as restrições (1.16) nos dizem que haverá travessia no arco (i, j) se houver troca de produção do item i para o item j. As restrições (1.16) também são restrições de domı́nio das variáveis. Observe que nas duas formulações, MTZ1S1M e MCF1S1M, a decisão sobre o preparo ou não da máquina para a produção de um item é dada implicitamente pelas variáveis de troca através da soma: CAPÍTULO 1. O PROBLEMA PIDS 15 wjt = J∑ i=i0 i6=j zijt, ∀j,∀t. (1.17) De acordo com as restrições (1.7) e (1.10), a variável wjt pertence ao conjunto {0, 1}, para cada j e t, ou seja, se houver troca de um item i para um item j no peŕıodo t, então a máquina tem que ser preparada para produção do item j. Assim, wjt = 1. Caso contrário, a máquina não produzirá o item j e então não há preparo, ou seja, wjt = 0. Desta maneira, podemos definir a variável binária de preparo w: • wjt =  1, se a máquina deve ser preparada para produzir o item j no peŕıodo de tempo t, 0, caso contrário. Isto nos motiva a reformular os modelos MTZ1S1M e MCF1S1M considerando esta nova variável de preparo w. O Modelo MTZ1S1MP é dado por (1.1)− (1.3), (1.17), (1.18) e (1.5)− (1.12), xjt ≤ Ct wjt pj , ∀j,∀t, (1.18) sendo que as restrições (1.18) nos dizem que haverá produção do item j apenas quando a máquina estiver preparada para produźı-lo. Da mesma forma, podemos obter o modelo MCF1S1MP, cuja formulação é dada por (1.1)− (1.3), (1.5)− (1.7), (1.13)− (1.16), (1.17), (1.18) e (1.5)− (1.12). No Apêndice A, são apresentadas as descrições completas dos modelos discutidos nesta seção. Exemplo 1.2.2. Para exemplificar os modelos, considere que queremos resolver uma instância do problema PIDS com os dados: CAPÍTULO 1. O PROBLEMA PIDS 16 • J = 5 • T = 2 • h = ( 6 9 2 9 8 ) • g = ( 90 135 30 135 120 ) • p = ( 1 1 1 1 1 ) • b =  0 8 9 9 8 9 0 8 8 8 6 8 0 7 8 6 6 7 0 6 6 8 6 7 0  • s =  0 402 471 432 378 446 0 396 422 419 278 384 0 343 408 311 324 348 0 304 292 412 288 348 0  • C = ( 1716 1315 ) • d =  40 42 58 44 47 56 52 43 59 52  Figura 1.2: Dados de uma instância do problema PIDS. Escrevendo os modelos na sintaxe do AMPL [23] e utilizando o CPLEX [39] para resolver a instância gerada com os dados apresentados na Figura 1.2, obtemos a solução ilustrada na Figura 1.3. Na solução ótima obtida, a ordem de produção no peŕıodo 1 é produzir os itens na sequência 4−5−3−1−2 e no peŕıodo 2, a ordem é 5−4−2. Os itens 1 e 3 não foram produzidos no peŕıodo 2, mas foi produzida uma quantidade maior destes itens no peŕıodo 1, e estocados para atender a demanda do peŕıodo 2, como podemos ver na Figura 1.4. Os números mostrados nos retângulos representam o tamanho do lote. Por exemplo, no peŕıodo 1 são produzidas 59 unidades do item 5. CAPÍTULO 1. O PROBLEMA PIDS 17 Figura 1.3: Plano de produção e sequenciamento. I+ =  42 0 0 0 56 0 0 0 0 0  Figura 1.4: Estoque da produção. Caṕıtulo 2 Limitantes primais e duais para PI Neste caṕıtulo veremos algumas maneiras de derivar limites superiores e limites inferiores para um problema de otimização inteiro - PI (caso minimização). A partir dos valores destes limitan- tes podemos provar a otimalidade da solução, ou seja, quando os dois limites são iguais ou ainda quando a diferença entre eles é muito pequena. Podemos ainda dar um intervalo, denominado GAP, que é calculado pela diferença do limite superior pelo limite inferior, dividido pelo limite superior. Esse valor nos fornece uma medida de quão boa é a solução fact́ıvel encontrada. 2.1 Limitantes primais Suponhamos que o problema que queremos resolver seja da forma (PI) z = min{f(x)|x ∈ V }. Toda solução fact́ıvel x∗ ∈ V provê um limitante primal (limitante superior, no caso de minimização), para o problema (PI). Entretanto, para muitos problemas inteiros encontrar uma solução fact́ıvel não é trivial. Como exemplo, se tomarmos o problema de partição de conjuntos, saber se existe uma solução fact́ıvel é um problema NP-completo [49]. Uma maneira rápida de obter uma solução fact́ıvel para um PI é usando uma abordagem heuŕıstica [2], [55]. Uma heuŕıstica é um algoritmo desenvolvido a partir de um modelo cog- nitivo, usualmente utilizando regras baseadas na experiência dos desenvolvedores. Os métodos heuŕısticos se utilizam de estratégias, com o objetivo de encontrar uma boa solução, mesmo que não seja a ótima, em um tempo computacional razoável. Ginsberg [27] descreve os pro- cedimentos heuŕısticos como “regras de ouro”. Podemos classificar as heuŕısticas em quatro grupos: • Métodos gulosos - são métodos em que uma solução é constrúıda elemento a elemento, escolhendo a cada iteração aquele que traz o maior retorno para a função objetivo; • Métodos de decomposição - são métodos que consistem em dividir o problema original em vários subproblemas menores de tal forma que a resolução de todos esses subproblemas 18 CAPÍTULO 2. LIMITANTES PRIMAIS E DUAIS PARA PI 19 se combinem e compõem uma solução para o problema maior; • Métodos de redução - são métodos em que algumas variáveis tem seu valor fixado, de acordo com a estrutura do problema original; • Métodos de busca - são métodos que partem de uma solução, que pode ser obtida por outro método, e buscam na sua vizinhança uma solução melhor. Neste trabalho, desenvolvemos um Método Guloso para resolução do problema integrado de dimensionamento de lotes e sequenciamento da produção (ver seção 4.1). 2.2 Limitantes duais Em geral, os algoritmos para resolver um problema de otimização inteiro (PI) geram duas sequências de valores. Uma sequência de limites duais {z} (limites inferiores, no caso do critério de otimização ser minimização), tais que cada elemento zi desta sequência obedeça zi ≤ z. E a outra de limites primais {z} tais que zj ≥ z, para todo elemento desta sequência. Desta forma, um algoritmo para resolver o problema PI gera as sequências: z1 ≤ z2 ≤ . . . ≤ zt ≤ z ≤ zs ≤ . . . z2 ≤ z1. (2.1) O algoritmo para quando zs − zt ≤ ε, (2.2) para algum valor de ε escolhido adequadamente [85]. A relaxação é uma das técnicas utilizadas para gerar limites duais e definida de acordo com a Definição 2.2.1 [26]. Definição 2.2.1 (Relaxação). Um problema (PR) zR = min{g(x) | x ∈ W} é uma relaxação de (PI) z = min{f(x) | x ∈ V } se, e somente se, (i) V ⊆ W , e (ii) g(x) ≤ f(x),∀x ∈ V. A solução ótima de uma relaxação determina um limitante dual para o valor ótimo do problema original. Muitas das vezes a solução do problema relaxado é infact́ıvel para o problema original, mas pode ser usada como ponto de partida para métodos heuŕısticos. Na Proposição 2.2.1, enunciamos algumas relações existentes entre os problemas originais e as relaxações associadas [62], [85]. CAPÍTULO 2. LIMITANTES PRIMAIS E DUAIS PARA PI 20 Proposição 2.2.1. (i) Se (PR) é uma relaxação de (PI), então zR ≤ z; (ii) Seja x∗ a solução ótima do problema relaxado (PR). Se x∗ é fact́ıvel para o problema original (PI) e f(x∗) = g(x∗), então x∗ também é ótimo para (PI); (iii) Se o problema relaxado (PR) é infact́ıvel, então o modelo original (PI) também é infact́ıvel. Demonstração. (i) Sendo x∗ o ótimo de (PI), então x∗ ∈ V ⊆ W e, assim, z = f(x∗) ≥ g(x∗). (2.3) Como x∗ ∈ W , segue que g(x∗) é um limite superior para zR, ou seja, zR ≤ g(x∗). (2.4) Portanto, por (2.3) e (2.4), o resultado segue, ou seja, zR ≤ g(x∗) ≤ z. (ii) Como x∗ é fact́ıvel de (PI), ótimo para (PR) e f(x∗) = g(x∗), segue que z ≤ f(x∗) = g(x∗) = zR. (2.5) Mas, por (i), temos que zR ≤ z. Portanto, conclúımos que z = zR = f(x∗). (iii) Como (PR) é infact́ıvel, então W = ∅. Por (PR) ser uma relaxação de (PI), temos que V ⊆ W = ∅. Logo, V = ∅, ou seja, (PI) também é infact́ıvel. Uma das relaxações mais usadas é a relaxação linear definida na Definição 2.2.2 [85]. Definição 2.2.2 (Relaxação Linear). Considere o problema inteiro (PI) z = min{f(x) : x ∈ P ∩ Zn}, onde P = {x ∈ Rn + : Ax ≤ b}. Então, a relaxação linear de (PI) é o problema (PL) dado por zPL = min{f(x) : x ∈ P}. Observe que como P ∩ Zn ⊂ P e as funções objetivos de (PI) e (PL) são as mesmas, pela Definição 2.2.1, o problema (PL) é uma relaxação de (PI). 2.2.1 Planos de corte Nesta seção, definiremos o que são inequações válidas e como elas podem ser usadas para gerar planos de corte, os quais serão utilizados no Caṕıtulo 5. Precisaremos das definições de poliedro e inequações válidas encontradas nas Definições 2.2.3 e 2.2.4, respectivamente [85]. CAPÍTULO 2. LIMITANTES PRIMAIS E DUAIS PARA PI 21 Definição 2.2.3 (Poliedro). Um subconjunto P ⊂ Rn descrito por um conjunto finito de res- trições lineares P = {x ∈ Rn : Ax ≤ b} é chamado poliedro. Definição 2.2.4 (Inequações Válidas). Uma inequação da forma υx ≤ υ0 é uma inequação válida para o poliedro P ⊂ Rn, se υx ≤ υ0 para todo x ∈ P . A ideia de utilizar inequações válidas reside no fato de que quando acrescentadas ao pro- blema de otimização inteiro, estas diminuem a região fact́ıvel da relaxação linear sem excluir soluções inteiras, aproximando-se assim do envoltório convexo. Esse problema é conhecido como problema de separação [69]. Essa ideia é utilizada no método de planos de cortes que consiste em tratar o problema de otimização linear inteiro como um problema de otimização linear cont́ınuo e acrescentar a este problema, de forma iterativa inequações válidas (planos de cortes). Esses cortes são feitos de forma a eliminar a solução ótima da relaxação linear obtida a cada iteração, quando esta for infact́ıvel para o problema inteiro [60]. Existem muitas inequações válidas que podem ser usadas como planos de cortes [86], entre elas: Inequações GUB (Generalized Upper Bounding) [34], Inequações de cobetura (Cover Cuts) [60], Inequações de cobertura de fluxo (Flow Cuts) [35], [67], Inequações de cobertura de caminho de fluxo (Flow Path) [82], MIR (Mixed Integer Rounding) [59], Cliques [7], Implied Bounds Cuts [36], Inequações de Gomory [9], [31], [85]. Tais inequações são utilizadas por pacotes de otimização como o CPLEX 12.6 [39] que resolvem problemas gerais de otimização inteiro mistos. 2.2.2 Relaxação Lagrangeana Considere o seguinte problema de otimização linear inteiro: zPI = min cx (2.6) s.a. Ax ≤ b, x ∈ Zn. Podemos subdividir o problema (2.6) da seguinte maneira: zPI = min cx s.a. A1x ≤ b1, A2x ≤ b2, x ∈ Zn, ou ainda, CAPÍTULO 2. LIMITANTES PRIMAIS E DUAIS PARA PI 22 zPI = min cx (2.7) s.a. A1x ≤ b1, x ∈ Q, sendo Q = {x ∈ Zn|A2x ≤ b2} e vamos supor que as restrições A1x ≤ b1 são restrições que dificultam a resolução do problema (2.7) no sentido que sem elas, o problema seria de fácil resolução [62]. Definição 2.2.5. Seja π ≥ 0 um vetor. A função Z(π, x) = cx + π(A1x − b1) é dita função Lagrangeana. Definição 2.2.6. A relaxação Lagrangeana de (2.7) relativa às restrições A1x ≤ b1, com mul- tiplicadores de Lagrange π ≥ 0, é o problema ZRL(π) = min Z(π, x) (2.8) s.a. x ∈ Q. O problema (2.8) também é chamado de problema Lagrangeano. Proposição 2.2.2. O problema Lagrangeano (2.8) é uma relaxação do problema inteiro (2.7). Demonstração. De fato, tomando x fact́ıvel para o problema (2.7), então x ∈ Q e assim, fact́ıvel para o problema (2.8). Além disso, observe que Z(π, x) = cx+ π(A1x− b1) ≤ cx, para todo x factivel em (2.7). Assim, de acordo com a Definição 2.2.1, o resultado segue. Observe que como (2.8) é relaxação de (2.7), como demonstrado na Proposição 2.2.2, segue que ZRL(π) ≤ ZPI ,∀π ≥ 0, ou seja, para cada π ≥ 0, temos um limitante inferior ZRL(π) para ZPI . Logo, o interessante seria encontrarmos o maior desses limitantes inferiores, ou seja, o equivalente a resolvermos o problema: ZDL = max ZRL(π) (2.9) π ≥ 0. Definição 2.2.7. O problema (2.9) é chamado dual Lagrangeano de (2.7) com relação às res- trições A1x ≤ b1. CAPÍTULO 2. LIMITANTES PRIMAIS E DUAIS PARA PI 23 Observe que o problema (2.9) pode ser reescrito da seguinte maneira: ZDL = max π≥0 min x∈Q Z(π, x), (2.10) ou seja, o problema dual Lagrangeano é um problema não diferenciável irrestrito [8], [24], [62]. Desta maneira, técnicas de otimização não diferenciável serão necessárias para sua re- solução. A relaxação Lagrangeana também pode ser aplicada a problemas com restrições de igual- dade. Suponhamos que o problema que queremos relaxar via multplicadores de Lagrange seja da seguinte forma: min cx s.a. A1x = b1, A2x ≤ b2, x ∈ Zn. As restrições complicadoras são as restrições de igualdade A1x = b1. Observe que podemos reescrever esta restrição como sendo a interseção dos hiperplanos A1x ≤ b1 e −A1x ≤ −b1. Agora, tomando os multiplicadores µ ≥ 0 e ν ≥ 0, e dualizando estas duas restrições, temos min cx+ µ(A1x− b1) + ν(−A1x+ b1) s.a. A2x ≤ b2, x ∈ Zn, que pode ser reescrito convenientemente como min cx+ π(A1x− b1) s.a. A2x ≤ b2, x ∈ Zn, sendo π = µ− ν. Neste caso, π é livre de sinal, pois é posśıvel que µ < ν. Definição 2.2.8. 1. Fixado um valor de π, denotaremos a solução do problema (2.8) em relação a este π fixado, por x(π). 2. Dado um problema de otimização P, denotaremos por v(P) o valor ótimo de P. CAPÍTULO 2. LIMITANTES PRIMAIS E DUAIS PARA PI 24 Proposição 2.2.3. Seja π ≥ 0. Se x(π) satisfaz as seguintes condições (i) é ótimo para (2.8), (ii) é fact́ıvel para (2.7), ou seja, A1x(π) ≤ b1, e (iii) satisfaz as folgas complementares, ou seja, π(A1x(π)− b1) = 0, então x(π) é ótimo para (2.7) e ZDL = ZPI . Demonstração. Por (i), temos que x(π) é ótimo para o problema (2.8), ou seja, ZDL ≥ ZRL(π) = cx(π) + π(A1x(π)− b1); Por (iii), temos que π(A1x(π)− b1) = 0, ou seja, cx(π) + π(A1x(π)− b1) = cx(π); Ainda, por (ii), sendo x(π) fact́ıvel para o problema (2.7), segue que cx(π) ≥ ZPI . Logo, concluimos que ZDL ≥ ZRL(π) = cx(π) ≥ ZPI , ou seja, ZDL ≥ ZPI . Como sabemos que ZPI ≥ ZDL, o resultado segue, ou seja, ZDL = ZPI . Observe que podemos ter x(π) ótimo para o problema (2.7) sem satisfazer as folgas com- plementares, já que a condição é apenas suficiente, e não necessária. Outro detalhe importante é que se as restrições a serem dualizadas são restrições de igualdade, então não necessitamos verificar as folgas complementares, uma vez que estas são automaticamente satisfeitas. Exemplo 2.2.1. Para exemplificar alguns conceitos mencionados neste texto, considere o se- guinte problema de otimização inteiro [2]: ZPI = min−7x1 − 2x2 −x1 + 2x2 ≤ 4 5x1 + x2 ≤ 20 −2x1 − 2x2 ≤ −7 (2.11) −x1 ≤ −2 x2 ≤ 4 x ∈ Z2 +. CAPÍTULO 2. LIMITANTES PRIMAIS E DUAIS PARA PI 25 Denominemos de V o conjunto fact́ıvel do problema (2.11), e dualizemos a restrição −x1 + 2x2 ≤ 4 com o multiplicador de Lagrange π ≥ 0. Desta forma, o subproblema Lagrangeano é dado pelo problema (2.12): ZRL(π) = min−7x1 − 2x2 + π(−x1 + 2x2 − 4) 5x1 + x2 ≤ 20 −2x1 − 2x2 ≤ −7 (2.12) −x1 ≤ −2 x2 ≤ 4 x ∈ Z2 +. Da mesma forma, denominemos por Q o conjunto fact́ıvel do problema (2.12). Podemos ver na Figura 2.1 os conjuntos fact́ıveis Q, conv(Q) e conv(V). Observe que Q = {x1, x2, . . . , x8} = {(2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 0)}. Figura 2.1: Conjuntos fact́ıveis Q, conv(Q) e conv(V), e soluções do problema inteiro, do problema dual Lagrangeano e da relaxação linear. A sigla (PL) usada na Figura 2.1 refere-se a relaxação linear do problema (PI). Podemos tentar resolver o problema 2.12 usando duas abordagens: CAPÍTULO 2. LIMITANTES PRIMAIS E DUAIS PARA PI 26 1a abordagem: Tomar a função Z(π, x) como uma função afim de x para π fixo. Para π fixo, podemos obter o valor de ZRL(π) resolvendo o seguinte problema de programação linear: ZRL(π) = min Z(π, x) x ∈ conv(Q), onde conv(Q) = {x ∈ R2 + | −x1 ≤ −2, x2 ≤ 4,−x1 − x2 ≤ −4, 4x1 + x2 ≤ 16}, que, para este exemplo, pode facilmente ser obtido usando a Figura 2.1. Assim, o subproblema Lagrangeano se torna: ZLR(π) = min−7x1 − 2x2 + π(−x1 + 2x2 − 4) −x1 − x2 ≤ −4 4x1 + x2 ≤ 16 (2.13) −x1 ≤ −2 x2 ≤ 4 x ∈ R2 +. Para resolvermos o problema (2.13), como π é fixo, podemos usar uma heuŕıstica simples de busca, ir variando π até encontrarmos a solução ótima, já que a função ZLR(π) é uma função linear por partes côncava. Por exemplo, π = 0 ⇒ ZRL(0) = min {−7x1 − 2x2 | x ∈ conv(Q)} = Z(0, x7) = −29 π = 0.1 ⇒ ZRL(0.1) = min {−7.1x1 − 1.8x2 − 0.4 | x ∈ conv(Q)} = Z(0.1, x7) = −28.9 π = 0.5 ⇒ ZRL(0.5) = min {−7.5x1 − x2 − 2 | x ∈ conv(Q)} = Z(0.5, x8) = −32 π = 0.75 ⇒ ZRL(0.75) = min {−7.75x1 − 0.5x2 − 3 | x ∈ conv(Q)} = Z(0.75, x8) = −34 π = 1 ⇒ ZRL(1) = min {−8x1 − 4 | x ∈ conv(Q)} = Z(1, x8) = −36 π = 1.5 ⇒ ZRL(1.5) = min {−8.5x1 + x2 − 6 | x ∈ conv(Q)} = Z(1.5, x8) = −40. Observe que ∇ZRL(π) = (−7 − π,−2 + 2π), e assim para qualquer π > 1, a solução do problema é o ponto x8, pois o vetor gradiente se encontra no 2o quadrante e o ponto x8 é o ponto mais distante com relação as retas perpendiculares ao vetor gradiente. Assim, fixemos x8 e verifiquemos o que acontece quando π → +∞. Considerando x8 fixo, temos ZRL(π) = −4π − 32 e assim, ZRL(π)→ −∞. Logo, o valor de π ótimo pertence ao intervalo [0, 1), mais precisamente, próximo do valor 0.1, como podemos ver quando variamos o valor de π. CAPÍTULO 2. LIMITANTES PRIMAIS E DUAIS PARA PI 27 Fazendo mais algumas comparações entre os valores de π, chegamos que a solução ótima de π é 0, 11 e de x é x7, cujo valor ótimo é −28, 89. 2a abordagem: Tomar a função Z(π, x) como uma função afim de π para x fixo. Para cada xi, i = 1, 2, . . . 8, temos uma função ZRL(π) : Z(π, x1) = −18− 2π Z(π, x2) = −20 Z(π, x3) = −22 + 2π Z(π, x4) = −23− 5π Z(π, x5) = −25− 3π Z(π, x6) = −27− π Z(π, x7) = −29 + π Z(π, x8) = −28− 8π. Na Figura 2.1, podemos ver os gráficos das funções Z(π, xi), i = 1, 2, . . . , 8, e em vermelho, a função ZRL(π). Temos que ZRL(π) = min π≥0 ZRL(π, x) = min π≥0 Z(π, xi) x ∈ Q i = 1, 2, . . . , 8, e, assim, ZRL(π) = min π≥0 {−18− 2π,−20,−22 + 2π,−23− 5π,−25− 3π,−27− π,−29 + π,−28− 8π} = { −29 + π, se 0 ≤ π ≤ 1/9 −28− 8π, se π ≥ 1/9. Claramente vemos que π = 1/9 maximiza a função ZRL(π), e assim, ZDL = ZRL(1/9) = −28.89. Uma outra maneira de enxergarmos essa solução é a seguinte: Sabemos que ZDL = max π≥0 ZRL(π) = max π≥0 min i=1,2,...,8 Z(π, xi), que é equivalente a CAPÍTULO 2. LIMITANTES PRIMAIS E DUAIS PARA PI 28 Figura 2.2: Gráficos das funções Z(π, xi), i = 1, 2, . . . , 8. ZDL = max π≥0 w w ≤ Z(π, xi), i = 1, 2, . . . , 8. Ou seja, necessitamos apenas resolver o problema de otimização linear: CAPÍTULO 2. LIMITANTES PRIMAIS E DUAIS PARA PI 29 ZDL = max w w ≤ −18− 2π w ≤ −20 w ≤ −22 + 2π w ≤ −23− 5π w ≤ −25− 3π w ≤ −27− π w ≤ −29 + π w ≤ −28− 8π w ≥ 0, π ≥ 0. A solução deste problema é π = 1/9 e w = −28.89. Observe que em todas as abordagens usadas para resolver o problema do Exemplo 2.2.1, foi preciso conhecer todos os pontos do conjunto Q, tornando essas práticas inviáveis para proble- mas de grande porte. No Teorema 2.2.1, apresentamos um resultado proposto por Geoffrion [26], que embasa toda a teoria de ralaxação Lagrangeana. Teorema 2.2.1. O dual Lagrangeano (2.9) é equivalente ao problema min cx (2.14) s.a. A1x ≤ b1, x ∈ conv(Q), no sentido de que o valor ótimo do problema (2.14) é igual ao valor ótimo do problema (2.9). O problema (2.14) é dito relaxação primal (RP). Demonstração. Suponhamos que Q seja não vazio e limitado. Observe que: ZRL(π) = min cx+ π(A1x− b1) = min cx+ π(A1x− b1) x ∈ Q x ∈ conv(Q). Sabemos que ZDL = max π≥0 ZRL(π). Logo, CAPÍTULO 2. LIMITANTES PRIMAIS E DUAIS PARA PI 30 ZDL = max π≥0 min cx+ π(A1x− b1) x ∈ conv(Q). Como Q 6= ∅, podemos reescrever Q em função de seus pontos extremos como sendo Q = {xk ∈ Zn+ | k ∈ K}, onde K é o conjunto de ı́ndices dos pontos extremos, ou seja, a cardinalidade de K é a quantidade de pontos extremos de Q uma vez que tomamos Q limitado. Desta forma, teremos que min cx+ π(A1x− b1) = cxk + π(A1xk − b1), s.a. x ∈ conv(Q). para algum k ∈ K, e ZDL = max π≥0 [ min k∈K cxk + π(A1xk − b1) ] . Equivalentemente, temos que ZLD = max µ s.a. µ ≤ cxk + π(A1xk − b1), k ∈ K π ≥ 0, µ livre, que ainda equivale a ZLD = max µ s.a. µ− π(A1xk − b1) ≤ cxk, k ∈ K (2.15) π ≥ 0, µ livre. Dualizando o problema (2.15) nas variáveis duais αk, k ∈ K, temos ZLD = min ∑ k∈K (cxk)αk s.a.− ∑ k∈K (A1xk − b1)αk ≥ 0∑ k∈K αk = 1 αk ≥ 0, k ∈ K, CAPÍTULO 2. LIMITANTES PRIMAIS E DUAIS PARA PI 31 que equivale a ZLD = min ∑ k∈K (cxk)αk s.a. ∑ k∈K (A1xk)αk ≤ b1 ∑ k∈K αk = 1 αk ≥ 0, k ∈ K, que pode ser reescrito como: ZLD = min cx A1x ≤ b1 x ∈ conv(Q), uma vez que conv(Q) = { x ∈ Rn + | x = ∑ k∈K αkxk, ∑ k∈K αk = 1, αk ≥ 0, k ∈ K } . Portanto, o resultado segue. Guignard [62] observa que se a matriz de restrições não for formada por números racionais, então o Teorema 2.2.1 pode não ser verdadeiro. Definição 2.2.9. O problema (2.9) tem a propriedade de integralidade se {x | A2x ≤ b2} = conv{x | A2x ≤ b2}. Na Figura 2.3, podemos ver uma interpretação geométrica da relaxação Lagrangeana. Ob- servando a Figura 2.3, se o problema (2.9) tem a propriedade de integralidade, então a relaxação primal não produz melhor limitante que a relaxação linear. Esta observação nos motiva ao se- guinte corolário: Corolário 2.2.1. 1. Se o problema (2.9) tem a propriedade de integralidade, então v(PL) = v(RP ) = v(RL) ≤ v(PI). 2. Se o problema (2.9) não tem a propriedade de integralidade, ou seja, {x | A2 ≤ b2} ⊃ conv{x | A2 ≤ b2}, então v(PL) < v(RP ) = v(RL) ≤ v(PI). Este resultado nos diz que o limitante obtido através da relaxação Lagrangeana é melhor ou igual ao obtido pela relaxação linear. CAPÍTULO 2. LIMITANTES PRIMAIS E DUAIS PARA PI 32 Figura 2.3: Interpretação geométrica da relaxação Lagrangeana [62]. 2.2.3 Relaxação Surrogate A relaxação Surrogate tem sido menos aplicada que a relaxação Lagrangeana. Ela apareceu pela primeira vez na literatura nos trabalhos de Glover [28] e [29]. Esta técnica consiste basicamente em substituir um conjunto de restrições do problema original (PI) por uma combinação linear destas restrições, dando origem a chamada restrição Surrogate. Em 1975, Glover [30] apresentou a teoria da dualidade Surrogate, resumindo o trabalho feito anteriormente por Greenberg e Pierskalla [33]. Em 1979 Karwan e Rardin [46] desenvolveram um estudo relacionando o dual Lagrangeano e o dual Surrogate, para o caso de problemas inteiros. Lorena, Freville e Plateau [51], Lorena e Lopes [52], e Lorena e Narciso [53] utilizaram a relaxação Surrogate cont́ınua, ou seja, relaxa-se também as restrições de integralidade, aos problemas da mochila 0− 1, cobertura de conjuntos e ao problema generalizado de atribuição, respectivamente. Em todos eles pode-se observar um melhor desempenho com relação ao uso da relaxação Lagrangeana. A formulação do problema Surrogate é bastante simples. Considere o problema de oti- mização inteiro (PI) definido na Subseção 2.2.2: CAPÍTULO 2. LIMITANTES PRIMAIS E DUAIS PARA PI 33 zPI = min cx s.a. A1x ≤ b1, (2.16) A2x ≤ b2, x ∈ Zn. Considere um vetor de multiplicadores µ = (µ1, µ2, . . . , µk), onde µi ≥ 0, i = 1, 2, . . . , k. Uma relaxação Surrogate RS(µ) do problema (2.16) pode ser formulada como zRS(µ) = min cx s.a. µ(A1x− b1) ≤ 0, (2.17) A2x ≤ b2, x ∈ Zn. Desta forma, as k restrições escritas como A1x ≤ b1, são substitúıdas por apenas uma restrição µ(A1x − b1) ≤ 0. Quando também relaxamos as restrições de integralidade, pondo x ∈ Rn, obtemos a relaxação Surrogate cont́ınua. Galvão [25] diz que problemas resultantes de relaxação Surrogate são mais dif́ıceis de resolver que os da relaxação Lagrangeana, devido a natureza de mochila que os problemas relaxados obtém. Entretanto, o dual Surrogate (DS), definido como ZDS = max ZRS(µ) (2.18) µ ≥ 0, fornece limites melhores ou iguais ao dual Lagrangeano, como veremos nos Teoremas 2.2.2 e 2.2.3. Teorema 2.2.2. Considere os problemas PI, RS(µ) e DS definidos por 2.16, 2.17 e 2.18, respectivamente. Então, v(RS(µ)) ≤ v(PI), e consequentemente, v(DS) ≤ v(PI). Demonstração. Claramente, para cada µ ≥ 0, temos que o problema Surrogate RS(µ) é uma relaxação do problema (PI), conforme o item (i) da Proposição 2.2.1, pois toda solução fact́ıvel de (PI) também é factivel para RS(µ). Assim, ainda pela Proposição 2.2.1, v(RS(µ)) ≤ v(PI), ∀µ ≥ 0. Como a desigualdade é válida para todo µ ≥ 0, segue que CAPÍTULO 2. LIMITANTES PRIMAIS E DUAIS PARA PI 34 max µ≥0 v(RS(µ)) ≤ v(PI). Mas, max µ≥0 v(RS(µ)) = v(DS). Logo, v(DS) ≤ v(PI). Teorema 2.2.3. Considere os problemas (PI), (DL(π)) e (DS(µ)) como definidos anterior- mente. Então, v(DL(π)) ≤ v(DS(µ)). Além disso, se v(DL(π)) = v(DS(µ)), então para qualquer π que resolva (DL(π∗)), deve existir x∗ tal que π∗(A2x∗ − b2) = 0. Demonstração. Ver o livro de Parker e Rardin [68]. 2.2.4 Relaxação Lagrangeana/Surrogate A relaxação Lagrangena/Surrogate foi proposta por Narciso [64]. Seu objetivo é combinar as re- laxações Lagrangeana e Surrogate para conseguir melhores tempos computacionais na aplicação de heuŕısticas subgradientes. Esta relaxação consiste em relaxar via multiplicadores Surrogate um conjunto de restrições, e depois relaxar via multiplicadores de Lagrange esta única restrição. O multiplicador de Lagrange é unidimensional. Considere o problema de otimização inteiro (PI) definido na Subseção 2.2.2: zPI = min cx s.a. A1x ≤ b1, (2.19) A2x ≤ b2, x ∈ Zn. A relaxação Surrogate RS(µ) do problema (2.19) (ver Subseção 2.2.3): zRS(µ) = min cx s.a. µ(A1x− b1) ≤ 0, (2.20) A2x ≤ b2, x ∈ Zn. Relaxando a restrição Surrogate de RS(µ) via multiplicadores de Lagrange, obtemos o sub- problema Lagrangeano/Surrogate (RLS(t, µ)): CAPÍTULO 2. LIMITANTES PRIMAIS E DUAIS PARA PI 35 zRLS(t, µ) = min cx+ tµ(A1x− b1) s.a. A2x ≤ b2, (2.21) x ∈ Zn. Da mesma forma que as outras relaxações, temos o dual Lagrangeano Surrogate (DLS): ZDLS = max ZRLS(t, µ) (2.22) t ≥ 0, µ ≥ 0, Claramente, se substituirmos u = tπ obtemos o dual Lagrangeano usual. Fixando µ∗ ≥ 0, e enxergando a função Lagrangeana/Surrogate em função do parâmetro t, ou seja, RLS(t, µ∗) = (µ∗A1x− µ∗b1)t+ cx, uma visualização do seu comportamento pode ser visto na Figura 2.4. Figura 2.4: Comportamento da função Lagrangeano/Surrogate em função de t [64]. O objetivo então é encontrar t∗ que maximize o valor de ZRLS(t, µ∗). Existem vários métodos que encontram o valor de t que minimiza o valor da função v(RLS(t, µ)), como dito por Narciso [64]. Entretanto, estes métodos são caros computacionalmente. O método usado neste trabalho é apresentado na subseção 4.3.1. O método consiste em fixado um valor para µ = µ∗ e dado um valor inicial para t, buscar na vizinhança de t melhores limitantes para o problema (2.21). Caṕıtulo 3 Solução do problema dual Lagrangeano Neste caṕıtulo, introduziremos métodos para resolver o problema dual Lagrangeano, e apresen- tamos alguns conceitos para melhor entendimento dos métodos. Como vimos no Exemplo 2.2.1, o problema dual Lagrangeano é linear por partes, não diferenciável e côncavo [41], [10]. Assim, é necessário um método de otimização não linear para resolver o problema dual Lagrangeano. Solodov [42] argumenta que problemas de otimização não diferenciáveis necessitam da utilização de técnicas de solução próprias, diferentes daquelas para o caso diferenciável. Para a minimização irrestrita sobre uma função convexa f , muitos métodos estão dispońıveis: subgradientes, planos de corte, métodos de feixes, entre outros. Esses métodos tem suas vantagens e desvantagens, e as respectivas eficiências dependerão da natureza do problema a ser resolvido. De uma maneira geral, os algoritmos de otimização não diferenciável, fundamentam-se na geração de iterados xk através da busca de posśıveis direções de descida dk e tamanhos de passo sk, e consequente atualização na forma xk+1 = xk + skd k. 3.1 Conceitos básicos Nesta seção, faremos uma introdução a alguns conceitos da teoria de Análise Matemática e Oti- mização Não Linear necessária para o entendimento dos métodos apresentados neste Caṕıtulo. Mais detalhes podem ser obtidos em [41], [42], [50]. De maneira informal, podemos definir uma sequência como uma sucessão interminável de termos. O interesse em sequências vem particularmente em saber como ela evolui, ou seja, como ela se comporta conforme seus termos vão sendo gerados. Formalmente, a definição de sequência é dada pela Definição 3.1.1: Definição 3.1.1 (Sequência). Uma sequência é uma função x : N → R. O valor x(n) será representado por xn e chamado termo de ordem n da sequência. 36 CAPÍTULO 3. SOLUÇÃO DO PROBLEMA DUAL LAGRANGEANO 37 Intuitivamente, dizer que o número real a é limite de uma sequência (xn) significa afirmar que quanto maior o valor de n, mais próximo a sequência está de a. Isto nos leva a seguinte definição: Definição 3.1.2 (Limite de Sequência). Dizemos que o número real a é limite de uma sequência xn, se para cada valor arbitrário de ε > 0, for posśıvel obter um número n0 ∈ N tal que | xn − a |< ε, para todo n > n0. Denotaremos limxn = a. Em śımbolos matemáticos, limxn = a⇔ ∀ε > 0,∃n0 ∈ N;n > n0 ⇒| xn − a |< ε. Uma sequência (xn) limitada (ou seja, a ≤ xn ≤ b, ∀n) pode não ter limite. Para resolver este problema, generaliza-se o limite, como vemos na Definição 3.1.3: Definição 3.1.3 (Limites Superior e Inferior). Seja (xn) uma sequência limitada em R. O lim sup de (xn) é definido por: lim supxn := lim k→∞ sup{xn | n ≥ k}, e o lim inf de (xn) é definido por: lim inf xn := lim k→∞ inf{xn | n ≥ k}. Definição 3.1.4 (Séries). Dada uma sequência (xn) de números reais, chama-se série numérica a soma infinita: x1 + x2 + . . . , xn + . . . = ∞∑ k=1 xn. Para calcularmos, se posśıvel, o valor da série ∞∑ k=1 xn, consideremos a seguinte sequência: S1 = x1; S2 = x1 + x2; S3 = x1 + x2 + x3; ... Sn = x1 + x2 + . . .+ xn; ... em que cada Si, ∀i é chamado de soma parcial de (xn). Com esta observação, a Definição 3.1.5 nos ajuda a verificar se a série tem ou não valor finito. CAPÍTULO 3. SOLUÇÃO DO PROBLEMA DUAL LAGRANGEANO 38 Definição 3.1.5 (Convergência de Série). Se existe um número real S tal que lim n→∞ Sn = S, então dizemos que a série ∞∑ k=1 xn é convergente e ∞∑ k=1 xn = S. Uma condição necessária para a convergência de uma série é que seu termo geral tenda para zero [50], ou seja, Teorema 3.1.1. Se ∞∑ k=1 xn é uma série convergente, então limxn = 0. Demonstração. Como a série ∞∑ k=1 xn é convergente, pela Definição 3.1.5 temos que existe um valor S real tal que lim n→∞ Sn = S. Claramente, lim n→∞ Sn−1 = S. Observe que Sn − Sn−1 = x1 + x2 + . . .+ xn − x1 − x2 − . . .− xn−1 = xn. Desta forma, 0 = S − S = lim n→∞ Sn − lim n→∞ Sn−1 = lim n→∞ (Sn − Sn−1) = lim n→∞ xn, ou seja, limxn = 0. Convexidade é uma noção muito importante na teoria de otimização, pois com hipóteses de convexidade, todo ponto estacionário torna-se uma solução global do problema. Em particular, qualquer minimizador local é global. Definição 3.1.6 (Conjunto convexo). Seja D ⊂ Rn. Dizemos que D é convexo, se αx+ (1− α)y ∈ D, ∀x, y ∈ D, ∀α ∈ [0, 1]. O ponto αx + (1 − α)y, onde α ∈ [0, 1], chama-se combinação convexa de x e y (com parâmetro α). O conjunto vazio, o espaço Rn e um conjunto que contém um ponto só são trivialmente convexos. Definição 3.1.7 (Função convexa). Seja D ⊂ Rn um conjunto convexo. A função f : D → R é dita convexa em D quando para quaisquer x, y ∈ D, e α ∈ [0, 1], tem-se: f(αx+ (1− α)y) ≤ αf(x) + (1− α)f(y). Diremos que uma função f é côncava, se −f é convexa. CAPÍTULO 3. SOLUÇÃO DO PROBLEMA DUAL LAGRANGEANO 39 Figura 3.1: f(x) = |x|. Exemplo 3.1.1. A função f(x) = |x| é convexa em R. De fato, sejam x, y ∈ R. Aplicando a definição 3.1.7, temos: f(αx+ (1− α)y) = |αx+ (1− α)y| ≤ α|x|+ (1− α)|y| = αf(x) + (1− α)f(y). Logo, a função f(x) = |x| é convexa em R. O gráfico desta função é exibido na Figura 3.1.1. A seguir, estudaremos uma generalização do conceito de gradiente, chamada subgradiente, para o caso de funções convexas não diferenciáveis. Definição 3.1.8 (Subgradiente). Seja f : Rn → R uma função convexa. Dizemos que y ∈ Rn é um subgradiente de f no ponto x ∈ Rn se f(z) ≥ f(x) + 〈y, z − x〉, ∀z ∈ Rn, em que 〈a, b〉 = n∑ i=1 aibi, a, b ∈ Rn. O conjunto de todos os subgradientes de f em x se chama o subdiferencial de f em x, e o denotamos por ∂f(x). O sugbradiente nada mais é do que uma aproximação linear de f cujo gráfico fica abaixo do gráfico de f , e cujo valor coincide com f no ponto x. Definição 3.1.9 (Direção de descida). Dizemos que d ∈ Rn é uma direção de descida da função f : Rn → R no ponto x ∈ Rn, se existe ε > 0 tal que: f(x+ td) < f(x), ∀t ∈ (0, ε]. Denotamos por Df (x) o conjunto de todas as direções de descida da função f no ponto x. CAPÍTULO 3. SOLUÇÃO DO PROBLEMA DUAL LAGRANGEANO 40 Figura 3.2: Os elementos y1 e y2 são subgradientes de f em x, isto é, para todo z tem-se que f(z) ≥ f(x) + 〈yi, z − x〉, i = 1, 2. Uma condição necessária e suficiente para que d ∈ Rn seja uma direção de descida da função f , convexa em Rn, no ponto x é: d ∈ Df (x)⇔ 〈y, d〉 < 0, ∀y ∈ ∂f(x). Se tomarmos um subgradiente qualquer, a direção de anti-subgradiente pode não ser de descida. Veja o exemplo abaixo: Exemplo 3.1.2. Seja f : R2 → R, f(x) = |x1|+ 2|x2|. Veja o gráfico desta função na Figura 3.3. Consideremos um ponto x = (x1, 0), tal que x1 > 0 é arbitrário. É fácil verificar que y = (1, 2) ∈ ∂f(x), pois f(x) + 〈y, z − x〉 = f(x1, 0) + 〈(1, 2), (z1, z2)− (x1, 0)〉 = |x1|+ 〈(1, 2), (z1 − x1, z2)〉 = |x1|+ z1 − x1 + 2z2 x1>0 = x1 + z1 − x1 + 2z2 = z1 + 2z2 ≤ |z1|+ 2|z2| = f(z), ∀z ∈ R2. CAPÍTULO 3. SOLUÇÃO DO PROBLEMA DUAL LAGRANGEANO 41 No entanto, para todo t > 0 suficientemente pequeno, f(x− ty) = |x1 − t|+ 2|0− 2t| = x1 − t+ 4t = x1 + 3t > x1 = f(x), o que mostra que −y 6∈ Df (x). Figura 3.3: Gráfico de f(x) = |x1|+ 2|x2|. Teorema 3.1.2. Sejam f : Rn → R e fi : Rn → R, i = 1, . . . , p, funções convexas. Então, (a) ∀x ∈ Rn, ∂f(x) é convexo, compacto e não-vazio; (b) f é diferenciável em x⇔ ∂f(x) = {f ′(x)}; (c) x é minimizador de f no Rn ⇔ 0 ∈ ∂f(x); (d) ∂ ( p∑ i=1 fi(x) ) = p∑ i=1 ∂fi(x). Demonstração. Ver Teorema 1.3.9 em [42] e Proposição 3.4.8 em [41]. Na Definição 3.1.10 abaixo, apresentamos uma noção muito importante do ponto de vista computacional, a de subgradiente aproximado. Segundo Izmailov e Solodov [41], sua utilidade é analisar a convergência de vários métodos interativos para otimização não diferenciável. Definição 3.1.10 (ε - subgradiente). Sejam f : Rn → R uma função convexa e ε ∈ R+. Dizemos que y ∈ Rn é um ε-subgradiente de f no ponto x ∈ Rn quando f(z) ≥ f(x) + 〈y, z − x〉 − ε, ∀z ∈ Rn. O conjunto de todos os ε-subgradientes de f em x, denotado por ∂εf(x), é chamado de ε-subdiferencial de f em x. CAPÍTULO 3. SOLUÇÃO DO PROBLEMA DUAL LAGRANGEANO 42 Um outro resultado importante que nos será útil nos caṕıtulos seguintes é o Teorema 3.1.3. Teorema 3.1.3. Sejam D ⊂ Rn um conjunto convexo e aberto, e f : D → R uma função convexa em D. Então, f é cont́ınua em D. Demonstração. Ver Teorema 3.4.2 em [41]. Apresentaremos a seguir métodos para resolver o problema (3.1), escrito da forma geral min f(x) sujeito a x ∈ X, (3.1) tal que o conjunto fact́ıvel X ⊂ Rn é convexo e a função objetivo f : Rn → R é convexa e não necessariamente diferenciável em todos os pontos. Um dos métodos mais básicos para resolvermos o problema primal (3.1) é gerar uma sequência {xk} tal que a função objetivo f(xk) decresce em cada iteração, e as direções de descida são as caracterizadas na Definição 3.1.9. Um pseudocódigo para este método, Método de Descida, é exibido na Figura 3.4. Método de Descida 1. Tome x0 inicial e k = 1. 2. Se 0 ∈ ∂f(xk) e xk ∈ X então PARE. 3. Calcule uma direção de descida dk; 4. Defina um tamanho de passo sk onde f(xk + skd k) < f(xk); 5. Atualize xk+1 = xk + skd k; 6. Incremente k = k + 1 e volte ao Passo 2. Figura 3.4: Pseudocódigo do Método de Descida. O critério de parada 0 ∈ ∂f(xk) é justificado da seguinte maneira: 0 ∈ ∂f(xk)⇔f(y) ≥ f(xk)− 〈0, y − xk〉, ∀y ∈ Rn, ⇔f(y) ≥ f(xk), ∀y ∈ Rn, ou seja, se 0 é um subgradiente da função f em xk, então xk é a solução do problema (3.1), desde que xk ∈ X. Observamos que o teste de parada descrito no passo 2 é impraticável ou até mesmo im- posśıvel do ponto de vista computacional, pois não conhecemos todo o conjunto subdiferencial. Um bom exemplo desta situação é a relaxação Lagrangeana, onde a avaliação da função dual num dado ponto fornece apenas um subgradiente neste ponto. Assim, este método não é im- plementável. Nas próximas seções veremos algoritmos que tentam contornar essa questão. CAPÍTULO 3. SOLUÇÃO DO PROBLEMA DUAL LAGRANGEANO 43 3.2 Algoritmo do Subgradiente Vimos na seção 3.1 que é impraticável conhecer todo o conjunto subdiferencial. Uma maneira de contornarmos isso é exigir o cálculo de apenas um subgradiente. Outro detalhe infeliz de algoritmos similares ao algoritmo exibido na Figura 3.4 é que nem sempre obtemos direções reais de descida, pois nem sempre a direção antisubgradiente é uma direção de descida, como vimos no Exemplo 3.1.2. Logo, para um algoritmo de resolução ser considerado eficiente ele tem que gerar e reconhecer candidatos reais de descida, ou seja, direções que realmente causem um decréscimo na função objetivo. A ideia do Algoritmo de Subgradiente é baseada no método de Cauchy, onde uma direção de descida é a oposta ao vetor gradiente. No caso do método de Subgradientes, tomaremos o vetor oposto ao subgradiente. Fukuda [24] diz que escolhas adequadas do tamanho do passo podem garantir a convergência do método, apesar de não gerar decréscimo a cada iteração na função objetivo. Na realidade, esta dificuldade em gerar decréscimos é contornada fixando inicialmente uma sequência de valores de comprimentos de passos. Entretanto, Solodov [42] diz que esta estratégia não é satisfatória na prática, apesar de resolver a dificuldade no âmbito teórico. Algoritmo de Subgradiente Básico 1. Escolha sequências de valores reais positivos {εk}, {sk}; 2. Tome x0 um vetor inicial e inicialize k = 0; 3. Calcule dk ∈ ∂εkf(xk); 4. Atualize xk+1 = xk + skd k; 5. Incremente k = k + 1 e volte ao Passo 1. Figura 3.5: Pseudocódigo do Algoritmo de Subgradiente O Algoritmo de Subgradiente depende então de três sequências: {εk}, {sk} e {dk}. Clara- mente, não são quaisquer sequências que fazem o algoritmo convergir. Vejamos a seguir, quais condições tais sequências devem possuir para que o Algoritmo de Subgradiente convirja [42]. Teorema 3.2.1. Seja f : Rn → R uma função convexa no Rn. Suponhamos que as sequências {εk}, {sk} e {dk} escolhidas no Algoritmo de Subgradiente Básico, Figura 3.5, satisfaçam as condições: +∞∑ k=0 sk = +∞, (3.2) lim k→+∞ εk = 0, (3.3) lim k→+∞ sk‖dk‖2 = 0. (3.4) CAPÍTULO 3. SOLUÇÃO DO PROBLEMA DUAL LAGRANGEANO 44 Então, a sequência {xk} gerada pelo Algoritmo de Subgradiente Básico converge para o ótimo de f , ou seja, lim inf k→+∞ f(xk) = v, onde v = inf x∈Rn f(x). Demonstração. A ideia desta demonstração é usar o argumento da Redução ao Absurdo. Ire- mos supor que a sequência {xk} não converge para v e concluir que a série +∞∑ k=0 sk diverge contradizendo as hipóteses do Teorema. Sabemos da Definição 3.1.10, que: ∂εf(x) = {y ∈ Rn|f(z) ≥ f(x) + 〈y, z − x〉 − ε, ∀z ∈ Rn}, e considere que a atualização da sequência {xk} é dada por: xk+1 = xk + skd k. Assim, para qualquer x ∈ Rn, temos que: ‖xk+1 − x‖2 = ‖(xk − x) + (xk+1 − xk)‖2 = ‖xk − x‖2 + 2〈xk − x, xk+1 − xk〉+ ‖xk+1 − xk‖2 = ‖xk − x‖2 + 2〈xk − x,−skdk〉+ ‖skdk‖2 = ‖xk − x‖2 + 2sk〈dk, x− xk〉+ s2 k‖dk‖2 ≤ ‖xk − x‖2 + 2sk(f(x)− f(xk) + εk) + s2 k‖dk‖2 (3.5) Vamos supor, por absurdo, que lim inf k→+∞ f(xk) > v. Assim, como v = inf x∈Rn f(x), existem x ∈ Rn, δ > 0 e k ∈ N+, tais que f(x) < f(xk)− δ, ∀k ≥ k. (3.6) Como temos (3.3) e (3.4) por hipótese, podemos tomar k suficientemente grande de tal forma que 2εk ≤ δ/2 e sk‖dk‖2 ≤ δ/2, ou seja, sk‖dk‖2 + 2εk ≤ δ, ∀k ≥ k. (3.7) Substituindo as relações (3.6) e (3.7) em (3.5), temos que CAPÍTULO 3. SOLUÇÃO DO PROBLEMA DUAL LAGRANGEANO 45 ‖xk+1 − x‖2 ≤ ‖xk − x‖2 + 2sk(f(x)− f(xk) + εk) + s2 k‖dk‖2 < ‖xk − x‖2 + 2sk(−δ + εk) + s2 k‖dk‖2 = ‖xk − x‖2 − 2skδ + 2skεk + s2 k‖dk‖2 = ‖xk − x‖2 − 2skδ + sk(2εk + sk‖dk‖2) ≤ ‖xk − x‖2 − 2skδ + skδ ≤ ‖xk − x‖2 − skδ, ∀k ≥ k. Assim, para qualquer k ∈ N, com k ≥ k, temos que: skδ ≤ ‖xk − x‖2 − ‖xk+1 − x‖2. Somando de k a k, segue que k∑ i=k skδ ≤ k∑ i=k ‖xi − x‖2 − ‖xi+1 − x‖2 ≤ ‖xk − x‖2 − ‖xk+1 − x‖2 + . . .+ ‖xk − x‖2 − ‖xk+1 − x‖2 ≤ ‖xk − x‖2 − ‖xk+1 − x‖2 < ‖xk − x‖2, ou ainda, k∑ i=k sk < 1 δ ‖xk − x‖2, Dáı, quando k → +∞, a série +∞∑ i=k si converge, contradizendo a hipótese (3.2). Portanto, o Algoritmo de Subgradiente Básico gera uma sequência que converge para o ótimo. O algoritmo de subgradiente mais empregado usa direções normalizadas e εk = 0, ∀k [42]. Assim temos o seguinte teorema: Teorema 3.2.2. Seja f : Rn → R uma função convexa no Rn. Supondo que o problema tenha uma solução e que utilizamos as sequências, εk = 0, sk = βk ‖dk‖ , ∀k (3.8) CAPÍTULO 3. SOLUÇÃO DO PROBLEMA DUAL LAGRANGEANO 46 no Algoritmo de Subgradiente Básico, de tal forma que +∞∑ k=0 βk = +∞, +∞∑ k=0 β2 k < +∞, (3.9) então, a sequência {xk} gerada pelo Algoritmo de Subgradiente Básico converge para uma solução do problema. Demonstração. Seja x a solução do problema. Assim, f(x) ≤ f(xk), ∀k, ou seja, f(x)− f(xk) ≤ 0, ∀k. (3.10) Usando a hipótese de que εk = 0 e βk = sk‖dk‖, ∀k, e tomando x = x em (3.5), temos ‖xk+1 − x‖2 ≤ ‖xk − x‖2 + 2sk(f(x)− f(xk) + εk) + s2 k‖dk‖2 ≤ ‖xk − x‖2 + β2 k . (3.11) Seja k um valor fixo. Dáı, para todo j ≥ k + 1, teremos ‖xj − x‖2 ≤ ‖xj−1 − x‖2 + β2 j−1 ≤ ‖xj−2 − x‖2 + β2 j−1 + β2 j−2 ... ≤ ‖xk − x‖2 + j−1∑ i=k β2 i (3.12) ≤ ‖xk − x‖2 + +∞∑ i=0 β2 i < +∞, ou seja, a sequência {xk} é limitada. Observe que como ∂f(xk) é compacto (Teorema 3.1.2), segue que a sequência {dk} também é limitada, pois dk ∈ ∂f(x), para todo k. Como {βk} ⊂ R+, pois {sk} ⊂ R+ e temos (3.9), então lim k→∞ β2 k = 0, e assim, lim k→∞ βk = 0. Desta forma, lim k→∞ sk‖dk‖2 = lim k→∞ βk ‖dk‖ ‖dk‖2 = lim k→∞ βk‖dk‖ = 0, pois βk → 0 e {dk} é limitada (Teorema 7, Caṕıtulo VI, Lima [50]). CAPÍTULO 3. SOLUÇÃO DO PROBLEMA DUAL LAGRANGEANO 47 Ainda, +∞∑ k=0 sk = +∞, por (3.9) e lim k→+∞ εk = 0, pois εk = 0, ∀k. Portanto, estamos nas hipóteses do Teorema 3.2.2. Logo, lim inf k→+∞ f(xk) = f(x). Como f é cont́ınua, pois é convexa (Teorema 3.1.3), e {xk} é limitada, existe um ponto de acumulação x̂ de {xk} onde f(x) = f(x̂). Isto é, x̂ é uma solução do problema. Tomando x = x̂ em (3.12), temos que ‖xj − x̂‖2 ≤ ‖xk − x̂‖2 + +∞∑ i=k β2 i , (3.13) e tendo (3.9) como hipótese, segue que lim k→+∞ +∞∑ i=k β2 i = 0. Por definição de limite, dado δ > 0, existe k tal que +∞∑ i=k β2 i < δ 2 . Ainda, por x̂ ser ponto de acumulação da sequência {xk} podemos escolher um k de tal forma que ‖xk − x̂‖2 < δ 2 . Logo, por (3.13) segue que para todo δ > 0, existe k tal que ‖xj − x̂‖2 < δ, ∀j ≥ k + 1, ou seja, a sequência {xk} gerada pelo Algoritmo de Subgradiente Básico converge para a solução x̂ do problema. A partir destes resultados, podemos derivar valores para o tamanho do passo sk de tal forma que o Algoritmo de Subgradiente convirja. Tome x um minimizador de f . Então, de (3.5), com εk = 0, ∀k, temos que ‖xk+1 − x‖2 ≤ ‖xk − x‖2 − 2sk(f(xk)− f(x)) + s2 k‖dk‖2, e conclúımos que: ‖xk+1 − x‖2 < ‖xk − x‖2 CAPÍTULO 3. SOLUÇÃO DO PROBLEMA DUAL LAGRANGEANO 48 se 0 < sk < 2(f(xk)− f(x)) ‖dk‖2 . (3.14) Entretanto, como não conhecemos o valor ótimo do problema, não há como escolhermos um comprimento de passo que garanta a propriedade (3.14). Naturalmente, outras condições de tamanho de passo podem garantir a convergência do método. De fato, podemos generalizar a condição (3.14) tomando, por exemplo, um limite inferior LB para f , ao invés de usar o valor f(x). Temos assim um tamanho de passo que não depende de f(x): 0 < sk < 2(f(xk)− LB) ‖dk‖2 . (3.15) Os métodos de subgradientes são muito atrativos pela sua extrema simplicidade, mas geralmente são pouco eficientes pois não possuem uma regra de parada razoável (normalmente é limitado pela quantidade de iterações) e não há garantia de decréscimo da função objetivo em toda iteração. Uma generalização deste método que contorna estes problemas é o Algoritmo de Volume proposto por Barahona e Anbil [21] e que apresentamos na seção 3.3. 3.3 Algoritmo de Volume Apresentamos nesta seção o Algoritmo de Volume que é uma generalização do Algoritmo de Subgradientes. Esse algoritmo contorna os problemas que o algoritmo de subgradientes apre- senta, e produz uma aproximação de solução primal enquanto se resolve o dual. A solução dual é obtida semelhantemente à do algoritmo de subgradientes, e a solução primal é obtida estimando-se o volume formado pelas faces ativas relativas às restrições dualizadas, o que jus- tifica o nome do algoritmo. Antes de apresentarmos o Algoritmo de Volume, faremos uma breve introdução ao método que fundamentou seu desenvolvimento (juntamente com o Método de Subgradiente), que é o Método de Feixes [42], [24]. Considere o seguinte problema de otimização irrestrito: min f(x), x ∈ Rn, (3.16) tal que f : Rn → R é uma função convexa e não diferenciável. O método de feixes baseia-se em aproximar a função objetivo f(x) por funções lineares, ou seja, aproximação linear por partes, ao mesmo tempo agregando um artif́ıcio de estabilização CAPÍTULO 3. SOLUÇÃO DO PROBLEMA DUAL LAGRANGEANO 49 e uma regra de parada confiável. O método consiste em gerar duas sequências de pontos: a sequência {xk}, que são os candidatos, ou seja, os valores iterados do algoritmo, e a sequência {x̂k}, que são os centros de estabilização, ou seja, os pontos que realmente decrescem o valor da função objetivo. A cada iteração k do método, um problema linear por partes ψk(x) : Rn → R é constrúıdo de acordo com (3.17): ψk(x) = max i=0,1,...,k {f(xi) + 〈vi, x− xi〉}, vi ∈ ∂f(xi), ∀i. (3.17) Observe que a sequência {ψk} é uma sequência não-decrescente, pois ψk ≤ ψk+1, ∀k e, ainda, ψk ≤ f . Desta forma, estamos aproximando a função f pela função ψk para cada k, inferiormente. Podemos ver essa propriedade na Figura 3.6. Figura 3.6: Um passo do método de feixes em que foi gerado um ponto xk+1 com valor de f menor de f(xk). Precisaremos da noção de centro de estabilização, cuja definição está na Definição 3.3.1. Definição 3.3.1 (Centro de estabilização). Um iterado xk+1 torna-se um centro de estabi- lização, isto é, x̂k+1 = xk+1 se satisfizer uma condição do tipo Armijo, ou seja, f(x̂k)− f(xk+1) ≥ mδk+1, (3.18) em que δk+1 é denominado decréscimo nominal e m é um parâmetro pertencente ao intervalo (0, 1). Caso o iterado se torne um centro de estabilização, dizemos que foi realizado um passo sério, caso contrário, diremos que o passo foi nulo e x̂k+1 = x̂k. CAPÍTULO 3. SOLUÇÃO DO PROBLEMA DUAL LAGRANGEANO 50 Definição 3.3.2 (Decréscimo nominal). O decréscimo nominal citado na Definição 3.3.1 é calculado da seguinte maneira: δk+1 = f(x̂k)− ( ψk(x k+1) + µk 2 ‖xk+1 − x̂k‖2 ) . (3.19) A sequência de centros de estabilização {x̂1, x̂2, . . . , x̂k} é uma subsequência de {x1, x2, . . . , xk}. A ideia do método de feixes é obter o próximo iterado xk+1 utilizando o problema (3.17). O iterado xk+1 será a solução do seguinte problema, denominado problema estabilizado: min x∈Rn ψk(x) + µk 2 ‖x− x̂k‖2. (3.20) O termo quadrático da função objetivo do problema (3.20) tem o papel de não permitir um deslocamento muito grande do ponto xk+1 em relação ao centro x̂k. O centro de estabilização será mudado apenas quando o passo de x̂k a xk+1 resultar em um decréscimo suficiente da função objetivo f , ou seja, apenas quando o decréscimo nominal for verificado. Com estas considerações, podemos desenvolver um pseudocódigo para o Método de Feixes apresentado na Figura 3.7. Método de Feixes 1. Tome uma tolerância δmin e m ∈ (0, 1); 2. Inicialize x1 um ponto qualquer, k = 1 e δ1 =∞; 3. Calcule v1 ∈ ∂f(x1) e f(x1); 4. Construa o modelo ψ1(x) = f(x1) + 〈v1, x− x1〉 e calcule δ1; 5. Se δk ≤ δmin então PARE; 6. Senão, 7. Resolva o problema (3.20) e tome xk+1 o minimizador; 8. Calcule o decréscimo nominal δk+1; 9. Se f(x̂k)− f(xk+1) ≥ mδk+1 10. Então x̂k+1 = xk+1 e atualize µk+1; 11. Senão, 12. Faça x̂k+1 = xk; 13. Construa o modelo ψk+1 = max i=1,2,...,k {f(xi) + 〈vi, x− xi〉}; 14. Incremente k = k + 1 e volte ao Passo 5. Figura 3.7: Pseudocódigo do Método de Feixes. O parâmetro µk+1 é atualizado resolvendo a seguinte equação [24]: 1 µk+1 = 1 µk + 〈v̂k+1 − v̂k, x̂k+1 − x̂k〉 ‖v̂k+1 − v̂k‖2 , (3.21) CAPÍTULO 3. SOLUÇÃO DO PROBLEMA DUAL LAGRANGEANO 51 em que v̂k ∈ ∂f(xk+1). Observe que no caso de um passo nulo, ou seja, x̂k+1 = x̂k, a fórmula resulta em µk+1 = µk. Os métodos de feixe são métodos robustos, com regras de parada confiáveis, mas demandam um esforço computacional considerável pois tem-se que resolver vários problemas de otimização quadráticos. Uma alternativa à este método é o denominado Algoritmo de Volume, que passaremos a apresentar. Suponhamos que o problema que temos interesse em resolver apresenta a seguinte estrutura: min cx s.a. Ax ≤ b, (3.22) x ∈ Q, em que Q é um poliedro não vazio correspondente às restrições que não complicam a re- solução do problema (3.22), c ∈ Rn, A ∈ Rmxn, b ∈ Rm e as restrições Ax ≤ b são as que complicam o nosso problema. Já vimos na subseção 2.2.2 que a função Lagrangeana associada às restrições Ax ≤ b é dada por: Z(π, x) = cx+ π(Ax− b), (3.23) e o problema Lagrangeano é definido por ZRL(π) = min{Z(π, x) | x ∈ Q}. (3.24) Proposição 3.3.1. [24] Dado xk ∈ arg minZ(π, x), então vk = Axk − b ∈ ∂ZRL(π). Demonstração. Para todo π, temos que ZRL(π) = minZ(π, x) ≤ Z(π, xk) = cxk + π(Axk − b) = cxk + π(Axk − b) + πk(Axk − b)− πk(Axk − b) = cxk + πk(Axk − b) + (π − πk)(Axk − b) = ZRL(πk) + (π − πk)(Axk − b), ou seja, ZRL(π) ≤ ZRL(πk) + (π − πk)(Axk − b), e assim o resultado segue. CAPÍTULO 3. SOLUÇÃO DO PROBLEMA DUAL LAGRANGEANO 52 Assim como vimos no Método de Feixes, o Algoritmo de Volume trabalha com duas sequências: a sequência πk de pontos candidatos, e a sequência π̂k de centros de estabilização. Além disso, as direções v̂k serão dadas por combinações convexas de subgradientes. A estrutura geral do Algoritmo de Volume é apresentada na Figura 3.8. Algoritmo de Volume 1. Sejam 0 < α < 1 um parâmetro, ξpd tolerância de parada primal-dual 2. e ξv tolerância de parada de viabilidade; 3. Tome π0 inicial e resolva o problema (3.24) obtendo x0 e ZRL(π0); 4. Calcule v0 = Ax0 − b; 5. Inicialize x̂1 = x0, v̂1 = v0, π̂1 = π0 e k = 1; 6. Se ‖v̂k‖ < ξv e cx̂k − ZRL(π̂k) ZRL(π̂k) < ξpd então PARE 7. Calcule sk = µ UB − ZRL(πk, xk) ‖ v̂k ‖2 ; 8. Compute πk = π̂k + skv̂k; 9. Resolva o problema (3.24) obtendo xk, ZRL(πk) e vk = Axk − b; 10. Se ZRL(πk) > ZRL(π̂k) então π̂k+1 = πk; 11. Senão, π̂k+1 = π̂k; 11. Atualize x̂k+1 = αxk + (1− α)x̂k e v̂k+1 = αvk + (1− α)v̂k; 12. Incremente k = k + 1 e volte ao Passo 5. Figura 3.8: Pseudocódigo do Algoritmo de Volume Um resultado muito importante é uma relação que temos entre os pontos x̂k e v̂k apresentada na forma da Proposição 3.3.2 a qual será substitúıda no Algoritmo de Volume. Proposição 3.3.2. Sejam {x̂k} e {v̂k} as sequências geradas pelo Algoritmo de Volume. Então, v̂k = Ax̂k − b, em toda iteração k. Demonstração. [24] Nesta demonstração usaremos o Prinćıpio de Indução Finita (PIF) para mostrar o resultado. Quando k = 1, temos pelas definições dadas no Algoritmo de Volume: v̂1 = v0 = Ax0 − b = Ax̂1 − b. Suponhamos que o resultado é válido para uma iteração k ≥ 1, ou seja, que v̂k = Ax̂k − b, e mostremos que o resultado é válido para a iteração k + 1 seguinte. De fato, CAPÍTULO 3. SOLUÇÃO DO PROBLEMA DUAL LAGRANGEANO 53 v̂k+1 = αvk + (1− α)v̂k = α(Axk − b) + (1− α)(Ax̂k − b) = αAx̂k − αb+ Ax̂k − b− αAx̂k + bα = A(αx̂k + x̂k − αx̂k)− b = A(αxk + (1− α)x̂k)− b = Ax̂k+1 − b. Logo, o resultado segue. O parâmetro α usado no Algoritmo de Volume fica fixo por uma quantidade de iterações pré estabelecidas, e vai sendo atualizado de acordo com o algoritmo apresentado na Figura 3.9. A ideia básica é escolher α de modo a atingir a viabilidade primal, ou seja, ter um valor para α de modo que v̂k = Ax̂k − b ≈ 0. Algoritmo para a escolha de α 1. Seja αmax um limite superior para α. 2. Compute αopt = arg min ξ∈R (ξv̂t+1 + (1− ξ)vt+1)2 3. Se αopt < 0, então faça α = αmax/10. 4. Senão faça α = min{αopt, αmax}. Figura 3.9: Algoritmo para a escolha de α Caṕıtulo 4 Relaxações para o PIDS Neste caṕıtulo, iremos apresentar o algoritmos de Subgradiente e de Volume descritos nas seções 4.2.1 e 4.2.2, respectivamente, para resolver os problemas duais Lagrangeano e La- grangeano/Surrogate descritos nas seções 2.2.2 e 2.2.3, respectivamente, particularizados para gerar limitantes para o problema integrado de dimensionamento de lotes e sequenciamento da produção descrito na seção 1.2. Iniciamos o caṕıtulo com uma proposta de algoritmo guloso. A solução gulosa é útil não apenas para fornecer uma solução fact́ıvel mas também nos Algoritmos de Subgradiente e de Volume fornecendo limitantes primais. Considere as formulações para o PIDS apresentadas na seção 1.2. As relaxações que apre- sentamos nas seções 4.2 e 4.3 são baseadas nos modelos MT1S1MP e MCF1S1MP, os quais consideram de forma expĺıcita a variável de preparo wjt. A escolha destes modelos, como veremos no Caṕıtulo 5, é por sua melhor performance em relação aos modelos MTZ1S1M e MCF1S1M, respetivamente. 4.1 Uma heuŕıstica gulosa para o PIDS Uma maneira simples de obtermos limitantes superiores (no caso de problemas de minimização) são as heuŕısticas gulosas. Desenvolvemos uma heuŕıstica gulosa para o PIDS com a seguinte ideia: • Fase I: Ordenação dos itens em ordem não-decrescente de custo de troca; • Fase II: Resolvemos o problema de dimensionamento de lotes (PDL), descrito por (4.1)- (4.7): 54 CAPÍTULO 4. RELAXAÇÕES PARA O PIDS 55 Min Z = ∑ j∈J ∑ t∈T (hjI + jt + gjI − jt) + ∑ t∈T ∑ i∈J ∑ j∈J j 6=i sijzijt (4.1) sujeito a: I+ j(t−1) + I−jt + xjt − I+ jt − I−j(t−1) = djt, ∀j,∀t (4.2)∑ j∈J pjxjt + ∑ i∈J ∑ j∈J j 6=i bijzijt ≤ Ct, ∀t (4.3) xjt ≤ Ct pj  J∑ i=i0 i6=j zijt  , ∀j,∀t (4.4) xjt, I + jt , I − jt ≥ 0, zijt = 0/1, ∀i, j,∀t (4.5) I+ j0 = 0, ∀j (4.6) I−j0 = 0; ∀j (4.7) • Por fim, verificamos se o sequenciamento constrúıdo na Fase I é fact́ıvel. Se não for, factibilizamos a solução mantendo a ordenação obtida na Fase I e reduzindo a produção com a consequente introdução de atrasos. O pseudocódigo para a heuŕıstica é apresentado na Figura 4.1. CAPÍTULO 4. RELAXAÇÕES PARA O PIDS 56 4.2 Relaxação Lagrangeana para o PIDS Nesta seção iremos apresentar o subproblema Lagrangeano para o problema PIDS e os métodos de resolução desenvolvidos para resolvê-lo. Considere o problema PIDS apresentado na seção 1.2. Dualizando as restrições (1.3) com o multiplicador π1 ∈ RT + e (1.17) com o multiplicador π2 ∈ RJT + , temos o seguinte subproblema Lagrangeano (4.8)-(4.18): Min L(x, I+, I−, z, π1, π2) = ∑ j∈J ∑ t∈T (hjI + jt + gjI − jt) + ∑ t∈T ∑ i∈J ∑ j∈J j 6=i sijzijt + ∑ t∈T π1 t ∑ j∈J pjxjt + ∑ i∈J ∑ j∈J j 6=i bijzijt − Ct + ∑ j∈J ∑ t∈T π2 jt wjt − J∑ i=i0 i6=j zijt  (4.8) sujeito a: I+ j(t−1) + I−jt + xjt − I+ jt − I−j(t−1) = djt, ∀j,∀t (4.9) xjt ≤ Ct wjt pj , ∀j,∀t (4.10) ∑ j∈J zi0jt ≥ J∑ i=i0 zikt, ∀k ∈ J ; k 6= i, ∀t (4.11) J∑ i=i0 i6=k zikt = J∑ j=i0 j 6=k zkjt, ∀k ∈ J, ∀t (4.12) J∑ j=i0 j 6=i zijt ≤ 1, ∀i = i0, 1, . . . , J, ∀t (4.13) xjt, I + jt , I − jt ≥ 0, zijt = 0/1, ∀i,∀j,∀t (4.14) Restrições de eliminação de subrotas (MTZ ou MCF) (4.15) I+ j0 = 0, ∀j (4.16) I−j0 = 0, ∀j (4.17) wjt = 0/1, ∀j,∀t. (4.18) O interessante na dualização das restrições (1.3) e (1.17) é que o subproblema resultante pode ser decomposto em dois: o problema de dimensionamento de lotes sem capacidade e o problema de sequenciamento. O subproblema Lagrangeano pode então ser resolvido com a resolução destes dois subproblemas independentes. Em nosso estudo utilizamos o software CPLEX para resolução dos subproblemas. CAPÍTULO 4. RELAXAÇÕES PARA O PIDS 57 Heuŕıstica Gulosa 1. Fase 1 - Ordenaç~ao dos itens: 2. Passo 1: Tome i0 como item inicial e i1 o item subsequente tal 3. que si0i1 = min{sij,∀i, j}, e k = 2. Faça zi0i1t = 1, ∀t; 4. Passo 2: Enquanto k < J acrescente à sequência o item ik tal 5. que sik−1ik = min{sikj,∀j} e ik 6= i0, i1, . . . , ik−1, e 6. faça zik−1ikt = 1, ∀t; 7. Fase 2 - Dimensionar e factibilizar: 8. Passo 1: Resolva o problema PDL: (4.1)-(4.7) ; 9. Passo 2: Seja zijt,∀i, j, t a solução da Fase 1 e xjt, I + jt 10. e I−jt ,∀i, j, t a solução do dimensionamento de lotes 11. obtida no Passo 1; 12. Passo 3: Para cada peŕıodo t, faça: 13. Tome at = ∑ j∈J pjxjt + ∑ i∈J ∑ j∈J j 6=i bijzijt − Ct. 14. Se at ≤ 0 então passe para o próximo peŕıoto t. 15. Senão, seja j1, j2, . . . , jJ uma ordenação nos itens de 16. acordo com seus custos de atraso. 17. Tome k = 1. 18. Enquanto at 6= 0, faça: 19. Se xjkt = 0 então k = k + 1. 20. Senão, 21. Se at − xjkt ≥ 0, então 22. at = at − xjkt, 23. xjkt = 0, 24. zmjkt = zjknt = 0, onde m é o item produzido 25. imediatamente antes de jk e n imediatamente depois, 26. I−jkt = djkt − xjkt + I−jkt−1. 27. Senão, 28. xjkt = xjkt − at, 29. I−jkt = djkt − xjkt + I−jkt−1, 30. at = 0. 31. Para todo i = 1, . . . , J se xit − dit = 0 e I−it−1 > 0, 32. então I−it = I−it−1. Figura 4.1: Pseudocódigo para a heuŕıstica gulosa CAPÍTULO 4. RELAXAÇÕES PARA O PIDS 58 4.2.1 Algoritmo de Subgradiente para resolução do Dual Lagrange- ano Apresentamos na Figura 4.2 o pseudocódigo do algoritmo de subgradiente proposto para resolver o problema dual Lagrangeano associado à formulação MTZ1S1MP. Para obter o algoritmo associado à formulação MCF1S1MP basta substituir o problema a ser resolvido no Passo 2 pelo problema (1.1)− (1.7), (1.11), (1.12) e (1.13)− (1.16), e utilizar as restrições MCF no problema (4.8)− (4.18). Denotaremos o multiplicador π1 t na iteração k por π1,k t e o multiplicador π2 j,t na iteração k por π2,k j,t . Algoritmo de Subgradiente para o problema MTZ1S1MP 1. Faça k = 0, π1,0 t = 0, π2,0 it = 0,∀i, t, e max it um limitante para a quantidade de iterações. 2. Seja UB um limite superior para o problema (1.1)− (1.12). 3. Resolva o subproblema (4.8)− (4.18) (MTZ) com π1 t = π1,k t , π2 it = π2,k it ∀i, t e tome xkjt, z k ijt e wkjt os minimizadores. 4. Calcule v1,k t = ∑ j∈J pjxjt + ∑ i∈J ∑ j∈J j 6=i bijzijt − Ct,∀t, 5. v2,k jt = wjt − J∑ i=i0 i6=j zijt,∀j, t, 6. sk = µ(UB − L(xk, I+k, I− k , zk, π1,k, π2,k)) ‖vk‖2 , onde µ ∈ (0, 2). 7. Atualize π1,k+1 t = max(π1,k t + skv1,k t , 0),∀t, 8. π2,k+1 it = π2,k it + skv2,k it ,∀t, 9. k = k + 1. 10. Se max it < k então PARE, senão volte ao Passo 3. Figura 4.2: Pseudocódigo do Algoritmo de Subgradiente para a formulação MTZ1S1MP - Dual Lagrangeano. 4.2.2 Algoritmo de Volume para resolução do Dual Lagrangeano Apresentamos na Figura 4.3 o pseudocódigo do algoritmo de volume proposto para resolver o problema dual Lagrangeano associado à formulação MTZ1S1MP. Denotaremos o multiplicador π1 t na iteração k por π1,k t e o multiplicador π2 j,t na iteração k por π2,k j,t . Os centros de estabilizações CAPÍTULO 4. RELAXAÇÕES PARA O PIDS 59 são denotados por π̂1,k e π̂2,k, onde k só é atualizado quando há uma melhoria no valor da função Lagrangeana. Algoritmo de Volume para o modelo MTZ1S1MP - Dual Lagrangeano 1. Passo 0 - Ińıcio: 2. Sejam 3. - π1,0 e π2,0 vetores de multiplicadores de Lagrange; 4. - max iter = 2500; 5. - α = 0.5; 6. - zLB o limite inferior para o problema dual Lagrangeano (1.1)− (1.12); 7. - ξpd = 0.001; 8. - ξv = 0.001. 9. - Resolva o subproblema Lagrangeano (4.8)− (4.18) (MTZ) com π1 = π1,0 10. e π2 = π2,0, e tome I+ 0 , I− 0 , x 0, w 0 e z 0 as soluções ótimas, 11. e θ0 = L(I+ 0 , I− 0 , x 0, w 0, z 0) o valor ótimo. 12. - Calcule 13. v1,0 t = ∑ j∈J pjx 0 jt + ∑ i∈J ∑ j∈J j 6=i bijz 0 ijt − Ct, t = 1, 2, . . . , T , 14. v2,0 jt = w 0 jt − J∑ i=i0 i6=j z 0 ijt, j = 1, 2, . . . , J, t = 1, 2, . . . , T , 15. - Inicialize zLB = θ0, Î+ 0 = I+ 0 , Î− 0 = I− 0 , x̂0 = x0, ŵ0 = w0 16. e ẑ0 = z0, v̂1,0 = v1,0, v̂2,0 = v2,0, π̂1,0 = π1,0, π̂2,0 = π2,0, k = 0 e ` = 0. 17. Passo 1: 18. - Calcule 19. s` = µ UB − θ` T∑ t=1 (v1,0 t )2 + J∑ j=1 T∑ t=1 (v2,0 jt )2 , 20. onde µ ∈ (0, 2) e UB é um limite superior para o problema (1.1)− (1.12). 21. - Tome 22. π1,`+1 = π̂1,k + s`v̂ 1,`, 23. π2,`+1 = π̂2,k + s`v̂ 2,`. 24. Passo 2: CAPÍTULO 4. RELAXAÇÕES PARA O PIDS 60 25. - Resolva o subproblema Lagrangeano (4.8)− (4.18) (MTZ) com π1 = π1,`+1 26. e π2 = π2,`+1, e tome I+ `+1 , I− `+1 , x`+1, w`+1 e z`+1 as soluções 27. ótimas, e θ` = L(I+ `+1 , I− `+1 , x`+1, w`+1, z`+1) o valor ótimo. 28. Passo 3: 29. Atualize as variáveis primais: 30. x̂`+1 = αx`+1 + (1− α)x̂`, 31. ŵ`+1 = αw`+1 + (1− α)ŵ`, 32. ẑ`+1 = αz`+1 + (1− α)ẑ`, 33. Î+ `+1 = αI+ `+1 + (1− α)Î+ ` , 34. Î− `+1 = αI− `+1 + (1− α)Î− ` , 35. e o subgradiente 36. v1,` t = ∑ j∈J pjx ` jt + ∑ i∈J ∑ j∈J j 6=i bijz ` ijt − Ct, t = 1, 2, . . . , T , 37. v2,` jt = w ` jt − J∑ i=i0 i6=j z ` ijt, j = 1, 2, . . . , J, t = 1, 2, . . . , T , 38. Passo 4: 39. - Verifique se θ`+1 > zLB. 40. - Se for falso, declare uma iteração vermelha. 41. - Se for verdadeiro, calcule dir = T∑ t=1 v̂1,`+1 t v1,`+1 t + J∑ j=1 T∑ t=1 v̂1,`+1 jt v1,`+1 jt : 42. Se dir < 0 declare uma iteração amarela; 43. Se dir ≥ 0 declare uma iteração verde e atualize: 44. - zLB = θ`+1, 45. - k = k + 1, 46. - π̂1,k = π1,`+1, 47. - π̂2,k = π2,`+1, 48. Passo 5 - Testes de parada: 49. - 1. Se 50. ∣∣∣∣∣∣∣ ∑ j∈J ∑ t∈T (hj Î + jt `+1 + gj Î − jt `+1 ) + ∑ t∈T ∑ i∈J ∑ j∈J j 6=i sij ẑ `+1 ijt − zLB ∣∣∣∣∣∣∣ | zLB | < ξpd, CAPÍTULO 4. RELAXAÇÕES PARA O PIDS 61 51. e 52. √√√√ T∑ t=1 (v1,`+1 t )2 + J∑ j=1 T∑ t=1 (v2,`+1 jt )2 T (J + 1) < ξv, 53. então PARE. 54. - 2. Se 55. UB − zLB < 1, 56. então PARE. 57. - 3. Se 58. ` > max iter, 59. então PARE. 60. Senão, atualize ` = `+ 1 e retorne ao Passo 1. Figura 4.3: Pseudocódigo do Algoritmo de Volume para a formulação MTZ1S1MP - Dual Lagrangeano. Neste algoritmo, utilizamos uma atualização no fator de correção µ, da seguinte maneira: • µ = 2.1µ a cada iteração verde; • µ = 1.8µ a cada 100 iterações amarelas; • µ = 0.6µ a cada 20 iterações vermelhas; Os valores de max iter e α foram dados empiricamente, assim como a quantidade de iterações verdes, amrelas e vermelhas. Para obter o algoritmo associado à formulação MCF1S1MP basta substituir o problema a ser resolvido no Passo 0 para obtenção do zLB pelo problema (1.1) − (1.7), (1.11), (1.12) e (1.13)− (1.16), e utilizar as restrições MCF no problema (4.8)− (4.18) (passos 0 e 2). 4.3 Relaxação Lagrangeana/Surrogate para o PIDS Nesta seção iremos apresentar o subproblema Lagrangeano/Surrogate para o problema PIDS e o método de resolução desenvolvido para resolvê-lo. CAPÍTULO 4. RELAXAÇÕES PARA O PIDS 62 Dualizando as restrições (1.17) com o multiplicador Surrogate π2 obtemos a restrição Sur- rogate ∑ j∈J ∑ t∈T π2 jt wjt − J∑ i=i0 i6=j zijt  = 0. (4.19) Dualizado a restrição Surrogate (4.19) com o multiplicador de Lagrange t, e as restrições (1.3) com o multiplicador π1, obtemos o subproblema Lagrangeano/Surrogate (4.20)-(4.30): Min LS(x, I+, I−, z, π1, π2) = ∑ j∈J ∑ t∈T (h