線性規劃 (Linear programming, 簡稱LP) , 應用非常廣泛, 其普遍應用于軍事, 產
業經濟、運輸, 能資源分配、社會問題, ……等一般領域, 其重要性顯而可見。而最
常用來解 LP 問題的方法是簡算法 (Simplex Method) , 自發展出來到現在四十餘年
, 仍為實務上所廣為使用。它是一反覆 (iterative)求解的程序, 每一步驟為些簡單
的計算, 但其最壞的情況下, 反覆之次數是指數形式的。因而我們想提供給簡算法一
較好的起始可行解, 如此可以減少反覆之次數, 執行效率就更高了, 最壞的情況就不
致于發生了。
本研究的目的,就是想找到一較靠近最佳解之可行解, 提供為Simplex Method 的起始
解。研究結果, 我們提出一方法于 O( )時間內可找到 LP 問題的一可行解; 第四
章我們提出一方法, 使用 O(mn)的時間, 由此可行解出發, 找到一較靠近最佳解之可
行解。此較靠近最佳解之可行解, 除了可提供給簡算法較好的起始解外, 還可提供給
其他的演算法一好的起始可行解。
我們的方法, 是隨意取一點 , 若 點是在polytope 上, 即為一可行解; 但若 是在
polytope外, 則拉到 polytope 之面上于 過 p點, 取—2 維平面, 切 Polytope ,
在切出來之 convex polygon 上找出最低點 q; 再過此最低點 q取另—2 維平面切po
lytope, 找出切面之最低點; ……; 如此反覆幾次后, 我們便可以找到一蠻靠近最佳
點之一可行點了。