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
é formada por elementos nulos e negativos;
(c) () existirá uma variável não básica com maior
formada por elementos nulos ou negativos;
(d) () existirá mais de uma VNB candidata a entrar na base com o mesmo valor de
.
(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
(c) () existirá uma variável não básica com maior
(d) () existirá mais de uma VNB candidata a entrar na base com o mesmo valor de
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
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
com
ou seja, ainda há chance de aumentar indefinidamente o valor da função-objetivo ao incrementar
.
Passo 3
Para aplicar o teste da razão, examinamos a coluna
(os coeficientes
nas restrições básicas). Se todos esses coeficientes satisfazem
então não há pivô positivo e o Simplex não encontra valor limite para
. Isso significa que podemos aumentar
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
é 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)