Programação linear

Prévia do material em texto

36 Cap´ıtulo 2. Programac¸a˜o Linear
Dada uma matriz A de ordem n, se existir uma matriz B, tambe´m de ordem
n, tal que
AB = BA = I,
enta˜o que B e´ a matriz inversa de A. Existindo, a inversa de A e´ u´nica. E´ comum
representar a inversa de A como A−1.
O menor ij de uma matriz quadrada A de ordem n e´ a submatriz denotada
por Aij obtida deletando-se a i-e´sima linha e a j-e´sima coluna de A. O determi-
nante de A e´ o escalar representado como det A ou | A |, definido recursivamente
da seguinte forma: se n = 1, enta˜o
det A = a11.
Se n = 2,
det A = a11a22 − a21a12.
Se n > 2, seleciona-se qualquer linha i e enta˜o
detA = (−1)i+1ai1(det Ai1) + (−1)
i+2ai2(det Ai2)+
· · ·+ (−1)i+nain(det Ain). (2.16)
A quantidade det Aij e´ o cofator ij da matriz A e (2.16) e´ chamada de
expansa˜o pelos cofatores da linha i de A. A matriz cofatora de A e´ a matriz
definida como cof A = {det Aij}. Finalmente, a matriz adjunta de A e´ dada por
adj A = (cof A)T .
Uma matriz A de ordem n e´ singular se det A = 0. A inversa de uma matriz
A existe se e somente se A e´ na˜o-singular, ou seja, se det A 6= 0. Neste caso, A−1
pode ser calculada pela expressa˜o
A−1 =
adj A
detA
.
Rank
Considere uma matriz A ∈m×n definida por meio de vetores-colunas:
A =
[
a:1
... a:2
... · · ·
... a:n
]
,
aT:j =
[
a1j a2j · · · amj
]
, j = 1, 2, . . . , n.
Alternativamente e´ possivel representar A por meio de vetores-linhas:
A =


a1:
. . .
a2:
. . .
...
. . .
am:


,
2.9. Sistemas de equac¸o˜es lineares 37
ai: =
[
ai1 ai2 · · · ain
]
, i = 1, 2, . . . ,m.
O rank ou poˆsto de A ∈ Rm×n, denotado como rank A, e´ igual ao nu´mero
ma´ximo de colunas linearmente independentes de A. Como e´ poss´ıvel mostrar
que rank A = rank AT , o rank de A tambe´m pode ser definido como o nu´mero
ma´ximo de linhas linearmente independentes de A. Desta propriedade se conclui
que rank A = min{m,n}. O rank de uma matriz nula e´ igual a zero.
Exemplo 2.13 Considere a seguinte matriz de dimensa˜o 3× 4:
A =

 1 1 1 01 1 0 1
1 1 1 0

 .
A matriz possui quatro colunas, mas a primeira e a segunda colunas podem
ser obtidas somando-se a terceira e a quarta. Existem no ma´ximo duas colunas
linearmente independentes. Portanto, rankA = 2. Alternativamente, a primeira
e a terceira linhas sa˜o linearmente dependentes. Existem no ma´ximo duas linhas
linearmente independentes, e, novamente, rank A = 2. 2.
Um importante resultado para matrizes quadradas estabelece que A ∈ Rn×n
e´ invert´ıvel se e somente se rank A = n, isto e´, se todas as n colunas (n linhas) de
A sa˜o linearmente independentes.
2.9 Sistemas de equac¸o˜es lineares
Considere o sistema linear com m equac¸o˜es e n inco´gnitas a seguir. Os aij ’s e
bi’s sa˜o quantidades dadas. Assuma que m ≤ n.∣∣∣∣∣∣∣∣∣
a11x1 + a12x2 + · · ·+ a1nxn = b1,
a21x1 + a22x2 + · · ·+ a2nxn = b2,
...
am1x1 + am2x2 + · · ·+ amnxn = bm,
(2.17)
Definindo
A =


a11 a12 · · · a1n
a21 a22 · · · a2n
...
...
. . .
...
am1 am2 · · · amn

 , x =


x1
x2
...
xn

 e b =


