(0.5 pontos) Se um problema primal de minimização tem solução ótima, o seu problema dual pode ter valor ótimo +\infty.

Passo 1

O enunciado pergunta se a seguinte afirmativa pode acontecer: "Se um problema primal de minimização tem solução ótima, o seu problema dual pode ter valor ótimo +\infty".
Informações dadas (diretas do enunciado):
  • Temos um problema primal do tipo minimização que possui uma solução ótima (isto é, existe x^* factível com valor ótimo finito).
  • A questão é sobre o valor ótimo do problema dual associado: será que ele pode ser +\infty?

Passo 2

Vamos esclarecer os termos que aparecem para evitar confusão:
  • Uma solução factível é um ponto que satisfaz todas as restrições do problema.
  • Uma solução ótima é uma solução factível que minimiza (no primal) o valor objetivo; o valor ótimo primal será um número finito, denotemos por p^*. Ou seja, existe x^* tal que p^* = c^\top x^* (isso depende da forma do problema, mas a ideia é essa).
  • Quando dizemos que o problema dual tem valor ótimo +\infty, queremos dizer que a função objetivo do dual é não limitada superiormente (o dual é problema de maximização), ou seja, seu supremo é +\infty (o dual está “ilimitado” para cima).

Passo 3

Vou escrever o par primal–dual em uma forma padrão e explicar cada símbolo (isso ajuda a provar a afirmação):
Considere o primal em forma padrão de minimização
\text{minimizar } c^\top x \quad \text{sujeito a } Ax=b,\; x\ge 0,
onde A é uma matriz m\times n, b\in\mathbb{R}^m, c\in\mathbb{R}^n e x\in\mathbb{R}^n é a variável.
O dual associado (problema de maximização) é
\text{maximizar } b^\top y \quad \text{sujeito a } A^\top y \le c,
onde y\in\mathbb{R}^m são as variáveis dual.
Aqui:
  • c^\top x é o custo (objetivo) do primal.
  • b^\top y é o objetivo do dual.
  • A desigualdade A^\top y \le c significa que cada componente de A^\top y é menor ou igual à componente correspondente de c.

Passo 4

Apresento agora o resultado fundamental que vamos usar: a desigualdade fraca (weak duality). Ela diz o seguinte: para qualquer x factível do primal e qualquer y factível do dual vale
b^\top y \le c^\top x.
Prova simples e elementar (passo a passo):
  1. Se x é factível do primal então Ax=b.
  2. Se y é factível do dual então A^\top y \le c. Como x\ge 0, multiplicando termo a termo obtemos x^\top A^\top y \le x^\top c.
  3. Mas x^\top A^\top y = (Ax)^\top y = b^\top y.
  4. Combinando, b^\top y \le x^\top c = c^\top x.
    Essa desigualdade vale para qualquer par factível (x,y). Em palavras: qualquer valor admissível do dual não pode ultrapassar qualquer valor admissível do primal.

Passo 5

Agora usemos a desigualdade fraca para responder à pergunta: suponha que o primal tem solução ótima e finita, com valor ótimo denotado p^*. Então existe x^* factível tal que c^\top x^* = p^*. Pela desigualdade fraca, para todo y factível do dual temos
b^\top y \le c^\top x^* = p^*.
Logo o conjunto dos valores factíveis do dual está limitado superiormente por p^*. Portanto o supremo do objetivo do dual não pode ser +\infty. Em outras palavras, o dual não pode ser ilimitado para cima quando o primal tem valor ótimo finito.

Passo 6

Observações finais (úteis na prova):
  • Conclusão direta: a afirmação do enunciado é falsa. Se o primal de minimização tem solução ótima finita, o dual não pode ter valor ótimo +\infty.
  • Um detalhe adicional útil: a desigualdade fraca mostrou só que o supremo do dual é ≤ p^*. Em problemas lineares, existe ainda o teorema da dualidade forte que afirma, sob condições que se cumprem na forma padrão, que se um dos problemas tem solução ótima finita então o outro também tem e os valores ótimos coincidem (isto mostra ainda mais que o dual tem valor finito e igual ao primal). Mas para responder a esta questão bastou usar a desigualdade fraca.
  • Não se desanime: lembrar e saber aplicar a desigualdade fraca é uma arma poderosa em provas; ela costuma resolver vários problemas de dualidade direto e rápido.

Resposta

Falso

Exercícios relacionados