Softwares

1

Pesquisa Operacional

Instituto de Engenharia de Produção e Gestão

Universidade Federal de Itajubá

Prof. Dr. José Arnaldo Barra Montevechi

Exemplo 4.6.4 – Uso de softwares

Resolver os problemas do item 4.5 pelo simplex

Eu não aguento todo aquelealgebrismo!

2

Calma existem softwares para o

problema!

O Lindo é um deles.

Opção para evitar o simplex manualmente

O solver é outra opção

3

Outras opções

Linprog;

QM for windows;

DS for windows;

Matlab;

Etc...

Vejamos alguns destes....

Softwares para auxiliar a solução dos problemas

LINPROG

4

O problema de Giapetto

Max Z = 3X1 + 2X2 sujeito a:

2X1 + X2 ≤ 100 X1 + X2 ≤ 80 X1 ≤ 40 X1 ≥ 0 X2 ≥ 0

Solução pelo simplex

5

Resolva o problema abaixo usando o linprog

max Z = 5X1 + 2X2 sujeito a:

X1≤ 3 X2 ≤ 4 X1 + 2X2 ≤ 9 X1 ≥ 0 X2 ≥ 0

Solução pelo linprog

6

Procedimentos para minimizar Z

Item 4.6.5 - Exemplo 1min Z = 2x1 - 3x2sujeito a:x1 + x2 ≤ 4 x1 - x2 ≤ 6x1 ≥ 0x2 ≥ 0

Dá para resolver diretamente pelo Simplex?

7

Converter o problema de PL na forma canônica

min Z = 2x1 - 3x2sujeito a:x1 + x2 + x3 = 4 x1 - x2 + x4 = 6x1 ≥ 0x2 ≥ 0

Trabalhando a FO

min Z = 2x1 - 3x2Z = -2x1 + 3x2Para minimizar a Função (-Z):max (-Z) = -2x1 + 3x2

8

Nova formulação

Max (-Z) = - 2x1 + 3x2

sujeito a:

x1 + x2 + x3 = 4

x1 - x2 + x4 = 6

x1 ≥ 0

x2 ≥ 0

Variáveis não básicas: X1 = X2 = 0

Variáveis básicas: X3 = 4 X4 = 6

Solução básica inicialMax (-Z) = - 2x1 + 3x2

sujeito a:

x1 + x2 + x3 = 4

x1 - x2 + x4 = 6

x1 ≥ 0

x2 ≥ 0

9

Pivô

O problema pode ser representado assim:

Z X1 X2 X3 X4 b Razão Base -1 2 -3 0 0 0 X3 0 1 1 1 0 4 X4 0 1 -1 0 1 6

4/1=46/-1

Indica que X2 entra nolugar de X3Solução parcial: (0, 0, 4, 6)

Próximo quadro - Base: X2 e X4

Devem se colocadas na forma canônica

X2 entra na base

solução é ótima

Valor máximo possívelpara a função objetivo

Solução ótima: (0, 4, 0, 10)

Segunda iteração

Z X1 X2 X3 X4 b Razão Base -1 5 0 3 0 12 X2 0 1 1 1 0 4 X4 0 2 0 1 1 10

10

Solução do problema pelo simplex

Solução ótima: (0, 4, 0, 10) Z = 2*0 - 3*4 = -12

min Z = 2x1 - 3x2sujeito a:x1 + x2 ≤ 4 x1 - x2 ≤ 6x1 ≥ 0x2 ≥ 0

ExercícioResolver o problema da 2 do item 4.6.5 da apostila;

Usar o linprog.

11

4.6.5 - Exemplo 2min Z = 4x1 - x2sujeito a:2x1 + x2 ≤ 8 x2 ≤ 5x1 - x2 ≤ 4 x1 ≥ 0x2 ≥ 0

Z X1 X2 X3 X4 X5 b razãoBase -1 4 -1 0 0 0 0

X3 0 2 1 1 0 0 8 8X4 0 0 1 0 1 0 5 5X5 0 1 -1 0 0 1 4 -4

Z X1 X2 X3 X4 X5 b razãoBase -1 4 0 0 1 0 5

X3 0 2 0 1 -1 0 3X2 0 0 1 0 1 0 5X5 0 1 0 0 1 1 9

4.6.5 - Exemplo 2

12


O método BIG M

13

Item 4.7.2 - Exemplo 1 min Z = 2x1 + 3x2sujeito a:1/2x1 + 1/4x2 ≤ 4 x1 + 3x2 ≥ 20x1 + x2 = 10 x1 ≥ 0x2 ≥ 0

Dá para resolver pelo Simplex?


14

ExercícioResolver o problema da 2 do item 4.7.2 da apostila;

Usar o linprog.

Item 4.7.2 - Exemplo 2min Z = 2x1 + 3x2sujeito a:2x1 + x2 ≥ 4 x1 - x2 ≥ -1 x1 ≥ 0x2 ≥ 0

