slides

Transcrição

slides

Universidade Federal de São Carlos
Departamento de Engenharia de Produção
Otimização Contı́nua e Discreta
PPGEP - Semestre 01/2016
Prof. Pedro Munari ([email protected])
Aula 3: Dualidade, condições de otimalidade e o método simplex
Objetivos da aula de hoje
I
Aprofundar nosso estudo em dualidade;
I
Estudar as condições de otimalidade;
I
Introdução ao método simplex.
(Prof. Pedro Munari, [email protected])
Aula anterior...
I
Notação matricial e forma padrão;
I
Definições: Hiperplano e semi-espaço; poliedro e politopo; raio e raio
de subida/descida; função convexa, conjunto convexo e envoltório
convexo;
I
Solução gráfica;
I
Problema dual usando tabela de conversão;
I
Problema dual pela teoria Lagrangiana;
I
Principais resultados em Dualidade;
I
Interpretação econômica.
Exercı́cios - Lista 1
. Exercı́cio 8
Coloque na forma padrão, os seguintes problemas de programação linear:
(a) max
s.a
f (x1 , x2 , x3 ) = −5x1 − 3x2 + 7x3
2x1 + 4x2 + 6x3 ≥ 7
3x1 − 5x2 + 5x3 ≤ 5
x1 ≥ 0, x2 ≥ 2, x3 livre
(b) max
s.a
f (x1 , x2 , x3 ) = 2x1 − 3x2 + 7x3
2x1 + 4x2 + 6x3 = 7
3x1 − 5x2 + 3x3 ≤ 5
−4x1 − 9x2 + 4x3 ≤ −4
x1 ≥ −2, 0 ≤ x2 ≤ 4, x3 ≥ 0
. Exercı́cio 8(a)
(a) max
s.a
f (x1 , x2 , x3 ) = −5x1 − 3x2 + 7x3
2x1 + 4x2 + 6x3 ≥ 7
3x1 − 5x2 + 5x3 ≤ 5
x1 ≥ 0, x2 ≥ 2, x3 livre
. Exercı́cio 8(a)
−
a
a
Substituindo x2 = x02 + 2, x3 = x+
3 − x3 e adicionando x1 e x2 :
−min
−
5x1 + 3x02 − 7x+
3 + 7x3 + 6
−
a
s.a −2x1 − 4x02 − 6x+
3 + 6x3 + x1 = 1
−
a
3x1 − 5x02 + 5x+
3 − 5x3 + x2 = 15
−
a
a
x1 , x02 , x+
3 , x3 , x1 , x2 ≥ 0.
. Exercı́cio 8(b)
(b) max
s.a
f (x1 , x2 , x3 ) = 2x1 − 3x2 + 7x3
2x1 + 4x2 + 6x3 = 7
3x1 − 5x2 + 3x3 ≤ 5
−4x1 − 9x2 + 4x3 ≤ −4
x1 ≥ −2, 0 ≤ x2 ≤ 4, x3 ≥ 0
. Exercı́cio 8(b)
Substituindo x1 = x01 − 2 e adicionando xa2 , xa3 , xa4 :
−min
−2x01 + 3x2 − 7x3 + 4
s.a
2x01 + 4x2 + 6x3 = 11
3x01 − 5x2 + 3x3 + xa2 = 11
4x01 + 9x2 − 4x3 − xa3 = 12
x2 + xa4 = 4
x01 , x2 , x3 , x3 , xa2 , xa3 , xa4 ≥ 0.
. Exercı́cio 9(a)
Determine uma solução ótima usando solução gráfica.
min f (x1 , x2 ) = 2x1 + x2
s.a
x1 − x2 ≤ 1
3x1 + 2x2 ≤ 12
2x1 + 3x2 ≥ 3
−2x1 + 3x2 ≤ 9
x1 ≥ 0, x2 ≥ 0.
. Exercı́cio 9(a)
min
s.a
x2
f (x1 , x2 ) = 2x1 + x2
x1 − x2 ≤ 1
3x1 + 2x2 ≤ 12
2x1 + 3x2 ≥ 3
−2x1 + 3x2 ≤ 9
x1 ≥ 0, x2 ≥ 0.
x1
. Exercı́cio 9(a)
min
s.a
x2
f (x1 , x2 ) = 2x1 + x2
x1 − x2 ≤ 1
3x1 + 2x2 ≤ 12
2x1 + 3x2 ≥ 3
−2x1 + 3x2 ≤ 9
x1 ≥ 0, x2 ≥ 0.
x1
-1
. Exercı́cio 9(a)
x2
6
min
s.a
f (x1 , x2 ) = 2x1 + x2
x1 − x2 ≤ 1
3x1 + 2x2 ≤ 12
2x1 + 3x2 ≥ 3
−2x1 + 3x2 ≤ 9
x1 ≥ 0, x2 ≥ 0.
4
-1
x1
. Exercı́cio 9(a)
x2
6
min
s.a
f (x1 , x2 ) = 2x1 + x2
x1 − x2 ≤ 1
3x1 + 2x2 ≤ 12
2x1 + 3x2 ≥ 3
−2x1 + 3x2 ≤ 9
x1 ≥ 0, x2 ≥ 0.
4
-1
x1
. Exercı́cio 9(a)
x2
6
min
s.a
f (x1 , x2 ) = 2x1 + x2
x1 − x2 ≤ 1
3x1 + 2x2 ≤ 12
2x1 + 3x2 ≥ 3
−2x1 + 3x2 ≤ 9
x1 ≥ 0, x2 ≥ 0.
-5
4
-1
x1
. Exercı́cio 9(a)
x2
6
min
s.a
f (x1 , x2 ) = 2x1 + x2
x1 − x2 ≤ 1
3x1 + 2x2 ≤ 12
2x1 + 3x2 ≥ 3
−2x1 + 3x2 ≤ 9
x1 ≥ 0, x2 ≥ 0.
-5
4
-1
x1
. Exercı́cio 9(a)
x2
6
min
s.a
f (x1 , x2 ) = 2x1 + x2
x1 − x2 ≤ 1
3x1 + 2x2 ≤ 12
2x1 + 3x2 ≥ 3
−2x1 + 3x2 ≤ 9
x1 ≥ 0, x2 ≥ 0.
-5
4
-1
x1
. Exercı́cio 9(a)
x2
6
min
s.a
f (x1 , x2 ) = 2x1 + x2
x1 − x2 ≤ 1
3x1 + 2x2 ≤ 12
2x1 + 3x2 ≥ 3
−2x1 + 3x2 ≤ 9
x1 ≥ 0, x2 ≥ 0.
-5
4
-1
x1
. Exercı́cio 9(a)
x2
6
min
s.a
f (x1 , x2 ) = 2x1 + x2
x1 − x2 ≤ 1
3x1 + 2x2 ≤ 12
2x1 + 3x2 ≥ 3
−2x1 + 3x2 ≤ 9
x1 ≥ 0, x2 ≥ 0.
-5
4
-1
x1
. Exercı́cio 9(a)
min f (x1 , x2 ) = 2x1 + x2
s.a
x1 − x2 ≤ 1
3x1 + 2x2 ≤ 12
2x1 + 3x2 ≥ 3
−2x1 + 3x2 ≤ 9
x1 ≥ 0, x2 ≥ 0.
Logo, temos a solução ótima x∗ = (0, 1) com valor ótimo f (x∗ ) = 1.
. Exercı́cio 2(a)
Determine o problema dual e encontre a solução ótima dual usando
solução gráfica.
min
f (x1 , x2 ) = 2x1 + x2
s.a
−2x1 + 3x2 ≥ 9
3x1 + 2x2 ≥ 12
x1 ≥ 0, x2 ≥ 0.
. Exercı́cio 2(a)
Determine o problema dual e encontre a solução ótima dual usando
solução gráfica.
min
f (x1 , x2 ) = 2x1 + x2
s.a
−2x1 + 3x2 ≥ 9
max
s.a
g(p1 , p2 ) = 9p1 + 12p2
−2p1 + 3p2 ≤ 2
3x1 + 2x2 ≥ 12
3p1 + 2p2 ≤ 1
x1 ≥ 0, x2 ≥ 0.
p1 ≥ 0, p2 ≥ 0.
. Exercı́cio 2(a)
λ2
max
s.a
g(p1 , p2 ) = 9p1 + 12p2
−2p1 + 3p2 ≤ 2
3p1 + 2p2 ≤ 1
p1 ≥ 0, p2 ≥ 0.
λ1
. Exercı́cio 2(a)
λ2
max
s.a
g(p1 , p2 ) = 9p1 + 12p2
−2p1 + 3p2 ≤ 2
3p1 + 2p2 ≤ 1
p1 ≥ 0, p2 ≥ 0.
-1
λ1
. Exercı́cio 2(a)
λ2
max
s.a
g(p1 , p2 ) = 9p1 + 12p2
−2p1 + 3p2 ≤ 2
3p1 + 2p2 ≤ 1
p1 ≥ 0, p2 ≥ 0.
-1
λ1
. Exercı́cio 2(a)
λ2
max
s.a
g(p1 , p2 ) = 9p1 + 12p2
−2p1 + 3p2 ≤ 2
3p1 + 2p2 ≤ 1
p1 ≥ 0, p2 ≥ 0.
-1
λ1
. Exercı́cio 2(a)
λ2
max
s.a
g(p1 , p2 ) = 9p1 + 12p2
−2p1 + 3p2 ≤ 2
3p1 + 2p2 ≤ 1
p1 ≥ 0, p2 ≥ 0.
-1
λ1
. Exercı́cio 2(a)
λ2
max
s.a
g(p1 , p2 ) = 9p1 + 12p2
−2p1 + 3p2 ≤ 2
3p1 + 2p2 ≤ 1
p1 ≥ 0, p2 ≥ 0.
-1
λ1
. Exercı́cio 2(a)
λ2
max
s.a
g(p1 , p2 ) = 9p1 + 12p2
−2p1 + 3p2 ≤ 2
3p1 + 2p2 ≤ 1
p1 ≥ 0, p2 ≥ 0.
"
#
0
∗
p =
0.5
∗
g(p ) = 6
-1
λ1
. Exercı́cio 2(b)
A partir da solução ótima dual encontrada no item anterior, determine
uma solução ótima para o problema primal (sem resolvê-lo diretamente).
min
f (x1 , x2 ) = 2x1 + x2
s.a
−2x1 + 3x2 ≥ 9
max
s.a
g(p1 , p2 ) = 9p1 + 12p2
−2p1 + 3p2 ≤ 2
3x1 + 2x2 ≥ 12
3p1 + 2p2 ≤ 1
x1 ≥ 0, x2 ≥ 0.
p1 ≥ 0, p2 ≥ 0.
. Exercı́cio 2(b)
Teorema: Folgas Complementares.
I
Sejam x e p soluções factı́veis dos problemas primal e dual, respect.
Os vetores x e p são soluções ótimas dos respectivos problemas se, e
somente se,
(i) pi (ATi x − bi ) = 0, i = 1, . . . , m;
(ii) (cj − pT aj )xj = 0, j = 1, . . . , n.
. Exercı́cio 2(b)
I
I
Pelo Teorema das folgas complementares, temos que:
p1 (9 − (−2x1 + 3x2 ))
=
0
p2 (12 − (3x1 + 2x2 ))
=
0
(2 − (−2p1 + 3p2 ))x1
=
0
(1 − (3p1 + 2p2 ))x2
=
0
Sabemos que a solução ótima dual é p∗ = (0, 0.5). Assim, devemos ter
12 − (3x1 + 2x2 ) = 0. Além disso, substituindo essa solução nas duas
últimas equações, obtemos:
(2 − 1.5)x1
=
0 ⇒ x1 = 0
(1 − 1)x2
=
0 ⇒ x2 ≥ 0
. Exercı́cio 2(b)
I
Pelo Teorema das folgas complementares, temos que:
p1 (9 − (−2x1 + 3x2 ))
=
0
p2 (12 − (3x1 + 2x2 ))
=
0
(2 − (−2p1 + 3p2 ))x1
=
0
(1 − (3p1 + 2p2 ))x2
=
0
I
Logo, juntando esses resultados, obtemos:
12 − (3 ∗ 0 + 2x2 ) = 0 ⇒ 12 − 2x2 = 0 ⇒ x2 = 6;
I
Portanto, x∗ = (0, 6) é uma solução ótima do problema primal.
Dualidade
I
A teoria de dualidade tem suas raı́zes nos trabalhos de Lagrange;
I
A otimização de uma função restrita a um domı́nio é tratada como a
otimização de uma função irrestrita penalizada;
Dualidade
I
Considere que o seguinte problema possua solução ótima x∗ :
min
f (x) = cT x
s.a
Ax = b
x≥0
I
Existe um vetor p∗ ∈ Rm tal que o seguinte problema é equivalente:
min
cT x + (p∗ )T (b − Ax)
s.a
x≥0
Dualidade
I
Para um vetor p ∈ Rm arbitrário, temos uma relaxação:
f (x∗ )
I
=
min{cT x | Ax = b}
=
min{cT x + pT (b − Ax) | Ax = b}
≥
min{cT x + pT (b − Ax)}.
x≥0
x≥0
x≥0
Seja g(p) o valor ótimo deste problema relaxado (em função de p), i.e.
g(p) = min{cT x + pT (b − Ax)}.
x≥0
I
Para qualquer p ∈ Rm , temos g(p) ≤ f (x∗ ). Assim, temos um limitante
inferior para o valor ótimo do problema original.
Dualidade
Surgem então as questões:
I
Qual será o vetor p∗ ∈ Rm que resulta no melhor limitante inferior?
I
Será que podemos garantir que g(p∗ ) = f (x∗ )?
Melhor limitante:
g(p∗ )
=
=
max g(p)
p∈Rm
max min{cT x + pT (b − Ax)}.
p∈Rm x≥0
Dualidade
Temos que para p ∈ Rm arbitrário:
g(p)
=
min{cT x + pT (b − Ax)}
=
min{cT x + pT b − pT Ax}
=
pT b + min{cT x − pT Ax}
=
pT b + min{(cT − pT A)x}
x≥0
( n
)
X
T
T
p b + min
(cj − p aj )xj
=
=
x≥0
x≥0
x≥0
x≥0
pT b +
n
X
j=1
j=1
min (cj − pT aj )xj .
xj ≥0
Dualidade
Observe que para cada j = 1, . . . , n, temos:

 −∞, se (cj − pT aj ) < 0,
