A respeito das relações entre o Problema Primal e o Problema Dual, responda:
Supondo que o Problema Dual seja factível e sua solução seja ilimitada, o que se pode afirmar sobre o Problema Primal?
Supondo que o Problema Dual seja factível e sua solução seja ilimitada, o que se pode afirmar sobre o Problema Primal?
Passo 1
O enunciado dá estas informações e pede uma conclusão:
- Dado: o Problema Dual é factível (existe pelo menos uma solução dual factível).
- Dado: a solução do Problema Dual é ilimitada (isto é, o valor objetivo do Dual pode ser levado arbitrariamente na direção da otimização — por exemplo, arbitrariamente grande se o Dual for um problema de maximização, ou arbitrariamente pequeno se for de minimização).
- Pergunta: o que se pode afirmar sobre o Problema Primal?
Passo 2
Vou colocar formas padrão para trabalhar com desigualdades de forma clara (isso não limita o resultado — o argumento vale para qualquer par primal/dual com a orientação apropriada, basta acompanhar o sentido da otimização).
Escolho a forma em que o Problema Primal é um problema de minimização:
e o Problema Dual associado é um problema de maximização:
Aqui expliquei o que cada símbolo significa:
-
é o vetor de variáveis do primal (com coordenada a coordenada). -
é o vetor de variáveis do dual (com ). -
é a matriz de coeficientes, e são vetores dados. -
é o valor objetivo do primal; é o valor objetivo do dual.
Passo 3
Apresento a desigualdade de fraca dualidade (weak duality) e mostro-a passo a passo — é a ferramenta chave.
Se
é factível para § e
é factível para (D), então vale a desigualdade
Prova elementar (passo a passo):
- Como
é factível em §, tem . - Como
, multiplicando pelo vetor obtém-se
ou seja
- Como
é factível para (D), tem . - Como
, multiplicando pelo vetor obtém-se
- Combinando as duas desigualdades envolvendo
obtemos
logo
que era o que queríamos. Esta é a fraca dualidade: para qualquer par factível, o valor do Dual nunca ultrapassa o valor do Primal (na orientação escolhida).
Passo 4
Agora aplico essa desigualdade ao caso dado (Dual factível e ilimitado) por contradição.
Suponha, para obter contradição, que o Problema Primal seja factível; seja
uma solução factível do primal (portanto
é um número finito fixo). Como o Dual é factível por hipótese, existem vetores
factíveis. Pela fraca dualidade, para todo
factível vale
Isto impõe um limite superior fixo para os valores
possíveis sobre o conjunto factível do Dual: nenhum
pode exceder
. Em particular, o conjunto de valores objetivos do Dual seria limitado acima.
Mas a hipótese diz que o Dual é ilimitado na sua direção de otimização (no nosso molde o Dual é de maximização e seu valor pode crescer arbitrariamente). Isso contradiz o fato que todos os
factíveis deveriam satisfazer
. Portanto a suposição de que o Primal é factível é impossível.
Conclusão lógica: o Problema Primal não pode ser factível. Em outras palavras, o Primal é inviável.
Passo 5
Observação útil e rápida: se em vez da forma escolhida o par primal/dual tiver as orientações trocadas (por exemplo primal é maximização e dual minimização), o raciocínio é análogo — basta aplicar a fraca dualidade na forma correspondente. A conclusão geral válida em qualquer formulação padrão é: “se o Dual é factível e seu valor objetivo é ilimitado na direção da otimização, então o Primal é inviável.”
Resposta
O problema primal é inviável.