Exemplos de Modelagem em Pesquisa Operacional

Prévia do material em texto

UNIVERSIDADE FEDERAL DE VIÇOSA
DEPARTAMENTO DE INFORMÁTICA
INF 280 – PESQUISA OPERACIONAL I
Gabarito: Lista de Exercícios para Modelagem
Obs.: todas as variáveis de decisão são  0, a menos que se diga o contrário.
1)
Variáveis de decisão:
xB - Quantidade de cereais barulhentas.
xE - Quantidade de cereais encharcadas.
xP - Quantidade de cereais pipocadas.
xR - Quantidade de cereais repousantes.
Max. Z : pB xB + pE xE + pP xP + pR xR
s.a aBi xB + aEi xE + aPi xP + aRi xR  Mi, i = 1, 2, ..., I.
xB  105.000
xE  130.000
xP  45.000
xR  600.000

2) 
Variáveis de decisão:
A- Quantidade de automóveis produzidos por dia;
C-Quantidade de caminhões produzidos por dia;

Max f: 200A + 300C
s.a C + A 50
 A/60 + C/40  1
3)
Variáveis de decisão:
xij = número de galões enviados da companhia i para o aeroporto j.
Min f : 10x11 + 10x12 + 9x13 + 11x14 +
7x21 + 11x22 + 12x23 + 13x24 +
8x31 + 14x32 + 4x33 + 9x34
s.a. Cia 1) x11 + x12 + x13 + x14  275000
Cia 2) x21 + x22 + x23 + x24  550000
Cia 3) x31 + x32 + x33 + x34  660000
Aer 1) x11 + x21 + x31 = 110000
Aer 2) x12 + x22 + x32 = 220000
Aer 3) x13 + x23 + x33 = 330000
Aer 4) x14 + x24 + x34 = 440000
4)
Variáveis de decisão:
A- Quantidade produzida do modelo A;
B- Quantidade produzida do modelo B;
C- Quantidade produzida do modelo C;
Max f: 16A + 30B + 50C
s.a (3/12)A + (3,5/12 )B + (5/12)C 120
(4/12)A + (5/12)B + (8/12)C 160
(1/12A) + (1,5/12)B + (3/12)C  48
A  20
B  120
C  60

