Metodo simplex

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 vizinhos V(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 = (