Lista de Exercicios - Pesquisa Operacional

Prévia do material em texto

19/03/2013
1
1
© UNESP 6 Agosto 2008
Autor: Anibal Tavares de Azevedo
Limeira, 20 de Março 2013
TÓPICOS EM PESQUISA OPERACIONAL
LISTA 4 – Resolução dos exercícios 1 até 9
2
© UNESP 6 Agosto 2008
Max z=4x1 + 3x2
S.a.: x1 + 3x2 ≤ 7
2x1 + 2x2 ≤ 8 
x1 + x2 ≤ 3 
x2 ≤ 2
x1, x2 ≥ 0
Exercício 1:Encontrar a solução ótima.
FORMULAÇÃO MATEMÁTICA
19/03/2013
2
3
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
7/3
4 6 8-2
x1 + 3x2 ≤ 7
x2 ≤ 2
3
3 7
2
2x1 + 2x2 ≤ 8 x1 + x2 ≤ 3
4
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
7/3
4 6 8-2
x1 + 3x2 ≤ 7
x2 ≤ 2
3
3 7
2
2x1 + 2x2 ≤ 8
Região
factível
x1 + x2 ≤ 3
19/03/2013
3
5
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
7/3
4 6 8-2
3
3 7
2






=










=∇
3
4
2
1
dx
dz
dx
dz
f
6
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
7/3
4 6 8-2
3
3 7
2
Solução ótima
O ponto ótimo 
pode ser determinado
numericamente, 
pois é a intersecção
de: x1 + x2 = 3
e: x2 = 0
A solução do sistema
fornece:
(x1, x2)=(3, 0)
x1 + x2 ≤ 3
19/03/2013
4
7
© UNESP 6 Agosto 2008
Min z=x1 + 2x2
S.a.: x1 + x2 ≥ 1
-5x1 + 2x2 ≥ -10 
3x1 + 5x2 ≥ 15 
x1, x2 ≥ 0
Exercício 2:Encontrar a solução ótima.
FORMULAÇÃO MATEMÁTICA
8
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
2
x2
2 100
-2
-4
4 6 8-2
x1 + x2 ≥ 1
4
-6
5
3 -5x1 + 2x2 ≥ -10
3x1 + 5x2 ≥ 15
x1≥ 0
x2≥ 0
19/03/2013
5
9
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
2
x2
2 100
-2
-4
4 6 8-2
4
-6
5
3
Região
factível
10
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
2
x2
2 100
-2
-4
4 6 8-2
4
-6
5
3 





=










=∇
2
1
2
1
dx
dz
dx
dz
f
19/03/2013
6
11
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
2
x2
2 100
-2
-4
4 6 8-2
4
-6
5
3 -5x1 + 2x2 = -10
(x1, x2) = (45/31, 80/31):
z = 1x1 + 2x2
= 1*80/31 + 2*45/31
=135/31 = 4,35
(x1, x2) = (0, 3):
z= 1x1 + 2x2
= 1*0 + 2*3
= 0 + 6 
= 6
3x1 + 5x2 = 15
A intersecção ocorre em:
(x1, x2) = (80/31, 45/31)
12
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
2
x2
2 100
-2
-4
4 6 8-2
4
-6
5
3
Solução ótima
O ponto ótimo 
pode ser determinado
numericamente, 
pois é a intersecção
de: 3x1 + 5x2 = 15
e: -5x1 + 2x2 = -10
A solução do sistema
fornece: (x1, x2)=
(80/31, 45/31)
19/03/2013
7
13
© UNESP 6 Agosto 2008
Max z=4x1 + 8x2
S.a.: 3x1 + 2x2 ≤ 18
x1 + x2 ≤ 5 
x1 ≤ 4
x1, x2 ≥ 0
Exercício 3:Encontrar a solução ótima.
FORMULAÇÃO MATEMÁTICA
14
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
5
4 6 8-2 5
2
10
9
3x1 + 2x2 ≤ 18
x1 + x2 ≤ 5
x1 ≤ 4
19/03/2013
8
15
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
5
4 6 8-2 5
2
10
9
3x1 + 2x2 ≤ 18
x1 + x2 ≤ 5
x1 ≤ 4
Região
factível
16
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
5
4 6 8-2 5
2
10
9






