Pesquisa Operacional - Lista de Exercícios 2017 Gabarito

Prévia do material em texto

RESPOSTAS DA LISTA DE EXERCÍCIOS 
Matéria – Programação Linear 
 
1. MAX Z = 3000 LB + 5000 LA 
 
0,5 LB + 0,2 LA <= 16 
0,25 LB + 0,3 LA <= 11 
0,25 LB + 0,5 LA <= 15 
 
2. MAX Z= 100 E + 80 M + 120 A + 20 P 
 
1 E + 1 M + 1 A + 4 P <= 250 
0 E + 1 M + 1 A + 2 P <= 600 
3 E + 2 M + 4 A + 0 P <= 500 
 
3. MIN Z = 30000 REV + 200000 TV + 5000 RAD 
 
1 REV + 10 TV + 0,8 RAD >= 80 
0,7 REV + 8 TV + 0,2 RAD >= 60 
 
4. MAX Z = 3,5 MC + 5 ML 
 
1 MC + 1,5 ML <= 400 
MC <= 300 
ML <= 150 
 
5. MIN Z = 1 M1 + 2 M2 + 3 M3 + 2 M4 
 
8 M1 + 4 M2 + 2 M3 + 0 M4 >= 500 
0 M1 + 1 M2 + 2 M3 + 3 M4 >= 350 
 
6. MIN Z = X1 + X2 + X3 + X4 + X5 + X6 
 
X6 + X1 >= 22 
X1 + X2 >= 55 
X2 + X3 >= 88 
X3 + X4 >= 110 
X4 + X5 >= 44 
X5 + X6 >= 33 
 
Todas as variáveis são inteiras. 
 
7. MIN Z = 350 (ND + NJ + NF) + 450 (XD + XJ + XF) + 050 (ED + EJ + EF) 
 
ND <= 1300 
NJ <= 1300 
NF <= 1300 
 
XD <= 400 
XJ <= 400 
XF <= 400 
 
EJ <= 350 
EF <= 350 
ED <= 350 
 
ND + XD >= 400 
NJ + XJ >= 400 
NF + XF >= 400 
 
ND + XD + ED >= 1200 
NJ + XJ + EJ >= 1900 
NF + XF + EF >= 1200 
 
ED = 0 
EJ = ND + XD + ED - 1200 
EF = NJ + XJ + EJ - 1900 
EM = 0 
 
8. MAX Z = 35 (S1 + S2 + S3 + S4) + 
 28 (Z1 + Z2 + Z3 + Z4) + 
 22 (A1 + A2 + A3 + A4) – 
 19 (S1 + Z1 + A1) – 
 24 (S2 + Z2 + A2) – 
 20 (S3 + Z3 + A3) – 
 27 (S4 + Z4 + A4) 
 
S1 + Z1 + A1 <= 3500 
S2 + Z2 + A2 <= 2200 
S3 + Z3 + A3 <= 4200 
S4 + Z4 + A4 <= 1800 
 
0,3 (S1 + S2 + S3 + S4) >= S1 
0,4 (S1 + S2 + S3 + S4) <= S2 
0,5 (S1 + S2 + S3 + S4) >= S3 
 
0,3 (Z1 + Z2 + Z3 + Z4) >= Z1 
0,1 (Z1 + Z2 + Z3 + Z4) <= Z2 
 
0,7 (A1 + A2 + A3 + A4) >= A1 
 
9. 
 
10. MAX Z = 1000 O + 1500 P + 4500 T 
 
1,5 O + 1 P + 3 T <= 600 
P >= O + T 
 
11. MAX Z = 10 P1 + 20 P2 + 15 P3 + 25 P4 + 
 8 M1 + 16 M2 + 12 M3 + 20 M4 
 
P1 + P2 + P3 + P4 <= 48 
M1 + M2 + M3 +M4 <= 32 
 