min (cj − pT aj )xj =
xj ≥0

0, c.c.
(xj → ∞)
(xj = 0)
I
Sempre que essa expressão resulta em −∞, temos um limitante trivial;
(lembre-se que estamos buscando o limitante máximo)
I
Assim, queremos evitar esse tipo de limitante;
I
Basta restringirmos p t.q. cj − pT aj ≥ 0, j = 1, . . . , n;
I
Dessa forma, min (cj − pT aj )xj = 0.
xj ≥0
Dualidade
Continuando a expressão para g(p), temos que:
g(p)
=
pT b +
=
pT b
n
X
j=1
min (cj − pT aj )xj
xj ≥0
para todo p ∈ Rm t.q. cj − pT aj ≥ 0, j = 1, . . . , n. Portanto,
g(p∗ )
=
=
=
max g(p)
p∈Rm
max {g(p) | AT p ≤ c}
p∈Rm
max {pT b | AT p ≤ c}.
p∈Rm
(problema dual)
Dualidade
Problema primal
min f (x) = cT x
s.a
Ax = b
x≥0
Problema dual
max g(p) = bT p
s.a
AT p ≤ c
. Exercı́cio 1
Usando a teoria Lagrangiana, determine o problema dual do seguinte
problema de programação linear (sem usar a forma padrão):
min
f (x1 , x2 , x3 ) = c1 x1 + c2 x2 + c3 x3
s.a
a11 x1 + a12 x2 + a13 x3 = b1
a21 x1 + a22 x2 + a23 x3 ≤ b2
a31 x1 + a32 x2 + a33 x3 ≥ b3
x1 ≥ 0, x2 ≤ 0, x3 livre.
Dualidade
. Propriedades
Teorema: Dualidade fraca.
I
Se x é uma solução factı́vel para o problema primal e p é uma
solução factı́vel para o problema dual, então bT p ≤ cT x.
Dualidade
. Propriedades
Corolário 1:
1. Se o problema primal é ilimitado, então o dual é infactı́vel;
2. Se o problema dual é ilimitado, então o primal é infactı́vel.
Corolário 2:
1. Sejam x e p soluções factı́veis dos problemas primal e dual, respect.,
tais que bT p = cT x. Então, x e p são soluções ótimas dos problemas
primal e dual, respect.
Dualidade
. Propriedades
Teorema: Dualidade forte.
I
Se um problema de programação linear tem solução ótima, então
seu dual também tem, e os respectivos valores ótimos são iguais.
Dualidade
. Propriedades
Teorema: Lema de Farkas.
I
Sejam A uma matriz m × n e b ∈ Rm . Então, exatamente uma das
afirmações a seguir é válida:
1. Existe algum x ≥ 0 tal que Ax = b;
2. Existe algum vetor p ∈ Rm tal que pT A ≥ 0 e pT b < 0.
Dualidade
. Lema de Farkas: Ilustração
a1
a3
a2
a4
I
Representação vetorial das colunas de A = [a1 , a2 , a3 , a4 ];
Dualidade
a1
a3
a2
a4
I
Representação vetorial das colunas de A = [a1 , a2 , a3 , a4 ];
Dualidade
a1
a3
a4
I
Cone formado pelas colunas a1 , a2 , a3 , a4 ;
a2
cone: combinações
lineares não-negativas
das colunas de A
Dualidade
a1
b
a4
I
a3
a2
cone: combinações
das colunas de A
Caso 1: b pertence ao cone (i.e., pode ser escrito como uma
combinação linear positiva das colunas de A);
Dualidade
a1
a4
a3
a2
cone: combinações
das colunas de A
b
I
Caso 2: b não pertence ao cone (i.e., não pode ser escrito como
uma combinação linear positiva das colunas de A);
Dualidade
a1
p
a3
a2
a4
b
I
Caso 2: Então existe p
Dualidade
a1
p
a3
a2
T
p z =0
a4
b
I
Caso 2: Então existe p tal que pt z = 0 é hiperplano separador ;
Dualidade
a1
p
a3
a2
T
p z =0
a4
pT z > 0
b
pT z < 0
I
Caso 2: Então existe p tal que pt z = 0 é hiperplano separador
(i.e., pT ai ≥ 0 e pT b < 0);
Dualidade
a1
a3
a2
b
a4
p
I
(i.e., pT ai ≥ 0 e pT b < 0);
Dualidade
p T z =0
a1
a3
a2
b
a4
p
I
(i.e., pT ai ≥ 0 e pT b < 0);
Dualidade
a1
b
a3
a2
a4
I
Caso 1: b pertence ao cone e, logo, não existe hiperplano separador.
Dualidade
. Propriedades
Teorema: Lema de Farkas.
I
2. Existe algum vetor p ∈ Rm tal que pT A ≥ 0 e pT b < 0.
. Exercı́cio 4
Mostre que o par primal-dual de problemas a seguir satisfaz o Lema de
Farkas.
min
x1 + 2x2
max
p1 + 3p2
s.a
x1 + x2 = 1
s.a
p1 + 2p2 = 1
2x1 + 2x2 = 3
p1 + 2p2 = 2
. Exercı́cio 4
I
Para aplicarmos o Lema de Farkas, precisamos colocar o problema
primal na forma padrão. Assim:
min
s.a
−
+
−
x+
1 − x1 + 2x2 − 2x2
−
+
+
x+
1 − x1 + x2 − x2 = 1
⇒
−
+
+
2x+
1 − 2x1 + 2x2 − 2x2 = 3
−
+
−
x+
1 , x1 , x2 , x2 ≥ 0
max
s.a
p1 + 3p2
p1 + 2p2 ≤ 1
−p1 − 2p2 ≤ −1
p1 + 2p2 ≤ 2
−p1 − 2p2 ≤ −2
. Exercı́cio 4
3
2
1
1
2
. Exercı́cio 4
3
2
a1
1
1
2
. Exercı́cio 4
3
2
a1
1
1
a2
2
. Exercı́cio 4
3
2
b
a1
1
1
a2
2
. Exercı́cio 4
3
2
b
a1
1
1
a2
2
. Exercı́cio 4
3
2
b
a1
1
1
2
p
a2
Dualidade
. Propriedades
Teorema: Lema de Farkas. (Forma 2)
I
2. Existe algum vetor p ∈ Rm tal que pT A ≤ 0 e pT b > 0.
Dualidade
. Lema de Farkas: Interpretação
I
Se existe p ∈ Rm tal que pT A ≤ 0 e pT b > 0, então p pode ser um
raio de subida no espaço dual; (dual ilimitado se for factı́vel)
Definição: Raio.
I
Considere o poliedro S = {p ∈ Rm |AT p ≤ c}. O vetor r ∈ S é chamado
de raio quando satisfaz p + εr ∈ S, para todo p ∈ S e escalar ε ≥ 0.
Definição: Raio de subida.
I
Considere o poliedro S = {p ∈ Rm |AT p ≤ c} contendo um raio r ∈ S.
Seja g : S → R um funcional linear arbitrário. Se g(p + εr) > g(p), para
todo p ∈ S e escalar ε ≥ 0, então r é chamado de raio de subida de g.
Dualidade
. Propriedades
Teorema: Lema de Farkas. (Forma 3)
I
1. Existe algum r ∈ Rn tal que Ar = 0, cT r < 0 e r ≥ 0;
2. Existe algum p ∈ Rm tal que AT p ≤ c.
Dualidade
. Propriedades
I
Sejam x e p soluções factı́veis dos problemas primal e dual,
respectivamente. Os vetores x e p são soluções ótimas dos
respectivos problemas se, e somente se,
(i) pi (ATi x − bi ) = 0, i = 1, . . . , m;
(ii) (cj − pT aj )xj = 0, j = 1, . . . , n.
Dualidade
. Propriedades
Problema primal
min f (x) = cT x
s.a
Ax = b
x≥0
Problema dual
max g(p) = bT p
s.a
AT p ≤ c
Dualidade
. Propriedades
Problema primal
min f (x) = cT x
s.a
Ax ≥ b
x≥0
Problema dual
max g(p) = bT p
s.a
AT p ≤ c
p≥0
Dualidade
. Propriedades
I
(i) pi (ATi x − bi ) = 0, i = 1, . . . , m;
(ii) (cj − pT aj )xj = 0, j = 1, . . . , n.
Dualidade
. Condições de otimalidade
I
Considere o problema primal na forma padrão;
(sem perda de generalidade)
I
Vamos reescrever o Teorema das Folgas Complementares:
I
(i) pi (ATi x − bi ) = 0, i = 1, . . . , m;
(ii) (cj − pT aj )xj = 0, j = 1, . . . , n.
Dualidade
I
I
I
Sejam x ∈ Rn e p ∈ Rm tais que
Ax =
b
x ≥
0
AT p
≤
c
somente se,
(i) pi (ATi x − bi ) = 0, i = 1, . . . , m;
(ii) (cj − pT aj )xj = 0, j = 1, . . . , n.
Dualidade
I
I
I
Sejam x ∈ Rn e p ∈ Rm tais que
Ax =
b
x ≥
0
AT p
≤
c
somente se, (cj − pT aj )xj = 0, j = 1, . . . , n.
Dualidade
I
I
Os vetores x ∈ Rn e p ∈ Rm são soluções ótimas dos problemas
primal e dual, respectivamente, se e somente se, satisfazem
Ax
= b
AT p
≤ c
T
(cj − p aj )xj
x
=
0, j = 1, . . . , n,
≥ 0
Dualidade
I
Considere os problemas primal e dual na forma padrão;
I
Os vetores x ∈ Rn , p ∈ Rm e s ∈ Rn são soluções ótimas dos
problemas primal e dual, respectivamente, se e somente se,
satisfazem
Ax
= b
T
A p+s = c
sj xj
=
0, j = 1, . . . , n
x, s ≥ 0
Dualidade
I
Com isso, nós acabamos de deduzir um dos principais resultados em
Otimização (linear e não-linear):
Condições KKT (Karush-Kuhn-Tucker)
Ax =
b
A p+s =
c
T
sj xj
=
x, s ≥
0, j = 1, . . . , n
0
I
Em programação linear, temos que as condições KKT são
necessárias e suficientes para otimalidade;
I
Para problemas de otimização em geral, são condições necessárias
apenas (e podem exigir algumas condições a mais).
Dualidade
. Condições KKT
“When Kuhn and Tucker proved the Kuhn-Tucker theorem in 1950 they
launched the theory of non-linear programming. However, in a sense this
theorem had been proven already: In 1939 by W. Karush in a master’s
thesis, which was unpublished; in 1948 by F. John in a paper that was at
first rejected by the Duke Mathematical Journal; and possibly earlier by
Ostrogradsky and Farkas.”
Kjeldsen, T.H. A Contextualized Historical Analysis of the Kuhn-Tucker
Theorem in Nonlinear Programming: The Impact of World War II. Historia
Mathematica 27(4), 331–361, 2000.
Dualidade
. Condições KKT
Considere o problema de Otimização (geral)
min
f (x1 , . . . , xn )
s.a
h1 (x1 , . . . , xn ) = 0
..
.
hl (x1 , . . . , xn ) = 0
g1 (x1 , . . . , xn ) ≤ 0
..
.
gm (x1 , . . . , xn ) ≤ 0
Dualidade
. Condições KKT
Considere o problema de Otimização (geral)
min
f (x)
s.a
h(x) = 0
g(x) ≤ 0
com f : Rn → R, h : Rn → Rl e g : Rn → Rm .
Definimos a função Lagrangiana do problema:
L(x, p, s) = f (x) + pT h(x) + sT g(x)
com sT ≥ 0.
(1)
Dualidade
. Condições KKT
Teorema: Condições necessárias de primeira ordem (condições KKT).
I
Suponha que x seja um ótimo local do problema de otimização (1),
que as funções f , g e h sejam continuamente diferenciáveis e que
certas condições de qualificação sejam válidas. Então existe um
vetor de multiplicadores de Lagrange (p, s) tal que as seguintes
condições são satisfeitas:
∇x L(x, p, s)
=
0
hk (x)
=
0, k = 1, . . . , l
gj (x) ≤ 0, j = 1, . . . , m
sj gj (x)
=
0, j = 1, . . . , m
sj
≥
0, j = 1, . . . , m
Dualidade
. Condições KKT
I
No caso particular de programação linear, temos:
f (x) = cT x;
h(x) = b − Ax;
gj (x) = − xj , j = 1, . . . , n;
L(x, p, s) = cT x + pT (b − Ax) − sT (x)
⇒ ∇x L(x, p, s) = c − AT p − s
I
Além disso, as condições de qualificação são sempre satisfeitas;
I
Pela dualidade forte, as condições são também suficientes.
Dualidade
. Condições KKT
Teorema: Condições necessárias de primeira ordem (condições KKT).
I
Suponha que x seja um ótimo local do problema de otimização (1),
que as funções f , g e h sejam continuamente diferenciáveis e que
certas condições de qualificação sejam válidas. Então existe um
vetor de multiplicadores de Lagrange (p, s) tal que as seguintes
condições são satisfeitas:
∇x L(x, p, s)
=
0
hk (x)
=
0, k = 1, . . . , l
gj (x) ≤ 0, j = 1, . . . , m
sj gj (x)
=
0, j = 1, . . . , m
sj
≥
0, j = 1, . . . , m
Dualidade
. Condições KKT
I
Assim, a teoria dos multiplicadores de Lagrange é a base da teoria
de dualidade;
I
Que por sua vez é a base das condições KKT;
I
Que por sua vez são a base dos métodos de solução em otimização.
Dualidade
. Condições KKT: Métodos de solução
Ax =
T
A p+s =
sj xj
=
x, s ≥
b
(2)
c
(3)
0, j = 1, . . . , n
(4)
0
(5)
I
Onde está a dificuldade? Nas folgas complementares (são não-lineares);
I
Métodos tipo simplex: particionam as variáveis em dois conjuntos, B e N
(i.e. B ∩ N = ∅ e B ∪ N = {1, 2, . . . , n}). Para garantir (4), impõem
xj = 0, ∀j ∈ N , e sj = 0, ∀j ∈ B. (2) e (3) são sempre satisfeitos. Além
disso, a partição deve garantir:
I
I
Método primal simplex: x ≥ 0 (factibilidade primal, busca-se s ≥ 0);
Método dual simplex: s ≥ 0 (factibilidade dual, busca-se x ≥ 0).
Dualidade
. Condições KKT: Métodos de solução
I
Métodos de pontos interiores: Perturbam a dificuldade do sistema KKT:
Ax
=
b
(6)
A p+s
=
c
(7)
sj xj
=
µ, j = 1, . . . , n
(8)
T
para µ > 0. Baseiam-se na direção do método de Newton para
determinam direções de busca, tais que iterativamente o valor de µ é
estritamente reduzido e, assim, µ → 0. Além disso:
I
Método primal-dual: usa (6) e (7) para calcular as direções de busca.
É chamado factı́vel quando (6) e (7) devem ser satisfeitos em toda
iteração. Caso contrário, o método é chamado infactı́vel.
Método simplex
I
Vamos agora estudar o método (primal) simplex;
I
Método iterativo para resolver problemas de programação linear;
I
Em média, menos de 3m iterações para obter a solução ótima
(embora tenha complexidade não-polinomial);
I
Proposto em 1947 por George B. Dantzig;
I
2000: reconhecido como um dos 10 algoritmos mais importantes do
século 20 (IEEE);
I
2012: ”The algorithm that runs the world”(NewScientist).
Método simplex
I
n putting together this issue of Computing in
Science & Engineering, we knew three things:
it would be difficult to list just 10 algorithms;
it would be fun to assemble the authors and
read their papers; and, whatever we came up
with in the end, it would be controversial. We
tried to assemble the 10 algorithms with the greatest
influence on the development and practice of science
and engineering in the 20th century. Following is our
list (here, the list is in chronological order; however,
the articles appear in no particular order):
• Metropolis Algorithm for Monte Carlo
• Simplex Method for Linear Programming
hand in developing the algorithm, and in other cases,
the author is a leading authority.
Monte Carlo methods are powerful tools for evaluating the properties of complex, many-body systems,
as well as nondeterministic processes. Isabel Beichl and
Francis Sullivan describe the Metropolis Algorithm.
We are often confronted with problems that have an
enormous number of dimensions or a process that involves a path with many possible branch points, each
of which is governed by some fundamental probability
of occurence. The solutions are not exact in a rigorous
Método simplex
NewScientist, 2012: ”You might not have heard of the algorithm that
runs the world. Few people have, though it can determine much that
goes on in our day-to-day lives: the food we have to eat, our schedule at
work, when the train will come to take us there. Somewhere, in some
server basement right now, it is probably working on some aspect of your
life tomorrow, next week, in a year’s time.”
Método simplex
I
Métodos tipo simplex se baseiam em partições [B, N ];
I
Surgem então as questões:
I
I
I
Qual a partição ótima?
I
É viável testarmos todas as partições possı́veis?
I
Se tivermos uma partição qualquer, como detectar se ela é ótima?
I
Se não for ótima, é sempre possı́vel determinar uma melhor?
Para enumerar todas as partições: combinar os n ı́ndices, m a m;
n!
Isso exigiria avaliar até
partições!
m!(n − m)!
Método simplex
Problema das ligas metálicas na forma padrão:
min
s.a
−3x1 − 2x2 + 0x3 + 0x4 + 0x5
0.5x1 + 0.3x2 + x3
0.1x1 + 0.2x2
0.4x1 + 0.5x2
=3
+ x4
=1
+ x5 = 3
x1 , x 2 , x 3 , x 4 , x 5 ≥ 0
Notação matricial
f (x) = −3x1 − 2x2
min
s.a
0.5x1 + 0.3x2 + x3
0.1x1 + 0.2x2
=3
+ x4
0.4x1 + 0.5x2
=1
+ x5 = 3
x1 , x 2 , x 3 , x 4 , x 5 ≥ 0

