線性規(guī)劃LP線性規(guī)劃是一種對問題進(jìn)行求解方法

1、第三章第三章 線性規(guī)劃的一般求解方法線性規(guī)劃的一般求解方法 單純形法單純形法它的一般形式為：它的一般形式為：0, 2 , 1cminmax(21221111kjjjiininiiiinnxxxmibxaxaxaxcxz），（或）或其中，其中， , ， 是已知數(shù)，是已知數(shù)， 是待決策的變量。是待決策的變量。ijaibjcjx一、線性規(guī)劃問題的一般形式一、線性規(guī)劃問題的一般形式nnxcx11c稱為目標(biāo)函數(shù)(objective function), jc稱為價值系數(shù)(cost coefficient),向量),(21ncccc稱為價值向量。由系數(shù)ija組成的矩陣， mnmnaaaaa1111 稱為約

2、束矩陣(constraints matrix)， 列向量tmbbb),(1稱為右端向量（right-hand-side vector），ininiibxaxaxa），（或2211，mi, 2 , 1和 一般情況下一般情況下 m m n n , , m m , , n n 為正整數(shù)為正整數(shù), ,分別表示約束條件的個數(shù)和決策變量的個數(shù)分別表示約束條件的個數(shù)和決策變量的個數(shù), , 稱為約束條件稱為約束條件( (subject to)subject to)。 稱為變量的非負(fù)約束條件。其余稱為變量的非負(fù)約束條件。其余的變量可取正值、負(fù)值、或零值，稱這樣的變量的變量可取正值、負(fù)值、或零值，稱這樣的變量為符

3、號無限制變量或自由變量。為符號無限制變量或自由變量。線性規(guī)劃模型的特征是：一組決策變量線性規(guī)劃模型的特征是：一組決策變量 ，一組，一組約束條件。一個目標(biāo)函數(shù)。目標(biāo)函數(shù)和約束條件約束條件。一個目標(biāo)函數(shù)。目標(biāo)函數(shù)和約束條件都是線性的。都是線性的。0,21kjjjxxxklxlj, 1, 0由前面一般形式可知由前面一般形式可知, ,線性規(guī)劃問題可能有各線性規(guī)劃問題可能有各種不同的形式。目標(biāo)函數(shù)有實(shí)現(xiàn)最大化也有實(shí)種不同的形式。目標(biāo)函數(shù)有實(shí)現(xiàn)最大化也有實(shí)現(xiàn)最小化的現(xiàn)最小化的; ;約束條件可以是約束條件可以是“ ” ”形式、形式、“ ”形式不等式形式不等式, ,有的是等式有的是等式 決策變量有時有非負(fù)限制

4、有時沒有。這決策變量有時有非負(fù)限制有時沒有。這種多樣性給討論問題代來了不便。為了便種多樣性給討論問題代來了不便。為了便于今后討論，我們就要規(guī)定線性規(guī)劃問題于今后討論，我們就要規(guī)定線性規(guī)劃問題的標(biāo)準(zhǔn)型的標(biāo)準(zhǔn)型二、線性規(guī)劃問題的標(biāo)準(zhǔn)行式是什么？二、線性規(guī)劃問題的標(biāo)準(zhǔn)行式是什么？如何將一個如何將一個lplp問題的一般形式轉(zhuǎn)換為問題的一般形式轉(zhuǎn)換為標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式？(1)(1)、這里規(guī)定的標(biāo)準(zhǔn)形式為：這里規(guī)定的標(biāo)準(zhǔn)形式為： 021221122222121112121112211nmnmnmmnnnnnnx,x,xbxaxaxabxaxaxabxaxaxaxcxcxczmin 這里我們假設(shè)這里我們假設(shè)

5、b bi i 0 ( 0 ( i i = 1,2,= 1,2, ,m m),),否否則兩端同時乘以則兩端同時乘以“-1”“-1”。njxmibxatsxczjnjijijnjjj, 2 , 1, 0,2 , 1. .min11簡記為簡記為：0. .minxbaxt scxz用矩陣表示為用矩陣表示為：0min1xbpxcxznjjjmjjjjaaap21用列向量表示為：用列向量表示為：（2 2）為了把一般形式的）為了把一般形式的lplp變換為標(biāo)準(zhǔn)變換為標(biāo)準(zhǔn)形式，必須消除其不等式約束和符號形式，必須消除其不等式約束和符號無限制變量。無限制變量。 目標(biāo)函數(shù)的轉(zhuǎn)換目標(biāo)函數(shù)的轉(zhuǎn)換 約束條件的轉(zhuǎn)換約束條件

6、的轉(zhuǎn)換 變量的非負(fù)約束的轉(zhuǎn)換變量的非負(fù)約束的轉(zhuǎn)換 任何形式的線性規(guī)劃數(shù)學(xué)模型都可以轉(zhuǎn)任何形式的線性規(guī)劃數(shù)學(xué)模型都可以轉(zhuǎn)換成標(biāo)準(zhǔn)型的線性規(guī)劃換成標(biāo)準(zhǔn)型的線性規(guī)劃 例例4: 4: 試將如下線性規(guī)劃問題化成標(biāo)準(zhǔn)型試將如下線性規(guī)劃問題化成標(biāo)準(zhǔn)型無限制32132132132132103523221732x,x,x)(xxx)(xxx)(xxxxxxzmin解：令解：令 x x3 3 = = x x4 4 - - x x5 5 , , x x4 4 , , x x5 5 0 , (1) 0 , (1)式左式左端加上非負(fù)松弛變量端加上非負(fù)松弛變量 x x6 6 , (2) , (2)式左端減去非負(fù)剩余式左端

7、減去非負(fù)剩余變量變量 x x7 7 , , 則可將上述線性規(guī)劃問題化成如下的標(biāo)準(zhǔn)則可將上述線性規(guī)劃問題化成如下的標(biāo)準(zhǔn)型型: :05223270033272154217542165421765421x,x,xxxxxxxxxxxxxxxxxxxxxzmin三、什么是可行解、可行域，三、什么是可行解、可行域，可行域的幾何結(jié)構(gòu)？可行域的幾何結(jié)構(gòu)？ 滿足所有約束條件的決策變量，稱為可滿足所有約束條件的決策變量，稱為可行解或可行點(diǎn)行解或可行點(diǎn)( (feasible point)feasible point)。使目標(biāo)函數(shù)值最大的可行解使目標(biāo)函數(shù)值最大的可行解稱稱為最優(yōu)解為最優(yōu)解所有可行點(diǎn)組成的集合稱為 可

8、 行 域所有可行點(diǎn)組成的集合稱為 可 行 域（feasible regionfeasible region），），記為記為d.d.給定一個給定一個lplp問題問題可行域可行域d,d,下列三種情況下列三種情況必居其一必居其一 d = d = 稱該問題無解或不可行。稱該問題無解或不可行。d d 且可行域有界。則線性規(guī)劃問題一且可行域有界。則線性規(guī)劃問題一定存在最優(yōu)解。這時最優(yōu)解唯一，也可能有定存在最優(yōu)解。這時最優(yōu)解唯一，也可能有無窮多。無窮多。d d ， 且可行域?yàn)闊o界，則線性規(guī)劃問題且可行域?yàn)闊o界，則線性規(guī)劃問題或者有最優(yōu)解（唯一或無窮多）也可能沒有或者有最優(yōu)解（唯一或無窮多）也可能沒有有限的最

