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
x_{B_\ell} = p_\ell - d_\ell x_e - \sum_{j\in N,\;j\neq e} D_{\ell j}\, x_j,
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
z = z_0 + \bar c_e\, x_e + \sum_{j\in N,\;j\neq e} \bar c_j\, x_j,
com z_0=c_B^T p. Relembre: escolhemos e porque \bar c_e>0. Pelo teste da razão mínima escolhemos \ell tal que
\theta=\frac{p_\ell}{d_\ell}=\min\left\{\frac{p_i}{(D_e)_i} \mid (D_e)_i>0\right\},
portanto d_\ell>0 e p_\ell>0 (não degenerado) e \theta>0.

Passo 4

Substituição que mostra o novo custo reduzido da variável que saiu. Isolamos x_e na equação da linha \ell:
x_e = \frac{p_\ell - x_{B_\ell} - \sum_{j\in N,\;j\neq e} D_{\ell j}\, x_j}{d_\ell}.
Substituímos essa expressão em z:
\begin{aligned} z &= z_0 + \bar c_e\left(\frac{p_\ell - x_{B_\ell} - \sum_{j\neq e} D_{\ell j}\, x_j}{d_\ell}\right) + \sum_{j\neq e} \bar c_j\, x_j \\\ &= \underbrace{z_0 + \frac{\bar c_e p_\ell}{d_\ell}}_{\text{novo }z_0} \;+\; \left(-\frac{\bar c_e}{d_\ell}\right) x_{B_\ell} \;+\; \sum_{j\neq e}\left(\bar c_j - \frac{\bar c_e D_{\ell j}}{d_\ell}\right) x_j. \end{aligned}
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.

Exercícios relacionados