1º Exame de Optimização e Decisão
Mestrado Integrado em Engenharia Mecânica
14 de Janeiro de 2008
5º Ano / 1º Semestre
Exame sem consulta
13:00 – 16:00 h
Nome:
Número:
Escreva o seu número em todas as folhas de exame. O exame tem 8 perguntas, estando a cotação de cada
uma delas indicada entre parêntesis.
1. (1.0) Quais são as fases de um estudo de um problema de Investigação Operacional (ou mais
genericamente, de um problema de optimização)? Explique essas fases de forma sucinta.
2. (3.0) A Empresa Caixilhos, Lda. tem três empregados e fabrica dois tipos de janelas
manufacturadas: janelas com caixilho de madeira ou com caixilho de alumínio. A empresa
ganha 30€ por cada janela com caixilho de alumínio e 60€ por cada janela com caixilho de
madeira. O trabalhador José Trabalho faz janelas com caixilho de madeira, e pode fazer 6 por
dia. A trabalhadora Maria Empregada faz janelas com caixilho de alumínio, e pode fazer 4
por dia. O trabalhador João Vitrais trabalha o vidro e pode fazer 10 m2 de vidro por dia. Cada
janela com caixilho de madeira utiliza 1 m2 de vidro e cada janela com caixilho de alumínio
utiliza 1.2 m2 de vidro. A empresa quer determinar quantas janelas de cada tipo deve
produzir por dia para maximizar o lucro. Formule este problema.
3. (2.0) Considere o problema de atribuição com a seguinte tabela de custos:
“A atribuir”
A
B
C
D
1
8
6
7
6
Tarefas
2
3
6
5
5
3
8
4
7
5
4
7
4
6
6
a) (1.0) Represente a rede deste problema de atribuição.
b) (1.0) Formule o problema como um problema de transportes, construindo uma tabela apropriada.
4. (4.0) O Banco Número Um vai instalar servidores em cada uma das suas filiais, que estarão
ligados ao servidor da sede e utilizarão linhas de telefone dedicadas. Uma dada linha
telefónica de uma filial não necessita de estar ligadas directamente à sede; pode estar ligada
indirectamente utilizando outras ligações de outras filiais. Apenas é requerido que exista uma
ligação, que pode ser indirecta, entre cada filial e a sede.
1
O custo de cada linha a instalar é de 100€ por Km. A distância em Km entre a sede e as filiais
é dada por:
Sede
Filial 1
Filial 2
Filial 3
Filial 4
Filial 5
Distância entre pares de agências
Sede Fil. 1 Fil. 2 Fil. 3 Fil. 4 Fil. 5
–
190
70
115 270 160
190
–
100 110 215
50
70
100
–
140 120 220
115 110 140
–
175
80
270 215 120 175
–
310
160
50
220
80
310
–
a) (2.0) Justifique que este problema pode ser formulado como um problema de redes. Que
tipo de problema de redes é este?
b) (2.0) Resolva este problema utilizando o algoritmo apropriado.
5. (2.0) Considere as seguintes afirmações sobre problemas de Programação Dinâmica. Diga se
as afirmações são verdadeiras ou falsas, justificando.
a) (0.5) O algoritmo de resolução utiliza uma relação recursiva que permite resolver o
problema na etapa (n + 1), sabendo a política óptima na etapa n.
b) (0.5) Após completar o algoritmo de resolução, se por engano foi tomada uma decisão não
óptima numa dada etapa, o algoritmo de resolução deverá ser de novo aplicado para
determinar as novas decisões óptimas (dada a decisão não óptima) nas etapas subsequentes.
c) (1.0) Uma vez determinada a política óptima para o problema global, as informações
necessárias para especificar a decisão óptima numa dada etapa serão: o estado nessa etapa e
as decisões tomadas anteriormente.
6. (3.5) Considere o seguinte problema:
Maximize Z = 9 + 3x1 + 34x2 + 6x3 + 4x4
sujeito a
5x1 + 2x2 ≤ 4
x3 + x4 ≤ 1
x3 ≤ 1
e
xj ≥ 0, para j = 1, 2, 3, 4.
xj é uma variável do tipo binário, para j = 3, 4.
a) (0.5) Como se denomina este tipo de problema?
b) (3.0) Indique um algoritmo que pode ser utilizado para resolver este tipo de problema,
indicando os passos principais da sua aplicação.
7. (2.5) Enuncie os passos principais do Método da Bissecção, indicando a que tipos de
problemas se poderá aplicar. Utilize um exemplo, se quiser.
8. (3.0) Considere que quer minimizar o número de entradas (estados) de um dado modelo
dinâmico, mantendo a precisão desse modelo. Como poderia aplicar uma meta-heurística
para resolver este problema?
2