9、優(yōu)解。有限的最優(yōu)解。當(dāng)可行域非空時，可行域的幾何結(jié)構(gòu)為當(dāng)可行域非空時，可行域的幾何結(jié)構(gòu)為( (多多面面) )凸集凸集 四、基本解、基本可行解四、基本解、基本可行解 (basic solution、basic feasible solution)0xbax. t .scxzmin秩（秩（a a）=m=m，則矩陣則矩陣a a中存在一個中存在一個m m階滿秩階滿秩子方陣子方陣b b。稱稱b b矩陣為線性規(guī)劃問題的一個基。矩陣為線性規(guī)劃問題的一個基。故 a 中必有 m 個線性無關(guān)的列向量。 構(gòu)成滿秩方陣 b,把 a中其余各列組成的子陣記為 n,再把tnxxxx),(21分量也相應(yīng)的分為兩部分， 記為b

10、x和nx， 則bax 可 重 寫 為 ；bnxbxnb， 由 于 b 非 奇 異 ， 則nbnxbbbx11 令0nx， 就 得 到 約 束 方 程 組 的 一 種 特 殊 形 式 的 解01bbx，稱這一解為相應(yīng)于 b 的基本解。 當(dāng)01bb時，稱基本解為基本可行解。這是對應(yīng)的基 b 稱為可行基。由此可知；基的數(shù)目最多為mnc個，基解的數(shù)目最多也為mnc個，一般基本可行解的數(shù)目要小于基解的數(shù)目。 解之間的關(guān)系解之間的關(guān)系可行解：滿足約束條件可行解：滿足約束條件最優(yōu)解：滿足約束條件，同時使目標(biāo)函數(shù)值最優(yōu)。最優(yōu)解：滿足約束條件，同時使目標(biāo)函數(shù)值最優(yōu)。基礎(chǔ)解：滿足基礎(chǔ)解：滿足 且非零分量的數(shù)目不大

11、且非零分量的數(shù)目不大于方程的個數(shù)于方程的個數(shù)m m?；尚薪猓菏腔A(chǔ)解又是可行解。基可行解：是基礎(chǔ)解又是可行解。基最優(yōu)解：滿足約束條件，且無非零分量，或非基最優(yōu)解：滿足約束條件，且無非零分量，或非零分量對應(yīng)的列向量現(xiàn)性無關(guān)，同時使目標(biāo)函數(shù)零分量對應(yīng)的列向量現(xiàn)性無關(guān)，同時使目標(biāo)函數(shù)值最優(yōu)。值最優(yōu)。0xbax, bax 五、五、 lp問題的幾何意義（單純問題的幾何意義（單純形表的數(shù)學(xué)原理）形表的數(shù)學(xué)原理） 若線性規(guī)劃問題存在可行域，則其可行域若線性規(guī)劃問題存在可行域，則其可行域d d是凸集是凸集線性規(guī)劃問題的可行解為基可行解的充要條件是的正線性規(guī)劃問題的可行解為基可行解的充要條件是的正分量所對應(yīng)的

12、系數(shù)列向量線性無關(guān)分量所對應(yīng)的系數(shù)列向量線性無關(guān)。x x是基本可行解的充分必要條件是是基本可行解的充分必要條件是x x是可行域是可行域d d的頂點(diǎn)的頂點(diǎn) 一個標(biāo)準(zhǔn)的一個標(biāo)準(zhǔn)的lplp問題，若有可行解，則至少有一個基本問題，若有可行解，則至少有一個基本可行解可行解 一個標(biāo)準(zhǔn)的一個標(biāo)準(zhǔn)的lplp問題，若有有限的最優(yōu)值，則一定存在問題，若有有限的最優(yōu)值，則一定存在一個基本可行解是最優(yōu)解。一個基本可行解是最優(yōu)解。 若線性規(guī)劃問題存在可行域，則其可行域若線性規(guī)劃問題存在可行域，則其可行域d d是凸集是凸集證明：只需證明 d 上的任意兩點(diǎn)為端點(diǎn)的線段上的點(diǎn)全部屬于 d。 對于任意給定的1 , 0，令21)

