線性規(guī)劃的一般求解方法——單純形法

第三章 線性規(guī)劃的一般求解方法 ——單純形法
它的一般形式為：

稱為約束條件(Subject to)。 稱為變量的非負約束條件。其余的變量可取正值、負值、或零值，稱這樣的變量為符號無限制變量或自由變量。 線性規(guī)劃模型的特征是：一組決策變量 ，一組約束條件。一個目標函數(shù)。目標函數(shù)和約束條件都是線性的。

二、線性規(guī)劃問題的標準行式是什么？ 如何將一個LP問題的一般形式轉(zhuǎn)換為 標準形式？ (1)、這里規(guī)定的標準形式為：

簡記為：
用矩陣表示為：
用列向量表示為：
（2）為了把一般形式的LP變換為標準形式，必須消除其不等式約束和符號無限制變量。
目標函數(shù)的轉(zhuǎn)換
約束條件的轉(zhuǎn)換
變量的非負約束的轉(zhuǎn)換
任何形式的線性規(guī)劃數(shù)學(xué)模型都可以轉(zhuǎn)換成標準型的線性規(guī)劃


三、什么是可行解、可行域，可行域的幾何結(jié)構(gòu)？
滿足所有約束條件的決策變量，稱為可行解或可行點(feasible point)。
使目標函數(shù)值最大的可行解稱為最優(yōu)解
所有可行點組成的集合稱為可行域（feasible region），記為D.
給定一個LP問題可行域D,下列三種情況必居其一
D = ø 稱該問題無解或不可行。 D ø 且可行域有界。則線性規(guī)劃問題一定存在最優(yōu)解。這時最優(yōu)解唯一，也可能有無窮多。 D ø， 且可行域為無界，則線性規(guī)劃問題或者有最優(yōu)解（唯一或無窮多）也可能沒有有限的最優(yōu)解。 當可行域非空時，可行域的幾何結(jié)構(gòu)為(多面)凸集
四、基本解、基本可行解 (basic solution、basic feasible solution)



五、 LP問題的幾何意義（單純形表的數(shù)學(xué)原理）
若線性規(guī)劃問題存在可行域，則其可行域D是凸集
線性規(guī)劃問題的可行解為基可行解的充要條件是的正分量所對應(yīng)的系數(shù)列向量線性無關(guān)。
X是基本可行解的充分必要條件是X是可行域D的頂點
一個標準的LP問題，若有可行解，則至少有一個基本可行解
一個標準的LP問題，若有有限的最優(yōu)值，則一定存在一個基本可行解是最優(yōu)解。


X是基本可行解的充分必要條件是X是可行域D的頂點

由以上定理可知，最優(yōu)解一定在某一基本可行解處達到。因此單純形法的基本思想是：先找一個基本可行解，然后判斷它是否為最優(yōu)解，如不是，就找一個更好的基本可行解，再進行判斷，如此迭代進行，直到找到最優(yōu)解或者判斷該問題無界。
1．單純形表 為了計算的方便，我們可以將單純形法的全部計算過程在一個類似增廣矩陣的數(shù)表上進行，這種表格稱單純形表，不同的教材設(shè)計表格稍有不同，這里設(shè)計如下：
2．  單純形方法步驟

 Step1　轉(zhuǎn)換一般的LP模型為標準型。
Step2 　找一個初始可行基。
Step3 　計算單純形表中的各矩陣。
Step4 構(gòu)造單純形表。
Step5 判斷最優(yōu)解，是，則結(jié)束。否　　　　 則，轉(zhuǎn)入下一步。
Step6 換基迭代，返回Step5。

如何得到第一個基本可行解？ 為了得到初始基本可行解，要首先找到初始基本可行基，設(shè)B為約束矩陣的一個m階子式，如果B非奇異，則矩陣B是一個基， 進一步，若 ，那么B是初始基本可行基。 就是初始基本可行解。找初始基本可行基的方法如下 1．觀察法與試驗法。2.大M法。3.兩階段法
如何判斷基本可行解是最優(yōu)解？ 對線性規(guī)劃問題的求解結(jié)果可能出現(xiàn)唯一最優(yōu)解、無窮多最優(yōu)解、無界解和無可行解四種情況，



——掌握線性規(guī)劃問題的數(shù)學(xué)原理及代數(shù)的單純形解法是學(xué)習(xí)LP的最高境界。 ——掌握這一方法對于以后的學(xué)習(xí)大有裨益，希望同學(xué)們發(fā)揚十二分的耐心和鉆研精神。


2、寫出初始單純形表

3、判斷基本可行解是最優(yōu)解 由于檢驗數(shù)有正數(shù)，且對應(yīng)的列向量不全為負，故進行換基迭代，
4、換基迭代 選上表中的　為軸心項
5、判斷、由于檢驗數(shù)有正數(shù)且對應(yīng)的列向量不全為負，故進行換基迭代，選上表中的　為軸心項
由單純形表得一基最優(yōu)解， 由于有非基變量的檢驗數(shù)為零，則此線性規(guī)劃有無窮解。選上表中的 為軸心項.
原線性規(guī)劃所有最優(yōu)解為：
如何用QM軟件求解LP問題 三角洲航空公司的航班配置問題（怎樣為各條航線分配班機和為乘客分配座位）。用LP模型解決，用到60000個變量，40000個約束條件。
課堂練習(xí) A、用單純形法求解兩個變量的LP問題。 B、用QM軟件求解LP問題
謝謝

線性規(guī)劃的一般求解方法——單純形法