550 P1 + 580 P2 + 640 P3 + 700 P4 + 400 M1 + 420 M2 + 460 M3 + 500 M4 <= 48000 
 
10 P1 + 8 M1 <= 100 
20 P2 + 16 M2 <= 100 
15 P3 + 12 M3 <= 100 
25 P4 + 20 M4 <= 100 
 
12. MIN Z = 60 C + 25 D 
 
C >= 5 
D <= 40 
 
500 C + 250 D >= 5000 
500 C + 250 D <= 20000 
 
3 C + 4 D <= 180 
50 C + 50 D <= 2500 
 
 SEGUNDA PARTE 
 
MAX Z = 150 C + 100 D (RECEITA) 
MAX Z = 90 C + 75 D (LUCRO) 
 
13. MIN Z = 700 RT207 + 1500 RT407 
 
30 RT207 + 65 RT407 >=700 
3 RT207 + 5 RT407 <= 60 
 
14. MAX Z = 2,16 T + 1,26 A + 0,812 M 
 
0,2 T + 0,3 A + 0,4 M <= 60 
T + A + M <= 200000 
 
T >= 400 
A >= 800 
M >= 10000 
 
15. MAX Z = 5000 (M1 + M2 + M3) + 4000 (A1 + A2 + A3) + 1800 (F1 + F2 + F3) 
 
M1 + M2 + M3 <= 660 
A1 + A2 + A3 <= 880 
F1 + F2 + F3 <= 400 
 
M1 + A1 + F1 <= 400 
M2 + A2 + F2 <= 650 
M3 + A3 + F3 <= 350 
 
5,5 M1 + 4 A1 + 3,5 F1 <= 1800 
5,5 M2 + 4 A2 + 3,5 F2 <= 2200 
5,5 M3 + 4 A3 + 3,5 F3 <= 950 
 
(M1 + A1 + F1)/400 = (M2 + A2 + F2)/650 = (M3 + A3 + F3)/350 
 
16. MAX Z = C + N 
 
3 N + 2 C <= 70 
2 N + 2 C <= 18 
1500 N + 1000 C <= 80000 
 
17. MAX Z = 1,56 CAIXA + 0,765 ACOES + 48,3 LETRAS + 15 TESOURO – 180000 
 
0,45 ACOES + CAIXA + 30 LETRAS + 10 TESOURO <= 180000 
0,45 ACOES + 30 LETRAS <= 150000 
 
ACOES <= 20000 
LETRAS <= 4000 
CAIXA >= 20000 
 
10 TESOURO <= 2 CAIXA 
 
18. MAX Z = 6000 (UPR + UCE + UPO) + 
 8000 (CPR + CCE + CPO) + 
 5000 (SPR + SCE + SPO) 
 
UPR + CPR + SPR <= 2000 
UCE + CCE + SCE <= 3000 
UPO + CPO + SPO <= 1500 
 
60 UPR + 50 CPR + 25 SPR <= 100000 
60 UCE + 50 CCE + 25 SCE <= 135000 
60 UPO + 50 CPO + 25 SPO <= 30000 
 
UPR + UCE + UPO <= 6000 
CPR + CCE + CPO <= 4000 
SPR + SCE + SPO <= 2000 
 
(UPR + CPR + SPR)/2000 = (UCE + CCE + SCE)/3000 = (UPO + CPO + SPO)/1500 
 
19. 
 
20. 
 
21. 
 
22. 
 
23. 
 
24. 
 
25. 
 
 
Matéria – Simplex, Branch and Bound e Método Gráfico 
 
1. 
Quadro final do primeiro modelo 
BASE X1 X2 X3 X4 X5 d 
X1 1 0 1 0 0 3 
X4 0 0 0,5 1 -0,5 1 
X2 0 1 -0,5 0 0,5 3 
Z 0 0 4 0 1 21 
 