13、1 (xxx 則 21)1 (axaxaxbb)1 ( b 顯然，0x。 說明 x 滿足 lp 問題的約束條件，因此dx 。證完 線性規(guī)劃問題的可行解線性規(guī)劃問題的可行解x x為基可行解的充要條件是為基可行解的充要條件是x x的正分量所對應(yīng)的系數(shù)列向量線性無關(guān)的正分量所對應(yīng)的系數(shù)列向量線性無關(guān)。證明： （1）必要性，由基可行解的定義知。 （2）充分性，若向量kppp,21線性獨(dú)立，則必有，mk ；當(dāng)mk 時，他們恰構(gòu)成一個基，從而)0 , 0 ,(, 21kxxxx 為相應(yīng)的基可行解。當(dāng)mk 時，則一定可以從其余的基向量中km個與kppp,21構(gòu)成最大的線性獨(dú)立向量組，其對應(yīng)的解恰為x，所以根

14、據(jù)定義它是基可行解。 x x是基本可行解的充分必要條件是是基本可行解的充分必要條件是x x是可行域是可行域d d的頂點(diǎn)的頂點(diǎn) 證明：充分性。設(shè)x是 d 的頂點(diǎn)，則x滿足約束條件，x是一可行解，仍設(shè)x的前k 個分量取正值。即)0 , 0 ,(, 21kxxxx 。則其正分量對應(yīng)的系數(shù)列向量kppp,21一定線性無關(guān)。從而，由定理 2 知x為基本可行解。 這一部分是線性規(guī)劃部分的基本定理，也是單純形法求解lp 問題的數(shù)學(xué)原理。通過這一部分的學(xué)習(xí)，一定要清楚線性規(guī)劃問題的可行解、基可行解、最優(yōu)解的幾何意義。即線性規(guī)劃問題的所有可行解構(gòu)成的集合是凸集，也可能為無界域，他們有有限個頂點(diǎn)，線性規(guī)劃問題的每

15、個基可行解對應(yīng)可行域的一個頂點(diǎn)；若線性規(guī)劃問題有最優(yōu)解，則在某個定點(diǎn)上達(dá)到。 雖然頂點(diǎn)數(shù)目是有限的 （不多于mnc個） ，若采取“枚舉法”找所有的基可行解，然后一一比較，最終可以找到最優(yōu)解。 但當(dāng)nm,較大時這種方法是行不通的，如何有效的找到最優(yōu)解，這就是單純形法。 由以上定理可知，最優(yōu)解一定在某一基本可行解處達(dá)到。因此單純形法的基本思想是：先找一個基本可行解，然后判斷它是否為最優(yōu)解，如不是，就找一個更好的基本可行解，再進(jìn)行判斷，如此迭代進(jìn)行，直到找到最優(yōu)解或者判斷該問題無界。六、單純形法六、單純形法( (simplex method)simplex method)1 1單純形表單純形表為了計(jì)

16、算的方便，我們可以將單純形法的全部計(jì)為了計(jì)算的方便，我們可以將單純形法的全部計(jì)算過程在一個類似增廣矩陣的數(shù)表上進(jìn)行，這種算過程在一個類似增廣矩陣的數(shù)表上進(jìn)行，這種表格稱單純形表，不同的教材設(shè)計(jì)表格稍有不同，表格稱單純形表，不同的教材設(shè)計(jì)表格稍有不同，這里設(shè)計(jì)如下：這里設(shè)計(jì)如下： x z bbcb1 cabcb1 bx bb1 ab1 2 單純形方法步驟 step1step1轉(zhuǎn)換一般的轉(zhuǎn)換一般的lplp模型為標(biāo)準(zhǔn)型。模型為標(biāo)準(zhǔn)型。step2 step2 找一個初始可行基。找一個初始可行基。step3 step3 計(jì)算單純形表中的各矩陣。計(jì)算單純形表中的各矩陣。step4 step4 構(gòu)造單純形表

17、。構(gòu)造單純形表。step5 step5 判斷最優(yōu)解，是，則結(jié)束。否判斷最優(yōu)解，是，則結(jié)束。否 則，轉(zhuǎn)入下一步。則，轉(zhuǎn)入下一步。step6 step6 換基迭代，返回?fù)Q基迭代，返回step5step5。q 如何得到第一個基本可行解？如何得到第一個基本可行解？ 為了得到初始基本可行解，要首先找到初始基本可為了得到初始基本可行解，要首先找到初始基本可行基，設(shè)行基，設(shè)b b為約束矩陣的一個為約束矩陣的一個m m階子式，如果階子式，如果b b非奇非奇異，則矩陣異，則矩陣b b是一個基，是一個基，進(jìn)一步，若進(jìn)一步，若 ，那么，那么b b是初始基本可行基。是初始基本可行基。 就是初始基本可行解。找初始基本可

