Se o conjunto de soluções viáveis do PPL não for limitado, em alguma iteração do algoritmo Simplex:
(a) () será necessário utilizar o método das duas fases para obter a inviabilidade;
(b) () pelo menos uma das colunas correspondentes as VNB com zj-cj >= 0 é formada por elementos nulos e negativos;
(c) () existirá uma variável não básica com maior zj-cj formada por elementos nulos ou negativos;
(d) () existirá mais de uma VNB candidata a entrar na base com o mesmo valor de zj-cj >= 0.

Passo 1

O enunciado pergunta o que ocorre, em alguma iteração do Simplex, quando o conjunto de soluções viáveis de um PPL é não limitado. O conteúdo aqui é a detecção de não-limitatividade pelo teste do razão: precisamos lembrar que, para um problema de maximização, escolhemos uma variável não básica (VNB) com (zj-cj)>0 para entrar na base e então aplicamos o teste da razão mínima para encontrar quem sai.

Passo 2

Suponha que em certo tableau exista uma VNB xk com
zk-ck>0,
ou seja, ainda há chance de aumentar indefinidamente o valor da função-objetivo ao incrementar xk.

Passo 3

Para aplicar o teste da razão, examinamos a coluna k (os coeficientes aik nas restrições básicas). Se todos esses coeficientes satisfazem
aik<= 0 para toda linha i,
então não há pivô positivo e o Simplex não encontra valor limite para xk. Isso significa que podemos aumentar xk sem nunca violar as restrições, logo a função-objetivo cresce sem limite e o problema é não-limitado.

Passo 4

A condição descrita corresponde exatamente à opção (b): “pelo menos uma das colunas correspondentes às VNB com zj-cj>=0 é formada por elementos nulos e negativos”. É essa coluna que impede a escolha de um pivô positivo e sinaliza que o PPL é não limitado.

Resposta

(b)

Exercícios relacionados