Optimização em redes
Contents
1.2. Fundamentos de Investiga o Operacional Folha n 3 Problemas de optimiza o em redes 2008 09 1 Uma companhia sediada no Porto pretende estabelecer o plano mais econ mico para as desloca es dos seus vendedores s cidades onde existem representantes dos seus produtos A fig mostra um mapa simplificado onde os n s representam as cidades e os arcos representam as liga es poss veis Bragan a Braga 200 100 Vila Real 200 papi Guarda Viseu 150 2 Aveiro 39 60 Coimbra A cada arco est associado um valor representando o custo que a empresa atribui a esse trajecto em fun o da dist ncia das condi es da estrada e da densidade do tr fego Determine os percursos mais econ micos que os vendedores da empresa dever o efectuar entre a sede e todas as cidades 2 Uma empresa pretende determinar a pol tica ptima de substitui o de um dado equipamento num per odo de planeamento de 5 anos Os custos envolvidos s o Kj custo de aquisi o do equipamento no ano j Sj valor residual do equipamento ap s j anos de uso cj custos de opera o e manuten o durante o ano j Formule este problema como um de caminho mais curto numa rede dirigida 3 Usando o algoritmo de Floyd determine os caminhos mais curtos entre todos os pares de nodos na rede da fig Fundamentos de Investiga o Operacional Problemas de optimiza o em redes 1 4 Em todas as cidades da regi o em an lise no prob 1
3. est o sediadas empresas de diferentes ramos de actividade que t m necessidade de definir os trajectos mais econ micos para as desloca es dos seus vendedores entre a sede e as restantes cidades Adoptando o mesmo mapa simplificado do prob 1 determine os percursos mais econ micos para cada empresa 5 Uma empresa de telecomunica es pretende servir a mesma regi o do prob 1 com uma nova rede telef nica Na fig os nodos representam as localidades a servir e os arcos representam as liga es onde tecnicamente poss vel o lan amento de cabos A cada arco est associada a dist ncia entre as localidades que liga Quais as liga es a concretizar se a empresa quiser minimizar o comprimento de cabo a instalar 6 A rede da fig representa uma parte do sistema rodovi rio de uma cidade O custo associado a cada arco representa o tempo m dio em minutos que o tr fego demora nesse percurso A cada mudan a de direc o num cruzamento est associada uma penaliza o adicional de 3 minutos Qual o caminho mais r pido entre o nodo 1 e o nodo 8 7 Dada a rede da fig onde a cada arco est associada a sua capacidade qual o fluxo m ximo que pode ser enviado do nodo origem 1 para o nodo terminal 5 8 A empresa Paga amp Ri Lda propriet ria de um parque de divers es Na fig os nodos representam os pontos de divers o e os arcos as respectivas liga es onde os visitantes s o transportados por pequenos comboi
4. os el ctricos Dado que os caminhos s o algo acidentados geograficamente e o material circulante apresenta sinais de envelhecimento apenas podem ser realizadas diariamente as viagens assinaladas Assumindo que os comboios andam sempre cheios quais s o os percursos e quantos comboios devem circular de modo a levar o m ximo n mero de visitantes di rios da entrada nodo 0 para a montanha russa nodo 6 Considere a situa o em que n o h viagens como solu o inicial Fundamentos de Investiga o Operacional Problemas de optimiza o em redes 2 9 Na rede da figura a cada arco i j est associada a sua capacidade bi e o fluxo nele existente xij a Determine o valor de x42 e de x53 de modo a que a solu o actual seja admiss vel b Determine o fluxo m ximo que pode ser enviado do nodo origem 1 para o nodo terminal 6 No processo de etiquetagem siga a ordem crescente do ndice dos nodos eventualmente usando a excep o de tentar etiquetar o nodo terminal antes de outros nodos com ndice mais baixo c Determine o corte m nimo da rede e mostre que a sua capacidade igual ao fluxo m ximo 10 Determine o plano ptimo de envio de 10 unidades de fluxo ao custo m nimo do nodo 1 para o nodo 5 na rede da fig bij representa a capacidade do arco e cij o custo de enviar uma unidade de fluxo atrav s do arco bij cij Fundamentos de Investiga o Operacional Problemas de optimiza o em redes 3
Download Pdf Manuals
Related Search