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