Use este identificador para citar ou linkar para este item: http://repositorio.ufla.br/jspui/handle/1/5637
Título: Análise de complexidade assintótica de um algoritmo exato para o cálculo do nucleolus de um jogo cooperativo
Autor : Lima Júnior, Adonias Amorim de
Primeiro orientador: Moreira, Renata Couto
Primeiro membro da banca: Abreu, Ricardo Martins de
Monserrat Neto, José
Data da publicação: 29-Abr-2015
Referência: LIMA JÚNIOR, A. A. Análise de complexidade assintótica de um algoritmo exato para o cálculo do nucleolus de um jogo cooperativo. 2002. 57 p. Monografia (Graduação em Ciência da Computação) - Universidade Federal de Lavras, Lavras, 2002.
Resumo: O problema atacado pelo projeto está em alocar os custos de uma rede de maneira justa entre os participantes e analisar a complexidade da solução para tal problema. A aplicação se encontra em situações onde determinadas entidades visam alcançar um objetivo comum. Visto que cada entidade possui um custo para obter o mesmo serviço, uma cooperação pode ser formada para a redução do custo. Para se obter uma divisão deste custo de maneira ótima entre os usuários, o valor de Shapley e o Nucleolus podem ser utilizados como solução. A solução do nucleolus, que é uma solução pertencente à Teoria dos Jogos Cooperativos, foi utilizada, pois este aloca os custos entre os usuários de maneira mais justa. Um algoritmo baseado na programação linear para a obtenção do nucleolus, proposto por [Grano81], foi desenvolvido, no entanto foi verificado que tal algoritmo necessitava de modificações para que a solução pudesse ser obtida, logo este foi estendido. Ao verificar os resultados, pode-se verificar que o algoritmo proposto resultava em resultados mais justos que o algoritmo encontrado na literatura, onde a complexidade se manteve a mesma.
Abstract: The problem attacked by the project is to allocate the costs of a net in a fair way among the participants and to analyze the complexity of the solution for the problem. The application is in situations where certain entities seek to reach a common objective. Because each entity possesses a cost to obtain the same service, a cooperation can be formed for the reduction of the cost. To obtain a division of this cost in a great way among the users, the value of Shapley and Nucleolus can be used as solution. The solution of the nucleolus, that is a solution belonging to the Cooperative Game Theory, it was used, therefore this allocates the costs among the users in a fairer way. An algorithm based on the lineal programming for the obtaining of the nucleolus, proposed for [Grano81], it was developed, however it was verified that such algorithm needed modifications so that the solution could be obtained, so this was extended. When verifying the results, it can be verified that the proposed algorithm resulted in fairer results than the algorithm found in the literature, where the complexity stayed the same.
URI: http://repositorio.ufla.br/jspui/handle/1/5637
Idioma: pt_BR
Aparece nas coleções:PROGRAD - Ciência da Computação (Trabalhos de Conclusão de Curso)



Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.