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

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

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

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

4、采用切割方案18的套數(shù)，的套數(shù)，方方案案2.9m2.1m1.5m合合計計余余料料12017.30.121207.10.331116.50.941037.4050306.31.160227.20.2根，但購買最優(yōu)解為則有零料最少若目標函數(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)解則有鋼筋最少若目標函數(shù)為使購買的OBJxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxf7 1.1.2 線性規(guī)劃數(shù)學模型的一般表示方式線性規(guī)劃數(shù)學模型的一般表示方式技技術(shù)術(shù)系系數(shù)數(shù)右右端端項項價價值值系系數(shù)數(shù)線線性性規(guī)規(guī)劃劃問問題題的的規(guī)規(guī)模模約約束束行行數(shù)數(shù)變變量量個個數(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ī)劃問題的幾個特點：線性規(guī)劃問題的幾個特點： 線性規(guī)劃問題的可性解的集合是凸集線性規(guī)劃問題的可性解的集合是凸集 線性規(guī)劃問題的基礎(chǔ)可行解都對應于凸集的極線性規(guī)劃問題的基礎(chǔ)可行解都對應于凸集的極點點 凸集的極點的個數(shù)是有限的凸集的極點的個數(shù)是有限的 最優(yōu)解必然在凸集的極點上，而不可能發(fā)生在最優(yōu)解必然在凸集的極點上，而不可能發(fā)生在凸集的內(nèi)部凸集的內(nèi)部131.2 線性規(guī)劃問題的單純型解法線性規(guī)劃

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

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

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

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

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

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

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

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

16、前前單單純純型型表表中中的的的的數(shù)數(shù)據(jù)據(jù)表表示示上上一一個個單單純純型型表表中中 ,(1.2.5b) (1.2.5a) *ijijijiijjiijijjiijiiiaabaaaaaaabbb27 1.2.4 標準型的單純型算法標準型的單純型算法5、迭代過程、迭代過程(4)變換變換CB，XB(5)計算目標函數(shù)、機會成本計算目標函數(shù)、機會成本 zj 和檢驗數(shù)和檢驗數(shù) cj zj 6、返回步驟、返回步驟 2aijai*jaij*ai*j*主主行行主主列列主主元元四四角角算算法法圖圖示示28 表表1.2.4 例例1.2.2 單純型表的迭代過程單純型表的迭代過程x1x2x3x4x5序序號號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 單純型表中元素的幾點說明單純型表中元素的

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

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

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

21、xxxxxxxxxxxtsMxxxxxf32 表表1.3.1 例例1.3.1的單純型表迭代過程的單純型表迭代過程x1x2x3x4x5x6序序號號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法的一些說明法的一些說明 大大M法實質(zhì)上與原單純型法一樣，法實質(zhì)上與原單純型法一樣，M 可看成一個很可看成一個很大的常數(shù)大的常數(shù) 人工變量被迭代出去后一般就不會再成為基變量人工變量被迭代出去后一般就不會再成為基變量 當檢驗數(shù)都滿足最優(yōu)條件，但基變量中仍有人工變當檢驗數(shù)都滿足最優(yōu)條件，但基變量中仍有人工變量，說明原線性規(guī)劃問題量，說明原線性規(guī)劃問題無可行解無可行解 大大M法手算很不方便法手算很不方便 因此提出了二階段法因此提出了二階段法 計算機中常用大

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

24、是是人人工工變變量量時時當當為為人人工工變變量量時時當當時時目目標標函函數(shù)數(shù)為為不不是是人人工工變變量量時時當當為為人人工工變變量量時時當當時時目目標標函函數(shù)數(shù)為為jjjjjjjjxcxcxcxc01max01min35 表表1.3.2 用二階段法求解例用二階段法求解例1.3.1的第一階段的第一階段x1x2x3x4x5x6序序號號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序序號號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)解對應的最優(yōu)解對應的B1在哪？在哪？371.5 單純型法的一些具體問題單純型法的一些具體問題1.5.1 關(guān)于無界解問題關(guān)于無界解問題 可行區(qū)域不閉合可行區(qū)域不閉合(約束條件有問題約束條件有問題) 單

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

27、退化問題關(guān)于退化問題 退化問題的原因很復雜，當原問題存在平衡約束時退化問題的原因很復雜，當原問題存在平衡約束時 當單純型表中同時有多個基變量可選作出變量時當單純型表中同時有多個基變量可選作出變量時 退化的嚴重性在于可能導致死循環(huán)，克服死循環(huán)的退化的嚴重性在于可能導致死循環(huán)，克服死循環(huán)的方法有方法有“字典序字典序”法法0, 060240.43)(max1.5.2 2121212121xxxxxxxxtsxxxf例例x1x2x3x4序號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)于多重解問題關(guān)于多重解問題 多個基礎(chǔ)可行解都是最優(yōu)解，這些解在同一個超平多個基礎(chǔ)可行解都是最優(yōu)解，這些解在同一個超平面上，且該平面與目標函數(shù)等值面平行面上，且該平面與目標函數(shù)等值面平行 最優(yōu)單純型表中有非基變量的檢驗數(shù)為最優(yōu)單純型表中有非基變量的檢驗數(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 的單純型表及其迭代過程的單純型表及其迭代過程x1x2x3x4x5序序號號CBXBb40452500bi/aij*0 x41002(3)110(33.3)0 x51203320140 OBJ = 000000I初初始始解解cj- -zj40452500 迭迭代代 過過程程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