=










=∇
8
4
2
1
dx
dz
dx
dz
f
19/03/2013
9
17
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
5
4 6 8-2 5
2
10
9
Solução ótima
O ponto ótimo 
pode ser determinado
numericamente, 
pois é a intersecção
de: x1 + x2 = 5
e: x1 = 0
A solução do sistema
fornece:
(x1, x2)=(0, 5)
x1 + x2 ≤ 5
18
© UNESP 6 Agosto 2008
Max z=8x1 + 10x2
S.a.: -x1 + x2≤ 2
4x1 +5x2≥ 20 
x1 ≤ 6
x2 ≥ 4
x1, x2 ≥ 0
Exercício 4:Encontrar a solução ótima.
FORMULAÇÃO MATEMÁTICA
19/03/2013
10
19
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
5
4 6 8-2 5
2
10
-x1 + x2≤ 2
4x1 +5x2≥ 20
x2 ≤ 4
x1 ≤ 6
20
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
5
4 6 8-2 5
2
10
-x1 + x2≤ 2
4x1 +5x2≥ 20
x2 ≤ 4
x1 ≤ 6
Região
factível
19/03/2013
11
21
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
5
4 6 8-2 5
2
10






=










=∇
10
8
2
1
dx
dz
dx
dz
fSolução ótima
O ponto ótimo 
pode ser determinado
numericamente, 
pois é a intersecção
-x1 + x2 = 2 
e: x1 = 6
A solução do sistema
fornece:
(x1, x2)=(6, 8)
22
© UNESP 6 Agosto 2008
Min z= x1 + 3x2
S.a.: 4x1 + x2≥ 30
10x1 +2x2≤ 10 
x1, x2 ≥ 0
Exercício 5:Encontrar a solução ótima.
FORMULAÇÃO MATEMÁTICA
19/03/2013
12
23
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
x2
0 10
30
20 30-2
10
4x1 + x2≥ 30
10x1 +2x2≤ 10
20
24
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
x2
0 10
30
20 30-2
10
4x1 + x2≥ 30
10x1 +2x2≤ 10
20
Sem Região
factível !
19/03/2013
13
25
© UNESP 6 Agosto 2008
Min z=6x1 + 10x2
S.a.: -x1 + x2 ≤ 2
x1 ≤ 5
x2 ≤ 6
3x1 + 5x2 ≥ 15
5x1 + 4x2 ≥ 20
x1, x2 ≥ 0
Exercício 6:Encontrar a solução ótima.
FORMULAÇÃO MATEMÁTICA
26
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
-x1 + x2 ≤ 2
x1 ≤ 5
x2 ≤ 6
19/03/2013
14
27
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
-x1 + x2 ≤ 2
3x1 + 5x2 ≥ 15
x1 ≤ 5
x2 ≤ 6
28
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
-x1 + x2 ≤ 2
3x1 + 5x2 ≥ 15
5x1 + 4x2 ≥ 20
x1 ≤ 5
x2 ≤ 6
19/03/2013
15
29
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
Região
factível
30
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
Região
factível






=










=∇
10
6
2
1
dx
dz
dx
dz
f
19/03/2013
16
31
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
Múltiplas
soluções






−
−
=










−
−
=∇−
10
6
2
1
dx
dz
dx
dz
f






=










