Metodo simplex

Disponível somente no TrabalhosFeitos
  • Páginas : 22 (5308 palavras )
  • Download(s) : 0
  • Publicado : 9 de maio de 2012
Ler documento completo
Amostra do texto
IA 881 Otimização Linear

3-Método Simplex

ProfFernandoGomide

©DCA-FEEC-Unicamp

Conteúdo
1. 2. 3. 4. 5. 6. 7. Condições de otimalidade Desenvolvimento do método simplex Implementações do método simplex Anticiclagem: regras lexicográfica e de Bland Solução básica factível inicial Geometria de colunas do método simplex Eficiência computacional do simplex

2
©DCA-FEEC-Unicamp 1-Condições de otimalidade
min c′x sa Ax = b x≥0

Forma padrão

j = 1,L ,n i = 1,L ,m

c = (c1 ,L ,cn ) b = (b1 ,L ,bm )

′  a1   a11 L a1n  A =  M  =  M O M  = [A1 L A n ], ρ( A) = m     a′m  am1 L amn     

P = {x∈ℜn | Ax = b, x ≥ 0}

3
©DCA-FEEC-Unicamp

Algoritmo de busca local
vizinhança: é uma função V : S → 2S que atribui a cada s∈S um conjunto de vizinhosV(s) ⊆ S chamado de vizinhança de s. mínimo local: de f com relação a uma vizinhança V(s) é uma solução s* tal que f(s*) ≤ f(s), ∀s∈V(s*).

4
©DCA-FEEC-Unicamp

AlgoritmoBuscaLocal( ) retorna um ótimo local entrada: um modelo de otimização s ← GerarSoluçãoFactívelInicial( ) repetir s ← Melhorar(V(s)) até que melhorar f(s) não seja possível retornar s

Melhorar(V(s)) são funções do tipo:1. retorna a primeira solução encontrada que é melhor do que s, 2. explora N(s) exaustivamente e retorna a melhor solução, 3. combinações de (1) e (2).
5
©DCA-FEEC-Unicamp

Programação linear
Ótimo local é ótimo global: função convexa sobre conjunto convexo Busca ao longo de direções que decrescem o valor da função objetivo Considera vizinhanças de soluções básicas factíveis

Seja

x∈P d∈ ℜn
Definição 3.1 Seja x um elemento de um poliedro P. Um vetor d∈ℜn é uma direção factível em x se existe um escalar positivo θ para o qual x + θ d ∈ P.

6
©DCA-FEEC-Unicamp

Direções factíveis em diferentes pontos de um poliedro

y

x

z

7

Considerando

x solução básica factível B(1) ,K , B (m) índices das variáveis básicas B = [ A B (1) L A B ( m ) ] matriz básica x B = (xB (1) ,K , xB ( m ) ) variáveis básicas xi = 0 para toda variável não básica

Temos xB = B−1 b Busca de um novo vetor x + θ d 1. selecionar uma variável não básica xj (inicialmente xj = 0) 2. aumentar valor de xj até um valor θ > 0, mantndo as variáveis não básicas xi, i ≠ j, restantes nulas.
8
©DCA-FEEC-Unicamp

Algebricamente dj = 1 di = 0 ∀i∈N, i≠ j (N é o conjunto de índices dasvariáveis não básicas) xB + θ dB dB = (dB(1) ,…,dB(m)) Restrições de igualdade: x + θ d factível A(x + θ d) = b x é factível ⇒ Ax = b

θ > 0 ⇒ Ad = 0
como dj = 1 e di = 0 ∀i∈N, i≠ j

j-ésima direção básica ou direção simplex

0 = Ad = ∑ Ai di = ∑ A B (i ) d B (i ) + A j = Bd B + A j ⇒ d B = −B −1A j
i =1 i =1
©DCA-FEEC-Unicamp

n

m

9

Restrições de não negatividade de variáveis nãobásicas
xj → θ > 0 xi = 0 ∀i∈N, i≠ j ∴ variáveis não básicas OK

Restrições de não negatividade de variáveis básicas: dois casos 1. x não é solução básica factível degenerada
xB > 0 ⇒ xB + θ dB > 0 para θ suficientemente pequeno d é uma direção factível

2. x é solução básica factível degenerada
d nem sempre é uma direção factível xB(i) = 0 e dB = − B−1Aj < 0
10
©DCA-FEEC-Unicamp

x3 = 0n=5 n–m=2

F E x5 = 0 x1 = 0 x4 = 0

G x2 = 0

11
©DCA-FEEC-Unicamp

Efeito da busca na direção básica sobre função objetivo
d → j-ésima direção básica c'd → variação do valor da função objetivo ao longo de d c'd = c'B dB+ cj = cj − c'BB−1Aj cB = (cB(1) ,…,cB(m))

c j = c j − c′B B −1A j

Definição 3.2 Seja x uma solução básica, B uma matriz básica associada e cB o vetor decoeficientes associado às variáveis básicas. Para cada j, definimos o custo reduzido da variável xj pela cj fórmula

c j = c j − c′B B −1A j
12
©DCA-FEEC-Unicamp

Exemplo
min c1x1 + c2 x2 + c3 x3 + c4 x4 sa x1 + x2 + x3 + x4 = 2 2 x1 + 3x3 + 4 x4 = 2 x1 , x2 , x3 , x4 ≥ 0
A1 = (1, 2) A2 = (1, 0) são LI ⇒ x1 e x2 são variáveis básicas

1 1  B=   2 0

matriz básica correspondente...
tracking img