Pesquisa Operacional: Programação Linear Inteira

PESQUISA OPERACIONAL Organizador Rodrigo Rodrigues Catalogação na publicação Poliana Sanchez de Araujo CRB 102094 R696p Rodrigues Rodrigo Pesquisa operacional Rodrigo Rodrigues Porto Alegre SAGAH 2017 121 p il 225 cm ISBN 9788595020047 1 Pesquisa operacional Engenharia de produção I Título CDU 6585 Programacao linear inteira Objetivos de aprendizagem Ao final deste texto vocé deve apresentar os seguintes aprendizados lIdentificar as caracteristicas gerais da programacao linear inteira Determinar a alocagao de recursos a atividades Descrever uma programacao linear inteira Introducao Os problemas de programacao linear inteira PLI estado relacionados frequentemente ao fato de algumas ou todas as variaveis de decisdo terem de se restringir a valores inteiros Ha também muitas aplicagdes que envolvem decisdes simoundo que podem ser representadas por variaveis binarias 01 Por causa desses fatores a programacao inteira se tornou uma das técnicas de pesquisa operacional PO mais amplamente utilizadas Neste texto vocé vai conhecer caracteristicas importantes da pro gramagao linear inteira suas principais aplicacdes e os algoritmos mais utilizados para resolver problemas de PLI Programagao linear inteira caracteristicas geralis Programagao linear inteira PLI so programacées lineares nas quais algumas ou todas as variaveis estao restritas a valores inteiros ou discretos Quando estudamos PLI precisamos destacar trés areas aplicacao teoria e calculo Vocé vai ver algumas aplicagdes que demonstram a ampla utilizacgao de PLI na pratica Vai ver também dois algoritmos proeminentes de PLI branchand bound BB e planos de corte Dos algoritmos o BB é 0 mais eficiente em termos de calculo Na realidade praticamente todos os codigos comerciais tém suas raizes no BB TAHA 2008 94 Pesquisa operacional Os algoritmos de PLI apresentam uma desvantagem que a sua falta de consisténcia na resolucao de problemas com nimeros inteiros Embora seja comprovado teoricamente que esses algoritmos convergem em um nimero finito de iteracdes sua implantagao em computador com seu inerente erro de arredondamento é uma experiéncia diferente Nao se esqueca disso quando estudar os algoritmos PLI Programagao linear inteira recursos e aplicacoes Em geral as aplicagdes possuem duas categorias direta e transformada Na categoria direta as variaveis sao naturalmente inteiras e podem assumir valores binarios 0 ou 1 ou discretos gerais O problema pode consistir em determinar por exemplo se um projeto sera ou nao selecionado para execugao binario ou achar o numero 6timo de maquinas necessarias para executar uma tarefa valor discreto geral Na categoria transformada o problema original que pode ou nao envolver quaisquer variaveis inteiras é intratavel analiticamente Para transformalo em tratavel sdo usadas variaveis auxiliares inteiras em geral binarias Segundo Taha 2008 a natureza ou das restrigdes 6 que torna o problema analiticamente intratavel porque todos os algoritmos matematicos de programacao matematica tratam apenas de restrigdes e A situagao remediada usando variaveis binarias auxiliares para transformar as restrigdes ou em restrigdes e equivalentes Convencionouse a definicao de um problema inteiro puro como aquele que tem todas as variaveis inteiras Caso trate de variaveis continuas e inteiras é um problema de programacao inteira mista Orcamento de capital O nosso viés agora é com relacao a decisdes sobre 0 investimento ou nao em projetos individuais A decisao influenciada pelo orgamento limitado e pelas prioridades na execucao dos projetos Exemplo 1 selecao de projeto Em uma projecao de planejamento de trés anos cinco projetos estao sob avaliacao A Tabela apresenta os resultados esperados para cada projeto e os investimentos anuais associados Programagao linear inteira 95 Tabela1 Retornos esperados Desembolsos milhées ano Retornos Projeto milhées 5 8 20 2 4 7 10 40 3 3 9 2 20 4 7 4 1 15 5 8 6 10 30 Fundos 25 25 25 disponitveis milhdes Quais projetos devem ser selecionados na projeéo de trés anos O problema se reduz a uma decisao simnao para cada projeto Definimos a variavel binaria x como 1se 0 projeto j for selecionado X eee 0 se o projeto j nao for selecionado O problema de PLI é Maximizar z 20x 40x 15x 30x Sujeito a 5x 4x 3x 7x 8x 25 X 7x 9x 4x 6x 25 8x 10x 2x x 10x 25 X15 X59 Xo Xyy X 01 A solugao inteira 6tima que pode ser obtida pelo Excel Solver ou outros programas é x x xx 1 x0 com z 95 milhdes A solugao mostra que todos os projetos com excegao do 5 devem ser selecionados E interessante comparar a solucao continua de PL com a solugdo de PLI A PL otima obtida pela substituigao de x 01 por 0 x I para todo j da como resultado x 05789 x x x 1 x 07368 e z 10868 milhdes 96 Pesquisa operacional Nao ha sentido para a solugao devido a duas das variaveis que assumem valores fracionarios Podemos arredondar a solucao para o inteiro mais pré ximo que da x x 1 Contudo a solucao resultante inviavel porque as restrig6es sao violadas Mais importante 0 conceito de arredondamento nao tem sentido aqui porque x representa uma decisao simnao Problema de cobertura Nos problemas de cobertura varias instalagdes oferecem servicos sobrepostos a varias localidades O objetivo é identificar o numero minimo de instalagdes que atenderao as necessidades de cada localidade Por exemplo estagdes de tratamento de agua podem ser construidas em varios locais sendo que cada uma atenderia a um conjunto diferente de cidades A sobreposicaéo surge quando uma determinada cidade podera ser atendida pelos servigos de mais de uma estacao Exemplo 2 instalagao de telefones de seguranca Outro exemplo apresentado por Taha 2008 de um departamento de seguranca de uma universidade que para promover a seguranca no campus iniciou um processo de instalagao de telefones de emergéncia em locais se lecionados O departamento quer instalar o numero minimo de telefones contanto que cada uma das principais ruas do campus seja atendida por no minimo um telefone A Figura mostra o mapa do campus E conveniente colocar os telefones em cruzamentos de ruas de modo que cada um atenda no minimo duas ruas A Figura mostra que o leiaute das ruas requer um maximo de oito localizagées de telefones Definase aX hse um telefone for instalado no local j 4 0 caso contrario As restrigdes do problema requerem a instalagao de no minimo um telefone em cada uma das 11 ruas A a K Veja como fica 0 modelo Minimizar z X X X X X X FX X Sujeito a A solução ótima do problema requer instalar quatro telefones nos cru zamentos 1 2 5 e 7 Mais especificamente os problemas de cobertura são caracterizados por 1 As variáveis xj j 12n são binárias 2 Os coeficientes do lado esquerdo das restrições são 0 ou 1 3 O lado direito de cada restrição é da forma 1 Figura 1 Mapa de ruas do campus da universidade 97 Programação linear inteira 4 A função objetivo minimiza c1x1 c2x2 cnxn em que cj 0 para todo j 1 2 n Nesse exemplo cj 1 para todo j Se cj representar o custo de instalação no local j então esses coeficientes podem assumir valores que não sejam 1 Variações do problema de cobertura incluem condições adicionais de lado Problema de carga fixa O problema de carga fixa aborda situações em que a atividade econômica implica em dois tipos de custos uma taxa inicial fixa que deve ser incidida no início da atividade e um custo variável que é diretamente proporcional ao nível da atividade Por exemplo a preparação e o ajuste inicial das ferramentas de uma máquina antes de iniciar a produção implicam em um custo fixo de preparação independentemente da quantidade de unidades fabricadas Uma vez concluída o custo da mão de obra e do material é proporcional à quantidade produzida Dado que F é a carga fixa c é o custo unitário variável e x é o nível de produção a função custo é expressa como A função C x é intratável analiticamente porque envolve uma desconti nuidade em x 0 Restrições ouou e seentão Usamos variáveis binárias no problema de carga fixa para lidar com descon tinuidade na função objetivo custo Em muitos modelos as restrições não são satisfeitas ao mesmo tempo ou ou ou são dependentes seentão novamente usando variáveis binárias A transformação não muda a natureza de ou ou de dependência das restrições Ela simplesmente usa um truque matemático para apresentálas no formato desejado de restrições e TAHA 2008 Pesquisa operacional 98 Programagao linear inteira 99 Programacao linear inteira resolugao de problemas por meio de algoritmos Problemas de PLI sAo muito mais dificeis do que seriam sem a restricao de numeros inteiros por isso os algoritmos disponiveis para programagao inteira sao em geral menos eficientes que o método simplex Contudo ao longo das ultimas décadas houve progresso na capacidade de resolver alguns mas nao todos problemas de PLI extensos com dezenas ou até mesmo centenas de milhares de variaveis inteiras HILLIER LIEBERMAN 2013 Para todo problema de PLI existe um problema de programagao linear correspondente no qual as restricdes de nao fracionariedade sao removidas ou relaxadas Veja alguns resultados Espaco de solucées viaveis do PLI Espaco de solucées vidveis do PLI relaxado Valor 6timo de z do PLI Valor 6timo do PI relaxado Uma possivel abordagem para a solugao de problemas de PLI resolver seus problemas correspondentes relaxados e arredondar as variaveis de decisao para o maior ou menor inteiro mais proximo No entanto dois problemas podem resultar dessa abordagem Os valores arredondados podem resultar em pontos inviaveis no PLI As solucées resultantes sao altamente subotimas Os algoritmos de PLI sao baseados na exploracao do indiscutivel sucesso computacional da PL Segundo Taha 2008 a estratégia desses algoritmos envolve trés etapas Etapa 1 Relaxe a regiao de solucgdes da PLI eliminando a restrigao inteira imposta a todas as variaveis inteiras e substituindo qualquer variavel binaria y pela faixa continua 0 y 1 O resultado da relaxagao é uma PL normal Etapa 2 Resolva a PL e identifique a solugado 6tima continua Etapa 3 Comegando do ponto 6timo continuo adicione restrigdes especiais que modifiquem interativamente a regiao de solugdes da PL de maneira que a certa altura resultara em um ponto extremo 6timo que satisfacga os requisitos inteiros Dois métodos gerais foram desenvolvidos para gerar as restrições especiais na etapa 3 1 Método branchandbound BB 2 Método de planos de corte Embora nenhum dos dois métodos seja consistentemente efetivo em termos computacionais a experiência mostra que o método BB é muito mais bem sucedido do que o método de plano de corte Método BranchandBound para solução de problemas PLIs puros Considere o problema de PLI Max z 8x1 5x2 sa x1 x2 6 9x1 5x2 45 x1 x2 0 x1 x2 inteiros O método de solução de problemas de PI utilizando o branchandbound BB é operacionalizado em cinco passos descritos a seguir 1 Comece resolvendo o PLI relaxado Se a solução ótima for inteira esta é a solução do PLI Quando esse não for o caso a solução ótima do IPR problema de programação inteira relaxado é o limite superior da solução ótima do PLI A solução ótima desse exemplo de IPR é z 1654 x1 154 x2 94 2 Escolha uma variável de decisão fracionária em z do IPR por exemplo x1 154 O PLI admite valores de x1 3 ou x1 4 mas não em 3 x1 4 Crie dois subproblemas a partir de x1 SP2 SP1 restrição x1 4 SP3 SP1 Restrição x1 Pesquisa operacional 100 A sigla SP designa subproblema O problema designado por SP1 é o próprio problema de PLI 3 Escolha qualquer SP listado no passo anterior e resolva como se fosse um problema de programação linear Digamos SP2 com solução ótima z 41 x1 4 e x2 95 Os resultados obtidos até agora podem ser apresentados na forma de uma árvore hierárquica 4 Repita o procedimento em 3 usando o SP2 e a variável de decisão fracionária x2 95 Os subproblemas resultantes são SP4 SP1 x1 4 x2 2 ou SP2 x2 2 SP5 SP1 x1 4 x2 1 ou SP2 x2 1 Temos três problemas que podem ser resolvidos SP3 SP4 e SP5 Escolhemos entre eles um para resolução por exemplo SP4 SP4 não apresenta soluções viáveis não podendo assim gerar uma solução ótima para o problema de PLI Assim dizse que esse nodo da árvore foi terminado Entre os SPs não resolvidos escolhese o mais recente SP5 Veja a solução na árvore do problema a seguir 101 Programação linear inteira 5 Repita o procedimento em 3 usando SP5 e a variável de decisão fracio nária x1 Os subproblemas resultantes são SP6 SP5 x1 5 SP7 SP5 x1 4 Três SPs podem ser resolvidos SP3 SP6 e SP7 Escolhese aleatoriamente um dos mais recentes SP7 por exemplo A solução só possui valores inteiros para a variável de decisão podendo ser inter pretada como uma solução candidata ou um limite inferior no valor ótimo do problema de PLI O Solver pode ser usado para obter a solução dos diferentes subproblemas usando as opções adicionarmodificarexcluir na caixa de diálogo Parâmetros do Solver Pesquisa operacional 102 Algoritmo de plano de corte O algoritmo de corte a exemplo do algoritmo BB também começa na solução contínua ótima da PL Restrições especiais denominadas corte são adiciona das na região de soluções de uma maneira que resulta em um ponto extremo ótimo inteiro Em geral na resolução de um problema nesse método é feita sua representação em gráfico de como os cortes são usados para produzir uma solução inteira e então implementase a ideia algebricamente TAHA 2008 Mesmo após anos de pesquisa não há um código de computador que possa resolver problemas de PLI de modo consistente Contudo dos dois algoritmos de solução que vimos o BB é o mais confiável Praticamente todos os códigos comerciais de resolução de problemas de PLI são baseados em BB Em geral o método de planos de corte é difícil e incerto Segundo Hillier e Lieberman 2013 esse progresso se deve a uma com binação de três fatores melhorias impressionantes nos algoritmos de PLI melhorias notáveis nos algoritmos de programação linear usados internamente nos algoritmos de PLI e a grande aceleração no desenvolvimento dos com putadores Contudo os algoritmos de PLI ocasionalmente também falharão na resolução de problemas bem menores até mesmo como uma centena de variáveis inteiras 103 Programação linear inteira 1 Com relação à programação linear inteira PLI marque a alternativa correta a PLI são programações lineares nas quais qualquer variável pode ou não assumir valores inteiros b Os algoritmos de PLI apresentam uma vantagem que é a sua consistência na resolução de problemas com valores inteiros c Em geral as aplicações de PLI possuem apenas uma categoria que é a categoria transformada d As variáveis são naturalmente inteiras e podem assumir valores binários 0 ou 1 ou discretos gerais Essa é uma característica da categoria transformada e Em PLI na categoria transformada o problema original que pode ou não envolver quaisquer variáveis inteiras é intratável analiticamente 2 Quanto a aplicações de programação linear inteira PLI analise as alternativas a seguir e marque a afirmativa correta a Os problemas de cobertura são os relacionados a decisões sobre o investimento ou não em projetos individuais b Os problemas de orçamento de capital em geral estão relacionados a instalações que oferecem serviços sobrepostos a várias localidades c Os problemas de cobertura abordam situações em que a atividade econômica implica em dois tipos de custos uma taxa inicial fixa e um custo variável d Há modelos de problemas de restrições ouou e seentão em que a transformação não muda a natureza de ou ou de dependência das restrições e Os problemas de carga fixa são caracterizados pelas variáveis xj j 12n são binárias Os coeficientes do lado esquerdo das restrições são 0 ou 1 O lado direito de cada restrição é da forma 1 A função objetivo minimiza c1x1 c2x2 cnxn em que cj 0 para todo j 1 2 n 3 Com relação aos algoritmos de programação inteira marque a alternativa correta a Para todo problema de PLI existe um problema de programação linear correspondente no qual as restrições de não fracionariedade são mantidas b Uma possível abordagem para a solução de problemas de PLI é resolver seus problemas correspondentes relaxados sem arredondar as variáveis de decisão para o maior ou menor inteiro mais próximo c Dois métodos gerais foram desenvolvidos para gerar as restrições especiais na etapa 3 o método branchandbound BB e o método de planos de corte d Os métodos branchandbound BB e de planos de corte são consistentemente efetivos Pesquisa operacional 104 em termos computacionais e O algoritmo de corte ao contrário do algoritmo BB não começa na solução contínua ótima da PL 4 O método de solução de problemas de programação linear inteira PLI utilizando o branchandbound BB é operacionalizado em cinco passos Com relação a esses passos marque a alternativa correta a O passo 1 é a escolha de uma variável de decisão fracionária em z do PIR b O passo 2 é escolher um SP c O passo 3 é resolver o PLI relaxado d O passo 4 é repetir o passo 3 usando SP2 e a variável de decisão fracionária x1 e O passo 5 é repetir o passo 3 usando SP5 e a variável de decisão fracionária x1 5 Ainda sobre aspectos gerais que envolvem a programação linear inteira PLI marque a alternativa correta a Nos problemas de PLI não há a necessidade de algumas ou todas as variáveis de decisão terem de se restringir a valores inteiros b Há poucas aplicações que envolvem decisões simounão c A programação linear inteira é uma das técnicas de pesquisa operacional PO menos utilizadas d Problemas de PLI são muito mais fáceis pelo fato de não haver restrição de inteiros portanto os algoritmos disponíveis para programação inteira são em geral consideravelmente mais eficientes que o método simplex e O progresso na capacidade de resolver alguns problemas de PLI se deve a uma combinação de três fatores melhorias impressionantes nos algoritmos de PLI melhorias notáveis nos algoritmos de programação linear usados internamente nos algoritmos de PLI e a grande aceleração no desenvolvimento dos computadores 105 Programação linear inteira HILLIER F S LIEBERMAN G J Introdução à pesquisa operacional 9 ed Porto Alegre AMGH 2013 Ebook TAHA H A Pesquisa operacional uma visão geral São Paulo Pearson Prentice Hall 2008 Leitura recomendada HILLIER F S LIEBERMAN G J Introdução à pesquisa operacional 9 ed Port Alegre AMGH 2013 Ebook Pesquisa operacional 106 Encerra aqui o trecho do livro disponibilizado para esta Unidade de Aprendizagem Na Biblioteca Virtual da Instituição você encontra a obra na íntegra