This thesis involves the study of an algorithm for single commodity spatial market price equilibrium problems. The conventional approach is the conversion to the related nonlinear programming problem. When it is the multicommodity problem, the integrability assumption about supply and demand functions is needed to induce a so-called quasi-welfare function.
The presented algorithm works with a linear objective function which represents the total cost of transportation, while it considers a excess supply function in its derivation of the desired excess supply at each node. And it proceeds to find an equilibrium solution while it implicitly cuts some basic arcs when certain conditions are met. This approach has advantages in that it stops with an exact solution within a finite number of iterations, and the integrability assumption is not needed when it is extended to the case of multicommodity problem.
This tree cutting algorithm is basically a parametric programming technique, which is a natural extension of the study of Srinivasan and Thompson [23]. The operation which finds an adjacent dual basis provides the linear network problem with a direction so that it can be solved by the parametric network simplex method.
It is shown that the tree cutting algorithm with adjustment routine converges to an optimal solution in a finite number of iterations. All the proofs are presented for the case of linear excess supply functions. Computational results indicates that the suggested algorithm converges quite well for the linear case. Finally, the comments about the problems which may arise in applying the algorithm to more extended problems are suggested.
본 논문에서는 공간적으로 분포되어 있는 시장 간의 유동에 있어서 단일재화의 가격균형문제를 위한 tree cutting algorithm 을 제시하고 있다. 이러한 문제를 푸는 전통적인 방법은 그와 연관된 NLP 문제로 전환하는 것이다.
여기에 제시된 해법은 목적함수가 총수송비용을 나타내는 선형함수이고 각 지점에서의 기대초과공급량을 구하는 과정에서 초과공급함수를 고려한다. 그리고 최적해를 찾아가는 과정에서 basis preserving operation 을 계속하는데, 이때 특정한 조건이 만족되면 tree cutting operation 을 적용한다.
이러한 tree cutting algorithm 은 Srinivasan 과 Thompson의 연구 결과를 확장한 network 에서의 parametric programming technique에 그 기초를 두고 있다. Adjacent dual basis를 찾는 operation은 이 문제에 direct 을 제공하고 이것은 다시 parametric network simplex 법으로 풀린다.
이 tree cutting algorithm 은 유한한 iteration만에 그 최적해를 찾는다는 것이 선형 초과공급함수의 경우에 대해서 증명된다. 그리고 실제 계산결과는 이 algorithm 이 상당히 효율적이라는 것을 보여준다.