x1

 x2


x =  x3

 x
 4
x5





,





−3


 −2 




c =  0 ,


 0 



0.5

A= 
 0.1
0.4
0.3
1
0

0 
,
1
0.2
0
1
0.5
0
0
0
Ax = b

0


3



b= 
 1 
3
f (x) = −3x1 − 2x2 + 0x3 + 0x4 + 0x5

x1

 x2


f (x) = [−3, −2, 0, 0, 0]  x3

 x
 4
x5
f (x) = cT x












 0.5x1 + 0.3x2 + x3
0.1x1 + 0.2x2
=3
+ x4


 0.4x + 0.5x
1
2
+ x5 = 3


0.5
0.3
1
0

 0.1

0.4
0.2
0
1
0.5
0
0
=1
x1


0
 x2


0 
  x3

 x4
1

x5
Ax = b




3



 = 1




3








 0.5x1 + 0.3x2 + x3
0.1x1 + 0.2x2
=3
+ x4
=1


 0.4x + 0.5x
1
2
+ x5 = 3
a1 x1 + a2 x2 + a3 x3 + a4 x4 + a5 x5 = b

0.5


0.3


1


0


0


3













 0.1  x1 +  0.2  x2 +  0  x3 +  1  x4 +  0  x5 =  1 












0.5
0
0
1
3
0.4
Para uma dada partição B = {1, 2, 3}, N = {4, 5} :
AB xB + a4 x4 + a5 x5 = b
B := AB


