運(yùn)籌學(xué)課件ch1單純形法

1、1第二節(jié) 單純形法是求解線性規(guī)劃的主要算法，1947提出。 盡管在其后的幾十年中，又有一些算法問世，但單純形法以其簡單實(shí)用的特色始終保持著絕對(duì)的“市場(chǎng)”占有率。21.線性規(guī)劃的標(biāo)準(zhǔn)型 用單純形法求解線性規(guī)劃的前提是先將模型化為標(biāo)準(zhǔn)型表示為0. .XbAXtsCXMaxz 標(biāo)準(zhǔn)型的特征：Max型、等式約束、非負(fù)約束一、單純形法的預(yù)備知識(shí)。）（的秩為其中，0,bnmmAnm3非標(biāo)準(zhǔn)形式如何化為標(biāo)準(zhǔn)1) MinMin型化為型化為MaxMax型型 CXMinzCXMaxz/加負(fù)號(hào) 因?yàn)?，求一個(gè)函數(shù)的極小點(diǎn)，等價(jià)于求該函數(shù)的負(fù)函數(shù)的極大點(diǎn)。)(xf)(xf*x注意： Min型化為Max型求解后，最優(yōu)解不

2、變，但最優(yōu)值差負(fù)號(hào)。 4. .約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。 ijijbxa0 iniinjijxbxxa稱為松弛變量稱為松弛變量 ijijbxa0 iniinjijxbxxa稱為剩余變量稱為剩余變量5 例1 某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源?，F(xiàn)將有關(guān)數(shù)據(jù)列表如下： 試擬訂使總收入最大的生產(chǎn)方案。2) 不等式約束化為等式約束不等式約束化為等式約束62) 不等式約束化為等式約束分析：以例1中煤的約束為例3604921 xx之所以“不等”是因?yàn)樽笥覂蛇呌幸粋€(gè)差額，稱為“松弛量”，若在左邊加上這個(gè)松弛量，則化為等式。而這個(gè)松弛量也是變量，

3、記為X3 ，則有36049321xxxX3稱為松弛變量。問題：它的實(shí)際意義是什么？ 煤資源的“剩余”。7練習(xí)：請(qǐng)將例1的約束化為標(biāo)準(zhǔn)型0,3001032005436049.21212121xxxxxxxxts解：增加松弛變量則約束化為,543xxx0,300 10320054360 49.54321521421321xxxxxxxxxxxxxxts易見，增加的松弛變量的系數(shù)恰構(gòu)成一個(gè)單位陣I。8一般地，記松弛變量的向量為 Xs，則0. .XbAXts0,. .ssXXbIXAXts0. .XbAXts0,. .ssXXbIXAXts問題：松弛變量在目標(biāo)中的系數(shù)為何？ 0。 3) 當(dāng)模型中有某變

4、量 xk 沒有非負(fù)要求，稱為自由變量, 則可令 0,/kkkkkxxxxx化為標(biāo)準(zhǔn)型。sXCXzMAX092.基本概念（1）可行解與最優(yōu)解；的解，記為可行解：滿足全體約束X。，有解則對(duì)任可行的，記為最優(yōu)解：可行解中最優(yōu)* ,CXCXXX直觀上，可行解是可行域中的點(diǎn)，是一個(gè)可行的方案； 最優(yōu)解是可行域的角點(diǎn)，是一個(gè)最優(yōu)的方案。10（2）基矩陣與基變量基矩陣(簡稱基)：由系數(shù)陣A中的線性無關(guān)的列線性無關(guān)的列組成的m階子矩陣階子矩陣，記為B；其余列構(gòu)成非基矩陣，記為N。基向量：基B中的列；其余的列稱非基向量?；兞浚号c基向量Pj對(duì)應(yīng)的決策變量xj，記其組成的 向量為XB；與非基向量對(duì)應(yīng)的變量稱非基變