Quadro final do segundo modelo 
BASE X1 X2 X3 X4 d 
X1 1 0,5 0,5 0 7 
X4 0 2 -1 1 10 
Z 0 1,5 4,5 0 63 
 
Quadro final do terceiro modelo 
BASE X1 X2 X3 X4 X5 d 
X1 1 0 0,5 0 0 2 
X2 0 1 -0,33 0,33 0 2,66 
X5 0 0 -0,66 -0,33 1 1,33 
Z 0 0 4 4 0 64 
 
Matéria – Programação Inteira 
 
1. MAX Z = 10 A + 15 B + 12 C 
 
7 A + 3 B + 1 C <= 28 + 5 Y1 + 15 Y2 
2 A + 4 B + 6 C <= 19 + 12 Z1 + 32 Z2 
 
500 Y1 + 800 Y2 + 300 Z1 + 900 Z2 <= 1500 
 
Y1 + Y2 <= 1 
Z1 + Z2 <= 1 
 
Y1, Y2, Z1 e Z2 são binárias. 
 
2. MIN Z = 0.085 X1 + 0.08 X2 + 0.10 X3 + 0.09 X4 
 
X1 + X2 +X3 + X4 >= 10000 
 
X1 >= 2000 F1 
X1 <= 5000 F1 
X2 >= 3000 F2 
X2 <= 4500 F2 
 
X3 >= 7000 F3 
X3 <= 10000 F3 
X4 >= 5000 F4 
X4 <= 8000 F4 
 
F1, F2, F3 e F4 são binárias. 
X1, X2, X3 e X4 são inteiras. 
 
3. MAX Z = 7 FG + 5 FB + 6 FV + 4 DG + 3 DB + 5 DV 
 
FG + 15 FB + 18 FV + 12 DG + 10 DB+ 17 DV <= 33 
 
FG >= DG 
FB >= DB 
FV >= DV 
 
Todas as variáveis são binárias. 
 
4. MAX Z = 200 P11 + 250 P12 + 240 P13 + 240 P14 
 150 P21 + 175 P22 + 165 P23 + 140 P24 
 90 P31 + 102 P32 + 80 P33 + 70 P34 
 
P11 + P12 + P13 + P14 = 1 
P21 + P22 + P23 + P24 = 1 
P31 + P32 + P33 + P34 = 1 
 
X1 = 1000 P11 + 500 P12 + 300 P13 + 200 P14 
X2 = 500 P21 + 250 P22 + 150 P23 + 100 P24 
X3 = 300 P31 + 170 P32 + 80 P33 + 50 P34 
 
0,3 X1 + 0,4 X2 + 0,4 X3 <= 2000 
0,5 X2 + 0,4 X3 <= 1000 
0,2 X3 <= 500 
 
As variáveis Pij são binárias. 
 
5. MAX Z = 56 P1 + 40 P2 + 71 P3 + 25 P4 
 
D1 + D4 <= 1 
D1 >= D2 
 
P1 <= 10000 D1 
P2 <= 1 D2 
P3 <= 3 D3 
P4 <= 1 D4 
 
CA0 = 100 P1 + 200 P2 + 190 P3 + 300 P4 
CA1 = 40 P1 + 100 P2 - 200 P3 -200 P4 
CA2 = 40 P1 + 100 P2 – 50 P3 + 100 P4 
 
EA0 + EA1 <= 1 
RO <= 1 
 
CA0 <= 550 + 180 EA0 
CA1 <= 200 + 180 EA1 + (550 + 180EAD - CA0) 
CA2 <= 200 + 80 RO + (200 + 180 EA1 + (550 + 180EAD - CA0) - CA1) 
 
As variáveis Pj são inteiras. As variáveis Dj são binárias. As variáveis EA0, EA1 e RO são reais. 
 
6. MAX Z = A1 + A2 + A3 + A4 + 
 B1 + B2 + B3 + B4 + 
 C1 + C2 + C3 + C4 + 
 D1 + D2 + D3 + D4 
 