x1







0.5
0.3
1

 0.1

0.4
0.2
 







 





0 
  x2  +  1  x4 +  0  x5 =  1 
x3
0
0
1
3
0.5
0
0
3
BxB + a4 x4 + a5 x5 = b
(B := AB )

0.5

 0.1

0.4
0.3
0.2
0.5
 
x1
0

 




+
0   x2   1
0
x3
0
1



0


 x4 +  0


1

3


 x5 =  1


3





BxB = b − a4 x4 − a5 x5
(B := AB )

0.5

 0.1

0.4
0.3
0.2
0.5
 
x1
3

 




=
0   x2   1
x3
3
0
1



0
 
− 1
 
0

0


 x4 −  0


1



 x5

BxB = b − a1 x1 − a4 x4
(B := AB )



3


0.5


0

 0

0
0.2



 






 



0 
  x2  =  1  −  0.1  x1 −  1  x4
x5
1
3
0.4
0
Como deixar apenas o vetor xB do lado esquerdo?
0

0.3
0.5
x3

1
xB = B −1 b − B −1 a1 x1 − B −1 a4 x4

x3


1 0.3 0
−1 
3
 
1 0.3 0
−1 
0.5


1 0.3 0
−1 
0


x2
= 
0 0.2 0

1
− 
0 0.2 0

