Exercício Avaliativo de Poii

Informação Pública Centro Federal de Educacao Tecnologica Celso Suckow da Fonseca Campus Itaguaı Rod Gov Mario Covas Santana Itaguaı RJ Ministerio da Educacao Curso Engenharia de Producao Codigo GPRO7710IT Perıodo 7º Disciplina Pesquisa Operacional II Professora Nome Valor 5 pts Nota Lista de exercícios Data 20092024 GRAFOS 1 Considere o Grafo abaixo a ORIGE letra A o DESTINO letra T aplique os metodos explicando o passo a passo algoritmo a Considere que os nos do Grafo sao cidades e o peso das arestas sao a distˆancia entre as cidades Portanto um problema classico para distribuicao de mercadorias por exemplo e encontrar a distˆancia mınima entre duas cidades Desta forma encontre o caminho mais curto ORIGEM DESTINO utilizando o Metodo de Dijkstra b Com as mesmas consideracoes da letra a se temos uma cidade como Centro de Distribuicao e essencial saber a distancia mınina do Centro de Distribuicao ate todas as outras cidades Portanto encontre a Arvore Geradora Mınima iniciando pela ORIGEM c Considere cada no como um posto intermediario de distribuicao de petroleo e o peso das arestas sao a vazao de petroleo entre os postos de distribuicao Fique atento que pode ser enviado petroleo de O A e tambem de A O com 4 unidades de vazao ou seja estamos em um grafo nao direcionado Assim um problema comum e encontrar o quanto de petroleo conseguimos transferir de um posto para outro Desta forma encontre o Fluxo Maximo da ORIGEM ate o DESTINO PROGRAMAC AO NAO LINEAR 1 Use o metodo da Bisseccao com uma tolerˆancia de erro ϵ 004 e com os seguintes limites iniciais para resolver interativamente de forma aproximada cada um dos seguintes problemas a Maximizar f x 6x x2 com x 0 x 48 b Minimizar f x 6x 7x2 4x3 x4 com x 4 x 1 2 Considere o seguinte problema Maximizar f x 48x5 42x3 35x 16x6 61x4 165x2 Aplique o metodo de Newton neste problema com ϵ 0001 e x0 1 Informação Pública 3 Partindo do ponto inicial x1 x2 1 1 aplique duas iteracoes do metodo de busca por gradiente para comecar a resolver o problema Maximizar f x 4x1x2 2x2 3x2 1 2 Depois encontre a solucao exata resolvendo f x 0 diretamente Questão 1 CAMINHO mínimo O C F G T Valor 17 a O A B C D E F G H I T d 0 4 3 6 7 9 8 10 11 14 1517 pai 0 0 0 0 A A C F E E G 1 Visita O adiciona as arestas O A O B O C dO 0 2 Visita B adiciona as arestas B C e B E dB 3 3 Visita A adiciona as arestas A C e A D dA 4 3 Visita C adiona as arestas C D C F e C E dC 6 4 Visita D adiciona as arestas D F e D G dD 7 5 Visita F adiciona as arestas F G F H F E dF 8 6 Visita E adiciona as arestas E H e E I dE 9 7 Visita G adiciona as arestas G H e G T dG 10 8 Visita H adiciona as arestas H I e H T dH 11 9 Visita I adiciona a aresta I T dI 14 10 Visita T dT 17 b Ordem das arestas E F C D C F E H F G G H D F O B H I A D O A B C D G I T Árvore geradora mínima Custo 4 3 3 2 2 1 2 7 2 3 4 26 c caminho 1 O A D G T Fluxo 3 caminho 2 O C E I T Fluxo 4 caminho 2 O C F H T Fluxo 2 caminho 3 O B E H T Fluxo 2 caminho 4 O A C B E I H T Fluxo 1 caminho 5 O B E F H T Fluxo 1 Fluxo Máximo 13 a fx 6x x2 fx 6 2x iter a b c fc 1 0 48 24 12 2 24 48 36 12 3 24 36 3 0 Valor ótimo x 3 b fx 6x 7x2 4x3 x4 fx 6 14x 12x2 4x3 iter a b c fc 1 4 1 25 6 2 25 1 075 6 3 25 075 1625 22265625 4 1625 075 1875 0401367 5 11875 075 096875 00626 6 096875 11875 1078125 0158157 7 1078125 096875 10234375 0046926 Valor ótimo x 10234375 fx 48x5 42x3 35x 16x6 61x4 165x2 fx 240x4 126x2 35 96x5 244x3 33x fx 960x3 252x 480x4 732x2 33 i xi xi1 fxi 0 1 08939 35 1 08939 08078 11548 2 08078 07377 03819 3 07377 06804 01266 4 06804 06339 00418 5 06339 05968 00137 6 05968 05683 00044 7 05683 05472 00014 8 05472 00004 Solução ótima 05472 3 f 4x2 4x1 4x1 6x2 1º iteração 11 f11 11 02 11 2º iteração 11 f810 79 f 0