Modelagem em Pesquisa Operacional

Prévia do material em texto

Capítulo 1 
 
 
 
Modelagem em Pesquisa Operacional 
 
 
 
 Neste capítulo estudaremos o processo de modelagem em Pesquisa 
Operacional (PO). O objetivo aqui, não é o de obter soluções de problemas de PO, mas sim o 
de modelar problemas, em contraposição ao uso apenas da experiência e do bom senso. 
 Como referências básicas sugerimos (HILLIER e LIEBERMAN, 1995) e 
(GOLDBARG e LUNA, 2005). 
 A influência da Segunda Guerra Mundial foi decisiva para o ressurgimento 
da PO, e os desenvolvimentos que se seguiram nas décadas que sucederam ao grande conflito 
são devidos especialmente à difusão do computador nas universidades e empresas. Havia 
demandas da parte da indústria e dos governos (transportar, planejar e interceptar, etc.), novos 
conhecimentos em Matemática, Engenharia, Estatística, Economia e Computação eram 
publicados, e financiamentos de pesquisa nesta área de conhecimento surgiram. O projeto 
Scientific Computation of Optimum Programs é um exemplo de relevante financiamento 
ocorrido na ocasião, que resultou num grupo formado para pesquisar a viabilidade em aplicar 
a Matemática e técnicas correlacionadas à análise de problemas de planejamento e 
programação militar. 
 
1.1 O processo de modelagem 
 
 Os responsáveis pela tomada de decisões nos mais variados campos da 
atividade humana defrontam-se com a necessidade de resolver algum problema específico de 
PO. A compreensão e a definição do problema são de fundamental importância para o 
processo de modelagem. 
 O primeiro passo para a resolução de um problema de PO é a formulação, 
que consiste em traduzir a realidade empírica para sentenças lógicas e dados objetivos, 
permitindo a partir daí o estabelecimento de um modelo matemático. É onde devemos decidir 
(julgamento humano) que aspectos do sistema real devemos incorporar ao modelo, assim 
como quais podem ser ignorados, que suposições podem ser feitas e quais podem ser 
 2
descartadas. A tradução está sujeita a erros e falhas de comunicação. Também, não existem 
técnicas precisas capazes de permitir o estabelecimento do modelo de um problema. 
 O segundo passo é a dedução do modelo, isto é, analisá-lo e resolvê-lo 
através de algoritmos específicos. Sua solução, atenta aos métodos numéricos em 
Computação, sugere uma tomada de decisão. Para a sua sustentação, recorremos ao terceiro 
passo que é a interpretação de uma solução do modelo para uma solução do sistema real. Se o 
modelo não for validado, ele deve ser reformulado, e assim por diante. Este é o processo de 
modelagem. Para maiores detalhes sobre o processo de modelagem, recomendamos 
(RAVINDRAN, PHILLIPS e SOLBERG, 1987). 
 A seguir, estudaremos o primeiro passo do processo, ou seja, a formulação 
em Programação Matemática e exemplos de modelos probabilísticos, sem nos preocuparmos 
com a solução e a validação. 
 
1.2 Formulação de alguns problemas 
 
 Trataremos a seguir três problemas de PO nesta seção, um da área agrícola, 
outro de administração, um de eletricidade, além de alguns processos estocásticos. Em cada 
seção, enunciaremos o problema de PO e seu modelo correspondente. Finalmente com relação 
aos modelos probabilísticos, apenas enunciaremos alguns problemas. 
 
1.2.1 Um problema agrícola 
 
 Este problema foi extraído de (MÜLLER 2004), e trata da elaboração de um 
modelo de Programação Linear para planejamento de produção agrícola. 
 
1.2.1.1 O problema 
 
 Consideremos um problema na agricultura para decidir quais e em que 
quantidade os alimentos soja, milho, arroz e feijão devem ser plantados em uma determinada 
área de forma a maximizar o lucro líquido do produtor rural. A Tabela 1.1 resume os dados do 
problema. 
 
 
 3
Tabela 1.1 – Dados gerais do problema. 
 Produção esperada 