b1
b2
...
bm

 ,
obte´m-se a forma matricial do sistema (2.17):
Ax = b. (2.18)
Se A for representada por meio das suas colunas a:1, a:2, . . . , a:n, o sistema
assume a forma alternativa
a:1x1 + a:2x2 + · · ·+ a:nxn = b. (2.19)
38 Cap´ıtulo 2. Programac¸a˜o Linear
E´ poss´ıvel interpretar o lado esquerdo de (2.19) como uma combinac¸a˜o linear
das colunas de A, com x1, x2, . . . , xn fazendo o papel dos escalares da combinac¸a˜o.
Assim, (2.17) ((2.18), (2.19)) possui soluc¸a˜o se b pode ser escrito como combinac¸a˜o
linear das colunas de A. Na discussa˜o a seguir, assume-se que rankA = m
Se m = n, enta˜o m colunas linearmente independentes de A formam uma base
e qualquer vetor b pode ser escrito como combinac¸a˜o linear destas colunas de A.
Como a representac¸a˜o de b nesta base e´ u´nica, a soluc¸a˜o de (2.17) tambe´m e´ u´nica.
Se m < n, enta˜o (2.17) exibe infinitas soluc¸o˜es.
Exemplo 2.14 Considere o sistema representado por
A =
[
1 2 2
2 1 1
]
, x =

 x1x2
x3

 e b =
