Mostre que
para todo índice
de variável básica.
Dica: argumente que
implica
pois
é a r-ésima coluna de
.
Passo 1
O que o enunciado pede: mostrar que, para todo índice
que indica uma variável básica, vale
Informações fornecidas / contexto que vamos usar:
-
é a matriz das colunas básicas (matriz básica) e é invertível. -
é a coluna correspondente à variável ; assumimos que pertence às colunas de (pois é índice de variável básica). - A dica:
implica (ou, mais geralmente, se for a -ésima coluna de ). - Notação padrão do simplex (que usaremos): para qualquer índice
define-se e
onde
é o vetor dos coeficientes de custo das variáveis básicas. O objetivo é aplicar isso para
.
Passo 2
Explicando a definição de
e de
de forma clara e por que existem:
- A equação
significa: "procura-se um vetor tal que, multiplicando por , se obtenha a coluna ". Como é invertível, essa equação tem solução única e essa solução é
- O escalar
é o produto escalar entre o vetor de custos básicos e :
Esse
é o chamado “valor sombra” ou parte do cálculo do custo reduzido
.
Passo 3
Identificar a posição da coluna
dentro de
e usar a dica:
- Como
é índice de uma variável básica, a coluna aparece em . Suponha que seja a -ésima coluna de . (Isto é, se as colunas básicas são , então existe com .) - A
-ésima coluna de é precisamente . Portanto, ao multiplicar pelo vetor canônico (que tem na posição e zeros nas outras), obtemos a -ésima coluna de :
- Pela unicidade da solução de
temos então
(Se a convenção do enunciado fosse que
é exatamente a coluna
de
, então
e
; a argumentação é análoga.)
Passo 4
Calcular
usando
e relacioná-lo com
:
- Pela definição de
,
- O produto
seleciona a -ésima componente de , ou seja
- Por construção
é o coeficiente de custo da variável básica que ocupa a -ésima coluna de . Como essa variável é a variável (porque é a -ésima coluna), segue que
- Portanto
Passo 5
Concluir a igualdade pedida:
- Subtraindo
de ambos os lados obtemos
para todo índice
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.