Avaliacao APX2 Pesquisa Operacional II - Otimizacao em Redes e Celulas de Producao

Avaliação APX2 Curso de Engenharia de Produção EaD CEDERJ Disciplina Pesquisa Operacional II Professor Ormeu Coelho da Silva Júnior INSTRUÇÕES GERAIS A memória de cálculo de todas as questões deve ser apresentada A prova deve ser feita à mão e escaneada para entrega Detalhes da entrega foram repassados pelo mediador da disciplina na plataforma O compartilhamento de questões entre alunos será considerado COLA Questão 1 4pts O suprimento de ração para quatro granjas é transportado por caminhões a partir de três silos Restrições de ordem logística impedem que alguns silos abasteçam determinadas granjas assim como impõe limites de capacidade para a quantidade a ser transportada em cada rota direta entre silos e granjas uma vez que há uma quantidade limitada de caminhões e viagens disponíveis Os dados de demanda capacidade de fornecimento e capacidade de transporte para o próximo mês são mostrados na tabela abaixo Granja 1 Granja 2 Granja 3 Granja 4 Capacidade dos Silos ton Silo 1 30 5 0 40 20 Silo 2 0 0 5 90 20 Silo 3 100 40 30 40 240 Demanda das granjas ton 200 10 60 20 a Determine as quantidades que devem ser enviadas entre silos e granjas de modo a atender a maior demanda possível Para isso empregue seus conhecimentos de Otimização em Redes apresentando a rede que será usada para representar o problema e em seguida empregue um algoritmo apropriado b Alguma granja não terá sua demanda integralmente atendida Justifique sua resposta Questão 2 3pts Uma empresa de manufatura deseja formar células de produção reunindo em uma mesma célula máquinas similares A medida de dissimilaridade empregada é dada pelo índice 𝑑𝑖𝑗 definido como 𝑑𝑖𝑗 1 𝑛𝑖𝑗 𝑛𝑖𝑗 𝑚𝑖𝑗 onde 𝑛𝑖𝑗 é o número de produtos processados na máquina 𝑖 e também na máquina 𝑗 𝑚𝑖𝑗 é o número de produtos processados na máquina 𝑖 ou na máquina 𝑗 mas não em ambas Há 10 máquinas nas quais são processados 15 produtos A tabela abaixo lista os produtos processados em cada máquina Máquina Produtos 1 1 6 2 2 3 7 8 9 12 13 15 3 3 5 10 14 4 2 7 8 11 12 13 5 3 5 10 11 14 6 1 4 5 9 10 7 2 5 7 8 9 10 8 3 4 15 9 4 10 10 3 8 10 14 15 A empresa considera formar 3 ou 4 células de produção Para isso pedese a Represente o problema como uma rede não orientada onde as máquinas são vértices e os custos associados às arestas são os índices de dissimilaridade b Encontre as soluções desejadas usando para isso a árvore geradora de peso mínimo da rede desenhada no item a Questão 3 3pts Uma empresa produz um item em duas fábricas 1 e 2 O custo unitário de produção e a capacidade de produção durante cada período de tempo são apresentados na Tabela1 Após a produção o item é imediatamente enviado ao único cliente da empresa assuma que o tempo em trânsito é desprezível face à duração do período de tempo de acordo com os custos unitários de envio fornecidos na Tabela2 ou é armazenado para ser enviado no próximo período Mas no segundo caso existe um custo de manutenção de R1300 por unidade estocada Além disso no máximo seis unidades podem ser mantidas em estoque As demandas são as seguintes período 1 9 itens período 2 11 itens Formule um Problema de Fluxo de Custo Mínimo a ser usado para minimizar o custo de atender a todas as demandas no prazo Antes de escrever a formulação matemática desenhe a rede que representa o problema Tabela 1 Custos e Capacidades de Produção Planta Período Custo de Produção Runidade Capacidade unidades Planta 1 período 1 33 7 Planta 1 período 2 43 4 Planta 2 período 1 30 9 Planta 2 período 2 41 9 Tabela 2 Custos de envio entre plantas e consumidores Runidade Planta Período Período 1 Período 2 Planta 1 p consumidor 51 60 Planta 2 p consumidor 42 71 DICA Primeiro construa uma rede em que os vértices sejam dados pelos pares plantaperíodo e cliente período Na sequência faça as transformações necessárias para obter uma rede equivalente que atenda às premissas do Problema de Fluxo de Custo Mínimo Resolução Questão 1 Letra A O fluxo máximo nesta rede corresponde à maior quantidade de ração que pode ser enviada entre silos e granjas Para determinálo aplicase o algoritmo de FordFulkerson Para simplicar a notação os vértices foram reindexados conforme indicado na tabela abaixo Tabela de Indexação Índice Vértice 1 O 2 S1 3 S2 4 S3 5 G1 6 G2 7 G3 8 G4 9 D 1ª Iteração Considere a solução inicial 𝑥 0 e grafo auxiliar abaixo ilustrado A primeira cadeia enumerada neste grafo é 𝐶 14 45 59 ao longo da qual se pode aumentar o fluxo em Δ𝑓 min240100200 100 unidades Com isso 𝑓 𝑓 Δ𝑓 0 100 100 𝑥14 0 100 100 𝑥45 0 100 100 𝑥59 0 100 100 E as capacidades residuais ficam 𝑣14 240 100 140 𝑣14 100 0 100 𝑣45 100 100 0 𝑣45 100 0 100 𝑣59 200 100 100 𝑣59 100 0 100 2ª Iteração A próxima cadeia enumerada é 𝐶 14 46 69 ao longo da qual se pode aumentar o fluxo em Δ𝑓 min1404010 10 unidades Com isso 𝑓 𝑓 Δ𝑓 100 10 110 𝑥14 100 10 110 𝑥46 0 10 10 𝑥69 0 10 10 As capacidades residuais são 𝑣14 140 10 130 𝑣14 110 0 110 𝑣46 40 10 30 𝑣46 10 0 10 𝑣69 10 10 0 𝑣69 10 0 10 3ª Iteração A próxima cadeia enumerada é 𝐶 14 47 79 ao longo da qual se pode aumentar o fluxo em Δ𝑓 min1303060 30 unidades Com isso 𝑓 𝑓 Δ𝑓 110 30 140 𝑥14 110 30 140 𝑥47 0 30 30 𝑥79 0 30 30 Com as capacidades residuais 𝑣14 130 30 100 𝑣14 140 0 140 𝑣47 30 30 0 𝑣47 30 0 30 𝑣79 60 30 30 𝑣79 30 0 30 4ª Iteração A próxima cadeia enumerada é 𝐶 14 48 89 ao longo da qual se pode aumentar o fluxo em Δ𝑓 min1004020 20 unidades Com isso 𝑓 𝑓 Δ𝑓 140 20 160 𝑥14 140 20 160 𝑥48 0 20 20 𝑥89 0 20 20 Com as capacidades residuais 𝑣14 100 20 80 𝑣14 160 0 160 𝑣48 40 20 20 𝑣48 20 0 20 𝑣89 20 20 0 𝑣89 20 0 20 5ª Iteração A próxima cadeia enumerada é 𝐶 13 37 79 ao longo da qual se pode aumentar o fluxo em Δ𝑓 min20530 5 unidades Com isso 𝑓 𝑓 Δ𝑓 160 5 165 𝑥13 0 5 5 𝑥37 0 5 5 𝑥79 0 5 5 Com as capacidades residuais 𝑣13 20 5 15 𝑣13 5 0 5 𝑣37 5 5 0 𝑣37 5 0 5 𝑣79 30 5 25 𝑣89 35 0 35 5ª Iteração A próxima cadeia enumerada é 𝐶 12 25 59 ao longo da qual se pode aumentar o fluxo em Δ𝑓 min2030100 20 unidades Com isso 𝑓 𝑓 Δ𝑓 165 20 185 𝑥12 0 20 20 𝑥25 0 20 20 𝑥79 100 20 120 Com as capacidades residuais 𝑣12 20 20 0 𝑣12 20 0 20 𝑣25 30 20 10 𝑣25 20 0 20 𝑣59 100 20 80 𝑣59 120 0 120 6ª Iteração Como se vê na rede abaixo não há caminhos para o aumento do fluxo entre os vértices 1 e 9 pois as capacidades residuais dos arcos 12 37 69 e 89 são nulas indicando que estes arcos foram saturados O algoritmo então termina com o fluxo ótimo de 𝑓 185 unidades E os fluxos na solução ótima são ilustrados na figura abaixo A otimalidade desta solução também pode ser verificada através da corte de capacidade mínima entre os vértices OD ilustrada figura seguinte Observe que é nula a capacidade residual dos arcos que saem do subconjunto que contém o vértice 1 fonte O em direção ao subconjunto que contém o vértice 9 sumidoro D Este conjunto de arcos é 123745476989cuja soma das capacidades é 185 Como se sabe a capacidade do corte mínimo é igual ao valor do fluxo ótimo Logo a solução obtida é ótima Letra B Sim Os fluxos que saem dos vértices que representam as granjas definem o máximo fluxo que foi possível entregar a cada uma delas Note que não há caminhos no grafo de aumento de fluxo da iteração final entre os vértices 1 fonte O e 9 sumidouro D que passem pelos vértices 5 6 7 e 8 Questão 2 Letra A A rede usada na modelagem do problema é um grafo completo isto é há uma aresta entre cada par de vértices valorado onde cada vértice representa uma máquina e cada aresta representa a decisão de colocar duas máquinas adjacentes na mesma célula de manufatura O valor 𝑑𝑖𝑗 de uma aresta 𝑖 𝑗 define o índice de dissimilaridade entre as máquinas 𝑖 e 𝑗 Como o número de arestas em um grafo completo é igual a 𝑛 𝑛 1 2 seria necessário desenhar 45 ligações com seus respectivos valores o que certamente é desnecessário uma vez que já conhecemos a estrutura do grafo Os índices de dissimilaridades entre todos os pares de vértices são apresentados na matriz abaixo Matriz de dissimilaridades 𝑑𝑖𝑗 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 56 1 1 1 1 2 1011 49 1112 1112 35 79 1 710 3 1 15 57 34 56 45 12 4 910 1 23 1 1 910 5 34 79 67 56 47 6 58 67 35 89 7 34 67 79 8 34 23 9 56 10 Letra B Inicialmente vamos determinar uma Árvore Geradora de Peso Mínimo neste grafo através do algoritmo de Prim Esta árvore produzirá uma única célula de produção Passo 1 LST 0 C 1 C 2 3 4 5 6 7 8 9 10 ST 0 Passo 2 LST 56 C 1 6 C 2 3 4 5 7 8 9 10 ST 16 LST 4330 C 1 6 9 C 2 3 4 5 7 8 10 ST 16 69 LST 247120 C 1 6 7 9 C 2 3 4 5 8 10 ST 16 69 67 LST 319120 C 1 2 6 7 9 C 3 4 5 8 10 ST 16 69 67 27 LST 1117360 C 1 2 4 6 7 9 C 3 5 8 10 ST 16 69 67 27 24 LST 1369360 C 1 2 4 6 7 9 10 C 3 5 8 ST 16 69 67 27 24 210 LST 1549360 C 1 2 3 4 6 7 9 10 C 5 8 ST 16 69 67 27 24 210 310 LST 1621360 C 1 2 3 4 5 6 7 9 10 C 8 ST 16 69 67 27 24 210 310 35 LST 1861360 C 1 2 3 4 5 6 7 8 9 10 C ST 16 69 67 27 24 210 310 35 810 A árvore geradora de peso mínimo obtida pela aplicação do algoritmo é ilustrada a seguir Para produzir células a partir desta árvore as arestas serão removidas uma vez que isso desconecta a estrutura Mais precisamente será removida em primeiro lugar a aresta de maior custo isto é 16 Com isso temse agora duas árvores uma formada apenas pelo vértice 1 e outra com todos os demais Com a remoção da segunda aresta de maior valor 210 passamos a ter três árvores dadas pelos seguintes conjuntos de vértices e arestas 𝑉1 1 e 𝑇1 𝑉2 35810 e 𝑇2 35 310 810 𝑉3 24679 e 𝑇3 24 27 67 69 As três células assim formadas são apresentadas abaixo A solução que se obtém pela remoção da terceira aresta com maior peso 38 consiste nas seguintes árvores 𝑉1 1 e 𝑇1 𝑉2 3510 e 𝑇2 35 310 𝑉3 8 e 𝑇3 𝑉4 2467 e 𝑇4 24 27 67 69 Questão 3 A modelagem deste problema de planejamento da produção como um Problema de Fluxo de Custo Mínimo usa os vértices indicados na tabela abaixo Os valores associados a cada vértice são as capacidades das fábricas e as demandas nos dois períodos considerados Como há excesso de oferta na rede é preciso inserir um vértice artificial que atuará como sumidouro recebendo o excedente de fluxo Tabela de Indexação Índice Vértice Oferta Demanda 1 Sumidouro vértice artificial 9 2 Fábrica 1 Período 1 7 3 Fábrica 1 Período 2 4 4 Fábrica 2 Período 1 9 5 Fábrica 2 Período 2 9 6 Demanda Período 1 9 7 Demanda Período 2 11 A rede do problema então fica Conjuntos 𝑉 conjunto de vértices 𝐼 1234567 𝐴 conjunto de arcos 𝐴 21 26 27 31 37 41 46 47 51 57 𝐺 𝑉 𝐴 Variáveis de Decisão 𝑥𝑖𝑗 fluxo no arco 𝑖 𝑗 tal que 𝑖 𝑗 𝐴 Função Objetivo Atender à demanda total a um custo mínimo na rede min 𝑧 84𝑥26 106𝑥27 103𝑥37 72𝑥46 114𝑥47 112𝑥57 Restrições R1 Conservação de fluxo em cada vértice i soma das saídas menos a soma das entradas 𝑥21 𝑥31 𝑥41 𝑥51 9 vértice 1 𝑥21 𝑥26 𝑥27 7 vértice 2 𝑥31 𝑥37 4 vértice 3 𝑥41 𝑥46 𝑥47 9 vértice 4 𝑥51 𝑥57 9 vértice 5 𝑥26 𝑥46 9 vértice 6 𝑥27 𝑥37 𝑥47 𝑥57 11 vértice 7 R2 Limite superior para os fluxos que representam estoque para o período 2 𝑥27 6 vértice 2 vértice 7 𝑥47 6 vértice 4 vértice 7 R3 Declaração das variáveis de decisão 𝑥𝑖𝑗 0 𝑖 𝑗 𝐴 Avaliação AP2 Curso de Engenharia de Produção EaD CEDERJ Disciplina Pesquisa Operacional II Professor Ormeu Coelho da Silva Júnior Questão 1 4pts Um fabricante de eletroeletrônicos precisa planejar a reposição de um equipamento Sabese que seus custos com operação e manutenção aumentam significativamente com o tempo de modo que pode valer mais a pena vendêlo pelo valor residual e comprar um novo A tabela abaixo apresenta o custo 103R esperado de se comprar um equipamento no final do ano i e vendelo no final do ano j já descontado o valor residual j i 1 2 3 4 0 160 270 400 540 1 180 290 420 2 190 310 3 195 Represente e resolva este problema como um Problema de Caminho Mínimo Questão 2 3pts A administração de uma reserva ecológica precisa planejar um conjunto de estradas de acesso a sítios de interesse Estes sítios e as distâncias em milhas entre eles e a entrada da reserva no vértice A através de possíveis ligações viárias estão indicados no grafo abaixo Para minimizar os danos ao meio ambiente desejase minimizar o comprimento total das estradas necessárias para prover a acessibilidade desejada Encontre a solução ótima para este problema através de algum algoritmo válido Questão 3 3pts Uma estação de tratamento de esgoto precisa determinar sua máxima capacidade de tratamento em termos da vazão 103 m3s A rede abaixo ilustrada apresenta as conexões existentes entre o ponto de recebimento dos efluentes vértice A os tanques de tratamento vértices D a E e o ponto de despejo da água tratada vértice F Os arcos indicam as possíveis conexões e seus valores as capacidades em 103 m3s a Determine por inspeção o corte de menor capacidade nesta rede Feito isso podese dizer qual o valor do fluxo máximo entre A e F ou pelo menos estabelecer um limite superior para ele b Empregue o algoritmo de FordFulkerson para determinar os fluxos em cada arco que maximizem a quantidade de esgoto tratada Resolução Questão 1 Solução pelo método em tabelas 1 Iteração 1 Nó dj pj Status 0 0 Rotulado 1 0160 0 1600 Não Rotulado 2 0270 0 2700 Não Rotulado 3 0400 0 400 0 Não Rotulado 4 0540 0 540 0 Não Rotulado Iteração 2 Nó Rótulo Status 0 0 Rotulado 1 1600 Rotulado 2 2700 ou 160180 1 340 1 Não Rotulado 3 400 0 ou 160290 1 450 1 Não Rotulado 4 540 0 ou 160420 1 580 1 Não Rotulado Iteração 3 Nó Rótulo Status 0 0 Rotulado 1 1600 Rotulado 2 2700 Rotulado 3 400 0 ou 270190 2 460 2 Não Rotulado 4 540 0 ou 270310 2 580 2 Não Rotulado Iteração 4 Nó Rótulo Status 0 0 Rotulado 1 1600 Rotulado 2 2700 Rotulado 3 400 0 Rotulado 4 540 0 ou 400195 3 595 3 Não Rotulado Iteração 5 Nó Rótulo Status 0 0 Rotulado 1 1600 Rotulado 2 2700 Rotulado 3 400 0 Rotulado 4 540 0 Rotulado Uma vez que o nó de destino 𝑠4 foi rotulado o algoritmo para retornando o caminho ótimo 04 de custo igual a 540 Logo a política de reposição ótima consiste em comprar o equipamento no final do ano 0 início do ano 1 e vendêlo apenas no final do horizonte de planejamento isto é no final do ano 4 Solução pelo método em tabelas 2 0 1 2 3 4 k0 0 k1 1600 2700 4000 5400 k2 3401 4501 5801 k3 4602 5802 k4 5953 k5 Uma vez que o nó de destino 𝑠4 foi rotulado o algoritmo para retornando o caminho ótimo 04 de custo igual a 540 Solução pelo método em pseudocódigo Passo 1 R 0 NR 1 2 3 4 d0 0 p0 0 d1 d2 d3 d4 p1 7 p2 7 p3 7 p4 7 ultimo 0 Passo 2 k1 d1 min 160 160 p1 0 d2 min 270 270 p2 0 d3 min 400 400 p3 0 d4 min 540 540 p3 0 NR 2 3 4 R 0 1 d1 160 p1 0 ultimo 1 Passo 3 Nodo 4 não rotulado Retorne ao Passo 2 Passo 2 k2 d2 min270 310 270 d3 min400 450 400 d4 min540 580 540 NR 3 4 R 0 1 2 d2 270 p2 0 ultimo 2 Passo 3 Nodo 4 não rotulado Retorne ao Passo 2 Passo 2 k3 d3 min400 460 400 d4 min540 580 540 NR 4 R 0 1 2 3 d3 360 p3 2 ultimo 3 Passo 3 Nodo 4 não rotulado Retorne ao Passo 2 Passo 2 k4 d4 min540 595 540 NR R 0 1 2 3 4 d4 540 p4 0 ultimo 0 Passo 3 Nodo 4 rotulado Recuperando o caminho ótimo p4 0 O caminho mínimo do nó 0 ao nó 4 e dado por C 04 cujo valor é 540 Questão 2 Passo 1 LST 0 C A C B C E F G H ST Passo 2 LST 2 C A D C B C E F G H ST AD LST 5 C A B D C C E F G H ST AD AB LST 9 C A B D E C C F G H ST AD AB BE LST 10 C A B C D E C F G H ST AD AB BE EC LST 16 C A B C D E G C F H ST AD AB BE EC BG LST 19 C A B C D E G H C F ST AD AB BE EC BG GH LST 26 C A B C D E F G H C ST AD AB BE EC BG GH CF O conjunto de estradas que minimiza o custo de conexão destes sítios geológicos é dado pelas ligações indicadas na rede abaixo ilustrada cujo peso é 26km Questão 3 Questão Anulada Avaliação AP2 Curso de Engenharia de Produção EaD CEDERJ Disciplina Pesquisa Operacional II Professor Ormeu Coelho da Silva Júnior Questão 1 4pts A distribuição de gás natural veicular em uma cidade requer a construção de uma rede de dutos capaz de levar o produto de uma central de abastecimento até os postos de venda A figura abaixo ilustra as ligações que podem ser feitas para construção da rede A central está localizada no vértice a sendo os demais vértices pontos de consumo Os valores nas arestas representam o comprimento em 100m das respectivas ligações a Projete uma rede para transportar o gás entre a central e os pontos de consumo a custo mínimo b Sabese que a queda de pressão nestas redes diminui com o aumento da distância entre os pontos de envio e consumo Caso a rede fosse projetada evitar a queda de pressão como você modelaria o problema Como um Problema de Árvore Geradora de Peso Mínimo ou como um Problema de Caminhos Mínimos a partir de uma mesma origem e diversos destinos Justifique sua resposta Questão 2 3pts Considere a matriz abaixo que apresenta os valores dos comprimentos das arestas entre vértices de uma rede logística Para De 1 2 3 4 5 1 0 5 2 2 7 0 6 2 5 3 0 3 12 4 8 0 5 5 20 6 0 Aplicouse o algoritmo de Floyd para determinar os caminhos mínimos entre todos os pares de vértices desta rede obtendose as seguintes matrizes de distâncias mínimas e roteamento D5 1 2 3 4 5 1 0 5 2 5 10 2 7 0 6 2 5 3 18 11 0 3 8 4 15 8 14 0 5 5 20 14 20 6 0 P5 1 2 3 4 5 1 1 1 1 3 2 2 2 2 2 2 2 3 2 4 3 3 4 4 2 4 2 4 4 5 5 4 2 5 5 a Represente a rede deste problema b Execute as duas primeiras iterações do algoritmo de Floyd apresentado as matrizes D e P correspondentes c A partir dos resultados do algoritmo de Floyd represente a árvore de caminhos mínimos que tem o vértice 4 como origem Questão 3 3pts Uma estação de tratamento de esgoto precisa determinar sua máxima capacidade de tratamento em termos da vazão em 103 m3s A rede abaixo ilustrada apresenta as conexões existentes entre o ponto de recebimento dos efluentes vértice A os tanques de tratamento vértices D a E e o ponto de despejo da água tratada vértice F Os arcos indicam as possíveis conexões e seus valores as capacidades em 103 m3s a Determine por inspeção o corte de menor capacidade nesta rede A partir dele podese dizer qual o valor do fluxo máximo ou pelo menos estabelecer um limite superior para ele b Empregue o algoritmo de FordFulkerson para determinar os fluxos em cada arco que maximizam a quantidade de esgoto tratada O USO DAS TABELAS ABAIXO PARA APRESENTAR A RESPOSTA DA QUESTÃO 2b É OBRIGATÓRIO A MEMÓRIA DE CÁLCULO DEVE SER APRESENTADA EM SEPARADO D1 1 2 3 4 5 1 2 3 4 5 P1 1 2 3 4 5 1 2 3 4 5 D2 1 2 3 4 5 1 2 3 4 5 P2 1 2 3 4 5 1 2 3 4 5 6 Resolução Questão 1 Letra a Passo 1 LST 0 C a C ST Passo 2 LST 10 C a c C b d e f g h i j k l ST ac LST 11 C a c e C b d f g h i j k l ST ac ce LST 13 C a b c e C d f g h i j k l ST ac ce eb LST 17 C a b c e k C d f g h i j l ST ac ce eb ek LST 23 C a b c e i k C d f g h j l ST ac ce eb ek ki LST 28 C a b c e i j k C d f g h l ST ac ce eb ek ki ij LST 36 C a b c e f i j k C d g h l ST ac ce eb ek ki ij kf LST 39 C a b c e f g i j k C d h l ST ac ce eb ek ki ij kf fg LST 50 C a b c e f g i j k l C d h ST ac ce eb ek ki ij kf fg kl LST 63 C a b c d e f g i j k l C h ST ac ce eb ek ki ij kf fg kl bd LST 81 C a b c d e f g h i j k l C ST ac ce eb ek ki ij kf fg kl bd gh Custo Total 81 Letra b Como problema de Árvore de caminhos mínimos Ao modelarmos o problema como problema de caminho mínimo Árvore de caminhos mínimos temos as menores distâncias entre o ponto de envio e todos os demais vértices reduzindo assim a queda de pressão na rede Questão 2 Letra a Letra b D1 1 2 3 4 5 1 0 5 2 2 7 0 6 2 5 3 0 3 12 4 8 0 5 5 20 25 22 6 0 P1 1 2 3 4 5 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 5 5 1 1 5 5 1 2 3 4 5 5 2 7 6 6 5 2 3 12 8 5 20 12 6 D2 1 2 3 4 5 1 0 5 2 7 10 2 7 0 6 2 5 3 0 3 12 4 15 8 14 0 5 5 20 25 22 6 0 P2 1 2 3 4 5 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 4 2 4 2 4 4 5 5 1 1 5 5 Letra c 1 2 3 4 5 7 6 6 8 5 Avaliação AP2 Curso de Engenharia de Produção EaD CEDERJ Disciplina Pesquisa Operacional II Professor Ormeu Coelho da Silva Júnior INSTRUÇÕES GERAIS É permitido o uso de calculadora Questão 1 3pts Uma empresa de exploração de petróleo precisa escoar sua produção diária do ponto de produção em so para o ponto de embarque em si Para isso dispõe de quatro estações de bombeamento através das quais o óleo pode ser enviado A rede abaixo ilustra os oleodutos existentes entre o ponto de produção o ponto de embarque e as estações assim como as capacidades de bombeamento em milhares de barris dia em cada oleoduto a Escreva uma formulação de programação linear para maximizar o fluxo de óleo escoado de so para si b Determine o valor do fluxo máximo entre sosi Justifique sua resposta OBS Não é necessário que se resolva um algoritmo de determinação do fluxo máximo podendo a resposta ser obtida por inspeção Questão 2 4pts Um fornecedor de alimentos localizado em Osasco entrega salgados e doces para uma padaria localizada na região da Vila Formosa em São Paulo Para isso o motorista pode percorrer mais de um caminho passando por diferentes bairros em São Paulo A figura abaixo apresenta os possíveis caminhos que o veículo pode percorrer do nó de oferta Osasco para o nó de demanda Vila Formosa além das distâncias em quilômetros entre os nós ou bairros a Encontre a rota ótima entre Osasco e Vila Formosa b Se a ligação entre Mooca e Vila Formosa estiver temporariamente indisponível isso afetará a rota calculada em a Se sim diga qual a nova rota ótima justificando sua resposta e apresentando novos cálculos se estes forem necessários Questão 3 3pts Use o Método da Seção Áurea para determinar dentro de um intervalo de 06 a solução ótima para max 𝑧 𝑥 𝑒𝑥 s a 1 𝑥 3 Resolução Questão 1 Letra A Conjuntos 𝑉 conjunto de vértices 𝐼 𝑠𝑜 1234 𝑠𝑖 𝐴 conjunto de arcos 𝐴 𝑠𝑜 1 𝑠𝑜 2 12 13 24 32 43 3 𝑠𝑖 4 𝑠𝑖 𝑠𝑖 𝑠𝑜 Variáveis de Decisão 𝑥𝑖𝑗 fluxo no arco 𝑖 𝑗 𝑖 𝑗 𝐴 Função Objetivo Maximizar o fluxo total na rede max 𝑧 𝑥𝑠𝑖𝑠𝑜 Restrições R1 Conservação de fluxo em cada vértice i 𝑥𝑠𝑜1 𝑥𝑠𝑜2 𝑥𝑠𝑖𝑠𝑜 0 vértice so 𝑥12 𝑥13 𝑥𝑠𝑜1 0 vértice 1 𝑥24 𝑥𝑠𝑜2 𝑥12 𝑥32 0 vértice 2 𝑥32 𝑥3𝑠𝑖 𝑥13 𝑥43 0 vértice 3 𝑥43 𝑥4𝑠𝑖 𝑥24 0 vértice 4 𝑥𝑠𝑖𝑠𝑜 𝑥3𝑠𝑖 𝑥4𝑠𝑖 0 vértice si R2 Vazões mínimas e máximas em cada arco 𝑖 𝑗 0 𝑥𝑠𝑜1 7 0 𝑥𝑠𝑜2 3 0 𝑥12 1 0 𝑥13 6 0 𝑥24 8 0 𝑥32 3 0 𝑥3𝑠𝑖 2 0 𝑥43 2 0 𝑥4𝑠𝑖 8 𝑥𝑠𝑖𝑠𝑜 0 R3 Declaração de variáveis 𝑥𝑖𝑗 0 𝑖 𝑗 𝐴 Letra B Por inspeção verificase que a capacidade do corte sosi mínimo é 9 sendo este corte definido pelos arcos so2 12 32 e 3si cujas capacidades são respectivamente 3 1 3 e 2 Portanto o fluxo máximo nesta rede vale 9 unidades Questão 2 Letra A Solução pelo método em tabelas ou gráfico 1 Iteração 1 Nó dj pj Status 1 0 Rotulado 2 011 1 11 1 Não Rotulado 3 09 1 9 1 Não Rotulado Iteração 2 Nó Rótulo Status 1 0 Rotulado 2 11 1 Não Rotulado 3 9 1 Rotulado 4 98 3 17 3 Não Rotulado 5 96 3 15 3 Não Rotulado Iteração 3 Nó Rótulo Status 1 0 Rotulado 2 11 1 Rotulado 3 9 1 Rotulado 4 17 3 ou 114 2 15 2 Não Rotulado 5 15 3 ou 118 2 19 2 Não Rotulado Iteração 4 Nó Rótulo Status 1 0 Rotulado 2 11 1 Rotulado 3 9 1 Rotulado 4 15 2 Rotulado 5 15 3 Não Rotulado 6 156 4 21 4 Não Rotulado 7 155 4 20 4 Não Rotulado Iteração 5 Nó Rótulo Status 1 0 Rotulado 2 11 1 Rotulado 3 9 1 Rotulado 4 15 2 Rotulado 5 15 3 Rotulado 6 156 4 21 4 Não Rotulado 7 155 4 21 5 20 4 Não Rotulado 8 154 5 19 5 Não Rotulado Iteração 6 Nó Rótulo Status 1 0 Rotulado 2 11 1 Rotulado 3 9 1 Rotulado 4 15 2 Rotulado 5 15 3 Rotulado 6 21 4 Não Rotulado 7 20 4 Não Rotulado 8 19 5 Rotulado 9 196 8 25 8 Não Rotulado Iteração 7 Nó Rótulo Status 1 0 Rotulado 2 11 1 Rotulado 3 9 1 Rotulado 4 15 2 Rotulado 5 15 3 Rotulado 6 21 4 Não Rotulado 7 20 4 Rotulado 8 19 5 Rotulado 9 25 8 204 7 24 7 Não Rotulado Iteração 8 Nó Rótulo Status 1 0 Rotulado 2 11 1 Rotulado 3 9 1 Rotulado 4 15 2 Rotulado 5 15 3 Rotulado 6 21 4 Rotulado 7 20 4 Rotulado 8 19 5 Rotulado 9 27 6 24 7 Não Rotulado Iteração 9 Nó Rótulo Status 1 0 Rotulado 2 11 1 Rotulado 3 9 1 Rotulado 4 15 2 Rotulado 5 15 3 Rotulado 6 21 4 Rotulado 7 20 4 Rotulado 8 19 5 Rotulado 9 24 7 Rotulado Uma vez que o nó de destino 𝑠9 foi rotulado o algoritmo para retornando o caminho ótimo 12 244779 de custo igual a 24 Solução pelo método em tabelas 2 1 2 3 4 5 6 7 8 9 k0 0 k1 111 91 k2 111 173 153 k3 152 192 k4 153 214 204 k5 214 215 195 k6 214 204 258 k7 214 247 k8 276 k9 Uma vez que o nó de destino 𝑠9 foi rotulado o algoritmo para retornando o caminho ótimo 12 244779 de custo igual a 24 Letra B Sim uma vez que a ligação entre Mooca e Vila Formosa pertence ao caminho mínimo calculado e esta estiver temporariamente indisponível isso afetará a rota calculada em a No grafo original qualquer caminho entre 1 e 9 passa necessariamente pelos vértices 6 7 ou 8 isto é Belém Mooca ou Ipiranga Logo estando o arco 79 indisponível será preciso usar o caminho mínimo que passa por 6 ou 8 Não é preciso fazer novos cálculos para determinar o novo caminho mínimo entre 1 e 9 pois é possível resgatar os caminhos mínimos entre 1 e 6 e entre 1 e 8 a partir da memória de cálculo da letra a Como todos os vértices foram rotulados com o algoritmo de Dijkstra os caminhos mínimos de 1 para qualquer vértice da rede são conhecidos Concluise assim que o novo caminho mínimo passará pelo vértice 8 e terá o comprimento igual a 25km ou seja d8 c89 19 6 Questão 3 Questão cancelada Avaliação AP2 Curso de Engenharia de Produção EaD CEDERJ Disciplina Pesquisa Operacional II Professor Ormeu Coelho da Silva Júnior Questão 1 4pts Uma empresa localizada em El Cajon precisa distribuir mercadorias para clientes em sete outras cidades O grafo abaixo esboça as ligações rodoviárias entre as cidades envolvidas Identifique as rotas de comprimento mínimo entre o armazém e os clientes considerando que os carregamentos são feitos em veículos com carga cheia Por fim diga qual será a distância rodoviária percorrida por sua frota para atender todos os clientes considere que no planejamento em questão um embarque será realizado para cada cliente Questão 2 3pts Em transporte intermodal caminhõesreboque carregados são despachados entre terminais ferroviários sobre vagões plataforma especiais A figura abaixo mostra a localização dos principais terminais ferroviários nos Estados Unidos EUA e as ferroviais existentes O objetivo é definir quais ferrovias devem ser revitalizadas para enfrentar o trafego intermodal Em particular o terminal de Los Angeles LA deve ser conectado diretamente ao de Chicago para dar conta do esperado tráfego pesado Fora estes dois todos os terminais restantes podem ser conectados direta ou indiretamente de modo que o comprimento total das vias selecionadas seja minimizado Determine os trechos das ferrovias que devem ser incluídos no programa de revitalização assim como o comprimento total de rede a ser revitalizado Questão 3 3pts A empresa Petroduto transporta óleo gás natural biocombustíveis renováveis dentre outros produtos por meio de uma malha de dutos de 1000 quilômetros A empresa busca determinar o fluxo máximo de óleo em m3s que pode ser transportado na rede abaixo ilustrada que tem como nó de origem O a estação de Minas e como nó de destino T um consumidor final localizado em São Paulo Os valores nos arcos representam as capacidades máximas em cada arco em m3s a Determine por inspeção o corte de menor capacidade nesta rede A partir dele podese dizer qual o valor do fluxo máximo ou pelo menos estabelecer um limite superior para ele b Empregue o algoritmo de FordFulkerson para determinar os fluxos em cada arco que maximizam a quantidade de esgoto tratada Resolução Questão 1 Solução pelo método em tabelas EC SD R OS LA M SB B 0 EC 15 SD 105 SD 115 R 180 R 130 R 180 LA 135 LA 145 M 180 SB 190 Rotas CECSD ECSD e vCECSD 15 CECR ECSDSDR e vCECR 105 CECPS ECSDSDRRPS e vCECPS 180 CECLA ECSDSDLA e vCECLA 115 CECM ECSDSDLALAM e vCECM 135 CECSB ECSDSDLALASB e vCECSB 145 CECB ECSDSDRRB e vCECB 180 A distância total percorrida para abastecer todos os clientes é portanto de 1750 km pois em cada atendimento o veículo deverá executar ida e volta usando a mesmo conjunto de arestas agora percorridas no sentindo contrário Solução pelo método em tabelas ou gráfico 2 Iteração 1 Nó dj pj Status EC 0 Rotulado SD 015 EC 15 EC Não Rotulado Iteração 2 Nó Rótulo Status EC 0 Rotulado SD 15 EC Rotulado R 1590 SD 105 SD Não Rotulado LA 15100 SD 115 SD Não Rotulado Iteração 3 Nó Rótulo Status EC 0 Rotulado SD 15 EC Rotulado R 105 SD Rotulado LA 10525 R 130 R ou 115 SD Não Rotulado PS 10575 R 180 R Não Rotulado B 10575 R 180 R Não Rotulado Iteração 4 Nó Rótulo Status EC 0 Rotulado SD 15 EC Rotulado R 105 SD Rotulado LA 115 SD Rotulado PS 180 R Não Rotulado B 180 R Não Rotulado M 11520 LA 135 LA Não Rotulado SB 11530 LA 145 LA Não Rotulado Iteração 5 Nó Rótulo Status EC 0 Rotulado SD 15 EC Rotulado R 105 SD Rotulado LA 115 SD Rotulado PS 180 R Não Rotulado B 180 R Não Rotulado M 135 LA Rotulado SB 13545 M 180 M ou 145 LA Não Rotulado Iteração 6 Nó Rótulo Status EC 0 Rotulado SD 15 EC Rotulado R 105 SD Rotulado LA 115 SD Rotulado PS 180 R Não Rotulado B 180 R ou 14545 SB 190 SB Não Rotulado M 135 LA Rotulado SB 145 LA Rotulado Iteração 7 Nó Rótulo Status EC 0 Rotulado SD 15 EC Rotulado R 105 SD Rotulado LA 115 SD Rotulado OS 180 R Não Rotulado B 180 R Rotulado M 135 LA Rotulado SB 145 LA Rotulado Iteração 8 Nó Rótulo Status EC 0 Rotulado SD 15 EC Rotulado R 105 SD Rotulado LA 115 SD Rotulado OS 180 R Rotulado B 180 R Rotulado M 135 LA Rotulado SB 145 LA Rotulado Rotas CECSD ECSD e vCECSD 15 CECR ECSDSDR e vCECR 105 CECPS ECSDSDRRPS e vCECPS 180 CECLA ECSDSDLA e vCECLA 115 CECM ECSDSDLALAM e vCECM 135 CECSB ECSDSDLALASB e vCECSB 145 CECB ECSDSDRRB e vCECB 180 Solução pelo método em pseudocódigo Passo 1 R 𝐸𝐶 NR 𝑆𝐷 𝑅 𝑃𝑆 𝐿𝐴𝑀 𝑆𝐵 𝐵 dEC 0 pEC 0 dSD dR dPS dLA dM dSB dB pSD 9 pR 9 pPS 9 pLA 9 pM 9 pSB 9 pB 9 ultimo 0 Passo 2 k1 dSD min 15 15 pSD EC NR R OS LA M SB B R EC SD dSD 15 pSD EC ultimo SD Passo 3 Nodo B não rotulado Retorne ao Passo 2 Passo 2 k2 dR min 105 105 pR SD dLA min 115 115 pLA SD NR PS LA M SB B R EC SD R dR 105 pR SD ultimo R Passo 3 Nodo B não rotulado Retorne ao Passo 2 Passo 2 k3 dPS min180 180 pPS R dB min 180 180 pB R dLA min115 130 115 NR PS M SB B R EC SD R LA dLA 115 pLA SD ultimo LA Passo 3 Nodo B não rotulado Retorne ao Passo 2 Passo 2 k4 dPS min180 180 dB min180 180 dM min135 135 pM LA dSB min 145 145 pSB LA NR PS SB B R EC SD R LA M dM 135 pM LA ultimo M Passo 3 Nodo B não rotulado Retorne ao Passo 2 Passo 2 k5 dPS min180 180 dB min180 180 dSB min145180 145 NR OS B R EC SD R LA M SB dSB 145 pSB LA ultimo SB Passo 3 Nodo B não rotulado Retorne ao Passo 2 Passo 2 k6 dPS min180 180 dB min180 190 180 NR B R EC SD R LA M SB PS dPS 180 pPS R ultimo PS Passo 3 Nodo B não rotulado Retorne ao Passo 2 Passo 2 k6 dB min180 180 NR R EC SD R LA M SB OS B dB 180 pB R ultimo B Passo 3 Nodo B rotulado Recuperando as rotas ótimas CECSD ECSD e vCECSD 15 CECR ECSDSDR e vCECR 105 CECPS ECSDSDRRPS e vCECPS 180 CECLA ECSDSDLA e vCECLA 115 CECM ECSDSDLALAM e vCECM 135 CECSB ECSDSDLALASB e vCECSB 145 CECB ECSDSDRRB e vCECB 180 Questão 2 Para encontrar a rede ótima entre os terminais restantes de modo que o comprimento total das vias selecionadas seja minimizado é necessário encontrar a árvore geradora de peso mínimo do grafo em questão aplicandose o algoritmo de Prim ou o algoritmo de Kuskal Na resolução que segue optou se pelo primeiro Passo 1 LST 2000 C LA CH C SE NY DC DA DE ST LACH Passo 2 LST 2800 C LA CH NY C SE DC DA DE ST LACHCHNY LST 3000 C LA CH NY DC C SE DA DE ST LACHCHNYNYDC LST 3900 C LA CH NY DC DA C SE DE ST LACHCHNYNYDCCHDA LST 4680 C LA CH NY DC DA DE C SE ST LACHCHNYNYDCCHDADADE LST 5780 C LA CH NY DC DA DE SE C ST LACHCHNYNYDCCHDADADELASE Questão 3 a Por inspeção verificase que a capacidade do corte OT mínimo é110 sendo este corte definido pelos arcos OA e OB cujas capacidades são respectivamente 50 e 60 Portanto o fluxo máximo nesta rede vale 110 unidades b A aplicação do algoritmo de FordFulkerson produz as seguintes iterações 1ª Iteração Solução inicial 𝑥 0 com grafo auxiliar correspondente abaixo A cadeia enumerada é 𝐶 𝑂 𝐵 𝐵𝐷 𝐷𝑇 ao longo da qual se pode aumentar o fluxo em Δ𝑓 min606070 60 unidades Com isso 𝑓 𝑓 Δ𝑓 0 60 60 𝑥𝑂𝐵 0 60 60 𝑥𝐵𝐷 0 60 60 𝑥𝐷𝑇 0 60 60 Com as capacidades residuais 𝑣𝑂𝐵 60 60 0 𝑣𝑂𝐵 60 0 60 𝑣𝐵𝐷 60 60 0 𝑣𝐵𝐷 60 0 60 𝑣𝐷 𝑇 70 60 10 𝑣𝐷 𝑇 60 0 60 2ª Iteração A próxima cadeia enumerada é 𝐶 0 𝐴 𝐴 𝐶𝐶𝑇 ao longo da qual se pode aumentar o fluxo em Δ𝑓 min504050 40 unidade Com isso 𝑓 𝑓 Δ𝑓 60 40 100 𝑥0𝐴 0 40 40 𝑥𝐴𝐶 0 40 40 𝑥𝐶𝑇 0 40 40 Com as capacidades residuais 𝑣𝑂𝐴 50 40 10 𝑣𝑂𝐴 40 0 40 𝑣𝐴𝐶 40 40 0𝑣𝐴 𝐶 40 0 40 𝑣𝐶𝑇 50 40 10 𝑣𝐶 𝑇 40 0 40 3ª Iteração A próxima cadeia enumerada é 𝐶 𝑂 𝐴 𝐴 𝐷 𝐷 𝑇 ao longo da qual se pode aumentar o fluxo em Δ𝑓 min106010 10 unidades Com isso 𝑓 𝑓 Δ𝑓 100 10 110 𝑥0𝐴 40 10 50 𝑥𝐴𝐷 0 10 10 𝑥𝐷𝑇 60 10 70 Com as capacidades residuais 𝑣𝑂𝐴 50 50 0 𝑣𝑂 𝐴 50 0 50 𝑣𝐴𝐷 60 10 50𝑣𝐴 𝐷 10 0 10 𝑣𝐷 𝑇 70 70 0 𝑣𝐷 𝑇 70 0 70 4ª Iteração Como se vê na rede abaixo não há caminhos para o aumento do fluxo entre os vértices O e T pois todas as capacidades residuais dos arcos que saem do vértice O são nulas indicando que estes arcos foram saturados O algoritmo então termina com o fluxo ótimo de 𝑓 110 unidades Observe que este valor é o mesmo obtido para o corte de capacidade mínima na letra a