[
4
4
]
. (2.20)
Na forma de colunas,[
1
2
]
x1 +
[
2
1
]
x2 +
[
2
1
]
x3 =
[
4
4
]
.
Observe que rank A = m = 2 < 3 = n. Como a segunda e a terceira colunas
de A sa˜o iguais (linearmente dependentes), pode-se escrever
[
1
2
]
x1 +
[
2
1
]
(x2 + x3) =
[
4
4
]
.
Restam m = 2 colunas linearmente independentes da matriz A e a ana´lise se
reduz ao caso m = n com rank A = m. A soluc¸a˜o u´nica do sistema reduzido e´
x1 = 4/3 e x2 + x3 = 4/3. Como existem infinitas maneiras de se escolher x2 e x3
tais que x2 + x3 = 4/3, o sistema (2.20) possui infinitas soluc¸o˜es. 2
Sistemas de equac¸o˜es lineares com m < n e rank A = m sa˜o particularmente
importantes por estarem presentes na maioria dos problemas de programac¸a˜o linear
na forma padra˜o, reescrita aqui por convenieˆncia:
∣∣∣∣∣∣∣∣∣∣∣∣∣
minimizar z = c1x1 + c2x2 + · · · + cnxn
sujeito a a11x1 + a12x2 + · · · + a1nxn = b1,
a21x1 + a22x2 + · · · + a2nxn = b2,
...
...
...
...
am1x1 + am2x2 + · · · + amnxn = bm,
x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0.
(2.21)
Introduzindo o vetor adicional
c =
[
c1 c2 · · · cn
]
,
expressando a func¸a˜o objetivo como o produto z = cx e representando as restric¸o˜es
de na˜o-negatividade como x ≥ 0, no sentido de que cada componente do vetor de
2.9. Sistemas de equac¸o˜es lineares 39
varia´veis de decisa˜o deve ser na˜o-negativa, obte´m-se a representac¸a˜o matricial de
(2.21):
∣∣∣∣∣∣
minimizar z = cx,
sujeito a Ax = b,
x ≥ 0.
(2.22)
O exemplo a seguir relembra as operac¸o˜es necessa´rias para se obter a forma
padra˜o de um problema de programac¸a˜o linear. A forma matricial do problema e´
obtida em seguida.
Exemplo 2.15 Obtenha a forma matricial do problema de programac¸a˜o linear
∣∣∣∣∣∣∣∣
maximizar z = x1 − 2x2 − 3x3,
sujeito a x1 + 2x2 + x3 ≤ 14,
x1 + 2x2 + 4x3 ≥ 12,
x1 − x2 + x3 = 2,
com x1 e x2 varia´veis livres e x2 ≤ −3.
As varia´veis livres x1 e x2 sa˜o representadas por varia´veis na˜o-negativas x11,
x12, x21 e x22 como x1 = x11−x12 e x2 = x21−x22. Observe que se −x3 ≥ 3, enta˜o
definindo −x3 − 3 = x31 obtemos a restric¸a˜o na˜o-negativa equivalente x31 ≥ 0. O
problema com varia´veis na˜o-negativas seria
∣∣∣∣∣∣∣∣
maximizar z = x11 − x12 − 2x21 + 2x22 − 3x31 + 9,
sujeito a x11 − x12 + 2x21 − 2x22 − x31 ≤ 17,
x11 − x12 + 2x21 − 2x22 − 4x31 ≥ 0,
x11 − x12 − x21 + x22 − x31 = 5,
com x11 ≥ 0, x12 ≥ 0, x21 ≥ 0, x22 ≥ 0 e x31 ≥ 0. Eliminando a constante 9,
invertendo os sinais dos coeficientes da func¸a˜o-objetivo e renomeando as varia´veis
como x1 = x11, x2 = x12, x3 = x21, x4 = x22 e x5 = x31, obte´m-se a formulac¸a˜o
equivalente
∣∣∣∣∣∣∣∣
minimizar z¯ = −x1 + x2 + 2x3 − 2x4 + 3x5,
sujeito a x1 − x2 + 2x3 − 2x4 − x5 ≤ 17,
x1 − x2 + 2x3 − 2x4 − 4x5 ≥ 0,
x1 − x2 − x3 + x4 − x5 = 5,
com x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 e x5 ≥ 0. Introduzindo x6 ≥ 0 e x7 ≥ 0 como
varia´veis de folga e de excesso na primeira e segunda restric¸o˜es, respectivamente,
chega-se finalmente a` forma padra˜o do problema linear.
Para obter o problema na forma matricial (2.22), basta identificar as matrizes
c, b e A (n = 7 e m = 3). No caso em questa˜o,
c =
[
−1 1 2 −2 3 0 0
]
, b =

 170
5

 ,
40 Cap´ıtulo 2. Programac¸a˜o Linear
e
A =

 1 −1 2 −2 −1 1 01 −1 2 −2 −4 0 −1
1 −1 −1 1 −1 0 0

 .
2
Soluc¸o˜es ba´sicas de sistemas
Considere o sistema de equac¸o˜es lineares (2.17) presente na forma padra˜o da
programac¸a˜o linear. Conforme discutido, o sistema de equac¸o˜es pode ser represen-
tado como Ax = b, A ∈ Rm×n, b ∈ Rm. A restric¸a˜o de na˜o-negatividadex ≥ 0 sera´
reintroduzida oportunamente. Assume-se que rank A = m.
Seja I um conjunto de ı´ndices relativos a m colunas linearmente independentes
de A e J o conjunto complementar de I, no sentido de que I ∪ J = {1, 2, . . . , n}.
Os conjuntos I e J conte´m m e n−m ı´ndices, respectivamente. Em geral existem
va´rias maneiras de se definir I e J . O sistema de equac¸o˜es Ax = b pode ser enta˜o
reescrito como
Ax = a:1x1 + a:2x2 + · · ·+ a:nxn =
∑
i∈I
a:ixi +
∑
j∈J
a:jxj = b.
Suponha que as colunas indicadas em I e em J componham as matrizes
B ∈ Rm×n e N ∈ Rm×(n−m). Agrupando as varia´veis associadas a`s colunas de B e
N nos vetores xB ∈ Rm e xN ∈ Rn−m, respectivamente, o sistema original Ax = b
pode ser reescrito de forma equivalente como
BxB + NxN = b.
Como as m colunas de B sa˜o linearmente independentes, B e´ uma matriz
na˜o-singular, existindo a inversa B−1. Uma poss´ıvel soluc¸a˜o para Ax = b enta˜o
seria xB = B−1b e xN = 0 (xm+1 = xm+2 = · · · = xn = 0). As varia´veis de
decisa˜o em xB e xN sa˜o chamadas de varia´veis ba´sicas e varia´veis na˜o-ba´sicas,
respectivamente. Esta forma de soluc¸a˜o para Ax = b, no qual pelo menos n − m
varia´veis assumem valor nulo, e´ chamada de soluc¸a˜o ba´sica. O sistema Ax = b
apresentara´ tantas soluc¸o˜es ba´sicas quantas forem as maneiras de se selecionar m
colunas linearmente independentes dentre as n colunas de A.
Existeˆncia de soluc¸o˜es ba´sicas
As condic¸o˜es para a existeˆncia de soluc¸o˜es ba´sicas para o sistema de equac¸o˜es
Ax = b sa˜o relativamente fracas: se o nu´mero de equac¸o˜es (linhas de A) e´ menor do
que o nu´mero de inco´gnitas (colunas de A), e se as m linhas de A sa˜o linearmente
independentes, enta˜o Ax = b possui ao menos uma soluc¸a˜o ba´sica.
De fato, se o rank de A e´ igual a m, enta˜o A possui m colunas linearmente
independentes, as quais podem ser escolhidas para formar a matriz ba´sica B. As
demais colunas ira˜o compor a matriz na˜o-ba´sica N .
Dado que A ∈ Rm×n e m < n, de quantas maneiras e´ poss´ıvel selecionar m
colunas de A ? A resposta fornece um limite superior para o nu´mero de soluc¸o˜es
2.9. Sistemas de equac¸o˜es lineares 41
ba´sicas de Ax = b, pois em geral nem toda combinac¸a˜o de m colunas de A conduz
a uma matriz na˜o-singular (base). O nu´mero de combinac¸o˜es poss´ıveis e´(
n
m
)
=
n!
m! (n−m)!
.
Exemplo 2.16 Considere o sistema de equac¸o˜es abaixo.

 1 0 0 4 −2 0 10 −1 0 −2 0 1 5