0.1
 x1 −
0 0.2 0

1
 x4
x5
0 0.5 1

3
0 0.5 1

0.4
0 0.5 1

0
xB = B −1 b − B −1 a1 x1 − B −1 a4 x4

x3


x2
= 
x5

1 −1.5 0

3
 
1 −1.5 0

0.5

0

1
− 
0

0.1
 x1 −
5
0
0 −2.5 1
3
5
0
0 −2.5 1
0.4

1 −1.5 0

0

0

1
 x4
5
0
0 −2.5 1
0
xB = B −1 b − B −1 a1 x1 − B −1 a4 x4

x3


1.5
 
0.35


 
 



 x2 =  5 −  0.5  x1 − 
x5
0.5
0.15
−1.5
5
−2.5


 x4
. Escrever xB em função de xN
No caso geral, as restrições primais podem ser escritas como:
BxB +
X
aj x j = b
j∈N
BxB = b −
X
aj x j
j∈N
xB = B −1 b−
X
j∈N
B −1 aj xj (solução geral primal)
. Escrever xB em função de xN
Solução particular com xN = 0:
xB = B −1 b −
X
j∈N
−1
B
aj x j
x̄B = B −1 b, x̄N = 0 (solução básica primal)
(observe que usamos a barra sobre x para indicar que é uma solução particular)
AT p + s = c


0.5
0.1
0.4

 0.3


 1


 0

0
0.2

0.5 


0 


0 

1
0
1
0


p1

 p2

p3
s1

 s
 2
 
 +  s3
 

 s4

s5



−3





 −2 






 = 0 







 0 



0
B T p + s B = cB
N T p + s N = cN
(B := AB , N := AN )





−3

0.1
0.4

 0.3

1
0.2

 




 



0.5 
  p2  +  s2  =  −2 
0
p3
s3
0







p1


0
s4
0
  p2  + 
 =



1
s5
0
p3


0
0
1
0
0
p1

0.5
s1
B T p + s B = cB
N T p + s N = cN
(B := AB , N := AN )

1

 0.3

0


0
0.2
0
0.5
0.1
0
1
0



0.5 

1



0.4


0
p1


s3
 

p2 
 +  s2
p3
s5


p1

s
 1
p2 
+
s4
p3


0




 =  −2 



0


 =
−3
0


B T p = cB − s B
N T p + s N = cN
(B := AB , N := AN )

1

 0.3

0


0
0.2
0
0.5
0.1
0
1
0



0.5 

1



0.4


0

s3



 

 
p2 
 =  −2  −  s2
p3
0
s5




p1

s1
−3

 =
p2 
+
s4
0
p3



p1

0




pT B = cTB − sTB
N T p + s N = cN
(B := AB , N := AN )

p1
T 
1

0.5
0.1
0
1
0


0
T

s3
T

 






0 
 =  −2  −  s2 
0.5 1
0
s5







p1


0.4
s1
−3
 =

  p2  + 


0
s4
0
p3
 

 p2   0

 
p3
0

0.3
0.2
pT = cTB B −1 − sTB B −1
N T p + s N = cN
(B := AB , N := AN )

p1
T

0
T 
1


 

 p2  =  −2   0



 
p3
0
0


0.5
0.1
0
1
−1.5
5
−2.5


p1

0.4
  p2

0
p3
0


s3
 

0 
 −  s2
1
s5




s1
 +


s4
T 
1
 
  0
 
0

=
−3
0
−1.5
5
−2.5


0


0 

1
N T p + s N = cN
(B := AB , N := AN )

p1
T

0
T

s3
T 






 p2  =  −10  −  s2 






p3
0
s5





p1


0.5 0.1 0.4

  p2  + 


0
1
0
p3
1

 0

0
s1
s4

−1.5
0

−2.5

0 

1


5
 =
−3
0

pT aj + sj = cj , ∀j ∈ N
(B := AB , N := AN )

h
p1
p1
T

0
T

s3
T 
1
−1.5
0

 






 p2  =  −10  −  s2   0
5
0 
 






0 −2.5 1
p3
0
s5




0.5
0
i
h
i




p2 p3 
p1 p2 p3 
 0.1  + s1 = −3;
 1  + s4 = 0
0.4
0
sj = cj − pT aj , ∀j ∈ N
(B := AB , N := AN )
T
T
T 
0

 





 p2  =  −10  −  s2   0
