Mosre que se z_{j}-c_{j}<0 para todo índice j 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 \;z_j-c_j<0\; para todo índice j 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 A x = b,\; x\ge 0.
    • Há uma base B composta por colunas de A; os índices fora da base formam o conjunto N (variáveis não-básicas).
    • A solução básica viável associada à base B será chamada de x^*.
    • Para cada coluna a_j com j\in N define-se o custo reduzido z_j-c_j, onde z_j = c_B^{T} B^{-1} a_j.
    • Hipótese do enunciado: \;z_j-c_j<0\; para todo j\in N.

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:
    • B é a matriz formada pelas colunas básicas, c_B os custos correspondentes às variáveis básicas.
    • N é a matriz das colunas não-básicas, e c_N os custos dessas variáveis.
    • A solução básica viável corresponde a \;x_N^*=0\; e \;x_B^* = B^{-1}b\;. Chamamos esse vetor por x^*.
  • Qualquer vetor x que satisfaça A x = b pode ser escrito separando componentes básicas e não-básicas: x = \begin{pmatrix} x_B \\\ x_N \end{pmatrix}, \qquad B x_B + N x_N = b.Portanto x_B = B^{-1} b - B^{-1} N x_N.Isto é crucial: dado um x_N\ge 0 que respeite as desigualdades que mantêm x_B\ge 0, obtemos uma solução viável.

Passo 3

Expressar a diferença de valores da função objetivo entre uma solução qualquer x e a solução básica x^*.
  • A função objetivo (assumindo forma padrão de maximização com custos c) é c^{T}x = c_B^{T}x_B + c_N^{T}x_N.
  • Para a solução básica x^* com x_N^*=0 e x_B^*=B^{-1}b, o valor objetivo é c^{T}x^* = c_B^{T} B^{-1} b.
  • Para uma solução geral x (com x_N possivelmente não nulo),
    substituindo x_B = B^{-1}b - B^{-1}N x_N obtemos c^{T}x = c_B^{T}\bigl(B^{-1}b - B^{-1}N x_N\bigr) + c_N^{T}x_N.Reagrupando termos, c^{T}x - c^{T}x^* = -\,c_B^{T}B^{-1}N\,x_N + c_N^{T}x_N.

Passo 4

Introduzir os custos reduzidos e reescrever a diferença do objetivo em função deles.
  • Para cada j\in N o custo reduzido é definido por z_j - c_j = c_B^{T}B^{-1}a_j - c_j,onde a_j é a coluna j-ésima de A. Em notação matricial para todas as não-básicas, z_N - c_N = c_B^{T}B^{-1}N - c_N^{T}\,.
  • Usando essa definição, da expressão do passo anterior temos c^{T}x - c^{T}x^* = -\bigl(c_B^{T}B^{-1}N - c_N^{T}\bigr)x_N = -\bigl(z_N - c_N\bigr)^{T} x_N.Em forma de somatório, isto é c^{T}x - c^{T}x^* = -\sum_{j\in N} (z_j - c_j)\, x_j.

Passo 5

Usar a hipótese \;z_j-c_j<0\; e a não-negatividade das variáveis para concluir sobre unicidade.
  • Pela hipótese, para todo j\in N vale \;z_j-c_j<0.
  • Para qualquer solução viável x temos x_j\ge 0 para todo j\in N.
  • Portanto cada parcela (z_j-c_j)\,x_j do somatório é menor ou igual a zero, e como (z_j-c_j)<0, então -(z_j-c_j)x_j é estritamente positivo sempre que x_j>0.
  • Logo, da fórmula c^{T}x - c^{T}x^* = -\sum_{j\in N} (z_j - c_j)\, x_j,segue que:
    • Se existir algum j\in N com x_j>0, então o somatório à direita é negativo e portanto c^{T}x < c^{T}x^*.
    • A única maneira de ter c^{T}x = c^{T}x^* é que x_j=0 para todo j\in N. Mas x_j=0\;\forall j\in N implica, pela equação x_B = B^{-1}b - B^{-1}N x_N, que x_B = B^{-1}b, isto é x = x^*.
  • Conclusão imediata: não existe solução viável x\neq x^* 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 x^* é 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 x^* forem zero), pode haver mais de uma base B que represente o mesmo vetor x^*. Isso não contradiz a unicidade do vetor solução x^*: 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 x^* que seja ótimo.

Resposta

A solução básica viável correspondente é única.

Exercícios relacionados