A respeito das relações entre o Problema Primal e o Problema Dual, responda:
Supondo que o Problema Primal seja factível e tenha solução finita, o que se pode afirmar sobre o Problema Dual?

Passo 1

O enunciado dá duas informações claras:
  • O Problema Primal é factível (existe pelo menos uma solução que satisfaz as restrições).
  • O Problema Primal tem solução ótima finita (existe x^* factível tal que o valor objetivo atinge um máximo/minimo finito).
A pergunta é: o que se pode afirmar sobre o Problema Dual a partir disso?

Passo 2

Para ficar tudo concreto, vou escrever uma forma canónica (uma forma muito comum) do par Primal–Dual. Eu uso o Primal no formato de maximização porque aí a desigualdade entre objetivos fica bem intuitiva; se o teu curso usar outro formato a ideia é análoga.
Primal § — forma canónica de maximização:
\begin{aligned} \text{maximizar}\quad & c^{T}x\\\ \text{sujeito a}\quad & Ax \le b,\\\ & x \ge 0. \end{aligned}
Dual (D) correspondente — forma de minimização:
\begin{aligned} \text{minimizar}\quad & b^{T}y\\\ \text{sujeito a}\quad & A^{T}y \ge c,\\\ & y \ge 0. \end{aligned}
Aqui:
  • x é o vetor de variáveis do Primal, c são os coeficientes do objetivo primal.
  • y é o vetor de variáveis do Dual, b são os termos do lado direito do Primal.
  • A é a matriz de coeficientes das restrições.
Se o teu Primal estiver escrito de outra forma (minimização, desigualdades \ge, variáveis livres etc.), existem regras simples para transformar e obter o Dual — mas a ideia de dualidade é a mesma.

Passo 3

Vou ensinar um resultado muito importante e simples primeiro: a desigualdade fraca (weak duality). Ela dá uma relação que vale para qualquer solução factível do Primal e qualquer solução factível do Dual.
Teorema da dualidade fraca:
Se x é factível para § e y é factível para (D), então
c^{T}x \le b^{T}y.
Prova curta e didática:
  • Como y é factível em (D), vale A^{T}y \ge c. Tomando produto escalar com x \ge 0 obtém-se x^{T}A^{T}y \ge x^{T}c.
  • Mas x^{T}A^{T}y = (Ax)^{T}y. Como x é factível em §, vale Ax \le b e y \ge 0. Multiplicando termo a termo dá (Ax)^{T}y \le b^{T}y.
  • Compondo as desigualdades:
c^{T}x \le (Ax)^{T}y \le b^{T}y,
logo c^{T}x \le b^{T}y.
Interpretação prática: qualquer valor objetivo admissível do Primal é menor ou igual a qualquer valor objetivo admissível do Dual. Em termos de otimização, o Dual fornece um limite superior para problemas de maximização (ou um limite inferior no caso do Primal ser minimização — tudo depende do formato).

Passo 4

Agora uso a dualidade fraca para entender a consequência do fato “Primal factível e tem solução ótima finita”.
Seja p^{*} o valor ótimo do Primal, isto é p^{*} = \max\{c^{T}x \mid x \text{ factível}\}í e p^{*} é finito por hipótese.
Pela dualidade fraca, para todo y factível do Dual vale b^{T}y \ge c^{T}x para todo x factível. Em particular, para x que atinge o ótimo x^{*} obtemos b^{T}y \ge p^{*} para todo y factível. Isso diz que qualquer solução factível do Dual fornece um valor objetivo maior ou igual a p^{*}.
Agora precisamos da conclusão que o enunciado pede: que pode-se afirmar sobre o Dual? A resposta forte é o teorema da dualidade forte:
Teorema da dualidade forte (para programação linear):
Se o Primal é factível e tem valor ótimo finito p^{*}, então o Dual é factível e tem solução ótima; além disso os valores ótimos coincidem:
p^{*} = d^{*},
onde d^{*} é o valor ótimo do Dual.
Ou seja: existe pelo menos um y^{*} factível para o Dual tal que b^{T}y^{*} = p^{*}. Em palavras: o Dual também tem solução ótima e o valor ótimo do Dual é exatamente o mesmo que o do Primal.

Passo 5

Vou dar uma intuição/prova-mascara para essa afirmação (não exageradamente técnica, mas concreta): quando o Primal tem solução ótima finita e é factível, o método do Simplex (ou argumentos via o lema de Farkas/separação) produz uma base ótima. Dessa base ótima extraem-se os chamados multiplicadores (ou preços sombra) que são exatamente as variáveis y do Dual. Esses multiplicadores verificam A^{T}y \ge c e fazem com que b^{T}y = c^{T}x^{*}. Logo esses y são factíveis no Dual e atingem o mesmo valor, provando que o Dual é factível e ótimo.
Se preferires uma justificativa abstrata: a existência de solução ótima finita para um PL garante que não há incongruência entre as restrições, e a teoria dos teoremas da alternativa (como Farkas) assegura a existência do vetor dual que certifica otimalidade.

Passo 6

Complementarmente: a condição de otimalidade pode ser verificada por Complementaridade (Complementary Slackness). Para o par §/(D) acima, x^{*} e y^{*} são ótimos simultaneamente sse
y_{i}^{*}\bigl(b_{i} - (Ax^{*})_{i}\bigr)=0\quad\text{para todo }i
e
x_{j}^{*}\bigl((A^{T}y^{*})_{j} - c_{j}\bigr)=0\quad\text{para todo }j.
Isto dá uma forma prática de checar que uma solução primal e uma solução dual são ótimas uma à outra.

Passo 7

Observação útil para provas/exames e para não se confundir:
  • Se o Primal for factível mas o ótimo for \pm\infty (isto é, não finito), então o Dual pode ser infactível. Ex.: Primal ilimitado → Dual sem factibilidade.
  • Mas no caso que o enunciado dá (Primal factível e com solução finita), a conclusão é segura: o Dual é factível e tem solução ótima, com valores ótimos iguais.
Força aí — essa é uma das propriedades mais práticas da programação linear: quando o Primal tem solução ótima finita, o Dual dá exatamente o mesmo número ótimo e existe um y^{*} que atesta isso.

Resposta

O Problema Dual é factível e tem solução ótima; os valores ótimos coincidem, isto é p^{*}=d^{*}.

Exercícios relacionados