Quando existe empate no critério de saída da base, então:
(a) () existe degeneração;
(b) () existem infinitas soluções ótimas para o problema;
(c) () esse fato é absolutamente normal na condição de parada e a solução é única;
(d) () o conjunto das restrições é linearmente dependente;
(e) () é possível eliminar do problema uma das restrições que geraram o empate;
(f) () a partir da ocorrência do empate, as folgas das linhas empatadas serão sempre iguais a zero para todas as demais iterações do Simplex.

Passo 1

O enunciado fala de “empate no critério de saída da base” dentro do método Simplex, ou seja, duas (ou mais) linhas do tableau dão o mesmo valor mínimo no teste de razão
thetai = bar bi / aij. O conteúdo aqui é degeneração em programação linear.

Passo 2

No Simplex, para escolher a variável que sai da base, calculamos para cada linha viável
thetai = bar biaijcom aij>0
e selecionamos o menor thetai. Se houver empate, duas linhas atingem ao mesmo tempo o limite de aumento da variável que entra.

Passo 3

Degeneração ocorre quando, após o pivot, alguma variável básica assume valor zero. Num empate de saída cujos valores mínimos coincidam em zero, ambas as restrições ficam simultaneamente ativas (binding), levando a uma variável básica zerar. Mesmo que o empate não seja em zero, a escolha arbitrária de qual linha sair pode gerar um caminho degenerado em iterações seguintes.

Resposta

(a) existe degeneração.

Exercícios relacionados