=∇
10
6
2
1
dx
dz
dx
dz
f
32
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
Múltiplas
soluções
(x1, x2) = (5, 0)
z = 6x1 + 10x2
= 6*5 + 10*0
=30
(x1, x2) = (3, 6/5)
z= 6x1 + 10x2
= 6*3 + 10*6/5
=18 + 12 
= 30
19/03/2013
17
33
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
3x1 + 5x2 = 15
5x2 = 15- 3x1
x2 = 3-3/5 x1
6x1 + 10x2=0
10x2=- 6x1
x2= -3/5 x1
Coeficiente angular 
da restrição e da 
função objetivo 
são iguais !
Múltiplas soluções
34
© UNESP 6 Agosto 2008
Max z=6x1 + 10x2
S.a.: -x1 + x2 ≤ 2
x1 ≥ 5
x2 ≤ 6
3x1 + 5x2 ≥ 15
5x1 + 4x2 ≥ 20
x1, x2 ≥ 0
FORMULAÇÃO MATEMÁTICA
Exercício 7:Encontrar a solução ótima.
19/03/2013
18
35
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
Região
factível
x1 ≥ 5
36
© UNESP 6 Agosto 2008
Max Z = 6x1 + 10x2
19/03/2013
19
37
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
Eixo x
1
E
ix
o 
x
2
Curvas de nível
0 5 10 15 20
0
1
2
3
4
5
6
7
8
z=110z=90 z=130 z=190z=170z=150
z=190
38
© UNESP 6 Agosto 2008
Eixo x
1
E
ix
o 
x 2
Curvas de nível
0 5 10 15 20 25 30
0
1
2
3
4
5
6
7
8
RESOLUÇÃO GRÁFICA
z=120z=100 z=140 z=200z=180z=160
z=200
19/03/2013
20
39
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
Região
factível






=










=∇
10
6
2
1
dx
dz
dx
dz
f
x1 ≥ 5
40
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
Solução ilimitada
(z tão grande quanto se queira, ou
seja, x 1 pode crescer sem limite)
19/03/2013
21
41
© UNESP 6 Agosto 2008
Max z=6x1 + 10x2
S.a.: -x1 + x2 ≤ 2
x1 ≤ 5
x2 ≤ 6
3x1 + 5x2 ≥ 15
5x1 + 4x2 ≤ 20
x1, x2 ≥ 0
FORMULAÇÃO MATEMÁTICA
Exercício 8:Encontrar a solução ótima.
42
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
-x1 + x2 ≤ 2
x1 ≤ 5
x2 ≤ 6
19/03/2013
22
43
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
-x1 + x2 ≤ 2
3x1 + 5x2 ≥ 15
x1 ≤ 5
x2 ≤ 6
44
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
-x1 + x2 ≤ 2
3x1 + 5x2 ≥ 15
5x1 + 4x2 ≤ 20
x1 ≤ 5
x2 ≤ 6
19/03/2013
23
45© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
Região
factível
46
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2






=










=∇
10
6
2
1
dx
dz
dx
dz
f
Região
factível
19/03/2013
24
47
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
Solução ótima
O ponto ótimo 
pode ser determinado
numericamente, 
pois é a intersecção
de: -x1 + x2 = 2
e: 5x1 + 4x2 = 20
A solução do sistema
fornece:
(x1,x2)=(12/9,30/9)
-x1 + x2 ≤ 2
5x1 + 4x2 ≤ 20
48
© UNESP 6 Agosto 2008
Max z=6x1 + 10x2
S.a.: -x1 + x2 ≤ 2
x1 ≤ 5
x2 ≤ 6
3x1 + 5x2 ≤ 15
5x1 + 4x2 ≥ 20
x1, x2 ≥ 0
FORMULAÇÃO MATEMÁTICA
Exercício 9:Encontrar a solução ótima.
19/03/2013
25
49
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
-x1 + x2 ≤ 2
x1 ≤ 5
x2 ≤ 6
50
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
-x1 + x2 ≤ 2
3x1 + 5x2 ≤ 15
x1 ≤ 5
x2 ≤ 6
19/03/2013
26
51
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
-x1 + x2 ≤ 2
3x1 + 5x2 ≤ 15
5x1 + 4x2 ≥ 20
x1 ≤ 5
x2 ≤ 6
52
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
Região
factível
19/03/2013
27
53
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
Região
factível






=










=∇
10
6
2
1
dx
dz
dx
dz
f
54
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
Região
factível






=










=∇
10
6
2
1
dx
dz
dx
dz
f
Múltiplas
soluções
19/03/2013
28
55
© UNESP 6 Agosto 2008
RESOLUÇÃO GRÁFICA
x1
8
x2
0 2 10
6
4
2
4 6 8-2
Múltiplas
soluções
(x1, x2) = (5, 0)
z = 6x1 + 10x2
= 6*5 + 10*0
=30
(x1, x2) = (3, 6/5)
z= 6x1 + 10x2
= 6*3 + 10*6/5
=18 + 12 
= 30
56
© UNESP 6 Agosto 2008
OBRIGADO !!!
FIM !!!