(sacas/hectare) 
Renda líquida esperada 
(reais/hectare) 
Gleba Tamanho 
(hectare) 
Soja Milho Arroz Feijão Soja Milho Arroz Feijão 
1 10 50 130 30 40 1.200 1.040 240 1.450 
2 18 48 120 32 55 1.080 910 300 3.380 
3 22 48 140 30 43 1.065 1.728 300 1.890 
4 49 50 100 28 38 1.320 700 280 1.220 
5 51 35 70 36 32 365 -120 600 610 
6 54 32 65 37 30 160 -380 595 280 
7 77 35 68 37 32 360 -171 620 585 
8 69 38 95 39 36 610 410 665 900 
Mínimo 
(sacas ou 
hectares) 
2.500 
(sacas) 
3.000 
(sacas) 
150 
(hectares) 
 
Máximo 
(hectares) 
 80 
(hectares) 
 
 
 Em relação aos dados da Tabela 1.1, apenas a título de informação, um 
hectare corresponde a uma área plana equivalente a um quadrado de 100 metros de lado, ou 
seja, 10.000 m2, enquanto uma saca em geral pesa 50 kg. Pelas restrições impostas pelo 
proprietário da fazenda precisa-se colher no mínimo 2.500 sacas de soja, pois são para 
produzir semente encomendada; no mínimo 3.000 sacas de milho, pois será utilizada para 
pagar empréstimo feito em milho à cooperativa local; pretende-se plantar, no mínimo, 150 
hectares de arroz plantados, pois é terra de primeiro ano (terra fraca) e, no máximo, 80 
hectares de terra para plantio de feijão, pois se corre risco de perda e prefere-se, neste ano, 
não arriscar muito. 
 Ainda na Tabela 1.1, “Produção esperada” diz respeito ao que se espera de 
cada gleba (porção de terra) para o cultivo de cada um dos alimentos. A “Renda líquida 
esperada” é a diferença entre o custo de produção e renda bruta esperada. As duas últimas 
linhas formam o conjunto de restrições imposto pelo proprietário da fazenda, que diz respeito 
ao mínimo ou máximo de sacas que se deseja colher de um certo tipo de alimento, ou o 
mínimo ou máximo de terra (em hectare) que se deseja plantar. 
 
1.2.1.2 Um modelo 
 
 Como já afirmamos, não existem regras precisas para o processo de 
modelagem, por isto sugerimos uma tentativa de encontrar inicialmente as variáveis de 
 4
decisão. Também sugerimos verificar as unidades de grandeza de cada dado, inclusive das 
variáveis de decisão. 
 Neste caso, definimos 8,,2,1, �=ixij e 4,3,2,1=j , as variáveis de 
decisão que pretendemos encontrar, se existirem, a saber: 
 
ijx : área em hectares por gleba i , para o plantio do alimento j 
 ( 1=j , soja, 2=j , milho, 3=j , arroz, e 4=j , feijão). 
 
Como estamos interessados em maximizar a renda da fazenda, utilizamos os dados da “Renda 
líquida esperada (reais/hectare)” da Tabela 1.1 para construir o valor da chamada função 
objetivo do problema, a saber: 
.900665410610
585620171360
280595380160
610600120365
12202807001320
189030017281065
33803009101080
145024010401200
84838281
74737271
64636261
54535251
44434241
34333231
24232221
14131211
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
++++
+++−+
+++−+
+++−+
+++++
+++++
+++++
++++
 
 
 Nosso objetivo de maximização está sujeito a algumas restrições. Sabemos 
que a soma das áreas para o plantio dos quatro alimentos em cada gleba não pode ultrapassar 
o tamanho total da gleba. Temos então: 
 
.69
77
54
51
49
22
18
10
84838281
74737271
64636261
54535251
44434241
34333231
24232221
14131211
≤+++
≤+++
≤+++
≤+++
≤+++
≤+++
≤+++
≤+++
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
 
 
 Ainda, não pode haver área negativa para plantio de cada alimento. Para isso 
