Aula 6

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 Investigação Operacional 1

2007 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.

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
Grande M / 2 fases
Max z = 2 x1 + 3 x2 Max z = 2 x1 + 3 x2 + 0 S1
s.a : s.a :
Qual é a solução óptima?
x1 + 2 x2 ≤ 3 x1 + 2 x2 + S1 = 3
x1 , x2 ≥ 0 x1 , x2 , S1 ≥ 0

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

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

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
x1 + 2 x2 ≥ 3 x1 + 2 x2 − F1 + a1 = 3 começar
nula.
do ponto de solução
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

Min z = 2 x1 + 3 x2 Min z = 2 x1 + 3 x2 + Ma1
s.a : s.a :
x1 + 2 x2 ≥ 3 O quadro
x1 + 2 x2 − F1 + a1 = 3 não é válido
x1 , x2 , S1 ≥ 0 x1 , x2 , F1 , a1 ≥ 0
x1 + 2 x2 ≥ 3
x1 , x2 ≥ 0

4
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.

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.

5
Exemplo:
Validação do Quadro Simplex

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...

6
Exemplo:
sai
Ponto actual
entra
Solução óptima

O método das 2 fases resulta do Grande M

dividindo a Função Objectivo por M ???
2 x1 x2 Ma
Max z = + −
M M M
Max z = 0 + 0 − a
Min w = a
7
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.

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

8
Exemplo:
1ª Fase

Exemplo:
1ª Fase mais pequeno

sai da base
negativa (empate), entra na base
Não há artificiais na base,

Ponto actual podem ser removidas do quadro
e passa-se à 2ª fase...

9
Exemplo:
2ª Fase

Exemplo:
2ª Fase
sai da base
negativa, entra na base
Solução óptima

10
Simplex DUAL
Vamos ver uma curiosidade…
Coluna pivot
VAMOS
ERRAR !
Sai x4
Simplex DUAL
Há valores negativos nos termos independentes !!!
0 −7 1 − 5 0 − 175
2 4 2
1 3 0 1 0 115
2 4 2
0 −2 0 − 1 1 −45
2
0 24 0 5 0 575
2
O que fazer?
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 − 5 0 − 175
2 4 2
1 3 0 1 0 115
2 4 2
0 −2 0 − 1 1 −45
2
0 24 0 5 0 575
2
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 −5 0 − 175
2 4 2
sai a mais negativa
1 3 0 1 0 115
2 4 2
0 −2 0 − 1 1 −45
2
Qual é a que
0 24 0 5 0 575 Pivots entra?
2
negativos
12
Simplex DUAL
O que é necessário fazer para reparar o erro ?
transformar os negativos em positivos
Iterar, optimizando,
manter a matriz identidade
escolhe-se a menor
iterar, escolhendo pivots negativos razão em módulo!
0 −7 1 −5 0 − 175
2 4 2
sai a mais negativa
1 3 0 1 0 115
2 4 2
0 −2 0 − 1 1 −45
2
Qual é a que
0 24 0 5 0 575 Pivots entra?
2
negativos Entra x4
Simplex DUAL
Ainda há valores negativos nos termos independentes !!!
0 14 − 4 1 0 70
5 5
1 4 1 0 0 40
5 5
0 − 3 − 2 0 1 −10
5 5
0 − 1 2 0 0 400

13
Simplex DUAL
Quadro válido !!!
Falta Optimizar, resolução pelo Simplex PRIMAL
0 0 − 8 1 14 70
3 3 3
1 0 − 1 0 4 80
3 3 3
0 1 + 2 0 − 5 50
3 3 3
0 0 + 8 0 − 5 1250
5 3 3
Simplex DUAL
Solução Óptima
0 0 −4 3 1 5
7 14
1 0 3 − 2 0 20
7 7
0 1 − 2 5 0 25
7 14
0 0 12 5 0 425
7 14

14
Simplex DUAL
Só mudou a
ordem das 0 0 − 4 3 1 5
7 14
linhas 1 0 3
7
− 2
7
0 20
0 1 − 2 5 0 25
7 14
0 0 12 5 0 425
7 14