5、 量，記其組成的向量為XN?；仃嚨奶攸c(diǎn):1. 基B是可逆矩陣,即2. 基B是一個(gè) 方陣mm0Br（B）=m或者nmmnmppppA.11A= ( B N )111231241432123,0 xxxxxxxx例 ： 下 面 為 某 線 性 規(guī) 劃 的 約 束請(qǐng) 例 舉 出 其 基 矩 陣 和 相 應(yīng) 的 基 向 量 、 基 變 量 。階可逆子陣有中的，解：本例中，210011221AA 6個(gè)。一般地，mn 階矩陣A中基的個(gè)數(shù)最多有多少個(gè)？個(gè)。mnC;,100143434311xxXxxPPBB，基變量為，其相應(yīng)的基向量為?；兞繛槠湎鄳?yīng)的基向量為21212122,1221xxXxxPPBB問

6、題：本例的A中一共有幾個(gè)基？12【例【例4】線性規(guī)劃】線性規(guī)劃 32124maxxxxZ5 , 1, 0226103553214321jxxxxxxxxxj 求所有基矩陣求所有基矩陣。 【解】約束方程的系數(shù)矩陣為【解】約束方程的系數(shù)矩陣為25矩陣矩陣 10261001115A,610151B,010152B,110053B26114B10019B,12017B,02118B,16016B,06115B容易看出容易看出r(A)=2，2階子矩陣有階子矩陣有C52=10個(gè)，個(gè)，其中第其中第1列與第列與第3列構(gòu)成的列構(gòu)成的2階矩陣不是一個(gè)基，階矩陣不是一個(gè)基，基矩陣只有基矩陣只有9個(gè)，即個(gè)，即0210

7、1513（3）基本解與基本可行解.0,0, ,1111bBXbBXXNXBbBXbXXNBbAXXXXNBAmABBABkkBkBTkB時(shí)，有當(dāng)取即可表示為約束中的相應(yīng)地）（列，則可記中的前表示取定后，不妨設(shè)中的基當(dāng)解；為線性規(guī)劃的一個(gè)基本的解稱0NbBXbAX可見：一個(gè)基本解是由一個(gè)基決定的。注意：基本解僅是資源約束的解，并未要求其非負(fù)，因此其未必可行。稱非負(fù)的基本解為基本可行解基本可行解（簡稱基可行解）。14例3中0,321241421321xxxxxxxx 求相應(yīng)于基B1和B2的基本解，它們是否基本可行解？,31311001,1001,1001111bBBBNN解：是基本可行解。的基本解

