Optimização em redes com parâmetros aleatórios

Abstract

Esta dissertação tem por base os estudos efectuados sobre Optimização Combinatória, em particular Optimização em Redes. Estudou-se o problema do Trajecto Estocástico Optimo com parâmetros aleatórios contínuos e discretos. São propostos diversos algoritmos para a resolução deste problema que se baseiam nos algoritmos de rotulação, conhecidos para o caso da determinaçãao do Trajecto Optimo em IR e em IRk, e na generalização das equações de Bellman. Estes algoritmos foram aplicados a redes de grandes dimensões, geradas aleatoriamente, tendose adaptado uma estrutura de dados ao problema.

This dissertation has for base the studies on Combinatorial Optimization, in particular Network Optimization. The problem of the Stochastic Optimal Loopless Path with continuous and discrete random parameters was studied. Diverse algorithms for the resolution of this problem are considered. Those algorithms are based on the labelling algorithms, known for the case of the determination of the Optimal Path in IR and IRk, and in the generalization of Bellman equations. These algorithms had been applied to networks with high dimensions, randomly generated, having itself adapted a data structure to the problem.