Mostre que z_{r}-c_{r}=0 para todo índice r de variável básica.
Dica: argumente que \mathbf{B} \mathbf{y}_{r}=\mathbf{a}_{r} implica \mathbf{y}_{r}=\mathbf{e}_{r} pois \mathbf{a}_{r} é a r-ésima coluna de \mathbf{B}.

Passo 1

O que o enunciado pede: mostrar que, para todo índice r que indica uma variável básica, vale
z_{r}-c_{r}=0.
Informações fornecidas / contexto que vamos usar:
  • \mathbf{B} é a matriz das colunas básicas (matriz básica) e é invertível.
  • \mathbf{a}_{r} é a coluna correspondente à variável r; assumimos que \mathbf{a}_{r} pertence às colunas de \mathbf{B} (pois r é índice de variável básica).
  • A dica: \mathbf{B}\mathbf{y}_{r}=\mathbf{a}_{r} implica \mathbf{y}_{r}=\mathbf{e}_{r} (ou, mais geralmente, \mathbf{y}_{r}=\mathbf{e}_{k} se \mathbf{a}_{r} for a k-ésima coluna de \mathbf{B}).
  • Notação padrão do simplex (que usaremos): para qualquer índice j define-se \mathbf{y}_{j}=\mathbf{B}^{-1}\mathbf{a}_{j} e
z_{j}= \mathbf{c}_{B}^{T}\mathbf{y}_{j},
onde \mathbf{c}_{B} é o vetor dos coeficientes de custo das variáveis básicas. O objetivo é aplicar isso para j=r.

Passo 2

Explicando a definição de \mathbf{y}_{j} e de z_{j} de forma clara e por que existem:
  • A equação \mathbf{B}\mathbf{y}_{j}=\mathbf{a}_{j} significa: "procura-se um vetor \mathbf{y}_{j} tal que, multiplicando \mathbf{B} por \mathbf{y}_{j}, se obtenha a coluna \mathbf{a}_{j}". Como \mathbf{B} é invertível, essa equação tem solução única e essa solução é
\mathbf{y}_{j}=\mathbf{B}^{-1}\mathbf{a}_{j}.
  • O escalar z_{j} é o produto escalar entre o vetor de custos básicos \mathbf{c}_{B} e \mathbf{y}_{j}:
z_{j}= \mathbf{c}_{B}^{T}\mathbf{y}_{j} = \mathbf{c}_{B}^{T}\mathbf{B}^{-1}\mathbf{a}_{j}.
Esse z_{j} é o chamado “valor sombra” ou parte do cálculo do custo reduzido z_j-c_j.

Passo 3

Identificar a posição da coluna \mathbf{a}_{r} dentro de \mathbf{B} e usar a dica:
  • Como r é índice de uma variável básica, a coluna \mathbf{a}_{r} aparece em \mathbf{B}. Suponha que \mathbf{a}_{r} seja a k-ésima coluna de \mathbf{B}. (Isto é, se as colunas básicas são \mathbf{a}_{b_{1}},\dots,\mathbf{a}_{b_{m}}, então existe k com b_{k}=r.)
  • A k-ésima coluna de \mathbf{B} é precisamente \mathbf{a}_{r}. Portanto, ao multiplicar \mathbf{B} pelo vetor canônico \mathbf{e}_{k} (que tem 1 na posição k e zeros nas outras), obtemos a k-ésima coluna de \mathbf{B}:
\mathbf{B}\mathbf{e}_{k}=\mathbf{a}_{r}.
  • Pela unicidade da solução de \mathbf{B}\mathbf{y}_{r}=\mathbf{a}_{r} temos então
\mathbf{y}_{r}=\mathbf{e}_{k}.
(Se a convenção do enunciado fosse que \mathbf{a}_{r} é exatamente a coluna r de \mathbf{B}, então k=r e \mathbf{y}_{r}=\mathbf{e}_{r}; a argumentação é análoga.)

Passo 4

Calcular z_{r} usando \mathbf{y}_{r}=\mathbf{e}_{k} e relacioná-lo com c_{r}:
  • Pela definição de z_{r},
z_{r}= \mathbf{c}_{B}^{T}\mathbf{y}_{r}=\mathbf{c}_{B}^{T}\mathbf{e}_{k}.
  • O produto \mathbf{c}_{B}^{T}\mathbf{e}_{k} seleciona a k-ésima componente de \mathbf{c}_{B}, ou seja
\mathbf{c}_{B}^{T}\mathbf{e}_{k}=(\mathbf{c}_{B})_{k}.
  • Por construção (\mathbf{c}_{B})_{k} é o coeficiente de custo da variável básica que ocupa a k-ésima coluna de \mathbf{B}. Como essa variável é a variável r (porque \mathbf{a}_{r} é a k-ésima coluna), segue que
(\mathbf{c}_{B})_{k}=c_{r}.
  • Portanto
z_{r}=c_{r}.

Passo 5

Concluir a igualdade pedida:
  • Subtraindo c_{r} de ambos os lados obtemos
z_{r}-c_{r}=0,
para todo índice r de variável básica.
Breve comentário intuitivo: isto diz que o custo reduzido de uma variável que já está na base é zero — é exatamente a ideia de que a base atual já incorpora o custo dessa variável, então não há “melhora” imediata ao aumentar sua variável básica.

Resposta

z_{r}-c_{r}=0

Exercícios relacionados