Baixe o app para aproveitar ainda mais
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
Compartilhar