運(yùn)籌學(xué)課件_林齊寧_第一章_線性規(guī)劃與單純形法 (2)

1、管理與人文學(xué)院管理與人文學(xué)院 忻展紅忻展紅 1999，4運(yùn)籌學(xué)Operational Research英英 Operations Research美美運(yùn)籌帷幄之中，決勝千里之外運(yùn)籌帷幄之中，決勝千里之外 史記史記留侯世家留侯世家2目目 錄錄緒緒 論論第一章第一章 線性規(guī)劃問(wèn)題及單純型解法線性規(guī)劃問(wèn)題及單純型解法第二章第二章 線性規(guī)劃的對(duì)偶理論及其應(yīng)用線性規(guī)劃的對(duì)偶理論及其應(yīng)用第三章第三章 運(yùn)輸問(wèn)題數(shù)學(xué)模型及其解法運(yùn)輸問(wèn)題數(shù)學(xué)模型及其解法第四章第四章 整數(shù)規(guī)劃整數(shù)規(guī)劃第五章第五章 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃第六章第六章 圖與網(wǎng)路分析圖與網(wǎng)路分析第七章第七章 隨機(jī)服務(wù)理論概論隨機(jī)服務(wù)理論概論第八章第八章 生

2、滅服務(wù)系統(tǒng)生滅服務(wù)系統(tǒng)第九章第九章 特殊隨機(jī)服務(wù)系統(tǒng)特殊隨機(jī)服務(wù)系統(tǒng)第十章第十章 存儲(chǔ)理論存儲(chǔ)理論3第一章第一章 線性規(guī)劃問(wèn)題及單純型解法線性規(guī)劃問(wèn)題及單純型解法1.1 線性規(guī)劃問(wèn)題及其一般數(shù)學(xué)模型線性規(guī)劃問(wèn)題及其一般數(shù)學(xué)模型1.1.1 1.1.1 線性規(guī)劃問(wèn)題舉例線性規(guī)劃問(wèn)題舉例例例1 1、多產(chǎn)品生產(chǎn)問(wèn)題、多產(chǎn)品生產(chǎn)問(wèn)題（Max, ）設(shè)設(shè)x1, x2 分別代表甲、乙兩種電纜的生產(chǎn)量，分別代表甲、乙兩種電纜的生產(chǎn)量，.36)(max, 6, 2:0,78102.46)(max:21212212121xfxxxxxxxxxtsxxxfOBJ最優(yōu)解最優(yōu)解產(chǎn)量不允許為負(fù)值產(chǎn)量不允許為負(fù)值產(chǎn)量約束產(chǎn)量

3、約束鉛資源約束鉛資源約束銅資源約束銅資源約束4例例2、配料問(wèn)題（、配料問(wèn)題（min, ) )原原料料甲甲 原原料料乙乙 最最低低含含量量VA0.50.52VB11.00.33VB20.20.61.2VD0.50.22單單價(jià)價(jià)0.30.5設(shè)設(shè) x1, x2分別代表每粒膠丸中甲、分別代表每粒膠丸中甲、乙兩種原料的用量乙兩種原料的用量0,22 . 05 . 02 . 16 . 02 . 033 . 00 . 125 . 05 . 0. .5 . 03 . 0)(min212121212121xxxxxxxxxxtsxxxf5例例3、合理下料問(wèn)題、合理下料問(wèn)題 設(shè)設(shè) xj 分別代表采用切割方案分別代表

4、采用切割方案18的套數(shù)，的套數(shù)，方方案案2.9m2.1m1.5m合合計(jì)計(jì)余余料料12017.30.121207.10.331116.50.941037.4050306.31.160227.20.2根，但購(gòu)買最優(yōu)解為則有零料最少若目標(biāo)函數(shù)為使裁剪后15010,50,100:0,100231002321002.2 . 01 . 109 . 03 . 01 . 0)(min,64654321643165324321654321OBJxxxxxxxxxxxxxxxxxxxxtsxxxxxxxf616 ;90,30,50,10:0,100231002321002. .)(min,421654321643

5、165324321654321但余料為最優(yōu)解則有鋼筋最少若目標(biāo)函數(shù)為使購(gòu)買的OBJxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxf7 1.1.2 線性規(guī)劃數(shù)學(xué)模型的一般表示方式線性規(guī)劃數(shù)學(xué)模型的一般表示方式技技術(shù)術(shù)系系數(shù)數(shù)右右端端項(xiàng)項(xiàng)價(jià)價(jià)值值系系數(shù)數(shù)線線性性規(guī)規(guī)劃劃問(wèn)問(wèn)題題的的規(guī)規(guī)模模約約束束行行數(shù)數(shù)變變量量個(gè)個(gè)數(shù)數(shù): ;: ;: ;: ;:0,),(),(),(.)(max(min)21221122222121112121112211ijjjnmnmnmmnnnnnnabcmnmnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxf8 1、和式和式njxmibx

6、atsxcxfjinjjijnjjj, 2 , 1 , 0, 2 , 1 ,.)(max119 2、向量式向量式0000 ),( );,( .)(max210212121010bbbbaaaPxxxXcccC0XbxPtsCXxfmmjjjjTnnnjjj10 3、矩陣式矩陣式 ),(),();,(.)(max212121212222111211TmTnnmnmmnnbbbbxxxXcccCaaaaaaaaaA0XbAXtsCXxf11 1.1.3 線性規(guī)劃的圖解法線性規(guī)劃的圖解法1187654322x1876543O109x2A BCEDFGH123f(x)=0f(x)=12.36)(max

7、, 6, 2:0,78102.46)(max21212212121xfxxxxxxxxxtsxxxf最優(yōu)解最優(yōu)解1187654322x1876543O109x2A BCEDFGH123f(x)=3612 線性規(guī)劃問(wèn)題的幾個(gè)特點(diǎn)：線性規(guī)劃問(wèn)題的幾個(gè)特點(diǎn)： 線性規(guī)劃問(wèn)題的可性解的集合是凸集線性規(guī)劃問(wèn)題的可性解的集合是凸集 線性規(guī)劃問(wèn)題的基礎(chǔ)可行解都對(duì)應(yīng)于凸集的極線性規(guī)劃問(wèn)題的基礎(chǔ)可行解都對(duì)應(yīng)于凸集的極點(diǎn)點(diǎn) 凸集的極點(diǎn)的個(gè)數(shù)是有限的凸集的極點(diǎn)的個(gè)數(shù)是有限的 最優(yōu)解必然在凸集的極點(diǎn)上，而不可能發(fā)生在最優(yōu)解必然在凸集的極點(diǎn)上，而不可能發(fā)生在凸集的內(nèi)部凸集的內(nèi)部131.2 線性規(guī)劃問(wèn)題的單純型解法線性規(guī)劃

8、問(wèn)題的單純型解法1.2.1 解解線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式為了使線性規(guī)劃問(wèn)題的解法標(biāo)準(zhǔn)化，就要把一般形為了使線性規(guī)劃問(wèn)題的解法標(biāo)準(zhǔn)化，就要把一般形式化為標(biāo)準(zhǔn)形式式化為標(biāo)準(zhǔn)形式njxmibxatsxcxfjinjjijnjjj,2, 1 ),0(0,2, 1 ,),(.)(max(min)11不不限限njmixbmibxatsxcxfjiimnjjijmnjjj,2, 1 ,2, 1 ,0,2, 1 ,.)(max1114 變換的方法：變換的方法：目標(biāo)函數(shù)為目標(biāo)函數(shù)為min型，價(jià)值系數(shù)一律反號(hào)。令型，價(jià)值系數(shù)一律反號(hào)。令 f (x) = - -f(x) = - -CX, 有有

9、min f(x) = - - max - - f(x) = - - max f (x)第第i 個(gè)約束的個(gè)約束的bi 為負(fù)值，則該行左右兩端系數(shù)同時(shí)反號(hào)，為負(fù)值，則該行左右兩端系數(shù)同時(shí)反號(hào)，同時(shí)不等號(hào)也要反向同時(shí)不等號(hào)也要反向第第i 個(gè)約束為個(gè)約束為 型，在不等式左邊增加一個(gè)非負(fù)的變型，在不等式左邊增加一個(gè)非負(fù)的變量量xn+i ，稱為松弛變量；同時(shí)令稱為松弛變量；同時(shí)令 cn+i = 0第第i 個(gè)約束為個(gè)約束為 型，在不等式左邊減去一個(gè)非負(fù)的變型，在不等式左邊減去一個(gè)非負(fù)的變量量xn+i ，稱為剩余變量；同時(shí)令稱為剩余變量；同時(shí)令 cn+i = 0若若xj 0，令，令 xj= - -xj ，代入

10、非標(biāo)準(zhǔn)型，則有，代入非標(biāo)準(zhǔn)型，則有xj 0若若xj 不限，令不限，令 xj= xj - - xj ， xj 0，xj 0，代入非標(biāo)代入非標(biāo)準(zhǔn)型準(zhǔn)型15 變換舉例：變換舉例：0, ,20040065300432.423)(min:213321321321321xxxxxxxxxxxxtsxxxxf不限不限原非標(biāo)準(zhǔn)型原非標(biāo)準(zhǔn)型 0,2004006653004432.0004423)(max:65433216332153321433216543321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxf標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型16 關(guān)于標(biāo)準(zhǔn)型解的若干基本概念：關(guān)于標(biāo)準(zhǔn)型解的若干基本概念： 標(biāo)準(zhǔn)型有標(biāo)

11、準(zhǔn)型有 n+m 個(gè)變量，個(gè)變量， m 個(gè)約束行個(gè)約束行 “基基”的概念的概念 在標(biāo)準(zhǔn)型中，技術(shù)系數(shù)矩陣有在標(biāo)準(zhǔn)型中，技術(shù)系數(shù)矩陣有 n+m 列，即列，即 A = ( P1, P2 , , Pn+m ) A中線性獨(dú)立的中線性獨(dú)立的 m 列，構(gòu)成該標(biāo)準(zhǔn)型的一個(gè)列，構(gòu)成該標(biāo)準(zhǔn)型的一個(gè)基基，即，即 B = ( P1 , P2 , , Pm )， | B | 0 P1 , P2 , , Pm 稱為稱為基向量基向量 與與基向量基向量對(duì)應(yīng)的變量稱為對(duì)應(yīng)的變量稱為基變量基變量，記為，記為 XB = ( x1 , x2 , , xm )T，其余的變量稱為，其余的變量稱為非基變量非基變量，記為記為 XN = (

12、xm+1 , xm+2 , , xm+n ) T ， 故有故有 X = XB + XN 最多有最多有 個(gè)基個(gè)基mnmC17 關(guān)于標(biāo)準(zhǔn)型解的若干基本概念：關(guān)于標(biāo)準(zhǔn)型解的若干基本概念： 可行解可行解與與非可行解非可行解 滿足約束條件和非負(fù)條件的解滿足約束條件和非負(fù)條件的解 X 稱為稱為可行解可行解，滿足，滿足約束條件但不滿足非負(fù)條件的解約束條件但不滿足非負(fù)條件的解 X 稱為稱為非可行解非可行解 基礎(chǔ)解基礎(chǔ)解 令令非基變量非基變量 XN = 0，求得，求得基變量基變量 XB的值稱為的值稱為基礎(chǔ)解基礎(chǔ)解 即即 XB = B 1 b XB 是是基礎(chǔ)解基礎(chǔ)解的的必要條件必要條件為為XB 的非零分量個(gè)數(shù)的非

13、零分量個(gè)數(shù) m 基礎(chǔ)可行解基礎(chǔ)可行解 基礎(chǔ)解基礎(chǔ)解 XB 的非零分量都的非零分量都 0 時(shí)，稱為時(shí)，稱為基礎(chǔ)可行解基礎(chǔ)可行解，否則為否則為基礎(chǔ)非可行解基礎(chǔ)非可行解 基礎(chǔ)可行解基礎(chǔ)可行解的非零分量個(gè)數(shù)的非零分量個(gè)數(shù) 0, 則未達(dá)到最優(yōu)則未達(dá)到最優(yōu)(5) (4) )3( )()()(2) )(1) )(1jjmiijijNN1BN1BNN1BNNNN1BNNBBNNBBNNzcaczXABCCbBCXAbBCXCxfXAbBXXAbBXbBXXAXCXCxf檢驗(yàn)數(shù)檢驗(yàn)數(shù)機(jī)會(huì)成本機(jī)會(huì)成本24 1.2.4 標(biāo)準(zhǔn)型的單純型算法標(biāo)準(zhǔn)型的單純型算法1 找初始基礎(chǔ)可行基找初始基礎(chǔ)可行基 對(duì)于對(duì)于(max, )

14、，松弛變量對(duì)應(yīng)的列構(gòu)成一個(gè)單位陣，松弛變量對(duì)應(yīng)的列構(gòu)成一個(gè)單位陣 若有若有 bi 0 中找最大者，選中者稱為中找最大者，選中者稱為入變量入變量， xj* 第第j*列稱為列稱為主列主列4 確定確定入變量入變量的最大值和的最大值和出變量出變量 最小比例原則最小比例原則(1.2.4) 0min*ijijiiaab 25 1.2.4 標(biāo)準(zhǔn)型的單純型算法標(biāo)準(zhǔn)型的單純型算法4 確定確定入變量入變量的最大值和的最大值和出變量出變量 設(shè)第設(shè)第 i* 行使行使 最小，則第最小，則第 i* 行對(duì)應(yīng)的基變量稱為行對(duì)應(yīng)的基變量稱為出變量出變量，第，第 i* 行稱為行稱為主行主行5 迭代過(guò)程迭代過(guò)程 主行主行 i* 行

15、與行與主列主列 j* 相交的元素相交的元素ai*j* 稱為稱為主元主元，迭代，迭代以以主元主元為中心進(jìn)行為中心進(jìn)行 迭代的實(shí)質(zhì)是線性變換，即要將迭代的實(shí)質(zhì)是線性變換，即要將主元主元 ai*j*變?yōu)樽優(yōu)?，主主列列上其它元素變?yōu)樯掀渌刈優(yōu)?，變換步驟如下：，變換步驟如下：(1)變換主行變換主行nmjaaajijiji, 2 , 1*26 1.2.4 標(biāo)準(zhǔn)型的單純型算法標(biāo)準(zhǔn)型的單純型算法5 迭代過(guò)程迭代過(guò)程(2)變換主列變換主列除除主元主元保留為保留為1，其余都置，其余都置0(3)變換非主行、主列元素變換非主行、主列元素 aij (包括包括 bi)四角算法公式四角算法公式：數(shù)數(shù)據(jù)據(jù)表表示示當(dāng)當(dāng)

