Aula Dualidade

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Programação Linear
Dualidade
 
Dualidade
Já vimos em sala que para cada PPL existe um outro PL 
chamado dual, que consiste em modelar um problema que 
utiliza os mesmos dados que o original, mas alterando a 
função objetivo, ou seja, o foco.
Para facilitar a compreensão, vimos como exemplo o problema 
da dieta, que após modelado ficava no formato a seguir:
 
Dualidade
Para esse mesmo PPL, mudando o foco da narrativa, 
conseguimos obter a formulação do seu problema dual:
 max bT w
 s.a AT w ≤ c
 w ≥ 0
(*) Observe que o vetor de variáveis duais pode ter várias 
representações (letras) diferentes dependendo do livro onde 
estejam olhando; a única coisa importante é que as variáveis 
duais são DIFERENTES das variáveis primais; assim, não é 
recomendável utilizar a letra 'x' para representar.
 
Dualidade
O par de problemas primal-dual nesse formato é conhecido como “forma 
canônica”:
Primal: Dual:
min cT x max bT w
s.a A x ≥ b s.a AT w ≤ c
 x ≥ 0 w ≥ 0
Independente do formado dos PPLs, as observações abaixo são válidas:
* O número de variáveis de um PPL é igual ao número de restrições do outro 
PPL.
* Se um PPL é min o outro é max (e vice-versa)
* O tipo de restrição de um PPL influencia no tipo de variável do outro PPL.
* O tipo de variável de um PPL influencia no tipo de restrição do outro PPL.
* Se um PPL tem A como matriz nas restrições, o outro tem a matriz AT
* Entre o primal e o dual, os vetores b e c trocam de posição.
 
Exemplo
Primal:
Dual:
 
Forma padrão da dualidade
Para qualquer formato de PPL é possível escrever o dual. Para 
isso, basta pegar o primal, colocar no formato de 
minimização com restrições de “maior ou igual”, e escrever o 
dual conforme o slide anterior.
Por exemplo, o para de problemas primal dual abaixo está no 
formato “padrão”:
Primal: Dual:
min cT x max bT w
s.a A x = b s.a AT w ≤ c
 x ≥ 0 w irrestrito
 
Exemplo
Primal:
Dual:
 
Dualidade
Para facilitar, é possível utilizar a tabela abaixo que ajuda a 
escrever o dual de acordo com as características (tipos de 
restrições e tipos de variáveis) do primal.
 
Dupla dualidade
Os PPLs primal-dual possuem propriedades que os relacionam; 
a primeira propriedade é o lema abaixo, facilmente verificável 
(basta tomar um PPL original, escrever seu dual (D) e depois 
escrever o dual de (D), retornando ao PPL original).
LEMA
● O dual do dual é o primal
● O primal do primal é o dual
 
Teorema Fraco de Dualidade
TEOREMA FRACO DE DUALIDADE
Considere o par de problemas primal-dual na forma canônica. Se x é
um ponto viável para o problema primal e w é viável para o problema
viável, então:
Dem.
Como x é viável-primal e w é viável-dual, temos
e
 
Juntando as duas desigualdades
O que encerra a demonstração.
 
Teorema Fraco de Dualidade
O teorema fraco vale para qualquer par de problemas primal-
dual, desde que o primal seja de minimização. 
Ou seja, se temos um ponto viável no primal e um ponto viável 
no dual, podemos comparar as imagens e assegurar que a 
imagem do dual é SEMPRE menor ou igual que a imagem 
do primal.
 
Teorema Fraco de Dualidade
COROLÁRIO - TEOREMA FRACO DE DUALIDADE
Se x é um ponto viável para o primal e w é viável para o dual, 
tais que as imagens coincidam:
Então x é solução do primal e w é solução do dual.
Dem.
Seja x* SBV-primal e w* SBV-dual tais que bTw* = cTx*.
Sabemos, do teorema, que: bTw ≤ cTx*, para todo w. Assim
 bTw ≤ cTx* = bTw*
E portanto a imagem de w* é a maior possível no PPL dual 
 w* é ótimo dual
