20
Universidade do Minho 2007 Investigação Operacional José António Oliveira – [email protected] 1 Investigação Operacional Métodos de Programação Linear: Big M, 2 Fases, S Dual Universidade do Minho - Escola de Engenharia Departamento de Produção e Sistemas (Licenciatura) Tecnologias e Sistemas de Informação http://dps.uminho.pt/pessoais/zan Universidade do Minho 2007 Investigação Operacional José António Oliveira – [email protected] 2 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.

Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

Embed Size (px)

Citation preview

Page 1: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

1

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

1

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

Universidade do Minho - Escola de EngenhariaDepartamento de Produção e Sistemas

(Licenciatura)

Tecnologias e Sistemas de Informação http://dps.uminho.pt/pessoais/zan

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

2

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.

Page 2: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

2

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

3

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

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

4

Grande M / 2 fases

Qual é a solução óptima?

1 2

1 2

1 2

2 3. :

2 3, 0

Max z x xs ax xx x

= +

+ ≤≥

1 2 1

1 2 1

1 2 1

2 3 0. :

2 3, , 0

Max z x x Ss ax x Sx x S

= + +

+ + =≥

Page 3: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

3

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

5

Grande M / 2 fases

Qual é a solução óptima?

1

1 2 1

1 2 1

. :

2 3, , 0

Min z Ss ax x Sx x S

=

+ + =≥

O quadro não é válido

Minimizar a folga

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

6

Grande M / 2 fases

Qual é a solução óptima?

1

1 2 1

1 2 1

. :

2 3, , 0

Min z Ss ax x Sx x S

=

+ + =≥

O quadro não é válido

Validação doQuadro Simplex

Page 4: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

4

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

7

Grande M «» 2 Fases

Variáveis artificiais permitem começar do ponto de solução nula.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

1 2

1 2

1 2 1

2 3. :

2 3, , 0

Min z x xs ax xx x S

= +

+ ≥≥

1 2

1 2

2 3, 0x xx x+ ≥

1 2 1

1 2 1 1

1 2 1 1

2 3. :

2 3, , , 0

Min z x x Mas ax x F ax x F a

= + +

+ − + =≥

O quadro não é válido

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

8

Grande M «» 2 Fases1 2

1 2

1 2 1

2 3. :

2 3, , 0

Min z x xs ax xx x S

= +

+ ≥≥

1 2

1 2

2 3, 0x xx x+ ≥

1 2 1

1 2 1 1

1 2 1 1

2 3. :

2 3, , , 0

Min z x x Mas ax x F ax x F a

= + +

+ − + =≥

O quadro não é válido

Page 5: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

5

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

9

Grande M «» 2 FasesSí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 Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

10

Grande M «» 2 FasesSí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.

Page 6: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

6

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

11

Grande M «» 2 FasesExemplo:

Validação do Quadro Simplex

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

12

Grande M «» 2 FasesExemplo:

mais negativa, entra na base

mais pequenosai da base

Não há artificiais na base, podem ser removidas do quadro e prossegue-se com o Simplex...

Page 7: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

7

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

13

Grande M «» 2 FasesExemplo:

Ponto actualentra

sai

Solução óptima

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

14

Grande M «» 2 Fases

O método das 2 fases resulta do Grande M dividindo a Função Objectivo por M ???

1 22

0 0

x x MaMax zM M M

Max z aMin w a

= + −

= + −=

Page 8: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

8

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

15

Grande M «» 2 Fases

1ª FASEPara 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 Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

16

Grande M «» 2 Fases

2ª FASESe 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

Page 9: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

9

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

17

Grande M «» 2 FasesExemplo:

1ª Fase

Validação do Quadro Simplex

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

18

Grande M «» 2 FasesExemplo:

1ª Fase

negativa (empate), entra na base

mais pequenosai da base

Não há artificiais na base, podem ser removidas do quadro

e passa-se à 2ª fase...Ponto actual

Page 10: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

10

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

19

Grande M «» 2 FasesExemplo:

2ª Fase

Validação do Quadro Simplex

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

20

Grande M «» 2 FasesExemplo:

2ª Fase

negativa, entra na base

sai da base

Solução óptima

Page 11: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

11

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

21

Simplex DUALVamos ver uma curiosidade…

Coluna pivot

VAMOS ERRAR !

Sai x4

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

22

Simplex DUALHá valores negativos nos termos independentes !!!

O que fazer?

7 5 1 7 50 1 02 4 2− − −

3 1 1 511 0 02 4 210 2 0 1 4 52− − −

50 2 4 0 0 5 7 52

Page 12: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

12

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

23

Simplex DUALReiniciar a partir do quadro original?

Desfazer o erro?

-sair x1 e entrar x4

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

7 5 1 7 50 1 02 4 2− − −

