線型計劃法을 위한 非頂邊解法의 硏究

• 영문명: A Review Study on Non-edge Following Algorithms for Linear Programming
• 발행기관: 건국대학교 경제경영연구소
• 저자명: Seong Baek Seo(成百瑞)
• 간행물 정보: 『상경연구』제13권, 163~181쪽, 전체 19쪽
• 주제분류: 경제경영 > 경제학
• 파일형태: PDF
• 발행일자: 1988.09.15

영문 초록

This study reviews the solution techniques for Linear Programs which have been proposed after the well-known Simplex method was published in 1947. One group of them are simplex-based ones that include the advanced basis technique, constraint, relaxation technique, multiple pivoting or some ad hoc relaxation called PAPA. Second are the feasible direction search types of Nonlinear Programming solution methods to Linean Programs. Besides these, the theoretical evolution of polynomial-time algorithms including the Khachiyan’s ellipsoid algorithm and the Karmarkar’s projective algorithm is notable in the literatures. As a result of reviews, we conclude that the non-edge following strategies which are common in almost all of the above studies, seems to be promising for improving the computational efficiency over the Simplex Method. We then, investigate the polynomial-time property of the projective algorithm and a feasible direction algorithm with finite convergence which is noted to be more efficient than the Simplex with limited experiences. More research efforts are required on this topic.

목차

Ⅰ. 序論

Ⅱ. 投影解法(Projective method)

Ⅲ. 效率的인 非頂邊探索解法

Ⅳ. 線型計劃模型과 非頂邊解法의 展望

參考文獻

SUMMARY