SimplexCasosEspeciais

Prévia do material em texto

PESQUISA OPERACIONAL I 
 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 
 
 
Casos especiais no SIMPLEX 
O método Simplex pode apresentar algumas situações especiais que são descritas nos itens 
que se seguem. 
Variáveis entrantes com coeficientes iguais 
Ao ser analisada a função objetivo, pode ocorrer a seguinte situação: (MAX) Z = 10x1 + 
10x2. Neste caso, as variáveis x1 e x2 possuem a mesma importância (mesmo coeficiente) no ganho 
de Z, e podemos escolher qualquer uma das variáveis como entrante. 
Variáveis saintes empatadas 
Imagine que, no problema anterior, tivéssemos chegado à seguinte situação na escolha da 
variável sainte (sendo x1 entrante e F4 não básica): 
(1) Z – 20 x1 + 20 F4 = 3600 
(2) F1 = 700 – 70x1 + F4 70 / 3 (x1 máximo = 10) 
(3) F2 = 900 - 90x1 + F4 50 / 3 (x1 máximo = 10) 
(4) F3 = 80 – 2x1 (x1 máximo = 40) 
(5) x2 = 60 – F4 / 3 (x1 máximo = infinito) 
Nesta situação F1 e F2 estariam empatados como possível variável sainte. Podemos 
novamente escolher uma arbitrariamente. Entretanto, algo interessante acontece. Observemos a 
evolução, caso escolhêssemos F1 como sainte: 
(1) Z – 20 x1 + 20 F4 = 3600 
(2) 70x1 + F1 – F4 70 / 3 = 700 
(3) 90x1 + F2 – F4 50 / 3 = 900 
(4) 2x1 + F3 = 80 
(5) x2 + F4 / 3 = 60 
Para que (2), onde aparece a entrante, tenha coeficiente 1 (÷ 70): 
(2) x1 + F1 /70 – F4 / 3 = 10 
Para eliminar x1 de (1), faremos: (1)+(2)*20. Assim: 
Neste momento, teriamos: 
Básicas: F1, F2, F3, x2 
Não básicas: x1, F4 
entrante: x1 sainte: F1 
 PESQUISA OPERACIONAL I 
 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 
 
 (1) Z + F1 20/70 + F4 40/3 = 3800 
Para eliminar x1 de (3), substituímo-la por (3)+(2)*-90. Assim: 
 (3) - F1 90/70 + F2 + F4 40/3 = 0 
Para eliminar x1 de (4), substituímo-la por (4)+(2)*-2. Assim: 
(4) - F1 2/70 + F3 + F4 2/3 = 60 
Como x1 não aparece em (5), ficamos com: 
(1) Z + F1 20/70 + F4 40/3 = 3800 
 (2) x1 + F1 /70 – F4 / 3 = 10 
 (3) - F1 90/70 + F2 + F4 40/3 = 0 
 (4) - F1 2/70 + F3 + F4 2/3 = 60 
 (5) x2 + F4 / 3 = 60 
Zerando as variáveis não básicas (F1 e F4), teremos a solução: 
(1) Z = 3800 
(2) x1 = 10 
(3) F2 = 0 
(4) F3 = 60 
(5) x2 = 60 
Ou seja, a variável que não escolhemos como saínte, acabou ficando com 0 (chamamos de 
variável degenerada). Caso o empate fosse entre n variáveis, haveria n-1 degeneradas no próximo 
ciclo, o que não impede a continuação do algoritmo. Entretanto, em determinadas e raríssimas 
ocasiões isso pode causar um loop no SIMPLEX (o que em geral não é tratado pelas 
implementações computacionais, pois esse tratamento é muito demorado) . 
Não existência de variável sainte 
Suponha que na escolha da variável sainte temos a seguinte situação: x1 é a variável entrante 
e F1, F2 e F3 são as candidatas a variável sainte. Sejam as restrições das candidatas a sainte: 
(2) F1 = 5 + x1 + 3x2 
(3) F2 = 29 − 2x2 
 PESQUISA OPERACIONAL I 
 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 
 
