Dissertação (mestrado)—Universidade de Brasília, Faculdade de Economia, Administração, Contabilidade e Ciência da Informação e Documentação, Departamento de Economia, Programa de Pós-Graduação em Economia, 2009. / Submitted by Jaqueline Ferreira de Souza (jaquefs.braz@gmail.com) on 2011-05-30T22:02:53Z No. of bitstreams: 1 2009_MarioRubendoCouttoBastos.pdf: 686532 bytes, checksum: 98e9170e7a8c331d5b1bc3509673d0d2 (MD5) / Approved for entry into archive by Jaqueline Ferreira de Souza(jaquefs.braz@gmail.com) on 2011-05-30T22:04:44Z (GMT) No. of bitstreams: 1 2009_MarioRubendoCouttoBastos.pdf: 686532 bytes, checksum: 98e9170e7a8c331d5b1bc3509673d0d2 (MD5) / Made available in DSpace on 2011-05-30T22:04:44Z (GMT). No. of bitstreams: 1 2009_MarioRubendoCouttoBastos.pdf: 686532 bytes, checksum: 98e9170e7a8c331d5b1bc3509673d0d2 (MD5) / Essa dissertação analisa um modelo híbrido do Sistema de Pagamentos onde as transferências são acumuladas em filas que permitem a liquidação pelo valor líquido da posição multilateral do participante. Quando os recursos no sistema são insuficientes para liquidar todos os pagamentos existentes, a solução ótima depende da exclusão de alguns pagamentos do processo de liquidação. Esse problema, conhecido na literatura como Banking Clearing Problem (BCP), é NP completo sendo a solução inviável quando existe um número significativo de bancos e pagamentos. A modelagem do BCP por programação linear oferece uma alternativa, possibilitando priorizar a liquidação dos pagamentos que possuem maior capacidade de gerar novas liquidações e permitindo a elaboração de algoritmos de busca da solução ótima mais eficientes. _______________________________________________________________________________________ ABSTRACT / This dissertation analyses a hybrid model of Payment Settlement System where transfers are accumulated in queues allowing a multilateral net settlement. When funds are not enough to settle all existing payments, the optimal solution requires the exclusion of some payments from the process. This problem, known as Banking Clearing Problem (BCP), is NP complete and its solution is time demanding, which renders it not viable in the case of a large number of banks or payments. BCP modeling by linear programming offers an alternative, using the shadow-price of each payment to identify the potential to generate new settlements and allowing the development of more efficient algorithms in the search of optimal solutions.