Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 Resolução de PLs � O método de enumeração de soluções básicas é muito ineficiente. � O número de possíveis bases pode ser enorme � Para encontrar a solução associada a cada base é preciso resolver um sistema linear � O método simplex resolve ambos os problemas � Só considera um número relativamente pequeno de bases � Não é necessário resolver um sistema linear inteiro para encontrar a solução associada a cada base 2 Pesquisa Operacional I Método Simplex Prof.: Eduardo Uchoa http://www.logis.uff.br/~uchoa/POI/ 3 Exemplo: Problema de Mix de Produção x15 10 15 x 2 5 1 0 maximizar z = 4,0 x1 + 6,0 x2 Sujeito a 1,5 x1 + 4,0 x2 ≤ 24 3,0 x1 + 1,5 x2 ≤ 21 1,0 x1 + 1,0 x2 ≤ 8 x1 , x2 ≥ 0 4 Método Simplex O método exige que o PL esteja no formato padrão. Introduzir variáveis de folga maximizar z = 4,0 x1 + 6,0 x2 Sujeito a 1,5 x1 + 4,0 x2 ≤ 24 3,0 x1 + 1,5 x2 ≤ 21 1,0 x1 + 1,0 x2 ≤ 8 x1 , x2 ≥ 0 5 PL no formato padrão. maximizar z = 4,0 x1 + 6,0 x2 Sujeito a 1,5 x1 + 4,0 x2 + 1 x3 = 24 3,0 x1 + 1,5 x2 + 1 x4 = 21 1,0 x1 + 1,0 x2 + 1 x5 = 8 x1 , x2 , x3 , x4 , x5 ≥ 0 Método Simplex 6 As variáveis de folga formam uma base que é uma matriz identidade => a solução básica viável associada é facilmente encontrada maximizar z = 4,0 x1 + 6,0 x2 Sujeito a 1,5 x1 + 4,0 x2 + 1 x3 = 24 3,0 x1 + 1,5 x2 + 1 x4 = 21 1,0 x1 + 1,0 x2 + 1 x5 = 8 x1 , x2 , x3 , x4 , x5 ≥ 0 Método Simplex 7 Reescrever o sistema isolando as variáveis básicas do lado esquerdo das equações. As variáveis não-básicas e o termo constante ficam do lado direito. A variável z (valor da função objetivo) também é representada por uma equação; x3 = 24 – 1,5 x1 – 4,0 x2 x4 = 21 – 3,0 x1 – 1,5 x2 x5 = 8 – 1,0 x1 – 1,0 x2 z = 4,0 x1 + 6,0 x2 Método Simplex 8 Reescrever o sistema isolando as variáveis básicas do lado esquerdo das equações. As variáveis não-básicas e os termos constantes ficam do lado direito. A variável z (valor da função objetivo) também é representada: x3 = 24 – 1,5 x1 – 4,0 x2 x4 = 21 – 3,0 x1 – 1,5 x2 x5 = 8 – 1,0 x1 – 1,0 x2 z = 4,0 x1 + 6,0 x2 Método Simplex A solução básica é: x1 = 0 x2 = 0 x3 = 24 x4 = 21 x5 = 8 Valor da FO para essa solução: z = 0 9 Dicionário Um PL reescrito de forma a que as variáveis de uma solução básica viável fiquem isoladas no seu lado esquerdo está em forma de “dicionário” x3 = 24 – 1,5 x1 – 4,0 x2 x4 = 21 – 3,0 x1 – 1,5 x2 x5 = 8 – 1,0 x1 – 1,0 x2 z = 4,0 x1 + 6,0 x2 10 Dicionário Essa representação é muito conveniente, porque o valor das variáveis básicas já é dado pelas constantes (não é necessário resolver o sistema BxB = b ). x3 = 24 – 1,5 x1 – 4,0 x2 x4 = 21 – 3,0 x1 – 1,5 x2 x5 = 8 – 1,0 x1 – 1,0 x2 z = 4,0 x1 + 6,0 x2 11 x15 10 15 x 2 5 1 0 x1 = 0 x2 = 0 x3 = 24 x4 = 21 x5 = 8 z = 0 Solução atual 12 Melhorando a solução atual Escolher uma variável não-básica (do lado direito do dicionário) para ter seu valor aumentado, de forma a também aumentar o valor da função objetivo. x3 = 24 – 1,5 x1 – 4,0 x2 x4 = 21 – 3,0 x1 – 1,5 x2 x5 = 8 – 1,0 x1 – 1,0 x2 z = 4,0 x1 + 6,0 x2 13 Escolher uma variável não-básica (do lado direito do dicionário) para ter seu valor aumentado, de forma a também aumentar o valor da função objetivo. x3 = 24 – 1,5 x1 – 4,0 x2 x4 = 21 – 3,0 x1 – 1,5 x2 x5 = 8 – 1,0 x1 – 1,0 x2 z = 4,0 x1 + 6,0 x2 Escolhemos x2. O maior valor que x2 pode ter sem que alguma variável básica fique com valor negativo é dado por: 2 24 21 8 min , , 6 4 1,5 1 x = = Nesse momento já sabemos que a nova solução vai ter z=36. A variável que passou a valer 0 após o crescimento de x2 foi x3. Melhorando a solução atual 14 Montando o novo dicionário O sistema é reescrito de forma a que x2 fique isolada no lado esquerdo e x3 vá para o lado direito. 3 1 2 2 1 3 2 1 3 324 4 2 34 24 2 3 16 8 4 x x x x x x x x x = − − = − − = − − Primeiro reescrevemos a única equação em que x2 e x3 aparecem 15 Substituindo a equação para x2 nas equações restantes, todo o sistema é atualizado: 2 1 3 4 1 1 3 5 1 1 3 1 1 3 3 16 8 4 3 3 121 3 6 2 8 4 3 18 1 1 6 8 4 3 14 6 6 8 4 x x x x x x x x x x x z x x x = − − = − − − − = − − − − = + − − Montando o novo dicionário 16 Novo dicionário Dizemos que a variável x3 saiu da base e a variável x2 entrou na base. 2 1 3 4 1 3 5 1 3 1 3 3 16 8 4 39 312 16 8 5 12 8 4 7 336 4 2 x x x x x x x x x z x x = − − = − + = − + = + − 17 Novo dicionário 2 1 3 4 1 3 5 1 3 1 3 3 16 8 4 39 312 16 8 5 12 8 4 7 336 4 2 x x x x x x x x x z x x = − − = − + = − + = + − A nova solução básica viável é: x1 = 0 x2 = 6 x3 = 0 x4 = 12 x5 = 2 Esta solução aumentou a função objetivo: z = 36 Dizemos que a variável x3 saiu da base e a variável x2 entrou na base. 18 Nova solução básica viável x15 10 15 x 2 5 1 0 : x1 = 0 x2 = 6 x3 = 0 x4 = 12 x5 = 2 z = 36 19 Melhorando a solução Ainda é possível aumentar o valor de z? 2 1 3 4 1 3 5 1 3 1 3 3 16 8 4 39 312 16 8 5 12 8 4 7 336 4 2 x x x x x x x x x z x x = − − = − + = − + = + − 20 Melhorando a solução Ainda é possível aumentar o valor de z? Sim. 2 1 3 4 1 3 5 1 3 1 3 3 16 8 4 39 312 16 8 5 12 8 4 7 336 4 2 x x x x x x x x x z x x = − − = − + = − + = + − 21 Melhorando a solução 2 1 3 4 1 3 5 1 3 1 3 3 16 8 4 39 312 16 8 5 12 8 4 7 336 4 2 x x x x x x x x x z x x = − − = − + = − + = + − Aumentando x1 sem fazer que uma variável básica fique com valor negativo. O maior valor para x1 é: 1 6 12 2 16 min , ,3 39 5 58 16 8 x = = Nesse momento já sabemos que a nova solução vai ter z=36+7/4.16/5=41,6. A variável que passou a valer 0 após o crescimento de x1 foi x5. 22 Montando o novo dicionário Seguindo o mesmo procedimento da iteração anterior, o dicionário é atualizado através da 3ª equação do dicionário anterior. x1 entra na base (vai pro lado esquerdo) e x5 sai da base (vai para o lado direito). 1 3 5 1 3 5 5 12 8 4 16 2 8 5 5 5 x x x x x x = + − = + − 23 Novo dicionário Substituindo x1 nas equações restantes do dicionário anterior, tem-se o seguinte dicionário atualizado: 2 3 5 4 3 5 1 3 5 3 5 24 2 3 5 5 5 21 3 39 5 5 10 16 2 8 5 5 5 208 4 14 5 5 5 x x x x x x x x x z x x = − + = − + = + − = − − 24 Novo dicionário Substituindo x1 nas equações restantes do dicionário anterior, tem-se o seguinte dicionário atualizado: 2 3 5 4 3 5 1 3 5 3 5 24 2 3 5 5 5 21 3 39 5 5 10 16 2 8 5 5 5 208 4 14 5 5 5 x x x x x x x x x z x x = − + = − + = + − = − − A solução básica viável é: x1 = 16/5 x2 = 24/5 x3 = 0 x4 = 21/5 x5 = 0 Esta solução resulta em: z = 208/5 25 x1 = 16/5 =3,2 x2 = 24/5 = 4,8 x3 = 0 x4 = 21/5 = 4,2 x5 = 0 z = 208/5 = 41,6 x15 10 15 x 2 5 1 0 Nova solução básica viável 26 Novo dicionário Ainda é possível aumentar o valor da função objetivo? 2 3 5 4 3 5 1 3 5 3 5 24 2 3 5 5 5 21 3 39 5 5 10 16 2 8 5 5 5 208 4 14 5 5 5 x x x x x x x x x z x x = − + = − + = + − = − − 27Solução ótima 2 3 5 4 3 5 1 3 5 3 5 24 2 3 5 5 5 21 3 39 5 5 10 16 2 8 5 5 5 208 4 14 5 5 5 x x x x x x x x x z x x = − + = − + = + − = − − Não existem variáveis não-básicas que, quando aumentadas, resultem em aumento no valor da função objetivo. Logo, a solução básica mostrada nesse sistema é ótima. 28 1. Montar um dicionário inicial 2. Olhando a equação do z, escolha uma variável não- básica xin cujo aumento melhoraria a solução corrente do dicionário (coeficiente negativo se for minimização, positivo se for maximização). Se não houver tal variável, a solução corrente é ótima. 3. Calcule o máximo valor para que xin que não torne uma variável básica negativa. Se esse valor for infinito, o PL é ilimitado. Caso contrário, escolha uma variável xout que bloqueou o crescimento de xin. 4. A variável xin entra na base, xout sai da base. Atualize o dicionário colocando xin isolado do lado esquerdo, xout vai pro lado direito. Volte para o Passo 2. Método Simplex 29 OBSERVAÇÃO Este material refere-se às notas de aula do curso TEP117 (Pesquisa Operacional I) da Universidade Federal Fluminense (UFF) e foi criado a partir das notas do Prof. Rodrigo A. Scarpel do ITA (www.mec.ita.br/~rodrigo) e não pode ser reproduzido sem autorização prévia de ambos os autores. Quando autorizado, seu uso é exclusivo para atividades de ensino e pesquisa em instituições sem fins lucrativos.
Compartilhar