(4) F3 = 12 + 2x1. 
x2 é variável não básica, não é entrante ou seja vai continuar como não básica (= 0). Na 
equação (2) o valor de x1, que só pode ser ≥ 0, pode ir até ∞ que F1 não chegará a zero. Na equação 
(3) não aparece x1. Logo qualquer valor que ele assumir (até ∞) não vai influenciar o valor de F2. 
Na equação (4), x1 pode ir até +∞ que F3 não chegará a zero. Ou seja, o valor de x1 poderá ir até ∞ 
que nenhuma das candidatas a variável sainte chegará a zero (não existe variável sainte). Assim, 
temos um modelo com solução ilimitada ou seja Z = +∞ se o problema é de maximização ou Z=−∞ 
se o modelo é de minimização. Isto indica que o problema não está bem modelado, pois não deve 
existir objetivo igual a ±∞. 
 
Múltiplas soluções ótimas 
Seja o seguinte modelo de Programação Linear: 
(MAX) Z = 8x1 + 8x2 
2x1 + 2x2 ≤ 12 
2x1 + x2 ≤ 9 
x1 + 3x2 ≤ 16 
x1,x2 ≥ 0 
Resolvendo graficamente, temos: 
 
 PESQUISA OPERACIONAL I 
 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 
 
Como as retas “Z” são paralelas a um dos lados do espaço solução, a reta de Z ótima se 
confunde com o próprio lado do espaço solução e todos os pontos do segmento de reta (A – B) são 
pontos ótimos. Aplicando-se o simplex ao modelo temos: 
(1) Z − 8x1 − 8x2 = 0 
(2) 2x1 + 2x2 + F1 = 12 
(3) 2x1 + x2 + F2 = 9 
(4) x1 + 3x2 + F3 = 16 
Básicas: F1, F2, F3 Não básicas: x1, x2 . Entrante: x1 Sainte: F2 
 
 
Nova solução básica: 
(1) Z − 4x2 + 4F2 = 36 
(2) x2 + F1 − F2 = 3 
(3) x1 + x21/2 + F2 1/2 = 9/2 
(4) x2 5/2 − F2 1/2 + F3 = 23/2 
entrante: x2 ; sainte: F1 
 
Nova solução básica: (ponto A do gráfico) 
(1) Z + 4F1 = 48 
(2) x2 + F1 − F2 = 3 
(3) x1 − F1 1/2 + F2 = 3 
(4) − F1 5/2 + 2F2 + F3 = 4 
 
Observando a equação de Z ótima, Z + 4F1 = 48, vemos que ela tem uma característica 
incomum: uma variável não básica (F2) não aparece, ou seja tem coeficiente igual a 0, na equação. 
O fato de uma, ou mais, variáveis não básicas não aparecerem na equação (1) da solução ótima, 
indica que o modelo tem infinitas soluções ótimas. Como obtê-las? 
 PESQUISA OPERACIONAL I 
 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 
 
Podemos fazer com que F2, a variável não básica que não aparece na equação de Z, seja 
variável entrante. Como o seu coeficiente é igual a 0, ela não vai alterar o valor ótimo de Z. 
Escolhemos a variável sainte pelo processo normal e obtemos: 
Variável entrante: F2 Variável sainte: F3 
Nova solução básica: 
(1) Z + 4F1 = 48 
(2) x2 − 1/4 F1 +1/2F3 = 5 
(3) x1 +3/4F1 −1/2 F3 = 1 
(4) −5/4F1 + F2 +1/2 F3 = 2 
 
