CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / No problema do Caminho MÃnimo com RestriÃÃo ProbabilÃstica de Atraso MÃximo visamos considerar o fator tempo no projeto de rotas de transporte de cargas em malhas viÃrias a custo mÃnimo, atentando à crescente incerteza nos tempos de percurso dessas rotas em malhas reais, e observÃ-lo tendo em mente estratÃgias de qualidade de serviÃo, de forma a obtermos um compromisso entre o custo de percurso e a conformidade ao prazo de chegada ao destino. Realizamos um estudo de problemas relacionados na literatura da Ãrea de otimizaÃÃo em redes de transporte, de forma a tentarmos conhecer melhor o problema a ser estudado, sobre o qual nÃo tomamos conhecimento de trabalhos existentes. Desenvolvemos um esquema para enumeraÃÃo de partiÃÃes do espaÃo de soluÃÃes do problema, que utiliza uma decomposiÃÃo em L para selecionar partiÃÃes de forma inteligente, e que à auxiliado por soluÃÃes de relaxaÃÃes do problema de forma a obter cotas para o custo Ãtimo. AlÃm disso, desenvolvemos algumas estratÃgias de ramificaÃÃo e de poda para um esquema de Branch-and-Bound, com uma fase de prÃ-processamento, de forma a tentar resolver o problema diretamente. Os resultados computacionais obtidos demonstram que somos competitivos com a ferramenta comercial utilizada para comparaÃÃo em instÃncias de menor porte para o problema. Para as demais instÃncias, essa ferramenta se mostrou mais eficiente quanto ao tempo necessÃrio para a resoluÃÃo. / In the Probabilistic Delay Constrained Shortest Path problem we aim to consider the time factor in the design of cargo routing paths in road networks at minimum cost, considering the increasing uncertainty in travel times of these routes in real networks, and keeping in mind strategies of quality of service, in order to obtain a compromise between the travel costs and the compliance of the arrival time at the destination. We conducted a study of related problems in the literature of transport networks optimization, in order to better understand the problem to be addressed, about which we are not aware of existing works. We developed a scheme for enumerating partitions of the solution space of this problem, which uses an L decomposition to select these partitions wisely, and is aided by solutions to relaxations of the problem to obtain bounds for the optimal cost. In addition, we developed some branching and pruning strategies for a Branch-and-Bound scheme, with a pre-processing phase, in order to try and solve the problem directly. The computational results show that we are competitive with the commercial tool used for comparison in the smaller instances. For the remaining instances, this tool is more efficient in the time required for solving the problem.

Made available in DSpace on 2016-12-23T14:34:47Z (GMT). No. of bitstreams: 1 Rone Mauri.pdf: 1614722 bytes, checksum: 9403a819f35ef1a182bd8772f7204a6f (MD5) Previous issue date: 2013-08-16 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This work shows a proposal to approach Graph Theory, which is rarely taught at public high schools, and looks for working the theme through the resolution of problems, providing opportunities to the pupil for effective participation on the building of arguments and challenging them to search for solutions, instigating the curiosity and requiring from them an attitude that lead to take decisions, favoring the emergence of creative answers and developing abilities concerning to those proposed on the Common Basic Curriculum of the state public high school. This proposal is described in two chapters, being the first one to introduce the theme on the second grade of high school, and the second one, to retake concepts already seen on the first one and introduce new concepts to the students of the third grade of high school. Both chapters are composed of problems, to introduce concepts and results as much to apply them, bringing their solutions and, in some cases, commentaries to the teachers / Este trabalho traz uma proposta para abordar a Teoria de Grafos, conteúdo que raramente é lecionado no ensino médio em escolas públicas, e objetiva trabalhar o tema através de resolução de problemas, oportunizando aos educandos a participação efetiva na construção de argumentos e desafiando-os a buscarem soluções, instigando a curiosidade e exigindo deles uma postura que os leva a tomarem decisões, favorecendo o surgimento de respostas criativas e desenvolvendo habilidades concernentes àquelas propostas no Currículo Básico Comum da rede estadual de ensino. Esta proposta traz dois capítulos, sendo o primeiro para introduzir o tema na 2ª série do ensino médio, e o segundo, para retomar conceitos já vistos no primeiro e introduzir novos conceitos aos alunos da 3ª série do ensino médio. Os dois capítulos são constituídos de problemas, tanto para introduzir conceitos e resultados quanto para aplicá-los, trazendo suas soluções e, em alguns casos, comentários dirigidos aos professores

Made available in DSpace on 2015-03-26T13:45:36Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1755688 bytes, checksum: 33e268f82618cf29e2d1fa6df5c6fa6c (MD5) Previous issue date: 2013-07-30 / Fundação de Amparo a Pesquisa do Estado de Minas Gerais / A poset metric is the generalization of the Hamming metric. In this work we make a detailed study of poset spaces, hierarchy of I -weights and I -distribution of P P weights, emphasizing the non-degenerate poset codes. We verify the duality relation between the hierarchy weights of poset code and its dual. In the sequel two new parameters are defined to a class of poset codes non-degenerate with dual code is too non-degenerate in the environment. As a result enunciated in the Minimality Theorem, the Variance Theorem and the Minimality Identity in the poset spaces. / Uma generalização da métrica de Hamming é a métrica poset. Faremos um estudo detalhado dos espaços poset, hierarquia de I-pesos e a I-distribuição de pesos, dando ênfase aos códigos poset não degenerados. Verificamos a relação de dualidade poset entre as hierarquias de um código e seu dual. Definimos dois novos parâmetros para a classe de códigos dualmente não degenerados no ambiente poset. Como consequência, enunciamos e mostramos o Teorema da Minimalidade, o Teorema da e Variância e a Identidade de Minimalidades no espaço poset.