Investigação Operacional
Métodos de Programação Linear: Big M, 2 Fases, S Dual
(Licenciatura)
Tecnologias e Sistemas de Informação
http://dps.uminho.pt/pessoais/zan
Universidade do Minho - Escola de Engenharia
Departamento de Produção e Sistemas
Universidade do Minho
2007
Investigação Operacional
1
José António Oliveira – [email protected]
Simplex
•Como obter um quadro simplex válido para um problema
que tenha restrições de igualdade e/ou de maior ou
igual?
– Note-se que, se o problema só tiver restrições de "menor
ou igual", temos sempre uma base "à mão": a constituída
pelas variáveis de folga, i.e.
– O ponto de solução nula pertence ao espaço de soluções
válidas, e forma-se a base com as variáveis de folga.
Universidade do Minho
2007
Investigação Operacional
2
José António Oliveira – [email protected]
1
Simplex
•Modelos (a) e (b) são equivalentes.
– O modelo (b) está na forma estandardizada e inclui uma variável de
excesso (primeira restrição) e uma variável de folga (segunda restrição).
– Para a segunda linha é fácil encontrar uma variável básica inicial (tem
coeficiente 1 na própria linha e 0 nas restantes).
– Qual a variável básica a associar à primeira linha? Não é claro. Não há
nenhuma variável que tenha coeficiente 1 na própria linha e 0 nas
restantes.
•Modifica-se o modelo por inclusão de variáveis
artificiais
Investigação Operacional
Universidade do Minho
2007
3
José António Oliveira – [email protected]
Grande M / 2 fases
Max z = 2 x1 + 3 x2
Max z = 2 x1 + 3 x2 + 0 S1
s.a :
x1 + 2 x2 ≤ 3
s.a :
x1 + 2 x2 + S1 = 3
x1 , x2 ≥ 0
x1 , x2 , S1 ≥ 0
Universidade do Minho
2007
Qual é a solução óptima?
Investigação Operacional
4
José António Oliveira – [email protected]
2
Grande M / 2 fases
Min z = S1
Minimizar a folga
s.a :
x1 + 2 x2 + S1 = 3
Qual é a solução óptima?
x1 , x2 , S1 ≥ 0
O quadro
não é válido
Investigação Operacional
Universidade do Minho
2007
5
José António Oliveira – [email protected]
Grande M / 2 fases
Min z = S1
s.a :
x1 + 2 x2 + S1 = 3
Qual é a solução óptima?
x1 , x2 , S1 ≥ 0
O quadro
não é válido
Validação do
Quadro Simplex
Universidade do Minho
2007
Investigação Operacional
6
José António Oliveira – [email protected]
3
Grande M «» 2 Fases
Min z = 2 x1 + 3 x2 Min z = 2 x1 + 3 x2 + Ma1
s.a :
s.a :
Variáveis artificiais permitem
do ponto de solução
x1 + 2 x2 ≥ 3
x1 + 2 x2 − F1 + a1 = 3 começar
nula.
x1 , x2 , S1 ≥ 0
x1 , x2 , F1 , a1 ≥ 0
As variáveis artificiais medem
o desvio (distância) do espaço
de soluções válidas.
O objectivo é anular essa
distância / desvio da zona de
soluções válidas
x1 + 2 x2 ≥ 3
x1 , x2 ≥ 0
O quadro não é válido
Universidade do Minho
2007
Investigação Operacional
7
José António Oliveira – [email protected]
Grande M «» 2 Fases
Min z = 2 x1 + 3 x2 Min z = 2 x1 + 3 x2 + Ma1
s.a :
s.a :
x1 + 2 x2 ≥ 3
x1 + 2 x2 − F1 + a1 = 3
x1 , x2 , S1 ≥ 0
x1 , x2 , F1 , a1 ≥ 0
O quadro
não é válido
x1 + 2 x2 ≥ 3
x1 , x2 ≥ 0
Universidade do Minho
2007
Investigação Operacional
8
José António Oliveira – [email protected]
4
Grande M «» 2 Fases
Síntese:
Incluem-se no modelo variáveis artificiais com coeficientes na
função objectivo de tal forma que, numa solução óptima do
modelo modificado, as variáveis artificiais tenham valor nulo.
Dessa forma a solução óptima do modelo modificado é também
óptima do modelo original.
O coeficiente das variáveis artificiais representa-se por M.
Universidade do Minho
2007
Investigação Operacional
9
José António Oliveira – [email protected]
Grande M «» 2 Fases
Síntese:
No exemplo, o valor de M pode ser 100.
O modelo (c) obtido não é equivalente ao modelo original.
Uma solução admissível de (c) só é uma solução admissível de (a)
se o valor de a for zero.
Se, na solução óptima de (c) a variável artificial a tiver um valor
positivo, então o problema (a) é impossível.
Universidade do Minho
2007
Investigação Operacional
10
José António Oliveira – [email protected]
5
Grande M «» 2 Fases
Exemplo:
Validação do Quadro Simplex
Universidade do Minho
2007
Investigação Operacional
11
José António Oliveira – [email protected]
Grande M «» 2 Fases
Exemplo:
mais pequeno
sai da base
mais negativa, entra na base
Não há artificiais na base,
podem ser removidas do quadro
e prossegue-se com o Simplex...
Universidade do Minho
2007
Investigação Operacional
12
José António Oliveira – [email protected]
6
Grande M «» 2 Fases
Exemplo:
sai
Ponto actual
entra
Solução óptima
Universidade do Minho
2007
Investigação Operacional
13
José António Oliveira – [email protected]
Grande M «» 2 Fases
O método das 2 fases resulta do Grande M
dividindo a Função Objectivo por M ???
2 x1 x2 Ma
+
−
M M M
Max z = 0 + 0 − a
Max z =
Min w = a
Universidade do Minho
2007
Investigação Operacional
14
José António Oliveira – [email protected]
7
Grande M «» 2 Fases
1ª FASE
Para obter uma base inicial, utiliza-se
um problema auxiliar que consiste em
minimizar a soma das variáveis
artificiais.
– Elimina-se a distância à zona de
soluções válidas.
Universidade do Minho
2007
Investigação Operacional
15
José António Oliveira – [email protected]
Grande M «» 2 Fases
2ª FASE
Se não houver variáveis artificias na
base, procede-se com a função
objectivo original
Senão, o problema é impossível !
– É necessário validar o quadro
Universidade do Minho
2007
Investigação Operacional
16
José António Oliveira – [email protected]
8
Grande M «» 2 Fases
Exemplo:
1ª Fase
Validação do Quadro Simplex
Universidade do Minho
2007
Investigação Operacional
17
José António Oliveira – [email protected]
Grande M «» 2 Fases
Exemplo:
1ª Fase
mais pequeno
sai da base
negativa (empate), entra na base
Não há artificiais na base,
podem ser removidas do quadro
e passa-se à 2ª fase...
Ponto actual
Universidade do Minho
2007
Investigação Operacional
18
José António Oliveira – [email protected]
9
Grande M «» 2 Fases
Exemplo:
2ª Fase
Validação do Quadro Simplex
Universidade do Minho
2007
Investigação Operacional
19
José António Oliveira – [email protected]
Grande M «» 2 Fases
Exemplo:
2ª Fase
sai da base
negativa, entra na base
Solução óptima
Universidade do Minho
2007
Investigação Operacional
20
José António Oliveira – [email protected]
10
Simplex DUAL
Vamos ver uma curiosidade…
Coluna pivot
VAMOS
ERRAR !
Sai x4
Investigação Operacional
Universidade do Minho
2007
21
José António Oliveira – [email protected]
Simplex DUAL
Há valores negativos nos termos independentes !!!
0
−7
1
3
2
1
− 5
0
1
4
0
2
−2
0
4
− 1
0
24
0
5
O que fazer?
Universidade do Minho
2007
2
2
Investigação Operacional
0
− 175
0
115
1
−45
0
575
2
2
22
José António Oliveira – [email protected]
11
Simplex DUAL
Reiniciar a partir do quadro original?
Desfazer o erro?
-sair x1 e entrar x4
E se fosse possível continuar, apesar da asneira !?!?
0
−7
1
3
2
0
2
−2
0
24
1
− 5
0
1
4
4
1
0
−
2
5
0
2
0
− 175
0
115
1
−45
0
2
2
575
Investigação Operacional
Universidade do Minho
2007
23
José António Oliveira – [email protected]
Simplex DUAL
O que é necessário fazer para reparar o erro ?
transformar termos independentes em valores positivos
manter a matriz identidade
iterar, escolhendo pivots negativos
0
−7
1
3
2
0
2
−2
0
24
Universidade do Minho
2007
1
−5
0
1
4
4
0 − 1
2
5
0
2
0
− 175
0
115
1
−45
0
2
sai a mais negativa
2
575
Investigação Operacional
Pivots
negativos
Qual é a que
entra?
24
José António Oliveira – [email protected]
12
Simplex DUAL
O que é necessário fazer para reparar o erro ?
transformar os negativos em positivos
Iterar, optimizando,
escolhe-se a menor
razão em módulo!
manter a matriz identidade
iterar, escolhendo pivots negativos
0
−7
1
3
2
0
2
−2
0
24
1
−5
0
1
4
4
1
0 −
2
5
0
2
0
− 175
0
115
1
−45
0
2
sai a mais negativa
2
575
Pivots
negativos
Investigação Operacional
Universidade do Minho
2007
Qual é a que
entra?
Entra x4
25
José António Oliveira – [email protected]
Simplex DUAL
Ainda há valores negativos nos termos independentes !!!
0
14
1
4
0
0
Universidade do Minho
2007
5
5
− 3
5
− 1
− 4
5
1
5
− 2
2
5
1
0
0
0
40
1
−10
0
0
0
Investigação Operacional
70
400
26
José António Oliveira – [email protected]
13
Simplex DUAL
Quadro válido !!!
Falta Optimizar, resolução pelo Simplex PRIMAL
0
0
− 8
1
0
− 1
1
+ 2
0
+ 8
0
0
14
1
3
3
3
5
−
3
− 5
3
0
5
80
4
0
0
3
70
3
50
3
3
3
1250
Investigação Operacional
Universidade do Minho
2007
3
27
José António Oliveira – [email protected]
Simplex DUAL
Solução Óptima
0
0
−4
1
0
3
0
1
0
Universidade do Minho
2007
0
7
− 2
12
7
7
7
3
14
− 2
5
5
7
14
14
Investigação Operacional
1
5
0
20
0
25
0
425
28
José António Oliveira – [email protected]
14
Simplex DUAL
Só mudou a
ordem das
linhas
0
− 4
1
0
3
0
1
0
0
Universidade do Minho
2007
0
7
7
− 2
12
7
7
3
14
− 2
5
5
7
14
14
1
5
0
20
0
25
0
425
Investigação Operacional
29
José António Oliveira – [email protected]
Simplex DUAL
Exemplo
Min z = 2 x1 + x3
Max -z = −2 x1 − x3
Max -z = −2 x1 − x3
s.a :
x1 + x2 − x3 ≥ 5
s.a :
− x1 − x2 + x3 ≤ −5
s.a :
− x1 − x2 + x3 + s1 = −5
x1 − 2 x2 + 4 x3 ≥ 8
− x1 + 2 x2 − 4 x3 ≤ −8
− x1 + 2 x2 − 4 x3 + s2 = −8
x j ≥ 0, j = 1, 2,3
x j ≥ 0, j = 1, 2,3
x j ≥ 0, j = 1, 2,3
solução
básica
não admissível
Universidade do Minho
2007
Investigação Operacional
30
José António Oliveira – [email protected]
15
Simplex DUAL
sai
Síntese:
entra
Sai da base a variável com o valor mais negativo (que é
“menos admissível”).
Entra na base a variável que tem menor razão em módulo
entre o coeficiente da linha da função objectivo e o
coeficiente da linha pivot, considerando apenas as que têm
coeficientes negativos na linha pivot.
Investigação Operacional
Universidade do Minho
2007
31
José António Oliveira – [email protected]
Simplex DUAL
−
5
,
4
−
,
−
1
4
7
4
,
1
, 0, 1,
2
1
2
1
2
,
1 ,
,
0 ,
0 ,
1
,
4
−
0 ,
1
,
4
1
4
,
− 7
sai
2
− 2
entra
Solução
Óptima
Universidade do Minho
2007
Investigação Operacional
32
José António Oliveira – [email protected]
16
Simplex DUAL
Resumo da Iteração do algoritmo simplex dual:
1. Teste de optimalidade (a solução básica actual é óptima se todos
os termos independentes são não negativos e todos os
coeficientes da linha da função objectivo são não negativos). Se
a solução é óptima, parar. Se não, prosseguir com o passo 2.
2. Decidir qual a variável que sai da base (é aquela que tem o valor
mais negativo - em caso de empate decidir arbitrariamente).
Prosseguir com o passo 3.
3. Decidir qual a variável não básica que entra na base (é aquela que
tem a menor razão em módulo do critério de entrada - excluindo
as variáveis que têm coeficiente positivo ou nulo na linha pivot;
em caso de empate, escolher maior pivot em módulo). Se não
houver nenhuma variável com coeficiente negativo na linha pivot,
o problema é impossível, parar. Se não, prosseguir para 4.
4. Actualizar o quadro simplex para a base actual e passar à
iteração seguinte (passo 1).
Universidade do Minho
2007
Investigação Operacional
33
José António Oliveira – [email protected]
Simplex Matricial «» Revisto
Quadro Inicial
Quadro numa
qualquer iteração
Universidade do Minho
2007
Investigação Operacional
34
José António Oliveira – [email protected]
17
Simplex Matricial «» Revisto
Quadro Inicial
Matriz tecnológica (coeficientes das restrições)
Matriz Identidade
Termos independentes
Coeficientes na Função Objectivo
Variáveis de decisão
Variáveis de folga
Investigação Operacional
Universidade do Minho
2007
35
José António Oliveira – [email protected]
Simplex Matricial «» Revisto
Max z = 2 x1 + 5 x2 + 3 x3
4
s.a :
+ x2
+2 x3
≤7
2 x1
+ x2
≤6
3 x1
+ x2
,
xj ≥ 0
+6 x3
≤9
j = 1, 2,3
2 1 2
A =  3 1 0 
 0 1 6 
