Prova2_PO_2sem_2005.pdf

Prévia do material em texto

Prova II - Pesquisa Operacional - 23/02/2006 
Fernando Nogueira 1
nome: 
 
1)[2.0] Determine o Fluxo Máximo na rede abaixo, onde os números sob os arcos representam a capacidade máxima 
nos arcos. 
 
1
2
3
4
5
6
7
3
4
3
4
5
4
1
3
1
2
2
5
 
 
2)[2.0] Escreva o modelo de programação linear para a rede da questão 1. 
 
3)[2.0] Construa um problema de programação linear inteira cuja solução ótima seja igual a solução ótima 
arredondada do mesmo problema desconsiderando a restrição de solução inteira. Forneça as soluções para os 
problemas. Obs: a solução ótima do problema desconsiderando a restrição de solução inteira não pode ser inteira. 
 
4)[2.0] Escreva um programa, na linguagem que preferir que dado uma lista de arcos forneça um caminho entre o nó 
inicial e o nó final de uma rede. Considere que a lista contém ao menos um caminho entre o nó inicial e o nó final. 
 
5)[2.0] Seja µp e µi, a duração total de um projeto e a duração média de cada atividade i, respectivamente, qual a 
consideração que tem que ser feita sobre µi a fim de que ∑
=
µ=µ
n
1i
ip
seja correta. Justifique sua resposta. 
 
Observações Importantes 
? Período para realização desta prova: 2 hs. 
? O professor não irá responder qualquer dúvida dos alunos. 
? Não é permitido o uso de calculadora. 
? O prazo para realização da prova, bem como o entendimento/interpretação das questões fazem parte da 
avaliação. 
? O aluno poderá ficar com esta prova. 
 
 
 
 
 
 
 
 
 
Boa Prova 
 Prova II - Pesquisa Operacional - 23/02/2006 
Fernando Nogueira 2
Resolução 
 
1) [2.0] os números a esquerda da vírgula são as capacidades máximas nos arcos e os números a direita da vírgula 
são os fluxos efetivos. O fluxo máximo é 9. 
 
1
2
3
4
5
6
7
3,3
4,4
3,2
4,4
4,4
1,1
3,1
1,1
2,2
2,2
5,1
5,5
 
 
2) [2.0] código MPL 
max x71 
 
subject to 
 
x12+x13+x14-x71=0; 
x25-x12-x32=0; 
x32+x35+x36-x13=0; 
x45+x46-x14=0; 
x57+x56-x25-x35-x45=0; 
x67-x56-x36-x46=0; 
x71-x57-x67 = 0; 
x12<=3; 
x13<=4; 
x14<=3; 
x32<=5; 
x25<=4; 
x35<=2; 
x36<=1; 
x45<=3; 
x46<=1; 
x56<=2; 
x57<=5; 
x67<=4; 
 
3) [2.0] código MPL 
max x1+x2 
 
subject to 
x1<=5.2; 
x2<=5.2; 
 
 Prova II - Pesquisa Operacional - 23/02/2006 
Fernando Nogueira 3
integer x1 x2 
 
 
A solução ótima inteira é x1 = 5 e x2 = 5 com Z = 10. 
A solução ótima desconsiderando a restrição das variáveis serem inteiras é x1 = 5.2 e x2 = 5.2 com Z = 10.4, a qual 
arredondada é x1 = 5 e x2 = 5 com Z = 10, que por sua vez é idêntica a a solução considerando a restrição de inteiro. 
 
4) [2.0] Código Matlab 
 
% X é o nó final, fornecido pelo usuário 
%lista=[ 1 2 
% 2 3 
% .... 
% 5 6] 
%Y é o nó inicial, fornecido pelo usuário 
 
linhanofim= find(lista(:,2)==X); 
caminho=[lista(linhanofim,2) lista(linhanofim,1)]; 
no= lista(linhanofim,1); 
while no~=Y 
 linha=find(lista(:,2)==caminho(end)); 
 caminho=[caminho lista(linha,1)]; 
 no= lista(linha,1); 
end 
caminho 
 
5) [2.0] As durações médias de cada atividade i são estatisticamente independentes entre si.