Programacao Nao Linear - Conceitos e Aplicacoes

7º Aula PROGRAMAÇÃO NÃO LINEAR Objetivos de aprendizagem Ao término desta aula vocês serão capazes de entender os conceitos da programação não linear entender o raciocínio na resolução dos problemas de programação não linear entender as diferenças entre programação côncava convexa e quadrática Nesta sétima aula veremos um caso bem específico de modelagem onde nossa representação matemática dos problemas não se encacham em uma reta ou função linear que caracterizam a programação linear PL mas sim em outras formas de funções matemáticas como funções quadráticas por exemplo Bons estudos 58 Pesquisa Operacional 1 Seções de estudo Programação Não Linear 2 Programação Côncava Convexa E Quadrática 1 Programação não Linear Nesta seção faremos uma breve introdução à programação não linear mostrando suas diferenças com relação à programação linear Salientaremos ainda a dificuldade dos algoritmos na resolução desses problemas e suas possíveis consequências Resolução gráfica de problemas de programação não linear Programação côncava convexa e quadrática De acordo com Lachtermacher 2016 ao trabalhar com um grupo restrito de aspectos um modelo só será útil e adequado caso represente da maneira mais fidedigna possível o comportamento das variáveis selecionadas Esse comportamento no entanto raramente se mostra tão simples de ser trabalhado como nos problemas de programação linear Na realidade a maioria dos modelos que tratam de problemas reais apresenta algum grau de não linearidade Problemas de mix de produtos em que a margem de lucro por produto varia de acordo com a quantidade vendida e problemas de transporte com custos variáveis que dependem da quantidade enviada são apenas alguns exemplos corriqueiros nos quais o comportamento das variáveis relevantes e não linear Problemas de otimização em que a funçãoobjetivo eou pelo menos uma das restrições envolvidas não são funções lineares das variáveis de decisão são denominados problemas de programação não linear PNL ou nonlinear programming em inglês Aqui abordaremos as principais características desse tipo de problema bem como apresentaremos diversas técnicas para resolvêlos com o auxílio de uma planilha eletrônica LACHTERMACHER 2016 Um problema de programação não linear pode ser genericamente representado da seguinte forma Fonte Lachtermacher 2016 Percebemos que essa representação é ampla demais para que haja um único algoritmo capaz de resolver todos os problemas que podem ser incluídos nesse formato Os Problemas 1 2 e 3 a seguir por exemplo são extremamente diferentes entre si contudo são todos de programação não linear Fonte Lachtermacher 2016 Para entendermos claramente as diferenças entre programação linear e programação não linear vejamos alguns exemplos começando pelo Problema 4 de programação linear O conjunto de soluções viáveis do Problema 4 está representado na Figura 1 e sua solução gráfica está representada na Figura 2 Figura 1 Conjunto de soluções viáveis do Problema 4 Fonte Lachtermacher 2016 59 Figura 2 Solução gráfica do problema 4 Fonte Lachtermacher 2016 Resolver problemas lineares como esse é relativamente simples Precisamos apenas 1 definir a região viável delimitada pelas restrições 2 identificar o extremo no caso de solução ótima única da região viável em que a funçãoobjetivo apresenta o maior valor para um problema de maximização ou o menor valor para um problema de minimização No Problema 4 a solução ótima está no ponto extremo formado por x1 1 e x2 7 pois apresenta o maior valor possível para a funçãoobjetivo Z 58 Agora modificaremos o Problema 4 Manteremos a funçãoobjetivo porém trocaremos as restrições lineares 2x2 14 e 3x1 2x2 17 pela restrição não linear 4x1 2 9x2 2 144 Portanto temos agora o Problema 5 dado a seguir De acordo com Lachtermacher 2016 essa modificação introduz a não linearidade no problema modificando as fronteiras do conjunto de soluções viáveis de apenas retas para retas e curvas Nesse caso o conjunto de soluções viáveis Figura 3 tem uma fronteira delimitada por uma elipse lugar geométrico representado pela restrição introduzida e por diversas retas Figura 3 Conjunto de soluções viáveis para o Problema 5 Fonte Lachtermacher 2016 Nesse caso a funçãoobjetivo é uma reta e a metodologia para se encontrar a solução ótima é a mesma do problema de programação linear isto é ir incrementando o valor de Z até que nenhum ponto da reta pertença ao conjunto de soluções viáveis Figura4 Figura 4 Solução ótima do Problema 5 Fonte Lachtermacher 2016 Conforme podemos perceber a solução ótima ainda se situa na fronteira do conjunto de soluções viáveis No entanto nesse segundo problema a solução ótima não é mais um extremo do conjunto de soluções viáveis Essa constatação reflete uma das características dos problemas de programação não linear que e a possibilidade de a solução ótima assumir qualquer valor do conjunto de soluções viáveis não havendo a simplificação existente nos problemas de programação linear LACHTERMACHER 2016 Suponha agora o Problema 5 de otimização não linear em que todas as restrições são lineares as mesmas do Problema 4 e apenas a funçãoobjetivo e não linear O conjunto de soluções viáveis é representado na Figura 5 Assumindo que Z pode ser considerado uma constante temos que a funçãoobjetivo é uma equação quadrática uma elipse e pode ser assim desenvolvida Conforme Lachtermacher 2016 a metodologia para se encontrar a solução ótima do problema é a mesma dos problemas anteriores isto é ir incrementando o valor de Z até que nenhum ponto da respectiva elipse faça parte do conjunto de soluções viáveis Escolhendo três valores para Z temos que 60 Pesquisa Operacional Todas as três equações representam elipses no espaço R2 de x1 e x2 As equações quadráticas encontradas para os três valores escolhidos para a constante Z 3312 3676 e 3982 estão representadas na Figura 6 Figura 6 Solução ótima para o problema 6 Fonte Lachtermacher 2016 Analisando o gráfico resultante observamos que a funçãoobjetivo desse problema é uma elipse Quando o valor de Z aumenta a elipse diminui de tamanho convergindo para seu centro 8 8 Tendo em vista que o centro da elipse se encontra fora do conjunto de soluções viáveis a solução ótima do problema será o ponto do conjunto de soluções viáveis em que a curva da funçãoobjetivo assumir o maior valor de Z Nesse caso o ponto x1 272 e x2 468 em que a elipse Z 3676 tangencia o conjunto de soluções viáveis O principal objetivo deste exemplo é verificar que a solução ótima encontrase fora dos pontos extremos do conjunto de soluções viáveis independentemente da forma do conjunto dessas soluções Com base nos problemas apresentados apesar de nem sempre se encontrar um extremo a solução ótima de problemas não lineares estará sempre nas fronteiras do conjunto de soluções viáveis Mas será que essa afirmativa é verdadeira ou é apenas uma conclusão precipitada Consideremos agora o Problema 7 Figura 7 com as mesmas restrições do Problema 6 porém com uma nova funçãoobjetivo outra elipse Fonte Lachtermacher 2016 O conjunto de soluções viáveis é o mesmo do exemplo anterior uma vez que o conjunto de restrições é o mesmo nos dois exemplos Admitindo que Z pode ser considerado uma constante temos que a funçãoobjetivo é uma equação quadrática uma elipse e pode ser desenvolvida da seguinte maneira Escolhendo três valores para Z temos que De acordo com Lachtermacher 2016 a metodologia para encontrar a solução ótima é a mesma do Problema 6 isto é encontrar o maior valor de Z em que pelo menos um dos pontos da respectiva curva pertença ao conjunto de soluções viáveis O gráfico das equações quadráticas encontradas para os três valores escolhidos para a constante Z 100 85 e 62 e o conjunto de soluções viáveis do problema estão representados na Figura 7 Analisando os gráficos resultantes observamos que funçãoobjetivo desse problema é uma elipse na qual o valor de Z aumenta conforme a curva converge para seu centro 2 2 Tendo em vista que o centro da elipse encontra se dentro do conjunto de soluções viáveis a solução ótima do problema será esse ponto obtido pelo maior valor de Z Nesse caso o ponto x1 2 e x2 2 que leva Z ao valor de 100 Figura 7 Conjunto de soluções viáveis e solução ótima do Problema 7 Fonte Lachtermacher 2016 Sendo assim diferentemente dos problemas anteriores verificamos que a solução que maximiza o valor da função objetivo é encontrada não mais nas fronteiras do conjunto de 61 soluções viáveis mas sim no seu interior Utilizando o mesmo conjunto de soluções viáveis para diferentes problemas verificamos que dependendo da funçãoobjetivo do modelo a solução ótima de um problema de programação não linear pode estar localizada tanto em um extremo como na fronteira ou até mesmo em um ponto interno do conjunto de soluções viáveis Essa característica torna os problemas de programação não linear muito mais complexos que os de programação linear pois para descobrir qual solução viável fornece o valor ótimo para a funçãoobjetivo é preciso pesquisar todos os valores possíveis que se encontram no conjunto de soluções viáveis um conjunto infinito de pontos Diante da dificuldade de encontrar a solução ótima de um PNL a utilização de ferramentas como o Solver do Excel toma se imprescindível Todavia a validação do resultado obtido por esses algoritmos requer que sejam feitas algumas considerações sobre as características das funções que compõem o modelo 2 Programação Côncava Convexa e Quadrática Ao trabalhar com problemas de programação não linear nosso principal interesse é saber se algoritmos eletrônicos como o Solver do Excel entre outros encontrarão a solução ótima do problema sem dificuldades O trabalho do algoritmo consiste em a partir de uma condição inicial seguir passo a passo calculando valores para as variáveis do modelo e checando o comportamento da funçãoobjetivo No momento em que o valor da função objetivo inverte de tendência ou seja deixa de crescer para diminuir caso de maximização ou deixa de diminuir para começar a crescer caso de minimização o algoritmo supõe que encontrou um ponto ótimo máximo ou mínimo da função que pode ser tanto um extremo local quanto global LACHTERMACHER 2016 No entanto com esse procedimento o algoritmo não garante que a solução encontrada seja a solução global pois a princípio não há certeza se a função analisada não ira inverter seu comportamento novamente Se utilizarmos o Solver para encontrar o ponto máximo da função da Figura 8 por exemplo é bastante provável que o algoritmo encontre diversas soluções Dependendo dos valores com os quais iniciamos a otimização o algoritmo pode indicar o ponto 1 ou o ponto 3 como o ponto que maximiza a função sendo que no entanto apenas o ponto 3 é o máximo global da função e portanto o resultado que buscamos Figura 8 Função com vários máximos Fonte Lachtermacher 2016 Diante da incerteza quanto ao resultado apresentado pelo algoritmo precisamos saber se o tipo do modelo permite que a solução dada por ele seja assumida como a solução ótima do problema Devemos relembrar alguns conceitos matemáticos antes de prosseguir Uma função é dita convexa se ela tem a forma da Figura 9 isto é se tem valores marginais crescentes ou seja se a derivada vai de valores negativos para valores positivos Uma maneira alternativa de verificar se uma função é convexa é unir quaisquer dois pontos da função e verificar se o segmento de reta que os une está sempre acima ou sobre a função Se isso ocorrer poderemos também dizer que a função é convexa Figura 9 Função convexa Fonte Lachtermacher 2016 Uma função é dita côncava se tem a forma da Figura 10 isto é se possui valores marginais decrescentes Uma maneira alternativa de verificar se uma função é côncava é unir quaisquer dois pontos da função e verificar se o segmento de reta que os une está sempre abaixo ou sobre a função Se isso ocorrer poderemos também dizer que a função é côncava Figura 10 Função côncava Fonte Lachtermacher 2016 O último conceito matemático relevante é o de conjunto convexo Um conjunto é dito convexo se todos os pontos que formam o segmento de reta que une quaisquer dois pontos desse conjunto também pertencem ao conjunto Figura 11 Figura 11 Conjunto convexo 62 Pesquisa Operacional Fonte Lachtermacher 2016 Quando o modelo não apresenta restrições essa análise fica bastante simples O fato de a funçãoobjetivo ser côncava é condição necessária e suficiente para garantir que o máximo encontrado pelo algoritmo seja o máximo global De forma análoga o fato de a funçãoobjetivo de um PNL sem restrições ser convexa é condição necessária e suficiente para garantir que o mínimo encontrado pelo algoritmo seja global LACHTERMACHER 2016 Retomando a aula Ao chegar ao fi nal da sétima aula vamos recordar o que aprendemos 1 Programação Não Linear Nessa sétima aula focamos nossa atenção nos conceitos da programação não linear Vimos exemplos de modelagem e também as diferenças conceituais dos três principais modelos de programação não linear que é a côncava a convexa e a quadrática 2 Programação Côncava Convexa e Quadrática Já nessa segunda parte da aula aprofundamos as características específicas da programação côncava convexa e quadrática explorando apenas uma ótica mais conceitual visto que a resolução de problemas dessa espécie requer uma programação computacional muito específica Hillier FS e Lieberman GJ Introdução à Pesquisa Operacional 8ª edição São Paulo McGrawHill 2006 Lachtermacher G Pesquisa operacional na tomada de decisões 5ª edição São Paulo Prentice Hall 2016 Vale a pena ler Vale a pena Taha H A Pesquisa Operacional 8ª edição São Paulo Pearson 2008 Minhas anotações