8、為相應(yīng)于基,)3 ,1 ,0 ,0(NTXB,51-573151-525251,51-525251,1-221112bBBB22不是基本可行解。的基本解為相應(yīng)于基,0,0)51,-57(2TXB15,610151B對(duì)對(duì)來說，來說，x1,x2是基變量，是基變量，x3,x4，x5是非基變是非基變量，令量，令x3=x4=x5=0，因因|B1|，由克萊姆法則知，由克萊姆法則知，x1、x2有唯一解有唯一解x12/5,x2=1則則 基本解為基本解為TX)0,0,0, 1 ,52()1(32124maxxxxZ5 , 1, 0226103553214321jxxxxxxxxxj在例4中,Xi0,是基本可行解

9、16在在 中中x10,因此不是可行解，也就不是基本可行解。因此不是可行解，也就不是基本可行解。 ）（ 2X反之，可行解不一定是基本可行解反之，可行解不一定是基本可行解例如例如 滿足所有約束式滿足所有約束式,但不是但不是任何基矩陣的基本解。任何基矩陣的基本解。TX) 1 ,27,21, 0 , 0(32124maxxxxZ,010152B5 , 1, 0226103553214321jxxxxxxxxxjTX)0,4,0,0,51()2(基本解為基本解為0不全為NX17上二組概念間的聯(lián)系：系數(shù)陣A中可找出若干個(gè)基B每個(gè)基B都對(duì)應(yīng)于一個(gè)基本解非負(fù)的基本解就是基本可行解幾種解之間的關(guān)系：可行解基本解

10、非可行解基本可行解問題：基本可行解是可行域中的哪些點(diǎn)？使目標(biāo)函數(shù)值最優(yōu)的基本可行解是最優(yōu)解183.基本定理（1）線性規(guī)劃的可行域是一個(gè)凸多面體。（2）線性規(guī)劃的最優(yōu)解（若存在的話）必能在可行 域的角點(diǎn)獲得。（3）線性規(guī)劃可行域的角點(diǎn)與基本可行解一一對(duì)應(yīng)。19二、單純形法的步驟 單純形法是一種迭代的算法，它的思想是在可行域的角點(diǎn)基本可行解中尋優(yōu)。由于角點(diǎn)是有限個(gè)（為什么？），因此，算法經(jīng)有限步可終止。確定一個(gè)初始基可行解檢驗(yàn)這個(gè)基可行解是否最優(yōu)尋找一個(gè)更好的基可行解否是停止201.確定初始基可行解 由于基可行解是由一個(gè)可行基決定的，因此，確定初始基可行解X0相當(dāng)于確定一個(gè)初始可行基B0。方法：若

11、A中含I，則B0=I； 若A中不含I，則可用人工變量法構(gòu) 造一個(gè)I。問題：若B0=I，則X0=？可行。,000NMMbbBX212. 最優(yōu)性檢驗(yàn)問題：用什么檢驗(yàn)？ 目標(biāo)。kBkBkkkBkbkBXNBCCbBCXCNXBbBCXXCCCXz)(NN)()(11而目標(biāo)優(yōu)。時(shí)，當(dāng)前基可行解為最，則當(dāng)記 01NBCCBk非最優(yōu)。則當(dāng)前解為最優(yōu)；否則若的檢驗(yàn)數(shù)方法：計(jì)算每個(gè)變量0, ,1jjBjjjPBCcx問題：非最優(yōu)的特征為何？。至少有某個(gè)檢驗(yàn)數(shù)0k22NNBBNBNBNBNBNBXCXCXXCCCXZNXBbBXbNXBXXXNBAX)()(11NBNBXNBCCbBCz)(11因?yàn)?將XB代入