A nova solução, que também é ótima, é o ponto B do gráfico, ou seja o outro extremo do 
segmento de reta. Para se definir qualquer ponto de um segmento de reta precisamos de 2 pontos do 
segmento. O simplex nos deu os 2 pontos: A:(3,3) e B:(1,5). Com esses pontos podemos definir a 
equação da reta, limitada ao segmento limitado pelos pontos (3,3) e (1,5) que representa o conjunto 
infinito de soluções ótimas do problema. 
Modelos com função de minimização 
Quando o modelo do problema é de minimização, ao invés de maximização, a forma mais 
fácil de resolvê-lo é transformando o problema de minimização em um problema de maximização. 
Isto é feito multiplicando-se a função objetivo por -1. Observe que ao multiplicarmos uma função 
por -1, estamos invertendo os pontos da função em relação ao eixo dos X. Veja o gráfico abaixo: 
 
 
 
 
 
 
 
 
Z(x) → função a minimizar 
-Z(x) → função a maximizar 
x0 
O ponto x0 é o mesmo para minimizar Z(x) 
ou maximizar – Z(x) 
 PESQUISA OPERACIONAL I 
 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 
 
 
Assim, resolvemos o problema de maximização para – Z(x), encontramos os valores de x 
(variáveis de decisão) e multiplicamos o valor de Z obtido por -1. 
Por exemplo, resolva o sistema abaixo: 
(Min) Z = 3x1 + 6x2 - 2x3 + 4x4 com as seguintes restrições: 
x1 + 7x2 + 3x3 + 7x4 ≤ 46 
3x1 - x2 + x3 + 2x4 ≤ 8 
2x1 + 3x2 - x3 + x4 ≤ 10 
x1,x2,x3,x4 ≥ 0 
Solução: Z = -16; x1= x2= x4=0; x3=8 
 
Restrições de limite inferior (≥≥≥≥) 
Uma desigualdade em uma direção (≥ ou ≤) pode ser mudada para uma desigualdade na 
direção oposta, pela multiplicação de ambos os lados da desigualdade por (-1). 
Exemplo: a1 x1 + a2 x2 ≥ b é equivalente a - a1 x1 - a2 x2 ≤ -b 
 
Restrições de igualdade 
Uma equação podeser substituída por duas desigualdades de direções opostas. 
Exemplo: a1 x1 + a2 x2 = b é equivalente a duas desigualdades simultâneas: 
a1 x1 + a2 x2 ≤ b 
a1 x1 + a2 x2 ≥ b 
 
Variável irrestrita em sinal 
Uma variável irrestrita em sinal (ou seja, que pode ser positiva, nula ou negativa) pode ser 
substituída pela diferença de duas variáveis não negativas. 
Exemplo: se a variável x1 for irrestrita em sinal, pode ser substituída pela diferença (x'1 - x''1) 
com x'1 ≥ 0 e x''1 ≥ 0. 
 PESQUISA OPERACIONAL I 
 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 
 
Por exemplo, se no modelo anterior tivéssemos: 
(Min) Z = 3x1 + 6x2 - 2x3 + 4x4 com as seguintes restrições: 
x1 + 7x2 + 3x3 + 7x4 ≤ 46 
3x1 - x2 + x3 + 2x4 ≤ 8 
2x1 + 3x2 - x3 + x4 ≤ 10 
x1, x3,x4 ≥ 0 
x2 irrestrita em sinal 
 
Poderíamos fazer: x2 = x5 − x6. 
Nosso modelo ficaria então como: 
(Min) Z = 3x1 + 6x5 - 6x6 - 2x3 + 4x4 com as seguintes restrições: 
x1 + 7x5 - 7x6 + 3x3 + 7x4 ≤ 46 
3x1 - x5 + x6 + x3 + 2x4 ≤ 8 
2x1 + 3x5 - 3x6 - x3 + x4 ≤ 10 
x1, x3, x4, x5, x6 ≥ 0 
Obtida a solução ótima, para se obter o valor ótimo de x2 fazemos: 
x2 = x5 − x6. 
 
Resolva o sistema acima.