3 1 1 511 0 02 4 210 2 0 1 4 52− − −

50 2 4 0 0 5 7 52

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

24

Simplex DUALO que é necessário fazer para reparar o erro ?

transformar termos independentes em valores positivos

manter a matriz identidade

iterar, escolhendo pivots negativos

7 5 1 7 50 1 02 4 2− − −

3 1 1 511 0 02 4 210 2 0 1 4 52− − −

50 2 4 0 0 5 7 52

sai a mais negativa

Qual é a queentra?Pivots

negativos

Page 13: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

13

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

25

Simplex DUALO que é necessário fazer para reparar o erro ?

transformar os negativos em positivos

manter a matriz identidade

iterar, escolhendo pivots negativos

7 5 1 7 50 1 02 4 2− − −

3 1 1 511 0 02 4 210 2 0 1 4 52− − −

50 2 4 0 0 5 7 52

sai a mais negativa

Qual é a queentra?Pivots

negativos

Iterar, optimizando,escolhe-se a menorrazão em módulo!

Entra x4

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

26

Simplex DUALAinda há valores negativos nos termos independentes !!!

1 4 40 1 0 7 05 5−

4 11 0 0 4 05 53 20 0 1 1 05 5− − −

0 1 2 0 0 4 0 0−

Page 14: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

14

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

27

Simplex DUALQuadro válido !!!

Falta Optimizar, resolução pelo Simplex PRIMAL

8 7 01 40 0 13 3 3−

8 01 41 0 03 3 3−

5 5 020 1 03 3 3+ −

8 5 1 2 5 00 0 05 3 3+ −

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

28

Simplex DUALSolução Óptima

340 0 1 57 1 4−3 21 0 0 2 07 7−

520 1 0 2 57 1 4−

51 20 0 0 4 2 57 1 4

Page 15: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

15

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

29

Simplex DUALSó mudou a ordem das linhas

340 0 1 57 1 4−3 21 0 0 2 07 7−

520 1 0 2 57 1 4−

51 20 0 0 4 2 57 1 4

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

30

Simplex DUALExemplo

1 3

1 2 3

1 2 3

2. :

52 4 80, 1,2,3j

Min z x xs ax x xx x xx j

= +

+ − ≥

− + ≥

≥ =

1 3

1 2 3

1 2 3

- 2. :

52 4 8

0, 1,2,3j

Max z x xs ax x xx x xx j

= − −

− − + ≤ −

− + − ≤ −

≥ =

1 3

1 2 3 1

1 2 3 2

- 2. :

52 4 8

0, 1, 2,3j

Max z x xs ax x x sx x x sx j

= − −

− − + + = −

− + − + = −

≥ =

soluçãobásica

não admissível

Page 16: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

16

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

31

Simplex DUAL

Síntese: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.

sai

entra

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

32

Simplex DUAL

sai

entra

−54 , −

12 , 0 , 1 , 1

4 , − 714 , −

12 , 1 , 0 , −

14 , 2

74 , 1

2 , 0 , 0 , 14 , − 2

SoluçãoÓptima

Page 17: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

17

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

33

Simplex DUALResumo 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 Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

34

Quadro Inicial

Quadro numa

qualquer iteração

Simplex Matricial «» Revisto

Page 18: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

18

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

35

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

Simplex Matricial «» Revisto

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

36

Simplex Matricial «» Revisto1 2 3

1 2 3

1 2

2 3

5 2 34. :2 2 73 6

6 90 , 1, 2,3j

Max z x x x

s ax x xx x

x xx j

= + +

+ + ≤+ ≤+ + ≤

≥ =

1 2 3 4 5 6

1 2 3 4

1 2 5

2 3 6

52 3 0 0 04. :

2 2 73 6

6 90 , 1, 2,3,4,5,6j

Max z x x x x x x

s ax x x xx x x

x x xx j

= + + + + +

+ + + =+ + =+ + + =

≥ =

2 1 23 1 00 1 6

A =

769

b =

52 34c =

Page 19: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

19

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

37

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

Simplex Matricial «» Revisto

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

38

Simplex Matricial «» RevistoA 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.

Page 20: Investigação Operacional - pessoais.dps.uminho.ptpessoais.dps.uminho.pt/zan/IO_TSI/Aula6.pdf · 2 Universidade do Minho 2007 Investigação Operacional José António Oliveira –

20

Universidade do Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

39

Simplex Matricial «» RevistoNo 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 Minho2007

Investigação OperacionalJosé António Oliveira – [email protected]

40

Atendendo ao conceito de base de um espaço vectorial, qualquer vector Pj é dado por:

em que Xj é a representação do vector Pj em termos de base B. Donde

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.

Simplex Matricial «» Revisto

, 1, 2, ,j jP BX j n= = …

1j jX B P−=

BBX b= 1BX B b−=