Buscar

 

RI UFLA (Universidade Federal de Lavras) >
DCC - Departamento de Ciência da Computação >
DCC - Graduação >
DCC - Bacharelado em Ciência da Computação (Monografias) >

Por favor, utilize esse identificador para citar este item ou usar como link: 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(es): Lima Júnior, Adonias Amorim de
Orientador: Moreira, Renata Couto
Membro da banca: Abreu, Ricardo Martins de
Monserrat Neto, José
Data de Defesa: 16-Dez-2002
Data de 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: DCC - Bacharelado em Ciência da Computação (Monografias)

Arquivos neste Item:

Arquivo Descrição TamanhoFormato
MONOGRAFIA_Análise_de_complexidade_assintótica_de_um_algoritmo_exato_para_o_cálculo_do_nucleolus_de_um_jogo_cooperativo.pdf537,86 kBAdobe PDFVer/abrir

Itens protegidos por copyright, com todos os direitos reservados, Salvo indicação em contrário.


Mostrar estatísticas

 


DSpace Software Copyright © 2002-2007 MIT and Hewlett-Packard - Feedback