Pesquisa Operacional II - Métodos Exatos

Pesquisa Operacional II Prof Dr Allexandre Fortes Departamento de Engenharia Mecânica e Produção Universidade Federal de São João del Rei 20 de abril de 2023 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 1 43 Conteúdo 1 Introdução 2 Branchandbound 3 Geração de cortes 4 Geração de colunas 5 Métodos exatos combinados 6 Dúvidas Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 2 43 Problemas de Programação linear Hipóteses Proporcionalidade a quantidade consumida de recurso por uma atividade é proporcional ao nível da mesma assim como o custo associado Não negatividade deve ser sempre possível desenvolver dada atividade em qualquer nível não negativo e qualquer proporção de um dado recurso deve sempre poder ser utilizado Aditividade O custo é a soma dos custos das atividades executadas Separabilidade Os custos e consumos individuais podem ser identificados para cada ativi dade Divisibilidade Qualquer variável de decisão pode assumir qualquer valor proporcional Certeza Os parâmetros fornecidos no início do modelo são os mesmos durante todo o processo de solução Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 3 43 Problemas de Programação linear e inteira Características Hipótese da Divisibilidade nula x Z PPL Inteira eou Binária eou Mista Mixed Integer Programming MIP Aplicações Planejamento Produção Estoque Transporte e Roteamento Localização e Distribuição Como resolvêlos de maneira exata Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 4 43 Problemas de Programação linear e inteira Principais algoritmos exatos Tem certa inteligência e em comum eles têm a implementação do método Simplex Revisado e do Método de Pontos Interiores Primal Dual Branchandbound ou Ramificar e limitar 1960 Cortes Cutting Cortes de Gomory 1958 Inteiros primais e duais Combinatórios Interseção Método de decomposição de Benders Geração de colunas Column generation 1961 Decomposição de DantzigWolfe 1960 Branchandcut Branchandprice Branchpriceandcut ou Branchcutandprice etc Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 5 43 Branchandbound Características Land e Doig 1960 Ramificar e Podar ou Dividir e Limitar Procedimento de Enumeração Desvantagem Enumeração é finita mas problemas grandes são intratáveis Vantagem Confiabilidade Princípio Dividir para conquistar Etapas Ramificação Branch Poda Bound Inviabiliade Otimalidade Avaliação LAND A H DOIG A G 1960 An automatic method of solving discrete programming problems Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 6 43 Branchandbound Fatores principais Resolver o problema relaxado PR ao invés dele original inteiro P P mingxx ˆΓ Rn PR minfxx Γ Rn Tal que ˆΓ Γ e fx gx x ˆΓ logo P é um limitador de PR PR deve ser fácil de resolveruma vez que será resolvido muitas vezes Além disso também deve ser o mais justo possível ou seja uma aproximação próxima de P tanto no espaço de soluções quando no valor da fo Divisão Branch Cria novos problemas que são limitadores do original Seleção Escolher eficientemente quais novos problemas serão tratados que fará com que a lacuna gap entre as soluções diminua mais rapidamente Relaxação Seja MIP a relaxação de MIP e MIP mincT xAx b x 0 tal que xAx b x 0 xj Z j I xAx b x 0 índices das variáveis inteiras Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 7 43 Branchandbound Etapas do algoritmo BB Todos os solvers atuais usam al guma variação do algoritmo ori ginal de Land e Doig 1960 para resolver um MIP que é dividido da seguinte maneira 1 Inicialização 2 Seleção do problema 3 Divisão branching 4 Teste de otimalidade bound 1 Inicialização se x viável então zLS cT x senão zLS resolva MIP se MIP é inviável então MIP também é inviável PARE senão se MIP é viável e xj I é inteira então PARE pois a solução de MIP é solução de MIP senão adicione o problema MIP à lista de candidatos 2 Seleção do problema selecione um problema candidato PC para se paração da lista de de candidatos Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 8 43 Branchandbound Etapas do algoritmo BB Todos os solvers atuais usam al guma variação do algoritmo ori ginal de Land e Doig 1960 para resolver um MIP que é dividido da seguinte maneira 1 Inicialização 2 Seleção do problema 3 Divisão branching 4 Teste de otimalidade bound 1 Inicialização se x viável então zLS cT x senão zLS resolva MIP se MIP é inviável então MIP também é inviável PARE senão se MIP é viável e xj I é inteira então PARE pois a solução de MIP é solução de MIP senão adicione o problema MIP à lista de candidatos 2 Seleção do problema selecione um problema candidato PC para se paração da lista de de candidatos Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 8 43 Branchandbound Etapas do algoritmo BB Todos os solvers atuais usam al guma variação do algoritmo ori ginal de Land e Doig 1960 para resolver um MIP que é dividido da seguinte maneira 1 Inicialização 2 Seleção do problema 3 Divisão branching 4 Teste de otimalidade bound 1 Inicialização se x viável então zLS cT x senão zLS resolva MIP se MIP é inviável então MIP também é inviável PARE senão se MIP é viável e xj I é inteira então PARE pois a solução de MIP é solução de MIP senão adicione o problema MIP à lista de candidatos 2 Seleção do problema selecione um problema candidato PC para se paração da lista de de candidatos Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 8 43 Branchandbound 3 Divisão Branching selecione uma variável fracionária xk nk fk de PC gere dois novos problemas um com uma restrição xk nk 1 e outro com xk nk resolva os dois novos problemas Se o novo problema resolvido for inviável o descarte Se todas as variáveis xj j I que foram relaxadas são inteiras atualize a melhor solução corrente como sendo este problema zLSx e o descarte de qualquer separação futura Se a relaxação tem pelo menos uma variável fracionária e o valor da função objetivo é menor do que zLS adicione este problema a lista de candidatos 4 Teste de Otimalidade Bound apague da lista de candidatos qualquer problema te tenha valor de função objetivo pior do que zLS se a lista não estiver vazia volte a Etapa 2 senão se a lista está vazia e zLS então o MIP é inviável senão se a lista está vazia então zLS é o valor ótimo do MIP Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 9 43 Branchandbound 3 Divisão Branching selecione uma variável fracionária xk nk fk de PC gere dois novos problemas um com uma restrição xk nk 1 e outro com xk nk resolva os dois novos problemas Se o novo problema resolvido for inviável o descarte Se todas as variáveis xj j I que foram relaxadas são inteiras atualize a melhor solução corrente como sendo este problema zLSx e o descarte de qualquer separação futura Se a relaxação tem pelo menos uma variável fracionária e o valor da função objetivo é menor do que zLS adicione este problema a lista de candidatos 4 Teste de Otimalidade Bound apague da lista de candidatos qualquer problema te tenha valor de função objetivo pior do que zLS se a lista não estiver vazia volte a Etapa 2 senão se a lista está vazia e zLS então o MIP é inviável senão se a lista está vazia então zLS é o valor ótimo do MIP Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 9 43 Branchandbound Obtenção de limites e gerenciamento da árvore3 Técnicas de desenvolvimento da árvore de enumeração escolha do problema Busca em profundidade Busca em largura Variantes híbridas Técnicas de formação da árvore escolha da variável de separação Variante de Land Doig 1960 Variante de Dakin 1965 Variante de Spielberg Lemke Spielberg 1969 Spielberg 1979 Método das penalidades Beale Small 1965 Método de Taha 1971 Estratégias Dinâmicas Glover Tangedahl 1976 Outras variantes Técnicas complementares para obtenção dos limites Relaxação Lagrangeana Algoritmos heurísticos com uso de metaheurísticas Cortes Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 10 43 Branchandbound Problema Relaxado P0 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 x2 0 solução x1 0727273 e x2 286363 fx 3590903 P0 P1 P2 P3 P4 P5 P6 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 11 43 Branchandbound P1 Branching em x1 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 0 x1 x2 0 solução x1 00 e x2 25 fx 25 P2 Branching em x1 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x1 x2 0 solução x1 10 e x2 225 fx 325 P0 P1 P1 P2 P3 P4 P5 P6 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 12 43 Branchandbound P1 Branching em x1 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 0 x1 x2 0 solução x1 00 e x2 25 fx 25 P2 Branching em x1 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x1 x2 0 solução x1 10 e x2 225 fx 325 P0 P1 P1 P2 P3 P4 P5 P6 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 12 43 Branchandbound P1 Branching em x1 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 0 x1 x2 0 solução x1 00 e x2 25 fx 25 P2 Branching em x1 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x1 x2 0 solução x1 10 e x2 225 fx 325 P0 P1 P1 P2 P3 P4 P5 P6 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 12 43 Branchandbound P3 Branching em x2 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 2 x1 x2 0 solução x1 1111111 e x2 20 fx 3111111 P4 Branching em x2 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 3 x1 x2 0 solução Inviável P0 P1 P2 P3 P4 P5 P6 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 13 43 Branchandbound P3 Branching em x2 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 2 x1 x2 0 solução x1 1111111 e x2 20 fx 3111111 P4 Branching em x2 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 3 x1 x2 0 solução Inviável P0 P1 P2 P3 P4 P5 P6 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 13 43 Branchandbound P3 Branching em x2 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 2 x1 x2 0 solução x1 1111111 e x2 20 fx 3111111 P4 Branching em x2 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 3 x1 x2 0 solução Inviável P0 P1 P2 P3 P4 P5 P6 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 13 43 Branchandbound P5 Branching em x1 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 2 x1 1 x1 x2 0 solução x1 10 e x2 20 fx 30 P6 Branching em x2 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 2 x2 2 x1 x2 0 solução x1 1111111 e x2 20 fx 3111111 P0 P1 P2 P3 P4 P5 P6 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 14 43 Branchandbound P5 Branching em x1 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 2 x1 1 x1 x2 0 solução x1 10 e x2 20 fx 30 P6 Branching em x2 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 2 x2 2 x1 x2 0 solução x1 1111111 e x2 20 fx 3111111 P0 P1 P2 P3 P4 P5 P6 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 14 43 Branchandbound P5 Branching em x1 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 2 x1 1 x1 x2 0 solução x1 10 e x2 20 fx 30 P6 Branching em x2 min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 2 x2 2 x1 x2 0 solução x1 1111111 e x2 20 fx 3111111 P0 P1 P2 P3 P4 P5 P6 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 14 43 Branchandbound P5 Otimalidade min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 2 x1 1 x1 x2 0 solução x1 10 e x2 20 fx 30 P0 P1 P2 P3 P4 P5 P6 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 15 43 Branchandbound P5 Otimalidade min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 2 x1 1 x1 x2 0 solução x1 10 e x2 20 fx 30 Ilustração x1 x2 0 1 2 3 4 1 2 3 4 0 P1 1 P2 3 P4 2 P3 x Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 16 43 Branchandbound P5 Otimalidade min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 2 x1 1 x1 x2 0 solução x1 10 e x2 20 fx 30 Ilustração x1 x2 0 1 2 3 4 1 2 3 4 0 P1 1 P2 3 P4 2 P3 x Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 16 43 Branchandbound P5 Otimalidade min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 2 x1 1 x1 x2 0 solução x1 10 e x2 20 fx 30 Ilustração x1 x2 0 1 2 3 4 1 2 3 4 0 P1 1 P2 3 P4 2 P3 x Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 16 43 Branchandbound P5 Otimalidade min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 2 x1 1 x1 x2 0 solução x1 10 e x2 20 fx 30 Ilustração x1 x2 0 1 2 3 4 1 2 3 4 0 P1 1 P2 3 P4 2 P3 x Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 16 43 Branchandbound P5 Otimalidade min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 2 x1 1 x1 x2 0 solução x1 10 e x2 20 fx 30 Ilustração x1 x2 0 1 2 3 4 1 2 3 4 0 P1 1 P2 3 P4 2 P3 x Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 16 43 Branchandbound P5 Otimalidade min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 2 x1 1 x1 x2 0 solução x1 10 e x2 20 fx 30 Ilustração x1 x2 0 1 2 3 4 1 2 3 4 0 P1 1 P2 3 P4 2 P3 x Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 16 43 Branchandbound P5 Otimalidade min fx x1 x2 x1 2x2 5 9x1 4x2 18 4x1 2x2 4 x1 1 x2 2 x1 1 x1 x2 0 solução x1 10 e x2 20 fx 30 Ilustração x1 x2 0 1 2 3 4 1 2 3 4 0 P1 1 P2 3 P4 2 P3 x Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 16 43 Branchandbound Exemplo GLPK Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 17 43 Branchandbound Exercício 1 Para o Problema das Indústrias Reddy Mikks faça um BB na variável x2 do problema Sendo a solução relaxada x1 3 x2 1 5 e fx 21 e o problema original conforma abaixo max z 5x1 4x2 sa 6x1 4x2 24 x1 2x2 6 xj 0 j 1 2 Responda a É necessário realizar uma nova iteração do Algoritmo de BB b Qual dos novos nós teria prioridade Por quê c Qual variável seria analisada Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 18 43 Geração de cortes Motivação inicial Dado um PPLI após resolvido pelo SIMPLEX não apresenta algumas ou todas das variáveis xj I N com valor nãointeiro O que fazer Características Planos de corte Cutting planes ou Método de Separação Ralph Gomory 1958 Removerá uma porção do espaço de soluções que contém o ótimo atual Aproximar da solução ótima inteira Os cortes devem se relacionar com a formulação Desvantagem Não é totalmente confiável Vantagem Normalmente são rápidos PO1 Análise de sensibilidade Adição de restrição GOMORY R 1958 Outline of an algorithm for integer solutions to linear programs Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 19 43 Geração de cortes Motivação inicial Dado um PPLI após resolvido pelo SIMPLEX não apresenta algumas ou todas das variáveis xj I N com valor nãointeiro O que fazer Características Planos de corte Cutting planes ou Método de Separação Ralph Gomory 1958 Removerá uma porção do espaço de soluções que contém o ótimo atual Aproximar da solução ótima inteira Os cortes devem se relacionar com a formulação Desvantagem Não é totalmente confiável Vantagem Normalmente são rápidos PO1 Análise de sensibilidade Adição de restrição GOMORY R 1958 Outline of an algorithm for integer solutions to linear programs Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 19 43 Geração de cortes Definição formal Seja um Poliedro P Ax b x 0 Temse então que π π0 é uma desigualdade válida se e somente se P está contido no semiespaço x 0 πTx π0 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 20 43 Geração de cortes Definição formal Seja um Poliedro P Ax b x 0 Temse então que π π0 é uma desigualdade válida se e somente se P está contido no semiespaço x 0 πTx π0 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 20 43 Geração de cortes Definição formal Seja um Poliedro P Ax b x 0 Temse então que π π0 é uma desigualdade válida se e somente se P está contido no semiespaço x 0 πTx π0 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 20 43 Geração de cortes Ilustração Problema original Cortes Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 21 43 Geração de cortes Ilustração Problema original Cortes Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 21 43 Geração de cortes Ilustração Problema original Cortes Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 21 43 Geração de cortes Ilustração Problema original Cortes Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 21 43 Geração de cortes Ilustração Problema original Cortes Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 21 43 Geração de cortes Cortes de Gomory 1958 A proposta é baseada em adicionar iterativamente cortes que melhorem os limites da solução atual Estes cortes são um conjunto refinado e viável gerado por meio de inequações lineares Reduzindo a solução de problemas inteiros à sucessão de problemas lineares Estes cortes também chamados de cortes fracionários São definidos sobre as linhas do quadro SIMPLEX em que o o valor da variável que a ocupa seja fracionário mas por definição esta variável deveria ser inteira A ideia então é diminuir o valor das variáveis de folga e assim aproximar o valor das variáveis originais de termos inteiros Estes cortes foram melhorados e apresentados por Chvátal 1973 Todo solver comercial faz uso deles CHVÁTAL V 1973 Edmonds polytopes and weakly Hamiltonian graphs Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 22 43 Geração de cortes Cortes de Gomory 1958 Receita 1 Expresse cada um dos coeficientes da restrição como a soma de um número inteiro I e uma fração nãonegativa f 2 Aloque todos os termos direitos para o lado esquerdo da equação não se esqueça de alterar os sinais 3 Elimine todos os inteiros e mude para Exemplo 1x1 3x2 5 4s1 0s2 1 3 I Coeficiente Inteiro I parte fracionária sempre nula i positivo 3 3 0 1 ii negativo 1 1 0 1 iii nulo 0 0 0 1 II Coeficiente Fracionário f Parte inteira parte fracionária i positivo I f 1 3 0 1 3 ii negativo f f f 5 4 5 4 5 4 5 4 2 5 4 2 2 3 4 Resultado 0x1 0x2 3 4s1 0s2 1 3 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 23 43 Geração de cortes Cortes de Gomory 1958 Receita 1 Expresse cada um dos coeficientes da restrição como a soma de um número inteiro I e uma fração nãonegativa f 2 Aloque todos os termos direitos para o lado esquerdo da equação não se esqueça de alterar os sinais 3 Elimine todos os inteiros e mude para Exemplo 1x1 3x2 5 4s1 0s2 1 3 I Coeficiente Inteiro I parte fracionária sempre nula i positivo 3 3 0 1 ii negativo 1 1 0 1 iii nulo 0 0 0 1 II Coeficiente Fracionário f Parte inteira parte fracionária i positivo I f 1 3 0 1 3 ii negativo f f f 5 4 5 4 5 4 5 4 2 5 4 2 2 3 4 Resultado 0x1 0x2 3 4s1 0s2 1 3 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 23 43 Geração de cortes Cortes de Gomory 1958 Receita 1 Expresse cada um dos coeficientes da restrição como a soma de um número inteiro I e uma fração nãonegativa f 2 Aloque todos os termos direitos para o lado esquerdo da equação não se esqueça de alterar os sinais 3 Elimine todos os inteiros e mude para Exemplo 1x1 3x2 5 4s1 0s2 1 3 I Coeficiente Inteiro I parte fracionária sempre nula i positivo 3 3 0 1 ii negativo 1 1 0 1 iii nulo 0 0 0 1 II Coeficiente Fracionário f Parte inteira parte fracionária i positivo I f 1 3 0 1 3 ii negativo f f f 5 4 5 4 5 4 5 4 2 5 4 2 2 3 4 Resultado 0x1 0x2 3 4s1 0s2 1 3 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 23 43 Geração de cortes Cortes de Gomory 1958 Receita 1 Expresse cada um dos coeficientes da restrição como a soma de um número inteiro I e uma fração nãonegativa f 2 Aloque todos os termos direitos para o lado esquerdo da equação não se esqueça de alterar os sinais 3 Elimine todos os inteiros e mude para Exemplo 1x1 3x2 5 4s1 0s2 1 3 I Coeficiente Inteiro I parte fracionária sempre nula i positivo 3 3 0 1 ii negativo 1 1 0 1 iii nulo 0 0 0 1 II Coeficiente Fracionário f Parte inteira parte fracionária i positivo I f 1 3 0 1 3 ii negativo f f f 5 4 5 4 5 4 5 4 2 5 4 2 2 3 4 Resultado 0x1 0x2 3 4s1 0s2 1 3 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 23 43 Geração de cortes Cortes de Gomory 1958 Exemplo max fx 5x1 8x2 x1 x2 6 5x1 9x2 45 x1 x2 Z max fx 5x1 8x2 0s1 0s2 x1 x2 s1 0s2 6 5x1 9x2 0s1 s2 45 x1 x2 s1 s2 Z VB x1 x2 s1 s2 sol x1 1 0 225 025 225 x2 0 1 125 025 375 max 0 0 125 075 fx 4125 Por exemplo escolhendo a Linha 2 do quadro SIMPLEX Uma nova restrição resultante seria 0x1 0x2 3 4 s1 1 4 s2 3 4 max fx 5x1 8x2 0s1 0s2 x1 x2 s1 0s2 6 5x1 9x2 0s1 s2 45 0x1 0x2 0 75s1 0 25s2 0 75 x1 x2 s1 s2 Z Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 24 43 Geração de cortes Cortes de Gomory 1958 Exemplo max fx 5x1 8x2 x1 x2 6 5x1 9x2 45 x1 x2 Z max fx 5x1 8x2 0s1 0s2 x1 x2 s1 0s2 6 5x1 9x2 0s1 s2 45 x1 x2 s1 s2 Z VB x1 x2 s1 s2 sol x1 1 0 225 025 225 x2 0 1 125 025 375 max 0 0 125 075 fx 4125 Por exemplo escolhendo a Linha 2 do quadro SIMPLEX Uma nova restrição resultante seria 0x1 0x2 3 4 s1 1 4 s2 3 4 max fx 5x1 8x2 0s1 0s2 x1 x2 s1 0s2 6 5x1 9x2 0s1 s2 45 0x1 0x2 0 75s1 0 25s2 0 75 x1 x2 s1 s2 Z Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 24 43 Geração de cortes Cortes de Gomory 1958 Exemplo x1 x2 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 x x Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 25 43 Geração de cortes Cortes de Gomory 1958 Exemplo x1 x2 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 x x Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 25 43 Geração de cortes Cortes de Gomory 1958 Exemplo x1 x2 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 x x Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 25 43 Geração de cortes Cortes de Gomory 1958 Exemplo x1 x2 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 x x Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 25 43 Geração de cortes Cortes de Gomory 1958 Exemplo x1 x2 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 x x Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 25 43 Geração de cortes Cortes de Gomory 1958 Exemplo x1 x2 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 x x Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 25 43 Geração de cortes Cortes de Gomory 1958 Conclusões e Críticas A nova região não contará com o ótimo encontrado pelo SIMPLEX já que o corte o removerá É garantido que todas as soluções inteiras viáveis estarão presentes nessa nova região mais estreita Computacionalmente aumenta o número de coeficientes nãonulos na matriz do problema Pode não ser profundo o suficiente para se aproximar da solução ótima inteira Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 26 43 Geração de cortes Exercícios 1 Dado o seguinte quadro SIMPLEX final gere os respectivos corte de GOMORY para a L2 VB x1 x2 x3 x4 x5 x6 sol x2 0 1 32 12 12 0 45 x1 1 0 14 14 34 0 525 x6 0 0 34 14 14 1 275 max 0 0 254 94 14 0 fx 5775 2 Dada as seguintes soluções verifique se os cortes são válidos ou não a x1 0 x2 5 x3 2 e 3x1 5x2 4x3 7 b x1 1 x2 3 e 3x1 4x2 9 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 27 43 Geracdo de colunas a Pe Motivacao inicial O problema do corte de pecas em estoque Consiste em cortar o menor nimero de pegcas grandes de tamanho exato L em m pecgas menores de comprimentos 11lm nas quantidades bbm respectivamente Assim este problema pode ser reenunciado por se definir inicialmente todas as possiveis maneiras de se cortar as pecas grandes nas pecas menores chamandose de padrao de corte Existe também um pardmetro ad a1jQmj Ou ajj que fala a quantidade de itens do tipo 1 1m no padrdo j 1n de corte Gilmore Paul C and Ralph E Gomory 1961 A linear programming approach to the cuttingstock problem Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 PAS Geracdo de colunas a Pe Motivacao inicial O problema do corte de pecas em estoque Consiste em cortar o menor nimero de pegcas grandes de tamanho exato L em m pecgas menores de comprimentos 11lm nas quantidades bbm respectivamente Assim este problema pode ser reenunciado por se definir inicialmente todas as possiveis maneiras de se cortar as pecas grandes nas pecas menores chamandose de padrao de corte Existe também um pardmetro ad a1jQmj Ou ajj que fala a quantidade de itens do tipo 1 1m no padrdo j 1n de corte Exemplo para L llem4 1y 2lg 313 35 la Padréio 1 a5 00 0 4 4G Guia lole al Padrao 2 a 0 10 2 ty il mal mail Padréo 3 a1 30 0 4 Gilmore Paul C and Ralph E Gomory 1961 A linear programming approach to the cuttingstock problem Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 PAS Geracdo de colunas woe Motivacao inicial O problema do corte de pecas em estoque Consiste em cortar o menor nimero de pegcas grandes de tamanho exato L em m pecgas menores de comprimentos 11lm nas quantidades bbm respectivamente Assim este problema pode ser reenunciado por se definir inicialmente todas as possiveis maneiras de se cortar as pecas grandes nas pecas menores chamandose de padrao de corte Existe também um pardmetro ad a1jQmj Ou ajj que fala a quantidade de itens do tipo 1 1m no padrdo j 1n de corte Exemplo para L llem4 1y 2lg 313 35 la Formulacdo Padréio 1 a5 00 0 4 4G Guia lole al min Ly Padriio 2 4 0 1 02 J10 t 4 fy Saas SO aijay b Vilm j14n Padrdo 3 a 13 0 0 4 4 4 wy EZ Vj 1n aiallcasasallaaaasioal Gilmore Paul C and Ralph E Gomory 1961 A linear programming approach to the cuttingstock problem Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 Paew e Geração de colunas Motivação inicial O problema do corte de peças em estoque 1 Qual seria a solução a Inserir no PPL todas os cortes possíveis b Somente aqueles que fossem interessantes Características Column Generation Originária de vários trabalhos no final dos anos 1950 e início dos 1960 Problema muito grande n m não compensando explicitar todas as suas variáveis Assim somente variáveis com potencial de melhorar a solução são incluídas Dividido em dois problemas Problema Mestre PM Determina como usar as variáveis Subproblema SP Gera as variáveis PO1 Análise de sensibilidade adição de variável Ford e Fulkerson 1957 Manne 1958 Dantzig e Wolfe 1960 Gilmore e Gomory 1961 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 29 43 Geração de colunas Problema mestre restrito PMR Restricted master problem Precisa de uma solução inicial para sua primeira execução Responsável por decidir como e quais variáveis serão usadas Estas são relaxadas x Z x 0 Fornece um limite por vezes fraco inferior superior para a função objetivo de minimização maximização Subproblema de precificação SP Pricing subproblem ou Pricing O SP que majoritariamente define a complexidade do algoritmo e a qualidade das colunas Dita a velocidade e a qualidade da convergência do PMR Quando mais afiado melhores colunas são geradas Executado enquanto existam variáveis com potencial de contribuir para a melhora da solução cr 0 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 30 43 Geração de colunas Problema mestre restrito PMR Restricted master problem Precisa de uma solução inicial para sua primeira execução Responsável por decidir como e quais variáveis serão usadas Estas são relaxadas x Z x 0 Fornece um limite por vezes fraco inferior superior para a função objetivo de minimização maximização Subproblema de precificação SP Pricing subproblem ou Pricing O SP que majoritariamente define a complexidade do algoritmo e a qualidade das colunas Dita a velocidade e a qualidade da convergência do PMR Quando mais afiado melhores colunas são geradas Executado enquanto existam variáveis com potencial de contribuir para a melhora da solução cr 0 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 30 43 Geração de colunas Algoritmo minimização Fase 1 Determine um conjunto de r colunas para o Problema Mestre Res trito PMR a1 a2 ar r n Se necessário inclua co lunas artificiais às quais têm alto custo associado Fase 2 Passos i Resolva o PMR Se PMR é viável mas não ótimo então pare PMR não tem solução ótima ii Resolva o SP e obtenha as colunas aj cj iii Se cj r cj λT aj 0 então PARE A solução xb B1b é ótima Senão cj r cj λT aj 0 adicione as colunas aj cj ao PMR e retorne ao Passo i Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 31 43 Geração de colunas Algoritmo minimização Fase 1 Determine um conjunto de r colunas para o Problema Mestre Res trito PMR a1 a2 ar r n Se necessário inclua co lunas artificiais às quais têm alto custo associado Fase 2 Passos i Resolva o PMR Se PMR é viável mas não ótimo então pare PMR não tem solução ótima ii Resolva o SP e obtenha as colunas aj cj iii Se cj r cj λT aj 0 então PARE A solução xb B1b é ótima Senão cj r cj λT aj 0 adicione as colunas aj cj ao PMR e retorne ao Passo i Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 31 43 Geração de colunas Esquema minimização Início Fim Problema Mestre Subproblema cr 0 λi aj cj SIM NÃO Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 32 43 Geração de colunas Ilustração Problema Original Problema Mestre Restrito Colunas Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 33 43 Geração de colunas Ilustração Problema Original Problema Mestre Restrito Colunas Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 33 43 Geração de colunas Ilustração Problema Original Problema Mestre Restrito Colunas Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 33 43 Geração de colunas Ilustração Problema Original Problema Mestre Restrito Colunas Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 33 43 Geração de colunas Ilustração Problema Original Problema Mestre Restrito Colunas Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 33 43 Geração de colunas Exemplo O problema do corte de peças em estoque Considerando ainda o exemplo do problema de cortes de peças para o qual o comprimento das barras em estoque é L 11 e as peças demandadas nos tamanhos l1 2 l2 3 l3 3 5 l4 4 nas quantidades b1 500 b2 1000 b3 1000 b4 750 respectivamente A questão consiste em determinar qual é o menor número de barras necessárias para atender toda a demanda explicitandose como a barra é cortada Vamos considerar as seguintes colunas iniciais Fase 1 a1 5 0 0 0 a2 0 3 0 0 a3 0 0 3 0 a4 0 0 0 2 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 34 43 Geração de colunas Exemplo O problema do corte de peças em estoque Considerando ainda o exemplo do problema de cortes de peças para o qual o comprimento das barras em estoque é L 11 e as peças demandadas nos tamanhos l1 2 l2 3 l3 3 5 l4 4 nas quantidades b1 500 b2 1000 b3 1000 b4 750 respectivamente A questão consiste em determinar qual é o menor número de barras necessárias para atender toda a demanda explicitandose como a barra é cortada Vamos considerar as seguintes colunas iniciais Fase 1 a1 5 0 0 0 a2 0 3 0 0 a3 0 0 3 0 a4 0 0 0 2 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 34 43 Geração de colunas Exemplo O problema do corte de peças em estoque Fase 2 i Resolva o PMR Solução Primal x1 100 00 x2 333 33 x3 333 33 x4 375 00 fx 1141 66 Solução Dual λ1 0 20 λ2 0 33 λ3 0 33 λ4 0 50 ii Resolva o SP para verificar se a solução atual é ótima ou não max ϕa 0 2α1 0 33α2 0 33α3 0 5α4 2α1 3α2 3 5α3 4α4 11 α1 α2 α3 α4 Z Solução α1 0 α2 1 α3 0 α4 2 ϕa 1 33 que gera a coluna a5 0 1 0 2 iii Como de custo reduzido é negativo c5 r 1 1 33 0 33 0 adicione a5 ao PMR e retorne ao Passo i Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 35 43 Geração de colunas Exemplo O problema do corte de peças em estoque Fase 2 i Resolva o PMR Solução Primal x1 100 00 x2 333 33 x3 333 33 x4 375 00 fx 1141 66 Solução Dual λ1 0 20 λ2 0 33 λ3 0 33 λ4 0 50 ii Resolva o SP para verificar se a solução atual é ótima ou não max ϕa 0 2α1 0 33α2 0 33α3 0 5α4 2α1 3α2 3 5α3 4α4 11 α1 α2 α3 α4 Z Solução α1 0 α2 1 α3 0 α4 2 ϕa 1 33 que gera a coluna a5 0 1 0 2 iii Como de custo reduzido é negativo c5 r 1 1 33 0 33 0 adicione a5 ao PMR e retorne ao Passo i Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 35 43 Geração de colunas Exemplo O problema do corte de peças em estoque Fase 2 i Resolva o PMR Solução Primal x1 100 00 x2 333 33 x3 333 33 x4 375 00 fx 1141 66 Solução Dual λ1 0 20 λ2 0 33 λ3 0 33 λ4 0 50 ii Resolva o SP para verificar se a solução atual é ótima ou não max ϕa 0 2α1 0 33α2 0 33α3 0 5α4 2α1 3α2 3 5α3 4α4 11 α1 α2 α3 α4 Z Solução α1 0 α2 1 α3 0 α4 2 ϕa 1 33 que gera a coluna a5 0 1 0 2 iii Como de custo reduzido é negativo c5 r 1 1 33 0 33 0 adicione a5 ao PMR e retorne ao Passo i Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 35 43 Geração de colunas Exemplo O problema do corte de peças em estoque demais iterações Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 36 43 Geração de colunas Exercícios 1 Teste se as seguintes colunas seriam adicionadas ao PMR de maximização cj r cj λTaj 0 segundo o vetor de variáveis duais λT 1 2 0 3 2T a c6 2 5 e a6 1 0 1 b c7 4 0 e a7 3 4 2 c c8 10 0 e a8 5 2 1 2 Qual o principal empecilho no método de Geração de Colunas Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 37 43 Métodos exatos combinados Características Tornaramse viáveis em combinação com as técnicas de Branchandbound com Geração de Colunas eou Cortes Branchandcut Em cada nó da árvore de BB adicionase igualdades com o intuito de se obter limites melhores para a solução Branchandprice Em cada nó da árvore de BB após a precificação as variáveis básicas fracionárias são ramificadas Branchpriceandcut ou Branchcutandprice Por óbvio cortes e colunas são adicionados aos nós da árvore de busca Columnandcut Aproximação que busca verificar qual combinação de cortes e subproble mas geram melhores limites os cortes são para fortalecer a formulação Columnandrow As restrições adicionadas são parte da formulação para garantir sua viabilidade A diferença é que assim como as colunas são gradativamente explicitados Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 38 43 Columnandcut Ilustração Problema Original Problema Mestre Restrito Colunas Cortes Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 39 43 Columnandcut Ilustração Problema Original Problema Mestre Restrito Colunas Cortes Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 39 43 Columnandcut Ilustração Problema Original Problema Mestre Restrito Colunas Cortes Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 39 43 Columnandcut Ilustração Problema Original Problema Mestre Restrito Colunas Cortes Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 39 43 Columnandcut Ilustração Problema Original Problema Mestre Restrito Colunas Cortes Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 39 43 Columnandrow Ilustração Problema Original Problema Mestre Restrito Colunas Restrições Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 40 43 Columnandrow Ilustração Problema Original Problema Mestre Restrito Colunas Restrições Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 40 43 Columnandrow Ilustração Problema Original Problema Mestre Restrito Colunas Restrições Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 40 43 Métodos exatos combinados Exercícios 1 Qual a diferença entre Columnandcut e Columnandrow Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 41 43 DIONE KYe e a Ha perguntas ingénuas perguntas enfadonhas perguntas mal formuladas perguntas precipitadas Mas todas elas representam um desejo de compreender o mundo No ha perguntas estipidas Carl Sagan x 1934 t 1996 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 ro sc Referências 1 Arenales M Armentano V Morabito R Yanasse H Pesquisa Operacional para cursos de engenharia Modelagem e algoritmos 2ª Ed Rio de Janeiro Editora Campus 2015 2 Goldbarg M C Goldbarg E G Luna H P L Otimização Combinatória e Progra mação Linear 2ª Ed Rio de Janeiro Editora Elsevier 2005 3 Goldbarg M C Goldbarg E G Luna H P L Otimização Combinatória e Meta heurísticas Algoritmos e Aplicações 1ª Ed Rio de Janeiro Elsevier 2016 4 Martin Richard Kipp Large scale linear and integer optimization an unified ap proach Springer Science Business Media 2012 5 Taha Hamdy A Pesquisa operacional Pearson Education do Brasil 2008 Prof Allexandre Fortes DEMEPUFSJ PO2 Métodos exatos 20 de abril de 2023 43 43