내부해로부터 최적기저 추출에 관한 연구

다국어 초록 (Multilingual Abstract)

If the LP problem doesn't have the optimal solution uniquely, the solution of the primal-dual barrier method converges to the interior point of the optimal face. Therefore, when the optimal basis is required, we have to perform the additional procedure to recover the optimal basis from the final solution of the interior point method.
In this paper the existing methods for recovering the optimal basis or identifying the optimal solution are analyzed and the new methods are suggested. This paper treats the two optimal basis recovery methods. One uses the purification scheme and the simplex method, the other uses the optimal face solutions. In the method using the purification procedure and the simplex method, the basic feasible solution is obtained from the given interior solution and then simplex method is performed for recovering the optimal basis. In the method using the optimal face solution, the optimal basis in the primal-dual barrier method is constructed by integrating the optimal solution identification technique and the optimal basis extracting method from the primal-optimal solution and the dual-optimal solution.