Problema Dual, Metodo Dual Simplex e Analise de Sensibilidade em Programacao Linear

DESCRIÇÃO O problema dual o método dualsimplex e a relevância da análise de sensibilidade PROPÓSITO Dominar a técnica da dualidade facilitará solução de problemas complexos de programação linear Por sua vez a análise de sensibilidade o ajudará a responder a diversas questões gerenciais relacionadas a solução de problemas de programação linear incerteza ou erros de estimativa quanto aos coeficientes do modelo PREPARAÇÃO Para o estudo deste conteúdo são necessários uma calculadora e um software editor de planilhas eletrônicas com o add in do Solver habilitado Conhecimento sobre o método simplex e modelos de programação linear OBJETIVOS MÓDULO 1 Aplicar a dualidade para solução de problemas de programação linear MÓDULO 2 Avaliar a sensibilidade da solução obtida para problemas de programação linear em relação à incerteza ou erros de estimativa quanto aos coeficientes do modelo INTRODUÇÃO Você já deve saber como desenvolver modelos matemáticos que representem de forma simplificada um problema complexo para o qual desejamos encontrar a solução ótima utilizando equações lineares Esses modelos nos auxiliam no processo de tomada de decisão na medida em que nos permitem minimizar custos maximizar resultados e aprimorar as configurações operacionais em diversos problemas práticos importantes Problemas de programação linear tratam de alguns problemas representativos que você poderia enfrentar no ambiente empresarial tais como o problema da mistura a decisão entre fabricar ou comprar o problema do planejamento de produção e de estoques o problema de transporte e de transbordo e problemas de alocação É possível solucionálos por meio do método gráfico do método simplex ou com o auxílio de ferramentas computacionais que facilitam bastante o nosso trabalho Entretanto é importante compreender que encontrar a solução ótima para um problema nem sempre significa que ele esteja resolvido No processo de modelagem assumimos premissas e fazemos estimativas às vezes incertas com relação aos custos ou mesmo quanto à demanda ou à disponibilidade de recursos em determinada situação ou em um período A análise de sensibilidade trata exatamente de avaliar o impacto dessas incertezas na solução ótima avaliando os erros de estimativa quanto aos coeficientes do modelo ou quanto a mudanças que possam ocorrer Lachtermacher 2009 reforça a importância de realizar essa análise pósotimização verificando as possíveis variações dos valores dos coeficientes da função objetivo dos coeficientes e das constantes das restrições sem que a solução ótima seja alterada Destacase que a análise de sensibilidade está relacionada ao problema dual associado ao primal A dualidade nos permite além de análises econômicas como variações marginais resolver o problema dependendo do número de restrições e de variáveis de forma mais eficiente computacionalmente MÓDULO 1 Aplicar a dualidade para solução de problemas de programação linear APRESENTAÇÃO DO TEMA O vídeo aborda a importância da análise de sensibilidade e da dualidade O PROBLEMA DUAL E O MÉTODO DUALSIMPLEX O conceito de dualidade está relacionado à possibilidade do tratamento de duas naturezas distintas em uma mesma entidade Arenales et al 2007 destacam que diversos fenômenos físicos e químicos podem ser representados por modelos com estruturas e comportamentos iguais porém interpretados de formas distintas Especificamente em programação matemática podemos afirmar que todo problema de programação linear tem um dual correspondente sendo o problema original denominado primal Entender o conceito de dualidade é importante para interpretar a solução de problemas de otimização bem como para o aprendizado de tópicos mais avançados em programação matemática Métodos de decomposição por exemplo têm base na teoria primaldual Além disso podemos obter melhorias em termos de algoritmos ao levar em conta a contraparte dual tal como no método dualsimplex Existe uma série de relações e teoremas entre o primal e o dual na qual se destacam O dual do dual é o primal Se um dos dois problemas apresenta uma solução ótima o outro necessariamente também sendo que o valor de ambas as soluções coincide teorema da dualidade forte Uma solução viável do problema dual representa um limite superior para o problema primal teorema da dualidade fraca Se o primal é um problema inviável o seu dual é ilimitado Se o primal é um problema ilimitado o seu dual é inviável O número de variáveis do dual é igual ao número de restrições do primal O número de restrições do dual é igual ao número de variáveis do primal O sentido da otimização é sempre inverso entre o primal e o dual ou seja se o primal é um problema de maximização o dual é de minimização Por sua vez se o primal for um problema de minimização seu dual é de maximização Os termos independentes do primal surgem como coeficientes na função objetivo no dual e viceversa Os termos constantes das restrições do dual são os coeficientes das variáveis da função objetivo do primal enquanto os coeficientes das variáveis da função objetivo do dual são os termos constantes das restrições do primal A matriz dos coeficientes do dual é a transposta da matriz dos coeficientes do primal Complementaridade das folgas Seja fi a variável de folga associada à restrição i Seja yi a variável dual associada à restrição i Assim yifi 0 para todo i O yi representa o preçosombra valor marginal de um recurso Logo quando fi 0 yi 0 Quando si 0 yi 0 Em suma existe um conjunto de regras para se obter o dual de um problema de programação linear sintetizado na tabela a seguir Par assimétrico Problema primal dual Problema dual primal Maximizar Minimizar Termos independentes Coeficientes da Função Objetivo FO Coeficientes da Função Objetivo FO Termos independentes iésima linha de coeficientes tecnológicos iésima coluna de coeficientes tecnológicos jésima coluna de coeficientes tecnológicos jésima linha de coeficientes tecnológicos Restrição com relação tipo Variável tipo Não negativa Não positiva Sem restrição de sinal Variável tipo Restrição com relação tipo Não negativa Não positiva Sem restrição de sinal Atenção Para visualização completa da tabela utilize a rolagem horizontal Tabela Conversão de problemas em geral Com base nas regras apresentadas na tabela conseguimos achar o dual de qualquer problema de programação linear Vamos treinar determinando o dual para o seguinte problema de programação linear primal Max ZP 6X1 4X 2 10X3 X1 3X2 2X3 15 2X2X3 5 2X1 X2 5X3 10 X1 X2 X3 0 Atenção Para visualização completa da equação utilize a rolagem horizontal Se o primal é um problema de maximização sabemos que o dual é um problema de minimização Sabemos também que os termos independentes do primal são os coeficientes da função objetivo do dual Desse modo a função objetivo do dual é Min ZD 15Y1 5Y2 10Y3 Atenção Para visualização completa da equação utilize a rolagem horizontal Sabemos ainda que os coeficientes da função objetivo do primal são os termos independentes do dual A matriz dos coeficientes do dual é a transposta da matriz dos coeficientes do primal Além disso variáveis não negativas no primal implicam restrições do tipo no dual Assim conseguimos determinar as restrições para o dual que são Y1 Y3 6 3Y1 2Y2 Y3 4 2Y1 Y2 5Y3 10 Atenção Para visualização completa da equação utilize a rolagem horizontal Ainda é preciso determinar os tipos de variáveis Como a restrição 1 do primal é temos que y1 0 A restrição 2 do primal é logo y2 é não positiva y2 0 A restrição 3 é uma equação logo y3 é irrestrita y3 IR Assim chegamos à conclusão de que o dual para o problema apresentado é Min ZD 15Y1 5Y2 10Y3 sa Y1 Y3 6 3Y1 2Y2 Y3 4 2Y1 Y2 5Y3 10 Y1 0 Y2 0 Y3 IR Atenção Para visualização completa da equação utilize a rolagem horizontal Para fixar a aprendizagem veja agora como determinar o dual do problema a seguir Min W 50Y1 20 Y2 30Y3 80Y4 sa 400Y1 200Y2 150Y3 500Y4 500 3Y1 2Y2 6 2Y1 2Y2 4Y3 4Y4 10 2Y1 4Y2 Y3 5Y4 8 Y1 Y2 Y3Y4 0 Atenção Para visualização completa da equação utilize a rolagem horizontal Se o primal é um problema de minimização sabemos que o dual é um problema de maximização Os termos independentes do primal são os coeficientes da função objetivo do dual Desse modo a função objetivo do dual é Max Z 500X1 6X2 10X3 8X4 Atenção Para visualização completa da equação utilize a rolagem horizontal Os coeficientes da função objetivo do primal são os termos independentes do dual e a matriz dos coeficientes do dual é a transposta da matriz dos coeficientes do primal Além disso variáveis não negativas no primal implicam restrições do tipo no dual Logo as restrições para o dual são 400X1 3X2 2X3 2X4 50 200X1 2X2 2X3 4X4 20 150X1 4X3 X4 30 500X1 4X3 5X4 80 Atenção Para visualização completa da equação utilize a rolagem horizontal Por fim devese determinar os tipos de variáveis Como as restrições do primal são as variáveis X são não positivas X 0 Assim chegamos à conclusão de que o dual para o problema apresentado é Max Z 500X1 6X2 10X3 8X4 sa 400X1 3X2 2X3 2X4 50 200X1 2X2 2X3 4X4 20 150X1 4X3 X4 30 500X1 4X3 5X4 80 X1 X2 X3 X4 0 Atenção Para visualização completa da equação utilize a rolagem horizontal INTERPRETAÇÃO ECONÔMICA DO PROBLEMA DUAL O número de variáveis do problema dual é igual ao número de restrições do problema primal Vale notar que as variáveis originais do problema dual estão associadas às variáveis de folgaexcesso do problema primal De fato as variáveis originais do problema dual yi representam economicamente o valor marginal do recurso da restrição i em relação ao valor da função objetivo ou seja o preçosombra Tratase do valor pelo qual a função objetivo seria melhorada caso a quantidade do recurso i fosse aumentada em uma unidade Como foi apresentado há o teorema da complementaridade das folgas em que yifi 0 para todo i Esse teorema pode ser interpretado em função do preçosombra como descrito a seguir Quando a variável de folga fi para a restrição i é não negativa há sobra do recurso i Assim não faz sentido ter um valor marginal para o recurso de modo que o preçosombra yi deve ser zero Quando a variável de folga fi para a restrição i é nula todo o recurso i está sendo consumido não havendo assim sobra dele Logo o preçosombra deve ser maior que zero O conceito de preçosombra pode parecer um pouco abstrato então vamos trabalhar um exemplo para ajudar na compreensão desse conceito e na interpretação econômica do problema dual Caso Fitwear SA A Fitwear SA é uma confecção de roupas esportivas tendo uma linha fitness feminina que produz roupas de ginástica exclusivas para mulheres como tops e calças de lycra Cada top de ginástica vendido por 8000 gasta 2000 de matériaprima como tecido e alinhamentos e 3200 de mão de obra Trinta minutos de corte e 15 minutos de costura são demandados para a confecção de uma unidade desse produto Cada calça de ginástica vendida por 12000 utiliza 3500 de matériaprima como tecido e alinhamentos e 4000 de mão de obra Quinze minutos de corte e 30 minutos de costura são demandados para a confecção de uma unidade desse produto Por semana a Fitwear só pode contar com 100 horas de corte e 160 horas de costura Qual deve ser o plano de produção quantos tops e quantas calças de ginástica devem ser produzidas para maximizar os lucros da empresa Consideramos as seguintes variáveis X1 Número de tops de ginástica confeccionados a cada semana X2 Número de calças de ginástica confeccionadas a cada semana Temos a seguinte formulação matemática Max Z 28X1 40X2 sa 05X1 025X2 100 restrição de horas de corte 025X1 0 5X2 160 restrição de horas de costura X1 X2 0 restrição de não negatividade das variáveis de decisão Atenção Para visualização completa da equação utilize a rolagem horizontal TEORIA NA PRÁTICA Agora imagine que uma grande indústria têxtil estivesse disposta a comprar todos os recursos da Fitwear sua capacidade de corte e de costura Qual seria o preço de equilíbrio mínimo a partir do qual a Fitwear poderia abrir mão da fabricação RESOLUÇÃO Sejam y₁ e y₂ os preços de equilíbrio referentes à capacidade da Fitwear em horas de corte e de costura respectivamente A grande indústria têxtil deseja então minimizar o total a ser pago pela capacidade de corte e de costura da Fitwear ou seja a função objetivo do dual está relacionada ao ponto de vista do comprador Miniminar w 100y₁ 160y₂ Total a ser pago pela capacidade horas de corte Total a ser pago pela capacidade horas de costura Função objetivo O comprador deseja o menor preço mas este deve ser atraente o suficiente para que a Fitwear considere a venda Assim sendo para comprar toda a capacidade horas de corte e de costura necessária para confeccionar um top de ginástica o ágio a ser pago deve ser no mínimo o que a Fitwear lucraria com a venda do produto O mesmo se passa com a calça de ginástica Logo as condições para realizar o negócio seriam Tops de ginástica 05y₁ 025y₂ 28 O que é oferecido pela grande indústria têxtil tem que ser melhor ou pelo menos igual do que vender os itens produzidos Calças de ginástica 025y₁ 05y₂ 40 O que é oferecido pela grande indústria têxtil tem que ser melhor ou pelo menos igual do que vender os itens produzidos Condições do negócio Portanto o problema dual da Fitwear pode ser formulado assim Min W 100Y₁ 160Y₂ sa 05Y₁ 025Y₂ 28 025Y₁ 05Y₂ 40 Atenção Para visualização completa da equação utilize a rolagem horizontal A solução ótima é dada por y₁ 0 y₂ 80 w 12800 Observe que na conjuntura do problema assumindo a indiferença entre produzir ou vender para a indústria têxtil a capacidade de corte horas de corte excedente não tem preço para a Fitwear Por sua vez o ágio a ser cobrado por 1 hora de costura é de 8000 DUALIDADE NA EFICIÊNCIA COMPUTACIONAL PARA A SOLUÇÃO DE PROBLEMAS DE PROGRAMAÇÃO LINEAR Como você viu uma das razões para o estudo dos problemas duais está relacionada ao número de restrições Algumas vezes em termos computacionais é mais eficiente resolver o problema dual do que o seu primal em função de número de restrições e variáveis uma vez que a solução ótima do dual é sempre igual à de seu primal Para facilitar o entendimento desse conceito considere o problema primal a seguir Max Z 10X₁ 4X₂ 7X₃ sa 3X₁ X₂ 2X₃ 25 X₁ 2X₂ 2X₃ 40 X₁ X₂ X₃ 90 2X₁ X₂ X₃ 20 X₁ X₂ X₃ 0 Atenção Para visualização completa da equação utilize a rolagem horizontal ATIVIDADE DISCURSIVA PARA ESSE MODELO DE PROGRAMAÇÃO LINEAR DE QUE FORMA VOCÊ ACREDITA QUE SERIA MAIS EFICIENTE OBTER UMA SOLUÇÃO ÓTIMA APLICANDO O MÉTODO SIMPLEX DIRETAMENTE A ESSE PROBLEMA PRIMAL OU APLICANDO O SIMPLEX AO PROBLEMA DUAL RESPOSTA Observe que no problema primal temos três variáveis e quatro restrições Assim o dual desse problema teria três restrições e quatro variáveis de decisão Por isso acreditase que seria mais eficiente em termos computacionais aplicar o método simplex ao dual do problema uma vez que este possui menos restrições devendo assim ter menos iterações no desenvolvimento de sua resolução diretamente pelo método simplex REGRAS PARA IDENTIFICAÇÃO DA SOLUÇÃO ÓTIMA NA TABELA SIMPLEX ÓTIMA DO PRIMAL Sabemos que a solução ótima do dual é sempre igual à solução ótima do primal Porém como ler a solução ótima do dual a partir da Tabela Simplex ótima do problema primal Fogliatto 2004 sistematizou as regras para identificação da solução ótima do dual na linha z da Tabela Simplex ótima do primal Essas regras são apresentadas a seguir Problema primal de maximização Valor ótimo da var dual yᵢ quando a restrição i é do tipo Coeficiente de fi na linha z do tableau ótimo Valor ótimo da var dual yi quando a restrição i é do tipo Coeficiente de ei na linha z do tableau ótimo Valor ótimo da var dual yi quando a restrição i é do tipo Coeficiente de ai na linha z do tableau ótimo M Problema primal de minimização Valor ótimo da var dual yi quando a restrição i é do tipo Coeficiente de fi na linha z do tableau ótimo Valor ótimo da var dual yi quando a restrição i é do tipo Coeficiente de ei na linha z do tableau ótimo Valor ótimo da var dual yi quando a restrição i é do tipo Coeficiente de fi na linha z do tableau ótimo M VERIFICANDO O APRENDIZADO MÓDULO 2 Avaliar a sensibilidade da solução obtida para problemas de programação linear em relação à incerteza ou erros de estimativa quanto aos coeficientes do modelo O QUE É A ANÁLISE DE SENSIBILIDADE A análise de sensibilidade também chamada de análise pósotimalidade consiste em avaliar os impactos que variações nos parâmetros podem provocar na solução ótima do problema em estudo A partir dessa análise é possível verificar como alterações nos parâmetros iniciais de um problema de programação linear afetam a sua solução ótima e identificar os valores alternativos dos parâmetros que levariam a uma nova solução para o problema Em outras palavras a análise de sensibilidade permite avaliar como variações na disponibilidade de recursos ou variações nos coeficientes da função objetivo custos preço etc afetam a solução ótima sem ser necessária a resolução do problema novamente Como alguns problemas envolvem um grande número de variáveis e restrições exigindo muito tempo computacional para a sua solução essa é uma grande vantagem É importante ressaltar que ao construirmos um modelo matemático para um problema de programação linear assumimos valores exatos para os coeficientes desse modelo No entanto na realidade eles podem sofrer alterações constantemente Os preços que uma empresa cobra por seus produtos podem mudar ou um fornecedor pode ter uma redução na sua capacidade de produção e com isso diminuir a disponibilidade de oferta de determinado produto Um funcionário por exemplo pode ficar doente e faltar alterando assim a produtividade da fábrica ATENÇÃO São diversas as situações que podem nos levar a incertezas com relação aos valores dos coeficientes Por isso tornase fundamental compreender o quão sensível é a solução de um modelo de programação linear a essas possíveis alterações Por meio da análise de sensibilidade é possível identificar em quantas unidades a disponibilidade de um dado recurso pode variar ou qual é a maior variação admissível nos coeficientes da função objetivo sem que seja alterada a base ótima Assim esse tipo de avaliação faz com que a análise de sensibilidade seja um dos tópicos mais importantes em programação linear A análise de sensibilidade estuda como um modelo de programação matemática se comporta quando submetido a mudanças em suas condições iniciais tais como Mudança no vetor de custos das variáveis básicas e não básicas Mudança no vetor de termos independentes Mudanças nos coeficientes das variáveis Acréscimo de restrições Acréscimo de novas variáveis É preciso destacar que conseguimos analisar todas essas mudanças por meio do Solver Após resolver um problema de programação linear o Solver fornece uma análise de sensibilidade informando sobre diversas situações como a faixa de valores que os coeficientes da função objetivo podem assumir sem alterar a solução ótima o impacto provocado por alterações na disponibilidade dos diversos recursos limitados sobre o valor ótimo da função objetivo o impacto que alterações nos coeficientes das restrições terão sobre a solução ótima do problema etc PROBLEMA GLASS CO Como ilustração das mudanças abordadas no tópico anterior examine cada um dos casos no exemplo da Glass Co Glass Co A empresa Glass Co que possui três fábricas produz janelas e portas de vidro As esquadrias e ferragens em aço são feitas na fábrica 1 as esquadrias de madeira são produzidas na fábrica 2 e a fábrica 3 produz o vidro e monta os produtos A direção da empresa decidiu modernizar a linha de produtos e propôs o lançamento de duas novidades Produto 1 porta de vidro de 25m com esquadria de alumínio Produto 2 janela adornada com esquadria de madeira 12m x 18m O produto 1 requer capacidade produtiva das fábricas 1 e 3 O produto 2 precisa das fábricas 2 e 3 A divisão de marketing concluiu que a empresa poderia vender tanto quanto fosse possível produzir desses produtos por essas fábricas Porém ambos os produtos competem por capacidade produtiva da fábrica 3 não estando claro qual mix dos dois produtos seria mais lucrativo É preciso então determinar quais devem ser as taxas de produção para maximizar o lucro total sujeitas às restrições impostas pela capacidade produtiva Fábrica Tempo de produção por lote em horas Produtos Tempo de produção disponível por semana horas 1 2 1 1 0 4 2 0 2 12 3 3 2 18 Lucro por lote 300000 500000 Atenção Para visualização completa da tabela utilize a rolagem horizontal Tabela Produção empresa Glass Co extraída de Hillier e Lieberman 2013 pág 21 No caso da Glass Co a empresa deve decidir os produtos a serem fabricados Logo a definição da variável de decisão é X1 Quantidade de lotes produtos 1 fabricados X2 Quantidade de lotes produtos 2 fabricados Para cada lote de portas de vidro de 25m com esquadria de alumínio produto 1 vendido a empresa lucra 3000000 enquanto o lucro de venda de cada lote de janela adornada com esquadria de madeira 12m x 18m produto 2 equivale a 500000 Logo o lucro total é igual a 3000X1 5000X2 de modo que a função objetivo para o problema é Max Z 3X1 5X2 Atenção Para visualização completa da equação utilize a rolagem horizontal No caso do problema da Glass Co foi considerada ilimitada a demanda por seus produtos e a oferta de matériaprima de modo que não entram como restrições no modelo matemático Porém há restrições relacionadas ao tempo de produção disponível por semana em cada fábrica Logo temos as seguintes restrições X1 4 2X2 12 à X2 6 3X1 2X2 18 Atenção Para visualização completa da equação utilize a rolagem horizontal Há ainda a restrição de não negatividade das variáveis de decisão uma vez que não se pode produzir um número negativo de portas ou janelas Assim a restrição 4 é dada por X1 X20 Portanto o modelo para o problema é Max Z 3X1 5X2 sa X1 4 2X2 12 3X1 2X2 18 X1 X2 0 Atenção Para visualização completa da equação utilize a rolagem horizontal IMPLANTAÇÃO DO PROBLEMA GLASS CO NO SOLVER Antes de analisar a sensibilidade do problema pelo Solver é preciso implementar seu modelo matemático no Excel Para isso veremos a implantação de um modelo no software Excel A implantação do modelo matemático para o problema da Glass Co servirá para encontrar a sua solução com vistas à posterior análise do Relatório de Sensibilidade fornecido pelo Solver do Excel O passo inicial para a solução do problema é a organização dos dados como veremos a seguir Começamos representando as variáveis de decisãoX1 e X2 na planilha bem como seus coeficientes na função objetivo Em amarelo estão destacadas as células variáveisajustáveis reservadas na planilha para representar as variáveis de decisão do modelo Em seguida é preciso criar uma fórmula que represente a função objetivo usando a função SOMARPRODUTO do Excel para os coeficientes da função objetivo e as células destinadas a receber o valor das variáveis de decisão Com isso a célula destacada em amarelo para a função objetivo recebeu a fórmula 3X15X2 O passo seguinte se dá com a inserção das duas restrições para o problema da Glass Co Observe a função SOMARPRODUTO entre os vetores que indicam os coeficientes das restrições e as células destinadas para receber o valor das variáveis de decisão além da inserção das constantes b de cada restrição lado direito da restrição Após a inserção da restrição 3 3X₁ 2X₂ 18 está finalizada a implementação do modelo do problema de programação linear da Glass Co no Excel Terminamos a implementação do modelo Agora vamos resolvêlo Para tanto é necessário indicar para o Solver o que cada célula da planilha representa A função objetivo As variáveis de decisão As restrições Então definese a célula de destino aquela que representa a função objetivo na caixa de diálogo Parâmetros do Solver Observe que a célula E11 contém a fórmula que representa a função objetivo para o problema como havia sido preparado Neste momento instruise também o Solver para tentar maximizar seu valor especificando o botão Max Definindo a função objetivo na célula de destino Captura de tela do Excel Em seguida é preciso indicar as células que representam as variáveis de decisão no modelo Observe que as células C10 e D10 na planilha representam as variáveis de decisão para o modelo O Solver determinará os valores ótimos para essas células Definindo as variáveis de decisão Captura de tela do Excel É o momento então de definir as células de restrição na planilha e as restrições que se aplicam a essas células As células de restrição são aquelas em que foram implementadas as fórmulas para cada restrição Para definir as células de restrição clique no botão Adicionar na janela Parâmetros do Solver e em seguida preencha a caixa de diálogo Incluir Restrições apresentada na figura a seguir Observe que as células E15 E16 e E17 representam as células de restrição cujos valores devem ser menores ou iguais aos indicados nas células G15 G16 e G17 respectivamente Especificando as células de restrição Captura de tela do Excel Ainda é necessário especificar que as variáveis de decisão devem ser iguais ou maiores do que zero Para isso basta clicar em Tornar Variáveis Irrestritas Não Negativas na caixa de diálogo Parâmetros Condições de não negatividade Captura de tela do Excel Solução ótima para o problema da Glass Co Captura de tela do Excel Caixa de diálogo Resultados do Solver Captura de tela do Excel Relatório de Resposta para o problema da Glass Co Captura de tela do Excel Caixa de diálogo Resultados do Solver Captura de tela do Excel O Relatório de Resposta traz a solução do problema Esse relatório é praticamente autoexplicativo Observase na tabela Célula do Objetivo na coluna Valor Final a solução ótima para o problema Na tabela Células Variáveis na coluna Valor Final estão os valores que as variáveis X₁ e X₂ recebem na solução ótima do problema A tabela final do relatório traz as informações sobre as restrições A coluna Valor da Célula indica os valores finais assumidos por cada restrição com os valores ótimos das variáveis de decisão Por sua vez a coluna Margem de Atraso indica a diferença entre o valor do lado direito de cada restrição o valor b e os valores finais assumidos por cada restrição com os valores ótimos das variáveis de decisão Assim sendo por meio da figura a seguir podese observar que se essa solução for implementada todo o tempo de produção disponível nas fábricas 2 e 3 estão sendo utilizados havendo uma sobra de capacidade de duas horas na fábrica 1 Relatório de Resposta para o problema da Glass Co Captura de tela do Excel ANÁLISE DE SENSIBILIDADE DO PROBLEMA DA GLASS CO NO SOLVER O Relatório de Sensibilidade apresentado a seguir permite analisar o impacto das alterações nos coeficientes na solução ótima para o problema da Glass Co Relatório de Resposta para o problema da Glass Co Captura de tela do Excel MUDANÇA NO COEFICIENTE DA FUNÇÃO OBJETIVO DE UMA VARIÁVEL BÁSICA Essa análise serve para você compreender o quanto os coeficientes da função objetivo das variáveis básicas podem variar de forma que a base permaneça sendo a ótima No problema da Glass Co os coeficientes da função objetivo representam o lucro da empresa com a venda de cada tipo de produto Não é difícil imaginar situações reais que levassem a alterações na matriz de custos da empresa e que consequentemente impactassem o lucro com a venda de seus diferentes produtos EXEMPLO O componente de um produto pode ser importado de modo que variações cambiais levariam a alterações no seu custo e no lucro obtido com a sua venda Na coluna Objetivo Coeficiente da tabela Células Variáveis do Relatório de Sensibilidade observamse os valores originais atribuídos aos coeficientes de cada variável de decisão na função objetivo As duas colunas seguintes Permitido Aumentar e Permitido Reduzir indicam os aumentos e as reduções permitidos nos valores dos coeficientes de cada variável de decisão na função objetivo sem que haja alterações na base da solução ótima do problema Dessa forma X1 O coeficiente de X1 pode reduzir em 3 unidades ou aumentar em 45 unidades sem alterar a solução ótima assumindo que todos os demais coeficientes se mantenham constantes X2 O coeficiente de X2 ou seja o lucro da venda do produto 2 pode reduzir em 2 unidades sem que a solução ótima seja alterada Porém perceba que mesmo que esse coeficiente aumente indefinidamente não teremos alterações na solução ótima para o problema da Glass Co MUDANÇAS SIMULTÂNEAS NOS COEFICIENTES DA FUNÇÃO OBJETIVO Você acabou de ver que as colunas Permitido Aumentar e Permitido Reduzir indicam os aumentos e as reduções permitidos nos valores dos coeficientes de cada variável de decisão na função objetivo sem que haja alterações na base da solução ótima do problema assumindo que todos os demais coeficientes do modelo permaneçam constantes Mas e se ocorrssem alterações simultâneas em mais de um coeficiente da função objetivo Será que a solução atual permaneceria ótima Para esta análise utilizase a técnica conhecida como Regra dos 100 Ao aplicar essa regra duas situações diferentes podem ocorrer RAGSDALE 2009 SITUAÇÃO 1 Todas as variáveis cujos coeficientes da função objetivo se alteram têm custos reduzidos diferentes de zero Nesse caso não há alteração na solução ótima atual desde que o coeficiente de cada variável modificada permaneça dentro dos limites estabelecidos nas colunas Permitido Aumentar e Permitido Reduzir do Relatório de Sensibilidade SITUAÇÃO 2 Pelo menos uma variável cujo coeficiente da função objetivo se altere tem um custo reduzido igual a zero Nesse caso é preciso analisar a proporção de alteração planejada em cj para a máxima alteração permissível para a qual a solução atual permanece ótima rj rjΔcjIjseΔcj0 rjΔcjDjseΔcj0 Atenção Para visualização completa da equação utilize a rolagem horizontal Sendo Cj coeficiente da função objetivo para a variável xj Ij o aumento permissível em cj dado pelo Relatório de Sensibilidade coluna Permitido Aumentar Dj a redução permissível em cj dada pelo Relatório de Sensibilidade coluna Permitido Reduzir Se apenas um coeficiente da função objetivo se alterar a solução atual permanece ótima desde que rj 1 caso rj seja expresso como porcentagem deve ser menor ou igual a 100 De forma semelhante se mais de um coeficiente da função objetivo se alterar a solução atual permanecerá ótima desde que É importante ressaltar que se a solução atual pode permanecer ótima mas não há garantias MUDANÇA NO COEFICIENTE DA FUNÇÃO OBJETIVO DE UMA VARIÁVEL NÃO BÁSICA No problema da Glass Co as duas variáveis de decisão cujos coeficientes na função objetivo são diferentes de zero são variáveis básicas Na tabela Células Variáveis do Relatório de Sensibilidade observase que os valores da coluna Reduzido Custo são nulos tanto para X1 quanto para X2 Os valores Reduzido Custo indicam o quanto o coeficiente da função objetivo de uma variável não básica pode variar sem que a solução ótima para o problema se altere EXEMPLO Caso houvesse um produto 3 cuja quantidade de itens vendidos fosse representada pela variável x3 e este tivesse o valor de 10 unidades na coluna Reduzido Custo tal fato implicaria um aumento permissível de 10 unidades no coeficiente da função objetivo para o produto 3 Isso significa que a solução atual permaneceria como ótima desde que alterações no lucro marginal do produto 3 resultassem em um número menor ou igual a 10 Conforme reforçado por Ragsdale 2009 o aumento no valor da função objetivo será identificado de maneiras distintas de acordo com o tipo de problema Problema de maximização O custo reduzido de uma variável deve ser não negativo para indicar que um aumento no valor da variável implica um aumento no valor da função objetivo Problema de minimização O custo reduzido deve ser não positivo para indicar melhorias na função objetivo MUDANÇA NO VETOR DE DEMANDAS OU TERMO INDEPENDENTE Nessa análise o que se deseja é compreender como mudanças nos termos independentes das restrições vetor de demandas afetam a solução ótima para o problema de programação linear em análise Em outras palavras por meio dessa análise é possível determinar o quão melhor ou pior a solução seria se houvesse mais ou menos de determinado recurso Entretanto essa análise é distinta para restrições agrupadas e restrições não agrupadas As restrições que tenham folga igual a zero na solução ótima para um problema de programação linear são chamadas de restrições agrupadas Esse tipo de restrição impede que aperfeiçoemos mais a função objetivo Por exemplo como observado no Relatório de Resposta para o problema da Glass Co as restrições relativas à capacidade das fábricas 2 e 3 limitam a maximização do lucro da empresa sendo assim restrições agrupadas enquanto a restrição quanto à capacidade da fábrica 1 é não agrupada ATENÇÃO Apesar de os preçossombra indicarem que o valor da função objetivo se modifica caso o valor do termo independente da restrição seja alterado eles não indicam os valores que as variáveis de decisão vão assumir A determinação dos novos valores ótimos para as variáveis de decisão exige a realização das devidas alterações no modelo implementado no Excel e que este seja resolvido outra vez MUDANÇA NO VETOR DE DEMANDAS OU TERMO INDEPENDENTE EM RESTRIÇÕES AGRUPADAS A análise de sensibilidade em relação a mudanças no vetor de demandas em restrições agrupadas é fornecida na coluna Sombra Preço da tabela Restrições do Relatório de Sensibilidade O preçosombra de uma restrição indica o impacto que o aumento de uma unidade no valor do RHS b da restrição tem sobre o valor da função objetivo dado que todos os demais coeficientes permaneçam constantes Assim Preçosombra positivo Indica o aumento do valor de z obtido para a solução ótima Preçosombra negativo Implica uma redução no valor de z obtido para a solução ótima No entanto os valores do preçosombra se aplicam somente se o aumento ou redução no valor do termo independente da restrição se mantém dentro dos limites permitidos de aumento e redução de cada restrição indicados no Relatório de Sensibilidade EXEMPLO O Relatório de Sensibilidade do problema da Glass Co indica que o preçosombra para a restrição associada à disponibilidade de horas na fábrica 2 é igual 3 Dessa forma se o número de horas disponíveis na fábrica 2 aumentar na faixa de 0 a 3 o valor ótimo da função objetivo muda aumenta em 3 unidades para cada hora adicional Se o número de horas disponíveis se reduzir para uma quantia na faixa de 0 a 3 o valor ótimo da função objetivo muda reduz em 3 unidades MUDANÇA NO VETOR DE DEMANDAS OU TERMO INDEPENDENTE EM RESTRIÇÕES NÃO AGRUPADAS A restrição para a fábrica 1 tem preçosombra igual a zero com um aumento permissível igual a infinito e uma redução permissível igual a 2 Desse modo a disponibilidade de horas para a fábrica 1 pode aumentar para qualquer valor que a função objetivo não se altera Esse resultado já era esperado uma vez que atualmente a capacidade da fábrica 1 já está sendo subutilizada ou seja há disponibilidade de horas na fábrica 1 horas não utilizadas Além disso o valor do termo independente dessa restrição pode se reduzir em até duas horas sem afetar a solução ótima MUDANÇA NO COEFICIENTE DE RESTRIÇÃO DE UMA VARIÁVEL BÁSICA Neste tópico você verá como alterações em coeficientes de restrição afetam a solução ótima em um problema de programação linear Por exemplo caso houvesse uma alteração na produtividade da fábrica 3 sendo agora necessárias oito horas para se produzir um lote do produto 1 ainda seria lucrativo para a Glass Co continuar a produzir lotes desses produtos No exemplo a quantidade de lotes de produtos 1 fabricados variável X1 é uma variável básica Logo mudanças em um coeficiente de suas restrições implicariam alterações em B e em quase toda a Tabela Simplex conforme pode ser verificado na figura a seguir Tabela Simplex Assim a solução ótima permaneceria a mesma apenas se as duas situações a seguir ocorressem O lado direito da Tabela Simplex ótima o vetor B1b permanecesse positivo Todos os valores zjcj fossem maiores que zero DICA Mudanças no coeficiente de restrição de uma variável básica implicam tantas alterações na Tabela Simplex final que se torna mais fácil resolver novamente o problema RELATÓRIO DE LIMITES A próxima figura apresenta o Relatório de Limites para o problema da Glass Co Relatório de Limites para o problema da Glass Co Captura de tela do Excel O Relatório de Limites apresenta o valor ótimo para cada célula variável além de indicar quais valores a célula de destino assume se cada célula variável for ajustada para seu limite superior ou inferior A coluna Inferior Limite apresenta o menor valor que cada variável pode assumir enquanto os valores de todas as outras células variáveis permanecerem constantes e todas as restrições forem satisfeitas Por sua vez a coluna Superior Limite apresenta o maior valor que cada variável pode assumir enquanto os valores de todas as outras células variáveis permanecerem constantes e todas as restrições forem satisfeitas Para você reforçar o aprendizado dos conceitos apresentados referentes à análise de sensibilidade e consequentemente para facilitar a sua compreensão veja a seguir um exemplo de aplicação para a análise de sensibilidade em problemas de programação linear EXEMPLO DE APLICAÇÃO PARA ANÁLISE DE SENSIBILIDADE Uma confeitaria produz três tipos de doces compostos por açúcar e chocolate A empresa tem disponibilidade de 50kg de açúcar e 100kg de chocolate por semana e deseja maximizar seu lucro semanal A tabela a seguir apresenta as restrições de composição e lucro por produto da confeitaria Doce Açúcar Chocolate Lucro 1 1 2 3 2 1 3 7 3 1 1 5 Atenção Para visualização completa da tabela utilize a rolagem horizontal Tabela Restrições de composição e lucro por produto Questões 1 Ache a solução ótima para o problema 2 Para quais valores de lucro do doce 1 a base atual permanece ótima Se o lucro do doce 1 fosse 700 a solução ótima sofreria alterações 3 Para quais valores de lucro do doce 2 a base atual permanece ótima Se o lucro do doce 2 fosse 1300 haveria uma nova solução ótima 4 Para quais valores de açúcar disponível a base permaneceria a mesma 5 Se 60kg de açúcar estivessem disponíveis qual seria o lucro da empresa Primeiramente encontraremos a solução ótima para o problema Para atender à questão 1 o primeiro passo é construir o modelo matemático do problema Para isso adotamos as seguintes variáveis de decisão X1 Quantidade de lotes do doce 1 produzida por semana X2 Quantidade de lotes do doce 2 produzida por semana X3 Quantidade de lotes do doce 3 produzida por semana A confeitaria tem como objetivo maximizar seu lucro semanal sendo 300 o lucro unitário obtido pela venda de um lote do doce 1 700 o lucro unitário obtido pela venda de um lote do doce 2 e 500 o lucro unitário obtido pela venda de um lote do doce 3 Logo a função objetivo desse problema é Max Z 3X1 7X2 5X3 Atenção Para visualização completa da equação utilize a rolagem horizontal A produção de um lote do doce 1 requer 1kg de açúcar e 2kg de chocolate Um lote do doce 2 demanda 1kg de açúcar e 3kg de chocolate enquanto a produção de um lote do doce 3 requer 1kg de açúcar e 1kg de chocolate Como a confeitaria tem disponibilidade de 50kg de açúcar e 100kg de chocolate por semana são as seguintes as restrições que limitam a função objetivo do problema além da condição de não negatividade das variáveis de decisão X1 X2 X3 0 DISPONIBILIDADE DE AÇÚCAR X1 X2 X3 50 DISPONIBILIDADE DE CHOCOLATE 2X1 3X2 X3 100 Dessa forma o modelo matemático para esse problema de programação linear é Max Z 3X1 7X2 5X3 sa X1 X2 X3 50 2X1 3X2 X3 100 X1 X2 X3 0 Atenção Para visualização completa da equação utilize a rolagem horizontal Implantação do modelo no Solver e sua solução Captura de tela do Excel Relatório de Resposta Captura de tela do Excel Relatório de Sensibilidade Captura de tela do Excel Relatório de Sensibilidade Captura de tela do Excel ANÁLISE DE SENSIBILIDADE O vídeo aborda a importância da análise de sensibilidade para a solução de problemas reais de Programação Linear VERIFICANDO O APRENDIZADO CONCLUSÃO CONSIDERAÇÕES FINAIS A aprendizagem de técnicas de pesquisa operacional nos habilita a representar situações complexas por meio de modelos matemáticos permitindo a análise de diferentes cenários de forma mais rápida e barata Aplicar tais técnicas no processo de tomada de decisão para a solução desses problemas é de grande auxílio Entretanto encontrar a solução ótima nem sempre é simples exigindo grande número de cálculos Visando a facilitar o trabalho foram desenvolvidos diferentes softwares computacionais que permitem a solução de problemas de programação matemática desde o Solver de pacotes de planilhas eletrônicas como o Excel até programas mais robustos dedicados exclusivamente à otimização como o CPLEX Além disso encontrar a solução ótima para um problema nem sempre significa que ele esteja resolvido É importante conhecer o grau de liberdade na tomada de decisão ou seja saber quais as margens de manobra necessárias para alterar determinados aspectos na construção do modelo sem que a solução ótima seja modificada RODRIGUES et al 2014 A análise pósotimalidade conhecida como análise de sensibilidade permite esse tipo de avaliação No desenvolvimento do modelo premissas são assumidas e estimativas são feitas em relação a parâmetros e coeficientes que na realidade podem sofrer alterações ao longo do tempo Por exemplo o custo de um produto pode aumentar alterando então sua margem de lucro Um fornecedor pode enfrentar problemas na produção de um componente o que influenciará a disponibilidade desse produto A análise pósotimalidade permite avaliar a sensibilidade da solução em relação à incerteza ou a erros de estimativa quanto aos coeficientes do modelo ou quanto a mudanças que possam ocorrer A análise de sensibilidade está relacionada ao problema dual associado ao primal A teoria da dualidade pode ser aplicada em análises econômicas como variações marginais Em algumas situações dependendo do número de restrições e de variáveis a dualidade também pode ser aplicada para que o problema seja resolvido de modo mais eficiente computacionalmente PODCAST PODCAST Ouça o podcast com um resumo sobre dualidade e análise de sensibilidade REFERÊNCIAS ARENALES M et al Pesquisa operacional Rio de Janeiro Elsevier 2007 FOGLIATO F Pesquisa operacional Porto Alegre Deprot UFRGS 2006 HILLIER F S LIEBERMAN G J Introdução à pesquisa operacional Brasil McGraw Hill 2013 LACHTERMACHER G Pesquisa operacional na tomada de decisões Rio de Janeiro Campus 2009 RAGSDALE C T Modelagem e análise de decisão São Paulo Cengage Learning 2009 RODRIGUES L H et al Pesquisa operacional programação linear passo a passo do entendimento do problema à interpretação da solução São Leopoldo Unisinos 2014 EXPLORE Sobre os conceitos de análise de sensibilidade e dualidade leia Operations Research Applications and Algorithms 2004 de Winston W L e Goldberg J B capítulos 5 e 6 Pesquisa operacional na tomada de decisões 2009 de Lachtermacher G capítulo 5 Pesquisa operacional 2007 de Arenales M et al seção 210 do capítulo 2 Sobre a utilização do Solver leia o capítulo 4 de Modelagem e análise de decisão 2009 de Ragsdale C T CONTEUDISTA Renata Albergaria de Mello Bandeira CURRÍCULO LATTES