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.
(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
. 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
e selecionamos o menor
. 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.