(0.5 pontos) Se um PPL apresenta valor ótimo, então seu dual terá o mesmo valor ótimo.
Passo 1
O enunciado pede para julgar a afirmação: “Se um PPL apresenta valor ótimo, então seu dual terá o mesmo valor ótimo.”
Informações dadas: um PPL (problema de programação linear primal) tem um valor ótimo (isto é, existe uma solução ótima com valor objetivo finito). A tarefa é decidir se a afirmação é verdadeira ou falsa e justificar. Não há outras condições explícitas no enunciado.
Informações dadas: um PPL (problema de programação linear primal) tem um valor ótimo (isto é, existe uma solução ótima com valor objetivo finito). A tarefa é decidir se a afirmação é verdadeira ou falsa e justificar. Não há outras condições explícitas no enunciado.
Passo 2
Vamos explicar com calma o que são o primal e o dual, em uma forma padrão simples (a forma escolhida serve para explicar a ideia — a propriedade vale nas formas equivalentes). Considere o primal no formato de maximização:
onde
é uma matriz
,
,
e
são as variáveis. O dual associado é o problema de minimização
onde
são as variáveis duais (também chamadas de preços sombra).
Explicação rápida das notações: é o produto escalar (valor objetivo),
significa que cada componente da vetor
é menor ou igual ao correspondente em
, e
significa cada componente de
é não-negativo.
Explicação rápida das notações:
Passo 3
Primeiro resultado útil: lema da dualidade fraca (weak duality). Ele diz: para qualquer
factível de § e qualquer
factível de (D) vale
Prova do lema (passo a passo, bem didático):
- Se
é factível para (D) então . Como , multiplicando termo a termo obtemos
ou seja
- Se
é factível para § então . Como , multiplicando obtemos
- Juntando as duas desigualdades:
o que prova o lema. Intuição: qualquer valor objetivo admissível do primal não pode ultrapassar qualquer valor objetivo admissível do dual.
Passo 4
Consequência imediata do lema: se
é o valor ótimo do primal (o supremo dos
factíveis) e
é o valor ótimo do dual (o ínfimo dos
factíveis), então sempre temos
Isto é, o melhor que o primal alcança nunca excede o melhor que o dual alcança. Até aqui é uma desigualdade geral (fraca) que vale para quaisquer problemas lineares na forma indicada.
Passo 5
Agora precisamos justificar por que, se o primal tem valor ótimo finito (isto é, existe
factível com
finito), então o dual também tem solução ótima e os valores coincidem (
). Esta é a propriedade chamada dualidade forte (strong duality). Vou apresentar uma demonstração construtiva e intuitiva, baseada em resultados básicos do método simplex, porque é uma maneira concreta de ver que o dual realmente atinge o mesmo valor.
Passo construtivo (intuição via base ótima): para um problema linear factível e limitado, existe sempre uma solução básica factível ótima
(teorema básico de programação linear: se há uma solução ótima, há uma básica ótima). Suponha que
seja tal solução básica ótima. Seja
o conjunto de índices das variáveis básicas e
o conjunto das não-básicas; escrevendo
e particionando
e
em
e
, a solução básica tem
e
.
Defina o vetor
por
Explico isso:
é a submatriz de
formada pelas colunas básicas; como
é uma base válida,
é invertível. O vetor
é exatamente o vetor de multiplicadores (preços sombra) que o simplex fornece na tabela final — é uma construção linear direta a partir da base ótima.
Agora verificamos duas coisas essenciais:
-
é factível para (D): isto decorre do fato de que, na base ótima, os custos reduzidos das variáveis não-básicas são não-negativos (condição de otimalidade do simplex para maximização). Esses custos reduzidos são exatamente
A condição de optimalidade dá
(no nosso sinalado; dependendo da convenção de sinais pode aparecer
, a ideia é que nenhum movimento melhora o objetivo), o que reescrito implica
. Para as colunas básicas a igualdade
vale por construção. Assim juntando, obtemos
, isto é,
satisfaz as restrições do dual. Também
tem a não-negatividade exigida quando essa é uma condição do dual (na forma apresentada, a condição
aparece naturalmente quando o primal tem desigualdades do tipo
).
- Igualdade de valores objetivos: calcule
Como
(pela definição de
), segue
Portanto o valor objetivo do dual em
coincide com o valor objetivo do primal em
.
Da verificação 1 e 2:
é factível para (D) e obtém exatamente
. Pelo lema da dualidade fraca sabemos que
, e aqui encontramos
com valor igual a
, logo
e o dual alcança seu ótimo. Isso prova a dualidade forte no caso em que o primal tem uma solução ótima básica (e, como dito, sempre existe uma solução básica ótima quando há solução ótima).
Passo 6
Resumo e comentário prático: portanto, para problemas lineares bem formulados (como os apresentados aqui), se o primal tem um valor ótimo finito (isto é, existe solução ótima), então o dual também terá solução ótima e os valores ótimos coincidirão. Em linguagem amigável: existe sempre um vetor de preços sombra
que faz o valor do dual igualar o valor ótimo do primal. Essa é uma propriedade fundamental e muito útil em provas e aplicações (por exemplo para interpretar sensibilidade e obter o dual diretamente da tabela final do simplex).
Resposta
Verdadeiro.