Otimização Linear - UNESP: Câmpus de Bauruadriana/Pos/PO6.pdf · Departamento de Matemática...

Otimização Linear

Profª : AdrianaDepartamento de Matemática

adriana@fc.unesp.brwwwp.fc.unesp.br/~adriana

Revisão – Método Simplex

Solução básica factível:

Solução geral usando a partição básica:

,x̂

x̂x̂

N

B

1ˆ 0

ˆ 0

B

N

x B b

x

em que

N

B

x

xx

Revisão

N

T

N

x

N

11T

B xc)NxBbB(c)x(f

B

N

T

NN

1T

B

1T

B xcNxBcbBc

valor da soluçãobásica associadaa partição

A função objetivo f(x)=cTx considerando a partição básica:

( )BT T T T T

B N B B N N

N

xf x c x c c c x c x

x

ˆ( )f x

N

B

x

xx

Revisão

Definição (vetor multiplicador simplex) é o vetor (m 1),

também chamado de vetor das variáveis duais dado por:

1T

B

BcTB

TB c

Vetor multiplicador simplex na expressão de f(x):

ˆ( ) ( ) ( ) ( )1 1 N n m n m n m1

T T

N N N N Nf f c x c x

x x λ a λ a

T -1 T T T TB N N N N N N N N

ˆ ˆ ˆ(x) (x) c B Nx c x (x) Nx c x ( ) ( )Tf f f f x c λ N x

Custos relativos ou custos reduzidos

1ˆ ˆ ˆ ˆ( ) ( )

N 2 2 n m n m1N N N N Nf f c x c x c x

x x

jˆ ( )

j j

T

N N Nc c λ a

Revisão

Propriedade: (condição de otimalidade) Considere umapartição básica factível com solução básica factívelassociada e seja vetor multiplicadorsimplex.

Se , então a solução básica é ótima.

1T

B

T Bc

NBA

0bBx̂ 1

B

mn,,1j,0)c(NN jj

T aλ

“Se a condição de otimalidade for verificada, então a solução básica é ótima”.

Caso não seja ótima ( ), perturbamos essa

solução básica factível de modo a diminuir o valor da

função objetivo.

0ˆk

NNN

T

kkcc aλ

Revisão

Estratégia Simplex: perturbar soluções básicas factíveis queconsiste em alterar as variáveis não-básicas por:

.,,....,2,1,0

negativo) relativo custo com (variável,0ε

kimnjx

x

N

N

j

k

A função objetivo passa a valer:

mnN

mn

kN

k

N

NNcccff

N

xxx

0ˆεˆ0ˆ)ˆ()(

1

1xx

εˆ)ˆ(N k

cf x )ˆ(xf

Revisão

Alteração nas variáveis não-básicas: k

x

x

x

N

N

mn

k

N

0

ε

01

N

x

εεBBNB N k

yx̂aBx̂NxBbBx

y

-1-1-1

Alteração nas variáveis básicas:

Direção Simplex

Fornece os coeficientes de como as variáveis básicas são alteradas na estratégia simplex.

Revisão

Equação vetorial: εBB

yx̂x

Como:

como devemos ter

0iB

x 0ε

0 εˆ iBB

yxxii

i

B

y

xi

ˆε

Menor valor de :

miyy

x

y

xi

i

BB i ,...,1,0que talˆ

mínimoˆ

ε̂

Tamanho do passo

então para todo0yi

0yi 0yx̂x iBB ii

Tamanho do passo ?

Revisão

Ao resolvermos

Nova partição:

A variável básica se anula (sair da base)

A variável não-básica torna-se positiva (entrar na base)

Bx̂

kNx̂

0y/y

x̂min

y

x̂ˆ

i

i

BB i

kNB

]a,,a,,[aBBBB m1

]a,,a,,[a NNNN mnk1

]a,,a,,[aB́BNB mk1

]a,,a,,[aN´NBN mn1

Método Simplex - comentários

• Há uma versão do método usando tabelas,conhecida como “Tableau”.

• Estratégias para determinar partição inicial (Fase I).

• Algoritmo é finito, porém pode ocorrer ciclagem.

• Na análise de pior caso (complexidade dealgoritmo) é um algoritmo simplex pode ter umnúmero exponencial de iterações.

• Na prática, têm obtido sucesso na resolução deproblemas de programação linear.

• Utiliza três sistemas lineares que devem serresolvidos de forma eficiente (LU).

Método Simplex – Exemplo

Considere o problema de otimização linear:

Introduzindo variáveis de folga, temos:

Exemplo

Os coeficientes das variáveis de folga formam uma matriz identidade:

Fase II:

Fase I:

Exemplo

Exemplo

B N

Exemplo

Exercício: continue até obter a solução ótima.

Método Simplex em Tabelas

Maneira prática de se trabalhar

Interessante para a compreensão do método

Não é eficiente computacionalmente

◦ Simplex revisado

Método Simplex em Tabelas

Os parâmetros necessários para resolução aparecem na tabela abaixo:

Exemplo

Na forma padrão, temos:

Matriz básica. No método por tabelas, será sempre a matriz identidade

Se todos os valores forem positivo A solução é ótima, cc, a variável mais negativa é candidata a entrar na base

Variável básica: custo relativo é zero! Se não for , então temos q torna-lo nulo.

Exemplo

Sabemos que podemos escrever cada variável básica em função das demais variáveis (no caso, das variáveis não-básicas, x1 e x2). Como B = I, isso é feito muito facilmente:

Basta atribuir valores às variáveis não-básicas x1 e x2 para obter uma solução que satisfaça Ax = b.

Exemplo

• Se fixarmos as variáveis não-básicas x1 e x2 em seus limites, x1 = 0 e x2 = 0, então as demais variáveis têm como valores x3 = 6, x4 = 4, x5 = 4 e produzem uma solução factível para o problema que corresponde a um vértice da região factível.

• Em uma tabela simplex, a função objetivo é sempre escrita em termos das variáveis não-básicas: f = – x1 – 2x2

Exemplo

Aumentando x1 ou x2, a função objetivo diminui. Portanto, a solução básica:

(x1 = 0, x2 = 0, x3 = 6, x4 = 4 e x5 = 4 )

não é ótima.

Aumentar x2 e mantendo x1 = 0 , a função objetivo diminui com uma taxa de variação –2 e quanto maior o valor de x2, menor será o valor de f.

Ao aumentar x2, o que acontece com as variáveis básicas ?

Exemplo

Se x2 cresce e x1 = 0 os valores das variáveis básicas podem aumentar ou diminuir, entretanto, deve-se preservar a não-negatividade das variáveis:

Devemos nos preocupar apenas com x3 e x5

Exemplo – Solução ilimitada

Se no caso anterior tivéssemos:

Solução ilimitada!!

Exemplo

Aumentando o valor de x2 e mantendo x1 = 0 os valores das variáveis básicas podem aumentar ou diminuir. Para preservar a não-negatividade das variáveis:

x2 6

x2 4

Para x2 = 4, x5 se anula. Temos uma nova solução:

variáveis não-básicas: x1 = 0, x2 = 4 entra na base

variáveis básicas: x3 = 2, x4 = 8 e x5 = 0 sai da base

Valor da f.o.: f = 0 – 2 x2 = - 8.

Partição anterior: B = [3, 4, 5] NB = [1, 2]Nova partição: B = [3, 4, 2] NB = [1, 5]

Exemplo

Nova base: B = [3, 4, 2] NB = [1, 5]

As colunas da base devem formar uma identidade

entra na base

sai da base

Efetuar um pivotamento!!!

Exemplo

Nova base: B = [3, 4, 2] NB = [1, 5]

As colunas da base devem formar uma identidade

entra na base

sai da base pivô Restrição atingida

Exemplo

Tabela simplex – iteração 1. Variáveis básicas: x3, x4, x2

Os coeficientes das variáveis não básicas x1 e x5 são chamados de custos relativos

Exemplo

Aumentando o valor da variável x1 e x5 = 0 diminui o valor da f. o. diminui com uma taxa de variação –3.

Equações do sistema com x5 = 0x1 1

Exemplo

Enquanto a variável não-básica x1 = 1, a variável x3 se anula.

Temos uma nova solução básica :

variáveis não-básicas: x1 = 1, x5 = 0 entra na base

variáveis básicas: x3 = 0, x4 = 8 e x2 = 5 sai da base

• Redefinindo as variáveis:

variáveis não-básicas: x3 = 0, x5 = 0

variáveis básicas: x1 = 1, x4 = 8 e x2 = 5

Partição anterior: B = [3, 4, 2] NB = [1, 5]Nova partição: B = [1, 4, 2] NB = [3, 5]

Exemplo

entra na base

sai da base

Nova base: B = [1, 4, 2] NB = [3, 5]

As colunas da base devem formar uma identidade

Exemplo

entra na base

sai da base

Nova base: B = [1, 4, 2] NB = [3, 5]

As colunas da base devem formar uma identidade

pivô

Efetuar um pivotamento!!!

Exemplo

Com essa tabela:

𝟏

𝟐

Exemplo

Como essa tabela: (x3, x5) = (0, 0), (x1, x4,x2 ) = (1, 8, 5) (solução básica) e f = -11.

Atribuindo-se valores positivos a x3 ou x5) a função objetivo cresce, ou seja, f(x) ≥ -11 para qualquer solução factível x, o que significa que a solução atual é ótima.