15


Lindo ?

Vamos ver outra opção de software!

O Lindo!

Outro software

16

LINDO (Linear, Interactive and Discrete

Optmizer)Software desenvolvido pela Lindo Systems Inc. de Chicago Illinois, EUA.

Resolve modelos de programação linear, quadrática ou inteira.

No quadro a seguir encontra-se as versões disponíveis.

Site da Web: http://www.lindo.com

LINDO (Linear, Interactive and Discrete

Optmizer) Limites

máximos

Versão Linhas Colunas

Demonstração 150 300

Super 500 1000

Hiper 2000 4000

Industrial 8000 16000

Extended 32000 100000

*

* Versão utilizada no curso

17

Vamos resolver o problema do Giapetto no Lindo



2X1 + X2 ≤ 100 X1 + X2 ≤ 80 X1 ≤ 40 X1 ≥ 0 X2 ≥ 0

18

Formular no Lindo o problema 4.5.2

4.5.2 - Exemplo 2: Problema de orçamento de capital

Uma empresa de petróleo esta considerando 5 diferentes oportunidades de investimento. O fluxo de caixa e o Valor Presente Líquido das alternativas são dadas na tabela a seguir:

Alternativa 1 Alternativa 2 Alternativa 3 Alternativa 4 Alternativa 5 Investimento data 0

11

53

5

5

29

Investimento data 1

3

6

5

1

34

VPL 13

16

16

14

39

19

A empresa tem 40 milhões para investir hoje, e estima que no ano posterior terá 20 milhões. A empresa pode comprar qualquer fração de cada investimento, os investimentos e VPL são ajustados na proporção. Por exemplo, se a empresa compra (1/5) da alternativa 3, então 1 milhão é necessário na data 0 e na data 1.VPL = (1/5)16 = 3,2 milhões.


A empresa quer maximizar o VPL obtido para os investimentos de 1 a 5. Formular o problema.

Assumir que qualquer recurso não usado na data 0, não poderá ser usado na 1.


20

FormulaçãoMax Z = 13X1 +16X2 +16X3 +14X4 + 39X5sujeito a:

11X1 + 53X2 + 5X3 + 5X4 +29 X5 ≤ 40

3X1 + 6X2 + 5X3 + X4 + 34X5 ≤ 20

X1 ≤ 1

X2 ≤ 1

X3 ≤ 1

X4 ≤ 1

X5 ≤ 1

Xi ≥ 0 i = 1, 2, 3, 4, 5

Solução problema 4.5.2

X1 = X3 = X4 = 1X2 = 0,201X5 = 0,288Z = 57,449

21

Problema 4.5.2

Resposta:

X1 = X3 = X4 = 1

X2 = 0,201

X5 = 0,288

Z = 57,449

Max Z = 13X1 +16X2 +16X3 +14X4 + 39X5sujeito a:

11X1 + 53X2 + 5X3 + 5X4 +29 X5 ≤ 40

3X1 + 6X2 + 5X3 + X4 + 34X5 ≤ 20

X1 ≤ 1

X2 ≤ 1

X3 ≤ 1

X4 ≤ 1

X5 ≤ 1

Xi ≥ 0 i = 1, 2, 3, 4, 5

O QM for windows é outra opção

22

Vamos resolver o problema do Giapetto no QM



2X1 + X2 ≤ 100 X1 + X2 ≤ 80 X1 ≤ 40 X1 ≥ 0 X2 ≥ 0

23

Formular no QM o problema 4.5.2




11

53

5

5

29

Investimento data 1

3

6

5

1

34

VPL 13

16

16

14

39

24






25


11X1 + 53X2 + 5X3 + 5X4 +29 X5 ≤ 40

3X1 + 6X2 + 5X3 + X4 + 34X5 ≤ 20

X1 ≤ 1

X2 ≤ 1

X3 ≤ 1

X4 ≤ 1

X5 ≤ 1

Xi ≥ 0 i = 1, 2, 3, 4, 5


X1 = X3 = X4 = 1X2 = 0,201X5 = 0,288Z = 57,449

26

Problema 4.5.2

Resposta:

X1 = X3 = X4 = 1

X2 = 0,201

X5 = 0,288

Z = 57,449


11X1 + 53X2 + 5X3 + 5X4 +29 X5 ≤ 40

3X1 + 6X2 + 5X3 + X4 + 34X5 ≤ 20

X1 ≤ 1

X2 ≤ 1

X3 ≤ 1

X4 ≤ 1

X5 ≤ 1

Xi ≥ 0 i = 1, 2, 3, 4, 5

O solver do excel também é uma boa opção

27

Solver do Excel

O Microsoft Excel Solver usa o código de otimização não linear GeneralizedReduced Gradient (GRG2), desenvolvido por Leon Lasdon, da University of Texas em Austin, e Allan Waren, da Cleveland State University.

Os problemas lineares e de inteiros usam o método