0 0 1 1 0 0 0




x1
x2
x3
x4
x5
x6
x7


=

 24
6

 .
Observe que m = 3 < 7 = n e que A possui treˆs colunas linearmente inde-
pendentes, as 3 primeiras, por exemplo. Portanto, as treˆs linhas de A sa˜o tambe´m
linearmente independentes. Nem toda combinac¸a˜o de treˆs colunas constitui uma
base – as colunas 1,2 e 5, por exemplo. O nu´mero de soluc¸o˜es ba´sicas e´ menor do
que (
7
3
)
=
7!
3! 4!
=
7 · 6 · 5 · 4!
3! 4!
= 35.
Duas das soluc¸o˜es ba´sicas sa˜o:
Soluc¸a˜o 1: xB1 = 2, x
B
2 = −4, x
B
3 = 3, x
N
4 = x
N
5 = x
N
6 = x
N
7 = 0;
Soluc¸a˜o 2: xB1 = 2, x
B
6 = 4, x
B
3 = 3, x
N
2 = x
N
4 = x
N
5 = x
N
7 = 0.
2
Soluc¸o˜es ba´sicas degeneradas
Diz-se que uma soluc¸a˜o ba´sica e´ degenerada se uma ou mais varia´veis ba´sicas
assume valor nulo. Portanto, uma soluc¸a˜o ba´sica degenerada possui mais do que
n−m varia´veis assumindo valor nulo, dado que as varia´veis na˜o-ba´sicas sa˜o sempre
iguais a zero. E´ deseja´vel trabalhar apenas com soluc¸o˜es ba´sicas na˜o-degeneradas,
porque isso simplifica bastante certos aspectos da implementac¸a˜o do Me´todo Sim-
plex. As soluc¸o˜es ba´sicas do exemplo anterior sa˜o na˜o-degeneradas.
Soluc¸o˜es ba´sicas via´veis
Neste ponto reintroduz-se a restric¸a˜o adicional de na˜o-negatividade x ≥ 0 a`s
soluc¸o˜es de Ax = b. Qualquer soluc¸a˜o via´vel para o problema de programac¸a˜o
linear na forma padra˜o deve satisfazer Ax = b e x ≥ 0. Diz-se enta˜o que x e´ uma
soluc¸a˜o ba´sica via´vel se x for ao mesmo tempo ba´sica e via´vel, isto e´, se x for uma
soluc¸a˜o ba´sica e os valores das varia´veis ba´sicas forem na˜o-negativos. A Soluc¸a˜o 1
do exemplo anterior e´ uma soluc¸a˜o ba´sica invia´vel (x2 < 0); a Soluc¸a˜o 2 e´ via´vel.
Soluc¸o˜es ba´sicas via´veis podem ser degeneradas.
42 Cap´ıtulo 2. Programac¸a˜o Linear
Soluc¸o˜es via´veis o´timas
Diz-se que x? e´ uma soluc¸a˜o via´vel o´tima do problema (2.22) se x∗ for uma
soluc¸a˜o via´vel (Ax? = b, x? ≥ 0) e, dada qualquer outra soluc¸a˜o via´vel x de (2.22),
z∗ = cx∗ ≤ cx.
Em outras palavras, x∗ e´ uma das soluc¸o˜es via´veis – pode existir mais de uma
– que leva ao menor valor da func¸a˜o-objetivo do problema. O principal resultado
em programac¸a˜o linear pode ser enunciado como segue.
Teorema 2.17 (Teorema Fundamental da Programac¸a˜o Linear). Dado um proble-
ma linear na forma padra˜o (2.22), com A ∈ Rm×n, rankA = m,
i) se (2.22) possui uma soluc¸a˜o via´vel, enta˜o (2.22) possui uma soluc¸a˜o ba´sica
via´vel;
ii) se (2.22) possui uma soluc¸a˜o via´vel o´tima, enta˜o (2.22) possui uma soluc¸a˜o
ba´sica via´vel o´tima.
O item i) do Teorema 2.17 estabelece que se o problema for via´vel, isto e´, se
o problema possuir pelo menos uma soluc¸a˜o via´vel, enta˜o sera´ poss´ıvel determinar
uma soluc¸a˜o ba´sica via´vel. O item ii) estabelece que se o problema possui uma
soluc¸a˜o via´vel o´tima, enta˜o deve existir uma soluc¸a˜o ba´sica via´vel que leva ao menor
valor para a func¸a˜o-objetivo do problema. Em outras palavras, se x? e´ uma soluc¸a˜o
via´vel o´tima, enta˜o deve existir uma soluc¸a˜o ba´sica via´vel o´tima
x? = (x?B , x?N ) = (x?B , 0).
Se cB e cN representarem os custos da func¸a˜o-objetivo relativos a`s varia´veis
ba´sicas e na˜o-ba´sicas, respectivamente, enta˜o
z? = cx? =
[
cB cN
] [ xB
xN
]
= cBx
?B + cNx
?N = cBx
?B ,
Em geral, o sistema Ax = b, x ≥ 0 possui infinitas soluc¸o˜es, mas de acordo
com o Teorema 2.17, item ii), no ma´ximo
(
n
m
)
=
n!
m! (n−m)!
soluc¸o˜es precisam ser exploradas. Geralmente o nu´mero de soluc¸o˜es ba´sicas via´veis
e´ bem menor do que este ma´ximo.
Exemplo 2.18 Considere o problema de programac¸a˜o linear∣∣∣∣∣∣
minimizar z = 2x1 + x2,
sujeito a x1 + x2 ≤ 6,
x2 ≤ 3,
(2.23)
com x1 ≥ 0 e x2 ≥ 0. A Figura 2.9 ilustra a soluc¸a˜o gra´fica do problema (2.23).
2.9. Sistemas de equac¸o˜es lineares 43
PSfrag replacements
0 3
3
6
6 x1
x2
I
II III
IV
x1 + x2 = 6
x2 = 3
2x1 + x2 = 2
Figura 2.9: Soluc¸a˜o gra´fica do problema (2.23).
A regia˜o delimitada pelas linhas mais escuras, resultante da intersec¸a˜o das
restric¸o˜es x1 + x2 ≤ 6, x2 ≤ 3, x1 ≥ 0 e x2 ≥ 0, corresponde a` regia˜o via´vel do
problema. Observe que o problema possui infinitas soluc¸o˜es via´veis. A Figura 2.1
ilustra o conjunto dos pontos tais que 2x1 + x2 = z para z = 2. O valor o´timo do
problema (2.23) e´ z? = 0, atingido no ponto x? = (0, 0).
A forma padra˜o do problema e´∣∣∣∣∣∣∣∣
minimizar z = 2x1 + x2,
sujeito a x1 + x2 + x3 = 6,
x2 + x4 = 3,
x1 ≥ 0, x2 ≥ 0,
com x3 ≥ 0 e x4 ≥ 0 representando varia´veis de folga. As matrizes c, b e A
correspondentes a` forma matricial (m = 2, n = 4) sa˜o
c =
[
2 1 0 0
]
, b =
[
6
3
]
,
e
A =
[
1 1 1 0
0 1 0 1
]
.
Existem (
4
2
)
=
4!
2! 2!
= 6
maneiras de se combinar as quatro colunas de A duas-a-duas, como indicado na
Tabela 2.5.
44 Cap´ıtulo 2. Programac¸a˜o Linear
Tabela 2.5: Soluc¸o˜es ba´sicas do problema (2.23).
Combinac¸a˜o Colunas Soluc¸a˜o Ba´sica
I 3,4 xN1 = 0, x
N
2 = 0, x
B
3 = 6, x
B
4 = 3
II 2,3 xN1 = 0, x
B
2 = 3, x
B
3 = 3, x
N
4 = 0
III 1,2 xB1 = 3, x
B
2 = 3, x
N
3 = 0, x
N
4 = 0
IV 1,4 xB1 = 6, x
N
2 = 0, x
N
3 = 0, x
B
4 = 3
V 1,3 (matrizsingular)
VI 2,4 xN1 = 0, x
B
2 = 6, x
N
3 = 0, x
B
4 = −3 (invia´vel)
As quatro primeiras combinac¸o˜es correspondem a soluc¸o˜es ba´sicas via´veis. A
quinta combinac¸a˜o na˜o da´ origem a uma soluc¸a˜o ba´sica porque a matriz resultante
e´ singular. A sexta combinac¸a˜o e´ uma soluc¸a˜o ba´sica invia´vel (x4 < 0). O Teorema
2.1 assegura que uma das soluc¸o˜es ba´sicas via´veis, I, II, III ou IV, indicadas na
Figura 2.9, deve levar ao menor valor da func¸a˜o objetivo. Calculando os custos
z = cx correspondentes, obte´m-se
I: z =
[
2 1 0 0
]