temos, 
8,,2,1,0 �=≥ ixij e 4,3,2,1=j . 
 5
 Finalmente, consideramos as restrições impostas pelo proprietário da 
fazenda conforme a Tabela 1.1, que se referem aos requisitos de produção dos cereais para 
atendimento de encomenda, pagamento de empréstimo e condições de qualidade do solo e 
risco de perdas em relação ao feijão. Assim, obtemos as seguintes desigualdades: 
 
25003835323550484850 8171615141312111 ≥+++++++ xxxxxxxx 
300095686570100190120130 8272625242322212 ≥+++++++ xxxxxxxx 
.80
150
84746454443424148373635343332313
≤+++++++
≥+++++++
xxxxxxxx
xxxxxxxx
 
 
 Portanto, o nosso modelo matemático, que tenta traduzir uma particular 
realidade da agricultura, é dado pelo problema de PO 
 
maximizar 
84838281
74737271
64636261
54535251
44434241
34333231
24232221
14131211
900665410610
585620171360
280595380160
610600120365
12202807001320
189030017281065
33803009101080
145024010401200
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
++++
+++−+
+++−+
+++−+
+++++
+++++
+++++
++++
 
 
sujeito a: 
69
77
54
51
49
22
18
10
84838281
74737271
64636261
54535251
44434241
34333231
24232221
14131211
≤+++
≤+++
≤+++
≤+++
≤+++
≤+++
≤+++
≤+++
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
 
 
25003835323550484850 8171615141312111 ≥+++++++ xxxxxxxx 
300095686570100190120130 8272625242322212 ≥+++++++ xxxxxxxx 
80
150
8474645444342414
8373635343332313
≤+++++++
≥+++++++
xxxxxxxx
xxxxxxxx
 
 6
8,,2,1,0 �=≥ ixij e 4,3,2,1=j . 
 A formulação discutida nesta seção refere-se a um modelo com funções 
afins (isto é, lineares). Desta forma, denominamos este problema agrícola de um problema de 
Programação Linear (contínua), que estudaremos no Capítulo 3. 
 
1.2.2 Um problema de designação 
 
 Com base em (FANG e PUTHENPURA, 1993), extraímos o seguinte 
problema de Programação Linear Inteira. 
 
1.2.2.1 O problema 
 
 Cinco pessoas (A, B, C, D, E) estão designadas para trabalhar em cinco 
projetos diferentes (1, 2, 3, 4, 5). A Tabela 1.2 mostra quanto tempo (em dias) uma 
determinada pessoa consegue finalizar um específico projeto. 
 
Tabela 1.2 – Dados gerais do problema. 
Projetos Pessoas 
1 2 3 4 5 
A 5 5 7 4 8 
B 6 5 8 3 7 
C 6 8 9 5 10 
D 7 6 6 3 6 
E 6 7 10 6 11 
 
 O pagamento diário (em uma jornada de quatro horas) por pessoa é 60 reais. 
Suponha que uma pessoa é designada para realizar um único projeto e cada projeto só pode 
ser realizado por uma única pessoa. 
 
1.2.2.2 Um modelo 
 
 Neste caso definimos ijx , 5,,2,1 �=i ( 1=i , pessoa A e assim por 
diante) e 5,,2,1 �=j , os projetos pelas quais podem ser designadas responsáveis. A variável 
ijx pode ser definida como: 
 7
=ijx
�
�
�
contráriocaso,0
 projeto o para designadafor pessoaase,1 ji
 
 Nosso interesse agora é o de minimizar o custo para a execução dos 
