Lista 11 - Programação Linear

Prévia do material em texto

ER500 - 1s2016
Lista 10: Truques de Modelagem
Questa˜o 1: Um casal quer dividir suas tarefas dome´sticas entre eles de
modo que cada um tenha duas tarefas e o tempo total gasto seja mantido num
minimo. Suas eficieˆncias nas tarefas variam, e o tempo necessa´rio para executar
cada tarefa e´ dado na tabela a seguir:
fazer compras cozinhar lavar a louc¸a lavar a roupa
Mulher 4.5h 7.8h 3.6h 2.9h
Homem 4.9h 7.2h 4.3h 3.1h
Formule um modelo para esse problema.
Questa˜o 2:Uma empresa constro´i pequenos avio˜es a jato para vender a
empresas para o uso de seus executivos. Para atender a` necessidades desses
executivos, os clientes da empresa a`s vezes encomendam um projeto feito sob
encomenda dos avio˜es. Quando isso ocorre, um custo substancial set-up e´ incor-
rido para iniciar a produc¸a˜o. Foram recebidos recentemente pedidos de compra
a partir de treˆs clientes com prazos curtos. No entanto, a empresa ja´ esta´ quase
completamente ocupada com pedidos anteriores, e por isso na˜o sera´ capaz de
aceitar todos os treˆs pedidos. Portanto, uma decisa˜o deve ser feita sobre o
nu´mero de avio˜es a empresa vai concordar para produzir (se houver) para cada
um dos treˆs clientes. Os dados relevantes sa˜o apresentados na tabela seguinte.
A primeira linha da´ o custo de set-up necessa´rio para iniciar a produc¸a˜o dos
avio˜es para cada cliente. Uma vez que a produc¸a˜o esta´ em andamento, a re-
ceita l´ıquida marginal (prec¸o de compra menos o custo marginal de produc¸a˜o)
de cada avia˜o produzido e´ mostrado na segunda linha. A terceira coluna in-
dica a percentagem da capacidade de produc¸a˜o dispon´ıvel, que seriam usados
??para cada avia˜o produzido. A u´ltima linha indica o nu´mero ma´ximo de avio˜es
solicitados por cada cliente.
cliente 1 cliente 2 cliente 3
custo de set up $ 3 milho˜es $ 2 milho˜es 0
receita l´ıquida marginal $ 2 milho˜es $ 3 milho˜es $ 0.8 milho˜es
capacidade usada por avia˜o 20% 40% 20%
nu´mero ma´ximo 3 avio˜es 2 avio˜es 5 avio˜es
Formule um modelo que determine quantos avio˜es produzir (se produzir)
para cada cliente de modo a maximizar o lucro total.
Questa˜o 3: Um nu´mero crescente de americanos esta˜o se movendo para
regio˜es de clima mais quente quando se aposentam. Para tirar proveito dessa
tendeˆncia, uma empresa esta´ considerando realizar um grande projeto empre-
endimento imobilia´rio. O projeto e´ desenvolver uma forma completamente nova
de comunidade de aposentadoria que ira´ abranger va´rios quiloˆmetros quadrados.
Uma das deciso˜es a serem tomadas e´ o lugar onde a localizar os dois corpos de
bombeiros que foram disponibilizados para a comunidade. Para fins de planeja-
mento, a comunidade foi dividida em cinco espac¸os, e na˜o mais do que um corpo
1
de bombeiros pode ser alocado em um espac¸o. Cada corpo de bombeiro deve
responder a todos os inceˆndios que ocorrem no espac¸o no qual esta´ localizada,
bem como as ocorrencias nos outros espac¸os que esta˜o atribu´ıdos a esse corpo de
bombeiros. Assim, as deciso˜es a serem tomadas consistem em quais os espac¸os
que devem receber um corpo de bombeiros e a atribuic¸a˜o de cada um dos outros
espac¸os para um dos corpo de bombeiros. o objetivo e´ minimizar a me´dia geral
dos tempos de resposta aos inceˆndios.
1 2 3 4 5
1 5 12 30 20 15
2 20 4 15 10 25
3 15 20 6 15 12
4 25 15 25 4 10
5 10 25 15 12 5
freq. de inceˆndio por dia 2 1 3 1 3
Formule um modelo para esse problema.
Questa˜o 4: Uma empresa esta´ considerando abrir fa´bricas em 4 cidades:
Nova York, Los Angeles, Chicago e Atlanta para atender treˆs regio˜es no pa´ıs.
Cada fa´brica pode produzir 100 unidades por semana. O custo fixo semanal de
manter cada fa´brica aberta e´ de US$ 400,00 para Nova York, US$ 500,00 para
Los Angeles, US$ 300,00 para Chicago e US$ 300,00 para Atlanta. A regia˜o 1
do pa´ıs requer 80 unidades por semana, a regia˜o 2 requer 70 unidades semanais
e a regia˜o 3 requer 40 unidades por semana. Os custos (incluindo produc¸a˜o e
transporte) de enviar uma unidade de uma fa´brica para uma regia˜o e´ dada pela
tabela abaixo:
fa´brica regia˜o 1 regia˜o 2 regia˜o 3
Nova York 20 40 50
Los Angeles 48 15 26
Chicago 26 35 18
Atlanta 24 50 35
Se a fa´brica de Nova York for aberta enta˜o a fa´brica de Los Angeles tambe´m
devera´ ser aberta; no ma´ximo duas fa´bricas podera˜o ser abertas; ou Atlanta
ou Los Angeles deve ser aberta. Escreva um modelo de programac¸a˜o linear
que atenda a demanda das regio˜es a um custo mı´nimo e que leve em contas as
restric¸o˜es descritas.
Questa˜o 5: Um gerente de produc¸a˜o de uma indu´stria quimica necessita es-
quematizar a contratac¸a˜o de trabalhadores ao longos do treˆs turnos da empresa:
(00:01-08:00), (08:01-16:00),(16:01-24:00), denotados por turnos da noite, de dia
e da tarde, respectivemente. Esses empregados ira˜o trabalhar num novo setor
da empresa que funciona 24h por 7 dias e o nu´mero mı´nimo de empregados em
cada um dos turnos:
Segunda Terc¸a Quarta Quinta Sexta Sa´bado Domingo
Noite 5 3 2 4 3 2 2
Dia 7 8 9 5 7 2 5
Tarde 9 10 10 7 11 2 2
2
O sindicato acordou com a empresa as seguinte as regras:
• Cada trabalhador e´ designado para trabalhar ou no turno da noite ou no
turno de dia ou no turno de tarde. E, uma vez que o empregado tenha
sido designado a um turno, ele permanece naquele turno durante todos os
dias da semana.
• Cada trabalhador trabalha 4 dias consecutivos durante a semana.
Escreva um modelo de PL cuja soluc¸a˜o e´ a alocac¸a˜o dos trabalhadores nos
turnos e minimize o nu´mero de empregados contratados neste novo setor.
Questa˜o 6: Uma equipe esta´ tentando escolher a linha de partida para o
time de basquete. O time consiste em sete jogadores quer devem ser avaliados
(em uma escala em que 1 = pobre e 3 = excelente) de acordo com posse de
bola, arremesso, recuperac¸a˜o e habilidades defensivas. As posic¸o˜es em que cada
jogador pode jogar e as habilidades de cada jogador sa˜o listadas na seguinte
tabela:
jogador posic¸a˜o posse de bola aremesso recuperac¸a˜o habilidades defensivas
1 G 3 3 1 3
2 C 2 1 3 2
3 G-F 2 3 2 2
4 F-C 1 3 3 1
5 G-F 3 3 3 3
6 F-C 3 1 2 3
7 G-F 3 2 2 1
Os cinco jogadores na linha de partida devem satisfazer as seguintes res-
tric¸o˜es:
1. no mı´nimo quatro membros devem estar aptos a jogar em G (guard)
2. no mı´nimo dois membros devem estar aptos a jogar em F (forward)
3. no mı´nimo um membro deve estar apto a jogar em C (center)
4. a me´dia dos n´ıveis de posse de bola, arremesso e recuperac¸a˜o da linha de
partida deve ser no mı´nimo 2
5. se o jogador 3 comec¸a, enta˜o o jogador 6 na˜o pode comec¸ar
6. se o jogador 1 comec¸a, enta˜o os jogadores 4 e 5 devem ambos comec¸ar
7. ou o jogador 2 ou o jogador 3 deve comec¸ar
Dada essas restric¸o˜es, a equipe deseja maximizar a habilidade defensiva total
do time. Formule um problema que escolha qual deve ser a linha de partida.
Questa˜o 7: Um produto pode ser produzido em quatro ma´quinas diferentes.
Cada ma´quina tem um custo fixo de setup, um custo unita´rio de produc¸a˜o e
uma capacidade de produc¸a˜o, dados na tabela a seguir:
3
ma´quina custo fixo custo por unidade capacidade
1 1000 20 900
2 920 24 1000
3 800 16 1200
4 700 28 1600
Um total de 2000 unidades do produto devem ser produzidos. Formule um
problema cuja soluc¸a˜o minimize o custo total.
Questa˜o 8: Um caminha˜o que faz entrega de refrigerante comec¸a no local
1 e deve entregar o refrigerante para os locais 2,3,4 e 5 antes de retornar ao
local1. A distaˆncia entre esses locais e´ dada na tabela abaixo:
1 2 3 4 5
1 0 20 4 10 25
2 20 0 5 30 10
3 4 5 0 6 6
4 10 25 6 0 20
5 35 10 6 20 0
O caminha˜o deseja minimizar a distaˆncia total percorrida. Em qual ordem
a entrega deve ser feita?
Questa˜o 9: A diretoria de uma empresa esta´ considerando sete grandes
investimentos. Cada investimento pode ser feito somente uma vez. Esses in-vestimentos diferem no lucro de longo prazo estimado (valor l´ıquido presente)
que sera´ gerado assim como na quantia de dinheiro exigido, como mostrado na
tabela a seguir (em unidades de milho˜es de do´lares:)
1 2 3 4 5 6 7
lucro estimado 17 10 15 19 7 13 9
capital exigido 43 28 34 48 17 32 23
A quantidade total de dinheiro dispon´ıvel para esses investimentos e´ de 100
do´lares. Os investimentos 1 e 2 sa˜o mutuamente exclusivos, assim como os inves-
timentos 3 e 4. Ale´m disso, nem o investimento 3 nem o 4 pode ser feito a menos
que um dos dois primeiros investimentos seja feito. Na˜o existem restric¸o˜es sobre
os investimentos 5, 6 e 7. Formule um problema que selecione a combinac¸a˜o dos
investimentos que maximize o lucro total de longo prazo estimado.
Questa˜o 10: Uma empresa tem os seguintes investimentos dispon´ıveis:
• Investimento A: para cada real investido no tempo 0, recebe-se 0.10 reais
no tempo 1 e 1.30 reais no tempo 2.
• Investimento B: para cada real investido no tempo 1, recebe-se 1.60 reais
no tempo 2.
• Investimento C: para cada real investido no tempo 2, recebe-se 1.20 reais
no tempo 3.
(tempo 0 = agora; tempo 1 = 1 ano a partir de agora e assim por diante).
4
A qualque tempo, o dinheiro na˜o investido pode ser colocado em uma pou-
panc¸a, que retorna 10% por ano.
No tempo zero ha´ 100 reias. No ma´ximo 50 reais podem ser investidos em
cada um dos investimentos. Formule um PPL que maximize a quantidade de
dinheiro que a empresa pode ter no tempo 3.
5