16、前前單單純純型型表表中中的的的的數(shù)數(shù)據(jù)據(jù)表表示示上上一一個(gè)個(gè)單單純純型型表表中中 ,(1.2.5b) (1.2.5a) *ijijijiijjiijijjiijiiiaabaaaaaaabbb27 1.2.4 標(biāo)準(zhǔn)型的單純型算法標(biāo)準(zhǔn)型的單純型算法5、迭代過(guò)程、迭代過(guò)程(4)變換變換CB，XB(5)計(jì)算目標(biāo)函數(shù)、機(jī)會(huì)成本計(jì)算目標(biāo)函數(shù)、機(jī)會(huì)成本 zj 和檢驗(yàn)數(shù)和檢驗(yàn)數(shù) cj zj 6、返回步驟、返回步驟 2aijai*jaij*ai*j*主主行行主主列列主主元元四四角角算算法法圖圖示示28 表表1.2.4 例例1.2.2 單純型表的迭代過(guò)程單純型表的迭代過(guò)程x1x2x3x4x5序序號(hào)號(hào)CBXBb4

17、0452400bi/aij*0 x41002(3)110(33.3)0 x51203320140 OBJ = 000000I初初始始解解cj- -zj4045240045x2100/3 2/311/31/30500 x520(1)01 11(20) OBJ = 1500304515150IIcj- -zj1009 15045x22001 1/31 2/340 x120101 11 OBJ = 1700404525510III最最優(yōu)優(yōu)解解cj- -zj00 1 5 10答：最優(yōu)解為答：最優(yōu)解為 x1=20, x2=20, x3=0, OBJ=170029 單純型表中元素的幾點(diǎn)說(shuō)明單純型表中元素的

