·
Marketing e Comunicação ·
Outros
Envie sua pergunta para a IA e receba a resposta na hora
Texto de pré-visualização
UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP PESQUISA OPERACIONAL 1 ANÁLISE DE SENSIBILIDADE 1 Introdução O aspecto mais prático da Análise de Sensibilidade também chamada de análise de pós otimização consiste em responder à seguinte pergunta dada a solução ótima de um problema de Programação Linear para qual faixa de valores dos coeficientes a solução ótima seria mantida Tipos de alterações na estrutura de um modelo após a determinação de sua solução ótima 11 Alterações Simples alterações nos coeficientes de custo cj alterações nas constantes bi alterações nas restrições que podem incluir adição de novas variáveis eliminação de variáveis adição de novas restrições eliminação de restrições 12 Alterações Sistemáticas Programação Paramétrica alterações sistemáticas nos cj alterações sistemáticas nos bi A Análise de Sensibilidade aplicase a modificações pontuais nos coeficientes uma de cada vez Caso haja modificações simultâneas em diversos elementos há que considerar o problema como novo e resolvêlo desde seu início Outro tipo de alteração comum para a qual seria desejável a existência de algum procedimento simples seria a alteração dos coeficientes tecnológicos aij Para esses entretanto à exceção de casos particulares não existe nenhuma técnica sistemática e o problema deve ser considerado como novo Prof André Gandolpho DSc 20231 1 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP 11 Alterações Simples VARIAÇÕES NOS COEFICIENTES cj DA FUNÇÃO OBJETIVO Suponha um modelo de Programação Linear e sua solução ótima Desejase agora saber para que faixa de valores de cada coeficiente da função objetivo a solução permanece ótima A análise portanto considera a atual solução ótima e está dividida em duas partes se o coeficiente pertence a uma variável não básica e se o coeficiente pertence a uma variável básica VARIAÇÕES NAS CONSTANTES bi Suponha um modelo de Programação Linear e sua solução ótima Desejase saber para que faixa de valores de cada elemento do lado direito a solução permanece ótima A análise a seguir está dividida em duas partes caso em que a restrição não é ativa e caso em que a restrição é ativa No próximo item será apresentado um exemplo resolvido onde será possível explicar na prática os conceitos apresentados até aqui No item 3 temos mais exercícios do tópico Análise de Sensibilidade em Programação Linear com soluções Nas referências bibliográficas o aluno pode consultar as fontes de teoria e exercícios do tópico Análise de Sensibilidade em Programação Linear podendo aprofundar seus conhecimentos Este item está baseado no Capítulo 3 de Pizzolato Nélio Domingues Gandolpho André A Técnicas de Otimização LTC Rio de Janeiro 2005 Prof André Gandolpho DSc 20231 2 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP 2 Exemplo Resolvido Seja o seguinte problema de Programação Linear que será usado como veículo para ilustrar as metodologias da Análise de Sensibilidade MAX Z 5x1 7x2 3x3 Sujeito a 2x1 3x2 4x3 240 recurso 1 31 2x1 x2 x3 150 recurso 2 x1 80 recurso 3 x1 x2 x3 0 Acrescentandose as variáveis de folga temse o sistema 32 em que x1 x2 x3 além de Z são as variáveis reais do problema e as demais são as variáveis de folga acrescentados por força do método simplex MAX Z 5X1 7X2 3X3 0 X4 0 X5 0 X6 0 Sujeito a 2X1 3X2 4X3 X4 240 2X1 X2 X3 X5 150 32 X1 X6 80 X1 X2 X3 X4 X5 X6 0 Tableau Ótimo a Variação de cj para Xj não básica Variável não básica X3 Considere a variável X3 que tem valor nulo na solução ótima Intuitivamente caso o valor de seu coeficiente na FO original fosse mais favorável essa variável poderia ter valor positivo e este é o argumento que será explorado Na FO original temse Z 5X1 7X2 3X3 Suponha que o coeficiente de X3 seja alterado em Δc3 Portanto a FO original seria Z 5X1 7X2 3 Δc3 X3 Z 5X1 7X2 3 Δc3 X30 A aplicação do método simplex implicou na adição de múltiplos das linhas à FO até chegar à solução final em que o coeficiente de X3 é 625 O coeficiente recém acrescentado Δc3 apareceria na FO no último quadro como Z 57750 625 Δc3X3 225 X3 025 X5 Prof André Gandolpho DSc 20231 3 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Portanto a FO permanecerá ótima enquanto o coeficiente de X3 for não negativo ou seja 625 Δc3 0 Δc3 625 b Variação de cj para Xj básica Variável básica X1 Considere a variável básica X1 A FO do sistema original 31 consiste em Max Z 5X1 7X2 3X3 Suponha que o coeficiente de X1 seja alterado em Δc1 A FO original seria Z 5 Δc1X1 7X2 3X3 Introduzida no quadro final essa alteração faria com que o quadro se tornasse Base Z X1 X2 X3 X4 X5 X6 b Max 1 c1 0 625 225 025 0 57750 Linha 0 X2 0 0 1 15 05 05 0 450 Linha 1 X1 0 1 0 025 025 075 0 525 Linha 2 X6 0 0 0 025 025 075 1 275 Linha 3 Para zerar o custo reduzido da variável básica X1 há que se adicionar à linha 0 a linha 2 multiplicada por c1L0 L0 c1L2 As alterações resultantes na linha 0 estão transcritas no Quadro a seguir Base Z X1 X2 X3 X4 X5 X6 b Max 1 0 0 625025c1 225025c1 025075c1 0 57750525c1 Para a presente solução permanecer ótima devese ter 625 025c1 0 c1 625025 250 225 025c1 0 c1 225025 90 025 075c1 0 c1 025075 13 Portanto com respeito à variável X1 a função objetivo permanece inalterada enquanto 13 c1 9 Variável básica X2 Procedendose analogamente com a variável X2 supõese um acréscimo c2 em seu coeficiente de custo introduzido no quadro final disposto a seguir Prof André Gandolpho DSc 20231 4 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Base Z X1 X2 X3 X4 X5 X6 b Max 1 0 c2 625 225 025 0 57750 Linha 0 X2 0 0 1 15 05 05 0 450 Linha 1 X1 0 1 0 025 025 075 0 525 Linha 2 X6 0 0 0 025 025 075 1 275 Linha 3 Para zerar o custo reduzido da variável básica X2 há que se adicionar à linha 0 a linha 1 multiplicada por c2 No quadro resultante a única alteração ocorre na linha 0 a qual está transcrita no Quadro abaixo L0 L0 L1 Base Z X1 X2 X3 X4 X5 X6 b Max 1 0 0 625 15c2 225 05c2 025 05c2 0 57750 45c2 Para a presente solução permanecer básica devese ter 625 15c2 0 c2 62515 416667 12530 256 225 05c2 0 c2 22505 45 025 05c2 0 c2 02505 05 Portanto com respeito à variável X2 a função objetivo permanece inalterada enquanto 256 c2 05 Variações nas constantes do lado direito bi Suponha um modelo de Programação Linear e sua solução ótima Desejase saber para que faixa de valores de cada elemento do lado direito a solução permanece ótima A análise a seguir está dividida em duas partes caso em que a restrição não é ativa e caso em que a restrição é ativa Variação de bi em restrição não ativa Quando a restrição não é ativa a variável de folga correspondente é básica Considere a última restrição do sistema 31 que consiste em X1 80 e suponha que b3 80 seja alterado para X1 X6 80 b3 Prof André Gandolpho DSc 20231 5 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP De acordo com o quadro ótimo X1 525 e X6 275 Avaliação imediata sugere que aumentos em b3 não terão nenhum efeito na seleção ótima pois o insumo disponível supera o valor usado Por outro lado a quantidade de insumo pode ser reduzido com alteração da variável básica X6 a qual obedece à seguinte relação X6 275 b3 A condição para a atual solução continuar ótima é que X6 continue não negativa ou seja 275 b3 0 b3 275 Portanto para 80 275 525 a solução permanece ótima ou seja b3 80 80 275 80 635 Variação de bi em restrição ativa a Caso da 1a Restrição Considere a primeira restrição do sistema 31 qual seja 2X1 3X2 4X3 X4 240 A solução ótima indica que X4 0 tratandose portanto de uma restrição ativa Suponha agora que b1 seja alterado para A restrição passa a ser 2X1 3X2 4X3 X4 240 b1 O que se deseja saber é a influência que a variação b1 exerce sobre esta e sobre as demais restrições no decorrer dos pivotamentos Para simplificar suponha b1 1 e imagine um vetor coluna unitário com o valor 1 na primeira restrição e valores 0 nas outras duas Prof André Gandolpho DSc 20231 6 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Base Z X1 X2 X3 X4 X5 X6 b b1 Max 1 0 0 625 225 025 0 57750 0 X2 0 0 1 15 05 05 0 450 1 X1 0 1 0 025 025 075 0 525 0 X6 0 0 0 025 025 075 1 275 0 Tableau Inicial Tableau Final b b1 b b1 0 0 57750 225 240 1 450 05 150 0 525 025 80 0 275 025 Assim esse vetor adicionado ao lado direito do sistema é idêntico ao vetor unitário X4 e como todas as operações são elementares eles sofrem as mesmas alterações Desse modo eles coincidem no quadro final o qual indica que os componentes do vetor X4 são 05 025 025 nas linhas 1 2 e 3 respectivamente medindo os efeitos que a variação b1 1 exerce nos elementos do lado direito conferir no quadro anterior Multiplicando essas variações por b1 o lado direito do quadro final será X2 45 05b1 X1 525 025b1 X6 275 025b1 O conjunto dessas condições implica que 90 b1 210 ou seja b1 240 240 90 240 210 150 450 Prof André Gandolpho DSc 20231 7 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Nessa faixa de valores a solução ótima é composta pela mesma base ou seja pelas mesmas variáveis básicas embora com valores numéricos das variáveis e da função Z alterados em função da variação b1 A 2ª restrição do sistema 31 também é ativa no quadro ótimo com X5 0 Suponha que agora que b2 seja alterado para A restrição passa a ser 2X1 X2 X3 X5 150 b2 Novamente desejase saber qual a influência que a variação de b2 exerce sobre esta e sobre as demais restrições com os pivotamentos Como visto uma solução imediata para o sistema modificado consiste em estabelecer X5 b2 fazendo com que pequenas variações b2 estejam refletidas no valor de X5 Suponha uma variação unitária b2 1 e imagine um vetor unitário com valor 1 na 2ª restrição e valores zeros nas demais Observando o quadro ótimo do programa linear Quadro 32 o vetor X5 tem componentes 05 075 075 nas linhas 1 2 e 3 respectivamente indicando a influência que o vetor unitário b2 exerce no lado direito de cada uma das três restrições Assim multiplicandose essas alterações por b2 o lado direito do quadro final será X2 45 05 b2 X1 525 075 b2 X2 275 075 b2 Para se manter a não negatividade devese ter X2 45 05 b2 0 b2 4505 90 X1 525 075 b2 0 b2 525075 70 X2 275 075 b2 0 b2 275075 366667 O conjunto dessas restrições implica em 70 b2 366667 ou seja b2 150 150 70 150 366667 80 1866667 Prof André Gandolpho DSc 20231 8 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP 3 Exercícios Complementares 31 Seja o seguinte problema de PL já resolvido em lista anterior Determine a faixa de valores em que os coeficientes da Função Objetivo e das constantes do lado direito das restrições podem variar sem que a solução ótima mude Max Z 8x1 5x2 sa 12x1 10x2 150 x1 130 x2 100 40x1 60x2 567 x1 x2 0 Resolvendo o problema de PL utilizando o Método Simplex em forma de quadros Colocando as variáveis de folga Max Z 8x1 5x2 sa 12x1 10x2 x3 150 x1 x4 130 x2 x5 100 40x1 60x2 x6 567 x1 x2 x3 x4 x5 x6 0 TABLEAU INICIAL ENTRA Base Z X1 X2 X3 X4 X5 X6 b RAZÃO MAX 1 8 5 0 0 0 0 0 X3 0 12 10 1 0 0 0 150 125 SAI X4 0 1 0 0 1 0 0 130 130 X5 0 0 1 0 0 1 0 100 X6 0 40 60 0 0 0 1 567 14175 1a iteração TABLEAU ÓTIMO Base Z X1 X2 X3 X4 X5 X6 b RAZÃO MAX 1 0 53 23 0 0 0 100 X1 0 1 56 112 0 0 0 252 X4 0 0 56 112 1 0 0 2352 X5 0 0 1 0 0 1 0 100 X6 0 0 803 103 0 0 1 67 Solução ótima x1 252 x2 0 x3 0 x4 0 Z 100 Respostas da Análise de Sensibilidade Faixa de Variação dos Custos c1 2 c1 6 c2 53 1666 Faixa de Variação das Constantes do Lado Direito 150 b1 201 b2 2352 b3 100 b4 67 Solução da Análise de Sensibilidade Prof André Gandolpho DSc 20231 9 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Analisando a variável não básica X2 temos que no tableau final trocar o coeficiente original c2 por c2 ou seja c 5 c2 5 c2 No tableau final temos Base Z X1 X2 X3 X4 X5 X6 B MAX 1 0 53c2 23 0 0 0 100 X1 0 1 56 112 0 0 0 252 X4 0 0 56 112 1 0 0 2352 X5 0 0 1 0 0 1 0 100 X6 0 0 803 103 0 0 1 67 Portanto para que continuemos no ótimo 53c2 0 53 c2 Analisando a variável básica X1 temos que no tableau final trocar o coeficiente original c1 por c1 ou seja c1 8 c1 8 c1 No tableau final temos Base Z X1 X2 X3 X4 X5 X6 B MAX 1 c1 53 23 0 0 0 100 X1 0 1 56 112 0 0 0 252 X4 0 0 56 112 1 0 0 2352 X5 0 0 1 0 0 1 0 100 X6 0 0 803 103 0 0 1 67 Como a variável x1 é básica temos que fazer a seguinte operação na linha 0 do tableau final L0 L0 c1 Base Z X1 X2 X3 X4 X5 X6 B RAZÃO MAX 1 0 5356c1 23112c1 0 0 0 100252c1 Para permanecer no ótimo temos as seguintes condições 5356c10 c1 2 23112c10 c1 8 c1 2 c1 6 Analisando as variações das constantes do lado direito das restrições temos Restrição 1 b1 150 b1 150 b1 b b1 bf b1f 150 1 252 112 130 0 2352 112 100 0 100 0 567 0 67 103 252 112 b10 2352 112b10 100 0b10 67 103b10 150 b1 201 Continuando a análise das variações das constantes do lado direito da restrição 3 temos que b2 130 b2 130 b2 Prof André Gandolpho DSc 20231 10 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Tableau Inicial Tableau Final B b2 bf b2f 150 0 252 0 130 1 2352 1 100 0 100 0 567 0 67 0 Resolvendo o sistema composto pelas condições que o lado direito tem que ser não negativo temos 2352 b20 Continuando a análise das variações das constantes do lado direito da restrição 3 temos que b3 130 b3 130 b3 Tableau Inicial Tableau Final b b3 bf b3f 150 0 252 0 130 0 2352 0 100 1 100 1 567 0 67 0 Resolvendo o sistema composto pelas condições que o lado direito tem que ser não negativo temos 100 b30 b3 100 Tableau Inicial Tableau Final b b4 bf b4f 150 0 252 0 130 0 2352 0 100 0 100 0 567 1 67 1 Resolvendo o sistema composto pelas condições que o lado direito tem que ser não negativo temos 67 b40 b4 67 Prof André Gandolpho DSc 20231 11 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP 32 Seja o seguinte problema de Programação Linear extraído de TAHA Handy A Pesquisa Operacional 8 Ed São Paulo Pearson Prentice Hall 2008 A empresa TOYCO produz 3 tipos de brinquedos trens caminhões e carros Para isso a empresa usa 3 operações Os limites diários de tempo disponível minutos para as 3 operações são 430 460 e 420 minutos respectivamente e os lucros para os trens caminhões e carros são 3 2 e 5 respectivamente Os tempos de fabricação para o trem nas 3 operações são 1 2 e 1 minutos respectivamente Os tempos correspondentes para o caminhão são 2 0 e 4 minutos e para o carro são 1 2 e 0 minutos o zero indica que a operação não é utilizada Pedese a Modele este problema em termos de um problema de programação linear b Calcule caso exista uma solução ótima c Suponha que esta empresa deseja expandir sua linha de produção aumentando a capacidade diária de cada linha de produção em 40 passando para 602 644 e 588 minutos respectivamente Com estes aumentos como deverá ficar a solução final d Calcule a faixa de variação da capacidade de operação 3 Solução a Modelando o problema da empresa TOYCO Determinando as variáveis de decisão x1 número de trens produzidos diariamente x2 número de caminhões produzidos diariamente x3 número de carros produzidos diariamente Determinando as restrições Operação 1 x1 2x2 x3 430 Operação 2 2x1 0x2 2x3 460 Operação 3 x1 4x2 0x3 420 Não negatividade x1 x2 e x3 0 Determinando a função objetivo Maximizar o lucro z 3x1 2x2 5x3 Colocando em termos de um modelo de Programação Linear temos Maximizar z 3x1 2x2 5x3 Sujeito a x1 2x2 x3 430 2x1 0x2 2x3 460 x1 4x2 0x3 420 x1 x2 e x3 0 b Solução obtida pelo Método Simplex em forma de Quadros entra Base Z X1 X2 X3 X4 X5 X6 b RAZÃO MAX 1 3 2 5 0 0 0 0 X4 0 1 2 1 1 0 0 430 430 X5 0 2 0 2 0 1 0 460 230 Sai X6 0 1 4 0 0 0 1 420 entra Base Z X1 X2 X3 X4 X5 X6 b RAZÃO MAX 1 2 2 0 0 25 0 1150 X4 0 0 2 0 1 05 0 200 100 Sai X3 0 1 0 1 0 05 0 230 X6 0 1 4 0 0 0 1 420 105 Prof André Gandolpho DSc 20231 12 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Base Z X1 X2 X3 X4 X5 X6 b MAX 1 4 0 0 1 2 0 1350 X2 0 0 1 0 05 025 0 100 X3 0 1 0 1 0 05 0 230 X6 0 1 0 0 2 1 1 20 Tableau Final VALOR ÓTIMO DA FUNÇÃO OBJETIVO ENCONTRADO NA 2a ITERAÇÃO 1350 VARIÁVEL VALOR x1 000 x2 10000 x3 23000 c Supondo que o lado direito das restrições sofra as seguintes modificações Em termos de tableau final temse Neste Caso temos x1 0 x2 140 x3 322 x4 0 x5 0 x6 28 d Supondo que a terceira restrição sofra a seguinte alteração x1 2x2 x3 430 x1 2x2 x3 430 b3 Colocando em termos de matriz coluna No tableau inicial a coluna de b3 corresponde à coluna da variável de folga x6 Portanto depois de feitas as operações realizadas ao longo das iterações para a obtenção da solução ótima temse Para manter a não negatividade das variáveis básicas devese ter 20 b3 0 b3 20 Resumindo b3 20 b3 400 Prof André Gandolpho DSc 20231 13 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Complementando o exercício vamos calcular as variações para b1 e b2 Restrição 1 b1 430 b1 430 Δb1 No tableau inicial temos No tableau final temos 230Δb1 0 Δb1 230 Restrição 2 b2 460 b2 460 Δb2 No tableau inicial temos No tableau final temos 10005Δb2 0 Δb2 200 23005Δb2 0 Δb2 460 Prof André Gandolpho DSc 20231 14 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Calculando as variações dos coeficientes da função objetivo Base Z X1 X2 X3 X4 X5 X6 b MAX 1 4 0 0 1 2 0 1350 X2 0 0 1 0 05 025 0 100 X3 0 1 0 1 0 05 0 230 X6 0 1 0 0 2 1 1 20 Calculando a faixa de variação de c1 3 c1 3 Δc1 Base Z X1 X2 X3 X4 X5 X6 b MAX 1 4Δc1 0 0 1 2 0 1350 4Δc1 0 Δc1 4 Calcular a faixa de variação para o coeficiente c2 2 c2 2 Δc2 Base Z X1 X2 X3 X4 X5 X6 b MAX 1 4 Δc2 0 1 2 0 1350 Como x2 e variável básica temos que fazer uma operação elementar L0 L0 Δc2L1 Base Z X1 X2 X3 X4 X5 X6 b MAX 1 4 0 0 105 Δc2 205 Δc2 0 1350100 Δc2 1 05 Δc2 0 Δc2 2 2 05 Δc2 0 Δc2 4 Prof André Gandolpho DSc 20231 15 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP 33 Pedese resolver o seguinte problema de PL e determinar as faixas de variação dos custos de cada variável e as faixas de variação das constantes do lado direito de cada restrição de modo a manter a solução ótima Max Z x1 3x2 St 6x1 10x2 30 4x1 3x2 12 x1 2x2 4 x1 x2 0 Colocando as variáveis de folga Max Z x1 3x2 St 6x1 10x2 x3 30 4x1 3x2 x5 12 x1 2x2 x6 4 x1 x2 x3 x4 x5 x6 0 Resolvendo o modelo de PL com as variáveis de folga entra Base W X1 X2 X3 X4 X5 b RAZÃO MAX 1 1 3 0 0 0 0 X3 0 6 10 1 0 0 30 3 X4 0 4 3 0 1 0 12 4 X5 0 1 2 0 0 1 4 2 sai Base W X1 X2 X3 X4 X5 b MAX 1 12 0 0 0 32 6 X3 0 1 0 1 0 5 10 X4 0 52 0 0 1 32 6 X2 0 12 1 0 0 12 2 A partir do quadro acima serão determinados os valores dos c para cada uma das variáveis de decisão x1 e x2 a c1 12 05 ou seja para variações menores do que 12 no valor do coeficiente de c1 a solução permanece inalterada e ótima b Para a presente solução permanecer ótima devese ter ½ ½c2 0 c2 1 c2 1 3 2 32½c2 0 c2 3 c2 3 3 0 Desejase saber para que faixa de valores de cada elemento do lado direito a solução permanece ótima A análise segue para cada restrição a b1 10 30 20 b b2 6 12 6 c 26 b3 32 Prof André Gandolpho DSc 20231 16 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP 34 Seja o seguinte problema de Programação Linear e sua solução factível ótima conforme apresentado no tableau abaixo Determine a faixa de valores em que os coeficientes da Função Objetivo podem variar sem que a solução ótima mude Min Z 5x1 3x2 Sujeito a 3x1 5x2 15 5x1 2x2 10 x1 x2 0 Segue a solução do problema de PL feita no tableau Simplex ENTRA Base Z X1 X2 X3 X4 b RAZÃO MIN 1 5 3 0 0 0 X3 0 3 5 1 0 15 3 SAI X4 0 5 2 0 1 10 5 ENTRA Base Z X1 X2 X3 X4 b RAZÃO MIN 1 165 0 35 0 9 X2 0 35 1 15 0 3 5 X4 0 195 0 25 1 4 1 SAI Base Z X1 X2 X3 X4 b RAZÃO MIN 1 0 0 519 1619 23519 X2 0 0 1 519 319 4519 X4 0 1 0 219 519 2119 A partir do quadro acima serão determinados os valores dos c para cada uma das variáveis de decisão a c1 52 25 c1 165 32 b c2 1 c2 163 53333 Prof André Gandolpho DSc 20231 17 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP 35 Seja o seguinte problema de Programação Linear Determine a faixa de valores em que os coeficientes da Função Objetivo podem variar sem que a solução ótima mude Max Z 3x1 5x2 sa 2x1 3x2 30 3x1 8x2 70 x1 0 x2 0 Tableau inicial Base Z X1 X2 X3 X4 b MAX 1 3 5 0 0 0 X3 0 2 3 1 0 30 X4 0 3 8 0 1 70 Resolvendo o quadro acima usando o método Simplex temos Base Z X1 X2 X3 X4 b razao MAX 1 3 5 0 0 0 X3 0 2 3 1 0 30 10 X4 0 3 8 0 1 70 875 Base Z X1 X2 X3 X4 b MAX 1 1125 0 0 0625 4375 X3 0 0875 0 1 0375 375 4285714 X4 0 0375 1 0 0125 875 2333333 Base Z X1 X2 X3 X4 b MAX 1 0 0 1285714 0142857 4857143 X3 0 1 0 1142857 042857 4285714 X4 0 0 1 042857 0285714 7142857 Base Z X1 X2 X3 X4 b MAX 1 0 0 97 17 3407 X3 0 1 0 87 37 307 X4 0 0 1 37 27 507 Solução ótima FO 4857143 x1 4285714 x2 7142857 A partir do quadro acima que representa o tableau ótimo serão determinados os valores dos c para cada uma das variáveis de decisão x1 e x2 a Para a variável x1 que está na base o fato de colocarmos uma variação no problema inicial nos leva a ter no tableau final a mesma variação ou seja Max Z 3c1x1 5x2 sa 2x1 3x2 30 3x1 8x2 70 x1 0 x2 0 Prof André Gandolpho DSc 20231 18 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP No tableau inicial fica Base Z X1 X2 X3 X4 b MAX 1 3c1 5 0 0 0 X3 0 2 3 1 0 30 X4 0 3 8 0 1 70 No tableau final teremos Base Z X1 X2 X3 X4 b MAX 1 c1 0 97 17 3407 X3 0 1 0 87 37 307 X4 0 0 1 37 27 507 Para voltar a forma padrão temos que fazer uma operação neste tableau obtendo Base Z X1 X2 X3 X4 b MAX 1 0 0 9787c1 1737c1 3407307c1 X3 0 1 0 87 37 307 X4 0 0 1 37 27 507 Para se manter na solução ótima temos que 9787c1 0 1737c1 0 Resolvendo este sistema de inequações temos 98 c1 13 398 158 c1 313 103 b Para a variável x2 que está na base o fato de colocarmos uma variação no problema inicial nos leva a ter no tableau final a mesma variação ou seja Max Z 3x1 5c2x2 sa 2x1 3x2 30 3x1 8x2 70 x1 0 x2 0 No tableau inicial fica Base Z X1 X2 X3 X4 b MAX 1 3 5c2 0 0 0 X3 0 2 3 1 0 30 X4 0 3 8 0 1 70 Para voltar a forma padrão temos que fazer uma operação neste tableau obtendo Base Z X1 X2 X3 X4 b MAX 1 0 0 9737c2 1727c2 X3 0 1 0 87 37 307 X4 0 0 1 37 27 507 Para se manter na solução ótima temos que 9737c2 0 1727c2 0 Resolvendo este sistema de inequações temos 12 c1 3 512 92 c2 53 8 Prof André Gandolpho DSc 20231 19 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Referências Bibliográficas 1 Marco César Goldbarg and Henrique Pacca L Luna Otimização Combinatória e Programação Linear Modelos e Algoritmos Editora Campus 2a edição Rio de Janeiro 2005 2 Pizzolato Nélio Domingues Gandolpho André A Técnicas de Otimização LTC Rio de Janeiro 2005 3 Puccini Abelardo de Lima Pizzolato Nélio Domingues Programação Linear LTC 2a Edição Rio de Janeiro 4 Taha Hamdy A Pesquisa Operacional Editora Pearson 8a Edição 5 Arenales M Armentano V A Morabito R Yanasse H H Pesquisa Operacional Rio de Janeiro CampusElsevier 2007 523 p I Prof André Gandolpho DSc 20231 20
Envie sua pergunta para a IA e receba a resposta na hora
Texto de pré-visualização
UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP PESQUISA OPERACIONAL 1 ANÁLISE DE SENSIBILIDADE 1 Introdução O aspecto mais prático da Análise de Sensibilidade também chamada de análise de pós otimização consiste em responder à seguinte pergunta dada a solução ótima de um problema de Programação Linear para qual faixa de valores dos coeficientes a solução ótima seria mantida Tipos de alterações na estrutura de um modelo após a determinação de sua solução ótima 11 Alterações Simples alterações nos coeficientes de custo cj alterações nas constantes bi alterações nas restrições que podem incluir adição de novas variáveis eliminação de variáveis adição de novas restrições eliminação de restrições 12 Alterações Sistemáticas Programação Paramétrica alterações sistemáticas nos cj alterações sistemáticas nos bi A Análise de Sensibilidade aplicase a modificações pontuais nos coeficientes uma de cada vez Caso haja modificações simultâneas em diversos elementos há que considerar o problema como novo e resolvêlo desde seu início Outro tipo de alteração comum para a qual seria desejável a existência de algum procedimento simples seria a alteração dos coeficientes tecnológicos aij Para esses entretanto à exceção de casos particulares não existe nenhuma técnica sistemática e o problema deve ser considerado como novo Prof André Gandolpho DSc 20231 1 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP 11 Alterações Simples VARIAÇÕES NOS COEFICIENTES cj DA FUNÇÃO OBJETIVO Suponha um modelo de Programação Linear e sua solução ótima Desejase agora saber para que faixa de valores de cada coeficiente da função objetivo a solução permanece ótima A análise portanto considera a atual solução ótima e está dividida em duas partes se o coeficiente pertence a uma variável não básica e se o coeficiente pertence a uma variável básica VARIAÇÕES NAS CONSTANTES bi Suponha um modelo de Programação Linear e sua solução ótima Desejase saber para que faixa de valores de cada elemento do lado direito a solução permanece ótima A análise a seguir está dividida em duas partes caso em que a restrição não é ativa e caso em que a restrição é ativa No próximo item será apresentado um exemplo resolvido onde será possível explicar na prática os conceitos apresentados até aqui No item 3 temos mais exercícios do tópico Análise de Sensibilidade em Programação Linear com soluções Nas referências bibliográficas o aluno pode consultar as fontes de teoria e exercícios do tópico Análise de Sensibilidade em Programação Linear podendo aprofundar seus conhecimentos Este item está baseado no Capítulo 3 de Pizzolato Nélio Domingues Gandolpho André A Técnicas de Otimização LTC Rio de Janeiro 2005 Prof André Gandolpho DSc 20231 2 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP 2 Exemplo Resolvido Seja o seguinte problema de Programação Linear que será usado como veículo para ilustrar as metodologias da Análise de Sensibilidade MAX Z 5x1 7x2 3x3 Sujeito a 2x1 3x2 4x3 240 recurso 1 31 2x1 x2 x3 150 recurso 2 x1 80 recurso 3 x1 x2 x3 0 Acrescentandose as variáveis de folga temse o sistema 32 em que x1 x2 x3 além de Z são as variáveis reais do problema e as demais são as variáveis de folga acrescentados por força do método simplex MAX Z 5X1 7X2 3X3 0 X4 0 X5 0 X6 0 Sujeito a 2X1 3X2 4X3 X4 240 2X1 X2 X3 X5 150 32 X1 X6 80 X1 X2 X3 X4 X5 X6 0 Tableau Ótimo a Variação de cj para Xj não básica Variável não básica X3 Considere a variável X3 que tem valor nulo na solução ótima Intuitivamente caso o valor de seu coeficiente na FO original fosse mais favorável essa variável poderia ter valor positivo e este é o argumento que será explorado Na FO original temse Z 5X1 7X2 3X3 Suponha que o coeficiente de X3 seja alterado em Δc3 Portanto a FO original seria Z 5X1 7X2 3 Δc3 X3 Z 5X1 7X2 3 Δc3 X30 A aplicação do método simplex implicou na adição de múltiplos das linhas à FO até chegar à solução final em que o coeficiente de X3 é 625 O coeficiente recém acrescentado Δc3 apareceria na FO no último quadro como Z 57750 625 Δc3X3 225 X3 025 X5 Prof André Gandolpho DSc 20231 3 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Portanto a FO permanecerá ótima enquanto o coeficiente de X3 for não negativo ou seja 625 Δc3 0 Δc3 625 b Variação de cj para Xj básica Variável básica X1 Considere a variável básica X1 A FO do sistema original 31 consiste em Max Z 5X1 7X2 3X3 Suponha que o coeficiente de X1 seja alterado em Δc1 A FO original seria Z 5 Δc1X1 7X2 3X3 Introduzida no quadro final essa alteração faria com que o quadro se tornasse Base Z X1 X2 X3 X4 X5 X6 b Max 1 c1 0 625 225 025 0 57750 Linha 0 X2 0 0 1 15 05 05 0 450 Linha 1 X1 0 1 0 025 025 075 0 525 Linha 2 X6 0 0 0 025 025 075 1 275 Linha 3 Para zerar o custo reduzido da variável básica X1 há que se adicionar à linha 0 a linha 2 multiplicada por c1L0 L0 c1L2 As alterações resultantes na linha 0 estão transcritas no Quadro a seguir Base Z X1 X2 X3 X4 X5 X6 b Max 1 0 0 625025c1 225025c1 025075c1 0 57750525c1 Para a presente solução permanecer ótima devese ter 625 025c1 0 c1 625025 250 225 025c1 0 c1 225025 90 025 075c1 0 c1 025075 13 Portanto com respeito à variável X1 a função objetivo permanece inalterada enquanto 13 c1 9 Variável básica X2 Procedendose analogamente com a variável X2 supõese um acréscimo c2 em seu coeficiente de custo introduzido no quadro final disposto a seguir Prof André Gandolpho DSc 20231 4 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Base Z X1 X2 X3 X4 X5 X6 b Max 1 0 c2 625 225 025 0 57750 Linha 0 X2 0 0 1 15 05 05 0 450 Linha 1 X1 0 1 0 025 025 075 0 525 Linha 2 X6 0 0 0 025 025 075 1 275 Linha 3 Para zerar o custo reduzido da variável básica X2 há que se adicionar à linha 0 a linha 1 multiplicada por c2 No quadro resultante a única alteração ocorre na linha 0 a qual está transcrita no Quadro abaixo L0 L0 L1 Base Z X1 X2 X3 X4 X5 X6 b Max 1 0 0 625 15c2 225 05c2 025 05c2 0 57750 45c2 Para a presente solução permanecer básica devese ter 625 15c2 0 c2 62515 416667 12530 256 225 05c2 0 c2 22505 45 025 05c2 0 c2 02505 05 Portanto com respeito à variável X2 a função objetivo permanece inalterada enquanto 256 c2 05 Variações nas constantes do lado direito bi Suponha um modelo de Programação Linear e sua solução ótima Desejase saber para que faixa de valores de cada elemento do lado direito a solução permanece ótima A análise a seguir está dividida em duas partes caso em que a restrição não é ativa e caso em que a restrição é ativa Variação de bi em restrição não ativa Quando a restrição não é ativa a variável de folga correspondente é básica Considere a última restrição do sistema 31 que consiste em X1 80 e suponha que b3 80 seja alterado para X1 X6 80 b3 Prof André Gandolpho DSc 20231 5 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP De acordo com o quadro ótimo X1 525 e X6 275 Avaliação imediata sugere que aumentos em b3 não terão nenhum efeito na seleção ótima pois o insumo disponível supera o valor usado Por outro lado a quantidade de insumo pode ser reduzido com alteração da variável básica X6 a qual obedece à seguinte relação X6 275 b3 A condição para a atual solução continuar ótima é que X6 continue não negativa ou seja 275 b3 0 b3 275 Portanto para 80 275 525 a solução permanece ótima ou seja b3 80 80 275 80 635 Variação de bi em restrição ativa a Caso da 1a Restrição Considere a primeira restrição do sistema 31 qual seja 2X1 3X2 4X3 X4 240 A solução ótima indica que X4 0 tratandose portanto de uma restrição ativa Suponha agora que b1 seja alterado para A restrição passa a ser 2X1 3X2 4X3 X4 240 b1 O que se deseja saber é a influência que a variação b1 exerce sobre esta e sobre as demais restrições no decorrer dos pivotamentos Para simplificar suponha b1 1 e imagine um vetor coluna unitário com o valor 1 na primeira restrição e valores 0 nas outras duas Prof André Gandolpho DSc 20231 6 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Base Z X1 X2 X3 X4 X5 X6 b b1 Max 1 0 0 625 225 025 0 57750 0 X2 0 0 1 15 05 05 0 450 1 X1 0 1 0 025 025 075 0 525 0 X6 0 0 0 025 025 075 1 275 0 Tableau Inicial Tableau Final b b1 b b1 0 0 57750 225 240 1 450 05 150 0 525 025 80 0 275 025 Assim esse vetor adicionado ao lado direito do sistema é idêntico ao vetor unitário X4 e como todas as operações são elementares eles sofrem as mesmas alterações Desse modo eles coincidem no quadro final o qual indica que os componentes do vetor X4 são 05 025 025 nas linhas 1 2 e 3 respectivamente medindo os efeitos que a variação b1 1 exerce nos elementos do lado direito conferir no quadro anterior Multiplicando essas variações por b1 o lado direito do quadro final será X2 45 05b1 X1 525 025b1 X6 275 025b1 O conjunto dessas condições implica que 90 b1 210 ou seja b1 240 240 90 240 210 150 450 Prof André Gandolpho DSc 20231 7 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Nessa faixa de valores a solução ótima é composta pela mesma base ou seja pelas mesmas variáveis básicas embora com valores numéricos das variáveis e da função Z alterados em função da variação b1 A 2ª restrição do sistema 31 também é ativa no quadro ótimo com X5 0 Suponha que agora que b2 seja alterado para A restrição passa a ser 2X1 X2 X3 X5 150 b2 Novamente desejase saber qual a influência que a variação de b2 exerce sobre esta e sobre as demais restrições com os pivotamentos Como visto uma solução imediata para o sistema modificado consiste em estabelecer X5 b2 fazendo com que pequenas variações b2 estejam refletidas no valor de X5 Suponha uma variação unitária b2 1 e imagine um vetor unitário com valor 1 na 2ª restrição e valores zeros nas demais Observando o quadro ótimo do programa linear Quadro 32 o vetor X5 tem componentes 05 075 075 nas linhas 1 2 e 3 respectivamente indicando a influência que o vetor unitário b2 exerce no lado direito de cada uma das três restrições Assim multiplicandose essas alterações por b2 o lado direito do quadro final será X2 45 05 b2 X1 525 075 b2 X2 275 075 b2 Para se manter a não negatividade devese ter X2 45 05 b2 0 b2 4505 90 X1 525 075 b2 0 b2 525075 70 X2 275 075 b2 0 b2 275075 366667 O conjunto dessas restrições implica em 70 b2 366667 ou seja b2 150 150 70 150 366667 80 1866667 Prof André Gandolpho DSc 20231 8 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP 3 Exercícios Complementares 31 Seja o seguinte problema de PL já resolvido em lista anterior Determine a faixa de valores em que os coeficientes da Função Objetivo e das constantes do lado direito das restrições podem variar sem que a solução ótima mude Max Z 8x1 5x2 sa 12x1 10x2 150 x1 130 x2 100 40x1 60x2 567 x1 x2 0 Resolvendo o problema de PL utilizando o Método Simplex em forma de quadros Colocando as variáveis de folga Max Z 8x1 5x2 sa 12x1 10x2 x3 150 x1 x4 130 x2 x5 100 40x1 60x2 x6 567 x1 x2 x3 x4 x5 x6 0 TABLEAU INICIAL ENTRA Base Z X1 X2 X3 X4 X5 X6 b RAZÃO MAX 1 8 5 0 0 0 0 0 X3 0 12 10 1 0 0 0 150 125 SAI X4 0 1 0 0 1 0 0 130 130 X5 0 0 1 0 0 1 0 100 X6 0 40 60 0 0 0 1 567 14175 1a iteração TABLEAU ÓTIMO Base Z X1 X2 X3 X4 X5 X6 b RAZÃO MAX 1 0 53 23 0 0 0 100 X1 0 1 56 112 0 0 0 252 X4 0 0 56 112 1 0 0 2352 X5 0 0 1 0 0 1 0 100 X6 0 0 803 103 0 0 1 67 Solução ótima x1 252 x2 0 x3 0 x4 0 Z 100 Respostas da Análise de Sensibilidade Faixa de Variação dos Custos c1 2 c1 6 c2 53 1666 Faixa de Variação das Constantes do Lado Direito 150 b1 201 b2 2352 b3 100 b4 67 Solução da Análise de Sensibilidade Prof André Gandolpho DSc 20231 9 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Analisando a variável não básica X2 temos que no tableau final trocar o coeficiente original c2 por c2 ou seja c 5 c2 5 c2 No tableau final temos Base Z X1 X2 X3 X4 X5 X6 B MAX 1 0 53c2 23 0 0 0 100 X1 0 1 56 112 0 0 0 252 X4 0 0 56 112 1 0 0 2352 X5 0 0 1 0 0 1 0 100 X6 0 0 803 103 0 0 1 67 Portanto para que continuemos no ótimo 53c2 0 53 c2 Analisando a variável básica X1 temos que no tableau final trocar o coeficiente original c1 por c1 ou seja c1 8 c1 8 c1 No tableau final temos Base Z X1 X2 X3 X4 X5 X6 B MAX 1 c1 53 23 0 0 0 100 X1 0 1 56 112 0 0 0 252 X4 0 0 56 112 1 0 0 2352 X5 0 0 1 0 0 1 0 100 X6 0 0 803 103 0 0 1 67 Como a variável x1 é básica temos que fazer a seguinte operação na linha 0 do tableau final L0 L0 c1 Base Z X1 X2 X3 X4 X5 X6 B RAZÃO MAX 1 0 5356c1 23112c1 0 0 0 100252c1 Para permanecer no ótimo temos as seguintes condições 5356c10 c1 2 23112c10 c1 8 c1 2 c1 6 Analisando as variações das constantes do lado direito das restrições temos Restrição 1 b1 150 b1 150 b1 b b1 bf b1f 150 1 252 112 130 0 2352 112 100 0 100 0 567 0 67 103 252 112 b10 2352 112b10 100 0b10 67 103b10 150 b1 201 Continuando a análise das variações das constantes do lado direito da restrição 3 temos que b2 130 b2 130 b2 Prof André Gandolpho DSc 20231 10 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Tableau Inicial Tableau Final B b2 bf b2f 150 0 252 0 130 1 2352 1 100 0 100 0 567 0 67 0 Resolvendo o sistema composto pelas condições que o lado direito tem que ser não negativo temos 2352 b20 Continuando a análise das variações das constantes do lado direito da restrição 3 temos que b3 130 b3 130 b3 Tableau Inicial Tableau Final b b3 bf b3f 150 0 252 0 130 0 2352 0 100 1 100 1 567 0 67 0 Resolvendo o sistema composto pelas condições que o lado direito tem que ser não negativo temos 100 b30 b3 100 Tableau Inicial Tableau Final b b4 bf b4f 150 0 252 0 130 0 2352 0 100 0 100 0 567 1 67 1 Resolvendo o sistema composto pelas condições que o lado direito tem que ser não negativo temos 67 b40 b4 67 Prof André Gandolpho DSc 20231 11 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP 32 Seja o seguinte problema de Programação Linear extraído de TAHA Handy A Pesquisa Operacional 8 Ed São Paulo Pearson Prentice Hall 2008 A empresa TOYCO produz 3 tipos de brinquedos trens caminhões e carros Para isso a empresa usa 3 operações Os limites diários de tempo disponível minutos para as 3 operações são 430 460 e 420 minutos respectivamente e os lucros para os trens caminhões e carros são 3 2 e 5 respectivamente Os tempos de fabricação para o trem nas 3 operações são 1 2 e 1 minutos respectivamente Os tempos correspondentes para o caminhão são 2 0 e 4 minutos e para o carro são 1 2 e 0 minutos o zero indica que a operação não é utilizada Pedese a Modele este problema em termos de um problema de programação linear b Calcule caso exista uma solução ótima c Suponha que esta empresa deseja expandir sua linha de produção aumentando a capacidade diária de cada linha de produção em 40 passando para 602 644 e 588 minutos respectivamente Com estes aumentos como deverá ficar a solução final d Calcule a faixa de variação da capacidade de operação 3 Solução a Modelando o problema da empresa TOYCO Determinando as variáveis de decisão x1 número de trens produzidos diariamente x2 número de caminhões produzidos diariamente x3 número de carros produzidos diariamente Determinando as restrições Operação 1 x1 2x2 x3 430 Operação 2 2x1 0x2 2x3 460 Operação 3 x1 4x2 0x3 420 Não negatividade x1 x2 e x3 0 Determinando a função objetivo Maximizar o lucro z 3x1 2x2 5x3 Colocando em termos de um modelo de Programação Linear temos Maximizar z 3x1 2x2 5x3 Sujeito a x1 2x2 x3 430 2x1 0x2 2x3 460 x1 4x2 0x3 420 x1 x2 e x3 0 b Solução obtida pelo Método Simplex em forma de Quadros entra Base Z X1 X2 X3 X4 X5 X6 b RAZÃO MAX 1 3 2 5 0 0 0 0 X4 0 1 2 1 1 0 0 430 430 X5 0 2 0 2 0 1 0 460 230 Sai X6 0 1 4 0 0 0 1 420 entra Base Z X1 X2 X3 X4 X5 X6 b RAZÃO MAX 1 2 2 0 0 25 0 1150 X4 0 0 2 0 1 05 0 200 100 Sai X3 0 1 0 1 0 05 0 230 X6 0 1 4 0 0 0 1 420 105 Prof André Gandolpho DSc 20231 12 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Base Z X1 X2 X3 X4 X5 X6 b MAX 1 4 0 0 1 2 0 1350 X2 0 0 1 0 05 025 0 100 X3 0 1 0 1 0 05 0 230 X6 0 1 0 0 2 1 1 20 Tableau Final VALOR ÓTIMO DA FUNÇÃO OBJETIVO ENCONTRADO NA 2a ITERAÇÃO 1350 VARIÁVEL VALOR x1 000 x2 10000 x3 23000 c Supondo que o lado direito das restrições sofra as seguintes modificações Em termos de tableau final temse Neste Caso temos x1 0 x2 140 x3 322 x4 0 x5 0 x6 28 d Supondo que a terceira restrição sofra a seguinte alteração x1 2x2 x3 430 x1 2x2 x3 430 b3 Colocando em termos de matriz coluna No tableau inicial a coluna de b3 corresponde à coluna da variável de folga x6 Portanto depois de feitas as operações realizadas ao longo das iterações para a obtenção da solução ótima temse Para manter a não negatividade das variáveis básicas devese ter 20 b3 0 b3 20 Resumindo b3 20 b3 400 Prof André Gandolpho DSc 20231 13 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Complementando o exercício vamos calcular as variações para b1 e b2 Restrição 1 b1 430 b1 430 Δb1 No tableau inicial temos No tableau final temos 230Δb1 0 Δb1 230 Restrição 2 b2 460 b2 460 Δb2 No tableau inicial temos No tableau final temos 10005Δb2 0 Δb2 200 23005Δb2 0 Δb2 460 Prof André Gandolpho DSc 20231 14 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Calculando as variações dos coeficientes da função objetivo Base Z X1 X2 X3 X4 X5 X6 b MAX 1 4 0 0 1 2 0 1350 X2 0 0 1 0 05 025 0 100 X3 0 1 0 1 0 05 0 230 X6 0 1 0 0 2 1 1 20 Calculando a faixa de variação de c1 3 c1 3 Δc1 Base Z X1 X2 X3 X4 X5 X6 b MAX 1 4Δc1 0 0 1 2 0 1350 4Δc1 0 Δc1 4 Calcular a faixa de variação para o coeficiente c2 2 c2 2 Δc2 Base Z X1 X2 X3 X4 X5 X6 b MAX 1 4 Δc2 0 1 2 0 1350 Como x2 e variável básica temos que fazer uma operação elementar L0 L0 Δc2L1 Base Z X1 X2 X3 X4 X5 X6 b MAX 1 4 0 0 105 Δc2 205 Δc2 0 1350100 Δc2 1 05 Δc2 0 Δc2 2 2 05 Δc2 0 Δc2 4 Prof André Gandolpho DSc 20231 15 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP 33 Pedese resolver o seguinte problema de PL e determinar as faixas de variação dos custos de cada variável e as faixas de variação das constantes do lado direito de cada restrição de modo a manter a solução ótima Max Z x1 3x2 St 6x1 10x2 30 4x1 3x2 12 x1 2x2 4 x1 x2 0 Colocando as variáveis de folga Max Z x1 3x2 St 6x1 10x2 x3 30 4x1 3x2 x5 12 x1 2x2 x6 4 x1 x2 x3 x4 x5 x6 0 Resolvendo o modelo de PL com as variáveis de folga entra Base W X1 X2 X3 X4 X5 b RAZÃO MAX 1 1 3 0 0 0 0 X3 0 6 10 1 0 0 30 3 X4 0 4 3 0 1 0 12 4 X5 0 1 2 0 0 1 4 2 sai Base W X1 X2 X3 X4 X5 b MAX 1 12 0 0 0 32 6 X3 0 1 0 1 0 5 10 X4 0 52 0 0 1 32 6 X2 0 12 1 0 0 12 2 A partir do quadro acima serão determinados os valores dos c para cada uma das variáveis de decisão x1 e x2 a c1 12 05 ou seja para variações menores do que 12 no valor do coeficiente de c1 a solução permanece inalterada e ótima b Para a presente solução permanecer ótima devese ter ½ ½c2 0 c2 1 c2 1 3 2 32½c2 0 c2 3 c2 3 3 0 Desejase saber para que faixa de valores de cada elemento do lado direito a solução permanece ótima A análise segue para cada restrição a b1 10 30 20 b b2 6 12 6 c 26 b3 32 Prof André Gandolpho DSc 20231 16 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP 34 Seja o seguinte problema de Programação Linear e sua solução factível ótima conforme apresentado no tableau abaixo Determine a faixa de valores em que os coeficientes da Função Objetivo podem variar sem que a solução ótima mude Min Z 5x1 3x2 Sujeito a 3x1 5x2 15 5x1 2x2 10 x1 x2 0 Segue a solução do problema de PL feita no tableau Simplex ENTRA Base Z X1 X2 X3 X4 b RAZÃO MIN 1 5 3 0 0 0 X3 0 3 5 1 0 15 3 SAI X4 0 5 2 0 1 10 5 ENTRA Base Z X1 X2 X3 X4 b RAZÃO MIN 1 165 0 35 0 9 X2 0 35 1 15 0 3 5 X4 0 195 0 25 1 4 1 SAI Base Z X1 X2 X3 X4 b RAZÃO MIN 1 0 0 519 1619 23519 X2 0 0 1 519 319 4519 X4 0 1 0 219 519 2119 A partir do quadro acima serão determinados os valores dos c para cada uma das variáveis de decisão a c1 52 25 c1 165 32 b c2 1 c2 163 53333 Prof André Gandolpho DSc 20231 17 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP 35 Seja o seguinte problema de Programação Linear Determine a faixa de valores em que os coeficientes da Função Objetivo podem variar sem que a solução ótima mude Max Z 3x1 5x2 sa 2x1 3x2 30 3x1 8x2 70 x1 0 x2 0 Tableau inicial Base Z X1 X2 X3 X4 b MAX 1 3 5 0 0 0 X3 0 2 3 1 0 30 X4 0 3 8 0 1 70 Resolvendo o quadro acima usando o método Simplex temos Base Z X1 X2 X3 X4 b razao MAX 1 3 5 0 0 0 X3 0 2 3 1 0 30 10 X4 0 3 8 0 1 70 875 Base Z X1 X2 X3 X4 b MAX 1 1125 0 0 0625 4375 X3 0 0875 0 1 0375 375 4285714 X4 0 0375 1 0 0125 875 2333333 Base Z X1 X2 X3 X4 b MAX 1 0 0 1285714 0142857 4857143 X3 0 1 0 1142857 042857 4285714 X4 0 0 1 042857 0285714 7142857 Base Z X1 X2 X3 X4 b MAX 1 0 0 97 17 3407 X3 0 1 0 87 37 307 X4 0 0 1 37 27 507 Solução ótima FO 4857143 x1 4285714 x2 7142857 A partir do quadro acima que representa o tableau ótimo serão determinados os valores dos c para cada uma das variáveis de decisão x1 e x2 a Para a variável x1 que está na base o fato de colocarmos uma variação no problema inicial nos leva a ter no tableau final a mesma variação ou seja Max Z 3c1x1 5x2 sa 2x1 3x2 30 3x1 8x2 70 x1 0 x2 0 Prof André Gandolpho DSc 20231 18 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP No tableau inicial fica Base Z X1 X2 X3 X4 b MAX 1 3c1 5 0 0 0 X3 0 2 3 1 0 30 X4 0 3 8 0 1 70 No tableau final teremos Base Z X1 X2 X3 X4 b MAX 1 c1 0 97 17 3407 X3 0 1 0 87 37 307 X4 0 0 1 37 27 507 Para voltar a forma padrão temos que fazer uma operação neste tableau obtendo Base Z X1 X2 X3 X4 b MAX 1 0 0 9787c1 1737c1 3407307c1 X3 0 1 0 87 37 307 X4 0 0 1 37 27 507 Para se manter na solução ótima temos que 9787c1 0 1737c1 0 Resolvendo este sistema de inequações temos 98 c1 13 398 158 c1 313 103 b Para a variável x2 que está na base o fato de colocarmos uma variação no problema inicial nos leva a ter no tableau final a mesma variação ou seja Max Z 3x1 5c2x2 sa 2x1 3x2 30 3x1 8x2 70 x1 0 x2 0 No tableau inicial fica Base Z X1 X2 X3 X4 b MAX 1 3 5c2 0 0 0 X3 0 2 3 1 0 30 X4 0 3 8 0 1 70 Para voltar a forma padrão temos que fazer uma operação neste tableau obtendo Base Z X1 X2 X3 X4 b MAX 1 0 0 9737c2 1727c2 X3 0 1 0 87 37 307 X4 0 0 1 37 27 507 Para se manter na solução ótima temos que 9737c2 0 1727c2 0 Resolvendo este sistema de inequações temos 12 c1 3 512 92 c2 53 8 Prof André Gandolpho DSc 20231 19 UNIVERSIDADE CATÓLICA DE PETRÓPOLIS UCP Referências Bibliográficas 1 Marco César Goldbarg and Henrique Pacca L Luna Otimização Combinatória e Programação Linear Modelos e Algoritmos Editora Campus 2a edição Rio de Janeiro 2005 2 Pizzolato Nélio Domingues Gandolpho André A Técnicas de Otimização LTC Rio de Janeiro 2005 3 Puccini Abelardo de Lima Pizzolato Nélio Domingues Programação Linear LTC 2a Edição Rio de Janeiro 4 Taha Hamdy A Pesquisa Operacional Editora Pearson 8a Edição 5 Arenales M Armentano V A Morabito R Yanasse H H Pesquisa Operacional Rio de Janeiro CampusElsevier 2007 523 p I Prof André Gandolpho DSc 20231 20