aula_5_10

Prévia do material em texto

Obtendo uma solução 
básica factível inicial
Método Simplex duas fases
Base inicial – FASE I
• Como determinar uma partição básica 
factível inicial (A=(B, N)).
• Algumas classes de problemas de 
otimização linear oferecem naturalmente a 
solução básica factível
Minimizar f(x) = cTx 
sujeito a: Ax ≤ b 
 x ≥ 0 
em que b ≥ 0. 
Base inicial – FASE I
Minimizar f(x) = cTx 
sujeito a: Ax ≤ b 
 x ≥ 0 
em que b ≥ 0. 
Após a introdução das variáveis de folga, digamos, xf, temos: 
Minimizar f(x) = cTx 
sujeito a: Ax + xf = b 
 x ≥ 0, xf ≥ 0, 
A matriz dos coeficientes das restrições agora é dada por [A I] e
uma partição básica factível é dada por:
• B = I: as variáveis básicas são as variáveis de folga xB = xf 
• N = A: as variáveis não-básicas são as variáveis originais xN = x, 
e a solução básica factível é dada por: 
 



==
≥==
.
,
0xx
0bxx
N
B f
 
• Suponha agora que as restrições são, 
originalmente, de igualdade:
• Precisamos encontrar uma partição básica 
factível de A, isto é, uma partição da forma:
tal que existe e
Base inicial – FASE I
Quantas partições existem ?
• Tome A10 x 20
Precisamos identificar dez colunas L.I. de 
A para formar B, e o sistema Bxb = b, tem 
que ter xB ≥ 0. 
• Procedimento possível:
– 1. Escolher dez (m) colunas
– 2. Verificar se xB ≥0.
– 3. Se não, escolher outras dez colunas e 
retornar ao passo 2.
Quantas possíveis partições 
existem ?
• Se formos testar partição a partição, 
quantos testes temos que fazer ?
impraticável para problemas
grandes!
Introduzindo novas variáveis 
de folga
• Quando tínhamos variáveis de folga, 
funcionava, pois:
• Se não for o caso, podemos forçar variáveis de 
folga:
uma partição [I N] onde as variáveis de folga começam como as variáveis 
básicas.
Fase I
• Obviamente, essas variáveis não podem 
aparecer na solução final (pois elas não existem 
- são variáveis artificiais). 
• Método duas-fases: resolvemos primeiro um 
problema:
Fase I
• Se conseguimos uma solução de custo zero 
para o problema acima (fase I), a base final não 
contém nenhuma variável artificial (por quê ?)
• Neste caso, a base final do problema da fase I é
uma base inicial para o problema real (fase II).
Fase I
• E se não conseguimos uma solução de 
custo zero ? (Isto é, na solução ótima da 
fase I, existe uma variável artificial na 
base).
(Não existe solução factível para o nosso 
problema)
Exemplo
Forma padrão
Qual o problema da fase I a 
resolver ?
• Caso A: introduzimos uma variável 
artificial pra cada restrição:
e minimizamos o custo destas variáveis.
Qual o problema da fase I a 
resolver ?
• Caso B: note que x4 já fornece uma 
coluna da matriz identidade. Assim, a 
rigor, precisamos apenas de uma variável 
artificial:
e minimizamos o custo desta variável.
Exemplo
Obtenha a solução do problema original.
Outra possibilidade
• Em vez de resolver um problema auxiliar (fase I) 
para encontrar a base, simplesmente 
penalizamos as variáveis artificiais no problema 
original (fase II), de modo a garantir que elas 
sejam nulas na solução ótima:
valor suficientemente grande para garantir que xvalor suficientemente grande para garantir que x55 nnãão aparece na soluo aparece na soluçãção o óótima.tima.
Considere o Exemplo
3,2,1i,0x
4x3xx
3xxx
x2xxf
i
321
321
321
=≥
≤+−
=++
+−=
 
