线性规划—单形法(Simplexmethod).PDF

第四章 線性規劃—單形法 (Simplex method) 線性規劃的代數 求解方法—單形法 (simplex method) 單形法是。 George Dantzig 於1947 年所發展出 來的方法，至今仍是求解線性規劃問題最主要的方法。不論對於數個變數與限制式的小問題 ，或是成 千上萬個變數與限制式的大問題 ，單形法均能有效地予以求解 。由於其優越性 ，這些年來發展出許多 功能強大的單形法電腦軟體 ，並在學術界與實務界廣泛地使用。 (1) 理論 考慮一個 n個變數 m個限制式的線性規劃問題 ： max z=c x +c x +…+c x 1 1 2 2 n n s.t. a x +a x +…+a x ≦b 11 1 12 2 1n n 1 a x +a x +…+a x ≦b 2 1 1 22 2 2n n 2  a x +a x +…+a x ≦b n 1 1 n2 2 mn n m x ,x ,…,x ≧0 1 2 n 可以寫成線性規劃的標準式為 max z=c x +c x +…+ c x 1 1 2 2 n n s.t. a x +a x +…+a x +x =b 11 1 12 2 1n n n+1 1 a x +a x +…+a x +x =b 2 1 1 22 2 2n n n+2 2  a x +a x +…+a x +x =b n 1 1 n2 2 mn n n+m m x ,x ,…,x , x , x …, x ≧0 1 2 n n+1 n+2, n+m 定義： (i) 對於具有m個等式限制式( ) 、n+m個變數的標準式 ，我們可讓n個變數為零 ，而聯立求解剩餘的m 個等式 、m個變數問題 。我們稱所得到的解為基解(basic solution) 。 (ii) 若得到的所有變數均滿足非負限制式 ，則此基解稱為可行基解 (basic feasible solution ；BFS) 。 (iii) 若兩個 BFS僅有一個非基變數不同( 亦即僅有一個基變數不同) ，則此兩 BFS是相鄰(adjacent) 。 性質1 ：對於一個具有最佳解的線性規劃問題 ，一定存在一個為最佳解的BFS 。 性質2 ：BFS的個數是有限的 。 性質