18、幾點(diǎn)說(shuō)明 任何時(shí)候，基變量對(duì)應(yīng)的列都構(gòu)成一個(gè)單位矩陣任何時(shí)候，基變量對(duì)應(yīng)的列都構(gòu)成一個(gè)單位矩陣 當(dāng)前表中的當(dāng)前表中的 b 列表示當(dāng)前基變量的解值，通過(guò)變換列表示當(dāng)前基變量的解值，通過(guò)變換 B 1 b 得到得到 (資源已變成產(chǎn)品資源已變成產(chǎn)品) 當(dāng)前非基變量對(duì)應(yīng)的向量可通過(guò)變換當(dāng)前非基變量對(duì)應(yīng)的向量可通過(guò)變換 B 1 AN 得到，得到， 表示第表示第 j 個(gè)變量對(duì)第個(gè)變量對(duì)第 i 行對(duì)應(yīng)的基變量的消耗率行對(duì)應(yīng)的基變量的消耗率 非基變量的機(jī)會(huì)成本由非基變量的機(jī)會(huì)成本由 給出給出 注意基變量所對(duì)應(yīng)的行注意基變量所對(duì)應(yīng)的行x1x2x3x4x5序序號(hào)號(hào)CBXBb40452400bi/aij*45x210

19、0/3 2/311/31/30500 x520(1)01 11(20) OBJ = 1500304515150IIcj- -zj1009 150ijamiijijacz1 301.3 人工變量的引入及其解法人工變量的引入及其解法 1.3.1 當(dāng)約束條件為當(dāng)約束條件為“ ”型，引入剩余變量和人工變型，引入剩余變量和人工變量量 由于所添加的剩余變量的技術(shù)系數(shù)為由于所添加的剩余變量的技術(shù)系數(shù)為 1，不能作為初，不能作為初始可行基變量，為此引入一個(gè)人為的變量（注意，此始可行基變量，為此引入一個(gè)人為的變量（注意，此時(shí)約束條件已為時(shí)約束條件已為“=”型），以便取得初始基變量，故型），以便取得初始基變量，故

