Lista de Exercícios de Otimização e Programação Inteira

Lista 3 Exercício 1 Um viajante deseja se deslocar entre as cidades de Santo Ozzy Osbourne S e o São Tommy Iommi T gastando o mínimo possível Não há nós diretos entre os pontos S e T logo será necessário fazer conexões através dos reportos A B E e F Os valores nos arcos da rede indicam os preços R dos vosos no trecho e na data desejados Elabore um plano de viagem de custo mínimo entre S e T Exercício 2 A rede abaixo representa a malha viária de um pequeno bairro Os valores associados a seus arcos representam o tempo esperado de atravessamento das ruas ou avenidas correspondentes em horário de pico Encontre um caminho que permita a um cidadão localizado no vértice C se deslocar de carro até o vértice H no menor tempo possível Resolva este problema por algum algoritmo de caminho visto no curso Ao final indique o caminho ótimo encontrado e diga qual o tempo esperado para percorrêlo Exercício 3 Escreva uma formulação de Programação Inteira para o problema apresentado no Exercício 1 Na formulação devese necessitar exigir a integralidade das variáveis de decisão para que estas retornem inteiras Ou não o problema pode ser resolvido por um algoritmo para Programação Linear e mesmo assim se obter soluções inteiras Justifique sua resposta A gerência responsável por esta operação deseja saber quais trechos entre partes de áreas devem ser construídos para conectar todas as áreas a custo mínimo Assume que o custo de construção é diretamente proporcional ao comprimento total construído e empregou um algoritmo ótimo para resolver este problema Exercício 5 Uma empresa de manufatura deseja formar células de produção reunindo em uma mesma célula máquinas similares A média de dissimilaridade empregada é dada pelo índice dij definido como dij 1 nij nij mij onde nij é o número de produtos processados na máquina i e também na máquina j mij é o número de produtos processados na máquina i ou na máquina j mas não em ambas Há 10 máquinas nas quais são processados 15 produtos A tabela abaixo lista os produtos processados com cada máquina 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 Exercício 4 Os bairros de uma dada região metropolitana são conectados por vias de modo íntimo conforme indicado abaixo As distâncias percorridas nos arcos estão indicadas em 10m Uma pessoa pega um taxi no bairro F e deseja se deslocar até pagando o mínimo possível Qual a rota que o taxista deve fazer para minimizar o gosto do cliente e qual seu comprimento LISTA 4 Centro Federal de Educação Tecnológica Celso Suckow da Fonseca Departamento de Engenharia de Produção Disciplina Pesquisas Operacionais II Tema Árvore Geradora de Peso Mínimo Professor Ormeu Códio da Silva Júnior Exercício 1 A prefeitura de um município se propôs a asfaltar algumas das estradas que ligam as comunidades rurais e a cidade Desejase que qualquer comunidade possa ser acessada através de uma via pavimentada a partir da cidade Como os recursos são limitados a prefeitura deve escolher quais estradas seriam pavimentadas de modo a minimizar o investimento total A rede abaixo escolhe as estradas candidatas a pavimentação A cidade correspondente ao vértice B desta rede é comunidades rurais oito representadas pelos demais vértices Os pesos das arestas representam o custo 10R estimado de pavimentação de respectiva estrada Projete a rede rodoviária que minimiza os custos de construção garantindo que todas as cidades possam ser acessadas por uma estrada pavimentada Exercício 2 Desejase construir uma rede de metrôs ao longo de oito bairros de uma cidade com o menor investimento possível Um estudo preliminar mapeou as possíveis ligações que poderiam ser construídas e seus respectivos custos conforme se indica na tabela abaixo Custo de construção do ligáção 10R Estações 1 2 3 4 5 6 7 8 1 750 900 1050 990 1800 2 800 1250 1400 3 950 1400 4 900 750 1200 5 800 1300 1100 6 900 7 1300 1100 8 1150 Obtenda a rede que requere o menor investimento em total em sua construção Exercício 3 A figura abaixo apresenta as conexões para ligar 9 bocas de poços localizadas em plataformas marinhas offshore de gás natural com um ponto de entrega em terra Como a boca do poço 1 é a mais próxima do litoral ele é equipado com capacidades de bombeamento e armazenagem suficientes para bombear a produção dos oito poços restantes até o ponto de entrega a Determine a rede mínima de tubulações para ligar as bocas de poço ao ponto de entrega b Suponha agora que as bocas de poço estão divididas em dois grupos baixa e alta pressão Os poços 2 3 4 e 6 são da alta pressão enquanto os poços 5 7 8 e 9 são de baixa pressão Não é possível conectar a boca de poço de um grupo com outra poça Exercício 5 A figura abaixo apresenta as conexões viárias para ligar 9 bocas de poços localizadas em plataformas marinhas offshore de gás natural com um ponto de entrega em terra Como a boca do poço 1 é a mais próxima do litoral é equipada com capacidades de bombeamento e armazenagem suficientes para bombear a produção dos oito poços restantes até o ponto de entrega a Determine a rede mínima de tubulações para ligar as bocas de poço ao ponto de entrega b Suponha agora que as bocas de poço são divididas em dois grupos baixa e alta pressão Os poços 2 3 4 e 6 são de alta pressão enquanto os poços 5 7 8 e 9 são de baixa pressão Não é possível conectar as bocas de poço de um tipo com outro mas os dois grupos devem ser conectados ao ponto de entrega na boca de poço 1 Determine uma nova rede ótima considerando esta restrição Exercício 4 Uma empresa especializada no plantio e corte de madeira precisa construir um conjunto de estradas de chão para ligar outro áreas em exploração de modo que uma área seja acessível a partir de qualquer outra A distância em milhas entre cada par de áreas de exploração é dada na matriz abaixo A gerência responsável por esta empresa deseja saber quais trechos entre pares de áreas devem ser construídos para conectar todas as áreas a custo mínimo Assuma que o custo do construção é diretamente proporcional ao comprimento total construído e empregue um algoritmo ótimo para resolver este problema Por causa da poluição excessiva no rio Paraiabuna o estado de Minas Gerais vai construir estações de controle de poluição Três sites 1 2 e 3 estão sendo considerados O Estado está interessado em controlar os níveis de poluição de dois poluentes principais 1 e 2 A legislação estadual exige que pelo menos 80000 toneladas de poluente 1 e pelo menos 50000 toneladas de poluente 2 sejam removidas do rio Os dados relevantes para este problema são mostrados na tabela abaixo Formule um modelo de Programação Inteira para minimizar o custo do cumprimento das metas do legislativo estadual