12、Z, 有0Z*為最優(yōu)值的條件是233. 尋找更好的基可行解 由于基可行解與基對(duì)應(yīng)，即尋找一個(gè)新的基可行解，相當(dāng)于從上一個(gè)基B0變換為下一個(gè)新的基B1，因此，本步驟也稱為基變換。（基變換）0NNMNbBzz可行：改善：基變換的原則）變換的方法：（nklPPPP,N進(jìn)基出基進(jìn)基；對(duì)應(yīng)的令保證“改善”進(jìn)基kkP0可決定出基。由保證“可行”出基011kBNXBbBX 出基。對(duì)應(yīng)的令進(jìn)基；對(duì)應(yīng)的方法：令likikiiilkjjkPPBPBbBP0)()()(0111minmax稱作檢驗(yàn)比。i24 以例1為例，可按上述單純形法的步驟求出其最優(yōu)解，其大致的過程如下。（1）先將模型化為標(biāo)準(zhǔn)型0,3001032

13、005436049.54321521421321xxxxxxxxxxxxxxts 21127xxMaxz(2) 確定初始基可行解、檢驗(yàn);00,300)(0,0,360,2,00)(360,200,3,0100TTXbBB111;,52PP向量為再計(jì)算檢驗(yàn)比確定出基，確定進(jìn)基向量為計(jì)算非基向量的檢驗(yàn)數(shù)2500011000100010000CC3133PBB基B=(P3,P4,P5)=100010001=B-10054，同樣可知，非基N=(P1,P2)=105434973491000100010007CC1111PBB122確定進(jìn)基向量為確定進(jìn)基向量為P2計(jì)算檢驗(yàn)數(shù)計(jì)算檢驗(yàn)數(shù),確定進(jìn)基向量確定進(jìn)基

14、向量Max (0)26計(jì)算檢驗(yàn)比計(jì)算檢驗(yàn)比,確定出基向量確定出基向量Min (0)ik1i1ikPBbB300200360bB110541054100010001PB213040901030052004360P5出基出基B1=(P3,P4,P2)確定確定新基新基27（3）換基、計(jì)算下一個(gè)基可行解、再檢驗(yàn)，直至最優(yōu);50,0)(0,24,240,)(240,50,30,1051411111TTXbBB;0,0)(20,24,84,(84,20,24),103544912122TTXbBB00;,41PP向量為再計(jì)算檢驗(yàn)比確定出基量為計(jì)算檢驗(yàn)數(shù)確定進(jìn)基向前解為最優(yōu)。計(jì)算檢驗(yàn)數(shù)均非正，當(dāng)問題：當(dāng)模型

15、規(guī)模較大時(shí)，計(jì)算量很大。事實(shí)上，單純形法的實(shí)現(xiàn)是在單純形表上完成的。28練習(xí)：對(duì)于下面的線性規(guī)劃0,6222min2N2N2N2Nxxxxxxxxz（1）用圖解法求解；（2）將模型化為標(biāo)準(zhǔn)型；（3）用單純形法步驟求出其最優(yōu)解，并指出求 解過程中每一個(gè)基可行解相當(dāng)于可行域的 哪一個(gè)角點(diǎn)。29三、單純形表 單純形表是基于單純形法的步驟設(shè)計(jì)的計(jì)算格式，是單純形法的具體實(shí)現(xiàn)。110101100)()(000BmBbBmBCcbBXBikiiijBBjjmi nM回顧單純形法步驟bBN需計(jì)算ABN需計(jì)算,AbB1內(nèi)容是因此，單純形表的主體 121110AbBAbBAbB 即單純形表。變換迭代計(jì)算的由此設(shè)

16、計(jì)了基于初等行得。也可通過初等行變換求鄰兩個(gè)只有一列不同，故相而相鄰兩個(gè) 1BB30單純形表單純形表Ab分別將系數(shù)C,矩陣A和資源限制b填入, 得到單純形表的初表,計(jì)算檢驗(yàn)數(shù),進(jìn)行最優(yōu)性檢驗(yàn),若非優(yōu),就做初等行變換,形成新基的單純形表 =C-CBB-1A31單純形表的主要結(jié)構(gòu)： X CABNbBN問題：第一張表的B-1=？單位陣I。檢驗(yàn)數(shù)的公式是什么？jBjjPBCcN在哪里？jPBN列中的第jAB1 32例5：用單純形法求解例10,3001032005436049.21212121xxxxxxxxts21127xxMaxz將模型化為標(biāo)準(zhǔn)型：解：增加松弛變量,543xxx 0,30010320

17、05436049.54321521421321xxxxxxxxxxxxxxts 21127xxMaxz問題：標(biāo)準(zhǔn)模型的A中是否含I？松弛變量系數(shù)恰好構(gòu)成I。3354321 xxxxxbBNBXBC0 0 0 12 7100103010540014930020036054Pxxx000 0 0 0 12 7 3040907;3490) 0 (071111pBCcB其中檢驗(yàn)數(shù)904360P 中表示進(jìn)基列與出基行的交叉元，下一張表將實(shí)行以它為主元的初等行變換行變換（稱高斯消去）。方法是：先將主元消成1，再用此1將其所在列的其余元消成0。3454321 xxxxxbBNBXBC0 0 0 12 710

18、0103010540014930020036054Pxxx000 0 0 0 12 7 3040900.1 0 0 1 0.3 300.4- 0 1 0 7.8 2400.5- 1 0 0 2.5 50243xxx1200 1.2- 0 0 0 3.41002030.8 0.2- 0.4 0 0 1 201.16 0.32- 1 0 0 840.16 0.12- 0 1 0 24213xxx1270428.,0,0)(20,24,84,*zXT（請(qǐng)解釋其實(shí)際意義） 0.52- 1.36- 0 0 0此行元素除以主元1030 0.3 1 0 0 0.1此行元素乘以(-5)加入上行此行元素除以主元

19、2.535練習(xí)：用單純形法求解下面的線性規(guī)劃0,62-2-.2121 21xxxxxxts 212-xxMins將模型化為標(biāo)準(zhǔn)型：解：增加松弛變量, 43xx212xxMaxz0,622 -. .4342132121xxxxxxxxxxts36 4321xxxx 0 0 2- 1bBNBXBC10 2 101 1 1- 6243xx006 0 0 2- 1 1 0 2 1 6 1 1 3 0 813xx10 1- 0 4- 0TX)0,8,0,6(6s注：1. 表上每一列的含義：),(),(NNNNNnPBPBbBAbB2. 每張表上B-1的位置在哪？對(duì)應(yīng)于初表中I 的位置。,1110B,10

20、1111B3754321 xxxxxbBNBXBC0 0 0 12 7100103010540014930020036054Pxxx000 0 0 0 12 7 3040900.1 0 0 1 0.3 300.4- 0 1 0 7.8 2400.5- 0 1 0 2.5 50243xxx1200 1.2- 0 0 0 3.41002030.8 0.2- 0.4 0 0 1 201.16 0.32- 1 0 0 840.16 0.12- 0 1 0 24213xxx1270 1.2- 1.36- 0 0 0.428,)0 ,0 ,84,24,20(*zXT,111NMB,0.10.5-10.4-

21、111B.0.160.12-0.2-0.41.163.12-112B最優(yōu)基解XB=(x3,x1,x2)最優(yōu)基B=(p3,p1,p2)在哪里?.10305404912B3854321 xxxxxbBNBXBC100103010540014930020036054Pxxx000 0 0 0 12 7 0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0例6：填表：,2420843002003600.160.1200.20.401.163.1211bB解：10010540.160.1200.20.401.163

22、.12112PB242084100初表終表39練習(xí)：用單純形法求解下面的線性規(guī)劃0,25.2121 21xxxxxxts105153212.5xxMaxz將模型化為標(biāo)準(zhǔn)型：解：增加松弛變量, 43xx21xxMaxz5 .20,102515 53. .4342132121xxxxxxxxxxts4010 2 501 5 3101543xx00 0 0 1 2.525 4321xxxx 0 0 1 2.5bBNBXBC51 0 52 153- 1 519 02913xx2.50 0.5- 0 0 0TX)09,0,2,(5z,1110B,51053-111B問題：本題的單純形終表檢驗(yàn)數(shù)有何特點(diǎn)？

23、 非基變量x2 的檢驗(yàn)數(shù)等于零。41注：（1）解的幾種情況在單純形表上的體現(xiàn)（Max型）： - 唯一最優(yōu)解：終表非基變量檢驗(yàn)數(shù)均小于零； - 多重最優(yōu)解：終表非基變量檢驗(yàn)數(shù)中有等于零的； - 無界解：任意表有正檢驗(yàn)數(shù)相應(yīng)的系數(shù)列均非正。不同類型的解的判別不同類型的解的判別:42 （2） Min型單純形表與Max型的區(qū)別僅在于：檢驗(yàn)數(shù)反號(hào)，即 - 令負(fù)檢驗(yàn)數(shù)中最小的對(duì)應(yīng)的變量進(jìn)基；min - 當(dāng)檢驗(yàn)數(shù)均大于等于零時(shí)為最優(yōu)。Min型的單純形法型的單純形法0043大M法方法: 在一個(gè)標(biāo)準(zhǔn)的線性規(guī)劃問題的約束條件中加進(jìn)人工變量Xr并給定該人工變量在目標(biāo)函數(shù)中的系數(shù)為(-M)(M為任意大的正數(shù))bIXrAXMXCXzrmaxrMXCXzmin對(duì)于min型 有何不同?最優(yōu)性最優(yōu)基中不含人工變量若基變量中不含有非零的人工變量，表示原問題有若基變量中不含有非零的人工變量，表示原問題有解。若對(duì)于解。若對(duì)于MAX型，當(dāng)型，當(dāng) 0 ，而還有人工變量（非，而還有人工變量（非零）時(shí)，則表示原問題無可行解。零）時(shí)，則表示原問題無可行解。設(shè)規(guī)劃模型約束條件為設(shè)規(guī)劃模型約束條件為AXb或者或者AX=b，此時(shí)需加入人，此時(shí)需加入人工變量，以便在工變量，以便在A矩陣中得到一個(gè)矩陣中得