Cap2_Notas_de_Otim_Linear

Prévia do material em texto

Caṕıtulo 2
Geometria da Otimização
Linear
Neste caṕıtulo, vamos formalizar e generalizar, para problemas de qualquer di-
mensão n ≥ 2, as conclusões obtidas a partir do método gráfico para solução
de problemas bidimensionais. Para tanto, introduziremos os conceitos de poli-
edro, ponto extremo, vértice e convexidade. Em seguida, desenvolveremos uma
interpretação algébrica para esses conceitos essencialmente geométricos, com o
objetivo de viabilizar as suas utilizações em algoritmos.
2.1 Poliedros, hiperplanos e hiperespaços
Iniciaremos definindo poliedro como um conjunto descrito por um número finito
de equações ou inequações lineares, ou seja, um conjunto na forma de da região
fact́ıvel de um problema de otimização linear.
Definição 4. (Poliedro) Um poliedro é um conjunto que pode ser descrito na
forma
P = {x ∈ Rn|Ax ≥ b},
onde A é uma matriz m×n e b é um vetor do Rm. Em particular, um conjunto
na forma
P
′
= {x ∈ Rn|Ax = b, x ≥ 0}
também é um poliedro e será chamado poliedro na forma padrão.
21
22 CAPÍTULO 2. GEOMETRIA DA OTIMIZAÇÃO LINEAR
Como pudemos observar, através do método geométrico proposto no Caṕıtulo
1, os poliedros, que representam regiões fact́ıveis para problemas de otimização
linear, podem se estender ao infinito ou delimitar uma região finita. Nesse
contexto, apresentamos a Definição 5 para caracterizar conjuntos limitados.
Definição 5. (Conjunto limitado) Um conjunto S ⊂ Rn é dito limitado quando
existe um número real K tal que, para todo x = (x1, . . . , xn) ∈ R
n, tem-se
|xi| ≤ K, ∀i ∈ {1, . . . , n}.
A seguir, a Figura 2.1 ilustra a Definição 5 no contexto de poliedros.
Figura 2.1: Poliedro limitado e poliedro não limitado. Notação de acordo com
a Definição 5
Definição 6. (Hiperplano e hiperespaço) Sejam a ∈ Rn, a 6= 0, e b ∈ R.
(i) O conjunto {x ∈ Rn|aTx = b} é chamado hiperplano;
(ii) O conjunto {x ∈ Rn|aTx ≥ b} é chamado hiperespaço.
Geometricamente, o hiperespaço é limitado por um hiperplano. A Figura 2.2
ilustra um hiplano e um hiperespaço no R2.
A seguir, a Proposição 3 estabelece que o vetor a ∈ R é perpendicular ao
hiperplano {x ∈ Rn|aTx = b}. Trata-se de uma generalização de um resultado
bastante conhecido da Geometria Anaĺıtica plana e espacial.
Proposição 3. O vetor a ∈ R é perpendicular ao hiperplano H = {x ∈
R
n|aTx = b}.
2.1. POLIEDROS, HIPERPLANOS E HIPERESPAÇOS 23
Figura 2.2: Hiperplano e hiperespaço no R2, de acordo com a Definição 6
Demonstração. Com efeito, tome x, y ∈ H. Assim, temos que aTx = b e aT y =
b. Além disso,
aT (y − x) = aT y − aTx = b− b = 0.
Portanto, o vetor a é perpendicular a qualquer vetor contido em H, isto é, a é
perpendicular ao hiperplano H.
Agora, observe que o poliedro P = {x ∈ Rn|Ax ≥ b} pode ser escrito como
P = {x ∈ Rn|aT
i
x ≥ bi, i = 1, . . . ,m}, onde ai = (ai1, ai2, . . . , ain) é a i-ésima
da matriz A e bi é i-ésima coordenada do vetor b. Portanto, P é a intersecção
dos m hiperplanos aT
i
x ≥ bi, i = 1, . . . ,m, conforme ilustrado na Figura 2.3.
Figura 2.3: Poliedro como intersecção de hiperespaços e delimitado por hiper-
planos.
24 CAPÍTULO 2. GEOMETRIA DA OTIMIZAÇÃO LINEAR
2.2 Conjuntos convexos e envoltória convexa
O conceito de convexidade desempenha um papel central na teoria de oti-
mização, principalmente, na otimização linear. As Definições 7 e 8 estabelecem
os conceitos relacionados à convexidade que serão utilizados neste texto.
Definição 7. (Conjunto convexo) Um conjunto S ⊂ Rn é dito convexo quando,
para quaisquer x, y ∈ S, tem-se que
λx+ (1− λ)y ∈ S, ∀ λ ∈ [0, 1].
Geometricamente, o vetor λx+ (1− λ)y, com λ ∈ [0, 1], é um ponto no seg-
mento que une os vetores x e y. Portanto, um conjunto é convexo quando contém
todos os segmentos cujos extremos pertencem ao conjunto. Na Figura 2.4 apre-
sentamos uma representação geométrica de um conjunto convexo e um não
convexo. Sugerimos ao leitor verificar que conjunto não convexo apresentado na
Figura 2.4 não é um poliedro.
Figura 2.4: Representação geométrica de conjunto convexo.
Definição 8. (Combinação convexa e envoltória convexa) Sejam x1, . . . , xk ∈
R
n e λ1, . . . , λk escalares não-negativos, tais que λ1 + · · ·+ λk = 1.
(i) O vetor
k∑
i=1
λix
i é chamado combinação convexa dos vetores x1, . . . , xk;
(ii) O conjunto de todas as combinações convexas dos vetores x1, . . . , xk é
chamado envoltória convexa desses vetores, denotado por hull(x1, . . . , xk).
O Teorema 1 estabelece fatos relevantes sobre convexidade e poliedros.
Teorema 1. São válidas as seguintes afirmações.
2.3. PONTOS EXTREMOS, VÉRTICES E SOLUÇÕES BÁSICAS 25
a) A intersecção de conjuntos convexos é um conjunto convexo;
b) Todo poliedro é um conjunto convexo;
c) Uma combinação comvexa de um número finito de elementos de um con-
junto convexo também pertence ao conjunto;
d) A envoltória convexa de um número finito de vetores é um conjunto con-
vexo.
Finalizaremos esta seção com uma interpretação geométrica da envoltória
convexa. Claramente, a envoltória convexa de dois vetores é o segmento que os
une. Se possuirmos três vetores não colineares, a envoltória convexa consiste
em todo o triângulo (interior e fronteira) cujos vértices são os treês vetores
considerados, conforme ilustrado na Figura 2.5. No caso geral, dados n vetores,
de modo que nenhum deles pertença à envoltória convexa gerada pelos demais
vetores, a envoltória convexa consiste no poliedro cujos vértices são os n vetores
dados.
Figura 2.5: Envoltória convexa de três vetores não colineares.
2.3 Pontos extremos, vértices e soluções básicas
Definição 9. (Ponto extremo) Seja P um poliedro. Um vetor x ∈ P é chamado
ponto extremo de P quando não for posśıvel encontrar dois vetores y, z ∈ P ,
ambos diferentes de x, e um escalar λ ∈ [0, 1], tais que x = λy + (1− λ)z.
Uma definição geométria alternativa caracteriza um vértice de um poliedro
P como a única solução ótima de algum problema de otimização linear com
região fact́ıvel igual P .
Definição 10. (Vértice) Seja P um poliedro. Um vetor x ∈ P é um vértice de
P se existe algum c ∈ Rn tal que cTx < cT y, ∀y ∈ P, u 6= x.
26 CAPÍTULO 2. GEOMETRIA DA OTIMIZAÇÃO LINEAR
A noção de vértice estabelecida na Definição 10 é representada geometrica-
mente na Figura 2.6. Na figura, o poliedro P possui quatro vértices, denotados
por x1, x2, x3 e x4. Para cada i = 1, . . . , 4, se tomarmos P como região fact́ıvel
e consideramos o problema de minimizar a função objetivo f i(x) = (ci)Tx, ob-
teremos o vértice xi como única solução ótima, satisfazendo assim a definição
apresentada.
Figura 2.6: Ilustração da Definição 10
A partir da Definição 10, podemos dizer que x é um vértice quando P está
completamente contido em um lado do hiperplano que intercepta o poliedro P
apenas no ponto x. Utilizando os elementos definidos na Figura 2.6, para cada i,
tomando zi = (ci)Txi, teremos que o poliedro P estará contido num único lado
do hiperplano {x ∈ Rn|(ci)Tx = zi}, ou mais especificamente, no hiperespaço
{x ∈ Rn|(ci)Tx ≥ zi}.
Observe que as Definições 9 e 10 possuem caráter geométrico e são dif́ıceis
de serem verificadas num algoritmo. Desse modo, é importante obter definições
alternativas para esses conceitos em termos algébricos. Para tanto, considere
um poliedro P ⊂ Rn definido em termos de igualdades e desigualdades lineares,
conforme segue.
P :
aT
i
x ≥ bi, i ∈M1
aT
i
x ≤ bi, i ∈M2
aT
i
x = bi, i ∈M3
Na descrição do poliedro P , M1, M2 e M3 são conjuntos finitos e disjuntos
de ı́ndices, de modo que M1 ∪M2 ∪M3 = {1, . . . ,m}, ai ∈ R
n, i = 1, . . . ,m e
2.3. PONTOS EXTREMOS, VÉRTICES E SOLUÇÕES BÁSICAS 27
os bi’s são escalares.
Definição 11. (Restrição ativa) Se um vetor x∗ satisfaz aT
i
x∗ = bi para algum
i = 1, . . .,m, dizemos que a restrição correspondente está ativa ou vinculada em
x∗.
Exemplo 7. Seja P = {(x1, x2, x3) ∈ R
3|x1 + x2 + x3 = 1, x1, x2, x3 ≥ 0}.
Verifique quais restrições estão ativas em cada ponto destacado na Figura 2.9.
Figura 2.7: Representação geométrica do poliedro P
Seja x∗ ∈ P . Se existem n restrições ativas em x∗, então esse vetor satisfaz
um sistema de n equações lineares e n incógnitas. Tal sistema possuirá um única
solução se, e somente se, as suas n equações são linearmente independentes (LI).
O Teorema 2 estabelece essa afirmação de modo preciso.
Teorema 2. Sejam x∗ ∈ Rn e I o conjunto dos ı́ndices das restrições ativas em
x∗, ou seja, I = {i|aT
i
x∗ = bi}. Então, são equivalentes as seguintes afirmações:
a) Existem n vetores LI no conjunto {ai|i ∈ I}. Em outras palavras, existem
n restrições LI ativas em x∗.
b) O espaço gerado pelos vetores do conjunto {ai|i ∈ I} é o próprio R
n.
c) O sistema de quações aT
i
x = bi, i ∈ I, possui uma única solução (que é
x∗).
No enunciado do Teorema 2 cometemos um pequeno abuso de linguagem
ao dizer que algumas restrições são LI. Costumamos dizer que as restrições
aT
i
x = (≥)bi, i ∈M , são LI para indicar que os vetores ai, i ∈M , são LI.
28 CAPÍTULO 2. GEOMETRIA DA OTIMIZAÇÃO LINEAR
O Teorema 2 nos garante que se escolhermos n restrições LI e forçarmos que
elas sejam ativas, obteremos uma sistema de equações lineares que é posśıvel e
determinado, obtendo assim uma única solução. Tal solução, geometricamente,
possui as caracteŕısticas desejáveis para um vértice ou ponto extremo, conforme
as Definições 9 e 10. Voltemos ao Exemplo 7 para observar que todos os vértices
do poliedro P ⊂ R3 possuem exatamente 3 restrições ativas. Também observe
que o ponto D, apesar de ser um vértice, não é uma solução fact́ıvel, ou seja,
D /∈ P . Dessa forma, a caracterização algébrica induzida pelo resultado esta-
belecido no Teorema 2 pode produzir vértices infact́ıveis. Todos esses aspectos
são devidamente formalizados na Definição 12.
Definição 12. (Solução básica) Considere um poliedro P definido por restrições
de igualdade e desigualdade e seja x∗ ∈ Rn.
a) O vetor x∗ é chamado solução básica quando:
i. Todas as restrições de igualdade estão ativas em x∗; e
ii. Dentre as restrições ativas em x∗, existem n que são LI.
b) Se x∗ é uma solução básica que satisfaz todas as demais restrições, a
chamaremos de solução básica fact́ıvel.
Exemplo 8. Considere, novamente, o poliedro P = {(x1, x2, x3) ∈ R
3|x1+x2+
x3 = 1, x1, x2, x3 ≥ 0}. Classifique os pontos destacados na figura abaixo entre
solução básica fact́ıvel, solução básica infact́ıvel e solução não básica.
Figura 2.8: Representação geométrica do poliedro P
2.3. PONTOS EXTREMOS, VÉRTICES E SOLUÇÕES BÁSICAS 29
Observemos que, se o número de restrições (m) utilizadas para definir um
poliedro P ⊂ Rn é menor do que o número de variáveis de decisão (n), então
o número de restrições ativas em qualquer ponto será menor do que n. Desse
modo, não existirão soluções básicas. Em aplicações reais da otimização linear,
costumamos ter um número de restrições muito maior do que o número de
variáveis, isto é m >> n.
Observe que desenvolvemos três definições para representar um mesmo con-
ceito de interesse, a saber, ponto extremo, vértice e solução básica fact́ıvel. As
duas primeiras definições possuem um carácter geométrico, enquanto a última
é uma definição em termos algébricos. O Teorema 3 formaliza a equivalência
entre as três definições apresentadas.
Teorema 3. Sejam P um poliedro não vazio e x∗ ∈ P . Então, as seguintes
afirmações são equivalentes:
a) x∗ é um vértice;
b) x∗ é um ponto extremo;
c) x∗ é uma solução básica fact́ıvel.
De acordo com o Teorema 3, um vetor é solução básica fact́ıvel se, e somente
se, é um ponto extremo. Como a definição de ponto extrema independe da
representação adotada para o poliedro, conclúımos que a prorpiedade de solução
básica também independete da representação utilizada. A seguir, a Proposição 4
estabelece o número máximo de soluções básicas (vértices) de um poliedro.
Proposição 4. Um poliedro P = {x ∈ Rn|aT
i
x ≥ bi, i = 1, . . . ,m} admite um
número finito de soluções básicas.
Demonstração. Com efeito, a fim que x∗ seja uma solução básica, é necessário
que tenhamos n restrições LI ativas em x∗. Desse modo, o número máximo de
soluções básicas, fact́ıveis ou não, é igual ao número de maneiras que podemos
escolher n restrições, para serem ativas (ou ativadas), dentre as m restrições
dispońıveis. Ou seja, o número máximo de soluções básicas fact́ıveis é dado por
Cn
m
=
m!
n!(m− n)!
.
30 CAPÍTULO 2. GEOMETRIA DA OTIMIZAÇÃO LINEAR
Apesar do número de soluções básicas fact́ıveis ser finito, problemas reais
costumam admitir um número muito grande de vértices (soluções básicas), tor-
nando inviável a identificação de todos eles e, por conseguinte, uma solução
do problema via inspeção. Para exemplificar este fato, considere o poliedro
P = {x ∈ Rn|0 ≤ xi ≤ 1, i = 1, . . . , n}. O poliedro P possui 2n restrições,
admitindo 2n soluções básicas.
Encerraremos esta seção com a definição de soluções básicas adjacentes e um
exemplo sobre a identificação de tais soluções.
Definição 13. (Soluções básicas adjacentes) Duas soluções básicas referentes a
um mesmo poliedro são ditas adjacentes se for possivel encontrar n−1 restrições
LI ativas em ambas as soluções básicas.
Exemplo 9. Consideremos, novamente, o poliedro P = {(x1, x2, x3) ∈ R
3|x1+
x2 + x3 = 1, x1, x2, x3 ≥ 0} e suas soluções básicas A,B e C. Quais delas são
adjacentes entre si?
Figura 2.9: Representação geométrica do poliedro P
Bibliografia
[1] Marcos Arenales, Vińıcius Armentano, et al., Pesquisa operacional, Elsevier
Brasil, 2006.
[2] Mokhtar S Bazaraa, John J Jarvis, and Hanis D Sherali, Linear programming
and network flows, John Wiley & Sons, 2008.
[3] Dimitris Bertsimas and John Tsitsiklis, Introduction to linear optimization,
IIE Transactions 30 (1998), 855–863.
[4] Robert J Vanderbei et al., Linear programming, Springer, 2020.
[5] Stephen Wright, Jorge Nocedal, et al., Numerical optimization, Springer
Science 35 (1999), no. 67-68, 7.
31