Simplex DUAL
Exemplo
Min z = 2 x1 + x3 Max -z = −2 x1 − x3 Max -z = −2 x1 − x3
s.a : s.a : s.a :
x1 + x2 − x3 ≥ 5 − x1 − x2 + x3 ≤ −5 − 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

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.
Simplex DUAL
5 1 1
− , − , 0, 1, , − 7 sai
4 2 4
1 1 1
, − , 1 , 0 , − , 2
4 2 4
7 1 1
, , 0 , 0 , , − 2
4 2 4
entra
Solução
Óptima

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).

Simplex Matricial «» Revisto
Quadro Inicial
Quadro numa
qualquer iteração

17
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

Max z = 2 x1 + 5 x2 + 3 x3 Max z = 2 x1 + 5 x2 + 3 x3 + 0 x4 + 0 x5 + 0 x6
4 4
s.a : s.a :
2 x1 + x2 +2 x3 ≤7 2 x1 + x2 +2 x3 + x4 =7
3 x1 + x2 ≤6 3 x1 + x2 + x5 =6
+ x2 +6 x3 ≤9 + x2 +6 x3 + x6 =9
xj ≥ 0 , j = 1, 2,3 x j ≥ 0 , j = 1, 2,3, 4,5, 6
2 1 2 7 
A =  3 1 0  b =  6 
 0 1 6  9 
c = 2 5 3
 4 

18
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


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.

19
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.


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

20

Aula 6

Enviado por

Direitos autorais:

Formatos disponíveis

Aula 6

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Aula 6

Enviado por

Direitos autorais:

Formatos disponíveis

Investigação Operacional

Métodos de Programação Linear: Big M, 2 Fases, S Dual

Tecnologias e Sistemas de Informação

Universidade do Minho - Escola de Engenharia

Universidade do Minho Investigação Operacional 1

Universidade do Minho Investigação Operacional 2

•Modifica-se o modelo por inclusão de variáveis

Universidade do Minho Investigação Operacional 4

Universidade do Minho Investigação Operacional 5

Universidade do Minho Investigação Operacional 6

O quadro não é válido

Universidade do Minho Investigação Operacional 7

Universidade do Minho Investigação Operacional 8

O coeficiente das variáveis artificiais representa-se por M.

Universidade do Minho Investigação Operacional 9

Universidade do Minho Investigação Operacional 10

Validação do Quadro Simplex

Universidade do Minho Investigação Operacional 11

mais negativa, entra na base

Não há artificiais na base,

Universidade do Minho Investigação Operacional 12

Universidade do Minho Investigação Operacional 13

O método das 2 fases resulta do Grande M

Universidade do Minho Investigação Operacional 15

Senão, o problema é impossível !

Universidade do Minho Investigação Operacional 16

Validação do Quadro Simplex

Universidade do Minho Investigação Operacional 17

1ª Fase mais pequeno

negativa (empate), entra na base

Não há artificiais na base,

Universidade do Minho Investigação Operacional 18

Validação do Quadro Simplex

Universidade do Minho Investigação Operacional 19

negativa, entra na base

Universidade do Minho Investigação Operacional 20

E se fosse possível continuar, apesar da asneira !?!?

manter a matriz identidade

iterar, escolhendo pivots negativos

Universidade do Minho Investigação Operacional 26

Falta Optimizar, resolução pelo Simplex PRIMAL

Universidade do Minho Investigação Operacional 28

Universidade do Minho Investigação Operacional 29

Universidade do Minho Investigação Operacional 30

Entra na base a variável que tem menor razão em módulo

Universidade do Minho Investigação Operacional 32

Universidade do Minho Investigação Operacional 33

Simplex Matricial «» Revisto

Universidade do Minho Investigação Operacional 34

Matriz tecnológica (coeficientes das restrições)

Simplex Matricial «» Revisto

Universidade do Minho Investigação Operacional 36

Universidade do Minho Investigação Operacional 37

Simplex Matricial «» Revisto

Universidade do Minho Investigação Operacional 38

Universidade do Minho Investigação Operacional 39

Simplex Matricial «» Revisto

Qualquer solução básica resulta de igualar a zero as

Universidade do Minho Investigação Operacional 40