Trabalho de Casa 1
15.053 Introdução à Otimização
Para ser entregue no início da aula de quinta-feira, 14 de fevereiro de 2002
1. Formulações de PL
a. Dê um exemplo de uma programação linear de duas variáveis que tenha uma solução ótima.
b. Dê um exemplo de uma programação linear de duas variáveis que não tenha uma solução
viável.
c. Dê um exemplo de uma programação linear de duas variáveis que tenha múltiplas soluções
ótimas.
d. Dê um exemplo de uma programação linear de duas variáveis cujo valor objetivo não tenha
limite superior. (Assuma que estamos maximizando para esta parte.)
Não pegue exemplos do livro, mas não há problemas em pegar exemplos semelhantes.
2. Escala dos Funcionários do Correio. No correio local, os funcionários são escalados para
cinco dias de trabalho seguidos por dois dias de descanso, escala esta repetida semanalmente.
Assim, um funcionário tem os mesmos dois dias de folga toda as semanas, e esses dias são
consecutivos (por exemplo, domingo e segunda-feira). A demanda por funcionários é
fornecida na tabela abaixo. Essa demanda deve ser suprida ou excedida em cada dia. Os
números representam a quantidade total de funcionários que está trabalhando nesse dia. O
custo dos funcionários é $250 por dia útil, $275 por sábado e $300 por domingo.
Dia
Segunda
Demanda
17
Terça
13
Quarta
15
Quinta
19
Sexta
14
Sábado
16
Domingo
11
a. Formule um programa linear que minimizará o custo total dos funcionários do correio
necessários para suprir as demandas diárias. Obs.: o número de funcionários é inteiro, mas
para os propósitos deste exercício, você pode permitir que um número fracionado de
funcionários comece trabalhando em qualquer dia.
b. Use a planilha do Excel Solver fornecida no site (a de nome “2 Postal Workers” em
Homework_01.xls) como ponto de partida para solucionar esta programação linear (você precisará
do Excel Solver instalado como suplemento em seu computador, além de estudar as instruções
sobre como utilizar o Excel Solver). Obs.: O Excel Solver atual está ajustado para minimizar o
número de funcionários. Você precisará ajustar a PL de modo que ela minimize o custo total dos
trabalhadores.
c. Como a solução seria alterada se o número de funcionários requerido na quinta-feira
baixasse para 18?
d. Modifique a planilha de modo que ela encontre a solução de custo mínimo sujeita à restrição
adicional de que o número de funcionários que iniciam no sábado é pelo menos 2 e o número
de funcionários que começam no domingo é no mínimo 2.
e. Escreva um programa linear com base na seguinte versão abstrata do Problema do
Funcionário do Correio.
No correio local, os funcionários são escalados ao longo de n períodos. A escala repete-se
periodicamente. Existem n possíveis turnos para os funcionários, cada um começando em cada
um dos n períodos. Seja aij = 1 se os funcionários no turno j trabalharem durante o período i.
Seja di a demanda de funcionários no período i. Seja ci o custo de um funcionário durante o
período i. Assim, o custo de um turno é a soma de custos dos funcionários nos períodos do
turno. Expresse como programa linear o problema de minimização do custo da força de trabalho
de modo que ela supra ou exceda as demandas em cada período. Para suas variá veis de decisão,
1
você deve fazer xj denotar o número de funcionários que trabalha no turno j. Faça fj ser o custo
do funcionário no turno j. Deixe claro que fj é em termos dos c’s.
2
3. Construtor de apartamentos
Um construtor imobiliário está planejando um novo complexo de apartamentos. Podem ser
construídos três tipos de unidades: apartamentos de um quarto, apartamento de dois quartos e
apartamentos de três quartos. Cada apartamento de um quarto requer 700 pés2 , cada
apartamento de dois quartos requer 800 pés2 e cada apartamento de três quartos requer 1,200
pés2 .
O construtor quer fazer uma mistura de tipos de apartamento no complexo. Ele acredita que o
número de apartamentos com um quarto deve ser entre 15% e 50% do número total de
apartamentos. Do mesmo modo, os apartamentos de dois quartos devem corresponder entre
10% e 50% do número total de apartamentos, e os apartamentos de três quartos devem formar
de 0% a 25% do número total de apartamentos.
As leis locais de zoneamento não permitem que o construtor faça mais de 42 unidades neste
local de construção específico, além de restringirem o edifício a no máximo 41.000 pés2 . O
construtor já concordou em arrendar 5 unidades de um quarto e 8 unidades de dois quartos para
uma imobiliária local, que será um "sócio passivo" neste empreendimento. Os estudos de
mercado mostram que apartamentos de um quarto são alugados por $650 por mês, os de dois
quartos por $750 por mês e os de três quartos, $950 por mês. Assuma que o sócio passivo
pagará a taxa de mercado pelos apartamentos.
a. Defina o problema acima como um programa linear. Faça x1 , x2 e x3 denotarem,
respectivamente, o número de apartamentos de um quarto construídos, o número de
apartamentos de dois quartos construídos e o número de apartamentos de três quartos
construídos.
b. Use o Excel Solver para desenvolver um plano de construção. Você encontrará a planilha na
pasta de nome “3 Apartment Developer” em Homework_01.xls. Qual é a solução se o
tamanho dos apartamentos de um quarto for de apenas 650 pés2 ? Qual é a solução se o
tamanho dos apartamentos de um quarto for 700 pés2 e for necessário que a proporção de
apartamentos de um quarto seja de pelo menos 25% do total?
c. Qual seria a solução se requerêssemos que o número máximo de apartamentos de três
quartos fosse no máximo 30% do total (em vez de 25% do total)?
d. Escreva um programa linear baseado na seguinte versão abstrata e abreviada do Problema 3.
Um construtor imobiliário está planejando um novo complexo de apartamentos. Podem ser
construídos K tipos de unidades: as unidades do tipo i requerem si pés2 e são alugadas por $c i .
O construtor quer fazer uma mistura de tipos de apartamento no complexo. Ele acredita que o
número de unidades do tipo i deve ser de pelo menos li % do total e de no máximo ui % do total.
As leis locais de zoneamento não permitem que o construtor faça mais de B unidades neste local
de construção específico, além de restringirem o edifício a no máximo S pés2 (identifique
claramente as variáveis de decisão e use a notação de somatória para expressar seu programa
linear).
3
4. Agendamento de vôos por centrais. Considere o conjunto de quatro segmentos de vôo
abaixo. Ele é parte da grade de uma companhia aérea, que envolve milhares de vôos todos os
dias.
Nº do Vôo
Saída
Chegada
1A
Boston 8h
Chicago 10h15
1B
Chicago 10h45
San Francisco 12h15
2A
Nova York 7h45
Chicago 10h15
2B
Chicago 10h45
Los Angeles 12h15
Cada aeronave possui 200 assentos, e cada assento pode ser alocado para cada vôo. A partir
desses quatro vôos, é possível obter 8 itinerários distintos: Boston – Chicago, Boston – San
Francisco, Boston – Los Angeles, Nova York – Chicago, Nova York – San Francisco, Nova
York – Los Angeles, Chicago – San Francisco e Chicago – Los Angeles. As tarifas e demandas
dos vôos são determinadas na tabela abaixo (na próxima página). Considere o problema de
atribuição de assentos nos vôos para os itinerários de modo que não haja mais de 200 assentos
ocupados em cada um dos vôos e de modo que não seja excedida a demanda por nenhum
itinerário, para portando maximizar a receita.
a. Formule esse problema como um programa linear. Para suas variáveis de decisão, seja
xBC o número de pessoas no itinerário de Boston para Chicago e seja xBS o número de
pessoas no itinerário de Boston a San Francisco, etc. Além disso, seja yBC o número de
passageiros no vôo de Boston para Chicago, e seja yCS o número de pessoas no vôo de
Chicago para San Francisco, etc (Obs.: seria possível formular este problema sem as
variáveis y, mas seria muito difícil formular este problema sem as variáveis x. Uma
possível razão para o fato de que as variáveis y são úteis na prática é que o conjunto
ótimo de variáveis de decisão é armazenado no banco de dados, e é útil ter as variáveis y
no banco de dados para as dúvidas subseqüentes).
b. Solucione o problema usando o Excel. Você pode encontrar a planilha na pasta de nome
“4 Flight Schedulings” em Homework_01.xls. Na prática, esse deve ser um programa
inteiro no qual haverá um número inteiro de pessoas atribuído para cada itinerário.
Entretanto, para o propósito deste exercício, é permitido atribuições fracionadas.
c. Qual seria a solução ótima se as aeronaves pudessem transportar 210 passageiros em vez
de 200?
d. Qual seria a solução ótima se cada vôo pudesse transportar 200 passageiros e cada
itinerário precisasse ter atribuídos os assentos de pelo menos 15 pessoas?
4
Itinerário
Tarifa e demanda
B-C
$200
50
B-SF
$320
110
B-LA
$400
130
NY-C
$250
88
NY-SF
$410
125
NY-LA
$450
85
C-SF
$200
73
C-LA
$250
51
e. Escreva um programa linear com base na seguinte versão abstrata e abreviada do
Problema 4.
Uma linha aérea deseja maximizar suas receitas. Existem n itinerários diferentes e m vôos
diferentes. Seja aij = 1 se o vôo i for um dos vôos do itinerário j. A demanda pelo itinerário j é
dj . O número total de pessoas que podem pegar o vôo i é no máximo ui . A receita de um
passageiro no itinerário j é rj . Formule o problema de atribuição de assentos nos vôos para os
itinerários de modo que não estejam atribuídos mais de ui no vôo i, e de modo que não seja
excedida a demanda por nenhum itinerário, para assim maximizar a receita.
5