Max z = 2 x1 + 5 x2 + 3 x3 + 0 x4 + 0 x5 + 0 x6
4
s.a :
2 x1 + x2
3 x1
+ x2
+ x2
+2 x3
+ x4
=7
+ x5
+6 x3
+ x6
=6
=9
x j ≥ 0 , j = 1, 2,3, 4,5, 6
7 
b =  6 
9 
c = 2 5
3
4 

Universidade do Minho
2007
Investigação Operacional
36
José António Oliveira – [email protected]
18
Simplex Matricial «» Revisto
Matriz formada pelas colunas da Matriz
das variáveis básicas
Matriz Inversa da Matriz
Matriz dos coeficientes na Função Objectivo das variáveis básicas
Vector das variáveis básicas
Na Análise de Sensibilidade é esta forma matricial que se usa.
Quase Sempre a Matriz
é dada.
Quadro numa
qualquer iteração
Universidade do Minho
2007
Investigação Operacional
37
José António Oliveira – [email protected]
Simplex Matricial «» Revisto
A Revisão do Simplex teve como objectivo a definição de
uma metodologia mais eficiente para uso do cálculo
automático.
Dantzig e Orchard-Hays desenvolveram para a RAND
Corporation uma metodologia que visava tratar a informação
estritamente necessária para o cálculo automático.
O Simplex revisto permite reduzir o número de operações a
efectuar em cada iteração, o espaço de memória, e o tempo de
computação.
Universidade do Minho
2007
Investigação Operacional
38
José António Oliveira – [email protected]
19
Simplex Matricial «» Revisto
No percurso para a solução óptima só importa conhecer
os vectores (colunas) fora da base, em termos da base
actual (colunas das variáveis básicas):
– calculo dos custos reduzidos;
– determinação do vector a sair da base
– obtenção da nova solução por mudança de base.
Não se actualiza todo o quadro simplex, somente
interessa identificar o novo elemento pivot.
A forma revista explora o facto de se poder obter todo o
quadro simplex respeitante a qualquer SBA a partir do
conhecimento da matriz inversa da base B-1 dessa solução.
Universidade do Minho
2007
Investigação Operacional
39
José António Oliveira – [email protected]
Simplex Matricial «» Revisto
Atendendo ao conceito de base de um espaço vectorial,
qualquer vector Pj é dado por:
Pj = BX j , j = 1, 2,… , n
em que Xj é a representação do vector Pj em termos de
base B. Donde
X j = B −1 Pj
em que B-1 designa a matriz inversa da base actual.
Qualquer solução básica resulta de igualar a zero as
variáveis não básicas.
BX B = b
X B = B −1b
Universidade do Minho
2007
Investigação Operacional
40
José António Oliveira – [email protected]
20