projetos. Assim, utilizamos os dados da Tabela 1.2, para construir o valor da função objetivo, 
a saber: 
 
).1161076
63667
105986
73856
84755(60
5554535251
4544434241
3534333231
2524232221
1514131211
xxxxx
xxxxx
xxxxx
xxxxx
xxxxx
+++++
++++++
++++++
++++++
+++++
 
 
 Nosso objetivo de minimização está sujeito a algumas restrições. Sabemos 
que cada pessoa é designada para realizar um único projeto, isto é, 
1
5
1
=�
=j
ijx , 5,,2,1 �=i , 
e que cada projeto só pode ser realizado por uma única pessoa, isto é, 
1
5
1
=�
=i
ijx , 5,,2,1 �=j . 
Portanto, o nosso modelo matemático que tenta traduzir uma particular realidade do problema 
clássico de designação (assignment problem, em inglês), é dado pelo problema de PO, 
 
minimizar 
)1161076
63667
105986
73856
84755(60
5554535251
4544434241
3534333231
2524232221
1514131211
xxxxx
xxxxx
xxxxx
xxxxx
xxxxx
+++++
++++++
++++++
++++++
+++++
 
 
sujeito a: 
1
5
1
=�
=j
ijx , 5,,2,1 �=i 
 
1
5
1
=�
=i
ijx , 5,,2,1 �=j 
 { }1,0∈ijx , 5,,2,1 �=i e 5,,2,1 �=j . 
 
 8
 A formulação discutida nesta seção refere-se a um modelo com funções 
lineares tais que as variáveis de decisão são inteiras. Desta forma, denominamos este 
problema de designação de um problema de Programação Linear Inteira (discreto), assunto 
que não será objeto de estudo neste livro. Todavia, para os leitores interessados em 
aprofundar seus conhecimentos nesta área sugerimos os livros de (FOULDS, 1984) e 
(GARFINKEL e NEMHAUSER, 1972). 
 
1.2.3 Um problema de amplificador de tensão 
 
 A seguir apresentamos um problema de otimização que envolve um circuito 
elétrico. 
 
1.2.3.1 O problema 
 
 Em Engenharia Elétrica é comum a utilização de circuitos amplificadores 
em aparelhos de áudio e vídeo. Esses circuitos recebem em sua entrada uma tensão elétrica e 
aumentam sua amplitude disponibilizando na saída um sinal elétrico amplificado. 
 O circuito da Figura 1.1 mostra de maneira simplificada um amplificador 
onde os estágios de entrada e saída são representados, respectivamente, por uma fonte de 
tensão, v , e por uma resistência de carga, cR , igual a Ω10 ( AV=Ω ). Este circuito, para 
certos valores do parâmetro α , comporta-se como um amplificador de tensão. Devem ainda 
ser respeitados os limites inferior e superior de V12 e V30 , respectivamente, para a tensão 
na resistência de carga, cc iv 10= . 
 
 
 
 
 
 
 
 
 
entrada saída 
Figura 1.1 – Circuito básico para amplificação da tensão v . 
i 
ci 
−
+
cv 
ΩM7,0 
cR v 
−
+
abv 
Ω5 
ci 
+
 
ΩM1 abvα 
a
 
b 
 9
 A tensão v da fonte está restrita aos limites inferior e superior, 
respectivamente, de mV340 e mV500 . O parâmetro α deve ser no mínimo igual a 120 . 
 
1.2.3.2 Um modelo 
 
 Neste caso, definimos as variáveis de decisão que se pretende encontrar, se 
existirem, a saber: 
 
i : corrente elétrica em ampères (A) suprida pela fonte; 
ci : corrente elétrica em ampères (A) no lado da carga; 
v : tensão elétrica da fonte em volts (V); 
α : parâmetro de controle da fonte dependente, que é adimensional. 
 
 Nosso interesse está em operar o circuito da Figura 1.1 minimizando a perda 
de energia elétrica em watts ( VAW = ) nos resistores de resistências ΩM7,0 , ΩM1 e Ω5 , 
a saber: 
 
226 5107,1 cii +× . 
 
 Na expressão da perda de energia elétrica não incluímos a resistência cR 
porque esta representa a carga do circuito. 
 Nosso objetivo de minimização está sujeito a algumas restrições. De acordo 
com a 2ª Lei de Kirchhoff, que estabelece que a tensão aplicada a qualquer percurso fechado 
de um circuito é igual ao somatório das quedas de tensão naquele percurso, temos: 
 
abviv +×=
6107,0 , 
 
onde, abv é a queda de tensão no resistor de ΩM1 . 
 Procedemos de modo análogo para analisar o percurso fechado onde se 
encontra a resistência de carga e obtemos: 
 
cab viv += 5α . 
 
 
 10 
 Substituindo cc iv 10= na última igualdade e desenvolvendo, obtemos 
 
0105 =−− cab iivα . 
 
 Além disso, foi dado que: 
 
301012 ≤=≤ cc iv . 
 
 Dividindo cada dupla desigualdade por dez, obtemos: 
 
32,1 ≤≤ ci . 
 
 Portanto, o nosso modelo matemático que tenta traduzir uma particular 
realidade do problema de minimização das perdas em um circuito amplificador de tensão, é 
dado pelo problema de PO 
 
minimizar 226 5107,1 cii +× 
sujeito a: 0107,0 6 =−×− abviv 
 0105 =−− cab iivα 
 32,1 ≤≤ ci 
 50,034,0 ≤≤ v 
 120≥α . 
 
 A formulação discutida nesta seção refere-se a um modelo com pelo 
menos uma função não linear. Desta forma, denominamos este problema de amplificador de 
tensão de um problema de Programação Não Linear. Neste livro não estudaremos 
Programação Não Linear. Todavia, sugerimos as referências (BAZARAA, SHERALI e 
SHETTY, 1993) e (LUENBERGER, 1984). 
 
1.2.4 Formulação em processos estocásticos 
 
 Processos estocásticos (ou modelos probabilísticos) são modelos 
matemáticos desenvolvidos para analisar sistemas dinâmicos sujeitos a incerteza, usando a 
linguagem da probabilidade. O termo “dinâmico” significa que a variável tempo t geralmente 
está envolvidano processo de formulação. 
 11 
 A principal característica de um problema estocástico é que, associado a 
pelo menos uma de suas variáveis, temos um número que mede o grau de incerteza (ou de 
certeza) da ocorrência do valor da variável, dado pela probabilidade. 
 A formulação em processos estocásticos normalmente compreende a 
elaboração de sentenças lógicas, a interpretação de dados estatísticos sobre o problema e a 
identificação da distribuição de probabilidade que governa as variáveis. Depois de construído 
o modelo, este pode admitir soluções analíticas. Em casos de problemas complexos, a 
simulação computacional é a melhor alternativa. 
 Estudaremos a teoria de probabilidades e distribuições no Capítulo 4. 
Assim, substituiremos o passo da formulação pelo enunciado de alguns problemas para 
processos de Markov (Capítulo 5), teoria de filas (Capítulo 6) e simulação (Capítulo 7). 
 
 
1.2.4.1 Cadeias de Markov 
 
 Muitos processos que ocorrem em sistemas reais podem ser estudados como 
se o sistema sob análise passasse, a partir de um estado inicial, por uma seqüência de estados, 
onde a transição de um determinado estado para o seguinte ocorreria segundo uma certa 
probabilidade. No caso em que esta probabilidade de transição depende apenas do estado em 
que o fenômeno se encontra e do estado a seguir, o processo será designado processo de 
Markov de primeira ordem e uma seqüência de estados seguindo este processo será 
denominada cadeia de Markov. 
 Um conceito fundamental em processos de Markov é a noção de estado. 
Propriedades em comum entre indivíduos ou objetos caracterizam o que chamamos de 
estados. Podemos apontar associações entre propriedade em comum e estado: uma população 
da região norte que migra para o sul; veículos estacionados numa determinada área; e 
máquinas numa grande linha de produção. 
 
a) Exemplo 
 
 Em 1993, a utilização do solo em uma cidade de 130 2km de área ocupada 
