第1章線性規(guī)劃及單純型法

1、第1章線性規(guī)劃及單純型法 例: 生產計劃問題III資資 源源 限限 量量設設 備備原原 材材 料料 A原原 材材 料料 B1402048 臺臺 時時16kg12kg利利 潤潤23產品產品I產品產品2x1x2x1x2zIII資源限量資源限量設備設備原材料原材料 A原材料原材料 B1402048 臺時臺時16kg12kg利潤利潤23 0,.,),(.),(.),(.)min(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxczMax0,., 0,.,. 2121221122222121112121112211m

2、nmnmnmmnnnnnnbbbxxxbxaxaxabxaxaxabxaxaxaxcxcxcZMax目標函數(shù)最大目標函數(shù)最大約束條件等式約束條件等式?jīng)Q策變量非負決策變量非負 njxmibxaxcZjinjjijnijj,.,2 , 1 0,.2 , 1 max11 ),.cc,(cC ,.2, 1 0max212121n211 b.bb ba.aa Px.xxXnjxbxPCXZmmjjjjnjnijj其中： 0.000 ),.,( . 0 max 211111nmnmnPPPaaaaAXbAXCXZ決策變量向量 -X 價值向量 -C 資源向量0.000 ),.,( . 0 max 32111

3、11bPPPaaaaAXbAXCXZmnmnC C價值向量價值向量b b資源向量資源向量X X決策變量向量決策變量向量 0,12 4 16 48 200032max54321524132154321xxxxxxxxxxxxxxxxxz 無約束321321321321321,0,7232 7 32minxxxxxxxxxxxxxxxzMax x6 x7543xxxkx0, kkkkkxxxxx令 ：標準形為0,7 )(232 )( 7 )( 00)( 32max76542154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxz距離AB需求量X10445Y5

4、875Z61540供應量60100供需平衡供需平衡線性規(guī)劃模型舉例( (一一) ) 運輸問題運輸問題( (二二) ) 布局問題布局問題( (三三) ) 分派問題分派問題( (四四) ) 生產計劃問題生產計劃問題( (五五) ) 合理下料問題合理下料問題線性規(guī)劃模型的條件線性規(guī)劃模型的條件 （1 1）要求解問題的目標函數(shù)能用數(shù)）要求解問題的目標函數(shù)能用數(shù)值指標來反映，且為線性函數(shù)；值指標來反映，且為線性函數(shù)； （2 2）存在著多種方案；）存在著多種方案； （3 3）要求達到的目標是在一定約束）要求達到的目標是在一定約束條件下實現(xiàn)的，這些約束條件可用條件下實現(xiàn)的，這些約束條件可用線性等式或不等式來

5、描述。線性等式或不等式來描述。( (一一) ) 運輸問題運輸問題 設某種物資有設某種物資有m m個產地，個產地，A A1 1，A A2 2，A A m m；聯(lián)合供應聯(lián)合供應n n個銷地：個銷地：B B1 1，B B2 2，B Bn n。各產地產量（單位：噸），各銷地銷量（單位：各產地產量（單位：噸），各銷地銷量（單位：噸），各產地至各銷地單位運價（單位：元噸），各產地至各銷地單位運價（單位：元噸）如下表所示。噸）如下表所示。應如何調運，應如何調運，才使總運費最才使總運費最少？少？單價（元噸）單價（元噸）銷銷 地地產產 地地產量（噸）產量（噸） B1 B2 BnA1A2 Am銷量（噸）銷量（噸）

6、 C11 C12 C1n C21 C22 C2n Cm1 Cm2 Cmn b1 b2 bna1a2 am minjjiba11即即( (一一) ) 運輸問題運輸問題()()產銷平衡產銷平衡()()產銷平衡產銷平衡()()產銷不平衡產銷不平衡約束條件約束條件產地產地A Ai i發(fā)到各銷地的發(fā)量發(fā)到各銷地的發(fā)量總和應等于總和應等于A Ai i的產量的產量各產地各產地發(fā)到銷地發(fā)到銷地B Bj j的發(fā)量的發(fā)量總和應等于總和應等于B Bj j的銷量的銷量調運調運量不能為負數(shù)量不能為負數(shù)0約束條件約束條件產地產地A Ai i發(fā)到各銷地的發(fā)量發(fā)到各銷地的發(fā)量總和應等于總和應等于A Ai i的產量的產量各產地

7、各產地發(fā)到銷地發(fā)到銷地B Bj j的發(fā)量的發(fā)量總和應等于總和應等于B Bj j的銷量的銷量調運調運量不能為負數(shù)量不能為負數(shù)0njmixnjbxmiaxijijiijmijnj, 1;, 2 , 1 0, 2 , 1 , 2 , 1 11 約束條件約束條件njmixnjbxmiaxijijiijmijnj, 1;, 2 , 1 0, 2 , 1 , 2 , 1 11 njmiijijxcs11 min。的值最小目標函數(shù)m11injjiba即這一問題的數(shù)學模型應為： 求一組變量 的值,使它滿足njmixij, 2 , 1;, 2 , 1()()產銷不平衡產銷不平衡產大于銷產大于銷( (一一) )

8、運輸問題運輸問題約束條件約束條件njmixnjbxmiaxijjijiijminj, 2 , 1;, 2 , 1 0, 2 , 1 , 2 , 1 11 產地產地A Ai i發(fā)到各銷地的發(fā)量發(fā)到各銷地的發(fā)量總和不超過總和不超過A Ai i的產量的產量各產地各產地發(fā)到銷地發(fā)到銷地B Bj j的發(fā)量的發(fā)量總和應等于總和應等于B Bi i的銷量的銷量調運調運量不能為負數(shù)量不能為負數(shù)njmiijijxcs11 min 目標函數(shù)產小于產小于銷的模銷的模型呢型呢（二）布局問題（二）布局問題 作物布局 在n塊地上種植m種作物，已知各塊土地 畝數(shù)、各種作物計劃播種面積及各種作 物在各塊的單產（每畝的產量）如表

9、 （與運輸問題相似），問：如何合理安排種植計劃，才使總產量最多。 單價（元噸）單價（元噸）銷銷 地地產產 地地產量（噸）產量（噸） B1 B2 BnA1A2 Am銷量（噸）銷量（噸） C11 C12 C1n C21 C22 C2n Cm1 Cm2 Cmn b1 b2 bna1a2 am（二）布局問題（二）布局問題( (三）分派問題三）分派問題 設有設有n n件工作件工作 分派給分派給n n人人 去做，去做，每人只做一件工作且每件工作只分每人只做一件工作且每件工作只分派一人去做。設派一人去做。設A Ai i完成完成B Bj j的工時為的工時為 。問：應如何分派才使完成全部工作問：應如何分派才使完

10、成全部工作的總工時最少。的總工時最少。nBBB,21nAAA,21njicij,2, 1,解：設解：設 為為B Bj j分派給人分派給人A Ai i情況：情況： B Bj j分派給分派給A Ai i時，時， ； 不分派給不分派給A Ai i時，時， 。 那末這一問題的數(shù)學模型為：那末這一問題的數(shù)學模型為：ijx1ijxnjicij, 2 , 1,0njixij, 2 , 1, 求一組變量求一組變量 的值，的值，使目標函數(shù)使目標函數(shù) 的值最小。的值最小。nimjijijxcs11 (完成全部工作的總工時最少完成全部工作的總工時最少）( (三）分派問題三）分派問題約束條件約束條件njixnixnj

11、xijijijnjni,2, 1, 1 0,2, 1 1,2, 1 111或每件工作只分派一人去做每件工作只分派一人去做每人只做一件工作每人只做一件工作每人對每件工作只有每人對每件工作只有做與不做兩種情況做與不做兩種情況分派問題的模型分派問題的模型nimjijijxcs11 min目標函數(shù)目標函數(shù) 設用某原材料設用某原材料( (條材或板材條材或板材) )下零件下零件 的毛坯的毛坯. .根據(jù)過去經(jīng)驗根據(jù)過去經(jīng)驗在一件原材料上有在一件原材料上有 種不同種不同的下料方式的下料方式, ,每種下料方式可得各種毛每種下料方式可得各種毛坯個數(shù)及每種零件需要量如下表所示。坯個數(shù)及每種零件需要量如下表所示。問：

12、應怎樣安排下料方式，使得既問：應怎樣安排下料方式，使得既 能滿足需要，用的原材料又最少。能滿足需要，用的原材料又最少。mAAA,21nBBB,21( (四四) )合理下料問題合理下料問題各方式下的零件個數(shù)各方式下的零件個數(shù)下下 料料 方方 式式零件零件 名稱名稱 B1 B2 BnA1A2 Am C11 C12 C1n C21 C22 C2n Cm1 Cm2 Cmn零件零件需要量需要量a1a2 am( (五五) )合理下料問題合理下料問題 解：解： 設用設用 種方式下料的原材料數(shù)種方式下料的原材料數(shù) 為為 （j=1,2,j=1,2,n),n)， 則這一問題的數(shù)學模型為：則這一問題的數(shù)學模型為：

13、jBjxnjjxs1的值最少使目標函數(shù)( (五五) )合理下料問題合理下料問題所用原材料數(shù)量最少所用原材料數(shù)量最少), 2 , 1( , 0 ), 2 , 1( 1njxmiaxcjijijnj整數(shù)iA（所下的（所下的 Ai 零件總數(shù)不能少于零件總數(shù)不能少于 ）ia（各種方式下料的原材料數(shù)不能是負（各種方式下料的原材料數(shù)不能是負數(shù)、分數(shù)）數(shù)、分數(shù)）( (五五) )合理下料問題的模型合理下料問題的模型約束條件約束條件njjxs1min目標函數(shù)目標函數(shù)線性規(guī)劃模型9 8 7 6 5 4 3 2 1 0 |123456789x1x2x1 + 2x2 8(0, 4)(8, 0)4x1 164 x2 1

14、29 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域可行域9 8 7 6 5 4 3 2 1 0 |123456789x1x2x1 + 2x2 84x1 164 x2 16可行域可行域BCDEA9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16BCDEA9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16BCDEAx1+ 2x2=8 4x1 =16x26 5 4 3 2 1 0 |123456789x

15、16 5 4 3 2 1 0 x2|123456789x1 x2x118 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 1618 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16可行域可行域ABCDE18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE (8,0)(0,6.8)

16、18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE (8,0)(0,6.8)x218 16 14 12 10 8 6 4 2 0 |24681012141618x14x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE (8,0)(0,6.8)4x1+ 6x2=48 2x1+ 2x2 =18v線性規(guī)劃解的概念線性規(guī)劃解的概念v線性規(guī)劃問題的幾何意義線性規(guī)劃問題的幾何意義 （單純形法原理）（單純形法原理） 標準型 可行解:滿足AX=b, X=0的解X稱為

17、線性規(guī)劃問題的可行解。 最優(yōu)解：使Z=CX達到最大值的可行解稱為最優(yōu)解。0 max XbAXCXZ 基：若B是矩陣A中mm階非奇異子矩陣（B0），則B是線性規(guī)劃問題的一個基。不妨設：),.,(,.,.,.,11111mmmmmPPaaaaBjPjXjX , j=1，2，,m 基向量。 ，j=1，2，,m 基變量。 , j=m+1,n 非基變量。 求解 nmnnmmmmmmmmmmxaaxaabbxaaxaa.111111111110 max XbAXCXZ 基本解：稱上面求出的X解為基本解。 基本可行解：非負的基本解X稱為基本可行解 可行基：對應基本可行解的基稱為可行基TmBxxxX).,(2

18、10.21nmmxxx)0,.,0,0,.,(21mbbbX T基變量令 可求出： 線性規(guī)劃解的關系圖可行解可行解 基本可行解基本可行解 最優(yōu)解？最優(yōu)解？ 例：求基本解、基本可行解、最優(yōu)解。max, ,.,zxxxxxxxxxxxii235210401251231312425x1x2x5x4x3z1 0 0 5 10 4 5 Y 2 0 4 5 2 0 17 Y 3 5 0 0 5 4 10 Y 4 0 5 5 0 -1 20 N5 10 0 -5 0 4 15 N6 5 2.5 0 0 1.5 17.5 Y 7 5 4 0 -3 0 22 N8 2 4 3 0 0 19 Y 是否基是否基可行

19、解可行解最優(yōu)解最優(yōu)解解：解： ：求基本解、基本可行解、最優(yōu)解。0,12 4 16 48 200032max54321524132154321xxxxxxxxxxxxxxxxxz3.的秩是A 1 0 0 4 00 1 0 0 40 0 1 2 1A練習：3 基本概念凸集：為凸集。K），則10（，KX ）1（X連線上的一切點KX，KX對維歐氏空間的一點集，n是k設）2（）1（）2（）1（ 頂點:若K是凸集，XK；若X不能用不同的兩點 的線性組合表示為： 則X為頂點. KXKX)2()1(和) 10( )1 ()2()1 (XXX凸集凸集 凸組合： .,.,., 1,.,2, 1, 10,.,.,)

20、()1()()2(21111)()1的凸組合為則使且若存在個點維向量空間中的是設（kkkkiiikkXXXXXXXkiknXXX n=2，k=3定理1: 若線性規(guī)劃問題存在可行域, 則其可行域: D=X|AX=b，X0 是凸集. 基本定理證明:0, , 0,)2()2()1()1()2()1()2()1(XbAXXbAXXXDXDX則有：設： bbbAXAXXXAAXXX )1 ( )1 ( )1 (0)2()1()2()1(代入約束條件，有：將顯然，1)(0 )1 ()2()1()2()1(XXXXXX：連線上的任意一點，則和為令只要驗證只要驗證X X在在D D中即可中即可是凸集。因此，DD

21、X, 引理：可行解X為基本可行解 X的正分量對應的列向量線性無關 定理3：若可行域有界，線性規(guī)劃 問題的目標函數(shù)一定可以在 其可行域的頂點上達到最優(yōu)。 定理2：線性規(guī)劃問題的基本可行解X 對應于可行域D的頂點。 幾點結論： 線性規(guī)劃問題的可行域是凸集。 基可行解與可行域的頂點一一對應，可行域有有限多個頂點。 最優(yōu)解必在頂點上得到。9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域可行域BCDEA可行域為凸集可行域為凸集目標函數(shù)不同時目標函數(shù)不同時等值線的斜率不同等值線的斜率不同最優(yōu)解在頂點產生最優(yōu)解在頂點產生 目標函數(shù)等目標

22、函數(shù)等值線的斜率值線的斜率最優(yōu)解最優(yōu)解9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域可行域BCDEA可行域為凸集可行域為凸集目標函數(shù)不同時目標函數(shù)不同時等值線的斜率不同等值線的斜率不同最優(yōu)解在頂點產生最優(yōu)解在頂點產生 目標函數(shù)等目標函數(shù)等值線的斜率值線的斜率最優(yōu)解最優(yōu)解9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域可行域BCDEA可行域為凸集可行域為凸集目標函數(shù)不同時目標函數(shù)不同時等值線的斜率不同等值線的斜率不同最優(yōu)解在頂點產生最優(yōu)解在頂點產生 目

23、標函數(shù)等目標函數(shù)等值線的斜率值線的斜率最優(yōu)解最優(yōu)解求解LP的基本思路1.3 單純形法原理 本節(jié)通過一個引例，可以了解利用本節(jié)通過一個引例，可以了解利用單純形法求解線性規(guī)劃問題的思路，并單純形法求解線性規(guī)劃問題的思路，并將每一次的結果與圖解法作一對比，其將每一次的結果與圖解法作一對比，其幾何意義更為清楚。幾何意義更為清楚。引例引例（上一章例）（上一章例）0,12 4 16 48 200032max54321524132154321xxxxxxxxxxxxxxxxxz求解線性規(guī)劃問題的基本思路1、構造初始可行基；2、求出一個基可行解（頂點）3、最優(yōu)性檢驗：判斷是否最優(yōu)解；4、基變化，轉2。要保證目

24、標函數(shù)值比 原來更優(yōu)。從線性規(guī)劃解的性質可知求解從線性規(guī)劃解的性質可知求解線性規(guī)劃問題的基本思路。線性規(guī)劃問題的基本思路。第1步 確定初始基可行解 1 0 00 1 00 0 1),(543PPPB令：1 0 0 4 00 1 0 0 40 0 1 2 1),.,(51PPA根據(jù)根據(jù)顯然顯然 ， 可構成初等可行基可構成初等可行基B 。543,PPP 為基變量543,xxx 第2步 求出基可行解 )12,16, 8 , 0 , 0(, 0320 )0()0(2121XXxxxxZ得一基可行解令：代入目標函數(shù) 4 12 416 2 8 2514213xxxxxxx基變量用非基基變量用非基變量表示，

25、并變量表示，并令非基變量為令非基變量為 0時對應的解時對應的解是否是最優(yōu)解？第3步 最優(yōu)性檢驗分析目標函數(shù)zxx02312檢驗數(shù)檢驗數(shù)0 時，時， 無解無解換基，繼續(xù)換基，繼續(xù)xxz1200 ,只要取只要取 或或 的的 值可能增大。值可能增大。換入？基變量換入？基變量換出？基變量換出？基變量考慮將考慮將 或或 換入為基變換入為基變量量21 xx第4步 基變換 換入基變量：zxxxx0230121122換入變量 x2（即選最大非負檢驗數(shù)對應的變量）一般選取一般選取 對應的變量),max(2121,xx, 02, 1均可均可換入。 換出變量使換入的變量越大越好同時，新的解要可行。選非負 的最小者對

26、應的變量換出i為換出變量52254233)4/12,2/8min( 04 12 0 16 02 8 xxxxxxx2x為換入變量，應換出 ？ 變量。為換出變量變量：為換入變量，確定換出522542323) 4 /12, 2 / 8min( 04 12 0 16 02 8 xxxxxxxx3)4/12, 2/8min(0,min2323222121kaababab思考：當 時會怎樣？02ka因此，基由 變?yōu)锽PPP ()342 轉第轉第2步：基變量用非基變量表示。步：基變量用非基變量表示。 第第3步：最優(yōu)性判斷步：最優(yōu)性判斷 檢驗數(shù)檢驗數(shù) 存在正，按第存在正，按第4步換基繼續(xù)迭代步換基繼續(xù)迭代

27、均非正，停止均非正，停止 （這時的解即是最優(yōu)解）（這時的解即是最優(yōu)解）2x為換入變量，應換出 變量。為換出變量變量：為換入變量，確定換出522542323) 4 /12, 2 / 8min( 04 12 0 16 02 8 xxxxxxxx)(543PPPB )0,16,2,3,0(,04329 41 3 416 21 8 124 416 82 )1()1(515152145135214123XXxxxxZxxxxxxxxxxxxxx得一基可行解令：代入目標函數(shù))0,16,2,3,0(,04329 41 3 416 21 2 124 416 82 )1()1(51515214513521412

28、3XXxxxxZxxxxxxxxxxxxxx得一基可行解令：代入目標函數(shù)轉轉 第第2步步 繼續(xù)迭代, 可得到:43)3()2(125.05.114)4,0,0,2,4()0,8,0,3,2(xxZXX目標函數(shù)為：最優(yōu)值最優(yōu)解 結合圖形法分析（單純形法的幾何意義）6 5 4 3 2 1 0 x2|123456789x1)0,16,2,3,0(,04329 41 3 416 21 8 124 416 82 )1()1(515152145135214123XXxxxxZxxxxxxxxxxxxxx得一基可行解令：代入目標函數(shù)43)3()2(125.05.114)4,0,0,2,4()0,8,0,3,

29、2(xxZXX目標函數(shù)為：43)3()2(125.05.114)4,0,0,2,4()0,8,0,3,2(xxZXX目標函數(shù)為：A(0,3)B(2,3)C(4,2)D(4,0)單純形法迭代原理單純形法迭代原理從引例中了解了線性規(guī)劃的求解過程，將按上述思路介紹一般的線性規(guī)劃模型的求解方法單單純形法迭代原理純形法迭代原理。 觀察法:直接觀察得到初始可行基 約束條件: 加入松弛變量即形成可行基。（下頁） 約束條件: 加入非負人工變量, 以后討論. 1、初始基可行解的確定 0,.,. . . 2111221122111111nmnmnmmmmnnmmnnmmxxxbxaxaxbxaxaxbxaxax1

30、 1、初始基可行解的確定、初始基可行解的確定 不妨設不妨設 為松弛變量，為松弛變量，則約束方程組可表示為則約束方程組可表示為mxxx,21 是一初始基可行解。有：令：)0,.,0 , 0 ,.,(),.2 , 1( 0. . . . 21111211222111111miinmnmnmmmmmnnmmnnmmbbbXmibxxxxaxabxxaxabxxaxabx1 1、初始基可行解的確定、初始基可行解的確定2 2、最優(yōu)性檢驗與解的判別、最優(yōu)性檢驗與解的判別nmnmmmmmnnmmnnmmxaxabxxaxabxxaxabx11211222111111. . . . 行解：一般情況下，對于基可

31、 nmjmijijijmiiinnmmjnmjmjmmjnmjjnnxaccbcxcxcxabcxabcxcxcxcZ11111111112221)( . )(.)( .代入目標函數(shù)，有：2 2、最優(yōu)性檢驗與解的判別、最優(yōu)性檢驗與解的判別 jnmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ1010110 )()( 檢驗數(shù)令：令：2 2、最優(yōu)性檢驗與解的判別、最優(yōu)性檢驗與解的判別 (1) 最優(yōu)解判別定理：若： 為基可行解，且全部 則 為最優(yōu)解。 （2）唯一最優(yōu)解判別定理：若所有 則存在唯一最有解。 2 2、最優(yōu)性檢驗與解的判別、最優(yōu)性檢驗與解的判別 （3）無窮多最優(yōu)

32、解判定定理：若： 且存在某一個非基變量 則存在無窮多最優(yōu)解。（4）無界解判定定理：若有某一個非基 變量 并且對應的非基變量的系數(shù) 則具有無界解。 nmjj,.,1, 00的kkx0的kmkmxmiakmi,.2,1,0,2 2、最優(yōu)性檢驗與解的判別、最優(yōu)性檢驗與解的判別 kmkmmmmkmkmkmkmxabxxabxxabx222111. . . , , 0, 00ZxxZZxakmkmkmkmkim當即解都可行，對任意（4）之證明：）之證明：2 2、最優(yōu)性檢驗與解的判別、最優(yōu)性檢驗與解的判別最優(yōu)解判斷小結 （用非基變量的檢驗數(shù)）所有 基變量中有非零人工變量某非基變量檢驗數(shù)為零唯一最優(yōu)解無窮多

33、最優(yōu)解無可行解對任一 有 換基繼續(xù)YYYYNNN無界解Njji ka000jji ka000jji ka000以后以后討論討論3、基變換 換入變量確定 對應的 為換入變量. (一般)kmjmj)0(maxkmx注意注意：只要只要 對應的變量對應的變量 均可作為換入變量均可作為換入變量0jjxkmkmxZZ0此時，目標函數(shù)此時，目標函數(shù) 換出變量確定klmlkimkimiikmkmmmmkmkmkmkmabaabxabxxabxxabx22211100. .0 0 min3 3、基變換、基變換kmkmxZZ0kmxZ 大大大大（在可行的范圍內）（在可行的范圍內）lx4、迭代運算 mmnkmmmm

34、klmlmnkmmnlmmlbbbaaaaaaaaabxxxxxx211ln1111111. . 1 . . . . . 1 . . . . . 1 . 寫成增廣矩陣的形式,進行迭代.例： TXxxZbxxx xx)12,16,8,0,0(320 121681 0 0 4 00 1 0 0 40 0 1 2 1 )0(21543211x3x2x4x5xb4 4、迭代運算、迭代運算非基變量非基變量基變量基變量001通過初等行變通過初等行變換化主列為換化主列為主元主元 TXxxZ)0,16,2,3,0( 432931621/4 0 0 1 00 1 0 0 41/2- 0 1 0 1)1(511x

35、3x2x4x5xb4 4、迭代運算、迭代運算檢驗數(shù)檢驗數(shù)1.3 1.3 單純形法迭代原理單純形法迭代原理 為書寫規(guī)范和便于計算，對單純形法的計算設計了單純形表。每一次迭代對應一張單純形表，含初始基可行解的單純形表稱為初始單純形表，含最優(yōu)解的單純形表稱為最終單純形表。本節(jié)介紹用單純形表計算線性規(guī)劃問題的步驟。 0. . . . 111111221122111111nnmmmmmnmnmmmmnnmmnnmmxcxcxcxcZbxaxaxbxaxaxbxaxax 單純形表0 . 1. 1 0 . . . 1 0. 1 0 . . Z-211211212111121mnmmmnmmnmnmnmmbb

36、bcccccaaaaaabxxxxxE單位陣N非基陣基變量XB非基變量XNN0 單純形表xxxxmn12 2 1 0 0 0 jcBCbBXjjzc 檢驗數(shù)bbm1xxm1ccm1單純形表結構 單純形表單純形表 24/65/1minA0znmcccc21C已知xxxxmn12 2 1 0 0 0 jcBCbBXjjzc 24/65/1minC檢驗數(shù)bbm1xxm1ccm1單純形表結構 單純形表單純形表A0z)0 , 0 ,(1mbbX基可行解：單純形表結構 單純形表單純形表xxxxmn12 2 1 0 0 0 jcBCbBXjjzc 24/65/1minC檢驗數(shù)bbm1xxm1ccm1A0zj

37、nmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ1010110 )()( 檢驗數(shù)令：令：有時不有時不寫此項寫此項單純形表結構 單純形表單純形表xxxxmn12 2 1 0 0 0 jcBCbBXjjzc 24/65/1minC檢驗數(shù)bbm1xxm1ccm1A0zjnmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ1010110 )()( 檢驗數(shù)令：令：jcmjjaa1j單純形表結構 單純形表單純形表xxxxmn12 2 1 0 0 0 jcBCbBXjjzc 24/65/1minC檢驗數(shù)bbm1xxm1ccm1A0zkmmkmaa, 1

38、km 不妨設此不妨設此為主列為主列klmlkimkimiiabaab0minl主行主行單純形表結構 單純形表單純形表xxxxmn12 2 1 0 0 0 jcBCbBXjjzc 24/65/1minC檢驗數(shù)bbm1xxm1ccm1A0zkmmkmaa, 1km lkmla,主元主元用單純形表求解LP問題0,524261552max212121221xxxxxxxxxz例、用單純形表求解例、用單純形表求解LPLP問題問題解：化標準型0,524261550002max515214213254321xxxxxxxxxxxxxxxz 2 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2

39、0 1 0 0 5 1 1 0 0 1 2 1 0 0 0 jcBCbBX1x3x2x4x5xjjzc 3x4x5x 24/65/1min主元化為1主列單位向量 換出 換入1x4x表表1：列初始單純形表：列初始單純形表 （單位矩陣對應的變量為基變量）（單位矩陣對應的變量為基變量）正檢驗數(shù)中最大者對正檢驗數(shù)中最大者對應的列為主列應的列為主列 2 1 0 0 0 0 15 0 5 1 0 0 2 4 1 2/6 0 1 /6 0 0 1 0 4/6 0 -1/6 1 0 1/3 0 -1/3 0 jcBCbBX1x3x2x4x5xjjzc 3x1x5x 15/524/26/4min 0*5 2*2

40、/6 +0*4/61- 2/3=表表2：換基：換基 （初等行變換，主列化為單位向量，主元為（初等行變換，主列化為單位向量，主元為1）檢驗數(shù)檢驗數(shù)0確定主列確定主列 最小最小確定主列確定主列主元主元 2 1 0 0 0 0 15/2 0 0 1 5/4 -15/2 2 7/2 1 0 0 1/4 -1/2 1 3/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 jcBCbBX1x3x2x4x5xjjzc 3x1x2x min檢驗數(shù)0，則目標函數(shù)不可能實現(xiàn)最優(yōu)。例: 求解線性規(guī)劃問題0,1 232 411 2 332131321321321xxxxxxxxxxxxxxMinZ32

41、13xxxMaxz一、大 M 法 0,1 23 2 411 2 00376543217316532143217654321xxxxxxxxxxxxxxxxxxxMxMxxxxxxMinZ7654321003MxMxxxxxxMaxz一、大 M 法解:l加入松弛變量和剩余變量進行標準加入松弛變量和剩余變量進行標準 化化, , 加入人工變量構造初始可行基加入人工變量構造初始可行基. . 求解結果出現(xiàn)檢驗數(shù)非正 若基變量中含非零的人工變量， 則無可行解； 否則，有最優(yōu)解。j 0一、大 M 法l用單純形法求解（見下頁）。用單純形法求解（見下頁）。目標函數(shù)中添加“罰因子”-M為人工變量系數(shù)，只要人工變量

42、0，則目標函數(shù)不可能實現(xiàn)最優(yōu)。 1 -2 1 -4 1 2 -2 0 1 3-63-6M M -1 3M-1M M -1 3M-1 3 -1 -1 x x1 x x2 x x3 0 x x4 11 -M x x6 3 -M x x7 1C j - Z j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x x4 x x5 11 3/2 1 0 0 1 0 0 1 0 0 - M - M x x6 x x7 i表表1（初始單純形表）（初始單純形表）一、大 M 法（單純形法求解） 3 -2 0 0 1 0 -2 0 1 1 1 M M-1-1 0 0 3 -1 -1x x1 x

43、 x2 x x3 0 x x4 10 -M x x6 1 -1 x x3 1C j - Z j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x x4 x x5 1 0 -1 1 -2 0 1 0 1 1-3 3M M - M - M x x6 x x7 i一、大 M 法（單純形法求解）表表2 3 0 0 0 1 0 -2 0 1 1 0 0 3 -1 -1 x x1 x x2 x x3 0 x x4 12 -1 x x2 1 -1 x x3 1C j - Z j C j CB XB b 1 -2 0 -1 0 0 0 -1 0 0 x x4 x x5 4 i 2 -5

44、1 -2 0 1 1-1-M -1M -1 -M-M - M - M x x6 x x7 i表表3一、大 M 法（單純形法求解） 1 0 0 0 1 0 0 0 1 0 0 0 3 -1 -1 x x1 x x2 x x3 3 x x1 4 -1 x x2 1 -1 x x3 9 2 C j CB XB b1/3 -2/3 0 -1 2/3 -4/3 -1/3 -1/3 0 0 x x4 x x5 2/3 -5/3 1 -2 4/3 -7/3 1/3-1/3-M 2/3-MM 2/3-M - M - M x x6 x x7 i表表4一、大 M 法（單純形法求解）914321xxx檢驗數(shù)均非正，

45、此檢驗數(shù)均非正，此為最終單純形表為最終單純形表M在計算機上處理困難。分階段處理先求初始基，再求解。二、兩階段法二、兩階段法二、兩階段法 第一階段: 構造如下的線性規(guī)劃問題0.,., . . . , 121221122222212111121211121mnnnmmnnmnmmnnnnnnmnnnxxxxxbxxaxaxabxxaxaxabxxaxaxaxxxMin 用單純形法求解上述問題用單純形法求解上述問題,若若=0,進進入第二階段入第二階段,否則否則,原問題無可行解。原問題無可行解。 第二階段：去掉人工變量，還原目標函第二階段：去掉人工變量，還原目標函數(shù)系數(shù)，做出初始單純形表。數(shù)系數(shù)，做出

46、初始單純形表。 用單純形法求解即可。用單純形法求解即可。二、兩階段法二、兩階段法下面舉例說明，仍用大M法的例。0,1 232 411 232131321321xxxxxxxxxxx3213xxxMaxz例：二、兩階段法二、兩階段法 0,1 23 2 411 2 765432173165321432176xxxxxxxxxxxxxxxxxxxxxMin二、兩階段法二、兩階段法l構造第一階段問題并求解構造第一階段問題并求解解：解：用單純形法求解用單純形法求解二、兩階段法二、兩階段法（第一階段、求第一階段、求min min ） 1 -2 1 -4 1 2 -2 0 1 -6 1 3 0 0 0 x

47、x1 x x2 x x3 0 x x4 11 -1 x x6 3 -1 x x7 1 C i CB XB b 1 0 0 0 -1 1 0 0 0 0 -1 0 0 0 -1 - 1 x x4 x x5 x x6 0 11 0 3/2 1 1 0 - 1 x x7 i i表表1jjzc -1 - -2 1 1 - -3 - 1 x x7 3 -2 0 0 1 0 -2 0 1 0 1 0 0 0 0 x x1 x x2 x x3 0 x x4 10 -1 x x6 1 0 x x3 1 C i CB XB b 1 0 0 0 -1 1 0 0 0 0 -1 0 0 0 -1 x x4 x x5

48、 x x6i二、兩階段法二、兩階段法（第一階段、求第一階段、求min min ）表表2jjzc -5 4 -2 - 1 - -1 - 1 x x7 3 0 0 0 1 0 -2 0 1 0 0 0 0 0 0 x x1 x x2 x x3 0 x x4 12 0 x x2 1 0 x x3 1 C i CB XB b 1 -2 2 0 -1 1 0 0 0 0 0 -1 0 0 -1 x x4 x x5 x x6i二、兩階段法二、兩階段法（第一階段、求第一階段、求min min ）表表3：最終單純形表：最終單純形表jjzc 不含人工不含人工變量且變量且=0=0二、兩階段法二、兩階段法 3 0

49、0 0 1 0 -2 0 1 3 -1 -1 x x1 x x2 x x3 0 x x4 12 -1 x x2 1 -1 x x3 1 C i CB XB b 1 -2 2 0 -1 1 0 0 0 0 0 x x4 x x5 ijjzc 1 0 0 0 -1二、兩階段法二、兩階段法 1 0 0 0 1 0 0 0 1 3 -1 -1 x x1 x x2 x x3 3 x x1 4 -1 x x2 1 -1 x x3 9 C i CB XB b 1/3 -2/3 0 -1 2/3 -4/3 0 0 x x4 x x5 i 0 0 0 -1/3 -1/3jjzc 914321xxx單純形法計算中

50、的幾個問題j 0l1、目標函數(shù)極小化時解的最優(yōu)性判斷、目標函數(shù)極小化時解的最優(yōu)性判斷 只需用檢驗數(shù) 作為最優(yōu)性的標志。j 0l2、無可行解的判斷、無可行解的判斷 當求解結果出現(xiàn)所有 時，如基變量仍 含有非零的人工變量（兩階段法求解時第一階 段目標函數(shù)值不等于0），則問題無可行解。退化 基可行解中存在基變量=0的解退化解 換入變量和換出變量的換入變量和換出變量的BlandBland規(guī)則規(guī)則選擇 中下標最小的非基變量 為換入變量, 這里:當按 規(guī)則計算存在兩個和兩個以上最小比值時,選下標最小的基變量為換出變量。jkx)0min(jjk單純形法計算中的幾個問題單純形法計算中的幾個問題 不妨設基為不妨

51、設基為mPPPB21基變量基變量非基變量非基變量0.maxXbAXtsCXz設線性規(guī)劃問題設線性規(guī)劃問題)()()()(21NBNBnCCCXXXNBPPPA則則NNBNBNBXNbNXbBXbNXBXXXNBbAX)()(1 其中其中NBNbBb11,令令 得當前的基解為：得當前的基解為：0NXbBbXB1當前基解當前基解約束方程組約束方程組NBNBNBNBNNBBNBNBXNCCbCXNBCCbBCXCXCXXCCz)()()(11當前目標值當前目標值目標函數(shù)目標函數(shù)bBCbCzBB10令令 得當前的目標函數(shù)值為：得當前的目標函數(shù)值為：0NX nBnnmBmmnmmnmBNNPCCPCCP

52、PCCCCNCC)()(111111當前檢驗數(shù)當前檢驗數(shù) 檢驗數(shù)檢驗數(shù)其中其中jjPBP1當前當前 對應的系數(shù)列對應的系數(shù)列jx線性規(guī)劃問題線性規(guī)劃問題0.maxXbAXtsCXz化為標準型，引入松弛變量化為標準型，引入松弛變量sX0, 0. .0maxsssXXbIXAXtsXCXz初始單純形表初始單純形表00NBjjssNBCCzcINBbXXXX非基變量非基變量基變量基變量初始基變量初始基變量11110BCNBCCzcBNBIbBXCXXXBBNjjBBsNB基變量基變量非基變量非基變量當基變量為當基變量為 時，新的單純形表時，新的單純形表BX當前檢驗數(shù)當前檢驗數(shù)當前基解當前基解線性規(guī)劃

53、模型單純形法習題課基本概念 線性規(guī)劃模型 三個要素三個要素： 決策變量、目標函數(shù)、約束條件 線性性線性性 線性規(guī)劃解的性質線性規(guī)劃問題的可行域是凸集。最優(yōu)解必在頂點上得到。 線性規(guī)劃求解方法圖解法單純形法本次習題課內容單純形法小結 一般線性規(guī)劃問題的標準化及初始單純形法表.變量變量0, 0,: 0 0 jjjjjjjjjjjxxxxxxxxxxx令：無約束令不需要處理 約束條件約束條件 在加人工變量加剩余變量加人工變量加松弛變量約束條件兩端同乘不需要處理, 1- 0 0bb單純形法小結 目標函數(shù)目標函數(shù)MZZZ:0: maxZ,Z min max人工變量松弛變量和剩余變量的系數(shù)加入變量求令：不需要處理 單純形法計算步驟框圖（略）單純形法小結 一、已知某LP的初始單純形表和單純形法 迭代的表，求未知數(shù)al的值。 6 b c d 1 0 1 -1 3 e 0 1 a -1 2 0 0 f g 2 -1 1/2 0 4 h i 1 1/2