5
0



 


p3
0 −2.5 1
0
s5


0.5
h
h
i


s1 = −3 − p1 p2 p3 
s4 = 0 − p1 p2
 0.1  ;
0.4




p1

0

s3
1
−1.5

p3
0

i

 1 


0
Solução básica
Assim, no caso geral, as restrições duais resultam em:
sj = cj − pT aj , ∀j ∈ N
(Solução geral dual)
Fixando s̄B = 0, obtemos a solução particular:
p̄T = cTB B −1 , s̄B = 0,
s̄j = cj − p̄T aj , ∀j ∈ N .
(Solução básica dual)
I
Métodos tipo simplex partem de uma partição inicial e,
iterativamente, vão modificando essa partição até obter a ótima;
I
Os métodos consideram partições básicas apenas;
I
B : ı́ndices básicos ou base;
I
B = AB : matriz básica (deve ser invertı́vel);
I
N : ı́ndices não-básicos.
Determine a solução ótima do problema de programação linear:
min
−3x1 − 2x2 + 0x3 + 0x4 + 0x5
s.a
0.5x1 + 0.3x2 + x3 = 3
0.1x1 + 0.2x2 + x4 = 1
0.4x1 + 0.5x2 + x5 = 3
x1 , x 2 , x 3 , x 4 , x 5 ≥ 0
B = {3, 4, 5} e N = {1, 2};


1
B=  0
0
0
1
0
0
0 
1
T
h
i
−3
−2
0
0
0
0.5

A =  0.1
0.4
0.3
0.2
0.5
1
0
0
0
1
0



3
0



0  b= 1 
3
1
c
=

I Calcular a solução básica primal:


3
x̄B = B −1 b =  1 
3
I Essa solução é ótima?
I Como obter uma solução melhor?
I Calcular a solução básica dual:
−1
p̄T = cT
=
BB
0 0 0
s̄1 = c1 − p̄T a1 = − 3
s̄2 = c2 − p̄T a2 = − 2
Método simplex
. Condições KKT (Karush-Kuhn-Tucker)
Ax =
b
(9)
AT p + s =
c
(10)
0, j = 1, . . . , n
(11)
0
(12)
sj xj
=
x, s ≥
I
Toda solução básica satisfaz (9), (10) e (11);
I
Para ser ótima, falta satisfazer (12);
I
No método primal simplex, toda solução básica deve ser primal factı́vel e,
portanto, deve satisfazer x ≥ 0;
I
Devemos buscar pela partição básica que também satisfaça s ≥ 0.
Método simplex
. Função objetivo primal
Para o exemplo anterior, observe que se escrevermos a
função objetivo primal em função de xN , obtemos:
(B = {3, 2, 5}, N = {1, 4})
f (x) = −3x1 − 2x2 + 0x3 + 0x4 + 0x5

x3





x1



f (x) = [0, −2, 0] 
 x2  + [−3, 0]
x4
x5
f (x) = cTB xB + cTN xN
Método simplex
f (x) = cTB xB + cTN xN


f (x) = cTB B −1 b −
X
B −1 aj xj  + cTN xN
j∈N
f (x) = cTB B −1 b −
X
cTB B −1 aj xj + cTN xN
j∈N
f (x) = cTB B −1 b +
X
j∈N
cj − cTB B −1 aj xj
Método simplex
f (x) = cTB B −1 b +
X
cj − cTB B −1 aj xj
j∈N
Em uma solução básica, temos que x̄B = B −1 b e pT = cTB B −1 . Assim:
f (x)
=
cTB x̄B +
=
cTB x̄B
X
cj − pT aj xj
j∈N
+
X
sj xj
j∈N
Com isso, sj = cj − pT aj é conhecido como custo relativo de xj .
Nesse contexto, p é conhecido como vetor multiplicador simplex.
Método simplex
Temos até o momento:
I
Solução básica primal: x̄B = B −1 b, x̄N = 0;
I
Solução básica dual: p̄T = cTB B −1 , s̄B = 0, s̄j = cj − p̄T aj , ∀j ∈ N ;
I
As folgas duais sj são os custos relativos de xj , j ∈ N ;
I
Toda solução básica deve ser primal factı́vel (x̄B ≥ 0).
Ainda precisamos determinar:
I
Como saber se a partição básica atual é ótima?
R: sj ≥ 0, j ∈ N .
I
Se não for ótima, como obter uma melhor?
R: Perturbamos uma das variáveis primais não-básicas! (por exemplo,
aquela com o melhor custo relativo!)
Método simplex
. Perturbação da variável primal não-básica
Para o exemplo anterior, com B = {3, 2, 5} e N = {1, 4}, se x1 for escolhido
para ser perturbado, qual o maior valor possı́vel dessa perturbação?
xB = B −1 b − (B −1 a1 )x1 − (B −1 a4 )x4
xB = x̄B − (B −1 a1 )x1 − (B −1 a4 )x4

x3


1.5
 
0.35


 
 



 x2 =  5 −  0.5  x1 − 
x5
0.5
5


 x4
−2.5
0.15
Maior valor para x1 : min
−1.5
1.5 5 0.5
,
,
0.35 0.5 0.15
Método simplex
xB = B −1 b − (B −1 a1 )x1 − (B −1 a4 )x4
xB = x̄B − (B −1 a1 )x1 − (B −1 a4 )x4

x3


1.5
 
0.35


 
 



 x2 =  5 −  0.5  x1 − 
x5
0.5
5


 x4
−2.5
0.15
−1.5
n x̄
x̄B2 x̄B3 o
,
0.35 0.5 0.15
B1
,
Método simplex
xB = B −1 b − (B −1 a1 )x1 − (B −1 a4 )x4
xB = x̄B − yx1 − (B −1 a4 )x4

x3


1.5
 
0.35



 
 


 x2 =  5 − 0.5 x1 − 
x5
0.15
0.5
x̄B1 x̄B2 x̄B3
,
,
y1 y2 y3
−1.5
5


 x4
−2.5
, com y = B −1 a1 .
Método simplex
xB = B −1 b − (B −1 a1 )x1 − (B −1 a4 )x4
xB = x̄B − (B −1 a1 )x1 − (B −1 a4 )x4

x3


1.5
 
0.35



 
 


 x2 =  5 − 0.5 x1 − 
x5
0.5
0.15
−1.5
5


 x4
−2.5
5
Maior valor para x4 : min ×, , × = 1
5
Método simplex
xB = B −1 b − (B −1 a1 )x1 − (B −1 a4 )x4
xB = x̄B − (B −1 a1 )x1 − yx4

x3


1.5
 
0.35



 
 


 x2 =  5 − 0.5 x1 − 
x5
0.5
0.15
−1.5
5


x4
−2.5
x̄B
Maior valor para x4 : min ×, 2 , × , com y = B −1 a4 .
y2
Método simplex
xB = B −1 b − (B −1 a1 )x1 − (B −1 a4 )x4
xB = x̄B − (B −1 a1 )x1 − (B −1 a4 )x4

x3


1.5
 
0.35



 
 


 x2 =  5 −  0.5  x1 − 
x5
0.5
0.15
Maior valor para xk :
min
i=1,...,m
−1.5
5


 x4
−2.5
x̄Bi
, yi > 0 , com y = B −1 ak .
yi
Este cálculo é chamado de teste da razão.
Método simplex
Com isso, temos tudo o que precisamos:
I
Solução básica primal factı́vel: x̄B = B −1 b ≥ 0, x̄N = 0;
I
Solução básica dual: p̄T = cTB B −1 , s̄B = 0, s̄j = cj − p̄T aj , ∀j ∈ N ;
I
As folgas duais sj são os custos relativos de xj , j ∈ N , e indicam qual
variável perturbar;
I
O teste da razão determina a maior perturbação possı́vel para um dado
xk , k ∈ N , tal que x continue factı́vel (x ≥ 0) após a perturbação;
I
A variável xk perturbada se torna não-nula e assim k deve entrar em B;
I
A variável xBi que se torna nula pode sair de B;
I
Esse processo é chamado de troca de base, o que determina uma iteração
do método simplex.
Método simplex
Determine a solução ótima do problema de programação linear:
min
−3x1 − 2x2 + 0x3 + 0x4 + 0x5
s.a
0.5x1 + 0.3x2 + x3 = 3
0.1x1 + 0.2x2 + x4 = 1
0.4x1 + 0.5x2 + x5 = 3
x1 , x 2 , x 3 , x 4 , x 5 ≥ 0
Método simplex
Iteração 1: B = {3, 4, 5} e N = {1, 2};