apresentava os seguintes índices: 
 
 12 
(I) Uso residencial: 30% 
(II) Uso comercial: 20% 
(III) Uso industrial: 50% 
 
O problema é encontrar os estados de utilização do solo em 1998, 2003 e 2008, assumindo 
que as probabilidades de transição para intervalos de 5 anos são dadas pela seguinte matriz 
P : 
III
II
I
P
IIIIII
�
�
�
�
�
�
�
�
	
=
9,01,00
2,07,01,0
1,01,08,0
 
 
1.2.4.2 Teoria de filas 
 
 Um processo de filas consiste em chegadas de usuários em um 
estabelecimento de prestação de serviços, esperando alinhados (em fila). O usuário que chega 
ao estabelecimento aguarda se todos os atendentes estiverem ocupados, e é prontamente 
atendido em caso contrário. Após receber o serviço, o usuário deixa o estabelecimento. 
 
a) Exemplo 
 
 Uma casa de doces finos é operada por uma pessoa, o proprietário. O 
modelo de chegada de clientes nos sábados segue aproximadamente uma distribuição de 
Poisson, com uma taxa média de chegada de 10 pessoas por hora. Os clientes são atendidos 
em base FIFO (primeiro a entrar, primeiro a sair) e por causa do sucesso da loja eles têm que 
esperar para serem atendidos após chegarem. O tempo gasto para atender a um cliente é 
estimado como exponencialmente distribuído, com um tempo médio de atendimento de 4 
minutos. O problema é determinar a probabilidade de se formar uma fila; o tamanho médio da 
fila; o tempo esperado que um cliente deve aguardar na fila; o tempo médio que um cliente 
deve ficar na loja. 
 