2 
 :asujeito
)(minimizar x
4,...,1i,0x
4xx3xx
3xxx
x0x2xxf
i
4321
321
4321
=≥
=++−
=++
++−=
 
 2 
 :asujeito
)(minimizar x
Forma Padrão
Variável artificial apenas primeira restrição:
Obter uma solução Inicial para o problema.
5,...,1i,0x
4xx3xx
3xxxx
xx,...,xf
i
4321
5321
551a
=≥
=++−
=+++
=
 
 2 
 :asujeito
)(minimizar
Exemplo
5,...,1i,0x
4xx3xx
3xxxx
xx,...,xf
i
4321
5321
551a
=≥
=++−
=+++
=
 
 2 
 :a sujeito
)(minimizar
Para resolver o problema artificial, aplicamos o método simplex. 
Fase I: Partição básica factível inicial: 41 =B 52 =B 11 =N 22 =N 
33 =N 






=
01
10
B e 





−
=
312
111
N 
1a. Iteração 
1. Solução básica: 
Resolva o sistema bxB =Bˆ , cuja matriz aumentada é 





4
3
01
10
 e obtenha a 
solução: 





=





=
3
4
x
x
ˆ
5
4
Bx 
Exemplo
5,...,1i,0x
4xx3xx
3xxxx
xx,...,xf
i
4321
5321
551a
=≥
=++−
=+++
=
 
 2 
 :a sujeito
)(minimizar
1. Teste de otimalidade: 
i) Vetor multiplicador: Resolva o sistema BT cλB = , cuja matriz aumentada 
é 





1
0
01
10
 e obtenha 





=
0
1
λ 
ii) Custos relativos 
11 =N : 1ccˆ 1
T
11 −=−= aλ ← 1Nx = x1 entra na base 
22 =N : 1ccˆ 2
T
22 −=−= aλ 
33 =N : 1ccˆ 3
T
33 −=−= aλ 
Exemplo
5,...,1i,0x
4xx3xx
3xxxx
xx,...,xf
i
4321
5321
551a
=≥
=++−
=+++
=
 
 2 
 :a sujeito
)(minimizar
1. Direção simplex: Resolva o sistema 1aBy = , cuja matriz aumentada é 






2
1
01
10
 e obtenha y = 





1
2
 
1. Tamanho do passo 
1
B
i
i
B
y
x
2
1
3
,
2
4
min0y
y
x
min 1i ==






=






>=ε ( 1Bx = x4 sai da base) 
2. Atualização 
1B1 = 5B2 = 4N1 = 2N2 = 3N3 = 
 





=
02
11
B e 





−
=
311
110
N 
Exemplo
5,...,1i,0x
4xx3xx
3xxxx
xx,...,xf
i
4321
5321
551a
=≥
=++−
=+++
=
 
 2 
 :a sujeito
)(minimizar
2a. Iteração: 1B1 = 5B2 = 4N1 = 2N2 = 3N3 = 
1. Solução básica: Resolva o sistema bxB =Bˆ : 





4
3
02
11
 e obtenha 






=
1
2
ˆ Bx 
2. Teste de otimalidade 
i) Vetor multiplicador: Resolva o sistema BT cλB = : 





1
0
01
21
 e obtenha 
λλλλ = 





− 21
1
 
ii) Custos relativos 
4N1 = : 21444 =−= aλTccˆ 
22 =N : 23222 −=−= aλ
Tccˆ
 ← 
2Nx = x2 entra na base 
3N3 = : 3
1
3
T
33 ccˆ =−= aλ 
Exemplo
5,...,1i,0x
4xx3xx
3xxxx
xx,...,xf
i
4321
5321
551a
=≥
=++−
=+++
=
 
 2 
 :a sujeito
)(minimizar
1. Direção simplex: resolva o sistema 2aBy = : 





− 1
1
02
11
 e obtenha 







−
=
2
3
2
1
y
 
2. Tamanho do passo 
2
B
3
2
2
3i
i
B
y
x
;
1
min0y
y
x
min 2i ==








=






>=ε
 ( 2Bx = x5 sai da base - Variável 
artificial ) 
1. Atualização: 
1B1 = 2B2 = 41 =N 5N 2 = 3N3 = 
 





−
=
12
11
B
 Fim da FASE I
Exemplo – FASE II
5,...,1i,0x
4xx3xx
3xxxx
xx,...,xf
i
4321
5321
551a
=≥
=++−
=+++
=
 
 2 
 :a sujeito
)(minimizar
FASE I – Problema Artificial
Fase II: Aplicar o método simplexa partir da base obtida na Fase I. A variável 
artificial (segunda variável não básica: N2 = 5) é descartada e os índices não 
básicos são redefinidos: N1 = 4, N2 = 3.  
Exercício
Obtenha a uma base factível inicial do problema.
1 2
1 2
1 2
1 2
3 4
:
4
2 3 1 8
0 , 0
M i n i m i z e x x
s u j e i t o a
x x
x x
x x
− +
+ ≤
+ ≥
≥ ≥