5)
xij = Quantidade do ingrediente i (milho, sal, soja, ração) usada para a fabricação do tipo de
ração j (bovinos, ovelhas, galinhas).
Min f : 0,20x11 + 0,20x12 + 0,20x13 + 0,12x21 + 0,12x22 + 0,12x23 +0,24x31 + 0,24x32 + 0,24x33 +
0,12x41 + 0,12x42 + 0,12x43
s.a. 8x11 + 6x21 + 10x31 + 4x41  60000 (vitaminas / bovinos)
8x12 + 6x22 + 10x32 + 4x42  36000 (vitaminas / ovelhas)
8x13 + 6x23 + 10x33 + 4x43  32000 (vitaminas / galinhas)
8x13 + 6x23 + 10x33 + 4x43  48000
10x11 + 5x21 + 12x31 + 8x41  60000 (proteínas / bovinos)
10x12 + 5x22 + 12x32 + 8x42  36000 (proteínas / ovelhas)
10x13 + 5x23 + 12x33 + 8x43  48000 (proteínas / galinhas)
6x11 + 10x21 + 6x31 + 6x41  70000 (cálcio / bovinos)
6x12 + 10x22 + 6x32 + 6x42  36000 (cálcio / ovelhas)
6x13 + 10x23 + 6x33 + 6x43  48000 (cálcio / galinhas)
8x11 + 6x21 + 6x31 + 9x41  40000 (gordura / bovinos)
8x11 + 6x21 + 6x31 + 9x41  80000
8x12 + 6x22 + 6x32 + 9x42  24000 (gordura / ovelhas)
8x12 + 6x22 + 6x32 + 9x42  36000
8x13 + 6x23 + 6x33 + 9x43  32000 (gordura / galinhas)
8x13 + 6x23 + 6x33 + 9x43  56000
x11 + x12 + x13  6000 (limite milho)
x21 + x22 + x23  10000 (limite sal mineral)
x31 + x32 + x33  4000 (limite soja)
x41 + x42 + x43  5000 (limite ração p/ peixe)
x11 + x21 + x31 + x41 = 10000 (prod. ração bovinos)
x12 + x22 + x32 + x42 = 6000 (prod. ração ovelhas)
x13 + x23 + x33 + x43 = 8000 (prod. ração galinhas)
6)
Variáveis de decisão:
X1 - Quantidade produzida pela máquina 1;
X2 -Quantidade produzida pela máquina 2;
X3 - Quantidade produzida pela máquina 3;
X4 - Quantidade produzida pela máquina 4;
yj – variável binária que indica se a máquina j irá produzir alguma ferramenta (1) ou não (0).
Min Z = 60y1 + 50y2 + 45y3 + 55y4 + 1,12x1 + 1,23x2 + 1,5x3 + 1,2x4
s.a. x1  300
x2  300
x3  300
x4  300
x1 + x2 + x3 + x4  500
x1 – 300.y1  0
x2 – 300.y2  0
x3 – 300.y3  0
x4 – 300.y4  0
yj  {0,1}
7)
Variáveis de decisão:
Xij - Quantidade da cultura i plantada na fazenda j.
Max f: 6000Xa1 + 6000Xa2 + 6000Xa2 + 4500Xb1 + 4500Xb2 + 4500Xb3 + 5500Xc1 + 5500Xc2 +
5500Xc3
s.a. Area 1) Xa1 + Xb1 + Xc1  950
Area 2) Xa2 + Xb2 + Xc2  735
Area 3) Xa3 + Xb3 + Xc3  840
Area A) Xa1 + Xa2 + Xa3  950
Area B) Xb1 + Xb2 + Xb3  800
Area C) Xc1 + Xc2 + Xc3  1200
8)
Variáveis de decisão:
S- Quantidade de sapatos produzidos;
C- Quantidade de cintos produzidos;
Max 5S + 2C
s.a. 2S + C  6 (couro)
S/6 + C/5 1 (tempo)
9)
Variáveis de decisão:
L- Número de caixas de laranjas;
P- Número de caixas de pêssego;
T- Número de caixas de tangerina;
Max f: 20L + 10P + 30T
s.a L + P + T 00
L =200
P 100
T 200
ou, simplificando...
Max f: 4000 + 10P + 30T
s.a P + T 00
P 100
T 200
10)
Variáveis de decisão:
A- Número de vezes de execução do programa A / semana;
B- Número de vezes de execução do programa B / semana;
Max f: 30000 A+ 10000 B
s.a 20A + 10B 80
A + B 5
11)
Variáveis de decisão:
x1 = quantidade de M1/dia
x2 = quantidade de M2/dia
Max Z: 4x1 + 3x2
s.a 2 x1 + x2 1000 ( volume de produção)
x1 + x2 800 (quantidade máx. de couro)
x1 400 (quantidade de fivelas para M1)
x2 700 (quantidade de fivelas para M2)
12)
Variáveis de decisão:
J- Quantidade de jangadas;
S- Quantidade de supercanoas;
A- Quantidade de arcas;
Max f: 50J + 70S + 100A
s.a J + 2S + 3A 18
J + S + A 
J 4
S 8
A 3
13)
Variáveis de decisão:
A- Alqueires de terra para arrendamento;
P- Alqueires de terra para pecuária;
S- Alqueires de terra para plantio de soja;
Max f: 300A + 400P + 500S
s.a 100P + 200S 14000 (adubo)
100P + 200S 12750 (água)
A + P + S 100 (área)
14)
Variáveis de decisão:
S11 – Número de simulações tipo 1, efetuada pela máquina 1;
Sij – Número de simulações tipo i, efetuada pela máquina j;
Min f : 1961x11 + 1295x12 + 481x13 + 814x14 + 1073x15 + 1295x16 + 2072x17 + 1628x18 +
322x21 + 224x22 + 588x23 + 224x24 + 562x25 + 840x26 + 826x27 + 210x28 + 2064x31 +
774x32 + 258x33 + 1720x34 + 645x35 + 2408x36 + 301x37 + 1677x38 + 372x41 + 1798x42 +
3410x43 + 868x44 + 2604x45 + 930x46 + 186x47 + 3100x48.
s.a. M1) 53x11 + 35x12 + 13x13 + 22x14 + 29x15 + 35x16 + 56x17 + 44x18  1800
M2) 23x21 + 16x22 + 42x23 + 16x24 + 4x25 + 60x26 + 59x27 + 15x28  1800
M3) 48x31 + 18x32 + 6x33 + 40x34 + 15x35 + 56x36 + 7x37 + 39x38  1200
M4) 6x41 + 29x42 + 55x43 + 14x44 + 42x45 + 15x46 + 3x47 + 50x48  1200
S1) x11 + x21 + x31 + x41 = 50
S2) x12 + x22 + x32 + x42 = 50
S3) x13 + x23 + x33 + x43 = 50
S4) x14 + x24 + x34 + x44 = 50
S5) x15 + x25 + x35 + x45 = 50
S6) x16 + x26 + x36 + x46 = 50
S7) x17 + x27 + x37 + x47 = 50
S8) x18 + x28 + x38 + x48 = 50
15)
Variáveis de decisão:
A- Horas de trabalho da máquina A;
B- Horas de trabalho da máquina B;
C- Horas de trabalho da máquina C;
Min f: 30A + 50B + 80C
s.a 300A + 600B + 800C 10000
200A + 350B + 600C 6000
16)
Variáveis de decisão:
BR - Quantidade (ton.) produzida da “liga especial de baixa resistência”;
AR - Quantidade (ton.) produzida da “liga especial de alta resistência”;
Max f: 3000BR + 5000AR
s.a. 0,5BR + 0,2AR 16
0,25BR + 0,3AR 11
0,25BR + 0,5AR 15
Modelo no formato do LINDO:
17)
As combinações de corte para esse problema são as seguintes:
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 Demanda
55 cm 3 2 2 1 1 1 0 0 0 0 110
50 cm 0 1 0 2 1 0 3 2 1 0 120
30 cm 0 0 2 0 2 3 0 2 4 5 80
Perda: 5 10 0 15 5 25 20 10 0 20
LP OPTIMUM FOUND AT STEP 2
OBJECTIVE FUNCTION VALUE
1) 160000.0
VARIABLE VALUE REDUCED COST
BR 20.000000 0.000000
AR 20.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 2.000000 0.000000
3) 0.000000 5000.000000
4) 0.000000 7000.000000
NO. ITERATIONS= 2
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
BR 3000.000000 1166.666626 500.000000
AR 5000.000000 1000.000000 1400.000000
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2 16.000000 INFINITY 2.000000
3 11.000000 0.500000 2.0000004 15.000000 3.333333 1.000000
max 3000BR + 5000AR
st
0.5BR +0.2AR <= 16
0.25BR + 0.3AR <= 11
0.25BR + 0.5AR <= 15
Min f : x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10
s.a 3x1 + 2x2 +2x3 + x4 + x5 + x6 110
x2 + 2x4 + x5 + 3x7 + 2x8 + x9 
 2x3 + 2x5 +3x6 + x7 + 2x8 + 4x9 + 5x10 

