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