1.2.4.3 Simulação 
 
 Simulação significa reproduzir o funcionamento de um sistema com o 
auxílio de um modelo. 
 13 
 Toda simulação requer a construção de um modelo com o qual são feitos 
experimentos. Em nosso caso, este modelo é definido por um conjunto de relações lógico-
matemáticas, descritas geralmente por um programa de computador. A partir do modelo, as 
simulações nos permitirão testar algumas hipóteses sobre o valor de variáveis controladas. As 
conclusões são usadas então para melhorar o desempenho do sistema em estudo, 
proporcionando suporte bem fundamentado à tomada de decisões. 
 A simulação computacional surgiu a partir da idéia do método Monte Carlo, 
durante uma conferência em Los Alamos, nos Estados Unidos, após a Segunda Guerra 
Mundial. Naquela ocasião, após serem apresentadas as experiências adquiridas com o ENIAC 
(Electronic Numeric Integrator and Calculator), Stanislaw Ulam pressentiu a potencialidade 
da nova máquina para técnicas de amostragem estocástica. John Von Neumann, pioneiro da 
Computação, também presente na conferência, foi um dos precursores desse método. Monte 
Carlo baseia-se essencialmente na geração intensiva de números aleatórios para a solução por 
simulação computacional de problemas estocásticos. 
 Um número aleatório é um número de uma seqüência de números cuja 
probabilidade de ocorrência é a mesma que a de qualquer outro número na seqüência. 
Métodos de simulação de problemas probabilísticos (não determinísticos) exigem a geração 
de números aleatórios. 
 
a) Exemplo 
 Uma empresa deseja saber qual é o nível ideal de estoque para seus 
produtos. Um problema é manter o atendimento dentro dos padrões previamente estabelecidos 
com a maior economia possível no gerenciamento e na manutenção dos estoques. As 
variáveis são: a demanda aleatória em um período de tempo; o tempo de atendimento de 
pedido de reposição; e os estoques inicial e final no período. 
 
1.3 Exercícios 
 
1. (BOLDRINI, COSTA, FIGUEIREDO e WETZLER, 1986) A Cia. Sovina de Investimentos 
possui seis milhões de reais, quantia esta que deverá ser aplicada em cinco tipos de 
investimentos, sendo que os retornos anuais para cada investimento são: investimento 1 ( 1I ), 
10%; investimento 2 ( 2I ), 8%; investimento 3 ( 3I ), 6%; investimento 4 ( 4I ), 5%; e 
investimento 5 ( 5I ), 9%. 
 14 
 O gerente desta Cia. deseja diversificar os investimentos para obter o 
