·
Engenharia de Produção ·
Outros
Envie sua pergunta para a IA e receba a resposta na hora
Texto de pré-visualização
Análise de Pós Otimização ou de Sensibilidade Algébrica Nos modelos de programação linear muitas vezes não se conhecem com exatidão os coeficientes C j a ij e b i Diante disso são nestes casos necessários ajustes no modelo originalmente adotado Esses ajustes podem indicar modificações em determinados coeficientes iniciais adição de novas variáveis ou restrições ou ainda supressão de determinadas variáveis ou restrições Assim é importante saber que alterações seriam provocadas ou não na solução ótima já obtida Observe que com esta modificação o problema permanece factível pois as restrições não são alteradas I Mudanças nos coeficientes de custos Cj quando Cj é de xj nãobásica na tabela final p j Variabilidade líquida entre o Custo Reduzido da tabela inicial e o Custo Reduzido da tabela final jtabela inicial tabela final j j CR CR p Custo Reduzido da variável x onde j CRj Custo Reduzido Modificado da variável x onde j j CRM jtabela inicial tabela final j j CRM CRM p Variabilidade líquida Uma indústria produz dois tipos de porcas para parafusos alfa e beta que usam duas máquinas para serem fabricadas um torno e uma furadeira ambos mecânicos conforme os tempos de produção apresentados na tabela Tempo para fabricar um quilo de porcas tipo Alfa em horasKg Tempo para fabricar um quilo de porcas tipo Beta em horasKg Disponibilidade máxima diária das máquinas em horas hdia Torno 1hKg 0hKg 3hdia Furadeira 2hKg 3hKg 24hdia Lucro por quilo Rkg 1RKg 3RKg Determine quantos quilosdia de porcas dos tipos Alfa e Beta devem ser produzidos de forma a maximizar o lucro diário da indústria Exemplo 1 0 x x 24 3x 2x 3 x sa 3x Z x max primal 1 Seja o 2 1 2 1 1 2 1 0 x x 24 3x 2x 3 x sa 3x x max Z primal 1 Seja o 2 1 2 1 1 2 1 QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 1 0 0 1 24 x3 0 1 0 1 0 3 x2 0 23 1 0 13 8 24 3 8 2 0 3 com o mesmo valor Z permanece 0 entãoo valor da nova função objetivo básica e portanto x é não na otimização x Como 8 0 a solução ótima continua a mesma ou seja X então não básica x não entra na base problema é de máximo a variável o e 2 1 o CRM Como 2 1 CRM 2 3 CRM 2 CRM CRM p 0 2 x 3x 3 constante e na tabela a nova função objetivo fica Z 2 permanece p Como x na nova tabela final será o novo CRM da variável Qual 2 1 1 CR CR p 0 1 tabela inicial Z do problema original ficaria Na max 1 1 1 tabela final 1 1tabela final 1tabela final 1tabela inicial tabela final 1 1 2 1 1 1 1tabela inicial tabela final 1 1 2 1 3x x Z 2 1 x 3x Suponha que haja mudança da função objetivo para max Z 2 3 Tabela Inicial Z x1 x2 x3 x4 RHS Z 1 1 3 0 0 0 x3 0 1 0 1 0 3 x4 0 2 3 0 1 24 Uma indústria produz dois tipos de porcas para parafusos alfa e beta que usam duas máquinas para serem fabricadas um torno e uma furadeira ambos mecânicos conforme os tempos de produção apresentados na tabela Tempo para fabricar um quilo de porcas tipo Alfa em horasKg Tempo para fabricar um quilo de porcas tipo Beta em horasKg Disponibilidade máxima diária das máquinas em horas hdia Torno 1hKg 0hKg 3hdia Furadeira 2hKg 3hKg 24hdia Lucro por quilo Rkg 1RKg 3RKg Determine quantos quilosdia de porcas dos tipos Alfa e Beta devem ser produzidos de forma a maximizar o lucro diário da indústria Exemplo 2 0 x x 24 3x 2x 3 x sa 3x Z x max rimal Seja o p 2 1 2 1 1 2 1 2 0 x x 24 3x 2x 3 x sa 3x Z x max rimal Seja o p 2 1 2 1 1 2 1 2 QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 1 0 0 1 24 x3 0 1 0 1 0 3 x2 0 23 1 0 13 8 2 1 3x Suponha que haja mudança da função objetivo para max Z 3x novo valor de Z o e será a nova solução ótima Qual nova tabela final da solução ótima não continua a mesma então devemos dar continuidade ao método simplex a partir a e não básica x entra na base problema é de máximo a variável o 1 o CRM Como 1 CRM 3 CRM 2 CRM CRM p 0 constante e na tabela a nova função objetivo fica Z 3x 3x 2 permanece p Como x na nova tabela final será o novo CRM da variável Qual 2 1 1 CR CR p 0 1 tabela inicial Z do problema original ficaria Na max 1 tabela final 1 1tabela final 1tabela final 1tabela inicial tabela final 1 1 2 1 1 1 1tabela inicial tabela final 1 1 2 1 3x x Z Continua 1 Tabela Inicial Z x1 x2 x3 x4 RHS Z 1 1 3 0 0 0 x3 0 1 0 1 0 3 x4 0 2 3 0 1 24 0 x x 24 3x 2x 3 x sa 3x Z x max rimal Seja o p 2 1 2 1 1 2 1 2 QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 1 0 0 1 24 x3 0 1 0 1 0 3 x2 0 23 1 0 13 8 Novo QUADRO para max z3x 1 3x2 Z x1 x2 x3 x4 RHS Z 1 1 0 0 1 24 x3 0 1 0 1 0 3 x2 0 23 1 0 13 8 Novo QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 0 0 1 1 27 x1 0 1 0 1 0 3 x2 0 0 1 23 13 6 27 36 33 3 e Z X max 6 1 CRM 1tabela final Continuação Observe que com esta modificação o problema permanece factível pois as restrições não são alteradas II Mudanças simples nos coeficientes de custos Cj mudança em Cj quando xj é básica na tabela final Uma indústria produz dois tipos de porcas para parafusos alfa e beta que usam duas máquinas para serem fabricadas um torno e uma furadeira ambos mecânicos conforme os tempos de produção apresentados na tabela Tempo para fabricar um quilo de porcas tipo Alfa em horasKg Tempo para fabricar um quilo de porcas tipo Beta em horasKg Disponibilidade máxima diária das máquinas em horas hdia Torno 1hKg 0hKg 3hdia Furadeira 2hKg 3hKg 24hdia Lucro por quilo Rkg 1RKg 3RKg Determine quantos quilosdia de porcas dos tipos Alfa e Beta devem ser produzidos de forma a maximizar o lucro diário da indústria Exemplo 3 0 x x 24 3x 2x 3 x sa 3x Z x max rimal Seja o p 2 1 2 1 1 2 1 3 0 x x 24 3x 2x 3 x sa 3x Z x max Seja o primal Ex 2 1 2 1 1 2 1 3 QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 1 0 0 1 24 x3 0 1 0 1 0 3 x2 0 23 1 0 13 8 QUADRO ATUALIZADO Z x1 x2 x3 x4 RHS Z 1 1 2 0 1 24 x3 0 1 0 1 0 3 x2 0 23 1 0 13 8 QUADRO ATUALIZADO Z x1 x2 x3 x4 RHS Z 1 13 0 0 13 8 x3 0 1 0 1 0 3 x2 0 23 1 0 13 8 2 1 x Suponha que haja mudança da função objetivo para max Z x 1 2 CRM 1 CRM 3 CRM CRM p 0 então constantee Z x 1 x 3 permanece p Como novo valor de Z o e a nova solução ótima será x na nova tabela final e qual será o novo CRM da variável Qual 3 3 0 CR CR p 0 tabela inicial Z do problema original ficaria Na 2tabela final 2tabela final 2tabela inicial tabela final 2 2 2 1 2 max 2 2tabela inicial tabela final 2 2 2 1 3 x x Z Continua Tabela Inicial Z x1 x2 x3 x4 RHS Z 1 1 3 0 0 0 x3 0 1 0 1 0 3 x4 0 2 3 0 1 24 QUADRO ATUALIZADO Z x1 x2 x3 x4 RHS Z 1 13 0 0 13 8 x3 0 1 0 1 0 3 x2 0 23 1 0 13 8 NOVO QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 0 0 13 13 9 x1 0 1 0 1 0 3 x2 0 0 1 23 13 6 9 3 e Z X max 6 Continuação III Mudanças nos termos RHS bi 18 1 e b para b de b lise de pós otimização supondo que haja mudança nas componentes Faça a aná 2 1 i QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 0 0 13 13 9 x1 0 1 0 1 0 3 x2 0 0 1 23 13 6 0 x x 24 3x 2x 3 x sa x Z x max 1 Seja o primal EX 2 1 2 1 1 2 1 Tempo para fabricar um quilo de porcas tipo Alfa em horasKg Tempo para fabricar um quilo de porcas tipo Beta em horasKg Disponibilidade máxima diária das máquinas em horas hdia Torno 1hKg 0hKg 3hdia Furadeira 2hKg 3hKg 24hdia Lucro por quilo Rkg 1RKg 1RKg Tabela Inicial Z x1 x2 x3 x4 RHS Z 1 1 1 0 0 0 x3 0 1 0 1 0 3 x4 0 2 3 0 1 24 6 3 24 3 1 0 1 0 1 0 1 1 0 3 0 0 B 1 2 1 das restrições e dos termos independentes da tabela inicial ndose B pelas colunas dos coefientes multiplica das restrições e dos termos independentes da tabela final poderão ser obtidas Desta forma as colunas dos coefientes 4 3 1 3 2 0 1 e a matriz B e variáveis de folga são As às variáveis de folga no exemplo A inversa B será formada pelas colunas da tabela final referentes 3 3 2 0 1 B às variáveis básicas do item 1 no exemplo Construa a matriz da base B com as colunas da tabela inicial referentes 2 e Identifiqu e as variáveis básicas na tabela final no exemplo 1 os seguintes passos Siga 4 3 2 1 1 1 4 3 1 2 1 3 1 3 2 0 1 b B 3 3 1 3 2 0 1 a B 3 2 3 1 3 2 0 1 B a 3 1 3 2 0 1 a 3 1 3 2 0 1 a B x x x x 1 1 1 1 1 Propriedades QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 0 0 13 13 9 x1 0 1 0 1 0 3 x2 0 0 1 23 13 6 Tabela Inicial Z x1 x2 x3 x4 RHS Z 1 1 1 0 0 0 x3 0 1 0 1 0 3 x4 0 2 3 0 1 24 6 33 max 3 19 Z 3 16 1 e x x básicas porém com os valores variáveis va solução ótima contém as mesmas Logo a no 3 16 1 18 1 3 1 3 2 0 1 b B s Então temo 18 1 e b b tal que os novos valores sejam de b e haja mudança nas componentes Suponha qu 2 1 1 2 1 i B Resolução QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 0 0 13 13 9 x1 0 1 0 1 0 3 x2 0 0 1 23 13 6 0 x x x x 24 1x 3x 2x 3 1x x sa 0 0x 0x x x Z max 2 1 4 2 1 3 1 4 3 2 1 4 3 Tabela Inicial Z x1 x2 x3 x4 RHS Z 1 1 1 0 0 0 x3 0 1 0 1 0 3 x4 0 2 3 0 1 24 se ade e aplicando o dual simplex obtém lução viol a factibilid Logo a so 3 1 3 2 3 1 3 2 0 1 b B 3 2 e b b e haja mudança nas componentesde b tal que os novos valores sejam Suponha qu 1 2 1 i 2 NOVO QUADRO Z x1 x2 x3 x4 RHS Z 1 0 0 13 13 53 x1 0 1 0 1 0 2 x2 0 0 1 23 13 13 QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 0 0 13 13 9 x1 0 1 0 1 0 3 x2 0 0 1 23 13 6 53 13 2 z 0 x x 24 3x 2x 3 x sa x Z x max Seja o primal EX 2 1 2 1 1 2 1 2 Tabela Inicial Z x1 x2 x3 x4 RHS Z 1 1 1 0 0 0 x3 0 1 0 1 0 3 x4 0 2 3 0 1 24 2 3 0 2 3 max Z e x x va solução ótima será Logo a no 2 1 Tempo para fabricar um quilo de porcas tipo Alfa em horasKg Tempo para fabricar um quilo de porcas tipo Beta em horasKg Disponibilidade máxima diária das máquinas em horas hdia Torno 1hKg 0hKg 3hdia Furadeira 2hKg 3hKg 24hdia Lucro por quilo Rkg 1RKg 1RKg Problema Original Z x1 x2 x3 x4 x5 RHS Z 1 0 19 0 3 1 150 x1 0 1 1 0 1 2 20 x3 0 0 3 1 1 1 10 10 20 30 40 1 1 2 1 1 2 1 0 1 1 2 1 1 1 0 1 1 1 2 1 1 0 1 2 1 1 2 1 3 1 2 5 1 1 2 1 0 1 1 1 1 1 2 1 1 1 2 1 1 1 2 1 4 4 3 2 1 B b B a a B B a a a B 1 1 1 1 1 1 B B B 1 Max Z 4x1 2x2 7x3 sa 1 x1 5x2 2 x3 x4 40 1 x1 2x2 1 x3 x5 30 0 x x x 2x x 30 x sa x 5x 2x 40 2x 7x 4x Max Z Seja o primal 4 EX 3 2 1 3 2 1 3 2 1 3 2 1 OBS Exemplo com mais variáveis que restrições IV Acréscimo de nova restrição Observe que como a inclusão de nova restrição pode provocar uma redução na região viável então a função objetivo deve sofrer uma piora ou na melhor das hipóteses não sofre alteração O procedimento é verificar se atual solução satisfaz a nova restrição Se satisfaz então a solução ótima continua sendo a mesma Se não satisfaz então devese acrescentar no quadro ótimo uma linha devida à nova restrição e prosseguir com o método simplex ou com o dualsimplex QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 1 0 0 1 24 x3 0 1 0 1 0 3 x2 0 23 1 0 13 8 inserida conjuntamente a variável de folga x seja mos introduzir uma linha no quadro ótimo cuidando para que Então deve 30 48 6 8 0 08 X ução ótima não satisfaz a nova restrição Como a sol 30 6x x o galvanização e seja acrescentada a restriçã Suponha qu 5 2 1 NOVO QUADRO Z x1 x2 x3 x4 x5 RHS Z 1 1 0 0 1 0 24 x3 0 1 0 1 0 0 3 x2 0 23 1 0 13 0 8 x5 0 1 6 0 0 1 30 QUADRO ATUALIZADO Z x1 x2 x3 x4 x5 RHS Z 1 1 0 0 1 0 24 x3 0 1 0 1 0 0 3 x2 0 23 1 0 13 0 8 x5 0 3 0 0 2 1 18 24 8 0 min e Z X Transformar o 6 em zero pois x2 está na base Não altera pois x5 é de folga 0 x x 24 3x 2x 3 x sa 3x Z x max Seja o primal EX 2 1 2 1 1 2 1 Tabela Inicial Z x1 x2 x3 x4 RHS Z 1 1 3 0 0 0 x3 0 1 0 1 0 3 x4 0 2 3 0 1 24 05 2 1 033 entra a var da maior resultado 3 1 de Max é Algoritmo Dual quando o primal QUADRO ATUALIZADO Z x1 x2 x3 x4 x5 RHS Z 1 1 0 0 1 0 24 x3 0 1 0 1 0 0 3 x2 0 23 1 0 13 0 8 x5 0 3 0 0 2 1 18 2 33 9 2 3 max Z e x x va solução ótima será Logo a no 2 1 QUADRO ATUALIZADO Z x1 x2 x3 x4 x5 RHS Z 1 0 0 0 13 13 18 x3 0 0 0 1 23 13 3 x2 0 0 1 0 19 29 4 x1 0 1 0 0 23 13 6 QUADRO ATUALIZADO Z x1 x2 x3 x4 x5 RHS Z 1 0 0 12 0 12 332 x4 0 0 0 32 1 12 92 x2 0 0 1 16 0 16 92 x1 0 1 0 1 0 0 3 V Eliminação de uma restrição de desigualdade ário devese considerar um novo problema Caso contr a mesma após sua retirada permanece o original não é ativa e portanto a solução a restriçã for básica na otimalidade temse que de folga var Então se x 0 seja retirada x 6x x 0 6x x e em um problema a restrição Suponha qu 5 5 2 1 2 1 VI Eliminação de uma restrição de igualdade problema sem a restrição se recomeçar o Neste caso sugere VII Eliminação de uma variável xj simplex ou dualsimplex do método e prosseguir o processo com o uso do quadro a não básica em seguida retirála a tornál rma o pivotamento de fo se forçar então deve ável eliminada for básica na otimalidade Se a vari lução permanece a mesma pois x então a so vel eliminada não é básica na otimalidade Se a variá j 0 VIII Inclusão de uma variável xj do objetivo e nas demais restrições é acrescenta na função es com componentes coeficient os todo um vetor de Nestes cas 0 x x x x x x x x x x 5 3x x x x x sa x x Z x max EX 2 1 2 1 2 1 2 1 6 5 4 3 6 5 3 4 3 3 0 4 2 7 2 0 x x x x x x x x x x 5 3x x x x 1 x sa x x Z x max 2 1 2 1 2 1 2 1 6 5 4 3 6 5 3 4 3 3 0 1 1 1 4 2 7 2 TABELA FINAL Z x1 x2 x3 x4 x5 x6 RHS Z 1 0 0 0 2 1 1 13 x1 0 1 0 0 3 2 2 2 x2 0 0 1 0 3 2 3 2 x3 0 0 0 1 1 1 1 1 1 1 1 3 2 3 2 2 3 B 0 1 1 3 1 0 2 0 1 B 2 1 0 a a a a 4 e o vetor a nas restrições igual a e na função objetivo c coeficient l x com introdução de uma nova variáve Suponha a 1 37 27 17 7 7 7 7 0 x x x x x x x x x x 5 3x x x x 1 x sa x x Z x max 2 1 2 1 2 1 2 1 6 5 4 3 6 5 3 4 3 3 0 1 1 1 4 2 7 2 TABELA FINAL Z x1 x2 x3 x4 x5 x6 RHS Z 1 0 0 0 2 1 1 13 x1 0 1 0 0 3 2 2 2 x2 0 0 1 0 3 2 3 2 x3 0 0 0 1 1 1 1 1 1 4 2 2 1 0 1 1 1 3 2 3 2 2 3 a B a tab Inicial 7 1 tab Final 7 TABELA ATUALIZADA Z x1 x2 x3 x4 x5 x6 x7 RHS Z 1 1 2 7 0 0 0 4 13 x1 0 1 0 0 3 2 2 2 2 x2 0 0 1 0 3 2 3 4 2 x3 0 0 0 1 1 1 1 1 1 0 7 3 2 1 7 3 2 1 4x 7x 2x x Z 4x 7x 2x x Z ção objetivo fica A nova fun 0 Z x1 x2 x3 x4 x5 x6 x7 RHS Z 1 1 2 7 0 0 0 4 13 x1 0 1 0 0 3 2 2 2 2 x2 0 0 1 0 3 2 3 4 2 x3 0 0 0 1 1 1 1 1 1 Z x1 x2 x3 x4 x5 x6 x7 RHS Z 1 0 2 7 3 2 2 2 13 x1 0 1 0 0 3 2 2 2 2 x2 0 0 1 0 3 2 3 4 2 x3 0 0 0 1 1 1 1 1 1 Z x1 x2 x3 x4 x5 x6 x7 RHS Z 1 0 0 7 9 6 8 6 13 x1 0 1 0 0 3 2 2 2 2 x2 0 0 1 0 3 2 3 4 2 x3 0 0 0 1 1 1 1 1 1 Z x1 x2 x3 x4 x5 x6 x7 RHS Z 1 0 0 0 2 1 1 1 13 x1 0 1 0 0 3 2 2 2 2 x2 0 0 1 0 3 2 3 4 2 x3 0 0 0 1 1 1 1 1 1 0 2 6 13 max aplicando o método simplex temos Agora Z x1 x2 x3 x4 x5 x6 x7 RHS Z 1 0 0 0 2 1 1 1 13 x1 0 1 0 0 3 2 2 2 2 x2 0 0 1 0 3 2 3 4 2 x3 0 0 0 1 1 1 1 1 1 NOVA TABELA FINAL Z x1 x2 x3 x4 x5 x6 x7 RHS Z 1 0 14 0 114 12 74 0 272 x1 0 1 12 0 32 1 12 0 1 x7 0 0 14 0 34 12 34 1 12 x3 0 0 14 1 14 12 14 0 32 es nos valores de x e x e alteraçõ o na função objetivo um aument l x para zero da nova variável x determinou a reduçã o da variáve A inclusão 1 2 7 3 max IX Modificações nos coeficientes aij Deve se resolver como um problema novo
Envie sua pergunta para a IA e receba a resposta na hora
Texto de pré-visualização
Análise de Pós Otimização ou de Sensibilidade Algébrica Nos modelos de programação linear muitas vezes não se conhecem com exatidão os coeficientes C j a ij e b i Diante disso são nestes casos necessários ajustes no modelo originalmente adotado Esses ajustes podem indicar modificações em determinados coeficientes iniciais adição de novas variáveis ou restrições ou ainda supressão de determinadas variáveis ou restrições Assim é importante saber que alterações seriam provocadas ou não na solução ótima já obtida Observe que com esta modificação o problema permanece factível pois as restrições não são alteradas I Mudanças nos coeficientes de custos Cj quando Cj é de xj nãobásica na tabela final p j Variabilidade líquida entre o Custo Reduzido da tabela inicial e o Custo Reduzido da tabela final jtabela inicial tabela final j j CR CR p Custo Reduzido da variável x onde j CRj Custo Reduzido Modificado da variável x onde j j CRM jtabela inicial tabela final j j CRM CRM p Variabilidade líquida Uma indústria produz dois tipos de porcas para parafusos alfa e beta que usam duas máquinas para serem fabricadas um torno e uma furadeira ambos mecânicos conforme os tempos de produção apresentados na tabela Tempo para fabricar um quilo de porcas tipo Alfa em horasKg Tempo para fabricar um quilo de porcas tipo Beta em horasKg Disponibilidade máxima diária das máquinas em horas hdia Torno 1hKg 0hKg 3hdia Furadeira 2hKg 3hKg 24hdia Lucro por quilo Rkg 1RKg 3RKg Determine quantos quilosdia de porcas dos tipos Alfa e Beta devem ser produzidos de forma a maximizar o lucro diário da indústria Exemplo 1 0 x x 24 3x 2x 3 x sa 3x Z x max primal 1 Seja o 2 1 2 1 1 2 1 0 x x 24 3x 2x 3 x sa 3x x max Z primal 1 Seja o 2 1 2 1 1 2 1 QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 1 0 0 1 24 x3 0 1 0 1 0 3 x2 0 23 1 0 13 8 24 3 8 2 0 3 com o mesmo valor Z permanece 0 entãoo valor da nova função objetivo básica e portanto x é não na otimização x Como 8 0 a solução ótima continua a mesma ou seja X então não básica x não entra na base problema é de máximo a variável o e 2 1 o CRM Como 2 1 CRM 2 3 CRM 2 CRM CRM p 0 2 x 3x 3 constante e na tabela a nova função objetivo fica Z 2 permanece p Como x na nova tabela final será o novo CRM da variável Qual 2 1 1 CR CR p 0 1 tabela inicial Z do problema original ficaria Na max 1 1 1 tabela final 1 1tabela final 1tabela final 1tabela inicial tabela final 1 1 2 1 1 1 1tabela inicial tabela final 1 1 2 1 3x x Z 2 1 x 3x Suponha que haja mudança da função objetivo para max Z 2 3 Tabela Inicial Z x1 x2 x3 x4 RHS Z 1 1 3 0 0 0 x3 0 1 0 1 0 3 x4 0 2 3 0 1 24 Uma indústria produz dois tipos de porcas para parafusos alfa e beta que usam duas máquinas para serem fabricadas um torno e uma furadeira ambos mecânicos conforme os tempos de produção apresentados na tabela Tempo para fabricar um quilo de porcas tipo Alfa em horasKg Tempo para fabricar um quilo de porcas tipo Beta em horasKg Disponibilidade máxima diária das máquinas em horas hdia Torno 1hKg 0hKg 3hdia Furadeira 2hKg 3hKg 24hdia Lucro por quilo Rkg 1RKg 3RKg Determine quantos quilosdia de porcas dos tipos Alfa e Beta devem ser produzidos de forma a maximizar o lucro diário da indústria Exemplo 2 0 x x 24 3x 2x 3 x sa 3x Z x max rimal Seja o p 2 1 2 1 1 2 1 2 0 x x 24 3x 2x 3 x sa 3x Z x max rimal Seja o p 2 1 2 1 1 2 1 2 QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 1 0 0 1 24 x3 0 1 0 1 0 3 x2 0 23 1 0 13 8 2 1 3x Suponha que haja mudança da função objetivo para max Z 3x novo valor de Z o e será a nova solução ótima Qual nova tabela final da solução ótima não continua a mesma então devemos dar continuidade ao método simplex a partir a e não básica x entra na base problema é de máximo a variável o 1 o CRM Como 1 CRM 3 CRM 2 CRM CRM p 0 constante e na tabela a nova função objetivo fica Z 3x 3x 2 permanece p Como x na nova tabela final será o novo CRM da variável Qual 2 1 1 CR CR p 0 1 tabela inicial Z do problema original ficaria Na max 1 tabela final 1 1tabela final 1tabela final 1tabela inicial tabela final 1 1 2 1 1 1 1tabela inicial tabela final 1 1 2 1 3x x Z Continua 1 Tabela Inicial Z x1 x2 x3 x4 RHS Z 1 1 3 0 0 0 x3 0 1 0 1 0 3 x4 0 2 3 0 1 24 0 x x 24 3x 2x 3 x sa 3x Z x max rimal Seja o p 2 1 2 1 1 2 1 2 QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 1 0 0 1 24 x3 0 1 0 1 0 3 x2 0 23 1 0 13 8 Novo QUADRO para max z3x 1 3x2 Z x1 x2 x3 x4 RHS Z 1 1 0 0 1 24 x3 0 1 0 1 0 3 x2 0 23 1 0 13 8 Novo QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 0 0 1 1 27 x1 0 1 0 1 0 3 x2 0 0 1 23 13 6 27 36 33 3 e Z X max 6 1 CRM 1tabela final Continuação Observe que com esta modificação o problema permanece factível pois as restrições não são alteradas II Mudanças simples nos coeficientes de custos Cj mudança em Cj quando xj é básica na tabela final Uma indústria produz dois tipos de porcas para parafusos alfa e beta que usam duas máquinas para serem fabricadas um torno e uma furadeira ambos mecânicos conforme os tempos de produção apresentados na tabela Tempo para fabricar um quilo de porcas tipo Alfa em horasKg Tempo para fabricar um quilo de porcas tipo Beta em horasKg Disponibilidade máxima diária das máquinas em horas hdia Torno 1hKg 0hKg 3hdia Furadeira 2hKg 3hKg 24hdia Lucro por quilo Rkg 1RKg 3RKg Determine quantos quilosdia de porcas dos tipos Alfa e Beta devem ser produzidos de forma a maximizar o lucro diário da indústria Exemplo 3 0 x x 24 3x 2x 3 x sa 3x Z x max rimal Seja o p 2 1 2 1 1 2 1 3 0 x x 24 3x 2x 3 x sa 3x Z x max Seja o primal Ex 2 1 2 1 1 2 1 3 QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 1 0 0 1 24 x3 0 1 0 1 0 3 x2 0 23 1 0 13 8 QUADRO ATUALIZADO Z x1 x2 x3 x4 RHS Z 1 1 2 0 1 24 x3 0 1 0 1 0 3 x2 0 23 1 0 13 8 QUADRO ATUALIZADO Z x1 x2 x3 x4 RHS Z 1 13 0 0 13 8 x3 0 1 0 1 0 3 x2 0 23 1 0 13 8 2 1 x Suponha que haja mudança da função objetivo para max Z x 1 2 CRM 1 CRM 3 CRM CRM p 0 então constantee Z x 1 x 3 permanece p Como novo valor de Z o e a nova solução ótima será x na nova tabela final e qual será o novo CRM da variável Qual 3 3 0 CR CR p 0 tabela inicial Z do problema original ficaria Na 2tabela final 2tabela final 2tabela inicial tabela final 2 2 2 1 2 max 2 2tabela inicial tabela final 2 2 2 1 3 x x Z Continua Tabela Inicial Z x1 x2 x3 x4 RHS Z 1 1 3 0 0 0 x3 0 1 0 1 0 3 x4 0 2 3 0 1 24 QUADRO ATUALIZADO Z x1 x2 x3 x4 RHS Z 1 13 0 0 13 8 x3 0 1 0 1 0 3 x2 0 23 1 0 13 8 NOVO QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 0 0 13 13 9 x1 0 1 0 1 0 3 x2 0 0 1 23 13 6 9 3 e Z X max 6 Continuação III Mudanças nos termos RHS bi 18 1 e b para b de b lise de pós otimização supondo que haja mudança nas componentes Faça a aná 2 1 i QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 0 0 13 13 9 x1 0 1 0 1 0 3 x2 0 0 1 23 13 6 0 x x 24 3x 2x 3 x sa x Z x max 1 Seja o primal EX 2 1 2 1 1 2 1 Tempo para fabricar um quilo de porcas tipo Alfa em horasKg Tempo para fabricar um quilo de porcas tipo Beta em horasKg Disponibilidade máxima diária das máquinas em horas hdia Torno 1hKg 0hKg 3hdia Furadeira 2hKg 3hKg 24hdia Lucro por quilo Rkg 1RKg 1RKg Tabela Inicial Z x1 x2 x3 x4 RHS Z 1 1 1 0 0 0 x3 0 1 0 1 0 3 x4 0 2 3 0 1 24 6 3 24 3 1 0 1 0 1 0 1 1 0 3 0 0 B 1 2 1 das restrições e dos termos independentes da tabela inicial ndose B pelas colunas dos coefientes multiplica das restrições e dos termos independentes da tabela final poderão ser obtidas Desta forma as colunas dos coefientes 4 3 1 3 2 0 1 e a matriz B e variáveis de folga são As às variáveis de folga no exemplo A inversa B será formada pelas colunas da tabela final referentes 3 3 2 0 1 B às variáveis básicas do item 1 no exemplo Construa a matriz da base B com as colunas da tabela inicial referentes 2 e Identifiqu e as variáveis básicas na tabela final no exemplo 1 os seguintes passos Siga 4 3 2 1 1 1 4 3 1 2 1 3 1 3 2 0 1 b B 3 3 1 3 2 0 1 a B 3 2 3 1 3 2 0 1 B a 3 1 3 2 0 1 a 3 1 3 2 0 1 a B x x x x 1 1 1 1 1 Propriedades QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 0 0 13 13 9 x1 0 1 0 1 0 3 x2 0 0 1 23 13 6 Tabela Inicial Z x1 x2 x3 x4 RHS Z 1 1 1 0 0 0 x3 0 1 0 1 0 3 x4 0 2 3 0 1 24 6 33 max 3 19 Z 3 16 1 e x x básicas porém com os valores variáveis va solução ótima contém as mesmas Logo a no 3 16 1 18 1 3 1 3 2 0 1 b B s Então temo 18 1 e b b tal que os novos valores sejam de b e haja mudança nas componentes Suponha qu 2 1 1 2 1 i B Resolução QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 0 0 13 13 9 x1 0 1 0 1 0 3 x2 0 0 1 23 13 6 0 x x x x 24 1x 3x 2x 3 1x x sa 0 0x 0x x x Z max 2 1 4 2 1 3 1 4 3 2 1 4 3 Tabela Inicial Z x1 x2 x3 x4 RHS Z 1 1 1 0 0 0 x3 0 1 0 1 0 3 x4 0 2 3 0 1 24 se ade e aplicando o dual simplex obtém lução viol a factibilid Logo a so 3 1 3 2 3 1 3 2 0 1 b B 3 2 e b b e haja mudança nas componentesde b tal que os novos valores sejam Suponha qu 1 2 1 i 2 NOVO QUADRO Z x1 x2 x3 x4 RHS Z 1 0 0 13 13 53 x1 0 1 0 1 0 2 x2 0 0 1 23 13 13 QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 0 0 13 13 9 x1 0 1 0 1 0 3 x2 0 0 1 23 13 6 53 13 2 z 0 x x 24 3x 2x 3 x sa x Z x max Seja o primal EX 2 1 2 1 1 2 1 2 Tabela Inicial Z x1 x2 x3 x4 RHS Z 1 1 1 0 0 0 x3 0 1 0 1 0 3 x4 0 2 3 0 1 24 2 3 0 2 3 max Z e x x va solução ótima será Logo a no 2 1 Tempo para fabricar um quilo de porcas tipo Alfa em horasKg Tempo para fabricar um quilo de porcas tipo Beta em horasKg Disponibilidade máxima diária das máquinas em horas hdia Torno 1hKg 0hKg 3hdia Furadeira 2hKg 3hKg 24hdia Lucro por quilo Rkg 1RKg 1RKg Problema Original Z x1 x2 x3 x4 x5 RHS Z 1 0 19 0 3 1 150 x1 0 1 1 0 1 2 20 x3 0 0 3 1 1 1 10 10 20 30 40 1 1 2 1 1 2 1 0 1 1 2 1 1 1 0 1 1 1 2 1 1 0 1 2 1 1 2 1 3 1 2 5 1 1 2 1 0 1 1 1 1 1 2 1 1 1 2 1 1 1 2 1 4 4 3 2 1 B b B a a B B a a a B 1 1 1 1 1 1 B B B 1 Max Z 4x1 2x2 7x3 sa 1 x1 5x2 2 x3 x4 40 1 x1 2x2 1 x3 x5 30 0 x x x 2x x 30 x sa x 5x 2x 40 2x 7x 4x Max Z Seja o primal 4 EX 3 2 1 3 2 1 3 2 1 3 2 1 OBS Exemplo com mais variáveis que restrições IV Acréscimo de nova restrição Observe que como a inclusão de nova restrição pode provocar uma redução na região viável então a função objetivo deve sofrer uma piora ou na melhor das hipóteses não sofre alteração O procedimento é verificar se atual solução satisfaz a nova restrição Se satisfaz então a solução ótima continua sendo a mesma Se não satisfaz então devese acrescentar no quadro ótimo uma linha devida à nova restrição e prosseguir com o método simplex ou com o dualsimplex QUADRO FINAL Z x1 x2 x3 x4 RHS Z 1 1 0 0 1 24 x3 0 1 0 1 0 3 x2 0 23 1 0 13 8 inserida conjuntamente a variável de folga x seja mos introduzir uma linha no quadro ótimo cuidando para que Então deve 30 48 6 8 0 08 X ução ótima não satisfaz a nova restrição Como a sol 30 6x x o galvanização e seja acrescentada a restriçã Suponha qu 5 2 1 NOVO QUADRO Z x1 x2 x3 x4 x5 RHS Z 1 1 0 0 1 0 24 x3 0 1 0 1 0 0 3 x2 0 23 1 0 13 0 8 x5 0 1 6 0 0 1 30 QUADRO ATUALIZADO Z x1 x2 x3 x4 x5 RHS Z 1 1 0 0 1 0 24 x3 0 1 0 1 0 0 3 x2 0 23 1 0 13 0 8 x5 0 3 0 0 2 1 18 24 8 0 min e Z X Transformar o 6 em zero pois x2 está na base Não altera pois x5 é de folga 0 x x 24 3x 2x 3 x sa 3x Z x max Seja o primal EX 2 1 2 1 1 2 1 Tabela Inicial Z x1 x2 x3 x4 RHS Z 1 1 3 0 0 0 x3 0 1 0 1 0 3 x4 0 2 3 0 1 24 05 2 1 033 entra a var da maior resultado 3 1 de Max é Algoritmo Dual quando o primal QUADRO ATUALIZADO Z x1 x2 x3 x4 x5 RHS Z 1 1 0 0 1 0 24 x3 0 1 0 1 0 0 3 x2 0 23 1 0 13 0 8 x5 0 3 0 0 2 1 18 2 33 9 2 3 max Z e x x va solução ótima será Logo a no 2 1 QUADRO ATUALIZADO Z x1 x2 x3 x4 x5 RHS Z 1 0 0 0 13 13 18 x3 0 0 0 1 23 13 3 x2 0 0 1 0 19 29 4 x1 0 1 0 0 23 13 6 QUADRO ATUALIZADO Z x1 x2 x3 x4 x5 RHS Z 1 0 0 12 0 12 332 x4 0 0 0 32 1 12 92 x2 0 0 1 16 0 16 92 x1 0 1 0 1 0 0 3 V Eliminação de uma restrição de desigualdade ário devese considerar um novo problema Caso contr a mesma após sua retirada permanece o original não é ativa e portanto a solução a restriçã for básica na otimalidade temse que de folga var Então se x 0 seja retirada x 6x x 0 6x x e em um problema a restrição Suponha qu 5 5 2 1 2 1 VI Eliminação de uma restrição de igualdade problema sem a restrição se recomeçar o Neste caso sugere VII Eliminação de uma variável xj simplex ou dualsimplex do método e prosseguir o processo com o uso do quadro a não básica em seguida retirála a tornál rma o pivotamento de fo se forçar então deve ável eliminada for básica na otimalidade Se a vari lução permanece a mesma pois x então a so vel eliminada não é básica na otimalidade Se a variá j 0 VIII Inclusão de uma variável xj do objetivo e nas demais restrições é acrescenta na função es com componentes coeficient os todo um vetor de Nestes cas 0 x x x x x x x x x x 5 3x x x x x sa x x Z x max EX 2 1 2 1 2 1 2 1 6 5 4 3 6 5 3 4 3 3 0 4 2 7 2 0 x x x x x x x x x x 5 3x x x x 1 x sa x x Z x max 2 1 2 1 2 1 2 1 6 5 4 3 6 5 3 4 3 3 0 1 1 1 4 2 7 2 TABELA FINAL Z x1 x2 x3 x4 x5 x6 RHS Z 1 0 0 0 2 1 1 13 x1 0 1 0 0 3 2 2 2 x2 0 0 1 0 3 2 3 2 x3 0 0 0 1 1 1 1 1 1 1 1 3 2 3 2 2 3 B 0 1 1 3 1 0 2 0 1 B 2 1 0 a a a a 4 e o vetor a nas restrições igual a e na função objetivo c coeficient l x com introdução de uma nova variáve Suponha a 1 37 27 17 7 7 7 7 0 x x x x x x x x x x 5 3x x x x 1 x sa x x Z x max 2 1 2 1 2 1 2 1 6 5 4 3 6 5 3 4 3 3 0 1 1 1 4 2 7 2 TABELA FINAL Z x1 x2 x3 x4 x5 x6 RHS Z 1 0 0 0 2 1 1 13 x1 0 1 0 0 3 2 2 2 x2 0 0 1 0 3 2 3 2 x3 0 0 0 1 1 1 1 1 1 4 2 2 1 0 1 1 1 3 2 3 2 2 3 a B a tab Inicial 7 1 tab Final 7 TABELA ATUALIZADA Z x1 x2 x3 x4 x5 x6 x7 RHS Z 1 1 2 7 0 0 0 4 13 x1 0 1 0 0 3 2 2 2 2 x2 0 0 1 0 3 2 3 4 2 x3 0 0 0 1 1 1 1 1 1 0 7 3 2 1 7 3 2 1 4x 7x 2x x Z 4x 7x 2x x Z ção objetivo fica A nova fun 0 Z x1 x2 x3 x4 x5 x6 x7 RHS Z 1 1 2 7 0 0 0 4 13 x1 0 1 0 0 3 2 2 2 2 x2 0 0 1 0 3 2 3 4 2 x3 0 0 0 1 1 1 1 1 1 Z x1 x2 x3 x4 x5 x6 x7 RHS Z 1 0 2 7 3 2 2 2 13 x1 0 1 0 0 3 2 2 2 2 x2 0 0 1 0 3 2 3 4 2 x3 0 0 0 1 1 1 1 1 1 Z x1 x2 x3 x4 x5 x6 x7 RHS Z 1 0 0 7 9 6 8 6 13 x1 0 1 0 0 3 2 2 2 2 x2 0 0 1 0 3 2 3 4 2 x3 0 0 0 1 1 1 1 1 1 Z x1 x2 x3 x4 x5 x6 x7 RHS Z 1 0 0 0 2 1 1 1 13 x1 0 1 0 0 3 2 2 2 2 x2 0 0 1 0 3 2 3 4 2 x3 0 0 0 1 1 1 1 1 1 0 2 6 13 max aplicando o método simplex temos Agora Z x1 x2 x3 x4 x5 x6 x7 RHS Z 1 0 0 0 2 1 1 1 13 x1 0 1 0 0 3 2 2 2 2 x2 0 0 1 0 3 2 3 4 2 x3 0 0 0 1 1 1 1 1 1 NOVA TABELA FINAL Z x1 x2 x3 x4 x5 x6 x7 RHS Z 1 0 14 0 114 12 74 0 272 x1 0 1 12 0 32 1 12 0 1 x7 0 0 14 0 34 12 34 1 12 x3 0 0 14 1 14 12 14 0 32 es nos valores de x e x e alteraçõ o na função objetivo um aument l x para zero da nova variável x determinou a reduçã o da variáve A inclusão 1 2 7 3 max IX Modificações nos coeficientes aij Deve se resolver como um problema novo