(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.
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)
Dual (minimização)
Aqui eu expliquei cada símbolo:
-
é o vetor de variáveis do problema primal, com . -
é o vetor de variáveis do problema dual, com . -
é a matriz de coeficientes, e são vetores dados. -
e 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
factível do primal e qualquer solução
factível do dual, temos a desigualdade
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):
- Da restrição dual
e do fato que , multiplica-se ambos os lados por (produto escalar) para obter:
- Observe que
. Portanto a desigualdade anterior vira
- Da restrição primal
e do fato que , multiplicando ambos os lados por (produto escalar) obtemos:
- Juntando as desigualdades dos passos 2 e 3, temos
logo
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
, e as restrições do primal transformam
num valor menor ou igual a
. 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
do primal e uma solução factível
do dual tais que
então ambas são ótimas para seus respectivos problemas. Por quê? Porque pela Dualidade Fraca sempre temos
; se houve igualdade, nenhum outro valor factível do primal pode ser maior que
(porque seria maior que
), e nenhum outro valor factível do dual pode ser menor que
. 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
que demonstrámos. Portanto esta alternativa descreve corretamente a Dualidade Fraca (é a forma verbal da desigualdade).
- 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. “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