Mosre que se
para todo índice
de variável não básica, então a solução básica viável correspondente é única.
Passo 1
O que o enunciado pede e o que nos dá.
- Pedido: provar que, se
para todo índice de variável não-básica, então a solução básica viável correspondente é única (isto é, não existe outra solução viável com o mesmo valor ótimo). - Informações dadas (assumidas padrão em problemas de PL em forma canônica):
- O problema considera um sistema linear
. - Há uma base
composta por colunas de ; os índices fora da base formam o conjunto (variáveis não-básicas). - A solução básica viável associada à base
será chamada de . - Para cada coluna
com define-se o custo reduzido , onde . - Hipótese do enunciado:
para todo .
- O problema considera um sistema linear
Passo 2
Definições e fórmula importante — escrever qualquer solução viável em função das variáveis não-básicas.
- Notações:
-
é a matriz formada pelas colunas básicas, os custos correspondentes às variáveis básicas. -
é a matriz das colunas não-básicas, e os custos dessas variáveis. - A solução básica viável corresponde a
e . Chamamos esse vetor por .
-
- Qualquer vetor
que satisfaça pode ser escrito separando componentes básicas e não-básicas: Portanto Isto é crucial: dado um que respeite as desigualdades que mantêm , obtemos uma solução viável.
Passo 3
Expressar a diferença de valores da função objetivo entre uma solução qualquer
e a solução básica
.
- A função objetivo (assumindo forma padrão de maximização com custos
) é . - Para a solução básica
com e , o valor objetivo é - Para uma solução geral
(com possivelmente não nulo),
substituindoobtemos Reagrupando termos,
Passo 4
Introduzir os custos reduzidos e reescrever a diferença do objetivo em função deles.
- Para cada
o custo reduzido é definido por onde é a coluna -ésima de . Em notação matricial para todas as não-básicas, - Usando essa definição, da expressão do passo anterior temos
Em forma de somatório, isto é
Passo 5
Usar a hipótese
e a não-negatividade das variáveis para concluir sobre unicidade.
- Pela hipótese, para todo
vale . - Para qualquer solução viável
temos para todo . - Portanto cada parcela
do somatório é menor ou igual a zero, e como , então é estritamente positivo sempre que . - Logo, da fórmula
segue que: - Se existir algum
com , então o somatório à direita é negativo e portanto . - A única maneira de ter
é que para todo . Mas implica, pela equação , que , isto é .
- Se existir algum
- Conclusão imediata: não existe solução viável
com o mesmo valor objetivo; qualquer outra solução viável tem valor objetivo estritamente menor.
Passo 6
Interpretação final e observação sobre bases degeneradas.
- O argumento acima mostra que a solução básica viável
é a única solução viável que atinge o máximo da função objetivo — portanto é única ótima. - Observação adicional (útil para provas/entendimento): se houver degenerescência (ou seja, algumas componentes básicas em
forem zero), pode haver mais de uma base que represente o mesmo vetor . Isso não contradiz a unicidade do vetor solução : o que provamos é que o vetor solução ótimo é único. Em outras palavras, pode haver várias bases que produzam a mesma solução degenerada, mas não existe outro vetor viável diferente de que seja ótimo.
Resposta
A solução básica viável correspondente é única.