1
B=  0
0
0
1
0
0
0  = B −1
1
T
h
i
−3
−2
0
0
0
0.5

A =  0.1
0.4
0.3
0.2
0.5
1
0
0
0
1
0



3
0



0  b= 1 
3
1
c
=


x̄B = B
−1
3

I x1 entrará na base.
b=1
3
I Teste da razão:
−1
p̄T = cT
=
BB
0 0 0
s̄1 = c1 − p̄T a1 = − 3
s̄2 = c2 − p̄T a2 = − 2

y=B
−1

0.5
a1 =  0.1 
0.4
x̄B1
3 x̄B2
1 x̄B3
3
=
;
=
;
=
.
y1
0.5 y2
0.1 y3
0.4
I min:
x̄B1
y1
= 6 ⇒ x3 sairá da base.
Método simplex
Iteração 2: B = {1, 4, 5} e N = {3, 2};



0.5
B =  0.1
0.4
0
1
0
0
2
0  B −1 =  −0.2
1
−0.8
0
1
0

0
0 
1
T
h
i
−3
−2
0
0
0
0.5

A =  0.1
0.4
0.3
0.2
0.5
1
0
0
0
1
0



3
0



0  b= 1 
3
1
c
=


x̄B = B
−1
6

b =  0.4 
0.6
I Teste da razão:
−1
p̄T = cT
=
BB
−6 0 0
s̄3 = c3 − p̄T a3 =

y=B
6
s̄2 = c2 − p̄T a2 = − 0.2
−1

0.6
a2 =  0.14 
0.26
x̄B1
6 x̄B2
0.4 x̄B3
0.6
=
;
=
;
=
.
y1
0.6 y2
0.14 y3
0.26
I min:
x̄B3
y3
⇒ x5 sairá da base.
Método simplex
Iteração 3: B = {1, 4, 2} e N = {3, 5};
"
"
#
B=
0.5
0
0.3
0.1
1
0.2
0.4
0
0.5
B −1 =
3.84
0
−2.30
0.23
1
−0.54
−3.07
0
3.84

x̄B = B
−1
4.62
−5.36 0 −0.78
s̄3 = c3 − p̄T a3 = 5.36
s̄5 = c5 −
0
0
0.5

A =  0.1
0.4
0.3
0.2
0.5
1
0
0
0
1
0



3
0



0  b= 1 
3
1

I Não! Os custos relativos são ≥ 0.
p̄T a5
i
0
I É possı́vel melhorar essa solução?
2.30
−1
p̄T = cT
=
BB
h
−2
=

b =  0.08 
#
T
−3
c
= 0.78
I Ou seja, a solução dual é factı́vel.
I Portanto: solução ótima encontrada!
I x? = (4.62, 2.3, 0, 0.08, 0);
I f (x? ) = cT x = −18.46;
B B
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
x5 =0
C
D
x4 =0
A
E
6
7.5
10
x1
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
x5 =0
C
D
x4 =0
A
E
6
7.5
10
x1
Método simplex
Iteração 1: B = {3, 4, 5} e N = {1, 2};


1
B=  0
0
0
1
0
0
0  = B −1
1
T
h
i
−3
−2
0
0
0
0.5

A =  0.1
0.4
0.3
0.2
0.5
1
0
0
0
1
0



3
0



0  b= 1 
3
1
c
=


x̄B = B
−1
3

b=1
3
I Teste da razão:
−1
p̄T = cT
=
BB
0 0 0
s̄1 = c1 − p̄T a1 = − 3
s̄2 = c2 − p̄T a2 = − 2

y=B
−1

0.5
a1 =  0.1 
0.4
x̄B1
3 x̄B2
1 x̄B3
3
=
;
=
;
=
.
y1
0.5 y2
0.1 y3
0.4
I min:
x̄B1
y1
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
x5 =0
C
D
x4 =0
A
E
6
7.5
10
x1
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
x5 =0
C
D
x4 =0
A
E
6
7.5
10
x1
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
x5 =0
C
D
x4 =0
A
E
6
7.5
10
x1
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
x5 =0
C
D
x4 =0
A
E
6
7.5
10
x1
Método simplex
Iteração 1: B = {3, 4, 5} e N = {1, 2};


1
B=  0
0
0
1
0
0
0  = B −1
1
T
h
i
−3
−2
0
0
0
0.5

A =  0.1
0.4
0.3
0.2
0.5
1
0
0
0
1
0



3
0



0  b= 1 
3
1
c
=


x̄B = B
−1
3

b=1
3
I Teste da razão:
−1
p̄T = cT
=
BB
0 0 0
s̄1 = c1 − p̄T a1 = − 3
s̄2 = c2 − p̄T a2 = − 2

y=B
−1

0.5
a1 =  0.1 
0.4
x̄B1
3 x̄B2
1 x̄B3
3
=
;
=
;
=
.
y1
0.5 y2
0.1 y3
0.4
I min:
x̄B1
y1
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
x5 =0
C
D
x4 =0
A
E
6
7.5
10
x1
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
x5 =0
C
D
x4 =0
A
E
6
7.5
10
x1
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
x5 =0
C
D
x4 =0
A
E
6
7.5
10
x1
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
x5 =0
C
D
x4 =0
A
E
6
7.5
10
x1
Método simplex
Iteração 2: B = {1, 4, 5} e N = {3, 2};



0.5
B =  0.1
0.4
0
1
0
0
2
0  B −1 =  −0.2
1
−0.8
0
1
0

0
0 
1
T
h
i
−3
−2
0
0
0
0.5

A =  0.1
0.4
0.3
0.2
0.5
1
0
0
0
1
0



3
0



0  b= 1 
3
1
c
=


x̄B = B
−1
6

b =  0.4 
0.6
I Teste da razão:
−1
p̄T = cT
=
BB
−6 0 0
s̄3 = c3 − p̄T a3 =

y=B
6
s̄2 = c2 − p̄T a2 = − 0.2
−1

0.6
a2 =  0.14 
0.26
x̄B1
6 x̄B2
0.4 x̄B3
0.6
=
;
=
;
=
.
y1
0.6 y2
0.14 y3
0.26
I min:
x̄B3
y3
⇒ x5 sairá da base.
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
x5 =0
C
D
x4 =0
A
E
6
7.5
10
x1
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
x5 =0
C
D
x4 =0
A
E
6
7.5
10
x1
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
x5 =0
C
D
x4 =0
A
E
6
7.5
10
x1
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
x5 =0
C
D
x4 =0
A
E
6
7.5
10
x1
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
x5 =0
C
D
x4 =0
A
E
6
7.5
10
x1
Método simplex
Iteração 3: B = {1, 4, 2} e N = {3, 5};
"
"
#
B=
0.5
0
0.3
0.1
1
0.2
0.4
0
0.5
B −1 =
3.84
0
−2.30
0.23
1
−0.54
−3.07
0
3.84

x̄B = B
−1
4.62
−5.36 0 −0.78
s̄3 = c3 − p̄T a3 = 5.36
s̄5 = c5 −
0
0
0.5

A =  0.1
0.4
0.3
0.2
0.5
1
0
0
0
1
0



3
0



0  b= 1 
3
1

I Não! Os custos relativos são ≥ 0.
p̄T a5
i
0
I É possı́vel melhorar essa solução?
2.30
−1
p̄T = cT
=
BB
h
−2
=

