02 Simplex

M´etodo Simplex
Alexandre Salles da Cunha

DCC-UFMG, Mar¸co 2010

Alexandre Salles da Cunha

M´ etodo Simplex

Id´eias centrais do m´etodo

Se um PL na forma padr˜ ao possui uma solu¸c˜ ao o´tima, ent˜ao existe uma solu¸c˜ao b´asica vi´ avel ´ otima para o problema.
O M´etodo Simplex baseia-se neste fato. Iniciando em uma solu¸c˜ao b´asica vi´avel, move-se para uma solu¸c˜ ao b´ asica vizinha de menor custo. Este processo continua at´e que uma dire¸c˜ ao que permita reduzir a fun¸c˜ao objetivo n˜ao seja encontrada, comprovando a otimalidade da solu¸c˜ao em m˜aos.

Alexandre Salles da Cunha

M´ etodo Simplex

O Problema a ser resolvido

min

c ′x

s.t.:

Ax = b x ≥ 0

onde A ∈ Rm×n , b ∈ R a j-´esima coluna de A ´e designada por Aj a i -´esima linha de A ´e designada por ai .

Alexandre Salles da Cunha

M´ etodo Simplex

Uma id´eia muito comum nos algoritmos de otimiza¸c˜ao

Dada uma solu¸c˜ao vi´ avel, procure uma solu¸c˜ ao vi´avel mais barata nas vizinhan¸cas da solu¸c˜ao atual.
Esta procura de solu¸c˜ oes vi´ aveis normalmente ´e feita tentando movimentar sobre uma dire¸c˜ ao vi´ avel aprimorante.
Se uma dire¸c˜ao aprimorante n˜ ao existe, a solu¸c˜ ao corrente ´e um
´otimo local para o problema (n˜ ao necess´ ariamente global).
No caso do PL, todo ´ otimo local ´e global, uma vez que o PL ´e u problema de otimiza¸c˜ ao convexa (minimizar uma fun¸c˜ao conexa sobre um conjunto convexo).
O M´etodo Simplex explora exatamente esta id´eia.

Alexandre Salles da Cunha

M´ etodo Simplex

Dire¸c˜ao vi´avel
Seja x um ponto em um poliedro P. Um vetor d ∈ Rn ´e dito ser uma dire¸c˜ao vi´avel em x, se existir um escalar positivo θ para o qual x + θd ∈ P.

Alexandre Salles da Cunha

M´ etodo Simplex

Obtendo uma dire¸c˜ao vi´avel conveniente

Filosofia para escolha da dire¸c˜ao vi´avel
Vamos considerar a possibilidade de mover a partir de x para uma solu¸c˜ao b´asica vizinha (adjacente).
Por defini¸c˜ao, uma solu¸c˜ ao b´ asica adjacente a x deve compartilhar n − 1