A2 + A3 + B2 + B3 + C2 + C3 <= 2 
 
A2 + B2 + C2 + D2 <= 2 
A3 + B3 + C3 + D3 <= 2 
A4 + B4 + C4 + D4 <= 2 
 
A1 + A2 + A3 + A4 <= 1 
B1 + B2 + B3 + B4 <= 1 
C1 + C2 + C3 + C4 <= 1 
D1 + D2 + D3 + D4 <= 1 
 
2,5 A1 + 3,5 A2 + 2,8 A3 + 3,0 A4 + 
3,0 B1 + 4,0 B2 + 3,5 B3 + 4,0 B4 + 
4,0 C1 + 5,0 C2 + 4,2 C3 + 4,5 C4 + 
6,0 D1 + 5,8 D2 + 6,0 D3 + 5,0 D4 <= 8 
 
A1 + B1 + C1 + D1 >= 2 U 
A1 + B1 + C1 + D1 <= 3 U 
 
Todas as variáveis são binárias. 
 
7. MAX Z = 04 X11 + 06 X12 + 10 X13 + 12 X14 + 14 X15 + 
 02 X21 + 06 X22 + 08 X23 + 10 X24 + 12 X25 + 
 06 X31 + 12 X32 + 14 X33 + 18 X34 + 20 X35 + 
 01 X41 + 04 X42 + 08 X43 + 16 X44 + 20 X45 
 
X11 + X12 + X13 + X14 + X15 <= 1 
X21 + X22 + X23 + X24 + X25 <= 1 
X31 + X32 + X33 + X34 + X35 <= 1 
X41 + X42 + X43 + X44 + X45 <= 1 
 
1 X11 + 2 X12 + 3 X13 + 4 X14 + 5 X15 + 
1 X21 + 2 X22 + 3 X23 + 4 X24 + 5 X25 + 
1 X31 + 2 X32 + 3 X33 + 4 X34 + 5 X35 + 
1 X41 + 2 X42 + 3 X43 + 4 X44 + 5 X45 <= 7 
 
Todas as variáveis são binárias. 
 
 
8. MAX Z = 240000 A1 + 290000 A2 + 320000 A3 
 
300 A1 + 300 A2 + 300 A3 <= 3000 
 
D1 + D2 + D3 + D12 + D23 = 1 
 
A1 >= 1 D1 + 1 D12 
A1 <= 100 D1 + 100 D12 
A2 >= 1 D2 + 1 D12 + 1 D23 
A2 <= 100 D2 + 100 D12 + 100 D23 
A3 >= 1 D3 + 1 D23 
A3 <= 100 D3 + 100 D23 
 
0,3 (A1 + A2 +A3) <= A1 + 100 D2 + 100 D3 + 100 D23 
0,3 (A1 + A2 +A3) <= A2 + 100 D1 + 100 D3 
0,3 (A1 + A2 +A3) <= A3 + 100 D1 + 100 D2 + 100 D12 
 
D1, D2, D3, D12 e D23 são binárias. 
A1, A2 e A3 são inteiras. 
 
Matéria – Modelos de Rede e Transporte 
 
1. MIN Z = 2 A1 + 4 A2 + 9 A3 + 5 A4 + 
 5 B1 + 2 B2 + 2 B3 + 2 B4 + 
 6 C1 + 8 C2 + 10 C3 + 4 C4 
 
A1 + A2 + A3 + A4 <= 2300 
B1 + B2 + B3 + B4 <= 850 
C1 +C2 + C3 + C4<= 1200 
 
A1 + B1 + C1 >= 900 
A2 + B2 + C2 >= 1350 
A3 + B3 + C3 >= 1000 
A4 + B4 + C4 >= 1100 
 
2. MIN Z = 0,130 A1 + 0,124 A2 + 0,123 A3 + 
 0,132 B1 + 0,280 B2 + 0,132 B3 + 0,133 B4 + 
 0,116 C11 + + 0,114 C31 + 0,112 C41 
 0,149 C12 + + 0,147 C32 + 0,145 C42 
 
