Parametric LCP를 이용한 LP해법 = A Study on an algorithm for Parametric LCP

다국어 초록 (Multilingual Abstract)

In this paper, approach to solving the LP similiar to Dantzig's self-dual algorithm is described.
By the transformation of the LP to the Parametric LCP using parameter t, we search the primal and dual feasible path.
Some properties of algorithm are:
1) It solves the primal-dual problem at the same time.
2) It searchs the primal-dual feasible path.
3) It is the convergent algorithm of parameter t.
4) Choosing the initial feasible solution can effect the behavior of algorithm.
5) If the feasible start point is chosen, then the path will be primal-dual beasible throughout the algorithm.
6) At each step of algorithm, it provides a good bound of optimal objective function.
In solving the large scale problem by the simplex algorithm, in many cases, 95% of optimality may be achieved.
In these cases, disappropriate amount of time may be spent in obtaining very eittle improvement.
There is no way of halting to do this in the simplex algorithm.
Algorithm described will be appropriate for such problems.

목차 (Table of Contents)

• Ⅰ. 序 論
• Ⅱ. 선형상보문제의 고찰
• Ⅲ. 초기해 선택
• Ⅳ. 알고리즘의 흐름
• Ⅴ. 알고리즘의 적용
• Ⅵ. 結 論