INSTITUTO SUPERIOR TÉCNICO – DECIVIL
INVESTIGAÇÃO OPERACIONAL
Ano Lectivo 2014/2015
1º Exame - 06 de Junho de 2015
1. Só após entrega das respostas ao Grupo I os alunos poderão ter acesso aos elementos de
consulta (2 páginas A4 preparado pelo próprio) e à máquina de calcular. A entrega do Grupo
I pode ocorrer em qualquer instante, sendo a duração total da prova 2h30m.
2. Responda a cada grupo em conjunto separado de folhas (que possa ser destacado dos
restantes), preferencialmente agrafado. É obrigatório entregar pelo menos uma folha para
cada grupo (com identificação do aluno e do grupo), ainda que não contenha respostas.
3. Identifique todas as folhas (no topo das mesmas e deixando uma faixa com cerca de 2cm)
com o seu nome e número legíveis.
4. Deixe espaços em branco (pelo menos 2 linhas) entre respostas às diferentes
questões/alíneas.
Grupo II (3.5 valores)
a)
O gerente de uma empresa de transportes de turismo na cidade tem, entre outras, a tarefa de
assegurar um número adequado de motoristas ao longo do dia para dar resposta à procura.
Para resolver esse problema começou a analisar a procura num dia normal de semana (2ª a 6ª)
e conseguiu caracterizar as necessidades de motoristas de acordo com a seguinte tabela:
Período do dia
8h-10h
10h-12h
12h-14h
14h-16h
16h-18h
18h-20h
Nº mínimo de
motoristas
8
16
12
10
16
14
Para a realização do trabalho poderá afectar motoristas com os seguintes horários:
H1 – Horário completo e contínuo, em que o motorista trabalha 8 horas consecutivas
H2 – Horário completo repartido, em que o motorista trabalha 8 horas por dia em dois
períodos de 4 horas (com intervalo de 2 ou 4 horas)
H3 – Horário parcial, em que o motorista trabalha 4 h por dia
Adicionalmente, a empresa tem como estratégia de gestão dos recursos humanos que o
número de motoristas em horário parcial (H3) não deve ser superior ao número de motoristas
com horário completo (contínuo ou repartido).
Sabendo que os custos totais para a empresa são de 1400, 1800 e 800 euros mensais por cada
motorista contratado respectivamente com o horário H1, H2 e H3, formule o problema em
programação matemática que permita ao gerente da empresa optimizar os custos com os
motoristas. Na sua resposta explicite claramente:
i) as variáveis utilizadas, descrevendo o seu significado e as unidades;
ii) o objectivo e respectiva função, identificando as diferentes componentes que
formam a equação;
iii) as restrições e respectivas expressões analíticas que as descrevem.
b) Depois de resolver o problema anterior para cada dia da semana, o gerente da empresa
identificou as necessidades mínimas de motoristas por cada tipo de horário diário (H1, H2 e
H3) em cada dia de semana e que sintetizou no quadro seguinte.
H1
H2
H3
2ª
10
4
12
3ª
10
4
12
4ª
10
4
12
5ª
10
4
12
6ª
10
4
12
Sáb.
12
6
14
Dom.
14
8
22
Sabendo que cada motorista trabalha cinco dias consecutivos por semana (os dois dias de
descanso por semana têm que ser seguidos, por exemplo: Sábado e Domingo, Domingo e
Segunda, Segunda e Terça, etc) o gerente da empresa formulou o problema em Programação
Matemática para determinar quantos motoristas é que necessita de contratar para cada tipo
de horário que minimiza os custos com os motoristas a contratar.
Diga se concorda com a estratégia utilizada pelo gerente da empresa em separar o problema
em dois, comparada com a optimização conjunta dos dois problemas num só, realçando as
vantagens e inconvenientes de cada uma das estratégias (NÃO É NECESSÁRIO FORMULAR O
PROBLEMA). Justifique a sua resposta.
Grupo III (4.5 valores)
1. Considere o seguinte problema de Programação Linear:
Max G = 2 X1 - X2 + X3
S.a.
R1: X1 + X2 + X3 ≤ 3
R2: X1 - 2 X2 + X3 ≥ 1
R3:
2X2 + X3 ≤ 2
X1, X2, X3 ≥ 0
a) Escreva o primeiro quadro do Simplex para aplicação do método Big-M. Não efectue
qualquer iteração do algoritmo do Simplex.
b) Continuando a aplicar o algoritmo do Simplex, obteve-se o quadro que se segue, no qual
Fi designa a variável de folga da restrição Ri (i = 1,2,3).
X1
X2
X3
F1
F2
F3
0
1
0
1/3
1/3
0
2/3
1
0
1
2/3
- 1/3
0
7/3
0
0
1
- 2/3
- 2/3
1
2/3
0
0
-1
-1
1
0
-4
Tendo este quadro como ponto de partida, determine a solução óptima do problema.
Nota: Indique o valor da função objectivo e de todas as variáveis (de decisão e de folga)
nessa solução óptima.
2. Considere agora o seguinte problema de Programação Linear:
Max L = - 5 X1 + 5 X2 + 13 X 3
S.a.
R1: - X1 + X2 + 3 X3 ≤ 20
R2: 12 X1 + 4 X2 + 10 X3 ≤ 90
X1, X2, X3 ≥ 0
no qual os termos independentes das restrições R1 e R2 correspondem às quantidades
disponíveis de determinados recursos 1 e 2 e a função objectivo exprime o lucro (líquido) obtido
com a venda de três produtos nas quantidades expressas por X1, X2 e X3.
Por aplicação do algoritmo do Simplex a este problema obteve-se o seguinte quadro final, no
qual Fi é a variável de folga da restrição Ri (i = 1,2)
X1
X2
X3
F1
F2
-1
1
3
1
0
20
16
0
-2
-4
1
10
0
0
-2
-5
0
- 100
a) “A solução óptima do problema, expressa no quadro, não é única”. Concorda com esta
afirmação? Justifique.
b) Determine o intervalo em que pode variar o coeficiente da variável X2 na função objectivo
de forma a que a solução do quadro anterior se mantenha como solução óptima do
problema.
c) Há algum recurso cuja quantidade disponível possa ser diminuída sem que a solução do
quadro anterior deixe de ser óptima? Em caso de resposta negativa, explique porquê. Em
caso de resposta positiva, qual é este recurso e qual pode ser esse decréscimo, no
máximo? Justifique devidamente.
d) Verificou-se que a formulação do problema estava incompleta, sendo necessário
adicionar uma nova restrição:
X2 ≤ X1 + X3
d1) Qual o impacto da adição desta restrição sobre a solução óptima do problema
anterior (antes da adição da nova restrição) expressa no quadro, a nível de possibilidade
e de optimalidade? Justifique.
d2) Atendendo à resposta a d1), é possível que o valor óptimo da função objectivo no
domínio das soluções possíveis do novo problema (com a adição da nova restrição) se
mantenha igual ao do quadro (L=100)? Justifique. Nota: Pretende-se que dê uma
resposta genérica, sem efectuar quaisquer cálculos adicionais.
Grupo IV (4 valores)
Na sede de uma grande empresa, onde trabalham 1000 pessoas, existe uma oficina self-service
gratuita com o material necessário para operações de manutenção a bicicletas (com um só
posto de trabalho), a qual pode ser utilizada pelos trabalhadores durante o horário de
trabalho. Ao fim de um tempo de existência deste serviço, constatou-se que 50% dos
trabalhadores já usa bicicleta e que cada um destes utiliza a oficina em média duas vezes por
mês. Verificou-se ainda que tempo gasto por pessoa na oficina é aleatório, aproximando-se de
uma distribuição exponencial negativa com média 10 minutos. (Considere que um mês tem 22
dias e que um dia tem oito horas de trabalho.)
a) Quantas horas de trabalho são “perdidas” na oficina durante um mês?
b) Qual a probabilidade de haver mais do que duas pessoas na oficina?
c) Qual o valor máximo mensal que a empresa deve considerar despender para instalar e
manter um novo posto ao lado do existente, para reduzir a quebra de produtividade
provocada pela oficina, e no caso de valorizar a hora de trabalho do seu pessoal em 10
euros?
d) Suponha que se admite limitar o tempo de utilização da oficina a um máximo de 15
minutos por pessoa, mas sem alterar o tempo médio de utilização (que se manteria
nos 10 minutos). Assumindo que todos os outros pressupostos se mantinham,
nomeadamente quanto à taxa de chegada, qual o efeito expectável desta medida no
tempo de espera dos utentes da oficina? Justifique a sua resposta (sem efectuar
quaisquer cálculos).