20、稱為人工變量稱為人工變量 由于人工變量在原問(wèn)題的解中是不能存在的，應(yīng)盡快由于人工變量在原問(wèn)題的解中是不能存在的，應(yīng)盡快被迭代出去，因此人工變量在目標(biāo)函數(shù)中對(duì)應(yīng)的價(jià)值被迭代出去，因此人工變量在目標(biāo)函數(shù)中對(duì)應(yīng)的價(jià)值系數(shù)應(yīng)具有懲罰性，稱為罰系數(shù)。罰系數(shù)的取值視解系數(shù)應(yīng)具有懲罰性，稱為罰系數(shù)。罰系數(shù)的取值視解法而定法而定 兩種方法兩種方法 大大M法法 二階段法二階段法31 1.3.2 大大M法的求解過(guò)程法的求解過(guò)程 例例1.3.10,46 2.7810)(min32132121321xxxxxxxxtsxxxxf0,4 6 2. .)7810max()(max654321532164216321xxx

21、xxxxxxxxxxxtsMxxxxxf32 表表1.3.1 例例1.3.1的單純型表迭代過(guò)程的單純型表迭代過(guò)程x1x2x3x4x5x6序序號(hào)號(hào)CBXBb 10 8 700 M bi/aij* Mx66(2)10 101(3) 7x341110 104 6M 28 2M 7 M 7 7M7 MI初初始始解解cj zj2M 3M 10 M 70 10 x1311/20 1/201/26 7x310(1/2)11/2 1 1/2(2) 37 10 17/2 73/27 3/2IIcj zj01/20 3/2 7 M+3/2 10 x1210 1 111 8x220121 2 1 36 10 8 6

22、26 2III最最優(yōu)優(yōu)解解cj zj00 1 2 6 M+2答：最優(yōu)解為答：最優(yōu)解為 x1=2, x2=2, x3=0, OBJ=3633 大大M法的一些說(shuō)明法的一些說(shuō)明 大大M法實(shí)質(zhì)上與原單純型法一樣，法實(shí)質(zhì)上與原單純型法一樣，M 可看成一個(gè)很可看成一個(gè)很大的常數(shù)大的常數(shù) 人工變量被迭代出去后一般就不會(huì)再成為基變量人工變量被迭代出去后一般就不會(huì)再成為基變量 當(dāng)檢驗(yàn)數(shù)都滿足最優(yōu)條件，但基變量中仍有人工變當(dāng)檢驗(yàn)數(shù)都滿足最優(yōu)條件，但基變量中仍有人工變量，說(shuō)明原線性規(guī)劃問(wèn)題量，說(shuō)明原線性規(guī)劃問(wèn)題無(wú)可行解無(wú)可行解 大大M法手算很不方便法手算很不方便 因此提出了二階段法因此提出了二階段法 計(jì)算機(jī)中常用大

23、計(jì)算機(jī)中常用大M法法 二階段法手算可能容易二階段法手算可能容易34 1.3.3 二階段法的求解過(guò)程二階段法的求解過(guò)程 第一階段的任務(wù)是將人工變量盡快迭代出去，從而第一階段的任務(wù)是將人工變量盡快迭代出去，從而找到一個(gè)沒有人工變量的基礎(chǔ)可行解找到一個(gè)沒有人工變量的基礎(chǔ)可行解 第二階段以第一階段得到的基礎(chǔ)可行解為初始解，第二階段以第一階段得到的基礎(chǔ)可行解為初始解，采用原單純型法求解采用原單純型法求解 若第一階段結(jié)束時(shí)，人工變量仍在基變量中，則原若第一階段結(jié)束時(shí)，人工變量仍在基變量中，則原問(wèn)題無(wú)解問(wèn)題無(wú)解 為了簡(jiǎn)化計(jì)算，在第一階段重新定義價(jià)值系數(shù)如下：為了簡(jiǎn)化計(jì)算，在第一階段重新定義價(jià)值系數(shù)如下：不不

24、是是人人工工變變量量時(shí)時(shí)當(dāng)當(dāng)為為人人工工變變量量時(shí)時(shí)當(dāng)當(dāng)時(shí)時(shí)目目標(biāo)標(biāo)函函數(shù)數(shù)為為不不是是人人工工變變量量時(shí)時(shí)當(dāng)當(dāng)為為人人工工變變量量時(shí)時(shí)當(dāng)當(dāng)時(shí)時(shí)目目標(biāo)標(biāo)函函數(shù)數(shù)為為jjjjjjjjxcxcxcxc01max01min35 表表1.3.2 用二階段法求解例用二階段法求解例1.3.1的第一階段的第一階段x1x2x3x4x5x6序序號(hào)號(hào)CBXBb00000 1bi/aij* 1x66(2)10 101(3)0 x341110 104 6 2 1010 1Icj zj210 1000 x1311/20 1/201/20 x3101/211/2 1 1/2 0000000IIcj zj00000 136

25、 表表1.3.2 用二階段法求解例用二階段法求解例1.3.1的第二階段的第二階段x1x2x3x4x5序序號(hào)號(hào)CBXBb 10 8 700bi/aij* 10 x1311/20 1/206 7x310(1/2)11/2 1(2) 37 10 17/2 73/27Icj zj01/20 3/2 7 10 x1210 1 11 8x220121 2 36 10 8 626IIcj zj00 1 2 6最優(yōu)解對(duì)應(yīng)的最優(yōu)解對(duì)應(yīng)的B1在哪？在哪？371.5 單純型法的一些具體問(wèn)題單純型法的一些具體問(wèn)題1.5.1 關(guān)于無(wú)界解問(wèn)題關(guān)于無(wú)界解問(wèn)題 可行區(qū)域不閉合可行區(qū)域不閉合(約束條件有問(wèn)題約束條件有問(wèn)題) 單

26、純型表中入變量單純型表中入變量 xj* 對(duì)應(yīng)的列中所有對(duì)應(yīng)的列中所有0a*ij0,501002.)(max1 . 5 . 1 21212121xxxxxxtsxxxf例例f(x)=x1+x2x1x2505050100 x1-x2=50-2x1+x2=10038 表表1.5.1 例例1.5.1 的單純型表及其迭代過(guò)程的單純型表及其迭代過(guò)程x1x2x3x4序號(hào)CBXBb1100bi/aij*0 x310021100 x450(1)101(50) OBJ = 00000I初始解cj-zj11000 x32001121x1501101 OBJ = 50101IIcj-zj020 39 1.5.2 關(guān)于

27、退化問(wèn)題關(guān)于退化問(wèn)題 退化問(wèn)題的原因很復(fù)雜，當(dāng)原問(wèn)題存在平衡約束時(shí)退化問(wèn)題的原因很復(fù)雜，當(dāng)原問(wèn)題存在平衡約束時(shí) 當(dāng)單純型表中同時(shí)有多個(gè)基變量可選作出變量時(shí)當(dāng)單純型表中同時(shí)有多個(gè)基變量可選作出變量時(shí) 退化的嚴(yán)重性在于可能導(dǎo)致死循環(huán)，克服死循環(huán)的退化的嚴(yán)重性在于可能導(dǎo)致死循環(huán)，克服死循環(huán)的方法有方法有“字典序字典序”法法0, 060240.43)(max1.5.2 2121212121xxxxxxxxtsxxxf例例x1x2x3x4序號(hào)CBXBb3400bi/aij*0 x340(2)10(20)0 x460001(20)3x10100 OBJ = 03300IIcj-zj07004x22011/

28、200 x4003/213x12011/20 OBJ = 14033.50IIIcj-zj003.540 1.5.3 關(guān)于多重解問(wèn)題關(guān)于多重解問(wèn)題 多個(gè)基礎(chǔ)可行解都是最優(yōu)解，這些解在同一個(gè)超平多個(gè)基礎(chǔ)可行解都是最優(yōu)解，這些解在同一個(gè)超平面上，且該平面與目標(biāo)函數(shù)等值面平行面上，且該平面與目標(biāo)函數(shù)等值面平行 最優(yōu)單純型表中有非基變量的檢驗(yàn)數(shù)為最優(yōu)單純型表中有非基變量的檢驗(yàn)數(shù)為0 最優(yōu)解的線性組合仍是最優(yōu)解，即最優(yōu)解的線性組合仍是最優(yōu)解，即 X=aX1+bX2，a+b=10,12023310032.254540)(max 1.5.3 321321321321xxxxxxxxxtsxxxxf多重最優(yōu)解多重最優(yōu)解例例41 表表1.5.3 例例1.5.3 的單純型表及其迭代過(guò)程的單純型表及其迭代過(guò)程x1x2x3x4x5序序號(hào)號(hào)CBXBb40452500bi/aij*0 x41002(3)110(33.3)0 x51203320140 OBJ = 000000I初初始始解解cj- -zj40452500 迭迭代代 過(guò)過(guò)程程45x22001 1/31 2/3 40 x12010(1) 11(20) OBJ = 1700404525510III最最優(yōu)優(yōu)解解cj- -zj000 5 1045x226.67 1/3102/3 1/325