Método Simplex - aula 5

Otimização Linear
Profª : Adriana
Departamento de Matemática
[email protected]
wwwp.fc.unesp.br/~adriana
Perguntas??
Dada uma solução básica factível (vértice de S e,
portanto, candidata à solução ótima),
1) Essa solução é ótima?
2) Caso não seja ótima, como determinar uma outra solução
básica factível melhor?
Pergunta 1
A solução atual é ótima?
Considere uma solução básica factível:
 x̂ B 
x̂    , em que
x̂ N 
 xˆB  B 1b  0

 xˆN  0
E a solução geral usando a mesma partição básica,
isto é:
 xB 
x 
 xN 
Qual o valor desta solução geral??
Pergunta 1
 xB 
x 
 xN 
A função objetivo f(x)=cTx pode ser expressa considerando a
partição básica:
f ( x)  c x  c
T
T
B
 xB 
c     cBT xB cTN xN
 xN 
T
N
coeficientes das
variáveis básicas na
função objetivo
coeficientes das
variáveis não-básicas
na função objetivo
f ( x )  cTB (B1b  B1Nx N )  cTN x N


xB
 cTBB1b  cTBB1Nx N  cTN x N
valor da solução básica associada a esta partição:
f ( xˆ )
Vetor Multiplicador Simplex
cTB B1b corresponde ao valor da função objetivo em x̂
f (xˆ )  cTBxˆ B  cTN xˆ N  cTB (B1b)  cTN (0) = cTB (B1b)
f (xˆ )  cTBxˆ B  cTN xˆ N  cTB (B1b)  cTN (0)  cTBB 1b

T
Definição (vetor multiplicador simplex) é o vetor  (m 1),
também chamado de vetor das variáveis duais dado por:
T  c TBB 1

T
 cTB B 1
BT   cB
  c B  BT   c B
  B
1 T
Vetor Multiplicador Simplex
Vetor multiplicador simplex na expressão de f(x):
ˆ  cTBB-1Nx N  cTN x N  f (x)
ˆ   T Nx N  cTN x N
f (x)  f (x)
 f (xˆ )  (cTN  λ T N)x N
Expressando por colunas:
cTN   T N  (cN , cN , , cN )  λT (a N , a N , , a N )
1
2
n m
 (cN 1  λT a N 1 , cN 2  λT a N 2 ,
1
2
nm
, cN nm  λT a N nm )
x N  ( xN 1 , xN 2 , , xN nm )T
f (x)  f (xˆ )  (cN1  λT a N1 )x N  (cN2  λT a N2 )xN2 
1
 (cNnm  λT a Nnm )xNnm
Custos Relativos
f (x)  f (xˆ )  (cN1  λT a N1 )x N 
1
cˆN j  (cN j  λT a N j )
 (cNnm  λT a Nnm )xNnm
Custos relativos ou custos
reduzidos
Reescrevendo f(x):
f( x )  f( xˆ )  cˆN1 x N  cˆN2 xN2 
1
 cˆNnm xNnm
Exemplo

Considere o problema de otimização linear
Forma padrão
Exemplo
Intersecção das retas:
x1 + x2 = 4 e x1 = 3
Exemplo
x1 + x2 = 4
(variável de folga associada: x3)
 x1 = 3
(variável de folga associada: x4)

Logo, o vértice (solução básica) deve ser obtido
com a partição:
B = (1, 2, 5)
N = (3, 4)
Exemplo
Atribuindo zero às variáveis não-básicas:
x3 = x4 = 0

Todos positivos: solução básica factível.
Exemplo
n-m variáveis não-básicas
B = (B1,B2,B3) = (1, 2, 5)
m variáveis básicas
N = (N1,N2) = (3, 4)
Cálculo dos custos relativos
ˆcN j  (cN j  λ T a N j )
OU
B   cB
T
Cálculo dos custos relativos
Como
OU
Cálculo dos custos relativos
Condição de Otimalidade
Propriedade: (condição de otimalidade) Considere uma
partição básica factível A  B N com solução básica
factível associada x̂ B  B1b  0 e seja T  cTBB1 o vetor
multiplicador simplex.
Se (c N  λ T aN )  0, j 1,, n  m então a solução básica é
ótima.
j
j
“Se a condição de otimalidade for verificada, então a solução
básica é ótima”.
Perguntas
1) Essa solução é ótima?
Condição de
otimalidade!!!
2) Caso não seja ótima, como determinar uma outra
solução básica factível melhor?
A solução não é ótima...
Resposta à segunda pergunta: como determinar uma
solução básica factível melhor??
Supondo que a solução atual não seja ótima (a condição de
otimalidade está violada), isto é, suponha que exista k tal
que:
T
cˆN k  c N k  λ a N k  0
* Problemas de minimização
Perturbamos essa solução básica factível de modo a
diminuir o valor da função objetivo.
Essa estratégia é o fundamento do Método Simplex
Exemplo
Exemplo
(B = B-1 = I)
Cálculo dos custos relativos
cˆ1 e cˆ2 são negativos e não satisfazem a condição de
otimalidade.
Estratégia Simplex
cˆ
Nk
c
Nk
 λT a
Nk
0
Perturbamos essa solução básica
factível de modo a diminuir o valor da
função objetivo.
Estratégia Simplex: perturbar soluções básicas factíveis
que consiste em alterar as variáveis não-básicas por:
 x N k  ε  0, (variável com custo relativo negativo)

 x N j  0, j  1, 2,...., n  m, i  k .
