(1 ponto) Qual afirmação descreve o Teorema da Dualidade Fraca?
A. Soluções ótimas dos problemas primais e duais têm valores diferentes em suas respectivas funções objetivo.
B. O valor de função objetivo de uma solução do problema de minimização não pode ser menor do que o do problema de maximização.
C. Se um problema primal tem solução ótima, o problema dual também tem solução ótima.
D. Se duas soluções, uma para o primal e outra para o dual, tem mesmo valor de função objetivo, então elas são ótimas para seus respectivos problemas.
E. Nenhuma das anteriores.

Passo 1

O enunciado pede: escolher qual das alternativas descreve o Teorema da Dualidade Fraca. As alternativas apresentadas são:
A. Soluções ótimas dos problemas primais e duais têm valores diferentes em suas respectivas funções objetivo.
B. O valor de função objetivo de uma solução do problema de minimização não pode ser menor do que o do problema de maximização.
C. Se um problema primal tem solução ótima, o problema dual também tem solução ótima.
D. Se duas soluções, uma para o primal e outra para o dual, têm mesmo valor de função objetivo, então elas são ótimas para seus respectivos problemas.
E. Nenhuma das anteriores.
Listei aqui todas as informações relevantes (as cinco alternativas). A resolução vai mostrar o enunciado correto do Teorema da Dualidade Fraca e comparar com cada alternativa.

Passo 2

Vamos escrever de forma clara e precisa o enunciado usual da Dualidade Fraca para programação linear (na forma padrão de par primal-dual). Considere o par:
Primal (maximização)
\begin{aligned} \text{maximizar } & \; \; c^\top x\\\ \text{s.a. } & \; \; A x \le b,\\\ & \; \; x \ge 0, \end{aligned}
Dual (minimização)
\begin{aligned} \text{minimizar } & \; \; b^\top y\\\ \text{s.a. } & \; \; A^\top y \ge c,\\\ & \; \; y \ge 0. \end{aligned}
Aqui eu expliquei cada símbolo:
  • x é o vetor de variáveis do problema primal, com x\ge 0.
  • y é o vetor de variáveis do problema dual, com y\ge 0.
  • A é a matriz de coeficientes, b e c são vetores dados.
  • c^\top x e b^\top y são os valores das funções objetivo do primal e do dual, respectivamente.

Passo 3

Agora enuncio a Dualidade Fraca (forma matemática e intuitiva):
A Dualidade Fraca afirma que, para qualquer solução x factível do primal e qualquer solução y factível do dual, temos a desigualdade
c^\top x \le b^\top y.
Em palavras: o valor objetivo de qualquer solução factível do problema de maximização (primal) é no máximo o valor objetivo de qualquer solução factível do problema de minimização (dual). Essa desigualdade vale para quaisquer pares factíveis, não exige ótimalidade.

Passo 4

Prova curta e elementar dessa desigualdade (passo a passo, sem pular etapas):
  1. Da restrição dual \;A^\top y \ge c\; e do fato que x \ge 0, multiplica-se ambos os lados por x^\top (produto escalar) para obter:
x^\top A^\top y \ge x^\top c.
  1. Observe que x^\top A^\top y = (A x)^\top y = y^\top (A x). Portanto a desigualdade anterior vira
y^\top (A x) \ge c^\top x.
  1. Da restrição primal \;A x \le b\; e do fato que y \ge 0, multiplicando ambos os lados por y^\top (produto escalar) obtemos:
y^\top (A x) \le y^\top b = b^\top y.
  1. Juntando as desigualdades dos passos 2 e 3, temos
c^\top x \le y^\top (A x) \le b^\top y,
logo
c^\top x \le b^\top y,
que é exatamente a afirmação da Dualidade Fraca.
Explicando de forma intuitiva: a restrição dual dá que os coeficientes do primal são “menores ou iguais” a certos multiplicadores; multiplicando pelas variáveis não-negativas produz um limite inferior para y^\top (Ax), e as restrições do primal transformam y^\top (Ax) num valor menor ou igual a b^\top y. A cadeia mostra que qualquer valor factível do primal não ultrapassa qualquer valor factível do dual.

