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

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

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

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

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


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



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


X是基本可行解的充分必要條件是X是可行域D的頂點(diǎn)

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

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

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



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


2、寫(xiě)出初始單純形表

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

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