Em outras palavras, apenas uma variável não-básica
deixa de ser nula.
Essa estratégia é o fundamento do Método Simplex
Estratégia Simplex - resultado na
função objetivo

 xN k  ε  0, (variável com custo relativo negativo)

xN j  0, j  1, 2,...., n  m, i  k .


A função objetivo passa a valer:
f (x)  f (xˆ )  cˆN1 
0    cˆN k 
ε    cˆN nm 
0
x N1
 f (xˆ )  cˆN k ε  f (xˆ )
x Nk
x N nm
Estratégia Simplex - resultado na
função objetivo
• A função objetivo decresce quando  cresce, a uma taxa ĉ N k
• Quanto menor o valor de 𝑐𝑁Ƹ 𝑘 , mais rápido a função objetivo
decresce. Isso justifica a escolha da variável não-básica a ser
perturbada com o menor custo relativo Regra de Dantzig
Direção Simplex e Tamanho do
Passo
Qual o tamanho do passo  ?
Mudando as variáveis não-básicas, as variáveis básicas
também são alteradas, de modo que o sistema Ax = b seja
satisfeito. Alteração nas variáveis não-básicas é:
 x N1   0 
    

  
x N   xN k   ε   k

  
    
 x  0 
 N nm   
As variáveis básicas são modificadas por:
x B  B-1b  B-1 Nx N  x̂ B  B-1a N k ε  x̂ B  y ε

y
Direção Simplex
Direção Simplex e Tamanho do
Passo
Direção Simplex: é o nome dado ao vetor y  B-1a N , o
qual fornece os coeficientes de como as variáveis
básicas são alteradas na estratégia simplex. A
direção simplex é a solução do sistema de equações
lineares B y  a N .
k
k
Direção Simplex e tamanho do
Passo
Reescrevendo a equação vetorial: x B  x̂ B  y ε
Considerando a não-negatividade das variáveis básicas:
xBi  xˆ Bi  y i ε  0
yi  0 então xBi  0 para todo
yi  0 como
ε0
x Bi  x̂ Bi  yi   0 devemos ter ε 
xˆ Bi
yi
Logo, o menor valor de  é dado por:
 xˆ Bi

ε̂ 
 mínimo 
tal que yi  0, i  1,..., m
y
 yi

xˆ B
Tamanho
do passo
Tamanho do Passo
Se no cálculo do passo, todos os yi ≤ 0...
... significa que para qualquer valor de , a nova solução
é factível (não há limitante superior para ).
Como a função objetivo decresce com o crescimento de
, então f(x)  - ∞ quando   ∞. Disso concluímos que
o problema não tem solução ótima (a solução ótima
será ilimitada!)
Exemplo
(obtida para xNi =0)
xˆ B  B 1b
Exemplo
A solução é ótima?
Multiplicador Simplex:
Solução do sistema BT  = cB ou
:
Custos relativos:
k = 1 (x1 é alterada
pela estratégia
simplex)
Exemplo
A direção simplex indica a maneira como as variáveis
básicas se modificam, ao aumentar uma dada variável
não-básica (no caso, N1 = 1)
x3 = 4 - 
x4 = 3 - 
x5 = 7/2
Qual o valor máximo para ??
Exemplo
Tamanho do passo:
Atualização
Ao resolvermos ˆ 
x̂ B
y
 x̂ Bi

 min 
/ y i  0
 yi

Determinamos qual variável básica vai se anular (sair da
base)
Isso sugere uma nova partição!
A variável básica x̂ B se anula (sair da base)
A variável não-básica x̂ N torna-se positiva (entrar na
base)
De fato,

k
 x̂ B
ˆ
 -ésima variável básica: x B  x̂ B    x̂ B  y  
 y
k - ésima variável não-básica: x N k  ˆ

  0

Atualização
Nova partição básica, com a troca de índices:
B  N k
Atualização
Isto significa que as matrizes básicas e não-básicas são
alteradas por apenas uma coluna:
B  [a B1 ,, a B ,, a Bm ]

B´  [a B1 ,, a Nk ,, a Bm ]
N  [a N1 ,, a Nk ,, a Nnm ]

N´ [a N1 ,, a B ,, a Nnm ]
Teorema: A matriz B’, definida anteriormente, é invertível, de
modo que A = [B’ N’] é uma nova partição básica.
Pode-se mostrar as colunas de B’ são linearmente independentes
(invertível).
Atualização
Com isso mostramos que a estratégia simplex produz uma
solução básica factível (novo vértice), para o qual a função
objetivo tem um valor menor.
f ( x)  f ( xˆ )  cˆN k ε̂  f ( xˆ )
Podemos repetir o procedimento, isto é, encontrar outra
solução básica melhor a partir daquela em mãos, enquanto
a condição de otimalidade não for verificada.
Graficamente, no exemplo
Índice da variável não-básica escolhida para entrar (N1 = 1)
(escolhemos aquela com menor custo relativo)
Índice da variável básica escolhida para sair (B2 = 4)
(escolhemos aquela que primeiro se anulava ao aumentarmos .)
Nova partição: B = (3,1,5) N=(4,2)
Algoritmo Simplex
Supomos que temos uma partição básica factível já
determinada. Em alguns casos, será necessário efetuar alguns
procedimentos para obtê-la
Algoritmo
Algoritmo
Exercício

Seja o exemplo: