Lista Simplex II

Prévia do material em texto

Nome: Amanda Siman Fauro
Matrícula: 613945
Lista Simplex II
01) Resolva pelo Simplex, usando o método M grande para obter a solução básica inicial.
Max z = 2x1 + 3x2
Sujeito a:
x1 + x2 ≥ 10
2x1 +x2 ≤ 16
x1 ≥ 0, x2 ≥ 0
Resposta:
x1 + x2 ≥ 10 → x1 + x2 - xF1 + a1 = 10
2x1 +x2 ≤ 16 → 2x1 + x2 + xF2 = 16
Max z = 2x1 + 3x2 - M1 a1
z = 2x1 + 3x2 - M1a1 → z - 2x1 - 3x2 + M1a1 = 0
x1 + x2 - xF1 + a1 = 10
2x1 + x2 + xF2 = 16
z x1 x2 xF1 xF2 a1 b
L1 z 1 -2 -3 0 0 M1 0
L2 a1 0 1 1 -1 0 1 10
L3 xF2 0 2 1 0 1 0 16
Para eliminar o a1:
considerando xF1 = 0, temos:
10 / 1 = 10
16 / 2 = 8 , considerando o menor positivo, temos a L3, eliminando o xF2, porém é
necessário eliminar o a1, com isso considerando o xF2 = 0, temos:
10 / 1 = 10
16 / 1 = 16, considerando o menor positivo, conseguimos eliminar o a1, transformando a L2
em pivô e L5, fazemos: L5 = L2 / 1, ficando:
z x1 x2 xF1 xF2 a1 b
L4 z 1 -2 -3 0 0 M1 0
L5 x2 0 1 1 -1 0 1 10
L6 xF2 0 2 1 0 1 0 16
Fazendo pivotamento para excluirmos o menor negativo, temos:
z x1 x2 xF1 xF2 a1 b
1 1 0 -3 0 M1 + 3 30
0 1 1 -1 0 1 10
0 1 0 1 1 -1 6
Como temos a = 0, fazemos o pivotamento novamente para buscar uma solução ótima:
z x1 x2 xF1 xF2 b
1 4 0 0 3 48
0 2 1 0 1 16
0 1 0 1 1 6
Solução:
z = 48 xF1 = 6
x1 = 0 xF2 = 0
x2 = 16
02) Resolva pelo Simplex, usando o método da função objetiva artificial para obter a solução
básica inicial.
Min z = 3x1 + 2x2
Sujeito a:
2x1 + x2 ≥ 10
x1 +5x2 ≥ 15
x1 ≥ 0, x2 ≥ 0
2x1 + x2 ≥ 10 → 2x1 + x2 - xF1 + a1 = 10 → a1 = 10 - 2x1 - x2 + xF1
x1 +5x2 ≥ 15 → x1 + 5x2 - xF2 + a2 = 15 → a2 = 15 - x1 - 5x2 + xF2
somando a1 + a2, temos:
10 - 2x1 - x2 + xF1
+
15 - x1 - 5x2 + xF2
w = 25 - 3x1 - 6x2 + xF1 + xF2
min w = max - w → - 25 + 3x1 + 6x2 - xF1 - xF2
Min z = 3x1 + 2x2 = Max -z = -3x1 - 2x2 → -z + 3x1 + 2x2 = 0
2x1 + x2 - xF1 + a1 = 10
x1 + 5x2 - xF2 + a2 = 15
Max - w = - 25 + 3x1 + 6x2 - xF1 - xF2 → -w - 3x1 - 6x2 + xF1 + xF2 = - 25
z/w x1 x2 xF1 xF2 a1 a2 b
L1 -1 3 2 0 0 0 0 0
L2 0 2 1 -1 0 1 0 10
L3 0 1 5 0 -1 0 1 15
L4 -1 -3 -6 1 1 0 0 -25
Para zerar os as, temos:
10 / 1 = 10
15 / 5 = 3 , utilizando a L3 como pivô, encontramos o seguinte pivotamento:
-z/-w x1 x2 xF1 xF2 a1 a2 b
L1 -1 2,6 0 0 0,4 0 -0,4 -6
L2 0 1,8 0 -1 0,2 1 -0,2 7
L3 0 0,2 1 0 -0,2 0 0,2 3
L4 -1 -1,8 0 1 -0,2 0 1,2 -7
Fazendo um novo pivô pelo menor negativo temos:
7 / 1,8 = 3,88
3 / 0,2 = 15, utilizando L2 como pivô, encontramos o seguinte pivotamento:
-z/-w x1 x2 xF1 xF2 a1 a2 b
L1 -1 0 0 1,444 0,111 -1,444 -0,111 -16,111
L2 0 1 0 -0,556 0,111 0,556 -0,111 3,889
L3 0 0 1 0,111 -0,222 -0,111 0,222 2,222
L4 -1 0 0 0 0 1 1 0
Solução:
z = 16,111 xF1 = 0 a2 = 0
x1 = 3,889 xF2 = 0
x2 = 2,222 a1 = 0
03) Resolva usando Simplex
Max z = x1 + x2 + 2x3
Sujeito a:
x1 + 2x2 ≤ 10
3x1 + 4x2 + x3 ≤ 20
x1 ≥ 0, x3 ≥ 0, x2 livre
Substituindo x2 pela diferença de duas variáveis (x4 - x5), temos:
z = x1 + (x4 - x5) + 2x3
Sujeito a:
x1 + 2 (x4 - x5) ≤ 10
3x1 + 4 (x4 - x5) + x3 ≤ 20
x1 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0
z = x1 + (x4 - x5) + 2x3 → z - x1 - x4 + x5 - 2x3 = 0
x1 + 2 (x4 - x5) ≤ 10 → x1 + 2x4 - 2x5 + xF1 = 10
3x1 + 4 (x4 - x5) + x3 ≤ 20 → 3x1 + 4x4 - 4x5 + x3 + xF2 = 20
z x1 x3 x4 x5 xF1 xF2 b
L1 1 -1 -2 -1 1 0 0 0
L2 0 1 0 2 -2 1 0 10
L3 0 3 1 4 -4 0 1 20
Para fazer o pivô, escolhendo o menor positivo e fazendo o pivotamento, temos:
10 / 0 = ?
20 / 1 = 20
z x1 x3 x4 x5 xF1 xF2 b
L1 1 5 0 7 -7 0 2 40
L2 0 1 0 2 -2 1 0 10
L3 0 3 1 4 -4 0 1 20
Para fazer o pivô, escolhendo o menor positivo e fazendo o pivotamento, temos:
10 / -2 = -5
20 / -4 = -5
Temos uma solução ilimitada.
04) Mostre que o problema tem várias soluções
Min z = 2x1 + 4x2+ 10x3
Sujeito a:
x1+ x2 + x3 ≤ 120
x1 + 2x2 + 5x3 ≥ 30
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
x1+ x2 + x3 ≤ 120 → x1 + x2 + x3 + xF1 = 120
x1 + 2x2 + 5x3 ≥ 30 → x1 + 2x2 + 5x3 - xF2 + a1 = 30 → a1 = 30 - x1 - 2x2 - 5x3 + xF2
Min z = 2x1 + 4x2+ 10x3 = Max -z = -2x1 - 4x2 - 10x3 → -z + 2x1 + 4x2 + 10x3 = 0
x1 + x2 + x3 + xF1 = 120
x1 + 2x2 + 5x3 - xF2 + a1 = 30
z x1 x2 x3 xF1 xF2 a1 b
L1 -1 2 4 10 0 0 0 0
L2 0 1 1 1 1 0 0 120
L3 0 1 2 5 0 -1 1 30
Para fazer o pivô, escolhendo o menor positivo e fazendo o pivotamento, temos:
120 / 1 = 120
30 / 5 = 6
z x1 x2 x3 xF1 xF2 a1 b
L1 -1 0 0 0 0 2 -2 -60
L2 0 0,8 0,6 0 1 0,2 -0,2 114
L3 0 0,2 0,4 1 0 -0,2 0,2 6
Neste caso temos uma solução múltipla, pois nas minhas variáveis não básicas, temos o
coeficiente zero e o resto dos valores não são igual a 1.
05) Resolva usando Simplex
Min z = 2x1 + 4x2 + 5x3
Sujeito a:
x1 + 2x2 + 10x3 ≤ 600
x1 - x2 + x3 ≥ 50
2x1 - x3 ≤ 100
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
Min z = 2x1 + 4x2 + 5x3 = Maz - z = -2x1 - 4x2 - 5x3 = -z + 2x1 + 4x2 + 5x3 = 0
x1 + 2x2 + 10x3 ≤ 600 → x1 + 2x2 + 10x3 + xF1 = 600
x1 - x2 + x3 ≥ 50 → x1 - x2 + x3 - xF2 + a1 = 50 → a1 = 50 - x1 + x2 - x3 + xF2
2x1 - x3 ≤ 100 → 2x1 - x3 + xF3 = 100
z x1 x2 x3 xF1 xF2 xF3 a1 b
L1 -1 2 4 5 0 0 0 0 0
L2 0 1 2 10 1 0 0 0 600
L3 0 1 -1 1 0 -1 0 1 50
L4 0 2 0 -1 0 0 1 0 100
Para fazer o pivô, escolhendo o menor positivo e fazendo o pivotamento, temos:
600 / 10 = 60
50 / 1 = 50
100 / -1 = -100
z x1 x2 x3 xF1 xF2 xF3 a1 b
L1 -1 -3 9 0 0 5 0 -5 -250
L2 0 -9 12 0 1 10 0 -10 100
L3 0 1 -1 1 0 -1 0 1 50
L4 0 3 -1 0 0 -1 1 1 150
Como a1 = 0, podemos concluir que nossa solução é:
z = 250 xF1 = 100
x1 = 0 xF2 = 0
x2 = 0 xF3 = 150
x3 = 50 a1 = 0
06) Verifique se a solução do modelo abaixo é ilimitada. Qual a melhor solução básica antes
que a solução fique ilimitada?
Max z = x1 + 2x2 + x3
Sujeito a:
2x1 + 3x2 + x3 ≥ 10
4x1 + x2 + 2x3 ≥ 20
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
2x1 + 3x2 + x3 ≥ 10 → 2x1 + 3x2 + x3 - xF1 + a1 = 10 → a1 = 10 - 2x1 - 3x2 - x3 + xF1
4x1 + x2 + 2x3 ≥ 20 → 4x1 + x2 + 2x3 - xF2 + a2 = 20 → a2 = 20 - 4x1 - x2 - 2x3 + xF2
somando a1 + a2, temos:
10 - 2x1 - 3x2 - x3 + xF1
+
20 - 4x1 - x2 - 2x3 + xF2
w = 30 - 6x1 - 4x2 - 3x3 + xF1 + xF2 → w + 6x1 + 4x2 + 3x3 + xF1 + xF2 = 30
z = x1 + 2x2 + x3 → z - x1 - 2x2 - x3 = 0
z/w x1 x2 x3 xF1 xF2 a1 a2 b
L1 1 -1 -2 -1 0 0 0 0 0
L2 0 2 3 1 -1 0 1 0 10
L3 0 4 1 2 0 -1 0 1 20
L4 1 6 4 3 1 1 0 0 30
Para zerar os as, temos:
10 / 3 = 3,33
20 / 1 = 20
30 / 4 = 7,5, utilizando a L2 como pivô, encontramos o seguinte pivotamento:
z/w x1 x2 x3 xF1 xF2 a1 a2 b
L1 1 0,333 0 -0,333 -0,667 0 0,667 0 6,667
L2 0 0,667 1 0,333 -0,333 0 0,333 0 3,333
L3 0 3,333 0 1,667 0,333 -1 -0,333 1 16,667
L4 1 3,333 0 1,667 2,333 1 -1,333 0 16,667
Escolhendo o menor negativo, e fazendo um novo pivotamento, temos:
3,333 / 0,333 = 10,01
16,667 / 1,667 = 9,99
16,667 / 1,667 = 9,99
z/w x1 x2 x3 xF1 xF2 a1 a2 b
L1 1 0,999 0 0 -0,600 -0,200 0,600 0,200 9,996
L2 0 0,001 1 0 -0,400 0,200 0,400 -0,200 0,004
L3 0 1,999 0 1 0,200 -0,600 -0,200 0,600 9,998
L4 1 0 0 0 2 2 -1 -1 0
Não é uma solução ilimitada, e a solução básica inicial é:
z = 9,996 xF1 = 0 w = 0
x1 = 0 xF2 = 0
x2 = 0,004 a1 = 0
x3 = 9,998 a2 = 0
07) Minimizar z = 3x1 + 2x2 + x3
Sujeito a:
3x1 + x2 + 3x3 ≥ 6
3x1 + 2x2 = 6
x1 - x2 ≤ 1
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
Min z = Max -z = -3x1 - 2x2 - x3 → -z + 3x1 + 2x2 + x3 = 0
3x1 + x2 + 3x3 ≥ 6 → 3x1 + x2 + 3x3 - xF1 + a1 = 6 → a1 = 6 - 3x1 - x2 - 3x3 + xF1
3x1 + 2x2 = 6 → 3x1 + 2x2 + a2 = 6 → a2 = 6 - 3x1 - 2x2
x1 - x2 ≤ 1 → x1 - x2 + xF2 = 1
somando a1 + a2:
6 - 3x1 - x2 - 3x3 + xF1
+
6 - 3x1 - 2x2
w = 12 - 6x1 - 3x2 - 3x3 + xF1
min w = max - w → - 12 + 6x1 + 3x2 + 3x3 - xF1
Max - w = - 12 + 6x1 + 3x2 - xF1 → -w - 6x1 - 3x2 - 3x3 + xF1 = - 12
z/w x1 x2 x3 xF1 xF2 a1 a2 b
L1 -1 3 2 1 0 0 0 0 0
L2 0 3 1 3 -1 0 1 0 6
L3 0 3 2 0 0 0 0 1 6
L4 0 1 -1 0 0 1 0 0 1
L5 -1 -6 -3 -3 1 0 0 0 -12
Para fazer o pivô, escolhendo o menor positivo e fazendo o pivotamento, temos:
6 / 3 = 2
6 / 3 =2
1 / 1 = 1
-12 / -6 = 2
z/w x1 x2 x3 xF1 xF2 a1 a2 b
L1 -1 0 5 1 0 -3 0 0 -3
L2 0 0 4 3 -1 -3 1 0 3
L3 0 0 5 0 0 -3 0 1 3
L4 0 1 -1 0 0 1 0 0 1
L5 -1 0 -9-3 1 6 0 0 -6
Para fazer o pivô, escolhendo o menor positivo e fazendo o pivotamento, temos:
3 / 4 = 0,75
3 / 5 = 0,6
1 / -1 = -1
-6 / -9 = 0,66
z/w x1 x2 x3 xF1 xF2 a1 a2 b
L1 -1 0 0 1 0 0 0 -1 -6
L2 0 0 0 3 -1 -0,6 1 -0,8 0,6
L3 0 0 1 0 0 -0,6 0 0,2 0,6
L4 0 1 0 0 0 0,4 0 0,2 1,6
L5 -1 0 0 -3 1 0,6 0 1,8 -0,6
Solução:
z = 6 xF1 = 0 w = 0,6
x1 = 1,6 xF2 = 0
x2 = 0,6 a1 = 0,6
x3 = 0 a2 = 0
08) Um distribuidor de produtos para festas infantis compra dos produtores chapéus de papel,
línguas-de-sogra e bexigas, e prepara caixas com esses três produtos na forma de kits para
festas. Observações anteriores mostram que:
a) A quantidade de chapéus e línguas-de-sogra deve ser pelo menos 50% do total.
b) O pacote deve ter pelo menos 20 bexigas.
c) Cada item deve concorrer com pelo menos 25% do total da caixa. O custo dos
componentes (em milhares de unidades) é: Chapéu de papel : 50.000 Língua-de-sogra :
20.000 Bexigas : 5.000
Qual a composição da caixa que tem o menor custo?
x1 = chapéu de papel
x2 = língua de sogra
x3 = bexigas
Custo
x1 Qnt de x1 50
x2 Qtd de x2 20
x3 Qtd de x3 5
Min custo = 50x1 + 20x2 + 5x3
R01 → x1 + x2 ≥ 0,5
R02 → x3 ≥ 0,2
R03 → x1 ≥ 0,25
R04 → x2 ≥ 0,25
R05 → x3 ≥ 0,25
x1, x2, x3 ≥ 0
09) Uma empresa dispõe de recursos produtivos suficientes para produzir 3 diferentes
produtos P1, P2 e P3. A capacidade de armazenagem se fosse fabricado apenas um produto,
seria de:
1.000 unidades para P1
900 unidades para P2
1.200 unidades para P3
Espera-se ter que armazenar no máximo a produção de 5 dias. A capacidade de produção por
hora para cada produto individualmente é de: 10 unidades para P1; 6 unidades para P2 e 15
unidades para P3. A disponibilidade é de 8h/dia.
A disponibilidade diária de matéria-prima, usada nos 3 produtos, é de 240 kg. O uso por
unidade de produto é de: 1,5 kg para P1, 2,4 kg para P2 e 2 kg para P3.
Se os lucros unitários são de 500 u.m. para P1, 800 u.m. para P2 e 400 u.m. para P3, qual a
produção diária ótima?
x1 = P1
x2 = P2
x3 = P3
Cap
estocagem
Matéria
prima
Cap
Produção
Lucros
x1 Qtd x1 1.00 1,5 10 500
x2 Qtd x2 900 2,4 6 800
x3 Qtd x3 1.200 2 15 400
Total 240
Max lucro = 500x1 + 800x2 + 400x3
Rmp: 1,5x1 + 2,4x2 + 2x3 <=240
REstocagem (armazenar por 5 dias)
P1 → x1 / 1.000 = 5x1 / 1.000
P2 → x2 / 900 = 5x2 / 900
P3 → x3 / 1.200 = 5x3 / 1.200
(5x1/1000) + (5x2 / 900) + (5x3/1200) < = 1
RDisponibilidade 8hrs/dia
R01 → 10 * 8 = 80 - x1 < = 80
R02 → 6 * 8 = 48 - x2 < = 48
R03 → 15 * 8 = 120 - x3 < = 120
x1, x2, x3 ≥ 0