(Mestrado) Engenharia Industrial
Investigação OperacionalProgramação Inteira: Partição e Avaliação, Planos de Corte(Mestrado)Engenharia idade do Minho - Escola de EngenhariaDepartamento de Produção e SistemasUniversidade do Minho2006Investigação Operacional1José António Oliveira – zan@dps.uminho.ptPI: Introdução Problema de PI GeralIgnorando as restriçõesde integralidade num PI,obtém-se um problema dePL, que se designa porRelaxação Linear (de PI). Em geral, não faz sentido resolver a relaxação linear earredondar a solução óptima obtida. A soluçãoarredondada pode nem sequer ser admissível ou podeestar muito afastada da solução óptima. Há circunstâncias práticas em que o arredondamentopode fazer sentido, tendo-se a consciência de que seestá a obter uma solução que pode não ser óptima (porexemplo, na prática será muito diferente x 1999.5 oux 2000?).Universidade do Minho2006Investigação Operacional2José António Oliveira – zan@dps.uminho.pt1
PI: Introdução Problema de PI GeralIgnorando as restriçõesde integralidade num PI,obtém-se um problema dePL, que se designa porRelaxação Linear (de PI).Conjunto das soluçõesadmissíveis da RL inclui oconjunto das soluçõesadmissíveis do PI o queimplicaUniversidade do Minho2006Investigação Operacional3José António Oliveira – zan@dps.uminho.ptPI: Introdução Problema de PI é muito mais difícil de resolver do queo de PL (perdeu-se a convexidade do conjunto desoluções admissíveis.). Para PL são conhecidas condições necessárias esuficientes de optimalidade (admissibilidade primal edual e verificação do teorema da folga complementar). Para PI não são conhecidas condições necessárias nemsuficientes de optimalidade: dada uma soluçãoadmissível, a única forma de determinar se ela éóptima ou não é demonstrar que não existe nenhumasolução admissível com melhor valor. Algoritmos para PI baseiam-se na resolução demúltiplos problemas de PLUniversidade do Minho2006Investigação Operacional4José António Oliveira – zan@dps.uminho.pt2
PI: Introdução Intervalo (gap) de integralidade relativo Gap relativo acima de 10%:temos problema difícil! Gap relativo acima de 50%:temos problema muito difícil!!!Universidade do Minho2006Investigação Operacional5José António Oliveira – zan@dps.uminho.ptMétodos de planos de corte Um problema de PI é fácil de resolver se a região dassoluções admissíveis da relaxação linear tiver todos ospontos extremos inteiros! Nesse caso, ao resolver-se um problema de PL está-sea resolver o problema inteiro (é o que acontece nageneralidade dos problemas "fáceis": fluxo de customínimo, transportes, afectação,.).Universidade do Minho2006Investigação Operacional6José António Oliveira – zan@dps.uminho.pt3
Métodos de planos de corte Quanto mais a região das soluções admissíveis darelaxação linear se aproximar do invólucro convexo daregião das soluções admissíveis do PI melhor– (é por isso que uma boa formulação pode fazer a diferençaentre resolver-se o problema ou não).Universidade do Minho2006Investigação Operacional7José António Oliveira – zan@dps.uminho.ptMétodos de planos de corte Desigualdade válida (corte): restringe a região dassoluções admissíveis da relaxação linear, mas nãoexclui soluções inteiras. A inclusão de desigualdades válidas aproxima a regiãodas soluções admissíveis da relaxação linear doinvólucro convexo da região das soluções admissíveisdo PI (fortalecendo a formulação). Exemplo: problema da mochilaUniversidade do Minho2006Investigação Operacional8José António Oliveira – zan@dps.uminho.pt4
Métodos de planos de corte Exemplo: problema da mochilaUniversidade do Minho2006Investigação Operacional9José António Oliveira – zan@dps.uminho.ptMétodos de planos de corte Inicialização– PL pode ser relaxação linear do PI;– PL pode ser só parte da formulação original(se o número de restrições for muito elevado). Separação– Identificar uma (a) restrição (corte) que estáa ser (mais) violada. Cortes– Restrições válidas para qualquer problema dePI (exemplo: cortes de Gomory);– Restrições específicas do problema que está aser resolvido (exemplo: desigualdades decobertura para o problema da mochila);– Restrições que foram deixadas de fora daformulação propositadamente devido ao seuelevado número (exemplo: restrições deeliminação de subcircuitos para o problema docaixeiro viajante)Universidade do Minho2006Investigação Operacional10José António Oliveira – zan@dps.uminho.pt5
Métodos de planos de corte Exemplo de um método deplanos de corte: Método dos planos de corte deGomory para PIPs. Inicialização: PL é a relaxaçãolinear do problema PIP. Separação: é identificada umadesiguladade válida (corte deGomory) através das linhas doquadro simplex. Após um número finito deiterações é sempre obtida umasolução óptima para o PIP.Universidade do Minho2006Investigação Operacional11José António Oliveira – zan@dps.uminho.ptMétodos de planos de corte Quadro óptimo da resolução da relaxação linear. As duas restrições são desigualdades válidas:– excluem a solução actual (x1 2.25 e x2 1.5) e não excluemnenhuma solução inteira.Universidade do Minho2006Investigação Operacional12José António Oliveira – zan@dps.uminho.pt6
Métodos de planos de corte Quadro óptimo da resolução da relaxação linear. Qual escolher?– A que tem um termo independente com maior parte fraccionária.(Em caso de empate, escolher arbitrariamente).– No exemplo, a segunda.Universidade do Minho2006Investigação Operacional13José António Oliveira – zan@dps.uminho.ptMétodos de planos de corte Quadro óptimo da resolução da relaxação linear. Como foram obtidas?Universidade do Minho2006Investigação Operacional14José António Oliveira – zan@dps.uminho.pt7
Métodos de planos de corte Quadro óptimo da resolução da relaxação linear. Linha i está associada a uma variável básica com valor fraccionário. Define-se para todas as variáveis j : Para o termo independente : O Corte de Gomory é dado por :Universidade do Minho2006Investigação Operacional15José António Oliveira – zan@dps.uminho.ptMétodos de planos de corte No exemplo, a restrição introduzida é Quadro simplex após introdução da nova restrição:Universidade do Minho2006Investigação Operacional16José António Oliveira – zan@dps.uminho.pt8
Métodos de planos de corte Através de uma iteração do simplex dual Solução continua a não ser inteira. Novo corte de GomoryUniversidade do Minho2006Investigação Operacional17José António Oliveira – zan@dps.uminho.ptMétodos de planos de corte Quadro simplex após introdução da nova restrição:Universidade do Minho2006Investigação Operacional18José António Oliveira – zan@dps.uminho.pt9
Métodos de planos de corte Através de uma iteração do simplex dual Solução óptima inteira O método dos planos de corte de Gomory para PIPsobtém sempre uma solução óptima num número finito deiterações.Universidade do Minho2006Investigação Operacional19José António Oliveira – zan@dps.uminho.ptMétodos de planos de corte Primeiro corteUniversidade do Minho2006Investigação Operacional20José António Oliveira – zan@dps.uminho.pt10
Métodos de planos de corte Primeiro corte Segundo corteUniversidade do Minho2006Investigação Operacional21José António Oliveira – zan@dps.uminho.ptMétodos de planos de corte Primeiro corteZ 12.75Z 12.50 Segundo corteUniversidade do Minho2006Z 12.00Investigação Operacional22José António Oliveira – zan@dps.uminho.pt11
Método de partição e avaliação Se a relaxação linear. não tem solução óptimafinita,– PI não tem solução óptima finita. é impossível,– PI é impossível. tem solução óptima finita einteira– é a solução óptima de PI. tem solução óptima finita enão é inteira,– existe uma variável x que tem umvalor fraccionário f.Das duas umaouUniversidade do Minho2006Investigação Operacional23José António Oliveira – zan@dps.uminho.ptMétodo de partição e avaliação No exemplo, a solução óptima da relaxaçãolinear é x1 2.25 e x2 1.5 Numa solução inteira das duasuma:ouOu entãoouUniversidade do Minho2006Investigação Operacional24José António Oliveira – zan@dps.uminho.pt12
Método de partição e avaliação Criam-se dois novos subproblemas. No primeiro acrescenta-se às restrições originais arestrição No segundo acrescenta-se às restrições originais arestrição A solução óptima da relaxação linear (RL) é excluída deambos os subproblemas, mas nenhuma solução inteira éexcluída reunindo as regiões das soluções admissíveisdos dois subproblemas.Universidade do Minho2006Investigação Operacional25José António Oliveira – zan@dps.uminho.ptMétodo de partição e avaliação No exemplo, temos mais do que uma variável com valorfraccionário, qual escolher para efectuar a partição? Existem várias regras:(1) a que tem menor parte fraccionária,(2) a que tem maior parte fraccionária,(3) a que tem a parte fraccionária mais próxima de 0.5,(4) outras regras (muito mais.) sofistificadas, algumasdependentes do problema. Utilizando a regra (3) seleccionamos para variável departição a variável x2Universidade do Minho2006Investigação Operacional26José António Oliveira – zan@dps.uminho.pt13
Método de partição e avaliação Árvore de pesquisa do método de partição e avaliação. Cada nodo corresponde a um subproblema gerado ao adicionar-seuma restrição de partição ao seu ascendente.Universidade do Minho2006Investigação Operacional27José António Oliveira – zan@dps.uminho.ptMétodo de partição e avaliação Uma solução óptima inteira (a existir) faz parte daregião das soluções admissíveis de SP 1 ou SP2. Então basta obter a melhor solução inteira de SP1 e SP2e compará-las. Qual a melhor solução de SP1? Qual amelhor solução de SP2? Repetir o procedimento utilizado em RL para SP 1 e SP2(notando que a obtenção de uma solução óptima se fazde forma muito eficiente: estamos a resolver um(sub)problema do qual é conhecida uma solução óptima eao qual foi adicionada apenas uma restrição reoptimização!) Vamos explorar primeiro o SP1.Universidade do Minho2006Investigação Operacional28José António Oliveira – zan@dps.uminho.pt14
Método de partição e avaliaçãoUniversidade do Minho2006Investigação Operacional29José António Oliveira – zan@dps.uminho.ptMétodo de partição e avaliação Passámos a ter trêssubproblemas em aberto. Basta obter a melhorsolução inteira de SP2,SP3 e SP4 e comparálas. (notar quesubproblemasmas estamospertodeinteiras!).Universidade do Minho2006o número deestá a aumentarcada vez maistersoluçõesInvestigação Operacional30José António Oliveira – zan@dps.uminho.pt15
Método de partição e avaliação Qual resolver primeiro, ou seja qual a estratégia depesquisa da árvore a utilizar?(1) primeiro em profundidade (escolher subproblema que está aum nível mais profundo, ou seja, que tem mais restrições departição): SP3 ou SP4.(2) primeiro em largura (escolher subproblema que está a um nívelmenos profundo, ou seja, que tem menos restrições departição): SP2.(3) subproblema mais promissor (o que tem um maior limitesuperior - ver à frente),(4) outras regras (muito mais.) sofistificadas, algumasdependentes do problema. Utilizando a estratégia de pesquisa "primeiro emprofundidade" escolhemos SP3 (arbitrariamente emrelação a SP4).Universidade do Minho2006Investigação Operacional31José António Oliveira – zan@dps.uminho.ptMétodo de partição e avaliação zSP3 10, x1 2, x2 1(valores obtidos através da reoptimização do simplex jáexemplificada). Temos uma solução inteira! Como é amelhor solução inteira obtida até ao momento, designase por incumbente. SP3 não gera descendentes (por ter uma soluçãointeira). De acordo com a estratégia de pesquisa que estamos autilizar, o próximo subproblema a ser explorado é o SP4. zSP4 9, x1 3, x2 0.Temos outra solução inteira! Como é a pior do que asolução incumbente, ignoramo-la. SP4 não gera descendentes (por ter uma soluçãointeira). Falta explorar SP2.Universidade do Minho2006Investigação Operacional32José António Oliveira – zan@dps.uminho.pt16
Método de partição e avaliaçãoUniversidade do Minho2006Investigação Operacional33José António Oliveira – zan@dps.uminho.ptMétodo de partição e avaliaçãoUniversidade do Minho2006Investigação Operacional34José António Oliveira – zan@dps.uminho.pt17
Método de partição e avaliaçãoUniversidade do Minho2006Investigação Operacional35José António Oliveira – zan@dps.uminho.ptMétodo de partição e avaliaçãoUniversidade do Minho2006Investigação Operacional36José António Oliveira – zan@dps.uminho.pt18
Método de partição e avaliação Ponto da situação: incumbente vale 12 (soluçãoincumbente é x1 2, x2 1) e apenas falta explorar SP6. Resolvendo SP6 daria um problema impossível o quepermitiria concluir que a solução incumbente é a soluçãoóptima inteira. Mas. seria preciso resolver SP6 para chegar a essaconclusão? De facto, zSP6 zSP2 (onde zSP2 12.5) porque a diferença entreSP6 e SP2 é ter mais uma restrição (o valor de uma solução óptimanunca melhora ao adicionarem-se restrições). Como os coeficientes das variáveis na função objectivo são todosinteiros, a melhor solução que podemos obter resolvendo SP6 temvalor 12. A solução incumbente tem esse valor, logo resolvendo SP6 nuncavamos obter uma solução melhor do que a incumbente. Podemosabandonar SP6 sem o resolver! Podemos generalizar este tipo de raciocínio para todosos nodos!Investigação Operacional37Universidade do MinhoJosé António Oliveira – zan@dps.uminho.pt2006Método de partição e avaliação Estratégia de pesquisa: primeiro emprofundidade. Selecção da variável de partição: partefraccionária mais próxima de 0.5 .Universidade do Minho2006Investigação Operacional38José António Oliveira – zan@dps.uminho.pt19
Método de partição e avaliação Ponto da situação: incumbentedada por SP5 com valorzINC 40. O valor da solução óptimainteira, z*, é sempre maior ouigual ao da incumbente:z* zINC. O valor que se pode obter emcada SP, zSP, é sempre igualou inferior ao da solução doSP ascendente, zSPaUniversidade do Minho2006Investigação Operacional39José António Oliveira – zan@dps.uminho.ptMétodo de partição e avaliaçãoPara qualquer subproblemaSP tem de ser exploradoSP pode ser abandonadoUniversidade do Minho2006Investigação Operacional40José António Oliveira – zan@dps.uminho.pt20
Método de partição e avaliaçãoUniversidade do Minho2006Investigação Operacional41José António Oliveira – zan@dps.uminho.ptMétodo de partição e avaliaçãoO resultado da resolução de um subproblema pode ser:(i)(ii)impossível, o que implica o abandono do subproblema;solução tem um valor pior do que a incumbente, o queimplica que o subproblema é abandonado (avaliaçãodos limites);(iii) solução é inteira e tem melhor valor do que aincumbente, o que implica a actualização daincumbente (não são gerados descendentes);(iv) solução é fraccionária e tem melhor valor do que aincumbente, o que implica efectuar a partição, sendogerados dois novos subproblemas.Universidade do Minho2006Investigação Operacional42José António Oliveira – zan@dps.uminho.pt21
Método de partição e avaliaçãoInvestigação OperacionalUniversidade do Minho200643José António Oliveira – zan@dps.uminho.ptMétodos para PI Planos de Corte– Finais dos anos 50, início dos anos 60.– Adicionar restrições para aproximar RL do invólucro convexodo PI.– Tópico de investigação muito actual (utilização de Teoria dosPoliedros para definir invólucro convexo das soluçõesadmissíveis do problema). R. E. Gomory, "Outline of an algorithm for Integer solutions tolinear programs", Bulletin of the American Mathematical Society64, 1958. R. E. Gomory, "An Algorithm for Integer Solutions to LinearPrograms", in "Recent Advances in Mathematical Programming”,edited by R. L. Graves and P. Wolfe, 1963, McGraw-Hill.Universidade do Minho2006Investigação Operacional44José António Oliveira – zan@dps.uminho.pt22
Métodos para PI Partição e Avaliação ("branch-and-bound")– Início anos 60.– Enumeração implícita através do cálculo de limites inferiorese superiores. Utilizado em todos os packages de softwarepara Programação Inteira. A.H. Land, A.G. Doig, "An Automatic Method for SolvingDiscrete Programming Problems", Econometrica 28:3, 1960. As ideias centrais de ambos os métodos continuam aestar presentes nos métodos mais recentes pararesolver PIs. A evolução (em termos de implementaçõeseficientes em computador e em termos teóricos) foi(está a ser.) enorme! Os algoritmos apresentados são versões básicas.Universidade do Minho2006Investigação Operacional45José António Oliveira – zan@dps.uminho.ptMétodos para PI Partição com Cortes ("branch-and-cut")– Meados dos anos 80. Combinação de Partição e Avaliação comPlanos de Corte.– De forma muito geral, são adicionados cortes aossubproblemas da árvore de pesquisa do método de partição eavaliação.– Utilizado em todos os packages avançados de software paraProgramação Inteira.– Tópico de investigação muito actual. K. Hoffman, M. Padberg, "LP-based Combinatorial ProblemSolving", Annals of Operations Research 4, 1985. M. Padberg and G. Rinaldi, "A Branch-and-Cut Algorithm for s",SIAMReview 33, 1991.Universidade do Minho2006Investigação Operacional46José António Oliveira – zan@dps.uminho.pt23
Métodos para PI Partição e Geração de Colunas ("branch-and-price")– Meados dos anos 80.– Combinação de Partição e Avaliação com Método de Geraçãode Colunas para PL (variáveis são geradas à medida que sãoprecisas).– Tópico de investigação muito actual. J. Desrosiers, F. Soumis, M. Desrochers, Routing with timewindows by column generation, Networks, 14 (1984) 545-565. Partição e Geração de Colunas com Cortes ("branch-andcut-and-price")– Meados dos anos 90 (raízes anteriores).– Combinação entre Partição e Avaliação, Planos de Corte eGeração de Colunas.– Tópico de investigação muito actual.Universidade do Minho2006Investigação Operacional47José António Oliveira – zan@dps.uminho.ptMétodos para PI Métodos heurísticos– Heurísticas gulosas– Heurísticas de Pesquisa Local– Meta heurísticas (Pesquisa Tabu, Pesquisa por ArrefecimentoSimulado "Simulated Annealing", Algoritmos Genéticos,Colónias de Formigas, GRASP, Pesquisa em VizinhançasVariáveis, etc,.). Área de investigação muito activa desde finais dos anos 80,início dos anos 90. Raízes são muito anteriores. Continua umtópico de investigação muito actual. Conceitos básicos muito gerais (e simples!). Muito fáceis deimplementar. Têm de ser adaptadas para cada problema (o que pode ser feitode muitas formas.). O que tem vantagens e desvantagens. Utilizáveis noutros problemas (nomeadamente não lineares).– Heurísticas especializadasUniversidade do Minho2006Investigação Operacional48José António Oliveira – zan@dps.uminho.pt24
Métodos para PI Métodos heurísticos– Há problemas em que não se justifica o seu uso! As metaheurísticas não dão soluções óptimas (são heurísticas!) e, emproblemas fáceis, para os quais existem métodos exactosmuito eficientes, o custo de obter soluções óptimas ébaixíssimo. Mesmo para problemas difíceis, a existência desoftware com implementações muito eficientes de métodosexactos implica sempre a ponderação do seu uso.– A incorporação de heurísticas nos métodos exactos é cadavez mais utilizada (por exemplo para obter limites inferioresno método de partição e avaliação).Investigação OperacionalUniversidade do Minho200649José António Oliveira – zan@dps.uminho.ptMétodos para PI Outros métodos– Programação em Lógica por Restrições. Muito bom para obter soluções admissíveis em problemas ios(escalonamento, por exemplo), não tão bom para obter soluçõesóptimas. Combinação com Partição e Avaliação é recente (finaisdos anos 90) e em alguns problemas tem dado muito bonsresultados.– Algoritmos de redução de base. Método exacto que se baseia na Teoria dos Números. Poucasimplementações.Universidade do Minho2006Investigação Operacional50José António Oliveira – zan@dps.uminho.pt25
Métodos para PI Outros métodos– Relaxação Lagrangeana. Anos
(Mestrado) Engenharia Industrial . Universidade do Minho - Escola de Engenharia Departamento de Produção e Sistemas Universidade do Minho 2006 Investigação Operacional . Em geral, não faz sentido resolver a relaxação linear e arredondar a solução óptima obtida. A solução arredondada pode nem sequer ser admissível ou pode .
Faculdade de Engenharia da Universidade do Porto Página 1 de 35 1. INTRODUÇÃO No âmbito da unidade curricular Projeto FEUP, integrada no primeiro semestre do primeiro ano do Mestrado Integrado em Engenharia e Gestão Industrial, na Faculdade de Engenharia da Universidade do Porto (FEUP), foi conduzida uma pesquisa e posterior
Mestrado em Engenharia e Gestão Industrial Orientação: Professora Doutora Maria Teresa Ribeiro Pereira Vila do Conde, Dezembro de 2014 . João Pedro Abrunhosa Martins Estudo do Impacto do Transporte Ferroviário de Mercadorias no Eixo Leixões - Salamanca Dissertação de Mestrado
Mestrado em Engenharia Mecânica – Produção Industrial Dimensionamento Estrutural de Moldes de Injeção Pedro Francisco Venâncio Pereira Projeto de Mestrado realizada sob a orientação do Doutor Mário Simões Correia, Professor da Escola Superior de Tecnologia e Gestão do Instituto Politécnico de Leiria
Mestrado Integrado em Engenharia Química Estudo da Sujidade de Garrafas de Tara Retornável e da Eficiência de Remoção numa Lavadora Industrial Tese de Mestrado desenvolvida no âmbito da disciplina de Projecto de Desenvolvimento em Ambiente Empresarial Rui Vieira Afonso Unicer – Bebidas de Portugal, SGPS, S.A.
Mestrado em Engenharia de Petróleo, que terá a duração de 2 semestres (enquanto decorrem as actividades preparatórias para o arranque do curso de Mestrado), sendo que, em cada um desses semestres, serão leccionadas duas disciplinas que constituem o núcleo dos cursos de licenciatura em Engenharia de Petróleo.
O Mestrado em Engenharia Industrial visa a formação de técnicos especializados num dos seguintes domínios da Engenharia Industrial: Gestão Industrial, Avaliação e Gestão de Projectos e da Inovação, Logística e Distribuição e Qualidade, Segurança e Manutenção e compreende uma parte escolar, ocupando os dois
mestrado em engenharia industrial manoel messias domingos da silva anÁlise da viabilidade de inovaÇÃo tecnolÓgica do processo de produÇÃo de uma empresa metal – mecÂnica em maceiÓ – alagoas
Grammar 39. Adjectives — Rachna Khosla 40. Use of present continuous tense — Farzana Shamim www.trinitycollege.co.uk April 2013. Selected entries from the Trinity English Language Lesson Plan Competition 2013 3 Introduction About us Trinity College London is an international exam board with a rich cultural heritage and over 70 years’ experience in assessing English language proficiency .
