Embed Size (px)
Citation preview
Faculdade de Engenharia – Optimização
Prof. Doutor Engº Jorge Nhambiu
1
Faculdade de Engenharia – Optimização
Prof. Doutor Engº Jorge Nhambiu
2
Programação Linear (PL)
• Aula 6: Método Simplex (Aula Prática)
• O método Simplex.
• Algoritmo Primal Simplex.
Faculdade de Engenharia – Optimização
Prof. Doutor Engº Jorge Nhambiu
3
Problema 6.1
A companhia Metalco deseja misturar uma nova liga
composta de Aço, Manganês e Silício. As composições das
ligas, a disponibilidade dos elementos e o preço de venda
por quilograma encontram-se na tabela seguinte:
Elementos ( x100 g/kg) Liga 1 Liga 2 Liga 3 Disponibilidade
Aço 5 5 4 5000
Silício 2 3 2 1000
Manganês 3 2 4 1500
Lucro (Mt/kg) 500 400 600
Formule um modelo de programação linear e resolva-o pelo
Método Simplex de forma a maximizar o lucro da empresa.
Faculdade de Engenharia – Optimização
Prof. Doutor Engº Jorge Nhambiu
4
Problema 6.1 (Formulação)
x1 – liga 1
x2 – liga 2
x3 – liga 3
Sejam:
O problema fica:
Maximizar 500x1+ 400 x2 + 600 x3
5 x1 + 5 x2 + 4 x3 5000
2 x1 + 3 x2 + 2 x3 1000
3 x1 + 2 x2 + 4 x3 1500
x1, x2, x3 ≥ 0
Faculdade de Engenharia – Optimização
Prof. Doutor Engº Jorge Nhambiu
5
5 x1 + 5 x2 + 4 x3 5000
2 x1 + 3 x2 + 2 x3 1000
3 x1 + 2 x2 + 4 x3 1500
5x1 + 5x2 + 4x3 + x4 = 5000
2 x1 + 3x2 + 2x3 + x5 = 1000
3x1 + 2x2 + 4x3 + x6 = 1500
x4
x5
x6
1ª
2ª
3ª
Inicialização: Redução à Forma Padrão. Exemplo Protótipo.
Restrição de desigualdade
Restrição de igualdade
Variável de folga
Faculdade de Engenharia – Optimização
Problema 6.1 (Resolução III)
Prof. Doutor Engº Jorge Nhambiu
6
cj 500 400 600 0 0 0
cB xB x1 x2 x3 x4 x5 x6 b
0 x4 5 5 4 1 0 0 5000
0 x5 2 3 2 0 1 0 1000
0 x6 3 2 4 0 0 1 1500
zj 0 0 0 0 0 0 0
cj-zj 500 400 600 0 0 0
Início: Construção do 1º QUADRO.
A SBA X0= ( 0, 0, 0, 5000, 1000,1500 )
Faculdade de Engenharia – Optimização
Problema 6.1 (Resolução IV)
Prof. Doutor Engº Jorge Nhambiu
7
cj 500 400 600 0 0 0
cB xB x1 x2 x3 x4 x5 x6 b
0 x4 5 5 4 1 0 0 5000 1250
0 x5 2 3 2 0 1 0 1000 500
0 x6 3 2 4 0 0 1 1500 375
zj 0 0 0 0 0 0 0
cj-zj 500 400 600 0 0 0
Início: Construção do 1º QUADRO.
A SBA X0= ( 0, 0, 0, 5000, 1000,1500 )
mínimo
Faculdade de Engenharia – Optimização
Problema 6.1 (Resolução V)
Prof. Doutor Engº Jorge Nhambiu
8
cj 500 400 600 0 0 0
cB xB x1 x2 x3 x4 x5 x6 b
0 x4 2 3 0 1 0 -1 3500 1166,7
0 x5 0,5 2 0 0 1 -0,5 250 125
600 x3 0,75 0,5 1 0 0 0,25 375 750
zj 450 300 600 0 0 150 225000
cj-zj 50 100 0 0 0 -150
Construção do 2º QUADRO.
A SBA X1= ( 0, 0, 375, 3500, 250,0 )
mínimo
Faculdade de Engenharia – Optimização
Problema 7.1 (Resolução VI)
Prof. Doutor Engº Jorge Nhambiu
9
cj 500 400 600 0 0 0
cB xB x1 x2 x3 x4 x5 x6 b
0 x4 1,25 0 0 1 -1,5 -0,25 3125 2500
400 x2 0,25 1 0 0 0,5 -0,25 125 500
600 x3 0,625 0 1 0 -0,25 0,375 312,5 500
zj 475 400 600 0 50 125 237500
cj-zj 25 0 0 0 -50 -125
Construção do 3º QUADRO.
A SBA X2= ( 0, 125, 312.5 , 3125, 0,0 )
mínimo
Faculdade de Engenharia – Optimização
Problema 6.1 (Resolução VII)
Prof. Doutor Engº Jorge Nhambiu
10
cj 500 400 600 0 0 0
cB xB x1 x2 x3 x4 x5 x6 b
0 x4 0 -5 0 1 -4 1 2500
500 x1 1 4 0 0 2 -1 500
600 x3 0 -2,5 1 0 -1,5 1 0
zj 500 500 600 0 100 100 250000
cj-zj 0 -100 0 0 -100 -100
Fim: Construção do 4º QUADRO.
A SBA X3= ( 500, 0, 0, 2500, 0,0 ) é óptima, Z = 250000
Faculdade de Engenharia – Optimização
Problema 6.1 (Resolução VIII)
Prof. Doutor Engº Jorge Nhambiu
11
Resposta:
Deve-se produzir 500 kg da Liga 1, nenhuma
quantidade das ligas 2 e 3, restam 2500 kg de Aço e
obtém-se um lucro de 250000 Mt.
Faculdade de Engenharia – Optimização
Prof. Doutor Engº Jorge Nhambiu
12
Problema 6.2 (I)
Numa oficina, para se produzirem atrelados do tipo A e B utilizam-
se chapa metálica de 3 mm, tubo galvanizado de diâmetro 50 mm
e rolamentos de diâmetro externo de 60 mm. Para produzir
atrelados tipo A usam-se 2 rolamentos, 3 metros de tubo e 5 m2
de chapa, enquanto para se produzir atrelados tipo B usam-se 4
rolamentos 2 metros de tubo e 4 m2 de Chapa. Os atrelados A no
mercado geram um lucro de 45 000 Mt enquanto os atrelados B
dão o lucro de 75 000 Mt. A empresa tem disponíveis 100 metros
de tubo, 100 rolamentos e 400 m2 de chapa. Desenhar o plano
óptimo de produção de modo a maximizar o lucro da empresa.
Faculdade de Engenharia – Optimização
Problema 6.2 (II)
Prof. Doutor Engº Jorge Nhambiu
13
Atrelados A Atrelados B Disponibilidade
Rolamentos 2 4 100
Tubo de 5 mm 3 2 100
Chapa 5 4 400
Lucro 45000 Mt 75000 Mt
Faculdade de Engenharia – Optimização
Prof. Doutor Engº Jorge Nhambiu
14
Problema 6.2 (Formulação)
x1 – Atrelados do tipo A
x2 – Atrelados do tipo B
Sejam:
O problema fica:
Maximizar 45000x1+ 75000 x2
2 x1 + 4 x2 100
3 x1 + 2 x2 100
5 x1 + 4 x2 400
x1, x2 ≥ 0
Faculdade de Engenharia – Optimização
Prof. Doutor Engº Jorge Nhambiu
15
2 x1 + 4 x2 100
3 x1 + 2 x2 100
5 x1 + 4 x2 400
2 x1 + 4 x2 + x3 = 100
3 x1 + 2 x2 + x4 = 100
5 x1 + 4 x2 + x5 = 400
x3
x4
x5
1ª
2ª
3ª
Inicialização: Redução à Forma Padrão. Exemplo Protótipo.
Restrição de desigualdade
Restrição de igualdade
Variável de folga
x1, x2 , x3, x4, x5 ≥ 0
Faculdade de Engenharia – Optimização
Problema 6.2 (Resolução III)
Prof. Doutor Engº Jorge Nhambiu
16
cj 45 75 0 0 0
cB xB x1 x2 x3 x4 x5 b
0 x3 2 4 1 0 0 100
0 x4 3 2 0 1 0 100
0 x5 5 4 0 0 1 400
zj 0 0 0 0 0 0
cj-zj 45 75 0 0 0
Início: Construção do 1º QUADRO.
A SBA X0= ( 0, 0, 100, 100, 400 )
Faculdade de Engenharia – Optimização
Problema 7.2 (Resolução IV)
Prof. Doutor Engº Jorge Nhambiu
17
cj 45 75 0 0 0
cB xB x1 x2 x3 x4 x5 b
0 x3 2 4 1 0 0 100 25
0 x4 3 2 0 1 0 100 50
0 x5 5 4 0 0 1 400 200
zj 0 0 0 0 0 0
cj-zj 45 75 0 0 0
Construção do 2º QUADRO.
A SBA X1= ( 0, 0, 400, 100, 100 )
mínimo
Faculdade de Engenharia – Optimização
Problema 6.2 (Resolução V)
Prof. Doutor Engº Jorge Nhambiu
18
cj 45 75 0 0 0
cB xB x1 x2 x3 x4 x5 b
75 x2 0,5 1 0,25 0 0 25 50
0 x4 2 0 -1 1 0 50 25
0 x5 3 0 -1 0 1 300 100
zj 38 75 19 0 0 1875
cj-zj 7,5 0 -19 0 0
Construção do 3º QUADRO.
A SBA X2= ( 0, 25, 300, 0, 50 )
mínimo
Faculdade de Engenharia – Optimização
Problema 6.2 (Resolução VI)
Prof. Doutor Engº Jorge Nhambiu
19
cj 45 75 0 0 0
cB xB x1 x2 x3 x4 x5 b
75 x2 0 1 0.4 -0 0 12,5
45 x1 1 0 -0 0.5 0 25
0 x5 0 0 -0 -2 1 225
zj 45 75 17 3,8 0 2062,5
cj-zj 0 0 -17 -4 0
Fim: Construção do 4º QUADRO.
A SBA X3= ( 25, 12.5, 0, 0, 225 ) é óptima, Z = 2062,5
Faculdade de Engenharia – Optimização
Problema 6.2 (Resolução VII)
Prof. Doutor Engº Jorge Nhambiu
20
Resposta:
Deve-se produzir 25 atrelados do tipo A e 12,5
atrelados do tipo B, sobra 225m2 de chapa e obtém-
se um lucro de 2.062.500 Mt.
Faculdade de Engenharia – Optimização
Prof. Doutor Engº Jorge Nhambiu
21
Problema 6.3. Maximizar
0,0,0
40322
3033
..
634
321
321
321
321
xxx
com
xxx
xxx
as
xxxZ
Faculdade de Engenharia – Optimização
Prof. Doutor Engº Jorge Nhambiu
22
3 x1 + x2 +3 x3 30
2 x1 + 2 x2 + 3 x3 40
3 x1 + x2 +3 x3 +x4= 30
2 x1 + 2 x2 + 3 x3+ x5 = 40
x4
x5
1ª
2ª
Inicialização: Redução à Forma Padrão. Exemplo Protótipo.
Restrição de desigualdade
Restrição de igualdade
Variável de folga
x1, x2 , x3, x4, x5 ≥ 0
Faculdade de Engenharia – Optimização
Problema 6.3 (Resolução II)
Prof. Doutor Engº Jorge Nhambiu
23
cj 4 3 6 0 0
cB xB x1 x2 x3 x4 x5 b
0 x4 3 1 3 1 0 30
0 x5 2 2 3 0 1 40
zj 0 0 0 0 0 0
cj-zj 4 3 6 0 0
Início: Construção do 1º QUADRO.
A SBA X0= ( 0, 0, 0, 30, 40 )
Faculdade de Engenharia – Optimização
Problema 6.3 (Resolução III)
Prof. Doutor Engº Jorge Nhambiu
24
cj 4 3 6 0 0
cB xB x1 x2 x3 x4 x5 b
0 x4 3 1 3 1 0 30 10
0 x5 2 2 3 0 1 40 13
zj 0 0 0 0 0 0
cj-zj 4 3 6 0 0
Construção do 2º QUADRO.
A SBA X0= ( 0, 0, 0, 30, 40 )
mínimo
Faculdade de Engenharia – Optimização
Problema 6.3 (Resolução IV)
Prof. Doutor Engº Jorge Nhambiu
25
cj 4 3 6 0 0
cB xB x1 x2 x3 x4 x5 b
6 x2 1 0,3 1 0,3 0 10 30
0 x5 -1 1 0 -1 1 10 10
zj 6 2 6 2 0 60
cj-zj -2 1 0 -2 0
Construção do 3º QUADRO.
A SBA X1= ( 0, 10, 0, 0, 10 )
mínimo
Faculdade de Engenharia – Optimização
Problema 6.3 (Resolução V)
Prof. Doutor Engº Jorge Nhambiu
26
cj 4 3 6 0 0
cB xB x1 x2 x3 x4 x5 b
6 x2 1,3 0,0 1,0 0,7 -0,3 6,7
3 x5 -1 1 0 -1 1 10
zj 5,0 3,0 6,0 1,0 1,0 70,0
cj-zj -1,0 0,0 0,0 -1,0 -1,0
Fim: Construção do 4º QUADRO.
A SBA X2= ( 0, 6.7, 0, 0,10 ) é óptima, Z = 70
Faculdade de Engenharia – Optimização
Trabalho para Casa 02 (I)
Uma certa indústria do ramo electrónico tirou de produção uma certa linha de
produto não lucrativo. Isso criou um considerável excedente na capacidade de
produção. A gerência está considerando dedicar essa capacidade excedente a um
ou mais produtos, identificados como Produtos 1, 2 e 3. A capacidade disponível
das máquinas que poderia limitar a produção está resumida na tabela a seguir:
Prof. Doutor Engº Jorge Nhambiu
27
Tipo de máquina Tempo disponível
(horas de máquinas)
A 500
B 350
C 150
Faculdade de Engenharia – Optimização
Trabalho para Casa 02 (II)
O número de horas de máquina requerido por unidade dos respectivos produtos é
conhecido como coeficiente de produtividade (em horas de máquina por unidade),
conforme representado a seguir:
Prof. Doutor Engº Jorge Nhambiu
28
Tipo de máquina Produto 1 Produto 2 Produto 3 A 9 3 5 B 5 4 0 C 3 0 2
O lucro unitário estimado é de $ 30, $ 12 e $ 15, respectivamente, para os
produtos 1, 2 e 3.
Determine a quantidade de cada produto que a firma deve produzir para maximizar
o seu lucro.
Entregar em manuscrito, até 10 minutos do início da aula de quinta-feira dia 16 de
Agosto de 2012 ao Engº Chirrime.
