Teoria da Otimização Linear
Transformação de problemas na forma padrão
1 1i in n ia x a x b
ai1x1 + ...+ ainxn + xk = bi
xk ≥ 0
ai1x1 + ...+ ainxn - xk = bi
xk ≥ 0
1 1i in n ia x a x b
variável xi irrestrita de sinal no problema
, com 0, 0.i i i i ix x x x x
Adriana Cherri_____________________________________________________________________________________ 2
Teoria da Otimização Linear
minimizar f (x1, x2, . . . , xn) = c1x1 + c2x2 + . . . + cnxn
Sujeito a:
a11x1 + a12x2 + . . . + a1nxn = b1
a21x1 + a22x2 + . . . + a2nxn = b2
...
am1x1 + am2x2 + . . . + amnxn = bm
x1 0, x2 0,..., xn 0
Adriana Cherri_____________________________________________________________________________________ 3
Teoria da Otimização Linear
Solução factível satisfaz todas as restrições e as
condições de não-negatividade do problema de
otimização linear;
Região factível é conjunto de todas as soluções
factíveis define uma região no Rn;
Solução ótima é uma solução factível e fornece o
menor (maior) valor à função objetivo;
Adriana Cherri_____________________________________________________________________________________ 4
Teoria da Otimização Linear
Os vértices são determinados pela intersecção de
duas (ou mais) retas que definem a fronteira da
região factível;
Os vértices são soluções de sistemas de equações
lineares;
Se um problema de otimização linear tem uma
solução ótima, então existe um vértice ótimo;
Adriana Cherri_____________________________________________________________________________________ 5
Soluções básicas
Considere a seguinte região factível no R2
Variáveis de folga
Forma padrãoAdriana Cherri_____________________________________________________________________________________ 6
Soluções básicas
Adriana Cherri_____________________________________________________________________________________ 7
Soluções BásicasFactível?? Não-negatividade??
Adriana Cherri_____________________________________________________________________________________ 8
Soluções BásicasFactível?? Não-negatividade??
Adriana Cherri_____________________________________________________________________________________ 9
Soluções BásicasFactível?? Não-negatividade??
Adriana Cherri_____________________________________________________________________________________ 10
Restrição Ativa
Folga nula
Soluções BásicasFactível?? Não-negatividade??
Adriana Cherri_____________________________________________________________________________________ 11
Vértice da
região factível
Alguns pontos
• Apenas as coordenadas (x1, x2) pode ser
visualizadas;
• As coordenadas (x3, x4 , x5) medem as folgas em cada
restrição;
• Os pontos A e B estão no interior da região factível
(todas as variáveis de folga são positivas).
• Uma solução está na fronteira se e somente se xj = 0,
j = 3, 4, 5Adriana Cherri_____________________________________________________________________________________ 12
Fronteira da região factível
• Alguma variável se anula!
• Variáveis nulas indicam restrições ativas!
• Mais de uma variável se anula: vértice (mais de uma restrição
ativa)! Adriana Cherri_____________________________________________________________________________________ 13
Pontos InfactíveisRespeitam o sistema Ax = bCondição de não-negatividade!
Adriana Cherri_____________________________________________________________________________________ 14
Pontos InfactíveisRespeitam o sistema Ax = bCondição de não-negatividade!
Adriana Cherri_____________________________________________________________________________________ 15
Região ConvexaUm conjunto S é convexo se para qualquer par de elementos x, y de S e qualquer [0; 1], então:
x + (1 - )y S.
Adriana Cherri_____________________________________________________________________________________ 16
Região Convexa
A região factível de um problema de programação linear é um conjunto convexo.
Adriana Cherri_____________________________________________________________________________________ 17
Vimos que...
• Os vértices são soluções de sistemas de equações lineares;
• Sempre que existe uma solução ótima, existe um ponto extremo ótimo;
• Uma maneira de encontrar a soluções ótima seria visitar os pontos extremos sucessivamente;
• Como determinar pontos extremos sem o auxílio do gráfico??
Adriana Cherri_____________________________________________________________________________________ 18
Pontos Extremos
Duas restrições ativas:
duas variáveis nulas
n-m variáveis nulas
Ponto D:
3 equações, 3 incógnitas
1
2
5
5
1
13
x
x
x
Adriana Cherri_____________________________________________________________________________________ 19
Pontos Extremos
Ponto F:
1
4
5
6
2
15
x
x
x
2
3
0
0
x
x
1
1 4
1 5
6
4
3 3
x
x x
x x
Adriana Cherri_____________________________________________________________________________________ 20
Pontos Extremos
Infactíveis
Ao fixar (n-m) variáveis em zero, a resolução do sistema resulta em ao menos um valor negativo para as variáveis restantes. (Ex. ponto F)
Factíveis:Ao fixar (n-m) variáveis em zero, a resolução do sistema resulta em valores positivos para as variáveis restantes. (Ex. ponto D)
Adriana Cherri_____________________________________________________________________________________ 21
Escrevendo o sistema
Apesar de fixarmos m - n variáveis em zero (no ex., x3 e x4)
continuamos escrevendo-as no sistema, porém de forma isolada:
Adriana Cherri_____________________________________________________________________________________ 22
Escrevendo o sistema
Índices:
B = (B1, B2, B3): B1 = 1, B2 = 2, B3 = 5
N = (N1, N2): N1 = 3, N2 = 4
Índices das colunas da matriz A
que pertencem a B e a N
Adriana Cherri_____________________________________________________________________________________ 23
Notação
Índices:B = (B1, B2, B3): B1 = 1, B2 = 2, B3 = 5N = (N1, N2): N1 = 3, N2 = 4
Colunas associadas:
= [a1, a2, a5]
= [a3, a4]
1
2
3
1
2
5
x
B
B B
B
x x
x x
xx
1
2
3
4
xN
N
N
x x
x x
1 2 3=(a ,a ,a )B B BB
1 2=(a ,a )N NN
Adriana Cherri_____________________________________________________________________________________ 24
Reescrevendo o sistema
Minimizar f(x) = cT x
Ax = bx 0
Ax = b BxB+NxN = b
➢ No exemplo, as variáveis de xN foram fixadas em 0, portanto,
o sistema resultante, BxB = b, possui o mesmo número de
equações e incógnitas (m).
➢ Se as variáveis da solução desse sistema são 0, temos um
ponto extremo factível, caso contrário, o ponto é infactível.Adriana Cherri_____________________________________________________________________________________ 25
Revisando...• Se a matriz B do sistema for invertível, a solução é
bem determinada.
• E se a matriz B não for invertível?Sempre é possível selecionar m colunas da matriz A que formem uma matriz B invertível. As demais variáveis são fixadas.
• Quando consideramos um problema de otimização linear na forma padrão, admitimos que m < n (é comum m << n). Assim o sistema linear Ax = b tem infinitas soluções e o grau de liberdade é n – m.
• Se m = n o sistema tem solução única e o problema é trivial de ser resolvido.
Adriana Cherri_____________________________________________________________________________________ 26
Partição Básica (Matriz Básica)
Bm×m : matriz básica formada por m colunas da matriz A
e invertível.
B pode ser escrita como:
em que B1, B2,..., Bm são os índices das colunas
escolhidas da matriz A que pertencem a B (índices
básicos)
A = [B, N]
1 2= a ,a ,...,a
mB B BB
Adriana Cherri_____________________________________________________________________________________ 27
Partição Básica (Matriz Não-Básica)
Nm×(n-m) : matriz não-básica formada por n – m colunas
restantes da matriz A.
N pode ser escrita como:
em que N1, N2,..., Nn-m são os índices das colunas da
matriz A que pertencem a N (índices não-básicos)
A = [B, N]
1 2 ( )= a ,a ,..., a
n mN N NB
Adriana Cherri_____________________________________________________________________________________ 28
Partição Básica – Partição das Variáveis
• A partição de A em [B N] cria uma partição no vetor das variáveis:
variáveis básicas
variáveis não-básicas
Adriana Cherri_____________________________________________________________________________________ 29
Solução Geral do Sistema
A última expressão de xB é conhecida como solução geral do sistema.
bx
xNBbAx
N
B
bNxBx NB
N
11
B NxBbBx
Adriana Cherri_____________________________________________________________________________________ 30
Solução Básica
➢ Considerando a partição básica A = [B N], uma
solução é dita básica quando:
0x̂
bBx̂
N
1
B
Se ou seja, se todas as variáveis básicassão não-negativas, dizemos que é uma soluçãobásica factível.
0 1 bBxB
Adriana Cherri_____________________________________________________________________________________ 31
Voltando ao Exemplo...
0,,,
33
4
6
4321
521
421
321
xxxx
xxx
xxx
xxx
Adriana Cherri_____________________________________________________________________________________ 32
Voltando ao ExemploNo ponto Dvariáveis básicas: x1 , x2 e x5
variáveis não-básicas: x3 e x4
Adriana Cherri_____________________________________________________________________________________ 33
Voltando ao ExemploNo ponto Fvariáveis básicas: x1 , x4 e x5
variáveis não-básicas: x2 e x3
Solução básica não-factível.
Adriana Cherri_____________________________________________________________________________________ 34
Teoria BásicaPropriedade 1:
Seja S a região factível. S = { x ∈ Rn / Ax=b, x 0}.
Um ponto x ∈ S é um vértice de S se e somente se x foruma solução básica factível.
Propriedade 2:
Se um problema de otimização linear tem uma soluçãoótima, então existe um vértice ótimo.
“Se existe uma solução ótima, então existe uma soluçãobásica factível ótima”
Basta que se procure o ótimo entre todas as soluçõesbásicas factíveis.
Adriana Cherri_____________________________________________________________________________________35
Método possível..Enumerar todas as soluções básicas (vértices da região):x1, x2, ..., xk
Escolher aquela com melhor função objetivo.
Problema: k pode ser muito grande
Idéia:
Partir de uma solução básica factível
Visitar apenas as soluções básicas factíveis melhoresque ela.
Método SimplexAdriana Cherri_____________________________________________________________________________________ 36