Troca de variáveis – método de Gauss-Jordan - DT
Transcrição
Troca de variáveis – método de Gauss-Jordan - DT
2.9. Sistemas de equações lineares 45 poliedrais, exibindo pontos extremos, arestas e, eventualmente, faces, se poliedros no Rn , n ≥ 3, forem condiderados. Outra caracterı́stica importante, ilustrada na Figura 2.9, é a adjacência das soluções básicas viáveis. Partindo da solução básica viável I, obtém-se a solução básica viável II, adjacente a I, por meio de uma troca conveniente de uma variável básica por uma variável não-básica, e assim sucessivamente, até que todas as soluções básicas viáveis sejam percorridas. Troca de variáveis – método de Gauss-Jordan Considere o problema de, dada uma solução básica qualquer, obter uma solução básica alternativa de forma computacionalmente eficiente. Este problema pode ser abordado por meio do método de Gauss-Jordan para solução de sistemas de equações lineares do tipo Ax = b, sendo A uma matriz quadrada nãosingular. O método de Gauss-Jordan pode ser estendido a sistemas de equações lineares com m ≤ n e rank A = m. Uma operação particular do método, conhecida como pivoteamento, é ilustrada a seguir. Exemplo 2.19 Considere o seguinte sistema de equações lineares: x1 −x1 + + 2x2 2x2 x2 + x3 − x3 + x3 − + 2x4 x4 = = = 10, 6, 2. O sistema de equações pode ser representado na forma de uma matriz de coeficientes como .. .. I 1 2 1 . −2 . 10 h i .. M = B ... N ... b = −1 2 −1 ... . 1 . 6 . . 0 1 1 .. 0 .. 2 Inicialmente soma-se as duas primeiras linhas de M e armazena-se o resultado na segunda linha. Obtém-se .. .. 1 2 1 . −2 . 10 M1 = 0 I 4 0 ... −1 ... 16 . . . 0 1 1 .. 0 .. 2 O elemento da matriz M indicado por (I) funcionou como elemento-pivot. A operação que resultou na primeira coluna de M1 é chamada de pivoteamento. O segundo elemento pivot encontra-se indicado na matriz M1 . Inicialmente divide-se a segunda linha de M1 por 4. Multiplica-se a nova segunda linha por −2, soma-se o resultado à primeira linha e armazena-se a soma na primeira linha; multiplica-se a nova segunda linha por −1, soma-se o resultado à terceira linha e armazena-se a 46 Capı́tulo 2. Programação Linear soma na terceira linha. Obtém-se 1 1 0 M2 = 0 1 0 0 0 I1 .. . .. . .. . .. . .. . .. . −6/4 −1/4 1/4 2 . 4 −2 O terceiro elemento pivot encontra-se indicado na matriz M2 . Multiplica-se a terceira linha de M2 por −1, soma-se o resultado à primeira linha e armazena-se a soma na primeira linha, para obter a matriz final: .. .. 1 0 0 . −7/4 . 4 M3 = 0 1 0 ... −1/4 ... . 4 . . 0 0 1 .. I 1/4 .. −2 O sistema de equações original foi manipulado até atingir a forma x1 x2 x3 − (7/4)x4 − (1/4)x4 + (1/4)x4 = = = 4, 4, −2. xB 3 = −2 e xN 4 = 0. A solução básica indicada é xB 2 = 4, xB 1 = 4, Suponha que as variáveis x3 e x4 devam ser transformadas em variáveis não-básica e básica, respectivamente. A transformação desejada pode ser obtida aplicando-se o método de Gauss-Jordan ao elemento pivot indicado na matriz M 3 . A idéia é transformar a quarta coluna de M3 numa coluna idêntica à terceira coluna, associada à variável x3 . No processo, a terceira coluna de M3 transforma-se numa coluna não-básica. Com o pivoteamento, obtém-se .. .. 1 0 7 . 0 . −10 M4 = 0 1 1 ... 0 ... , 2 .. .. 0 0 4 . 1 . −8 correspondente ao sistema de equações x1 x2 + + + 7x3 x3 4x3 + x4 = = = −10, 2, −8. A nova solução básica é xB 1 = 10, xB 2 = 2, xB 4 = −8 e xN 3 = 0. 2 2.10. O método Simplex 2.10 47 O método Simplex O método Simplex para solução de problemas de programação linear explora o fato de que se um dado problema possui uma solução viável ótima, então o problema possui uma solução básica viável ótima. O método Simplex percorre as soluções básicas viáveis do problema até que uma solução básica viável ótima seja identificada. Para tanto, o método Simplex utiliza três procedimentos principais, detalhados em seguida. 1. Determinação de uma solução básica inicial viável; 2. Determinação da variável não-básica que se torna básica; 3. Determinação da variável básica que se torna não-básica. Determinação da variável básica que se torna não-básica A técnica de pivoteamento do método de Gauss-Jordan pode ser adaptada para resolver o seguinte problema: dada uma solução básica viável, suponha que uma variável não-básica deva ser transformada numa variável básica. Qual variável deve deixar de ser básica de forma que a nova solução básica também seja viável ? Na discussão deste problema assume-se que o sistema de equações Ax = b encontrase na forma x1 x2 .. . xm + + .. . y1,m+1 xm+1 y2,m+1 xm+1 .. . + + .. . + ym,m+1 xm+1 + ··· ··· ··· ··· + + .. . y1,n xn y2,n xn .. . = = .. . y1,0 , y2,0 , .. . + y2,n xn = ym,0 . (2.24) A obtenção da forma canônica (2.24) faz parte do procedimento de obtenção de uma solução básica inicial viável, a ser discutido posteriormente. Supõe-se que yi,0 > 0 para todo i = 1, 2, . . . , m, de tal maneira que a solução básica correspondente é viável e não-degenerada: xB xB . . . , xB 1 = y1,0 , 2 = y2,0 , m = ym,0 ; N N N xm+1 = xm+2 = · · · = xn = 0. Seja xq , q ≥ m+1, a variável não-básica a ser transformada em variável básica. É possı́vel expressar as variáveis básicas em termos de xq da seguinte maneira: x1 = y1,0 − y1,q xq , x2 = y2,0 − y2,q xq , .. . xm = ym,0 − ym,q xq . 48 Capı́tulo 2. Programação Linear Inicialmente, xq = 0, obtendo-se a solução básica inicial viável. Quando xq aumenta a partir de zero, a forma como os valores das variáveis x1 , x2 , . . . , xm variam depende dos valores dos yi,q ’s: yi,q > 0 : xi tende a dinimuir; yi,q = 0 : xi fica inalterada; yi,q < 0 : xi tende a aumentar. A situação yi,q ≤ 0 não leva à inviabilidade da solução porque xi permance positivo quando xq cresce. Entretanto as variáveis tais que yi,q > 0 tendem a zero; seus valores devem deixar de diminuir quando uma ou mais dessas variáveis atingir o valor zero. As variáveis que primeiro atingem o valor zero são aquelas associadas à menor razão entre os yi,0 ’s e yi,q ’s para yi,q ’s positivos: yi,0 , yi,q > 0 . min i yi,q Se a menor razão estiver associada a uma única variável básica, por exemplo xp (1 ≤ p ≤ m), então xq (agora positiva e básica) substitui xp (agora nula e nãobásica) na nova solução básica viável não-degenerada. Se a menor razão estiver associada a duas ou mais variáveis básicas, por exemplo xp e xs , então xq substitui xp (ou xs ) e xs (ou xp ) permanecerá como váriável básica igual a zero. Neste caso, a nova solução básica viável será degenerada. Exemplo 2.20 Considere o sistema de equações lineares na forma canônica x1 x2 x3 + 2x4 + x4 − x4 + 4x5 + 2x5 + 2x5 + 6x6 + 3x6 + x6 = 4, = 3, = 1. A solução básica viável inicial é xB xB xB 3 = 1, 2 = 3, 1 = 4, N N N x4 = x4 = x6 = 0. Suponha que a variável x5 deva ser transformada em variável básica. A variável a ser transformada em variável não-básica é determinada calculando-se 4 3 1 min , , . 4 2 2 A menor razão está associada à variável x3 . A troca de solução básica é realizada através de pivoteamento aplicado ao coeficiente de x5 na terceira equação. Executando a operação de pivoteamento, obtém-se o sistema x1 x2 − − + 2x3 2x3 (1/2)x3 + + − 4x4 2x4 (1/2)x4 + x5 + + + 4x6 2x6 (1/2)x6 = = = 2, 2, 1/2. 2.10. O método Simplex 49 A nova solução básica viável é xB 2 = 2, xB 1 = 2, xN 3 = xN 4 = xN 6 xB 5 = 1/2, = 0. 2 Determinação da variável não-básica que se torna básica Dada uma solução básica viável, e definido que uma variável não-básica deve se tornar básica, sabe-se agora como realizar a troca de solução básica mantendo a viabilidade da solução. Discute-se a seguir o critério para definir qual variável não-básica deve se tornar básica. Custos relativos A transformação de uma variável não-básica em básica é vantajosa apenas se a nova solução básica viável diminuir o valor da função-objetivo do problema linear considerado. Para saber a priori quando a transformação de uma variável não-básica em básica irá diminuir o valor da função-objetivo, é necessário calcular os custos relativos das variáveis de decisão, como discutido a seguir. A função-objetivo do problema pode ser expressa como z = c 1 x1 + c 2 x2 + c n xn , X X = ci xi + , i∈I (2.25) (2.26) j∈J = c B xB + c N xN . (2.27) Convém lembrar que I e J são os conjuntos de ı́ndices das variáveis básicas e não-básicas, respectivamente. Na terceira expressão para z, os custos básicos e não-básicos foram reunidos nos vetores cB ∈ R1×m e cN ∈ R1×(n−m) , de forma a representar z em termos matriciais. Lembre-se também que o sistema de equações Ax = b pode ser reescrito como BxB + N xN = b. Como B é não-singular, xB = B −1 b − B −1 N xN . Substituindo xB na função objetivo, obtém-se z = cB (B −1 b − B −1 N xN ) + cN xN = cB B −1 b + (cN − cB B −1 N )xN . Se xN = 0, então xB = B −1 b e z0 = cB B −1 b é o valor da função-objetivo na solução básica corrente. É possı́vel então expressar z na forma X rj xN z = z0 + rxN = z0 + j , j∈J 50 Capı́tulo 2. Programação Linear com r = cN −cB B −1 N representando um vetor de dimensão 1×(n−m) denominado de vetor de custos relativos das variáveis não-básicas. Os custos relativos das variáveis básicas são todos iguais a zero. O efeito de se transformar uma variável não-básica em básica, descolando seu valor de zero e mantendo todas as demais variáveis não-básicas em zero, depende do custo relativo associado: rj > 0 : z > z0 ; rj = 0 : z = z0 ; rj < 0 : z < z0 . As variáveis não-básicas candidatas a se tornarem básicas são apenas aquelas cujos custos relativos são negativos, porque neste caso o valor da função-objetivo torna-se inferior ao valor corrente, z0 . Exemplo 2.21 Considere o problema de programação linear na forma padrão minimizar z = 2x1 + x2 , sujeito a x1 + x2 + x3 = 6, x2 + x4 = 3, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0. As seguintes associações são possı́veis: 1 1 1 0 B= , N= , cB = 2 0 1 0 1 1 e cN = 0 0 . O vetor de custos relativos das variáveis não-básicas (x3 e x4 ) é dado por 1 −1 1 0 −1 r = c N − cB B N = 0 0 − 2 1 , 0 1 0 1 = −2 1 . Os valores das variáveis básicas são 1 −1 6 3 B −1 x =B b= = . 0 1 3 3 O valor da função-objetivo na base corrente é z0 = cB B −1 b = 9. Portanto, z = z0 + r3 x3 + r4 x4 = 6 − 2x3 + x4 . A transformação de x3 em variável básica leva à diminuição do valor da funçãoobjetivo. 2