This thesis presents a non edge-following algorithm for solving linear programming problems. Unlike simplex algorithm, this algorithm requires as its initial solution a dual feasible solution which is not necessarily a basic solution.
Convergence condition of this algorithm is investigated. Perturbation method as a resolution of cycling is developed.
Results of test runs with 25 randomly generated problems are presented.
線型計劃法을 푸는 解法은 이미 單體法(Simplex Method)을 爲始하여 相當히 開發되어 있고 商用化되어 있는 段階이므로, 이를 위해 보다 나은 解法을 提示함은 매우 挑戰的이라 보겠다. 問題는 이러한 先入觀 때문에 重要한 數理計劃法의 한 分野인 線型計劃法의 解法의 硏究가 소강상태가 있었음을 否認할 수 없다는 데 있다.
本 論文에서는 任意의 雙對實行可能解(dual feasible solution)에서 出發하여 雙對實行可能性과 相補的餘有性條件(complementary slackness condition)을 滿足시키면서 原實行可能性(primal feasibility)이 滿足될 때까지 反復段階(iteration)를 繼續하는 非頂邊形解法(non-edge-following algorithm)을 提示하고, 그 解法이 收斂하기 위한 條件과 그 條件이 만족되지 않을 경우에 對한 解決方案으로서의 攝動法(perturbation method)을 提示했다.
이 解法의 計算上 能率에 對한 理論的으로 明確한 結果를 얻지는 못했지만 最小限 25個의 無作爲로 作成된 問題에 對해서는 좋은 計算結果를 보여 주었다.
