Blog

Pontifícia Universidade Católica do Paraná centro DE CIÊNCIAS EXATAS E TECNOLOGIA CURSO DE ENGENHARIA DE PRODUÇÃO MILENA CHANG CHAIN LISTAS DE EXERCÍCIOS 10 PROVA DE MÉTODOS HEURÍSTICOS E PROCESSOS DECISÓRIOS CURITIBA 2012 SUMÁRIO ILISTA13 1 PROBLEMAS DE 1. 1 problema 3 (p. 3 . 1. 1 Formulação . 12 Iterações utili orlo to view nut*ge 1. 1. 1. 3 software (LINGO) 5 1 1. 2 Problema 7 (p. 4)5 1. 2. 1 Formulação Matemática 6 . 1. 2. 2 Iterações utilizando o método SIMPLEX 6 1. 1. 2. 3 software (LINGO) 8 1. 2 PROBLEMAS DE TRANSPORTE8 12. 1 problema 3 (p. 7) 8 . 2. 1. 1 Formulação Matemática 8 1-2. 12 Iterações Utilizando Algoritmo de Transporte 9 I . 2. 1. 3 software (LINGO) 10 1. 2. 2 Problema g (p. 29) 11 1. 2. 2. 1 Formulação Matemática 11 1. 2. 2. 2 Iterações Utilizando Algoritmo de Transporte 1 1 1. 2. 2. 3 software (LINGO) 14 1. 3 PROBLEMAS DE dESIGNAÇÃO 15 Construa o seu modelo matemático; b) Faça duas Iterações manualmente utilizando o Algoritmo de Transportes; c) Resolva, determinando a solução ótima para o problema, utilizando algum software para problemas de Transporte (LINGO; QM ou outro). Escolha dois problemas de Designação da apostila e: a) Construa o seu modelo matemático; b) Resolva manualmente utilizando o Método Húngaro; utilizando algum software para problemas de Designação (LINGO; PROBLEMAS DE FORMULAÇÃO Problema 3 (p. 3) Um fabricante de ração para cães produz dois tipos de mistura, F e H. Duas matérias-primas, cereal e carne, são utilizadas. Considerando os dados a seguir, o fabricante quer achar a quantidade de cada produto que maximize seus lucros. O tipo F é uma mistura de 1 kg. de cereal e 1,5 kg. e carne e é vendido a 0 cents o pacote de 2,5 kg. O tipo H é uma mistura de 2 kg. de cereal e 1 kg. de carne e é vendido a 60 cents o pacote com 3 kg. O cereal custa 10 cents o kg. ; a carne custa 20 cents por kg. O tipo H custa 18 cents por pacote para empacotar e o tipo F custa 14 cents. No período de um mês a companhia tem disponível 240. 000 kg. de cereal e 180. 000 kg. de carne. O tipo F exige uma máquina especial para empacotamento, que pode empacotar no máximo 110. 000 unidades por mês. RECURSOS I RAÇÃOF RAÇÃOH I QTD. DISPO. I CEREAL IKG 2KG 2. 00 CARNEI 1,5KGI IKG 1. 800 MÁQUINA X 1 10. 000 PREÇO DE VENDA | 10 ração tipo F H=quantidade de pacotes de 3kg a produzir da ração tipo H Função Objetivo: Maximizar o lucro Max I F*2HQ. 400 I ,5F+1 . 800 FAIO. OOO Iterações utilizando o método SIMPLEX F+X5=110. OOO Software (LINGO) @gin(F); @gin(H); Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: otal solver iterations: Model Class: Varia 714. 0000 o. oooooo 2 PILP Reduced Cost pregos por hora, enquanto o segundo produz 4. 000 parafusos e 2. 00 pregos por hora, mas nenhuma porca. A indústria tem uma encomenda de 12. 000 porcas, 16. 000 parafusos e 15. 000 pregos. Durante quantas horas ela deve empregar cada método para fazer a entrega o mais rapidamente possível ? PORCAS PARAFUSOS I PREGOS MÉTODO II 3. 000 | 2. 000 | 2. 500 | IH I MÉTODO 21 4. 000 | 2. 000 | IH I DEMANDA | 12. 000 | 16. 000 15. 000 Formulação Matemática Variáveis: M 1= Quantidade de horas empregadas pelo método 1 M2- Quantidade de horas empregadas pelo método 2 Função Objetivo: Minimizar horas Min Z-M1+M2 3.

OOOMl+4. OOOM2>12. OOO 2. OOOM1 16. 000 2. 500M1>15. ooo Ml,M220 Min Z=M14M2 3. 000M1+4. OOOM2-F3-12. OOO 2. OOOMl OOOM2-F4=16. OOO 2. 500M1-F5=1S. OOO Min XO=A6+A7+A8 3. OOOM I OOOM2-F3+A6=12. OOO 2. 000M1+2. OOOM2-F4+A7-16. OOO 8. oooooo 3 4 1. 000000 12000. 00 5000,000 -O. 5000000E-03 PROBLEMAS DE TRANSPORTE problema 3 (P. 27) Um fabricante de artigos de plástico possui um estoque de 1. 200 caixas de invólucros transparentes em uma de suas fábricas e outras 1. 000 caixas em uma segunda fábrica.

O fabricante recebeu pedidos deste produto provenientes de três diferentes varejistas nas quantidades de 1. 000, 700 e 500 caixas, espectivamente. Os custos unitários de expedição (em reais por caixa) desde as fábricas até os varejistas são os seguintes: Min custo: 14×11+1 3×12+1 xl 1+x12+x13g1200 000 xl 1+01=1000 XI 2+X22=700 xl 3+03=500 Iterações Utilizando Algoritmo de Transporte software (LINGO) MIN-14*X11+13*X12+11 *XI X21 COO; X12 X22=700, XI 3+X23=500; nfeasibilities: 27600. 00 PAGFSOFIO 500. 0000 X21 X22 X23 1000. 00 1 . oooooo Problema 9 (p. 29) Considere o seguinte problema da Distribuidora BGLP, cujos custos de transporte das fábricas até os depósitos estão contidos no quadro a seguir: Min custo: 2Xl 1+6Xl 2+4Xl 3+12X14+7X21 IX24+5 E 1 13×34 X21+X22*X23+X24Q50 x31 +x32+x33+x34s300 xl 2+x22+x32-1 SO x 13+x23+x33=200 xl 4+x24+x34=250 MIN- 5*X31 X31 XI 1+X21 +31 XI 2+X22+X32=150; X13 X23 X33=200; XI 4+X24+X34=250; Global optimal solution fo PAGF 10 2. oooooo X24 X32 X33 X34 PROBLEMAS DE dESlGNAÇÃO problema 7 (P. 32) 150. 000 1 oo. oooo 0,000000 119. 0000 1 50. 0000 3. 000000 5. 000000 3,000000 Min custo: 13×11+22×12+19×13+21×14+18×21+17X22+24X23+18 X24+20X31 +19X42+13X43+30X44 x31 +x32+x33+x34-1 X41+X42+X43+X44=l XI +X41=1 XI 2+X22+X32+X42=l xl 3+x23+x33+x43=l l 4+x24+x34+x44= 1 XC 34 Iterações Utilizando Método Húngaro MIN= 20*X31 X21 , X31 +X32+X33+X34-1, X41 +X42+X43+X44-1 XII+X21+X31+X41= Total solver iterations: Variable XII XI 3 X14 X42 Value 0-000000 0. 000000 I . OOOOOO 13. 00000 22. 00000 19,00000 21 . ooooo 18. 00000 17. 0000 24. 00000 18. ooooo 20. 00000 23. 00000 2400000 14. 00000 1 g. ooooo 0. oooooo problema 9 (P. 33) 30. 00000 A Xan Consulting deseja determinar a melhor distribuição de trabalho para seus três principais consultores. O objetivo é obter a distribuição que estabeleça o menor tempo total para a xecução das tarefas. Os tempos que cada consultor levaria para cada tarefa são: Min Custo= 10×11+15×12+gx13+gx21+18×22+5×2 para cada tarefa são: Min Custo: 1 141 5×12*9x1349x21 +14×32*3×33 xl 1+x12+x13=1 X21+X22*X23-1 x? +x32+x33-1 XII+X21+X31 xl 2+x22+x32-1 XI 3+X23+X33=1 xeB3 Z min=27 XI 1+X12+X13=1; X21+X22+X23=1, X31 X32 X33=1, XII+X21+X31-1• XI 2+X22+X32-1; XI 3+X23+X33 @bin(xl 2); @bincx23),• @bincx32),• 3. oooooo Row 6 7 LISTA 2 PROBLEMA 4 Slack or Surplus Dual Price 27. 00000 -1 . oooooo Utilize o algoritmo de Floyd para determinar a mínima distância ntre todos os pares de nós, dada a matriz de custos inicial. 112 11012 21310 31214 41313 5315 314151 315 1417181 015 51 1510161 PROBLEMA 7 Dado o seguinte trecho da cidade de Curitiba, aplique o algoritmo de Floyd para os 6 pontos assinalados no mapa, determinando a mínima distância entre todos os pares de nós e os caminhos pelos quais estas distâncias podem ser alcançadas. PROBLEMA 10 Dada a rede a seguir, determine o minimo caminho entre todos os pares de nós através do algoritmo de Floyd. PROBLEMA 11 Dado o seguinte grafo, determine as mínimas distâncias entre todos os pares de nós.