Atividades de Pesquisa Operacional

Prévia do material em texto

1/6 
 
 
 
 
CENTRO UNIVERSITÁRIO DA GRANDE DOURADOS 
Curso: Engenharia de Produção 
Semestre: 6º 
Disciplina: Pesquisa Operacional 
Professor: Bárbara Helen Rodrigues Ramires Seribeli 
 
ATIVIDADE 2 - REFERENTE AS AULA 05 A 08 
 
1. Uma pessoa vai trabalhar de carro todos os dias. Como acabou de concluir um curso de análise de 
redes, essa pessoa sabe determinar o caminho mais curto até seu local de trabalho. A rede da Figura a 
seguir mostra as possíveis rotas entre sua casa e seu trabalho. Desta forma, determine para essa pessoa 
a trilha mais curta que saem do nó 1 e chegam ao 7. 
 
R: 
 
n 
Nós resolvidos 
diretamente 
conectados para 
nós não 
resolvidos 
Nós não 
resolvido 
conectados 
mais 
próximos 
Distância 
total 
envolvida 
N-ésimo 
nó 
mais 
próximo 
Distância 
mínima 
Última 
conecção 
1 1 3 2 3 2 1_3 
3,4 e 5 1 4 4 4 4 1_4 
 3 4 2+2 4 4 3_4 
 3 5 2+3 5 
4 
3 5 2+3 5 5 3_5 
4 6 4+4 6 
5 3 6 2+5 7 
 5 6 2+3+1 6 6 5_6 
 5 7 10 7 
6 5 7 2+3+1+3 7 9 6_7 
 
A última tabela temos como conecção: 1-3;3-5;5-6;6-7. Assim o menor caminho é: 9 milhas 
 
 
 
 2/6 
 
 
 
 
2. Você precisa fazer uma viagem de carro para outra cidade que jamais havia estado anteriormente. 
Portanto, você está estudando um mapa para determinar a rota mais curta para seu destino. 
Dependendo de qual rota você escolher, há cinco outras cidades (chamemos estas A, B, C, D, E) que 
talvez você passe durante o caminho. O mapa mostra a milhagem ao longo de cada estrada que conecta 
diretamente duas cidades sem qualquer cidade entre elas. Esses números são sintetizados na tabela a 
seguir, na qual um traço indica que não há nenhuma estrada conectando diretamente essas duas cidades 
sem passar por alguma outra cidade. 
 
 
a) Formule esse problema como um problema do caminho mais curto desenhando uma rede em 
que nós representam cidades, ligações representam estradas e números indicam o comprimento 
de cada ligação em milhas. 
 
R: 
 
70
40
60
55
60
10
50 80
50
Origem
A
B
C
D
E
Destino
 
 
 
 
 
 
 
 
 
 
 
 
 3/6 
 
 
 
 
(b). Use o modelo formulado no item anterior para resolver esse problema do caminho mais curto e 
determine o caminho ótimo. 
 
R: 
 
n 
Nós resolvidos 
diretamente 
conectados para nós 
não resolvidos 
Nós não 
resolvido 
conectados 
mais 
próximos 
Distância 
total 
envolvida 
N-ésimo nó 
mais 
próximo 
Distância 
mínima 
Última 
conecção 
1.0 Origem A 0+40 A 40 0+A 
1.1 A D 40+70 D 110 A+D 
1.2 D Destino 40+70+60 Destino 170 Destino 
2.0 Origem B 0+60 B 60 0+B 
2.1 B D 60+55 D 115 B+D 
2.2 D Destino 60+55+60 Destino 165 Destino 
3.0 Origem C 0+50 C 50 0+C 
3.1 C E 50+50 E 100 C+E 
3.2 E Destino 50+50+80 Destino 180 Destino 
 
 
 
O Caminho ótimo ou mais rápido será: Origem →B→D→destino 
 
c) Suponha que o Custo unitário por milha percorrida seja de R$ 17,00 qual é o valor do custo 
mínimo? 
R: 
 
Distância 
ótima 
Distância 
ótima 
Distância 
ótima 
165 R$ 17,00 R$ 2.805,00 
 
