Proposição de um algoritmo alternativo para a resolução do problema de equilíbrio espacial de preços: aspectos computacionais associados à representação matricial e teoria dos grafos

Abstract

Este trabalho propõe um Algoritmo Alternativo para resolver problemas de Equilíbrio Espacial de Preços (SPE). O contexto do problema é representado por um sistema econômico em que uma dada commodity tem potencial para fluir entre todos os agentes do sistema, os quais atuam em modo de concorrência perfeita. O modelo do problema a ser utilizado aceita as restrições clássicas do modelo SPE em conjunto com a formulação geral das funções de preços não-linear dos seus agentes, nas quais devem ser positivas, duas vezes continuamente diferenciáveis e, em especial, possuir a propriedade de monotonicidade. O Algoritmo Alternativo é baseado na teoria de Grafos e na representação Matricial para manipular estruturas de dados visando representar subgrafos conexos maximais, que são nesta abordagem sempre bipartidos. Esses subgrafos assumem o papel de operandos em processos sucessivos de inserção de arcos livres, especialmente escolhidos. Cada subgrafo aumentado pela inserção é considerado como um novo subproblema SPE que é submetido a uma série de processos de linearizações. Uma representação matricial dual para esse subproblema é construída com o objetivo de extrair um operador auto-adjunto (self-dual) que mapeia uma solução aproximada única em um espaço linear de dimensão finita, dotado de produto interno como norma, no qual é possível ser gerado por um conjunto maximal de bases ortonormais. As aproximações primais e duais estão sempre em correspondência um-para-um. Uma tarefa adicional é realizada com o objetivo de identificar quais arcos devem ser retirados do subgrafo aumentado quando a restrição de positividade para seus fluxos estiver em fase de violação. A convergência linear é acompanhada em cada aproximação. A solução o final é alcançada quando não houver arcos livres com potencial para entrar em algum subgrafo parcial do problema original. A convergência não-linear é medida comparando-se a diferença entre soluções lineares e não-lineares com uma medida de erro previamente definida. Um estudo de caso é realizado sobre diversos problemas aplicando o Algoritmo Alternativo.<br>

Abstract : This work describes an Alternative Algorithm for solve SPE problems. The problem's context is represented by an economic system where a given commodity has potential to flow between all system's agents, in which act in perfect competition mode. The problem's model accepts the classical SPE's constraints in conjunction with the general formulation of agent's non-linear price functions, in which must have positivity, twice-differentiable continuity and monotonicity properties. The Alternative Algorithm is based on Graph's theory and Matricial representation to handle data structures to represent bipartite maximal connected subgraphs as operands of sucessive insertion processes of chosen arcs called ``free arcs\". Each augmented subgraph is considered as a new SPE subproblem that is submitted to a series of linearization processes. A dual matricial representation for that subproblem is builded aiming to extract a self-dual operator that mapps a unique approximated solution into a dual finite-dimensional inner product linear space, in which is spanneable by a set of maximal orthonormal basis. The primal and dual approximations are in one-to-one correspondence. An additional task is performed aiming to identify which arcs must be retired from the augmented subgraph when the positivity's restriction for their flows are in violating phase. The linear convergence is accomplished. The final solution is obtained when no more arcs are to be inserted to any subproblems. The non-linear convergence is measured by comparing the difference between linear and non-linear solutions with a preseted error. A case study is provided after Alternative Algorithm presentation.