(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.

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:
\text{(P)}\quad \max\{\,c^{T}x \mid Ax \le 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} são as variáveis. O dual associado é o problema de minimização
\text{(D)}\quad \min\{\,b^{T}y \mid A^{T}y \ge c,\; y \ge 0\,\},
onde y\in\mathbb{R}^{m} são as variáveis duais (também chamadas de preços sombra).
Explicação rápida das notações: c^{T}x é o produto escalar (valor objetivo), Ax\le b significa que cada componente da vetor Ax é menor ou igual ao correspondente em b, e x\ge0 significa cada componente de x é não-negativo.

Passo 3

Primeiro resultado útil: lema da dualidade fraca (weak duality). Ele diz: para qualquer x factível de § e qualquer y factível de (D) vale
c^{T}x \le b^{T}y.
Prova do lema (passo a passo, bem didático):
  • Se y é factível para (D) então A^{T}y \ge c. Como x\ge0, multiplicando termo a termo obtemos
x^{T}A^{T}y \ge x^{T}c,
ou seja
y^{T}Ax \ge c^{T}x.
  • Se x é factível para § então Ax \le b. Como y\ge0, multiplicando obtemos
y^{T}Ax \le y^{T}b = b^{T}y.
  • Juntando as duas desigualdades:
c^{T}x \le y^{T}Ax \le b^{T}y,
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 \pi_{P} é o valor ótimo do primal (o supremo dos c^{T}x factíveis) e \pi_{D} é o valor ótimo do dual (o ínfimo dos b^{T}y factíveis), então sempre temos
\pi_{P} \le \pi_{D}.
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 x^{*} factível com c^{T}x^{*}=\pi_{P} finito), então o dual também tem solução ótima e os valores coincidem ( \pi_{D}=\pi_{P}). 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 x^{*} (teorema básico de programação linear: se há uma solução ótima, há uma básica ótima). Suponha que x^{*} seja tal solução básica ótima. Seja B o conjunto de índices das variáveis básicas e N o conjunto das não-básicas; escrevendo A = [A_{B}\; A_{N}] e particionando x e c em (x_{B},x_{N}) e (c_{B},c_{N}), a solução básica tem x_{N}=0 e A_{B}x_{B}=b.
Defina o vetor y^{*} por
y^{*T} := c_{B}^{T}A_{B}^{-1}.
Explico isso: A_{B} é a submatriz de A formada pelas colunas básicas; como x^{*} é uma base válida, A_{B} é invertível. O vetor y^{*} é 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:
  1. y^{*} é 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
\bar{c}_{N}^{T} = c_{N}^{T} - c_{B}^{T}A_{B}^{-1}A_{N} = c_{N}^{T} - y^{*T}A_{N}.
A condição de optimalidade dá \bar{c}_{N} \le 0 (no nosso sinalado; dependendo da convenção de sinais pode aparecer \ge 0, a ideia é que nenhum movimento melhora o objetivo), o que reescrito implica A_{N}^{T}y^{*} \ge c_{N}. Para as colunas básicas a igualdade A_{B}^{T}y^{*}=c_{B} vale por construção. Assim juntando, obtemos A^{T}y^{*} \ge c, isto é, y^{*} satisfaz as restrições do dual. Também y^{*} tem a não-negatividade exigida quando essa é uma condição do dual (na forma apresentada, a condição y\ge0 aparece naturalmente quando o primal tem desigualdades do tipo \le).
  1. Igualdade de valores objetivos: calcule
b^{T}y^{*} = (A_{B}x_{B})^{T}y^{*} = x_{B}^{T}A_{B}^{T}y^{*}.
Como A_{B}^{T}y^{*}=c_{B} (pela definição de y^{*}), segue
b^{T}y^{*} = x_{B}^{T}c_{B} = c^{T}x^{*}.
Portanto o valor objetivo do dual em y^{*} coincide com o valor objetivo do primal em x^{*}.
Da verificação 1 e 2: y^{*} é factível para (D) e obtém exatamente b^{T}y^{*}=c^{T}x^{*}=\pi_{P}. Pelo lema da dualidade fraca sabemos que \pi_{P}\le\pi_{D}, e aqui encontramos y^{*} com valor igual a \pi_{P}, logo \pi_{D}=\pi_{P} 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 y^{*} 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.

Exercícios relacionados