0
0
6
3

 = 0;
II: z =
[
2 1 0 0
]


0
3
3
0

 = 3;
III: z =
[
2 1 0 0
]


3
3
0
0

 = 9;
IV: z =
[
2 1 0 0
]


6
0
0
3

 = 12.
Portanto, o valor o´timo (mı´nimo) da func¸a˜o objetivo e´ z? = 0 e ocorre na
soluc¸a˜o ba´sica via´vel o´tima x?N1 = 0, x
?N
2 = 0, x
?B
3 = 3 e x
?B
4 = 3, como esperado.
2
Geometria das soluc¸o˜es ba´sicas
O Exemplo 2.18 ilustra uma importante propriedade geome´trica: as soluc¸o˜es
ba´sicas via´veis de Ax = b, x ≥ 0 correspondem a ve´rtices (pontos extremos) da
regia˜o Ax ≤ 0, x ≥ 0. Por serem obtidas por meio da intersecc¸a˜o de restric¸o˜es que
descrevem semi-espac¸os, as regio˜es via´veis de problemas de programac¸a˜o linear sa˜o
2.9. Sistemas de equac¸o˜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, e´ a adjaceˆncia das
soluc¸o˜es ba´sicas via´veis. Partindo da soluc¸a˜o ba´sica via´vel I, obte´m-se a soluc¸a˜o
ba´sica via´vel II, adjacente a I, por meio de uma troca conveniente de uma varia´vel
ba´sica por uma varia´vel na˜o-ba´sica, e assim sucessivamente, ate´ que todas as soluc¸o˜es
ba´sicas via´veis sejam percorridas.