Simplex

Prévia do material em texto

Soluções básicas e
SIMPLEX
Elis Gonçalves
Universidade Estadual Paulista �Júlio de Mesquita Filho�
22 de Setembro 2017
Elis Gonçalves
Formulação de um problema
Em vários problemas que formulamos, obtivemos:
Um objetivo de otimização (max ou min);
Restrições de igualdade =;
Restrições de desigualdade ≤;
Restrições de desigualdade ≥.
Elis Gonçalves
Forma padrão
Elis Gonçalves
Forma padrão
Todo PL pode ser escrito na forma padrão:
Elis Gonçalves
Forma padrão
Elis Gonçalves
Forma padrão
Elis Gonçalves
Forma padrão
Elis Gonçalves
Forma padrão
Exemplo 1
Passe o problema para a forma padrão:
Elis Gonçalves
Forma padrão
Variáveis livres: se a variável xi é livre de sinal no problema;
xi = xi
+ − xi− com x+i ≥ 0 e x−i ≥ 0;
Qualquer número (positivo, negativo ou nulo) pode ser escrito
como uma diferença de dois outros números não-negativos.
Elis Gonçalves
Forma padrão
Exemplo 2
Elis Gonçalves
Forma padrão
Exercício 1
Elis Gonçalves
Forma matricial
Minimizar f (x) = cTx
S.a : Ax = b
x ≥ 0
(1)
A: matriz mxn chamada de matriz dos coeficientes;
c : vetor de custos;
x : variáveis;
b: vetor dos termos independentes ou termos de recursos.
Elis Gonçalves
Forma matricial
Exemplo 3
Max 22x
1
+ 20x
2
S .a : x
1
+ 3x
2
≤ 60
2x
1
+ 0x
2
≤ 30
0x
1
+ x
2
≤ 18
3x
1
+ x
2
≤ 55
x
1
, x
2
≥ 0
Elis Gonçalves
Resolução gráfica
Permite a visualização de soluções;
Viável para problemas muito pequenos;
Se um problema de otimização linear tem uma solução ótima,
então existe um vértice ótimo.
Elis Gonçalves
Métodos de solução
Elis Gonçalves
Possíveis soluções
Elis Gonçalves
Possíveis soluções
Elis Gonçalves
Possíveis soluções
Apenas as coordenadas (x
1
, x
2
) pode ser visualizadas;
As coordenadas (x
3
, x
4
, x
5
) medem as folgas em cada restrição;
Os pontos A e B estão no interior da região factível (todas as
variáveis de folga são positivas).
Uma solução está na fronteira se e somente se xj = 0, j = 1, ..., 5.
Elis Gonçalves
Possíveis soluções
Alguma variável se anula: restrições ativas.
Mais de uma variável se anula: vértice (mais de uma restrição
ativa).
Elis Gonçalves
Possíveis soluções
Elis Gonçalves
Possíveis soluções
Os vértices são soluções de sistemas de equações lineares;
Sempre que existe uma solução ótima, existe um ponto extremo
ótimo;
Uma maneira de encontrar a soluções ótima seria visitar os pontos
extremos sucessivamente;
Como determinar pontos extremos sem o auxílio do gráfico?
Elis Gonçalves
Escrevendo o sistema
Quando conhecemos uma possível solução, podemos reescrever o sis-
tema em variáveis básicas e não básicas:
Elis Gonçalves
Escrevendo o sistema
Elis Gonçalves
Notação sistema
Elis Gonçalves
Variáveis básicas e não básicas
As variáveis de xN foram fixadas em 0, portanto o sistema re-
sultante, BxB , possui o mesmo número de equações e incógnitas
(m);
Se as variáveis solução desse sistema são ≥ 0, temos um ponto
extremo factível, caso contrário, o ponto é infactível.
Elis Gonçalves
Variáveis básicas e não básicas
Se a matriz B do sistema for invertível, a solução é bem determi-
nada.
E se a matriz B não for invertível? Sempre é possível selecionar
m colunas da matriz A que formem uma matriz B invertível. As
demais variáveis são fixadas.
Quando consideramos um problema de otimização linear na forma
padrão, admitimos que m ≤ n (é comum m ≤≤ n). Assim o
sistema linear Ax = b tem infinitas soluções;
Se m = n o sistema tem solução única e o problema é trivial de
ser resolvido.
Elis Gonçalves
Partição
Elis Gonçalves
Solução geral do sistema
Elis Gonçalves
Solução básica do sistema
Elis Gonçalves
O método SIMPLEX
O método SIMPLEX encontra um vértice ótimo visitando apenas
um subconjunto de todos os vértices;
Pra construir um método de resolução de um problema de otimi-
zação linear, devemos responder a duas perguntas-chave:
1 Essa solução é ótima?
2 Caso não seja ótima, como determinar uma outra solução básica
factível melhor?
Elis Gonçalves
SIMPLEX
Elis Gonçalves
SIMPLEX
Elis Gonçalves
Vetor multiplicador SIMPLEX
Elis Gonçalves
Vetor multiplicador SIMPLEX
Elis Gonçalves
Custos relativos
Elis Gonçalves
Condição de otimalidade
Elis Gonçalves
Pergunta 2: e se a solução não é ótima?
Caso não seja ótima, como determinar uma outra solução básica
factível melhor?
Elis Gonçalves
Estratégia simplex
Elis Gonçalves
Estratégia simplex
Elis Gonçalves
Direção e tamanho do passo
Elis Gonçalves
Direção e tamanho do passo
Elis Gonçalves
Direção e tamanho do passo
Elis Gonçalves
Tamanho do passo
Solução ilimitada
Elis Gonçalves
Atualização
Elis Gonçalves
Atualização
Elis Gonçalves
Atualização
Elis Gonçalves
Solução básica de valor menor
Elis Gonçalves
Algoritmo simplex
Elis Gonçalves
Algoritmo simplex
Elis Gonçalves
Exercício
Elis Gonçalves