18、行基就是初始基本可行解。找初始基本可行基的方法如下的方法如下1 1觀察法與試驗(yàn)法。觀察法與試驗(yàn)法。2.2.大大m m法。法。3.3.兩階段法兩階段法01bb01bbq如何判斷基本可行解是最優(yōu)解如何判斷基本可行解是最優(yōu)解？對線性規(guī)劃問題的求解結(jié)果可能出現(xiàn)唯對線性規(guī)劃問題的求解結(jié)果可能出現(xiàn)唯一最優(yōu)解、無窮多最優(yōu)解、無界解和無一最優(yōu)解、無窮多最優(yōu)解、無界解和無可行解四種情況，可行解四種情況，標(biāo)準(zhǔn)型 0, 0bxbaxcxmaxz 0, 0bxbaxcxminz 檢驗(yàn)向量 cabcb1 cabcb1 判別結(jié)果 0 時，則 b 為最優(yōu)基，基本可行解01bb就 是 最優(yōu) 解，1bcb就 是 最 優(yōu)值。 當(dāng)

19、0 又存在某個非基變量的檢驗(yàn)數(shù)為零，則 lp 問題有無窮多解。 當(dāng) 檢 驗(yàn) 數(shù) 中 某 一 個 分 量0k同 時 有01kpb，則原問題無界。 0時，則 b 為最優(yōu)基，基本可行解01bb就是最優(yōu)解，1bcb就是最優(yōu)值。 當(dāng)0，又存在某個非基變量的檢驗(yàn)數(shù)為零，則 lp 問題有無窮多解。當(dāng)檢驗(yàn)數(shù)中某一個分量0k同時有01kpb，則原問題無界。 檢驗(yàn)向量 abccb1 abccb1 判別結(jié)果 0時，則 b 為最優(yōu)基，基本可行解01bb就是最優(yōu)解，bbcb1就是最優(yōu)值。 當(dāng)0， 又存在某個非基變量的檢驗(yàn)數(shù)為零，則 lp 問題有無窮多解。 當(dāng)檢驗(yàn)數(shù)中某一個分量0k同時有01kpb，則原問題無界。 0時，

