lista 1 po

Prévia do material em texto

Disciplina: Pesquisa Operacional
Professor: Francisco Glaubos
Lista de exercícios 1: modelagem
Questão 1
Defina uma formulação matemática para o seguinte problema. Uma refinaria
processa vários tipos de petróleo. Cada tipo de petróleo possui uma planilha
de custos diferente, expressando condições de transporte e preços na origem.
Por outro lado, cada tipo de petróleo representa uma configuração diferente
de subprodutos para a gasolina. Na medida em que um certo tipo de petróleo
é utilizado na produção da gasolina, é possível a programação das condições
de octanagem e outros requisitos. Esses requisitos implicam a classificação
do tipo da gasolina obtida. Supondo que a refinaria trabalhe com uma linha
de quatro tipos diferentes de petróleo e deseje produzir as gasolinas amarela,
azul e superazul, programe a mistura dos tipos de petróleo, atendendo às
condições que se seguem nas Tabelas 1 e 2, a fim de maximizar o lucro da
refinaria.
Tipo de petróleo Qtd máxima disponível(Barril/Dia)
Custo por Barril/Dia
(R$)
1 3500 19
2 2200 24
3 4200 20
4 1800 27
Tabela 1: Quantidade disponível de petróleo
1
Tipo de gasolina Especificação Preço de venda(R$/Barril)
superazul
Não mais que 30% de 1.
Não menos que 40% de 2.
Não mais que 50% de 3.
35
azul Não mais que 30% de 1.Não menos que 10% de 2. 28
amarela Não mais que 70% de 1. 22
Tabela 2: Percentuais para limites de qualidade das gasolinas
Questão 2
Suponha que você esteja interessado no investimento de um conjunto de
ações {1, ..., 7} utilizando variáveis booleanas (com valor 0 ou 1). Se a ação
i é escolhida então xi = 1, caso contrário, xi = 0. Modele as seguintes
restrições:
1. Você não pode investir em todas as ações.
2. Você deve escolher pelo menos uma das ações.
3. Ação 1 não pode ser escolhida se a ação 3 for escolhida.
4. Ação 4 pode se escolhida apenas se a ação 2 também for escolhida.
5. Você deve escolher ou ambas ações 1 e 5 ou nenhuma delas.
6. Ou você deve escolher pelo menos uma das ações 1,2,3 ou pelo menos
duas das ações 2,4,5,6.
Questão 3
Defina uma formulação matemática para o seguinte problema. Uma empresa
fabrica quatro variantes do mesmo produto e na parte final do processo de
fabricação existem operações de montagem, polimento e embalagem. Para
cada variante o tempo necessário para essas operações é mostrado na Tabela
3 e também o lucro por unidade vendida.
2
Variante Montagem Polimento Embalagem Lucro (R$)
1 2 3 2 1,50
2 4 2 3 2,50
3 3 3 2 3,00
4 7 4 5 4,50
Tabela 3: Tempo necessário para as operações (em minutos).
Dada a atual situação da mão-de-obra, a empresa estima que, a cada ano,
têm 100.000 minutos de montagem, 50.000 minutos de polimento e 60.000
minutos de tempo de embalagem. Quantos de cada variante a empresa deve
fazer por ano a fim de maximizar o lucro?
Suponha agora que a empresa é livre para decidir quanto tempo pode
dedicar a cada uma das três operações (montagem, polimento e embalagem)
dentro do tempo total permitido de 210.000 (= 100.000 + 50.000 + 60.000)
minutos. Quantos de cada variante a empresa deve fazer por ano a fim de
maximizar o lucro?
Questão 4
Defina uma formulação matemática para o seguinte problema. Um hospital
deseja planejar os horários de enfermeiras de seu turno da noite. A demanda
por enfermeiras no turno da noite no dia j = 1, ..., 7 da semana é um número
inteiro dj. Cada enfermeira trabalha 5 dias consecutivos e descansa nos 2
dias seguintes. O objetivo consiste em minimizar o número de enfermeiras
contratadas.
Questão 5
Certa empresa fabrica 2 produtos P1 e P2. O lucro por unidade de P1 é
de $100,00 e o lucro unitário de P2 é de $150,00. A empresa necessita de 2
horas para fabricar uma unidade de P1 e 3 horas para fabricar uma unidade
de P2. O tempo mensal disponível para essas atividades é de 120 horas. As
demandas esperadas para os 2 produtos levaram a empresa a decidir que os
montantes produzidos de P1 e P2 não devem ultrapassar 40 unidades de P1
e 30 unidades de P2 por mês. Construa o modelo do sistema de produção
3
mensal com o objetivo de maximizar o lucro da empresa.
Questão 6
Considere o seguinte programa de programação linear (PPL):
Min
∑
j∈J
cjxj (1)
s.a : (2)∑
j∈J
a1jxj ≤ b1 (3)∑
j∈J
a2jxj ≤ b2 (4)
xj ≥ 0 ∀j ∈ J (5)
Condição: pelo menos uma das restrições (3) ou (4) deve ser satisfeita.
A condição de que pelo menos uma das restrições deve ser mantida não
pode ser formulada em um PPL, no qual todas as restrições devem ser sa-
tisfeitas. Um exemplo de tal situação é um processo de fabricação, onde são
possíveis dois modos de operação.
Formule um novo PPL, atendendo a condição estabelecida.
Questão 7
Um sapateiro faz seis sapatos por hora, se fizer somente sapatos, e cinco
cintos por hora, se fizer somente cintos. Ele gasta duas unidades de couro
para fabricar uma unidade de sapato e uma unidade de couro para fabricar
uma unidade de cinto. Sabendo-se que o total disponível de couro é de 6
unidades e que o lucro unitário por sapato é de $5,00 e o do cinto é de
$2,00, pede-se: o modelo do sistema de produção do sapateiro, se o objetivo
é maximizar seu lucro por hora.
4
Questão 8
Antigamente, muitos vendedores chamados de caixeiros viajantes, ganhavam
a vida oferecendo seus produtos em diferentes cidades. Imagine que um cai-
xeiro viajante escolhesse algumas cidades e precisasse encontrar o caminho
mais curto para suas andanças. Em que ordem ele deveria percorrer as cida-
des escolhidas?
Defina um modelo de programação linear para o problema do caixeiro
viajante:
Dado um mapa de cidades e um ponto de partida do caixeiro, temos que
encontrar um percusso para o caixeiro visitar (n − 1) cidades, voltando ao
ponto de partida, visitando apenas uma vez cada cidade, de modo a reduzir
o custo total da viagem.
cij : custo da viagem da cidade i até a cidade j.
5