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) >

Please use this identifier to cite or link to this item: http://repositorio.ufla.br/jspui/handle/1/5637

Title: Análise de complexidade assintótica de um algoritmo exato para o cálculo do nucleolus de um jogo cooperativo
???metadata.dc.creator???: Lima Júnior, Adonias Amorim de
???metadata.dc.contributor.advisor1???: Moreira, Renata Couto
???metadata.dc.contributor.referee1???: Abreu, Ricardo Martins de
Monserrat Neto, José
???metadata.dc.date.submitted???: 16-Dec-2002
Issue Date: 29-Apr-2015
Citation: 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.
???metadata.dc.description.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
???metadata.dc.language???: pt_BR
Appears in Collections:DCC - Bacharelado em Ciência da Computação (Monografias)

Files in This Item:

File Description SizeFormat
MONOGRAFIA_Análise_de_complexidade_assintótica_de_um_algoritmo_exato_para_o_cálculo_do_nucleolus_de_um_jogo_cooperativo.pdf537.86 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


View Statistics

 


DSpace Software Copyright © 2002-2010  Duraspace - Feedback