simplex com limites sobre as variáveis e o método de

desvio e limite, implementado por John Watson e

Dan Fylstra, da Frontline Systems, Inc.

Site da Web: http://www.frontsys.com

Planilhas com exemplos: arquivos de

programas\microsoft

office\office\exemplos\solver\exemsolv.xls

Solver do Excel

28

Solver do Excel

Exemplos da planilha:• Guia rápido

• Combinação de produtos

• Rotas de transporte

• Planejamento de pessoal

• Maximizar a renda

• Carteira de ações

• Design de engenharia

Vamos resolver o problema do Giapetto no Solver do

Excel

29



2X1 + X2 ≤ 100 X1 + X2 ≤ 80 X1 ≤ 40 X1 ≥ 0 X2 ≥ 0

Formular no solver o problema 4.5.2

30




11

53

5

5

29

Investimento data 1

3

6

5

1

34

VPL 13

16

16

14

39



31





11X1 + 53X2 + 5X3 + 5X4 +29 X5 ≤ 40

3X1 + 6X2 + 5X3 + X4 + 34X5 ≤ 20

X1 ≤ 1

X2 ≤ 1

X3 ≤ 1

X4 ≤ 1

X5 ≤ 1

Xi ≥ 0 i = 1, 2, 3, 4, 5

32


X1 = X3 = X4 = 1X2 = 0,201X5 = 0,288Z = 57,449

Problema 4.5.2

Resposta:

X1 = X3 = X4 = 1

X2 = 0,201

X5 = 0,288

Z = 57,449


11X1 + 53X2 + 5X3 + 5X4 +29 X5 ≤ 40

3X1 + 6X2 + 5X3 + X4 + 34X5 ≤ 20

X1 ≤ 1

X2 ≤ 1

X3 ≤ 1

X4 ≤ 1

X5 ≤ 1

Xi ≥ 0 i = 1, 2, 3, 4, 5

33

Formular no Lindo, QM e no solver o problema 4.5.1

4.5.1 - Exemplo 1: Problema de programação do trabalho

Uma empresa de entregas necessita de diferentes números de funcionários durante os diferentes dias da semana. Os números de funcionários necessários é mostrado na tabela a seguir.

34


Número de funcionários necessários

Dia 1 = Segunda-feira 17

Dia 2 = Terça-feira 13 Dia 3 = Quarta-feira 15 Dia 4 = Quinta-feira 19 Dia 5 = Sexta-feira 14 Dia 6 = Sábado 16 Dia 7 = Domingo 11


As leis do sindicado asseguram que os funcionários devem trabalhar 5 dias consecutivos e 2 de folga. Por exemplo, um funcionário que trabalhou de Segunda a Sexta folga Sábado e Domingo.

O escritório quer funcionar apenas com funcionários de tempo integral.

Formular o problema de tal modo que a empresa possa minimizar o número de empregados de tempo integral que precisam ser contratados.

35

Formulação

min Z = X1 + X2 + X3 + X4 + X5 + X6 + X7

sujeito a:X1 + X4 + X5 + X6 + X7 ≥ 17 (SEG)

X1 + X2 + X5 + X6 + X7 ≥ 13 (TER)

X1 + X2 + X3 + X6 + X7 ≥ 15 (QUAR)

X1 + X2 + X3 + X4 + X7 ≥ 19 (QUIN)

X1 + X2 + X3 + X4 + X5 ≥ 14 (SEX)

X2 + X3 + X4 + X5 + X6 ≥ 16 (SAB)

X3 + X4 + X5 + X6 + X7 ≥ 11 (DOM)

Xi ≥ 0 (i = 1; 2;....; 7)


X1 = 4/3X2 = 10/3X3 = 2X4 = 22/3X5 = 0X6 = 10/3X7 = 5Z = 67/3

X1 = 2X2 = 4X3 = 2X4 = 8X5 = 0X6 = 4X7 = 5Z = 25

Exemplo típico para programação inteira! Será visto oportunamente.

36

Problema 4.5.1min Z = X1 + X2 + X3 + X4 + X5 + X6 + X7

sujeito a:X1 + X4 + X5 + X6 + X7 ≥ 17 (SEG)

X1 + X2 + X5 + X6 + X7 ≥ 13 (TER)

X1 + X2 + X3 + X6 + X7 ≥ 15 (QUAR)

X1 + X2 + X3 + X4 + X7 ≥ 19 (QUIN)

X1 + X2 + X3 + X4 + X5 ≥ 14 (SEX)

X2 + X3 + X4 + X5 + X6 ≥ 16 (SAB)

X3 + X4 + X5 + X6 + X7 ≥ 11 (DOM)

Xi ≥ 0 (i = 1; 2;....; 7)

X1 = 4/3X2 = 10/3X3 = 2X4 = 22/3X5 = 0X6 = 10/3X7 = 5Z = 67/3

Education

Softwares