Todos os custos relativos são não-negativos condição de otimalidade foi verificada!!

Representação gráfica

Algoritmo Simplex (em tabelas)

Base Inicial

Para que o método simplex possa ser aplicado, precisamos de uma solução básica factível inicial (Fase I)

Até agora supomos que sabemos facilmente encontrar uma base factível inicial. Isso é verdade, quando todas as restrições forem de ≤. Por exemplo:

Após a introdução das variáveis de folga:

Base Inicial

A matriz dos coeficientes das restrições agora é dada por [A I] e uma partição básica factível é dada por:

Base Inicial

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 A = [B N] tal que existe B-1 e xB = B-1b 0

Quantas partições existem?

Seja A10 x 20

Precisamos identificar dez colunas L.I. de A para formar B, e a solução do sistema BxB = b, deve satisfazer xB ≥ 0.

Procedimento possível:

◦ 1. Escolher dez (m) colunas e resolver o sistema.

◦ 2. Verificar se xB ≥ 0.

◦ 3. Se não, escolher outras dez colunas e retornar ao

passo 2.

Quantas partições existem?

Se formos testar partição a partição, quantos testes

temos que fazer ?

Impraticável para problemas grandes!

Método das duas fases

As variáveis de folga foram úteis para a classe de problemas:

Se não for o caso, podemos introduzir novas variáveis como se fossem de folga:

equivalente a:

uma partição [I N] em que 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:

Variáveis artificiais. Não fazem parte do problema original e devem ser eliminadas

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 destas variáveis.

Fase I

Uma vez encontrada uma solução básica em que todas as variáveis artificiais são não-básicas, temos uma base formada por colunas originais e, portanto, podemos aplicar o método simplex para resolver o problema original a partir dessa base.

Método Simplex duas fases:

◦ Fase I – resolve o problema artificial.

◦ Fase II – resolve o problema original, a partir da base factível obtida na Fase I.

Exemplo• Considere o problema:

E o problema artificial definido no caso B em que apenas uma variável artificial é introduzida:

Exemplo• Para resolver o problema artificial, aplicamos o método

simplex:

Exemplo

Exemplo

Exemplo

• Fase II: Aplicar o método simplex a partir da base obtida na Fase I. A variável artificial é descartada e os índices não-básicos são redefinidos: N1 = 4, N2 = 3.

Base formada pro variáveis originais do problema. A variável artificial x5 torna-se não básica. Fim da Fase I.

Método M-grande

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. Um objetivo alternativo para o problema artificial é:

Método M-grande

Valor suficientemente grande para garantir que x5

não aparece na solução ótima.