Baixe o app para aproveitar ainda mais
Prévia do material em texto
Reinaldo F. Santos 11 Pesquisa Operacional Pesquisa Operacional CURSO SUPERIOR DE TECNOLOGIA EM LOGÍSTICA E TRANSPORTE Professor: REINALDO FAGUNDES DOS SANTOS Reinaldo F. Santos 22 Pesquisa Operacional Semana Assunto 01 Apresentação da Disciplina e Introdução à Pesquisa Operacional; 02 Modelagem de Problemas de Otimização; 03 Modelagem de Problemas de Otimização (continuação) 04 Programação Linear; 05 Solução Gráfica; 06 Método Simplex; 07 Método Simplex (continuação); 08 A ferramenta Solver (laboratório); 09 Prova 1; 10 Correção e Comentários da Prova 1; 11 O problema de Transporte; 12 O problema de Transporte (continuação); 13 Simulação ( O método Monte Carlo); 14 Fundamentos da teoria das Restrições e solução de um problema; 15 Apresentação dos Trabalhos em Grupo; 16 Apresentação dos Trabalhos em Grupo; 17 Prova 2; 18 Correção e comentários da Prova 2; Prova ou Trabalho Substitutivo. Reinaldo F. Santos 33 Pesquisa Operacional MÉTODO SIMPLEX O modelo de programação linear pode ser resolvido por um método de solução de sistema de equações lineares. O processo que será apresentado no exemplo a seguir, retirado de ANDRADE (2000), é bastante intuitivo e tem por finalidade apresentar a metodologia utilizada pelo método Simplex. Reinaldo F. Santos 44 Pesquisa Operacional "Uma marcenaria deseja estabelecer uma programação diária de produção. Atualmente, a oficina faz apenas dois produtos: mesa e armário, ambos de um só modelo. (Para efeito de simplificação) Reinaldo F. Santos 55 Pesquisa Operacional A marcenaria tem limitações em somente dois recursos: madeira e mão-de-obra As disponibilidades diárias são mostradas na tabela a seguir. Recurso Disponibilidade Madeira 12m2 Mão-de-obra 8 H.h Reinaldo F. Santos 66 Pesquisa Operacional •O processo de produção é tal que, para fazer uma mesa a fábrica gasta 2 m2 de madeira e 2 H.h de mão-de-obra. •Para fazer um armário, a fábrica gasta 3 m2 de madeira e 1 H.h de mão de obra. •Além disso, o fabricante sabe que cada mesa dá uma margem de contribuição para o lucro de $ 4 e cada armário de $ 1. Reinaldo F. Santos 77 Pesquisa Operacional Fases do Estudo de Pesquisa Operacional (1) definição do problema; (2) construção do modelo; (3) solução do modelo; (4) validação do modelo; (5) implementação da solução. Reinaldo F. Santos 88 Pesquisa Operacional •Qual o programa de produção que maximiza a margem de contribuição total para o lucro." Reinaldo F. Santos 99 Pesquisa Operacional Fases do Estudo de Pesquisa Operacional (1) definição do problema; (2) construção do modelo; (3) solução do modelo; (4) validação do modelo; (5) implementação da solução. Reinaldo F. Santos 1010 Pesquisa Operacional A função objetivo é: Lucro: z = 4 M + A As variáveis de decisão envolvidas no problema são: M: quantidade a produzir de mesas A: quantidade a produzir de armários Para as restrições: Madeira: 2 M + 3 A <= 12 Mão-de-obra: 2 M + A <= 8 M, A >= 0 Reinaldo F. Santos 1111 Pesquisa Operacional Introduzindo as variáveis de folga, o problema a ser resolvido passa a ser: Maximizar: z = 4 M + A Sujeito a: 2 M + 3 A + s1 = 12 2 M + A + s2 = 8 M, A, s1, s2 >= 0 Reinaldo F. Santos 1212 Pesquisa Operacional O problema se transformou em encontrar a solução do sistema de equações lineares que maximiza o lucro. Como neste caso o número de variáveis (m = 4) é superior ao número de equações (n = 2), o sistema é indeterminado, apresentando infinitas soluções. No entanto, todas as variáveis devem ser maiores ou iguais a zero. Atribuir zero a uma variável significa não produzir um dos produtos (se a variável for M ou A) ou utilizar toda a disponibilidade de recursos (se a variável for f1 ou f2). Reinaldo F. Santos 1313 Pesquisa Operacional Desta forma, podemos encontrar soluções para o sistema de equações zerando duas variáveis (n - m = 2) e encontrando o valor para as duas variáveis restantes. Teremos que resolver então sistemas de equações lineares. Reinaldo F. Santos 1414 Pesquisa Operacional c.1) Variáveis não-básicas: M = 0 ; A = 0 temos as variáveis básicas f1 = 12 ; f2 = 8 dando o lucro z = 0 c.2) Variáveis não-básicas: M = 0 ; f1 = 0 temos as variáveis básicas A = 4 ; f2 = 4 dando o lucro z = 4 c.3) Variáveis não-básicas: M = 0 ; f2 = 0 temos as variáveis básicas A = 8 ; f1 = -12 como f1 < 0, a solução obtida é INVIÁVEL. Reinaldo F. Santos 1515 Pesquisa Operacional c.4) Variáveis não-básicas: A = 0 ; f1 = 0 temos as variáveis básicas M = 6 ; f2 = -4 como f2 < 0, a solução obtida é INVIÁVEL. c.5) Variáveis não-básicas: A = 0 ; f2 = 0 temos as variáveis básicas M = 4 ; f1 = 4 dando o lucro z = 16 c.6) Variáveis não-básicas: f1 = 0 ; f2 = 0 temos as variáveis básicas M = 3 ; A = 2 dando o lucro z = 14 Reinaldo F. Santos 1616 Pesquisa Operacional Procedimento do Método Simplex (Problemas de Maximização) •Passo 1: Monta-se o tableau que corresponde à origem; •Passo 2: O primeiro tableau é transformado em um segundo, que apresenta uma solução melhorada, por meio de uma série de cálculos; •Passo 3: Quando da criação de cada tableau, existe um teste para verificar se a solução ótima foi ou não atingida; •Passo 4: Esse procedimento se repete até que se chegue a um tableau que reflita a solução ótima; Reinaldo F. Santos 1717 Pesquisa Operacional Introduzindo as variáveis de folga, o problema a ser resolvido passa a ser: Maximizar: z = X + 2Y Sujeito a: 3X + 4Y <=24 5X + 2Y <= 20 X,Y >= 0 Reinaldo F. Santos 1818 Pesquisa Operacional Introduzindo as variáveis de folga, o problema a ser resolvido passa a ser: Maximizar: z = X + 2Y Sujeito a: 3X + 4Y + 1S1=24 5X + 2Y + 1S2= 20 X,Y ,S1,S2>= 0 Reinaldo F. Santos 1919 Pesquisa Operacional Introduzindo as variáveis de folga, o problema a ser resolvido passa a ser: Maximizar: z = X + 2Y + 0S1 + 0S2 Sujeito a: 3X + 4Y + 1S1 + 0S2=24 5X + 2Y + 0S1 + 1S2= 20 X,Y ,S1,S2>= 0 Reinaldo F. Santos 2020 Pesquisa Operacional Variáveis de Decisão 1 2 0 0 Objetivo Cj Variáveis na Solução X Y S1 S2 bj bj/aij 0 S1 3 4 1 0 24 0 S2 5 2 0 1 20 Linha Z Linha C-Z Primeiro Tableau Reinaldo F. Santos 2121 Pesquisa Operacional Variáveis de Decisão 1 2 0 0 Objetivo Cj Variáveis na Solução X Y S1 S2 bj bj/aij 0 S1 3(0) 4(0) 1(0) 0(0) 24(0) 0 S2 5(0) 2(0) 0(0) 1(0) 20(0) Linha Z 0 0 0 0 0 Linha C-Z Primeiro Tableau multiplicado por X, Y, Cj multiplicado por X, Y, S1 e S2 (que são zero) Linha Z Reinaldo F. Santos 2222 Pesquisa Operacional Variáveis de Decisão 1 2 0 0 Objetivo Cj Variáveis na Solução X Y S1 S2 bj bj/aij 0 S1 3 4 1 0 24 0 S2 5 2 0 1 20 Linha Z 0 0 0 0 Linha C-Z 1 2 0 0 Primeiro Tableau Linha de Objetivo Subtraído da Linha Z Linha C-Z Reinaldo F. Santos 2323 Pesquisa Operacional Variáveis de Decisão 1 2 0 0 Objetivo Cj Variáveis na Solução X Y S1 S2 bj bj/aij 0 S1 3 4 1 0 24 0 S2 5 2 0 1 20 Linha Z 0 0 0 0 Linha C-Z 1 2 0 0 Primeiro Tableau Reinaldo F. Santos 2424 Pesquisa Operacional Qual a Variável que entra noTableau? Reinaldo F. Santos 2525 Pesquisa Operacional Variáveis de Decisão 1 2 0 0 Objetivo Cj Variáveis na Solução X Y S1 S2 bj bj/aij 0 S1 3 4 1 0 24 0 S2 5 2 0 1 20 Linha Z 0 0 0 0Linha C-Z 1 2 0 0 Primeiro Tableau Variável Y é a que oferece Variável Y é a que oferece maior Margem Reinaldo F. Santos 2626 Pesquisa Operacional Qual a Variável que sai do Tableau? Reinaldo F. Santos 2727 Pesquisa Operacional Variáveis de Decisão 1 2 0 0 Objetivo Cj Variáveis na Solução X Y S1 S2 bj bj/aij 0 S1 3 4 1 0 24 24/4 0 S2 5 2 0 1 20 20/2 Linha Z 0 0 0 0 Linha C-Z 1 2 0 0 Primeiro Tableau Dividir bj pelo coeficiente Dividir bj pelo coeficiente da variável que sairá. Reinaldo F. Santos 2828 Pesquisa Operacional Variáveis de Decisão 1 2 0 0 Objetivo Cj Variáveis na Solução X Y S1 S2 bj bj/aij 0 S1 3 4 1 0 24 6 0 S2 5 2 0 1 20 10 Linha Z 0 0 0 0 Linha C-Z 1 2 0 0 Primeiro Tableau S1 oferece o menor valor, S1 oferece o menor valor, portanto deve sair Reinaldo F. Santos 2929 Pesquisa Operacional Variáveis de Decisão 1 2 0 0 Objetivo Cj Variáveis na Solução X Y S1 S2 bj bj/aij 0 S1 3 4 1 0 24 0 S2 5 2 0 1 20 Linha Z 0 0 0 0 Linha C-Z 1 2 0 0 Primeiro Tableau PivôPivô Reinaldo F. Santos 3030 Pesquisa Operacional Determinar a nova linha principal Reinaldo F. Santos 3131 Pesquisa Operacional Variável X Y S1 S2 bj Antiga Linha Principal 3 4 1 0 24 dividida pelo pivô 3/4 4/4 1/4 0/4 24/4 Nova linha principal 3/4 1 1/4 0 6 Reinaldo F. Santos 3232 Pesquisa Operacional Determinar a nova linha da variável S2 Reinaldo F. Santos 3333 Pesquisa Operacional Variáveis de Decisão 1 2 0 0 Objetivo Cj Variáveis na Solução X Y S1 S2 bj bj/aij 0 S1 3 4 1 0 24 0 S2 5 2 0 1 20 Linha Z 0 0 0 0 Linha C-Z 1 2 0 0 Primeiro Tableau IntersecçãoIntersecção Reinaldo F. Santos 3434 Pesquisa Operacional Variável X Y S1 S2 bj Nova Linha Principal 3/4 1 1/4 0 6 dividida pela intersecção de Y com S2 (2) 3/4 (2) 1 (2) 1/4 (2) 0 (2) 6 (2) Resultante 3/2 2 1/2 0 12 Reinaldo F. Santos 3535 Pesquisa Operacional Variável X Y S1 S2 bj Antiga Linha de S2 5 2 0 1 20 (Menos resultante) 3/2 2 1/2 0 12 Nova linha de S2 7/2 0 -1/2 1 8 Reinaldo F. Santos 3636 Pesquisa Operacional Segundo Tableau Incompleto Reinaldo F. Santos 3737 Pesquisa Operacional Variáveis de Decisão 1 2 0 0 Objetivo Cj Variáveis na Solução X Y S1 S2 bj bj/aij 2 Y 3/4 1 1/4 0 6 0 S2 7/2 0 -1/2 1 8 Linha Z Linha C-Z Primeiro Tableau Reinaldo F. Santos 3838 Pesquisa Operacional Calcular linha Z e linha C-Z do Segundo Tableau Reinaldo F. Santos 3939 Pesquisa Operacional Variáveis de Decisão 1 2 0 0 Objetivo Cj Variáveis na Solução X Y S1 S2 bj bj/aij 2 Y 3/4 (2) 1(2) 1/4 (2) 0 (2) 6 (2) 0 S2 7/2 (0) 0 (0) -1/2 (0) 1 (0) 8 (0) Linha Z 3/2 2 1/2 0 12 Linha C-Z Primeiro Tableau multiplicado por X, Y, Cj multiplicado por X, Y, S1 e S2) (que são 2 e 0) Linha Z Reinaldo F. Santos 4040 Pesquisa Operacional Variáveis de Decisão 1 2 0 0 Objetivo Cj Variáveis na Solução X Y S1 S2 bj bj/aij 2 Y 3/4 (2) 1(2) 1/4 (2) 0 (2) 6 (2) 0 S2 7/2 (0) 0 (0) -1/2 (0) 1 (0) 8 (0) Linha Z 3/2 2 1/2 0 12 Linha C-Z -1/2 0 -1/2 0 Primeiro Tableau Linha de Objetivo Subtraído da Linha Z Linha C-Z Reinaldo F. Santos 4141 Pesquisa Operacional O Segundo Tableau completo Reinaldo F. Santos 4242 Pesquisa Operacional Variáveis de Decisão 1 2 0 0 Objetivo Cj Variáveis na Solução X Y S1 S2 bj bj/aij 2 Y 3/4 1 1/4 0 6 0 S2 7/2 0 -1/2 1 8 Linha Z 3/2 2 1/2 0 12 Linha C-Z -1/2 0 -1/2 0 Primeiro Tableau Reinaldo F. Santos 4343 Pesquisa Operacional Verificamos que na linha C-Z todos os valores são negativos ou iguais a zero portanto chegamos na solução ótima. Reinaldo F. Santos 4444 Pesquisa Operacional Variáveis de Decisão 1 2 0 0 Objetivo Cj Variáveis na Solução X Y S1 S2 bj bj/aij 2 Y 3/4 1 1/4 0 6 0 S2 7/2 0 -1/2 1 8 Linha Z 3/2 2 1/2 0 12 Linha C-Z -1/2 0 -1/2 0 Primeiro Tableau Portanto a solução ótima é Y=6 e X=0 (X está fora do Portanto a solução ótima é Y=6 e X=0 (X está fora do Tableau) Reinaldo F. Santos 4545 Pesquisa Operacional Observamos que: z = X + 2Y = 0 + 2(6) = 12 Sujeito a: 3X + 4Y <=24 [3(0) + 4(6) <=24] 5X + 2Y <= 20 [5(0) + 2(6) <=20] X,Y >= 0 Reinaldo F. Santos 4646 Pesquisa Operacional Observamos que Z=
Compartilhar