Sabemos, do teorema, que: bTw* ≤ cTx, para todo x. Assim
 cTx* = bTw* ≤ cTx
E portanto a imagem de x* é a menor possível no PPL primal 
 x* é ótimo primal
 
Teorema Forte de Dualidade
Vimos que se as imagens são iguais, então temos as soluções 
primal-dual. Mas o contrário da afirmação também é verdade?
TEOREMA
Se o primal tem pelo menos uma SBV ótima x*, então o respectivo 
dual também tem pelo menos uma SBV ótima w*, e os 
correspondentes valores ótimos (imagens) coincidem. 
Dem.
Considere o PL primal escrito na forma padrão.
Se x* é uma SBV ótima do primal, então
Como ela é ótima, sabemos que todos os custos reduzidos são
menores ou iguais a zero
 
Teorema Forte de Dualidade
Denotando por , temos 
Onde aj são as colunas da matriz A. Como a desigualdade 
acima é válida para todas as colunas, então:
E portanto, verificamos que w* é ponto viável dual.
 
Teorema Forte de Dualidade
Observe também que
Ou seja, x* tem a mesma imagem que w*.
Pelo corolário, sabemos então que w* é solução ótima dual.
 
Teorema Forte de Dualidade
Ou seja, o que esse Teorema nos diz é que, se temos uma SBV 
ótima de um dos problemas (x*), podemos garantir que o 
outro PPL também tem pelo menos uma solução, dada por 
w*:
Ou seja, além de garantir que o outro PPL também tem 
solução, podemos exibir uma solução usando cB e B.
Isso nos indica que o número de bases ótimas é igual no dual e 
no primal. 
 
Teorema Fund. de Dualidade
Obs: No teorema abaixo, dizemos que um PPL “tem valor ótimo 
finito” se a imagem não tende a “menos infinito” (no caso de 
minimização) ou “mais infinito” (no caso de maximização). 
Ou seja, um PPL tem valor ótimo finito se existe pelo menos 
uma SBV ótima.
TEOREMA
(1) Um PPL tem valor ótimo finito se existem soluções viáveis 
para os problemas primal-dual.
(2) Se algum dos problemas não tem ótimo finito, então o outro 
não possui soluções viáveis.
Dem. (1) Sabemos que bTw ≤ cTx para quaisquer pontos x (viável 
primal) e w (viável dual). Em particular, para a solução x* do 
primal bTw ≤ cTx*
E portanto a imagem de x* é limitada inferiormente, e não pode 
tender a “menos infinito”.
 
Teorema Fund. de Dualidade
Dem. (1) 
Analogamente:
Sabemos que bTw ≤ cTx para quaisquer pontos x (viável primal) 
e w (viável dual). Em particular, para a solução w* do dual 
 bTw* ≤ cTx
E portanto a imagem de w* é limitada superiormente, e não 
pode tender a “mais infinito”.
Obs: 
* Se um PPL tem ponto viável, a solução do outro não tende a 
“menos infinito”.
* Se um PPLtem solução “ilimitada”, então o outro PPL não tem 
ponto viável.
 
Teorema Fund. de Dualidade
Dem. (2) Suponha que o primal não tem ótimo finito (ou seja, a
imagem da função objetivo tende a “- infinito”). 
Vamos supor por absurdo que, simultaneamente, o problema 
dual tem pontos viáveis; seja w um desses pontos.
Sendo assim, teríamos que nos indica que o valor 
da função objetivo primal é limitado inferiormente, o que é 
um absurdo.
De forma análoga, é possível demonstrar que se o dual não 
tem ponto ótimo finito, então o primal não tem pontos 
viáveis.
 
Conclusões
Pode-se concluir que, para os problemas primal-dual, verifica-
se uma e
só uma das seguintes situações:
 Ambos têm soluções ótimas x* e w* e os valores ótimos 
coincidem:
 Se um problema não tem ótimo finito, então o outro é 
impossível;
 Ambos os problemas são impossíveis.
 
Exemplos
 Ambos têm solução ótima
 
Exemplos
 Primal: ótimo infinito; Dual: inviável;
Exemplos
 Ambos são impossíveis.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23