A1 + A2 + A3 + <= 5000 
B1 + B2 + B3 + B4 <= 9000 
C11 + + C31 + C41 <= 4000 
C12 + + C32 + C42 <= 2500 
 
A1 + B1 + C11 + C12 >= 4500 
A2 + B2 >= 6200 
A3 + B3 + C31 + C32 >= 5100 
 B4 + C41 + C42 >= 2700 
 
3. MIN Z = 10 AB + 9 AC + 8 BD + 7 CD + 6 CE + 4 DF + 6 DG + 5 EG + 5 FH + 4 GH 
 
AB + AC = 1 
AB = BD 
AC = CD + CE 
BD + CD = DF + DG 
CE = EG 
EG + DG = GH 
DF = FH 
FH + GH = 1 
 
Todas as variáveis são binárias. 
 
4. MAX Z = 0,2 (F1E1) + 0,3 (R1E1 + R2E1) + 0,5 (C1E1) 
 
M1F1 = F1E1 
M1F2 = F2R1 + F2R2 
M1F3 = F3R1 + F3R2 
F2R1 + F3R1 = R1C1 + R1E1 
F2R2 + F3R2 = R2C1 + R2E1 
R1C1 + R2C1 = C1E1 
F1E1 + R1E1 + R2E1 = M1F1 + M1F2 + M1F3 
 
M1F1 + M1F2 + M1 F3 <= 10000 
M1F1 <= 5000 
M1F2 <= 4000 
M1F3 <= 3000 
F2R1 + F3R1 <= 6500 
F2R2 + F3R2 <= 7500 
R1C1 + R2C1 <= 5000 
F1E1 + R1E1 + R2E1 + C1E1 <= 12000 
 
F1E1 <= 8000 
R1E1 + R2E1 <= 5000 
C1E1 <= 3500 
 
5. MIN Z = 600 X11 + 850 X12 + 400 X13 + 550 X14 + 
 750 X21 + 900 X22 + 500 X23 + 700 X24 + 
 500 X31 + 800 X32 + 600 X33 + 650 X34 
 
X11 + X12 + X13 + X14 <= 14 
X21 + X22 + X23 + X24 <= 17 
X31 + X32 + X33 + X34 <= 11 
 
X11 + X21 + X31 >= 10 
X12 + X22 + X32 >= 10 
X13 + X23 + X33 >= 10 
X14 + X24 + X34 >= 10 
 
6. 
 
 
7. MIN Z = 400 MA + 580 MB + 220 FA + 380 FB + 140 KA + 200 KB 
 
MA + MB <= 10 
FA + FB <= 8 
KA + KB <= 5 
 
700 MA + 450 FA + 100 KA >= 4500 
700 MB + 450 FB + 100 KB >= 6000 
 
8. MIN Z = 4,0 B1 + 6,5 B2 + 3,9 B3 + 9,8 B4 + 6,0 B5 + 3,3 B6 + 
 3,2 V1 + 7,4 V2 + 5,5 V3 + 10,5 V4 + 4,1 V5 + 2,5 V6 + 
 3,9 S1 + 6,8 S2 + 4,8 S3 + 12,3 S4 + 4,5 S5 + 2,7 S6 
 
B1 + B2 + B3 + B4 + B5 + B6 = 2 
V1 + V2 + V3 + V4 + V5 + V6 = 2 
S1 + S2 + S3 + S4 + S5 + S6 = 2 
 
B1 + V1 + S1 = 1 
B2 + V2 + S2 = 1 
B3 + V3 + S3 = 1 
B4 + V4 + S4 = 1 
B5 + V5 + S5 = 1 
B6 + V6 + S6 = 1 
 
Todas as variáveis são binárias. 
 
9. 
 
10. 
 
11.