20、則 b 為最優(yōu)基，基本可行解01bb就是最優(yōu)解，bbcb1就是最優(yōu)值。 當(dāng)0，又存在某個非基變量的檢驗(yàn)數(shù)為零，則 lp 問題有無窮多解。 當(dāng)檢驗(yàn)數(shù)中某一個分量0k同時有01kpb，則原問題無界。 找入基變量找入基變量 找出基變量找出基變量 定軸心項(xiàng)定軸心項(xiàng) 作行變換作行變換 交換變量交換變量 q如何進(jìn)行換基迭代如何進(jìn)行換基迭代掌握線性規(guī)劃問題的數(shù)學(xué)原理及代數(shù)掌握線性規(guī)劃問題的數(shù)學(xué)原理及代數(shù)的單純形解法是學(xué)習(xí)的單純形解法是學(xué)習(xí)lplp的最高境界。的最高境界。掌握這一方法對于以后的學(xué)習(xí)大有裨掌握這一方法對于以后的學(xué)習(xí)大有裨益，希望同學(xué)們發(fā)揚(yáng)十二分的耐心和鉆研益，希望同學(xué)們發(fā)揚(yáng)十二分的耐心和鉆研精神

21、。精神。例題、用單純形法求解例題、用單純形法求解0,92542max21212121xxxxxxxxs化為滿秩標(biāo)準(zhǔn)形化為滿秩標(biāo)準(zhǔn)形 0,9254)2min(min54321521423121xxxxxxxxxxxxxxs100120101000101a954b00012 cccabcaabbbccbbb111, 0,0002、寫出初始單純形表寫出初始單純形表 取543pppb ， |b|0 ， 且09541bb，因此，b為可行基 54321xxxxx jjcz 0 00012 543xxx 954 100120101000101 3、判斷基本可行解是最優(yōu)解判斷基本可行解是最優(yōu)解由于檢驗(yàn)數(shù)有正數(shù)

22、，且對應(yīng)的列向量不全為負(fù)，故進(jìn)行換基迭代，4、換基迭代、換基迭代 選上表中的為軸心項(xiàng)選上表中的為軸心項(xiàng) 1 54321xxxxx jjcz -8 00210 541xxx 154 102100101000101 5、判斷、判斷、由于檢驗(yàn)數(shù)有正數(shù)且對應(yīng)的由于檢驗(yàn)數(shù)有正數(shù)且對應(yīng)的列向量不全為負(fù)，故進(jìn)行換基迭代，選上列向量不全為負(fù)，故進(jìn)行換基迭代，選上表中的為軸心項(xiàng)表中的為軸心項(xiàng) 1 54321xxxxx jjcz -9 10000 241xxx 144 102101120000101 由單純形表得一基最優(yōu)解，由單純形表得一基最優(yōu)解，由于有非基變量的檢驗(yàn)數(shù)為零，則此線性由于有非基變量的檢驗(yàn)數(shù)為零，則此線性規(guī)劃有無窮解。選上表中的規(guī)劃有無窮解。選上表中的 為軸心項(xiàng)為軸心項(xiàng). .t040142 54321xxxxx jjcz -9 10000 231xxx 522 0101021211002121001 原線性規(guī)劃所有最優(yōu)解為：原線性規(guī)劃所有最優(yōu)解為： t)(00252),()()(tt010025204014212121由此表的另一最優(yōu)解由此表的另一最優(yōu)解所有最優(yōu)解為：