Faculdade de Engenharia Optimização · Faculdade de Engenharia – Optimização Prof Dr, Engº Jorge Nhambiu 3 Problema 11.1 12 12 12 12 12 4.. 25 24 3 0, 0 Minimizar z x x sa

Faculdade de Engenharia – Optimização

Prof, Doutor Engº Jorge Nhambiu

1


Prof Dr, Engº Jorge Nhambiu

2

Aula 11. Aula Prática (PL)

• O método Simplex,

• Método das Duas Fases

• Método do Big M



3

Problema 11.1

1 2

1 2

1 2

1 2

1 2

4

. .

2 5

2 4

3

0, 0

Minimizar z x x

s a

x x

x x

x x

com

x x

Resolver pelo método das Duas fazes e pelo Big M


Prof Dr. Engº Jorge Nhambiu

4

Problema 11.1 Reduzir à forma padrão

1 2

1 2 3

1 2 5

1 2 4 6

1 2 3 4 5 6

z 4

. .

2 5

2 4

3

0, 0, 0, 0, 0, 0

Minimizar x x

s a

x x x

x x x

x x x x

com

x x x x x x


Prof Dr. Engº Jorge Nhambiu

5

Problema 11.1 Construir o Problema Auxiliar

5 6

1 2 3

1 2 5

1 2 4 6

1 2 3 4 5 6

z

. .

2 5

2 4

3

0, 0, 0, 0, 0, 0

Minimizar x x

s a

x x x

x x x

x x x x

com

x x x x x x



6

1ª Tabela Simplex (1ª fase)

Cj 0 0 0 0 1 1

CB xB x1 x2 x3 x4 x5 x6 b

0 x3 1 2 1 0 0 0 5 5

1 x5 2 1 0 0 1 0 4 2

1 x6 1 -1 0 -1 0 1 3 3

zj 3 0 0 -1 1 1 7

zj- cj 3 0 0 -1 0 0

A SBA X0= (0,0,5,0,4, 3 )



7

2ª Tabela Simplex (1ª fase) Fim

Cj 0 0 0 0 1 1


0 x3 0 1,5 1 0 -0,5 0 3

0 x1 1 0,5 0 0 0,5 0 2

1 x6 0 -1,5 0 -1 -0,5 1 1

zj 0 -1,5 0 -1 -0,5 1 1

zj- cj 0 -1,5 0 -1 -1,5 0

A SBA X1= (2,0,3,0,0, 1 )



8

1ª Tabela Simplex

Cj 1 4 0 0 M M


0 x3 1 2 1 0 0 0 5 5

M x5 2 1 0 0 1 0 4 2

M x6 1 -1 0 -1 0 1 3 3

zj 3M 0 0 -1M 1M 1M 7M

zj- cj 3M-1 -4 0 -1M 0 0

A SBA X0= (0,0,5,0,4, 3 )



9

2ª Tabela Simplex

Cj 1 4 0 0 M M


0 x3 0 3/2 1 0 -1/2 0 3

1 x1 1 1/2 0 0 1/2 0 2

M x6 0 -1/2 0 -1 -1/2 1 1

zj 1 -(M-1)/2 0 -1M -(M-1)/2 1M M+2

zj- cj 0 -(M+7)/2 0 -1M -(3M-1)/2 0

A SBA X1= (2,0,3,0,0, 1 )



10

Problema 11.2

1 2

1 2

1 2

1 2

3 2

. .

0

2

0, 0

Maximizar z x x

s a

x x

x x

com

x x



11

Problema 11.2 Reduzir à Forma Padrão

1 2

1 2 3

1 2 4 5

1 2 3 4 5

3 2

. .

0

2

0, 0, 0, 0, 0

Maximizar z x x

s a

x x x

x x x x

com

x x x x x



12


5

1 2 3

1 2 4 5

1 2 3 4 5

. .

0

2

0, 0, 0, 0, 0

Minimizar z x

s a

x x x

x x x x

com

x x x x x



13

1ª Tabela Simplex (1ª fase)

A SBA X0= (0,0,0,0,0, 2 )

Cj 0 0 0 0 1

xB x1 x2 x3 x4 x5 b

0 x3 -1 1 1 0 0 0

1 x5 1 1 0 -1 1 2 2

zj 1 1 0 -1 1 2

zj-cj 1 1 0 -1 0



14


A SBA X1= (2,0,2,0,0, 0 )

Cj 0 0 0 0 1

xB x1 x2 x3 x4 x5 b

0 x3 0 2 1 -1 1 2

0 x1 1 1 0 -1 1 2

zj 0 0 0 0 0 0

zj-cj 0 0 0 0 -1



15


A SBA X2= (2,0,2,0,0, 0 )

Cj 3 -2 0 0 0

xB x1 x2 x3 x4 x5 b

0 x3 0 2 1 -1 1 2

3 x1 1 1 0 -1 1 2

