ELIAB VARELA ATIVIDADE 2 doc

Prévia do material em texto

1/2
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. 
Temos uma conecção que o caminho mais proximo será 1-3,3-5,5-6,6-7
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. 
(b). Use o modelo formulado no item anterior para resolver esse problema do caminho mais curto e determine o caminho ótimo. 
Distancia mais curta parte de: Origem–A, A-B,B-D,D-destino
40+10+55+60 = 165 milhas.
c) Suponha que o Custo unitário por milha percorrida seja de R$ 17,00 qual é o valor do custo mínimo?
Custo mínimo = 165 milhas * R$ 17,00 = R$ 2.805,00
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.
Dois exemplos de que um engenheiro pode encontrar no seu dia a dia de trabalho são, mineração e rodovia. 
4. Em quais tipos de problemas deve-se analisar o Fluxo Máximo de uma rede? Cite exemplos. 
O fluxo máximo é utilizado quando deseja maximizar a quantidade de um fluxo de um ponto de origem para um ponto de destino e está sujeito a restrição de capacidade. Esse método está muito presente em situações que envolvem fluxos de água, óleo, gás, energia entre outros.
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: 
Estágio 1- Resumo:
Distância mais curta do nó 1 ao nó 2 = 8 milhas (a partir do nó 1).
Distância mais curta do nó 1 ao nó 3 = 12 milhas (a partir do nó 1).
Distância mais curta do nó 1 ao nó 4 = 11 milhas (a partir do nó 1).
Estágio 2- Resumo:
Distância mais curta do nó 1 ao nó 5 = 17 milhas (a partir do nó 2).
Distância mais curta do nó 1 ao nó 6 = 23 milhas (a partir do nó 3).
O resumo do estágio 3 mostra a distância mais curta do nó 1 ao nó 7 = 27 milhas (a partir do nó 5). Para determinar a rota ótima, o resumo do estágio 3 liga o nó 7 ao nó 5; o resumo do estágio
2 liga o nó 5 ao nó 2, e o resumo do estágio 1 liga o nó 2 ao nó 1.
A rota mais curta é 1 → 2 → 5 → 7.
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.
Modelo de PLI
Max Z = 16x1+ 10x2
Sujeito a 3x1+2x2 ≤ 8
2x1+ 3x2 ≤ 7
x1,x2 ≥ 0 e inteiros.
Problema relaxado
Max Z = 16x1+ 10x2
Sujeito a 3x1+2x2 ≤ 8
2x1+ 3x2 ≤ 7
x1,x2 ≥ 0
A primeira solução ótima apresenta x1 = 2,6667 e x2= 0 com Z = 42.667
Sendo assim o LSA é o valor máximo da função objetivo Z = 42,667 e o valor mínimo de z se dá no ponto x1= 0 e x2 = 2,3333 o que nos dá Z = 23,333 o que representa o LIA, a nossa solução está entre este intervalo. Sendo assim temos o seguinte intervalo como ponto inicial 23,333 ≤ valor ótimo da função objetivo ≥ 42.667
Subproblema 2
Max Z = 16x1+ 10x2
Sujeito a
3x1+2x2 ≤ 8
2x1+ 3x2 ≤ 7
x1 ≤ 2 (restrição adicionada ao problema relaxado)
x1,x2 ≥ 0
Subproblema 3
Max Z = 16x1+ 10x2
Sujeito a
3x1+2x2 ≤ 8
2x1+ 3x2 ≤ 7
x1 ≥ 3 (restrição adicionada ao problema relaxado)
x1,x2 ≥ 0
A solução ótima é Z = 42
O 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;
Teste dos Pontos no gráfico
b) Use o algoritmo de ramificação e avaliação progressiva (Método B&B) para resolver este
 problema de Programação inteira.
Z = 7 (LSA)
X1 = 2
X2 = 1
9. Formule um problema de caminho mais curto na forma de um problema de programação linear e apresente a sua rede. 
Um empresa deseja verificar a rota mais viável conforme a rede é composta por nós (cidades) representados por círculos de (Recife) ponto A até (Vitoria Santo Antão) ponto I, conforme suas distâncias indicadas nas setas, ligando os nós das 12 cidades. 
XAB = Recife (A) até Boa Vista (B); 
 XAC = Recife (A) até Bongi (C); 
 XAD = Recife (A) até Engenho do Meio (D);
 XBC = Boa Vista (B) até Bongi (C);
 XDC = Engenho do Meio (D) até Bongi (C);
 XCF = Bongi (C) até Curado (F);
 XCE = Curado (C) até Alto da colina (E);
 XFE = Curado (F) até Alto da Colina (E);
 XEG = Alto da Colina (E) até Santo Aleixo (G); 
XEH = Alto da Colina (E) até Moreno (H); 
XGH = Santo Aleixo (G) até Moreno (H); 
XHI = Moreno (H) até Vitoria Santo Antão (I).
MIN Z = 51XAB + 103XAC + 65XAD + 71Xbc + 85XDC + 86XCF + 53XCE + (1) 46XFE + 45XEG + 35XEH + 16XGH + 110XHI
Resultados apresentados no Excel
	Origem
	Destino
	Distancia em KM
	Rota
	A
	B
	51
	0
	A
	C
	103
	1
	A
	D
	65
	0
	B
	C
	71
	0
	D
	C
	85
	0
	C
	E
	53
	1
	C
	F
	86
	0
	F
	E
	46
	0
	E
	G
	45
	0
	E
	H
	35
	1
	G
	H
	16
	0
	H
	I
	110
	1
	
	
	
	
	
	Km total
	766
	
	Nós
	Fluxo 
	Demanda 
	A
	-1
	-1
	B
	0
	0
	C
	0
	0
	D
	0
	0
	E
	0
	0
	F
	0
	0
	G
	0
	0
	H
	0
	0
	I
	1
	1
Fluxo e demanda 
O objetivo e minimizar a distância total da rota foi atendido, obtendo a solução ótima para o problema do caminho mais curto. O menor caminho encontrado é representado no fluxo abaixo
PONTOCOORDENADA X (X1)COORDENADA Y (X2)VALOR DA FUNÇÃO (Z)
O000
A039
B306
C1,51,57,5
D026
E6012