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?

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:
\text{Primal (P):}\qquad \min_{x\ge 0} \; c^{T}x \quad\text{s.a.}\quad A x \ge b,
e o Problema Dual associado é um problema de maximização:
\text{Dual (D):}\qquad \max_{y\ge 0} \; b^{T}y \quad\text{s.a.}\quad A^{T}y \le c.
Aqui expliquei o que cada símbolo significa:
  • x é o vetor de variáveis do primal (com x\ge 0 coordenada a coordenada).
  • y é o vetor de variáveis do dual (com y\ge 0).
  • A é a matriz de coeficientes, b e c são vetores dados.
  • c^{T}x é o valor objetivo do primal; b^{T}y é 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 x é factível para § e y é factível para (D), então vale a desigualdade
b^{T}y \le c^{T}x.
Prova elementar (passo a passo):
  1. Como x é factível em §, tem A x \ge b.
  2. Como y\ge 0, multiplicando pelo vetor y^{T} obtém-se
y^{T}A x \ge y^{T} b,
ou seja
x^{T}A^{T}y \ge b^{T}y.
  1. Como y é factível para (D), tem A^{T}y \le c.
  2. Como x\ge 0, multiplicando pelo vetor x^{T} obtém-se
x^{T}A^{T}y \le x^{T}c = c^{T}x.
  1. Combinando as duas desigualdades envolvendo x^{T}A^{T}y obtemos
b^{T}y \le x^{T}A^{T}y \le c^{T}x,
logo
b^{T}y \le c^{T}x,
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 x^{\star} uma solução factível do primal (portanto c^{T}x^{\star} é um número finito fixo). Como o Dual é factível por hipótese, existem vetores y factíveis. Pela fraca dualidade, para todo y factível vale
b^{T}y \le c^{T}x^{\star}.
Isto impõe um limite superior fixo para os valores b^{T}y possíveis sobre o conjunto factível do Dual: nenhum b^{T}y pode exceder c^{T}x^{\star}. 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 b^{T}y factíveis deveriam satisfazer b^{T}y \le c^{T}x^{\star}. 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.

Exercícios relacionados