(0.5 pontos) Se um problema primal de minimização tem solução ótima, o seu problema dual pode ter valor ótimo
.
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
".
Informações dadas (diretas do enunciado):
Informações dadas (diretas do enunciado):
- Temos um problema primal do tipo minimização que possui uma solução ótima (isto é, existe
factível com valor ótimo finito). - A questão é sobre o valor ótimo do problema dual associado: será que ele pode ser
?
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
. Ou seja, existe tal que (isso depende da forma do problema, mas a ideia é essa). - Quando dizemos que o problema dual tem valor ótimo
, queremos dizer que a função objetivo do dual é não limitada superiormente (o dual é problema de maximização), ou seja, seu supremo é (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
Considere o primal em forma padrão de minimização
onde
é uma matriz
,
,
e
é a variável.
O dual associado (problema de maximização) é
O dual associado (problema de maximização) é
onde
são as variáveis dual.
Aqui:
Aqui:
-
é o custo (objetivo) do primal. -
é o objetivo do dual. - A desigualdade
significa que cada componente de é menor ou igual à componente correspondente de .
Passo 4
Apresento agora o resultado fundamental que vamos usar: a desigualdade fraca (weak duality). Ela diz o seguinte: para qualquer
factível do primal e qualquer
factível do dual vale
Prova simples e elementar (passo a passo):
- Se
é factível do primal então . - Se
é factível do dual então . Como , multiplicando termo a termo obtemos . - Mas
. - Combinando,
.
Essa desigualdade vale para qualquer par factível. 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
. Então existe
factível tal que
. Pela desigualdade fraca, para todo
factível do dual temos
Logo o conjunto dos valores factíveis do dual está limitado superiormente por
. Portanto o supremo do objetivo do dual não pode ser
. 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
. - Um detalhe adicional útil: a desigualdade fraca mostrou só que o supremo do dual é ≤
. 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