b =  0.08 
#
T
−3
c
= 0.78
I Ou seja, a solução dual é factı́vel.
I Portanto: solução ótima encontrada!
I x? = (4.62, 2.3, 0, 0.08, 0);
I f (x? ) = cT x = −18.46;
B B
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
x5 =0
C
D
x4 =0
A
E
6
7.5
10
x1
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
x5 =0
C
D
x4 =0
A
E
6
7.5
10
x1
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
x5 =0
C
D
x4 =0
A
E
6
7.5
10
x1
Método simplex
. Ilustração
x2
10
x3 =0
Para x = (x1 , x2 , x3 , x4 , x5 ):
I A: (0, 0, 3, 1, 3)
I B: (0, 5, 1.5, 0, 0.5)
I C: (3.33, 3.33, 0.33, 0, 0)
I D: (4.62, 2.3, 0, 0.08, 0)
I E: (6, 0, 0, 0.4, 0.6)
6
5
B
I Observe que não foi preciso
x5 =0
C
enumerar todos os pontos
extremos!
D
x4 =0
A
E
6
7.5
10
x1
Método simplex: Algoritmo (incompleto)
Entrada: B e N tal que B = AB é invertı́vel e B −1 b ≥ 0.
Passo 1: Calcular a solução básica primal: x̄B = B −1 b, x̄N = 0;
−1 , s̄ = c − p̄T a , ∀j ∈ N ;
Passo 2: Calcular a solução básica dual: p̄T = cT
j
j
j
BB
Passo 3: Determinar s̄k = min s̄j ;
j∈N
Passo 4: Se s̄k ≥ 0, então PARE! Solução ótima encontrada;
Senão, xk irá entrar na base;
Passo 5: Calcular y = B −1 ak ;
x̄
x̄B
Bi
l
Passo 6: Teste da razão:
| yi > 0 ;
= min
yl
yi
x̄B irá sair da base.
l
Passo 7: Atualizar B e N e voltar para o Passo 1.
Método simplex
. Exercı́cio
Resolva o seguinte problema pelo método simplex:
max
x1 + 2x2
s.a
x1 + x2 ≤ 6
x1 − x2 ≤ 4
−x1 + x2 ≤ 4
x1 ≥ 0, x2 ≥ 0
Método simplex
. Exercı́cio
min
5w1 + 6w2 + 3w3
s.a
5w1 + 5w2 + 3w3 ≥ 50
1w1 + 1w2 − 1w3 ≥ 20
7w1 + 6w2 − 9w3 ≥ 30
5w1 + 5w2 + 5w3 ≥ 35
2w1 + 4w2 − 15w3 ≥ 10
12w1 + 10w2 + 0w3 ≥ 90
0w1 + 1w2 − 10w3 ≥ 20
w1 , w2 , w3 ≥ 0
Método simplex
. Exercı́cio
max
2x1 + 2x2
s.a
−x1 + x2 ≤ 3
2x1 − 3x2 ≤ 3
x1 ≥ 0, x2 ≥ 0
Método simplex
Iteração 1: B = {3, 4} e N = {1, 2};
1 0
B=
= B −1
0
c
T
=
A=
1
h
−2
−2
0
0
"
−1
2
1
−3
1
0
0
1
i
#
"
b=
3
3
#
xB = B −1 b =
3
3
−1
p T = cT
=
BB
0 0
I s1 < 0 ⇒ x1 entra na base.
I Teste da razão:
y = B −1 a1 =
s1 = c1 − pT a1 = − 2
s2 = c2 − pT a2 = − 2
x̄Bl
yl
= min
−1
2
x̄Bi
x̄B2
3
| yi > 0 =
=
yi
y2
2
I B2 = 4 ⇒ x4 sai da base.
Método simplex
Iteração 2: B = {3, 1} e N = {4, 2};
1 0.5
B −1 =
0
0.5
c
T
=
A=
h
−2
−2
0
0
"
−1
2
1
−3
1
0
0
1
i
#
"
b=
3
3
#
xB = B −1 b =
4.5
1.5
−1
pT = cT
=
BB
0 −1
s4 = c4 − pT a4 =
I Teste da razão:
y = B −1 a2 =
1
s2 = c2 − pT a2 = − 5
x̄Bl
yl
= min
I E agora?
−0.5
−1.5
x̄Bi
| yi > 0
yi
= min ∅
Método simplex
Iteração 2: B = {3, 1} e N = {4, 2};
1 0.5
B −1 =
0
0.5
c
T
=
A=
h
−2
−2
0
0
"
−1
2
1
−3
1
0
0
1
i
#
"
b=
3
3
#
xB = B −1 b =
4.5
1.5
−1
pT = cT
=
BB
0 −1
s4 = c4 − pT a4 =
I Teste da razão:
y = B −1 a2 =
1
s2 = c2 − pT a2 = − 5
x̄Bl
yl
= min
I x2 → ∞
−0.5
−1.5
x̄Bi
| yi > 0
yi
= min ∅
Método simplex
Iteração 2: B = {3, 1} e N = {4, 2};
1 0.5
B −1 =
0
0.5
c
T
=
A=
h
−2
−2
0
0
"
−1
2
1
−3
1
0
0
1
i
#
"
b=
3
3
#
xB = B −1 b =
4.5
1.5
−1
pT = cT
=
BB
0 −1
s4 = c4 − pT a4 =
I Teste da razão:
y = B −1 a2 =
1
s2 = c2 − pT a2 = − 5
x̄Bl
yl
= min
−0.5
−1.5
x̄Bi
| yi > 0
yi
I PARE! Problema ilimitado.
= min ∅
Método simplex
. Solução gráfica: Casos particulares
x2
6
max
s.a
f (x1 , x2 ) = 2x1 + 2x2
−x1 + x2 ≤ 3
2x1 − 3x2 ≤ 3
x1 ≥ 0, x2 ≥ 0.
. Solução ilimitada
-5
4
-1
x1
Método simplex: Algoritmo
Entrada: B e N tal que B = AB é invertı́vel e B −1 b ≥ 0.
Passo 1: Calcular a solução básica primal: x̄B = B −1 b, x̄N = 0;
−1 , s̄ = c − p̄T a , ∀j ∈ N ;
Passo 2: Calcular a solução básica dual: p̄T = cT
j
j
j
BB
Passo 3: Determinar s̄k = min s̄j ;
j∈N
Passo 4: Se s̄k ≥ 0, então PARE! Solução ótima encontrada;
Senão, xk irá entrar na base;
Passo 5: Calcular y = B −1 ak ;
Passo 6: Se y ≤ 0, então PARE! Problema ilimitado;
x̄
x̄B
Bi
l
Passo 7: Teste da razão:
= min
| yi > 0 ;
yl
yi
x̄B irá sair da base.
l
Passo 8: Atualizar B e N e voltar para o Passo 1.
Método simplex
. Exercı́cio
Encontre três soluções ótimas pelo método simplex:
min
−1x1 − 2x2
s.a
0.5x1 + 0.3x2 ≤ 3
0.1x1 + 0.2x2 ≤ 1
0.4x1 + 0.5x2 ≤ 3
x1 ≥ 0, x2 ≥ 0
I
Obrigado pelo atenção!
I
Dúvidas?
I
Próxima aula:
I
Inicialização, Método dual simplex e análise de sensibilidade.

slides

Transcrição

Documentos relacionados

MÉTODO ASCENSIONAL VORONANDECK E MELCHIZEDECK 1

( JJJ) t?J~ J - BCo - Universidade Federal de São Carlos

ASTROLOGIA EMPRESARIAL pdf

ementa da disciplina: representação gráfica

DUALIDADE HISTÓRICA E PERSPECTIVAS DE INTEGRAÇÃO

ADUFSCar - Objetivos

Pesquisa Operacional - Ceplan

edital - PPGGEv - Universidade Federal de São Carlos

3- O MÉTODO SIMPLEX 3.1- Introdução O Método

Coleção UAB−UFSCar A Matemática na formação de