Passo 5

Uma consequência simples (corolário) da Dualidade Fraca é: se você encontrar uma solução factível x do primal e uma solução factível y do dual tais que
c^\top x = b^\top y,
então ambas são ótimas para seus respectivos problemas. Por quê? Porque pela Dualidade Fraca sempre temos c^\top x \le b^\top y; se houve igualdade, nenhum outro valor factível do primal pode ser maior que c^\top x (porque seria maior que b^\top y), e nenhum outro valor factível do dual pode ser menor que b^\top y. Portanto ambas alcançam o melhor possível — são ótimas. Isso mostra que a alternativa que diz que igualdade de valores implica optimalidade é verdadeira, mas note: isso é um corolário da Dualidade Fraca, não a formulação primária da desigualdade.

Passo 6

Agora vamos comparar cada alternativa com o enunciado e a prova acima:
  • A. “Soluções ótimas dos problemas primais e duais têm valores diferentes em suas respectivas funções objetivo.”
    • Isso é falso. A Dualidade Fraca não afirma que valores ótimos são diferentes; frequentemente, sob condições (p.ex. existência de soluções ótimas e condições de regularidade), os ótimos do primal e do dual coincidem (isso é Dualidade Forte). A alternativa A diz algo incorreto e incompatível com os teoremas usuais.
  • B. “O valor de função objetivo de uma solução do problema de minimização não pode ser menor do que o do problema de maximização.”
    • Tradução cuidadosa: se um problema é de minimização (o dual no nosso par) e o outro de maximização (o primal), então o valor da função objetivo de qualquer solução do minimização não pode ser menor do que (isto é, é sempre maior ou igual a) o valor de qualquer solução do maximização. Isso corresponde exatamente à desigualdade c^\top x \le b^\top y,que demonstrámos. Portanto esta alternativa descreve corretamente a Dualidade Fraca (é a forma verbal da desigualdade).
  • C. “Se um problema primal tem solução ótima, o problema dual também tem solução ótima.”
    • Isso não é garantido pela Dualidade Fraca. A existência de solução ótima em um lado não necessariamente implica existência do ótimo no outro; isso depende de condições adicionais (ex.: condições de viabilidade e fechamento, e às vezes a existência de soluções restritas). Portanto C é falso em geral.
  • D. “Se duas soluções, uma para o primal e outra para o dual, têm mesmo valor de função objetivo, então elas são ótimas para seus respectivos problemas.”
    • Isso é verdadeiro, mas (como expliquei no Passo 5) é um corolário da Dualidade Fraca: a igualdade entre valores factíveis implica optimalidade. A alternativa D não é a formulação básica do Teorema da Dualidade Fraca, mas sim uma consequência dele. Se a pergunta exige a descrição do teorema em si, a forma mais direta é a desigualdade (alternativa B); D é uma consequência equivalente em conteúdo prático, porém costuma ser apresentada como corolário.
  • E. “Nenhuma das anteriores.”
    • Visto que a alternativa B corresponde exatamente à enunciação padrão da Dualidade Fraca, E é falsa.

Passo 7

Resumo e fechamento didático (tipo amigo encorajador): a Dualidade Fraca é sobre uma desigualdade simples e poderosa que fornece um limite entre valores factíveis do primal e do dual. Na prova, quando te pedirem a Dualidade Fraca, lembre-se: é a mensagem “qualquer valor factível do max ≤ qualquer valor factível do min”. Se você controlar bem essa ideia, já resolve várias questões de prova sobre limites, testes de optimalidade e construções de contraexemplos. Vai dar certo — respira fundo e confia no raciocínio.

Resposta

B

Exercícios relacionados