Dualidade e Análise de Sensibilidade

Prévia do material em texto

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