Mostre que no método Simplex, se uma variável x_{j} sai a base então ela não pode voltar à base na iteração seguinte.
Passo 1
O que o enunciado pede: demonstrar que, numa iteração do método Simplex, se uma variável básica x_{B_\ell} sai da base (ou seja, torna-se não-básica) então essa mesma variável não pode voltar a entrar na base já na iteração imediatamente seguinte.
Informações dadas/convencionadas que vou usar (sem resolver ainda):
Problema em forma padrão: maximizar \,c^T x sujeito a \,Ax=b,\;x\ge0.
Tem-se uma base atual B (com variáveis básicas x_B) e o conjunto de não-básicas N.
Para cada coluna a_j de A define-se D_j := A_B^{-1} a_j e p := A_B^{-1} b.
Os custos reduzidos são \bar c_j := c_j - c_B^T D_j. Para variáveis básicas vale \bar c_{B_i}=0.
Na iteração considerarei e\in N como índice da variável que entra (escolhida porque \bar c_e>0 para aumentar a função objetivo) e \ell o índice da linha da base cujo x_{B_\ell} sai (determinado pelo teste da razão mínima).
O pivot é realizado na linha \ell, onde d_\ell := (D_e)_\ell > 0 e o passo \theta = p_\ell / d_\ell > 0.
Passo 2
Montagem das equações do tableau (forma conveniente). A expressão das variáveis básicas em função das não-básicas é:
x_B = p - \sum_{j\in N} D_j\, x_j.
Em componentes, para a linha \ell (a que sai) temos
onde escrevi d_\ell=(D_e)_\ell e D_{\ell j}=(D_j)_\ell. Expliquei o que é cada símbolo: p_\ell é a \ell-ésima componente de p, d_\ell a \ell-ésima componente da coluna do candidato a entrar.
Passo 3
Expressão da linha da função objetivo (linha z) antes do pivot. Usando custos reduzidos, a função objetivo fica
Interpretação: após o pivot a variável x_{B_\ell} tornou-se não-básica; o coeficiente que aparece multiplicando x_{B_\ell} na linha z é exatamente o novo custo reduzido dessa variável, que chamamos \bar c'_\ell. Assim
\bar c'_\ell = -\frac{\bar c_e}{d_\ell}.
Passo 5
Sinal e conclusão: como \bar c_e>0 (escolhida para entrar) e d_\ell>0 (condição do teste da razão mínima), tem-se
\bar c'_\ell = -\frac{\bar c_e}{d_\ell} < 0.
No método Simplex (forma usual para maximização) apenas variáveis com custo reduzido positivo são candidatas a entrar na base (pois estas aumentam o objetivo). Como \bar c'_\ell<0, a variável que saiu não pode ser escolhida como variável entrante na iteração imediatamente seguinte.
Observação importante (empática e prática): essa conclusão depende do pivot ser não-degenerado (\theta>0). Em pivôs degenerados (quando \theta=0) pode ocorrer que o novo custo reduzido fique igual a zero e, nesse caso, a variável que saiu pode eventualmente voltar à base na iteração seguinte. Por isso, a afirmação “não pode voltar” é válida no caso não-degenerado; no caso degenerado precisa-se de cuidado.
Resposta
Se a variável x_{B_\ell} sai da base por pivot não-degenerado (com d_\ell>0 e \theta=p_\ell/d_\ell>0) então, após o pivot, seu custo reduzido passa a ser \bar c'_\ell = -\dfrac{\bar c_e}{d_\ell}<0; consequentemente ela não pode voltar à base na iteração seguinte.