Solução de Problemas em Pesquisa Operacional: Múltiplos Objetivos e Programações Dinâmica e Não Linear

PESQUISA OPERACIONAL Organizador Rodrigo Rodrigues Tópicos complementares múltiplos objetivos programação dinâmica e não linear Objetivos de aprendizado Ao final deste texto você deve apresentar os seguintes aprendizados Definir solução de problemas considerando múltiplos objetivos Descrever as características e os problemas de uma programação dinâmica Identificar problemas de uma programação não linear Introdução Uma etapa fundamental na formulação de um modelo de pesquisa operacional PO é a construção da função objetivo É nesse sentido que o responsável pelas decisões desenvolve uma medida quantitativa de desempenho para cada um dos objetivos finais que são identificados durante a definição do problema Neste texto você vai conhecer os conceitos básicos de problemas com múltiplos objetivos e as características principais das programações dinâmica e não linear Solução de problemas considerando múltiplos objetivos A maioria dos modelos estudados é baseada na otimização de uma única função objetivo Há situações em que múltiplos objetivos conflitantes podem ser mais adequados Por exemplo políticos prometem reduzir a dívida nacional e ao mesmo tempo oferecem redução da carga tributária Em tais situações é impossível achar uma solução única que otimize essas duas metas confli tantes A programação de metas é o meio pelo qual se busca uma solução de compromisso baseada na importância relativa de cada objetivo Como podemos otimizar um modelo multiobjetivos com metas possivel mente conflitantes Dois métodos foram desenvolvidos para essa finalidade o método de pesos e o método hierárquico Ambos os métodos são baseados na conversão de múltiplos objetivos em uma única função O método de pesos forma uma única função objetivo que consista na soma ponderada das metas Já o método hierárquico otimiza as metas uma por vez começando com a meta de prioridade mais alta e terminando com a de prioridade mais baixa sem nunca degradar a qualidade da meta de prioridade mais alta A solução dada pelo método de pesos nada mais é do que uma programação linear comum O método hierárquico acarreta em considerações adicionais em relação ao algoritmo que se enquadram muito bem no domínio do método simplex TAHA 2008 Programação dinâmica A programação dinâmica PD é um método matemático útil para uma sequên cia de tomadas de decisão interrelacionadas Ela apresenta um procedimento sistemático para determinar a combinação de decisões ótimas Diferentemente da programação linear não há uma formulação matemática padrão para um problema de programação dinâmica Pelo contrário a programação dinâmica é um tipo genérico de metodologia para a resolução de problemas e para cada situação são desenvolvidas equações particulares Por isso segundo Hillier e Liebermann 2013 é necessário certo grau de engenhosidade e de insight na estrutura geral dos problemas de programação dinâmica para reconhecer quando e como um problema pode ser resolvido pelos procedimentos dessa mesma programação A PD é utilizada como método para realizar uma sequência de decisões interrelacionadas Ela exige a formulação de uma relação recursiva apropriada para cada problema individual Contudo ela resulta em grandes economias em termos de processamento em comparação com o emprego de enumeração exaustiva para encontrar a melhor combinação de decisões principalmente para problemas de grande porte Como exemplo supomos que um problema possui 10 estágios com 10 estados e 10 decisões possíveis a cada estágio então a enumeração exaustiva deve considerar até 10 bilhões de combinações ao passo que a programação dinâmica precisaria fazer não mais que um milhar Pesquisa operacional 108 de cálculos 10 para cada estado a cada estágio Consideramos apenas a programação dinâmica com um número finito de estágios Essa programação determina a solução ótima de um problema de multiva riáveis decompondoo em estágios sendo que cada estágio compreende um subproblema com uma única variável A vantagem da decomposição é que o processo de otimização em cada estágio envolve uma só variável uma tarefa mais simples com relação ao cálculo do que lidar com todas as variáveis ao mesmo tempo Um modelo de PD é basicamente uma equação recursiva que une os diferentes estágios do problema de modo que garanta que a solução ótima viável de cada estágio também seja ótima e viável para o problema inteiro Segundo Taha 2008 os cálculos em PD são feitos recursivamente de modo que a solução ótima de um subproblema é usada como dado de entrada para o subproblema seguinte Quando o último subproblema é resolvido a solução ótima para o problema inteiro está à mão A maneira como os cálculos recursivos são executados depende de como o problema original é decom posto Particularmente os subproblemas em geral estão ligados por restrições em comum À medida que passamos de um subproblema para o seguinte a viabilidade dessas restrições em comum deve ser mantida Programação não linear Em pesquisa operacional PO o papel fundamental da programação linear é refletido de forma aprimorada Uma suposição central da programação linear é que todas as suas funções função objetivo e funções de restrição sejam lineares Mesmo que essa hipótese seja válida para vários problemas práticos com frequência ela não se verifica Então muitas vezes é necessário lidar diretamente com problemas de programação não linear De um modo geral o problema de programação não linear é encontrar x x1 x2 xn de modo a maximizar fx sujeito a gix bi para i 1 2 m e x 0 em que f x e os gi x sejam funções dadas das n variáveis de decisão 109 Tópicos complementares múltiplos objetivos programação dinâmica e não linear Existem diversos tipos de problemas de programação não linear de acordo com as características das funções fx e gix São usados diferentes algorit mos para os diversos tipos Para determinados tipos em que as funções têm formas simples os problemas podem ser resolvidos de modo relativamente eficiente Para outros porém até mesmo a resolução de problemas pequenos é um verdadeiro desafio HILLIER LIEBERMANN 2013 Devido à existência de muitos tipos e de muitos algoritmos a programação não linear é um assunto particularmente extenso contudo abordaremos de forma reduzida Desse modo é importante um estudo complementar Veja as indicações no final deste texto Tipos de problema de programação não linear Existem diferentes formas e formatos de problemas de programação não linear Ao contrário do método simplex para programação linear não há um algoritmo único capaz de resolver todos esses tipos variados de problemas Ao contrário disso foram desenvolvidos algoritmos para várias classes tipos especiais individuais de problemas de programação não linear As classes mais importantes são apresentadas brevemente neste texto Para simplificar partiremos do pressuposto de que os problemas foram formulados ou refor mulados na forma genérica da qual já falamos Otimização irrestrita Os problemas de otimização irrestrita são aqueles que não apresentam restri ções de modo que o objetivo seja simplesmente maximizar fx ao longo de todos os valores de x x1 x2 xn Pesquisa operacional 110 A condição necessária para que determinada solução x x seja ótima quando fx for uma função diferenciável é que A condição de fx ser uma função côncava também é suficiente de modo que encontrar a solução para x limitase a resolver o sistema de n equações obtidas configurandose as n derivadas parciais iguais a zero Infelizmente para funções fx não lineares essas equações muitas vezes também serão não lineares Nesse caso dificilmente você será capaz de encontrar analiti camente sua solução simultânea Muitos algoritmos para problemas restritos são modelados de forma que sejam capazes de se concentrar em uma versão irrestrita do problema durante parte de cada iteração Quando uma variável xj não apresentar uma restrição de não negatividade xj 0 a condição precedente necessária e quem sabe suficiente muda rapidamente para f xj em x x se xj em x x se xj 0 0 0 0 para cada j deste Essa condição é ilustrada na Figura 1 em que a solução ótima para um problema com uma única variável encontrase em x 0 embora a derivada ali seja negativa em vez de zero Como esse exemplo tem uma função côncava a ser maximizada sujeita a uma restrição de não negatividade ter a derivada menor ou igual a 0 em x 0 é uma condição tanto necessária quanto suficiente para x 0 ser ótima A Figura 1 é um exemplo que ilustra como uma solução ótima pode estar em um ponto em que uma derivada é negativa em vez de zero pois esse ponto recai sobre o contorno de uma restrição de não negatividade 111 Tópicos complementares múltiplos objetivos programação dinâmica e não linear Figura 1 Condição de fx sendo uma função côncava com uma ótima solução e em derivada negativa Fonte Hillier e Liebermann 2013 A próxima classe de problemas é dedicada aos problemas que têm algumas restrições de não negatividade mas nenhuma restrição funcional São um caso especial m 0 Otimização linearmente restrita De acordo com Hillier e Liebermann 2013 as características de problemas de otimização linearmente restrita são restrições que se ajustam completamente à programação linear de modo que todas as funções de restrição gix sejam lineares mas com a função objetivo fx não linear O problema é conside ravelmente simplificado tendo apenas uma função não linear para levar em conta junto com uma região de soluções viáveis de programação linear Foi desenvolvida uma série de algoritmos especiais com base na extensão do método simplex para considerar a função objetivo não linear Pesquisa operacional 112 Programação quadrática A programação quadrática é um importante caso especial Os problemas de programação quadrática também possuem restrições lineares porém agora a função objetivo fx deve ser quadrática Com isso a única diferença entre um problema desses e um problema de programação linear é que alguns dos termos na função objetivo envolvem o quadrado de uma variável básica ou o produto de duas variáveis Foram desenvolvidos diversos algoritmos para esse caso sob a hipótese adicional de que fx seja uma função côncava A programação quadrática é muito importante devido a essas formulações que surgem naturalmente em diversas aplicações e porque uma metodologia comum para solucionar problemas de otimização genéricos linearmente res tritos é resolver uma sequência de aproximações de programação quadrática Programação convexa A programação convexa abrange uma ampla gama de problemas que na realidade engloba como casos especiais todos os tipos precedentes quando fx é uma função côncava a ser maximizada Continuando a supor a forma de problema genérico inclusive a maximização apresentado no início do texto as hipóteses são de que 1 fx seja uma função côncava 2 cada gix seja a função convexa Essas hipóteses são suficientes para garantir que um máximo local seja um máximo global Caso o objetivo fosse minimizar fx sujeito a gix bi ou então gixbi para i 1 2 m a primeira hipótese seria fazer uma alteração para que fx fosse uma função convexa visto que isso é o neces sário para garantir que um mínimo local seja um mínimo global HILLIER LIEBERMANN 2013 Há ainda a programação separável que é um caso especial de programação convexa em que a única hipótese adicional é 3 Todas as funções fx e gix sejam funções separáveis 113 Tópicos complementares múltiplos objetivos programação dinâmica e não linear Uma função separável é uma função na qual cada termo envolve apenas uma única variável assim a função tornase separável em uma soma de funções de variáveis individuais Se fx for uma função separável ela pode ser expressa por exemplo Em que cada função fjxj inclui apenas os termos que envolvem apenas xj Na terminologia da programação linear problemas de programação separável atendem à hipótese da aditividade mas quando qualquer uma das funções fjxj for não linear violam a hipótese da proporcionalidade É uma função separável pois ela pode ser expressa como fx1 x2 f1 x1 f2 x2 Na qual f1x1 126x1 9x2 2 e f2x2 182x2 13x2 2 são cada uma delas uma função de uma única variável x1 e x2 respectivamente É importante distinguir problemas de programação separável de outros de programação convexa pois qualquer um desses problemas pode ser aproximado por um problema de programação linear de modo que o eficiente método simplex possa ser utilizado Programação não convexa A programação não convexa engloba todos os problemas de programação não linear que não atendem às hipóteses da programação convexa Então mesmo que você consiga encontrar um máximo local não há nenhuma garantia de que ele também seja um máximo global Portanto não existe um algoritmo que encontrará uma solução ótima para todos esses tipos de problema Entretanto não existe um algoritmo que seja relativamente adequado para explorar várias partes da região de soluções viáveis e talvez encontrar um máximo global no processo Pesquisa operacional 114 Certos tipos específicos de problemas de programação não convexa podem ser resolvidos sem grandes dificuldades por métodos especiais Dois desses tipos particularmente importantes são discutidos a seguir de forma breve Programação geométrica Ao aplicar a programação não linear a problemas de desenvolvimento de engenharia bem como a certos problemas econômicos e de estatística a função objetivo e as funções de restrição assumem frequentemente essa forma Nesses casos ci e aij representam tradicionalmente constantes físicas e xj são variáveis de projeto Essas funções geralmente não são convexas nem côncavas e por isso as técnicas de programação convexa não podem ser aplicadas diretamente para esses problemas de programação geométrica Contudo há um caso importante no qual o problema pode ser transformado em um problema de programação convexa equivalente como nos casos em que todos os coeficientes ci em cada função são estritamente positivos de modo que as funções sejam polinômios positivos generalizados posinomiais e que a função objetivo seja minimizada O problema de programação convexa equivalente com variáveis de decisão y1 y2 yn é então obtido configurandose Ao longo do modelo original de modo que agora um algoritmo de programa ção convexa possa ser aplicado Também foram desenvolvidos procedimentos de resolução alternativos para resolver esses problemas de programação posi nomial bem como para problemas de programação geométrica de outros tipos 115 Tópicos complementares múltiplos objetivos programação dinâmica e não linear Programação fracionária Supomos que a função objetivo encontrese na forma de uma fração ou seja a razão de duas funções Os problemas de programação fracionária surgem por exemplo quando se está maximizando a razão entre produção e horas de mão de obra gastas produtividade ou entre lucro e capital investido taxa de retorno ou ainda entre valor esperado e desvio padrão de alguma medida de desempenho para uma carteira de investimentos retornorisco Foram desenvolvidos alguns procedimentos especiais para certas formas de f1x e f2x A mais simples e direta metodologia para solucionar um problema de programação fracionária quando é possível realizála é transformálo em um problema equivalente de tipo padrão para o qual já haja procedimentos de resolução eficientes Por exemplo suponha que fx seja da forma programação fracionária linear em que c e d são vetoreslinha x é um vetorcoluna e c0 e d0 são escalares Suponha também que as funções de restrição gix sejam lineares de modo que as restrições na forma matricial serão Ax b e x 0 Sob outras hipóteses amenas adicionais podemos transformar o problema em um problema de programação linear equivalente fazendo que de modo que x yt Esse resultado leva a maximizar z cy c0t sujeito a Ay bt 0 Pesquisa operacional 116 Dy d0t 1 e y 0 t 0 que podem ser resolvidos pelo método simplex De modo genérico o mesmo tipo de transformação pode ser usado para converter um problema de programação fracionária com f1x côncava f2x convexa e gix convexa em um problema de programação convexa equivalente Problema da complementaridade O problema da complementaridade busca encontrar uma solução viável para o conjunto de restrições W f z w 0 z 0 que também satisfaçam a restrição de complementaridade wtz 0 Aqui w e z são vetorescoluna f é determinada função avaliada por vetores e o t sobrescrito representa a transposição O problema não possui nenhuma função objetivo e portanto tecnicamente não é um problema de programação não linear totalmente desenvolvido Chamase problema da complementaridade em virtude das relações de complementaridade que Wi 0 ou zi 0 ou então ambos para cada i 12p Um caso especial importante é aquele do problema de complementaridade linear em que F z q Mz em que q é um vetorcoluna dado e M é uma matriz p x p dada Foram desenvolvidos algoritmos eficientes para solucionar esse problema sob diversas hipóteses sobre as propriedades da matriz M Um tipo envolve pivotar a partir 117 Tópicos complementares múltiplos objetivos programação dinâmica e não linear de uma solução básica viável BV para a próxima de modo muito parecido com o método simplex para programação linear HILLIER LIEBERMANN 2013 Além de ter aplicações em programação não linear os problemas de comple mentaridade possuem aplicações na teoria dos jogos problemas de equilíbrio econômico bem como problemas de equilíbrio de engenharia Há grande ênfase nos últimos anos no desenvolvimento de pacotes de software confiáveis e de alta qualidade para uso geral na aplicação dos melhores desses algo ritmos Por exemplo diversos pacotes de software poderosos como o Minos foram desenvolvidos no Laboratório de Otimização de Sistemas da Universidade de Stanford Problemas práticos de otimização frequentemente envolvem comporta mento não linear que deve ser levado em consideração Algumas vezes é possível reformular essas não linearidades para se adequar ao formato da programação linear como pode ser feito por exemplo no caso de problemas de programação separável Entretanto com frequência é necessário usar uma formulação de programação não linear Ao contrário do método simplex para programação linear não há um algoritmo eficiente de propósito genérico que possa ser utilizado para resolver todos os problemas de programação não linear Na verdade nenhum método pode resolver de maneira bem satisfatória alguns desses problemas Contudo está se obtendo progresso considerável para algumas classes importantes de problemas entre elas programação quadrática programação convexa e certos tipos especiais de programação não convexa Existe uma série de algoritmos disponíveis que frequentemente têm bom desempenho para esses casos Alguns desses algoritmos incorporam procedimentos altamente eficientes para otimização irrestrita para uma parte de cada iteração e outros usam uma sucessão de aproximações quadráticas ou lineares para o problema original Pesquisa operacional 118 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 Leituras recomendadas LACHTERMACHER G Pesquisa operacional na tomada de decisões São Paulo Pearson Prentice Hall 2009 WAGNER HM Pesquisa operacional 2 ed Rio de Janeiro PrenticeHall do Brasil 1996 119 Tópicos complementares múltiplos objetivos programação dinâmica e não linear Encerra aqui o trecho do livro disponibilizado para esta Unidade de Aprendizagem Na Biblioteca Virtual da Instituição você encontra a obra na íntegra Conteúdo saGAH SOLUÇÕES EDUCACIONAIS INTEGRADAS