·
Sistemas de Informação ·
Outros
Send your question to AI and receive an answer instantly
Preview text
28042022 1 1 ADM 043 Pesquisa Operacional UNIFEI Universidade Federal de Itajubá Prof Dr Alexandre Ferreira de Pinho 2 Solução de Problemas de PL Método Gráfico 1 2 28042022 2 Conceito 3 Possível para duas variáveis Essa técnica consiste em representar em um sistema de eixos ortogonais as equações das restrições do problema Região de soluções é o conjunto de todos os pontos que satisfazem todas as restrições do problema Pontos onde será procurada a solução ótima Método Gráfico 4 MAX Z 3X1 4X2 Sujeito a X1 X2 8 restrição da matériaprima A X1 2 X2 12 restrição da matériaprima B X1 6 restrição da matériaprima C X1 X2 0 Plotar as inequações no gráfico A modelagem apresentada aqui é de um problema de MIX de produção 3 4 28042022 3 Método Gráfico 5 X1 e X2 0 indicam o primeiro quadrante X1 X2 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 X1 6 X1 X2 8 X1 2 X2 12 Região de Soluções MAX Z 3X1 4X2 Sujeito a X1 X2 8 X1 2 X2 12 X1 6 X1 X2 0 Método Gráfico 6 Após a identificação da região de solução devese procurar a solução ótima que será o ponto da região que leva ao maior valor de Z 3 X1 4 X2 Para tal escolhese um valor arbitrário para Z por exemplo 10 12 20 24 30 etc Usando o 12 temse 3 X1 4 X2 12 Dica atribua um valor que seja divisível pelos coeficientes no caso 3 e 4 e que o resultado da divisão deste valor pelos coeficientes esteja dentro da região de soluções 5 6 28042022 4 Método Gráfico 7 Traçar a reta da função objetivo 3 X1 4 X2 12 X1 X2 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 X1 6 X1 X2 8 X1 2 X2 12 3 X1 4 X2 12 Uma vez desenhada a reta podese encontrar a solução ótima pelo movimento paralelo da reta que desenhamos Este movimento é feito até que toda a região de soluções seja considerada Método Gráfico 8 Note que Problemas de MAX paralelas para cima Problemas de MIN paralelas para baixo X1 X2 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 X1 6 X1 X2 8 X1 2 X2 12 Ponto Ótimo X1 4 X2 4 Z 28 7 8 28042022 5 Casos Especiais em PL 9 Sem solução infeasibility X2 X1 20 40 60 80 100 120 20 40 60 80 100 120 C E Casos Especiais em PL 10 Sem fronteira unboundedness X1 X2 20 40 60 80 100 120 20 40 60 80 100 120 C E 9 10 28042022 6 Casos Especiais em PL 11 Múltiplas soluções alternate optimal solutions X2 X1 20 40 60 80 100 120 20 40 60 80 100 120 C E Exercício 12 Uma empresa fabrica 2 produtos P1 e P2 A margem de contribuição unitária do produto P1 é de 1000 e a margem de contribuição unitária de P2 é 1500 A empresa precisa de 20 horas para fabricar uma unidade de P1 e de 40 horas para fabricar uma unidade de P2 O tempo anual de produção disponível para isso é de 1200 horas A demanda esperada para cada produto é de 40 unidades anuais para P1 e 50 unidades anuais para P2 Qual é o modelo matemático e o resultado do plano de produção anual para que a empresa maximize sua margem de contribuição nesses itens 11 12 28042022 7 Exercício Modelagem 13 Passo 1 Definição das variáveis de decisão X1 Quantidade que será produzida de P1 X2 Quantidade que será produzida de P2 Passo 2 Definição da Função Objetivo MAX Margem 1000 X1 1500 X2 MAX Z 1000 X1 1500 X2 Exercício Modelagem 14 Passo 3 Definição das restrições do problema Quantidade de tempo disponível 1200 horas 20 X1 40 X2 1200 Demanda de P1 40 unidades X1 40 Demanda de P2 50 unidades X1 50 Passo 4 Não negatividade X1 0 X2 0 13 14 28042022 8 Exercício Cálculo 15 X1 X2 10 20 30 40 50 60 70 80 90 100 110 120 10 20 30 40 50 60 70 80 90 100 X1 40 20 X1 40 X2 1200 MAX Z 1000 X1 1500 X2 Sujeito a 20 X1 40 X2 1200 X1 40 X2 50 X1 X2 0 X2 50 1000 X1 1500 X2 15000 Solução X1 40 X2 10 Z 55000 16 Solução de Problemas de PL Método Simplex 15 16 28042022 9 Conceito 17 Possível para qualquer quantidade de variáveis Desenvolvido em 1947 por George B Dantzig Método interativo algoritmo utilizado para achar algebricamente a solução ótima de um problema de PL Os softwares de PL são baseados no algoritmo SIMPLEX Passos do Simplex 18 1 Achar uma solução compatível básica inicial 2 Verificar se a solução é ótima Se for pare caso contrário siga para o passo 3 3 Determinar a variável não básica que deve entrar na base 4 Determinar a variável básica que deve sair da base 5 Achar a nova solução compatível básica e voltar ao passo 2 17 18 28042022 10 Problema da PO SA 19 MAX Z 3X1 4X2 Sujeito a X1 X2 8 restrição da matériaprima X1 2 X2 12 restrição da matériaprima X1 6 restrição da matériaprima X1 X2 0 Suponha um problema de MIX de produção qualquer Solução 20 Passo 1 achar uma solução compatível básica inicial Eliminar as desigualdades Z 3 X1 4 X2 0 X1 X2 xF1 8 X1 2 X2 xF2 12 X1 xF3 6 Variáveis de Folga 19 20 28042022 11 Solução 21 Passo 1 achar uma solução compatível básica inicial Representação em forma de tabela Solução básica inicial Z X1 X2 xF1 xF2 xF3 b 1 3 4 0 0 0 0 0 1 1 1 0 0 8 0 1 2 0 1 0 12 0 1 0 0 0 1 6 Para encontrar a solução é necessário identificar a base matriz identidade Variáveis básicas xF1 xF2 e xF3 escrever estas variáveis na tabela Encontrar a solução Z 0 X1 0 X2 0 xF1 8 xF2 12 xF3 6 Base xF1 xF2 xF3 Solução 22 Passo 2 Verificar se a solução é ótima Se for pare caso contrário siga para o passo 3 A solução será considerada ótima quando todos os coeficientes da primeira linha da tabela forem positivos Z X1 X2 xF1 xF2 xF3 b Base 1 3 4 0 0 0 0 xF1 0 1 1 1 0 0 8 xF2 0 1 2 0 1 0 12 xF3 0 1 0 0 0 1 6 A solução não é ótima 21 22 28042022 12 Solução 23 Passo 3 Determinar a variável não básica que deve entrar na base Regra escolher a variável com coeficiente negativo de maior valor absoluto Z X1 X2 xF1 xF2 xF3 b Base 1 3 4 0 0 0 0 xF1 0 1 1 1 0 0 8 xF2 0 1 2 0 1 0 12 xF3 0 1 0 0 0 1 6 X2 vai entrar na base Solução 24 Passo 4 Determinar a variável básica que deve sair da base Regra Calcular a razão entre os termos da direita das restrições pelos coeficientes positivos da variável que entra Escolher a menor razão Z X1 X2 xF1 xF2 xF3 b Base 1 3 4 0 0 0 0 xF1 0 1 1 1 0 0 8 xF2 0 1 2 0 1 0 12 xF3 0 1 0 0 0 1 6 xF2 vai sair da base Razão 81 8 122 6 23 24 28042022 13 Solução 25 Passo 5 Achar a nova solução compatível básica e voltar ao passo 2 a Cálculo da nova linha pivô linha do pivô pivô Z X1 X2 xF1 xF2 xF3 b Base 1 3 4 0 0 0 0 Razão xF1 0 1 1 1 0 0 8 8 xF2 0 1 2 0 1 0 12 6 xF3 0 1 0 0 0 1 6 Pivô Z X1 X2 xF1 xF2 xF3 b Base Razão 0 12 1 0 12 0 6 Solução 26 Passo 5 Achar a nova solução compatível básica e voltar ao passo 2 b Cálculo da nova linha i linha i coef i Nova linha pivô Z X1 X2 xF1 xF2 xF3 b Base Razão 0 12 1 0 12 0 6 Nova Linha 1 Linha 1 4 Nova Linha Pivô 1 3 4 0 0 0 0 0 2 4 0 2 0 24 1 1 0 0 2 0 24 Nova Linha 2 Linha 2 1 Nova Linha Pivô 0 1 1 1 0 0 8 0 12 1 0 12 0 6 0 12 0 1 12 0 2 1 1 0 0 2 0 24 0 12 0 1 12 0 2 25 26 28042022 14 Solução 27 Passo 5 Achar a nova solução compatível básica e voltar ao passo 2 b Cálculo da nova linha i linha i coef i Nova linha pivô Solução Z 24 X1 0 X2 6 xF1 2 xF2 0 xF3 6 Z X1 X2 xF1 xF2 xF3 b Base 1 1 0 0 2 0 24 Razão 0 12 0 1 12 0 2 0 12 1 0 12 0 6 Nova Linha 4 Linha 4 0 Nova Linha Pivô 0 1 0 0 0 1 6 0 0 0 0 0 0 0 0 1 0 0 0 1 6 0 1 0 0 0 1 6 xF1 X2 xF3 Solução 28 Passo 3 e 4 Variável que entra e que sai A Solução é ótima Resposta NÃO há negativos na primeira linha Passo 2 Verificar se a solução é ótima Se for pare caso contrário siga para o passo 3 Z X1 X2 xF1 xF2 xF3 b Base 1 1 0 0 2 0 24 Razão xF1 0 12 0 1 12 0 2 X2 0 12 1 0 12 0 6 xF3 0 1 0 0 0 1 6 205 4 605 12 61 6 Pivô 27 28 28042022 15 Solução 29 Passo 5 Achar a nova solução compatível básica e voltar ao passo 2 a Cálculo da nova linha pivô linha pivô pivô Z X1 X2 xF1 xF2 xF3 b Base Razão 0 1 0 2 1 0 4 0 12 0 1 12 0 2 12 0 1 0 2 1 0 4 Solução 30 Passo 5 Achar a nova solução compatível básica e voltar ao passo 2 b Cálculo da nova linha i linha i coef i Nova linha pivô Z X1 X2 xF1 xF2 xF3 b Base Razão 0 1 0 2 1 0 4 Nova Linha 1 Linha 1 1 Nova Linha Pivô 1 1 0 0 2 0 24 0 1 0 2 1 0 4 1 0 0 2 1 0 28 Nova Linha 3 Linha 1 12 Nova Linha Pivô 0 12 1 0 12 0 6 0 12 0 1 12 0 2 0 0 1 1 1 0 4 Nova Linha 4 Linha 1 1 Nova Linha Pivô 0 1 0 0 0 1 6 0 1 0 2 1 0 4 0 0 0 2 1 1 2 1 0 0 2 1 0 28 0 0 1 1 1 0 4 0 0 0 2 1 1 2 29 30 28042022 16 Solução 31 Passo 5 Achar a nova solução compatível básica e voltar ao passo 2 Solução Z 28 X1 4 X2 4 xF1 0 xF2 0 xF3 2 A Solução é ótima Resposta SIM não há negativos na primeira linha Z X1 X2 xF1 xF2 xF3 b Base 1 0 0 2 1 0 28 Razão 0 1 0 1 1 0 4 0 0 1 1 1 0 4 0 0 0 2 1 1 2 X1 X2 xF3 31
Send your question to AI and receive an answer instantly
Preview text
28042022 1 1 ADM 043 Pesquisa Operacional UNIFEI Universidade Federal de Itajubá Prof Dr Alexandre Ferreira de Pinho 2 Solução de Problemas de PL Método Gráfico 1 2 28042022 2 Conceito 3 Possível para duas variáveis Essa técnica consiste em representar em um sistema de eixos ortogonais as equações das restrições do problema Região de soluções é o conjunto de todos os pontos que satisfazem todas as restrições do problema Pontos onde será procurada a solução ótima Método Gráfico 4 MAX Z 3X1 4X2 Sujeito a X1 X2 8 restrição da matériaprima A X1 2 X2 12 restrição da matériaprima B X1 6 restrição da matériaprima C X1 X2 0 Plotar as inequações no gráfico A modelagem apresentada aqui é de um problema de MIX de produção 3 4 28042022 3 Método Gráfico 5 X1 e X2 0 indicam o primeiro quadrante X1 X2 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 X1 6 X1 X2 8 X1 2 X2 12 Região de Soluções MAX Z 3X1 4X2 Sujeito a X1 X2 8 X1 2 X2 12 X1 6 X1 X2 0 Método Gráfico 6 Após a identificação da região de solução devese procurar a solução ótima que será o ponto da região que leva ao maior valor de Z 3 X1 4 X2 Para tal escolhese um valor arbitrário para Z por exemplo 10 12 20 24 30 etc Usando o 12 temse 3 X1 4 X2 12 Dica atribua um valor que seja divisível pelos coeficientes no caso 3 e 4 e que o resultado da divisão deste valor pelos coeficientes esteja dentro da região de soluções 5 6 28042022 4 Método Gráfico 7 Traçar a reta da função objetivo 3 X1 4 X2 12 X1 X2 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 X1 6 X1 X2 8 X1 2 X2 12 3 X1 4 X2 12 Uma vez desenhada a reta podese encontrar a solução ótima pelo movimento paralelo da reta que desenhamos Este movimento é feito até que toda a região de soluções seja considerada Método Gráfico 8 Note que Problemas de MAX paralelas para cima Problemas de MIN paralelas para baixo X1 X2 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 X1 6 X1 X2 8 X1 2 X2 12 Ponto Ótimo X1 4 X2 4 Z 28 7 8 28042022 5 Casos Especiais em PL 9 Sem solução infeasibility X2 X1 20 40 60 80 100 120 20 40 60 80 100 120 C E Casos Especiais em PL 10 Sem fronteira unboundedness X1 X2 20 40 60 80 100 120 20 40 60 80 100 120 C E 9 10 28042022 6 Casos Especiais em PL 11 Múltiplas soluções alternate optimal solutions X2 X1 20 40 60 80 100 120 20 40 60 80 100 120 C E Exercício 12 Uma empresa fabrica 2 produtos P1 e P2 A margem de contribuição unitária do produto P1 é de 1000 e a margem de contribuição unitária de P2 é 1500 A empresa precisa de 20 horas para fabricar uma unidade de P1 e de 40 horas para fabricar uma unidade de P2 O tempo anual de produção disponível para isso é de 1200 horas A demanda esperada para cada produto é de 40 unidades anuais para P1 e 50 unidades anuais para P2 Qual é o modelo matemático e o resultado do plano de produção anual para que a empresa maximize sua margem de contribuição nesses itens 11 12 28042022 7 Exercício Modelagem 13 Passo 1 Definição das variáveis de decisão X1 Quantidade que será produzida de P1 X2 Quantidade que será produzida de P2 Passo 2 Definição da Função Objetivo MAX Margem 1000 X1 1500 X2 MAX Z 1000 X1 1500 X2 Exercício Modelagem 14 Passo 3 Definição das restrições do problema Quantidade de tempo disponível 1200 horas 20 X1 40 X2 1200 Demanda de P1 40 unidades X1 40 Demanda de P2 50 unidades X1 50 Passo 4 Não negatividade X1 0 X2 0 13 14 28042022 8 Exercício Cálculo 15 X1 X2 10 20 30 40 50 60 70 80 90 100 110 120 10 20 30 40 50 60 70 80 90 100 X1 40 20 X1 40 X2 1200 MAX Z 1000 X1 1500 X2 Sujeito a 20 X1 40 X2 1200 X1 40 X2 50 X1 X2 0 X2 50 1000 X1 1500 X2 15000 Solução X1 40 X2 10 Z 55000 16 Solução de Problemas de PL Método Simplex 15 16 28042022 9 Conceito 17 Possível para qualquer quantidade de variáveis Desenvolvido em 1947 por George B Dantzig Método interativo algoritmo utilizado para achar algebricamente a solução ótima de um problema de PL Os softwares de PL são baseados no algoritmo SIMPLEX Passos do Simplex 18 1 Achar uma solução compatível básica inicial 2 Verificar se a solução é ótima Se for pare caso contrário siga para o passo 3 3 Determinar a variável não básica que deve entrar na base 4 Determinar a variável básica que deve sair da base 5 Achar a nova solução compatível básica e voltar ao passo 2 17 18 28042022 10 Problema da PO SA 19 MAX Z 3X1 4X2 Sujeito a X1 X2 8 restrição da matériaprima X1 2 X2 12 restrição da matériaprima X1 6 restrição da matériaprima X1 X2 0 Suponha um problema de MIX de produção qualquer Solução 20 Passo 1 achar uma solução compatível básica inicial Eliminar as desigualdades Z 3 X1 4 X2 0 X1 X2 xF1 8 X1 2 X2 xF2 12 X1 xF3 6 Variáveis de Folga 19 20 28042022 11 Solução 21 Passo 1 achar uma solução compatível básica inicial Representação em forma de tabela Solução básica inicial Z X1 X2 xF1 xF2 xF3 b 1 3 4 0 0 0 0 0 1 1 1 0 0 8 0 1 2 0 1 0 12 0 1 0 0 0 1 6 Para encontrar a solução é necessário identificar a base matriz identidade Variáveis básicas xF1 xF2 e xF3 escrever estas variáveis na tabela Encontrar a solução Z 0 X1 0 X2 0 xF1 8 xF2 12 xF3 6 Base xF1 xF2 xF3 Solução 22 Passo 2 Verificar se a solução é ótima Se for pare caso contrário siga para o passo 3 A solução será considerada ótima quando todos os coeficientes da primeira linha da tabela forem positivos Z X1 X2 xF1 xF2 xF3 b Base 1 3 4 0 0 0 0 xF1 0 1 1 1 0 0 8 xF2 0 1 2 0 1 0 12 xF3 0 1 0 0 0 1 6 A solução não é ótima 21 22 28042022 12 Solução 23 Passo 3 Determinar a variável não básica que deve entrar na base Regra escolher a variável com coeficiente negativo de maior valor absoluto Z X1 X2 xF1 xF2 xF3 b Base 1 3 4 0 0 0 0 xF1 0 1 1 1 0 0 8 xF2 0 1 2 0 1 0 12 xF3 0 1 0 0 0 1 6 X2 vai entrar na base Solução 24 Passo 4 Determinar a variável básica que deve sair da base Regra Calcular a razão entre os termos da direita das restrições pelos coeficientes positivos da variável que entra Escolher a menor razão Z X1 X2 xF1 xF2 xF3 b Base 1 3 4 0 0 0 0 xF1 0 1 1 1 0 0 8 xF2 0 1 2 0 1 0 12 xF3 0 1 0 0 0 1 6 xF2 vai sair da base Razão 81 8 122 6 23 24 28042022 13 Solução 25 Passo 5 Achar a nova solução compatível básica e voltar ao passo 2 a Cálculo da nova linha pivô linha do pivô pivô Z X1 X2 xF1 xF2 xF3 b Base 1 3 4 0 0 0 0 Razão xF1 0 1 1 1 0 0 8 8 xF2 0 1 2 0 1 0 12 6 xF3 0 1 0 0 0 1 6 Pivô Z X1 X2 xF1 xF2 xF3 b Base Razão 0 12 1 0 12 0 6 Solução 26 Passo 5 Achar a nova solução compatível básica e voltar ao passo 2 b Cálculo da nova linha i linha i coef i Nova linha pivô Z X1 X2 xF1 xF2 xF3 b Base Razão 0 12 1 0 12 0 6 Nova Linha 1 Linha 1 4 Nova Linha Pivô 1 3 4 0 0 0 0 0 2 4 0 2 0 24 1 1 0 0 2 0 24 Nova Linha 2 Linha 2 1 Nova Linha Pivô 0 1 1 1 0 0 8 0 12 1 0 12 0 6 0 12 0 1 12 0 2 1 1 0 0 2 0 24 0 12 0 1 12 0 2 25 26 28042022 14 Solução 27 Passo 5 Achar a nova solução compatível básica e voltar ao passo 2 b Cálculo da nova linha i linha i coef i Nova linha pivô Solução Z 24 X1 0 X2 6 xF1 2 xF2 0 xF3 6 Z X1 X2 xF1 xF2 xF3 b Base 1 1 0 0 2 0 24 Razão 0 12 0 1 12 0 2 0 12 1 0 12 0 6 Nova Linha 4 Linha 4 0 Nova Linha Pivô 0 1 0 0 0 1 6 0 0 0 0 0 0 0 0 1 0 0 0 1 6 0 1 0 0 0 1 6 xF1 X2 xF3 Solução 28 Passo 3 e 4 Variável que entra e que sai A Solução é ótima Resposta NÃO há negativos na primeira linha Passo 2 Verificar se a solução é ótima Se for pare caso contrário siga para o passo 3 Z X1 X2 xF1 xF2 xF3 b Base 1 1 0 0 2 0 24 Razão xF1 0 12 0 1 12 0 2 X2 0 12 1 0 12 0 6 xF3 0 1 0 0 0 1 6 205 4 605 12 61 6 Pivô 27 28 28042022 15 Solução 29 Passo 5 Achar a nova solução compatível básica e voltar ao passo 2 a Cálculo da nova linha pivô linha pivô pivô Z X1 X2 xF1 xF2 xF3 b Base Razão 0 1 0 2 1 0 4 0 12 0 1 12 0 2 12 0 1 0 2 1 0 4 Solução 30 Passo 5 Achar a nova solução compatível básica e voltar ao passo 2 b Cálculo da nova linha i linha i coef i Nova linha pivô Z X1 X2 xF1 xF2 xF3 b Base Razão 0 1 0 2 1 0 4 Nova Linha 1 Linha 1 1 Nova Linha Pivô 1 1 0 0 2 0 24 0 1 0 2 1 0 4 1 0 0 2 1 0 28 Nova Linha 3 Linha 1 12 Nova Linha Pivô 0 12 1 0 12 0 6 0 12 0 1 12 0 2 0 0 1 1 1 0 4 Nova Linha 4 Linha 1 1 Nova Linha Pivô 0 1 0 0 0 1 6 0 1 0 2 1 0 4 0 0 0 2 1 1 2 1 0 0 2 1 0 28 0 0 1 1 1 0 4 0 0 0 2 1 1 2 29 30 28042022 16 Solução 31 Passo 5 Achar a nova solução compatível básica e voltar ao passo 2 Solução Z 28 X1 4 X2 4 xF1 0 xF2 0 xF3 2 A Solução é ótima Resposta SIM não há negativos na primeira linha Z X1 X2 xF1 xF2 xF3 b Base 1 0 0 2 1 0 28 Razão 0 1 0 1 1 0 4 0 0 1 1 1 0 4 0 0 0 2 1 1 2 X1 X2 xF3 31