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?
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
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:
Dual (D) correspondente — forma de minimização:
Aqui:
-
é o vetor de variáveis do Primal, são os coeficientes do objetivo primal. -
é o vetor de variáveis do Dual, são os termos do lado direito do Primal. -
é a matriz de coeficientes das restrições.
Se o teu Primal estiver escrito de outra forma (minimização, desigualdades
, 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 é factível para § e
é factível para (D), então
Se
Prova curta e didática:
- Como
é factível em (D), vale . Tomando produto escalar com obtém-se . - Mas
. Como é factível em §, vale e . Multiplicando termo a termo dá . - Compondo as desigualdades:
logo
.
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
o valor ótimo do Primal, isto é
e
é finito por hipótese.
Pela dualidade fraca, para todo
factível do Dual vale
para todo
factível. Em particular, para
que atinge o ótimo
obtemos
para todo
factível. Isso diz que qualquer solução factível do Dual fornece um valor objetivo maior ou igual a
.
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 , então o Dual é factível e tem solução ótima; além disso os valores ótimos coincidem:
Se o Primal é factível e tem valor ótimo finito
onde
é o valor ótimo do Dual.
Ou seja: existe pelo menos um
factível para o Dual tal que
. 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
do Dual. Esses multiplicadores verificam
e fazem com que
. Logo esses
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,
e
são ótimos simultaneamente sse
e
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
(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
que atesta isso.
Resposta
O Problema Dual é factível e tem solução ótima; os valores ótimos coincidem, isto é
.