O custo total usando o melhor caminho é de R$ 2.805,00 
 
 
 
 
 
 4/6 
 
 
 
3. Escreva ao menos 2 exemplos de programação não linear que um engenheiro ou administrador pode 
encontrar no dia a dia de trabalho. 
 
R: Um exemplo pode ser descrito como resolver problemas de um Mix de produtos em que a margem 
de lucro varia de acordo com a quantidade vendida do produto, outro exemplo no dia a dia é problemas 
de transporte com custos variáveis que dependem da quantidade que vai ser enviada. 
Investidores preocupados com o retorno esperado e o risco associado a seus investimentos usam a 
programação linear para determinar uma carteira, sob certas hipótese, forneça uma relação ótima entre 
esses dois fatores. 
 
4. Em quais tipos de problemas deve-se analisar o Fluxo Máximo de uma rede? Cite exemplos. 
 
R: Um tipo de problema que é maximizar o fluxo de uma rede de distribuidora de uma empresa a 
partir de suas fabricas para os seus clientes. Outro exemplo pode ser maximizar o fluxo de óleo ou 
outro produto liquido ou gasoso através de um sistema de tubulações ou maximizar o fluxo de 
veículos através de uma rede de transporte. 
 
5. Resolva o Exemplo 1.1 da aula 8 (programação dinâmica) considerando que são usadas as seguintes 
rotas apresentadas na figura abaixo: 
 
 
R: 
 
Estágio 01 Estágio 02 Estágio 03 
 distância distância distância 
ponto 1 e 2 8 ponto 2 e 5 8+9 17 ponto 5 e 7 17+10 27 
ponto 1 e 3 12 ponto 3 e 5 12+7 19 ponto 6 e 7 23+7 30 
ponto 1 e 4 11 ponto 4 e 5 11+9 20 
ponto 3 e 6 12+11 23 
ponto 4 e6 11+14 25 
 
 
 
 
 
 
 
 
 
 5/6 
 
 
 
 
 
 
 
 
 
Baseado nos cálculos e desenho e a tabela a rota mais curta é 1 → 2 → 5 → 7. Que somam 27 milhas 
 
 
 
6. Formule um problema de programação não linear que caracterize uma função quadrática. 
 
 
 
 
 
 
 
7. Uma ferramentaria fabrica dois produtos. Cada unidade do primeiro produto requer 03 (três) horas 
na máquina 1 e 02 (duas) horas na máquina 2. Cada unidade do segundo produto requer 02 (duas) 
horas na máquina 1 e 03 (três) horas na máquina 2. A máquina 1 se encontra disponível somente 08 
(oito) horas por dia e a máquina 2 apenas 07 (sete) horas por dia. O lucro por unidade vendida é 16 
para o primeiro produto e 10 para o segundo. A quantidade de cada produto produzido por dia tem de 
ser um valor inteiro. O objetivo é determinar o mix de volume de produção que maximizará o lucro. 
 
(a) Formule um modelo de PI (Programação Inteira) para esse problema. 
R: 
 
 
Produto 1 = x1 
Produto 2 = x2 
 
 maquina 1 maquina 2 lucro 
Produto 1 3 horas 2 horas 16 
Produto 2 2 horas 3 horas 10 
Dispon. 8 horas 7 horas 
 
Max Z = 16x1+ 10x2 
 6/6 
 
 
3x1+2x2 ≤ 8 
2x1+ 3x2 ≤ 7 
 X1,X2 ≥ 0 e inteiros. 
 
 
Solução ótima apresenta x1 = 2,6667 e x2= 0 com Z = 42.667 
Resultado: x1= 2; x2=1 e Z=42 
8. Considere o problema de Programação Inteira a seguir 
 
Max Z = 2x1 + 3x2 
Sujeito a 
x1+ x2 ≤ 3 
x1 + 3x2 ≤ 6 
x1, x2 ≥ 0 
x1, x2 são inteiras 
 
a) Solucione este problema graficamente de forma relaxada; 
b) Use o algoritmo de ramificação e avaliação progressiva (Método B&B) para resolver este 
 problema de Programação inteira.