zj 3 3 0 -3 3 6

cj-zj 0 -5 0 3 -3



16

Problema 11.3

1 2

1 2

1 2

1 2

1 2

1 2

z 4

. .

2 5

2 4

2 4

1

0, 0

Maximizar x x

s a

x x

x x

x x

x x

com

x x



17

Problema 11.3 Reduzir à Forma Padrão

1 2

1 2 3

1 2 4

1 2 5 7

1 2 6 8

1 2 3 4 5 6 7 8

4

. .

2 5

2 4

2 4

1

0, 0, 0, 0, 0, 0, 0, 0

Maximizar Z x x

s a

x x x

x x x

x x x x

x x x x

com

x x x x x x x x



18


7 8

1 2 3

1 2 4

1 2 5 7

1 2 6 8

1 2 3 4 5 6 7 8

z

. .

2 5

2 4

2 4

1

0, 0, 0, 0, 0, 0, 0, 0

Minimizar x x

s a

x x x

x x x

x x x x

x x x x

com

x x x x x x x x



19

1ª Tabela Simplex

A SBA X0= (0,0,5, 4,0,0, 4,1 ); Z = 5

Cj 0 0 0 0 0 0 1 1

xB x1 x2 x3 x4 x5 x6 x7 x8 b

0 x3 1 2 1 0 0 0 0 0 5

0 x4 2 1 0 1 0 0 0 0 4

1 x7 2 1 0 0 -1 0 1 0 4

1 x8 1 -1 0 0 0 -1 0 1 1

zj 3 0 0 0 -1 -1 1 1 5

zj-cj 3 0 0 0 -1 -1 0 0



20

2ª Tabela Simplex

A SBA X1= (1,0,4,0,0,0,2,0 ) Z = 2

Cj 0 0 0 0 0 0 1 1

xB x1 x2 x3 x4 x5 x6 x7 x8 b

0 x3 0 3 1 0 0 1 0 -1 4 1,33

0 x4 0 3 0 1 0 2 0 -2 2 0,67

1 x7 0 3 0 0 -1 2 1 -2 2 0,67

0 x1 1 -1 0 0 0 -1 0 1 1 -1,00

zj 0 3 0 0 -1 2 1 -2 2

zj-cj 0 3 0 0 -1 2 0 -3



21

3ª Tabela Simplex (Fim da 1ª Fase)

A SBA X2= (1.67,0,67,2, 0.0,0,0,0 ); Z = 0

Cj 0 0 0 0 0 0 1 1

xB x1 x2 x3 x4 x5 x6 x7 x8 b

0 x3 0 0 1 0 1 -1 -1 1 2

0 x4 0 0 0 1 1 0 -1 0 0

0 x2 0 1 0 0 -0,33 0,67 0,33 -0,67 0,67

0 x1 1 0 0 0 -0,33 -0,33 0,33 0,33 1,67

zj 0 0 0 0 0 0 0 0 0

zj-cj 0 0 0 0 0 0 -1 -1



22

1ª Tabela Simplex (Fim da 2ª fase)

A SBA X3= (1.6,0.6,2,0,0,0,0, 0); é óptima Z = 4,3

cj 1 4 0 0 0 0 0 0

xB x1 x2 x3 x4 x5 x6 x7 x8 b

0 x3 0,00 0,00 1,00 -1,00 0,00 -1,00 0,00 1,00 2,00

0 x4 0,00 0,00 0,00 1,00 1,00 0,00 -1,00 0,00 0,00

4 x2 0,00 1,00 0,00 0,33 0,00 0,67 0,00 -0,67 0,67

1 x1 1,00 0,00 0,00 0,33 0,00 -0,33 0,00 0,33 1,67

zj 1,00 4,00 0,00 1,67 0,00 2,33 0,00 -2,33 4,33

cj-zj 0,00 0,00 0,00 -1,67 0,00 -2,33 0,00 2,33


Trabalho para Casa Nº 4

Uma fábrica produz chapas de alumínio em rolos e para tal recebe rolos de 2

metros de largura e 70 metros de comprimento. As encomendas para o

próximo mês são pelo menos:

70 rolos de 70 centímetros de largura;

100 rolos de 60 centímetros de largura;

120 rolos de 50 centímetros de largura.

Admitindo que todos os rolos são fornecidos com 70 metros de

comprimento, pretende-se programar o corte de rolos de modo a satisfazer

totalmente a procura e minimizar o desperdício da chapa de alumínio.

Entregar até 10 minutos do início da aula de 30 de Agosto de 2012.

Prof, Doutor Engº Jorge Nhambiu

23

Documents

Faculdade de Engenharia Optimização · Faculdade de Engenharia – Optimização Prof Dr, Engº Jorge Nhambiu 3 Problema 11.1 12 12 12 12 12 4.. 25 24 3 0, 0 Minimizar z x x sa