Com isso, temos o seguinte modelo no formato do LINDO:
LP OPTIMUM FOUND AT STEP 6
OBJECTIVE VALUE = 90.0000000
FIX ALL VARS.( 7) WITH RC > 0.000000E+00
NEW INTEGER SOLUTION OF 90.0000000 AT BRANCH 0 PIVOT 6
BOUND ON OPTIMUM: 90.00000
ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 6
LAST INTEGER SOLUTION IS THE BEST FOUND
RE-INSTALLING BEST SOLUTION...
OBJECTIVE FUNCTION VALUE
1) 90.00000
VARIABLE VALUE REDUCED COST
X1 0.000000 1.000000
X2 55.000000 1.000000
X3 0.000000 1.000000
X4 0.000000 1.000000
X5 0.000000 1.000000
X6 0.000000 1.000000
X7 0.000000 1.000000
X8 30.000000 1.000000
X9 5.000000 1.000000
X10 0.000000 1.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 0.000000 0.000000
3) 0.000000 0.000000
4) 0.000000 0.000000
NO. ITERATIONS= 6
BRANCHES= 0 DETERM.= 1.000E 0
min x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10
st
3x1 + 2x2 + 2x3 + x4 + x5 + x6 >= 110
x2 + 2x4 + x5 + 3x7 + 2x8 + x9 >= 120
2x3 + 2x5 + 3x6 + 2x8 + 4x9 + 5x10 >= 80
end
gin 10
18)
Variáveis de decisão:
L- Quantidade de leite;
C- Quantidade de carne;
P- Quantidade de peixe;
S- Quantidade de salada;
Min f: 2L + 4C + 1,5P + S
s.a 112L + 2C + 10P + 20S 20
50L + 20C + 10P + 30S 70
250  80L + 70C + 10P + 80S 350
Modelo no formato do LINDO:
min 2L + 4C + 1.5P + S
st
2L + 2C + 10P + 20S <= 20
2L + 2C + 10P + 20S >= 11
50L + 20C + 10P + 30S >= 70
80L + 70C + 10P + 80S <= 350
80L + 70C + 10P + 80S >= 250
LP OPTIMUM FOUND AT STEP 3
OBJECTIVE FUNCTION VALUE
1) 11.69355
VARIABLE VALUE REDUCED COST
L 0.000000 495.370972
C 2.741935 0.000000
P 0.000000 2.887097
S 0.725806 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 0.000000 0.201613
3) 9.000000 0.000000
4) 6.612903 0.000000
5) 100.000000 0.000000
6) 0.000000 -0.062903
7) 0.000000 0.000000
8) 2.741935 0.000000
9) 0.000000 0.000000
10) 0.725806 0.000000
NO. ITERATIONS= 3
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
L 500.000000 INFINITY 495.370972
C 4.000000 426.569458 3.125000
P 1.500000 INFINITY 2.887097
S 1.000000 3.571429 30712.998047
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2 20.000000 42.500000 9.000000
3 11.000000 9.000000 INFINITY
4 70.000000 6.612903 INFINITY
5 350.000000 INFINITY 100.000000
6 250.000000 100.000000 24.117645
7 0.000000 0.000000 INFINITY
8 0.000000 2.741935 INFINITY
9 0.000000 0.000000 INFINITY
10 0.000000 0.725806 INFINITY
19)
Variáveis de decisão:
XAi - Quantidade do tipo de petróleo j usado na fabricação da gasolina amarela;
XZj - Quantidade do tipo de petróleo j usado na fabricação da gasolina azul;
XSj - Quantidade do tipo de petróleo j usado na fabricação da gasolina superazul;
Max f: 22 (XA1 + XA2 + XA3 + XA4) + 28 (XZ1 + XZ2 + XZ3 + XZ4) + + 35 (XS1 + XS2 + XS3 + XS4) -
19 (XA1 + XZ1 + XS1) - 24 (XA2 + XZ2 + XS2) - 20 (XA3 + XZ3 + XS3) - 27 (XA4 + XZ4 + XS4)
! max 22 (XA1 + XA2 + XA3 + XA4)
! + 28 (XZ1 + XZ2 + XZ3 + XZ4)
! + 35 (XS1 + XS2 + XS3 + XS4)
! - 19 (XA1 + XZ1 + XS1)
! - 24 (XA2 + XZ2 + XS2)
! - 20 (XA3 + XZ3 + XS3)
! - 27 (XA4 + XZ4 + XS4)
max 3XA1 - 2XA2 + 2XA3 - 5XA4 + 9XZ1 + 4XZ2 +
8XZ3 + XZ4 + 16XS1 + 11XS2 + 15XS3 + 8XS4
st
Tipo 1) XA1 + XZ1 + XS1 <= 3500
Tipo 2) XA2 + XZ2 + XS2 <= 2200
Tipo 3) XA3 + XZ3 + XS3 <= 4200
Tipo 4) XA4 + XZ4 + XS4 <= 1800
! Super Azul:
! XS1 <= 0.3 * (XS1 + XS2 + XS3 + XS4)
! XS2 >= 0.4 * (XS1 + XS2 + XS3 + XS4)
! XS3 <= 0.5 * (XS1 + XS2 + XS3 + XS4)
Super 1) 0.7XS1 - 0.3XS2 - 0.3XS3 - 0.3XS4 <= 0
Super 2) 0.6XS2 - 0.4XS1 - 0.4XS3 - 0.4XS4 >= 0
Super 3) 0.5XS3 - 0.5XS1 - 0.3XS2 - 0.3XS4 <= 0
! Azul:
! XZ1 <= 0.3 * (XZ1 + XZ2 + XZ3 + XZ4)
! XZ1 >= 0.1 * (XZ1 + XZ2 + XZ3 + XZ4)
Azul 1a) 0.7XZ1 - 0.3XZ2 - 0.3XZ3 - 0.3XZ4 <= 0
Azul 1b) 0.9XZ1 - 0.1XZ2 - 0.1XZ3 - 0.1XZ4 >= 0
! Amarela:
! XA1 <= 0.7 * (XA1 + XA2 + XA3 + XA4)
Amarela) 0.3XA1 - 0.7XA2 - 0.7XA3 - 0.7XA4 <= 0
end
20)
Variáveis de decisão:
X1 = Quantidade de recursos investida no programa institucional (em R$mil).
X2 = Quantidade de recursos investida diretamente na divulgação do produto P1 (em R$mil).
X3 = Quantidade de recursos investida diretamente na divulgação do produto P2 (em R$mil).
Min Z : X1 + X2 + X3
s.a X1 + X2 + X3  10
3X1 + 4X2 = 30
3X1 + 10X3 = 30
Podemos notar, no entanto, que o modelo acima não restringe o valor mínimo aplicado no
programa institucional (R$3 mil). Para fazer isso, podemos usar uma variável de decisão
binária Y1, da seguinte maneira:
Y1 = 1 se o programa institucional for usado.
Y1 = 0 caso contrário.
E acrescentar as seguintes restrições:
X1  10Y1
X1 3Y1
A primeira delas obriga o valor de Y1 = 1 caso o valor de X1 seja maior que zero (assumindo
um valor de aplicação máximo de R$10 mil), ou seja:
X1 > 0  Y1 = 1
A segunda pode ser entendida assim:
Y1 = 1  X1 > 3
21)
Variáveis de decisão:
P1- Quantidade do produto P1:
P2- Quantidade do produto P2:
Max f: 100 P1 + 150 P2
s.a 2 P1 + 3 P2 120
P1 40
P2 30
22)
Variáveis de decisão:
xij = número de caminhões transportados do porto i para a loja j.
Min f: 30x11 + 20x12 + 24x13 + 28x14 + 12x21 + 36x22 + 30x23 + 24x24 + 8x31 + 15x32 + 25x33 +
20x34
s.a. Loja 1) x11 + x21 + x31 = 5
Loja 2) x12 + x22 + x32 = 8
Loja 3) x13 + x23 + x33 = 4
Loja 4) x14 + x24 + x34 = 10
23)
Variáveis de decisão :
B - Quantidade de madeira beneficiada (em m³);
C - Quantidade de compensado (em unidades de 100m²);
Max f : 45B + 60C
s.a B + 2C 32
4B + 4C 72
B 5
C 12
24)
Variáveis de decisão:
x1 = qtd. de batata (em ton.) adquirida da Fonte 1.
x2 = qtd. de batata (em ton.) adquirida da Fonte 2.
Max. 5x1 + 6x2
s.a.
Batatas Fritas) 0,2x1 + 0,3x2  1,8
Batatas Picadas) 0,2x1 + 0,1x2  1,2
Flocos para purê) 0,3x1 + 0,3x2  2,4
25)
Variáveis de decisão:
x1 = qtd. de álcool anidro produzida diariamente (em ton.).
x2 = qtd. de álcool hidratado produzida diariamente (em ton.).
Max. 40x1 + 30x2
s.a. I) 0,5x1  8
II) x2  8
III) 1/3 x1 + 2/3 x2  8
Solução ótima: x* = (16; 4), Z* = 760. Ou: produzir 16 toneladas de álcool anidro e 4 toneladas
de álcool hidratado, diariamente, obtendo um lucro máximo de $760.
26)
Variáveis de decisão:
x1 = qtd. de Agrião (em porções de 100g) na dieta.
x2 = qtd. de Broto de Feijão (em porções de 100g) na dieta.
Min. 0,1x1 + 0,1x2
s.a. Ca) 169x1 + 52x2  1000
P) 41x1 + 58x2  900
Fe) 2,6x1 + 1,1x2  12
Na–) 33,2x1 + 131x2  1000
Na+) 33,2x1 + 131x2  2300
K) 180,4x1 + 35x2  2000
x1* = 9,34 x2* = 8,9 Z* = 1,83
27)
Variáveis de decisão:P1- Quantidade de unidades do processo 1;
P2- Quantidade de unidades do processo 2;
Max f: p1 P1 + p2P2
s.a.
P1 + 4P2 120
3P1 + 2P2  180
50P1 + 30P2 2800
20P1 + 80P2 2200
x* = (48; 18)
28)
Variáveis de decisão:
F1- Dias de funcionamento da fábrica 1;
F2- Dias de funcionamento da fábrica 2;
Min f: 1000F1 + 2000F2
s.a 8F1 + 2F2 16
F1 + F2 6
2F1 + 7F2 28
F1, F2 0.
x* = (2.8; 3.2) z* = 9200
29)
Variáveis de decisão:
X1 = qtd. (em kg) de carne de boi num hamburger de 1 kg;
x2 = qtd. (em kg) de carne de porco no hamburger de 1 kg;
Temos:
Min f: 5x1 + 3.5x2
s.a. x1 + x2 = 1
0.2x1 + 0.32x2  0.25
x1* = 0.58 x2* = 0.42 z* = 4.37
30)
Variáveis de decisão:
x1 = qtd. de chapéus na caixa;
x2 = qtd. de línguas de sogra na caixa;
x3 = qtd. de bexigas na caixa;
Temos:
Min f: 0.05x1 + 0.02x2 + 0.05x3
s.a.
x3 >= 20
0.5x1 + 0.5x2 - 0.5x3 0
0.75x1 - 0.25x2 - 0.25x3  0
-0.25x1 + 0.75x2 - 0.25x3  0
-0.25x1 - 0.25x2 + 0.75x3  0
Solução ótima:
z* = 1.7 x* = (10; 10; 20)
Solução Alternativa
Se interpretarmos a restrição “Cada item deve concorrer com pelo menos 25% do total da
caixa” como referência ao custo ao invés da quantidade, teremos:
Min f : 0.05x1 + 0.02x2 + 0.05x3
s.a.
x3  20
0.05x1  0.25 (0.05x1 + 0.02x2 + 0.05x3)
0.02x2  0.25 (0.05x1 + 0.02x2 + 0.05x3)
0.05x2  0.25 (0.05x1 + 0.02x2 + 0.05x3)
Ou seja:
Min f : 0.05x1 + 0.02x2 + 0.05x3
s.a.
x3  20
0.0375x1 - 0.005x2 - 0.0125x3  0
-0.0125x1 + 0.015x2 - 0.0125x3  0
-0.0125x1 - 0.005x2 + 0.0375x3  0
e a solução ótima, nesse caso, será:
z* = 2.0 x* = (10; 25; 20)