Simplex-Casos Especiais do Simplex

Simplex-Casos Especiais do Simplex

Campus - Mossoró Profª Adricia Fonseca Mendes

Algoritmo Simplex – Casos Especiais Notas de Aula da Profª Amanda Gondim de Oliveira

Introdução

•Esta seção considera quatro casos especiais que podem surgir na utilização do método simplex:

•Degeneração •Múltiplas soluções ótimas

•Soluções Ilimitadas

•Soluções Inviáveis

Degeneração

•Na aplicação da condição de viabilidade do método simplex pode ocorrer um empate na razão mínima, o qual pode ser resolvido arbitrariamente.

•Quando isso acontece , no mínimo uma variável básica será zero na iteração seguinte, e diz-se que essa nova solução é degenerada.

•Considere o problema:

Degeneração •Dadas as variáveis de folga x3 e x4, seguem as iterações do simplex:

•Na iteração 0, x3 e x4 empatam no critério que determina a variável que sai, o que leva à degeneração na iteração 1 porque a variável básica x4 assume valor igual a zero.

Degeneração •Qual a implicação prática da degeneração?

Degeneração

•Do ponto de vista teórico, a degeneração tem duas implicações:

1)Ciclagem ou retorno cíclico:

•Observe as iterações 1 e 2 do simplex e note que o valor da função objetivo não melhora (z=18).

•É possível que o método simplex entre em uma sequencia de iterações sem nunca melhorar o valor da função objetivo.

2)Segundo ponto: Examine as iterações 1 e 2 . Embora tenham variáveis básicas e não-básicas distintas, resultam em valores idênticos.

x1=0 , x2=2, x3=0, x4=0 e z=18 da iteração 1, ainda que não •É possível interromper os cálculos seja ótima?

•Não, A solução pode ser temporariamente degenerada.

Degeneração

•Observe que 3 retas passam pelo ponto ótimo, consequentemente 1 delas é redundante.

•O fato de saber alguns recursos são supérfluos pode ser valioso durante a implementação da solução.

Múltiplas Soluções Ótimas

•Quando a função objetivo tem direção paralela a uma restrição, a mesma pode assumir o mesmo valor em mais de um ponto de solução, ou seja, Múltiplas soluções ótimas.

Múltiplas Soluções Ótimas

•A iteração 1 dá a solução ótima x1=0, x2 = 2,5 e z=10, que coincide com o ponto B.

•Como sabemos por essa tabela que outras soluções ótimas existem?

Múltiplas Soluções Ótimas

•Observe os coeficientes das variáveis não básicas na equação Z da iteração 1.

•O coeficiente de x é zero, o que indica que x1 pode entrar na base sem alterar o valor de z.

Múltiplas Soluções Ótimas

•A iteração 2 faz exatamente isso, onde x1 entra e x4 sai da base. •O novo ponto ótimo é C ( x1=3 e x2=1) e z=10.

ConsidereZ = 3x1 + 2x2

Múltiplas Soluções Ótimas – 2° Exemplo HILLIER, LIEBERMAN (2006)

Múltiplas Soluções Ótimas – 2° Exemplo

Portanto, as duas soluções ótimas são (4, 3, O, 6, 0) e (2, 6, 2, O, O), cada uma delas levando a Z = 18. Logo, estas duas são as únicas soluções que são ótimas e todas as demais soluções ótimas são uma combinação convexa dessas duas.

Em que os pesos w1 e w2 são números que satisfazem as relações: Por exemplo considerando: w1= 1/3 e w2= 2/3

Então este pontoé caracterizado como uma combinação convexa das
duas soluções ótimase . Portanto, toda solução ótima no

exemplo é uma combinação convexa destas soluções. HILLIER, LIEBERMAN (2006)

Múltiplas Soluções Ótimas

•Na prática, múltiplas soluções ótimas são úteis porque podemos escolher entre muitas soluções sem que o valor da função objetivo sofra deterioração.

•No exemplo, a solução em B mostra que somente a atividade 2 é positiva, já em C ambas as atividades são positivas.

•Se o exemplo representar um mix de produtos, pode haver vantagem em produzir dois produtos em vez de um para enfrentar a concorrência de mercado.

•Nesse caso, a solução em C pode ser mais atraente.

Solução Ilimitada

•Em alguns problemas de PL, os valores das variáveis podem ser aumentados indefinidamente sem violar nenhuma das restrições, o que significa que a região de soluções é ilimitada em no mínimo uma variável.

Solução Ilimitada

•Na tabela inicial, x1 e x2 têm coeficientes negativos na equação Z, ou seja, qualquer uma pode melhorar a solução.

•Caso escolhêssemos x2 para entrar na base, qual variável iria sair da base?

•Todos os coeficientes são negativos ou zero.

•Não há nenhuma variável que saia e que x2 possa ser aumentada indefinidamente sem violar nenhuma das restrições.

Solução Inviável

•Problemas de PL podem não ter nenhuma solução viável.

•Os problemas que usam variáveis artificiais, terão as mesmas iguais a zero se o modelo tiver uma região viável.

•Caso contrário, ao menos uma variável artificial será positiva na iteração ótima.

Exercícios •1) Resolva pelo método simplex:

Exercícios 2) Max z = 20x1 + 10 x2 + x3

3x1 – 3x2 + 5x3 ≤ 50 x1 + x3 ≤ 10 x1 – x2 + 4x3 ≤ 20 x1, x2, x3 ≥ 0

Comentários