máximo de rendimento possível. Dado o elemento de risco envolvido, o gerente restringiu a 
quantia a ser aplicada em 1I a não mais que a quantia total aplicada em 3I , 4I e 5I (em 
conjunto). A soma da quantia total a ser aplicada em 2I e 5I deve ser pelo menos igual à 
quantia aplicada em 3I . O 2I deve estar limitado a um nível que não exceda a quantia 
aplicada em 4I . 
 É preciso determinar a alocação ótima de investimento entre as cinco 
categorias, de forma que o retorno ao final do ano seja o máximo possível. Formular o 
problema. 
 
2. (BOLDRINI, COSTA, FIGUEIREDO e WETZLER, 1986) Uma empresa nacional possui 
fábricas em Campinas e Belo Horizonte (BH). Esta empresa produz e distribui computadores 
a comerciantes de várias cidades. Numa determinada semana, a empresa possui: 30 unidades 
em Campinas e 40 unidades em BH. Nesta mesma semana, esta empresa deve atender os 
pedidos dos comerciantes das seguintes cidades: 20 unidades para São Paulo (SP), 25 
unidades para o Rio de Janeiro (RJ) e 25 unidades para Vitória. O problema consiste em 
distribuir as máquinas aos comerciantes de forma a atender os pedidos a um custo mínimo de 
transporte. Os custos unitários de transporte em reais são: 9 de Campinas para SP, 16 de 
Campinas para RJ, 25 de Campinas para Vitória, 27,50 de BH para SP, 22,50 de BH para RJ e 
21 de BH para Vitória. Formular o problema. 
 
3. (HILLIER e LIEBERMAN, 1995) Uma multinacional decide se instalar em Goiás e 
escolhe dois municípios para construir fábricas e armazéns: Catalão e Rio Verde. Construção 
de fábricas e armazéns nestas cidades resulta nos índices de retornos indicados na Tabela 1.3. 
 
Tabela 1.3 – Índices de retorno em unidades monetárias. 
 Catalão Rio Verde 
Fábrica 72 40 
Armazém 48 32 
 
 
 Os seguintes critérios devem ser respeitados no processo de decisão: se for 
construído armazém em Catalão não será construído armazém em Rio Verde; em unidadesmonetárias, o investimento requerido na construção de uma fábrica em Catalão é 48, o 
 15 
investimento requerido na construção de uma fábrica em Rio Verde é 24, o investimento 
requerido na construção de um armazém em Catalão é 40, o investimento requerido na 
construção de um armazém em Rio Verde é 16 e a empresa disponibiliza no máximo 80 para 
investir nas construções. 
 Temos ainda a condição de que na localidade onde for construído armazém 
tem que ser construída fábrica. Formular o problema de modo a maximizar o retorno do 
investimento. 
 
4. Considere o problema da seção 1.2.3 sobre operação do amplificador de tensão com 
mínimas perdas. Reescreva o modelo em função das variáveis de decisão α e v , que para 
este problema são de fato as variáveis de controle. 
 
5. (BAZARAA, JARVIS e SHERALI, 1997) A qualidade do ar em uma região depende 
principalmente das emissões de efluentes (e.g., 2CO , 2SO , 4CH , etc.) na atmosfera pelas n 
indústrias existentes. Cada instalação industrial pode utilizar m diferentes tipos de 
combustível. Suponha que a energia total necessária à indústria j é jb calorias por dia e que 
ijc é a emissão de efluentes por tonelada do combustível i pela indústria j . Além disso, 
suponha que o combustível do tipo i custa ic dólares por tonelada e que cada tonelada deste 
tipo de combustível gera ijα calorias na indústria j . O nível de poluição do ar na região não 
pode exceder b microgramas por metro cúbico. Finalmente, seja jγ um parâmetro 
meteorológico que relaciona emissões da indústria j à qualidade do ar da região. Escrever o 
modelo do problema para determinar a mistura de combustíveis a ser utilizada por cada 
indústria. 
 
6. Consulte a literatura em Pesquisa Operacional e forneça um exemplo de um problema 
estocástico.