aula2609casosEspeciais

Prévia do material em texto

3a. iteração Base ótima (B1, B2, B3) = (2, 1, 5) (N1, N2) = (4, 3) 
Exemplo: Simplex
Minimizar f(x1, x2) = − x1 − x2 
sujeito a: x1 + x2 ≤ 6 
 x1 − x2 ≤ 4 
 −x1+ x2 ≤ 4 
 x1 ≥ 0, x2 ≥ 0. 
• solução básica: xB = (x2, x1, x5) 
Resolva o sistema BxB = b, cuja matriz aumentada é dada por: 










−
−
4
4
6
111
011
011
, 
que pode ser resolvido pelo método de eliminação de Gauss, cuja solução é 










=
8
5
1
Bxˆ e a função objetivo vale f( xˆ ) = − 6. 
Exemplo: Simplex
• otimalidade: 
i) vetor dual: ( =)(
321 BBB
c,c,c (c2, c1, c5) = (−1, −1, 0)) 
Resolva o sistema BTλλλλ = cB, cuja matriz aumentada é dada por 










−
−
−
−
0
1
1
100
111
111
, 
e cuja solução é λλλλT = [−1 0 0]. 
Exemplo: Simplex (soluções 
múltiplas
ii) custos relativos: (N1 = 4, N2 = 3) 
04
T
44 =−= aλccˆ 
13
T
33 =−= aλccˆ 
Como jcˆ ≥ 0 para todas variáveis não básicas, segue que a solução 
atual 










=










=
8
5
1
5
1
2
x
x
x
ˆ Bx e 





=





=
0
0
3
4
x
x
ˆ Nx 
ou 
















=
















=
8
0
0
1
5
5
4
3
2
x
x
x
x
x
ˆ
1
x é ótima. 
6xx06)(f 34 −≥++−=x , para todo x4 ≥ 0 e x3 ≥ 0. 
f(x) = − 6, para todo x4 > 0 e x3 = 0, ou seja, a solução básica pode ser alterada com valores 
não nulos para x4, sem que a função objetivo se altere. 
 
Portanto, o problema tem múltiplas soluções ótimas, as quais podem ser determinadas por 
se atribuir valores diferentes a x4. 
Exemplo: Simplex (Múltiplas 
soluções e solução degenerada)
6xx06)(f 34 −≥++−=x , para todo x4 ≥ 0 e x3 ≥ 0. 
f(x) = − 6, para todo x4 > 0 e x3 = 0, ou seja, a solução básica pode ser alterada com valores 
não nulos para x4, sem que a função objetivo se altere. 
 
Portanto, o problema tem múltiplas soluções ótimas, as quais podem ser determinadas por 
se atribuir valores diferentes a x4. 
Se a solução básica ótima fosse degenerada (alguma variável básica nula), então com o 
aumento de x4, poderia ocorrer que uma variável básica nula ficasse negativa, de modo que 
x4 não poderia assumir valores diferentes de zero. 
Isto é, suponha que a i-ésima variável básica seja nula, ou seja, 
i
xˆB = 0, então 
εiBB yxx ii −= ˆ = εiy− . Portanto, se yi > 0 e caso ε > 0, então ixB < 0 e, portanto, a solução 
se torna infactível. 
Neste caso, o problema não apresenta múltiplas soluções ótimas, apesar de um custo 
relativo nulo na otimalidade . 
A existência de custos relativos nulos é condição necessária para múltiplas soluções ótimas, mas não é suficiente
Exemplo: Simplex (solução 
ilimitada
Minimizar f(x1, x2) = − x1 − x2 
sujeito a: x1 − x2 ≤ 4 
 −x1 + x2 ≤ 4 
 x1 ≥ 0, x2 ≥ 0. 
 x1 X2 x3 x4 B 
A 1 
−1 1 0 4 
−1 1 0 1 4 
Min f 
−1 −1 0 0 
 
Na forma padrão 
Exemplo: Simplex (solução 
ilimitada
Minimizar f(x1, x2) = − x1 − x2 
sujeito a: x1 − x2 ≤ 4 
 −x1 + x2 ≤ 4 
 x1 ≥ 0, x2 ≥ 0. 
 x1 X2 x3 x4 B 
A 1 
−1 1 0 4 
−1 1 0 1 4 
Min f 
−1 −1 0 0 
Na forma padrão 
A partir da partição básica inicial: 
 (B1, B2) = (3, 4) (N1, N2) = (1, 2). 
Na segunda iteração do método simplex obtemos: 
Exemplo: Simplex (solução 
ilimitada
2a. Iteração (B1, B2) = (1, 4) (N1, N2) = (3, 2) 
• solução básica: xB = (x1, x4)T 
Resolva o sistema BxB = b, cuja matriz aumentada é 





− 4
4
11
01
 e sua solução é 






=
8
4
Bxˆ e a função objetivo é f( xˆ )= 480412 −=×+×−=+ BBBB xˆcxˆc 211 
• otimalidade: 
i) multiplicador simplex: (cB = TBB c,c )( 21 =(c1, c4) = (−1, 0)) 
Resolva o sistema BTλλλλ = cB, cuja matriz aumentada é 




 −
− 0
1
11
01
 e obtenha 
λλλλ = 





−
−
1
1
. 
ii) custos relativos: (N1 = 3, N2 = 2) 
1333 =−= aλ
Tccˆ 
1222 −=−= aλ
Tccˆ ← k=2 (x2 entra na base) 
 A função objetivo em termos das variáveis não básicas é f(x) = 0 +1x3 − 1x2 
Exemplo: Simplex (solução 
ilimitada
• direção simplex 
 Resolva o sistema By = a2, cuja matriz aumentada é 




 −
− 1
1
11
01
 e obtenha 
y = 




−
0
1
. 
Temos então que, se aumentamos o valor da variável x2, a função objetivo
decresce (custo relativo negativo).
Note que x2 pode crescer indefinidamente, já que a direção simplex 
não tem componentes positivas 
(direções deste tipo são chamados raios da região factível). 
Exercício: Problema 
degenerado
Resolva o problema 
Min Z=-5x1-2x2 
Sujeito a: 
X1 <=3 
X2<=4 
4x1+3x2<=12 
x1>=0,x2>=0