線性規(guī)劃及單純形法課件

1、先修課：高等數(shù)學(xué)，基礎(chǔ)概率、線性代數(shù)先修課：高等數(shù)學(xué)，基礎(chǔ)概率、線性代數(shù)特點(diǎn)：系統(tǒng)整體優(yōu)化；多學(xué)科的配合；模型方法的應(yīng)用特點(diǎn)：系統(tǒng)整體優(yōu)化；多學(xué)科的配合；模型方法的應(yīng)用規(guī)定規(guī)定目標(biāo)目標(biāo)和和明確明確問題問題收集收集數(shù)據(jù)數(shù)據(jù)和和建立建立模型模型求解求解模型模型和和優(yōu)化優(yōu)化方案方案檢驗(yàn)檢驗(yàn)?zāi)Ｐ湍Ｐ秃秃驮u價評價方案方案方案方案實(shí)施實(shí)施和和不斷不斷改進(jìn)改進(jìn)解決問題解決問題制定決策制定決策表表1-11-1問題分析：問題分析：（1）問題的目標(biāo)是什么？）問題的目標(biāo)是什么？ 合理安排生產(chǎn)，實(shí)現(xiàn)利潤最大化合理安排生產(chǎn)，實(shí)現(xiàn)利潤最大化（2）利潤與哪些因素有關(guān)？）利潤與哪些因素有關(guān)？ 產(chǎn)量和單位產(chǎn)量的利潤產(chǎn)量和單位產(chǎn)

2、量的利潤按工藝資料規(guī)定，按工藝資料規(guī)定，生產(chǎn)每件產(chǎn)品生產(chǎn)每件產(chǎn)品I I需占用各設(shè)備分別為需占用各設(shè)備分別為2 2、1 1、4 4、0h0h；生產(chǎn)每件產(chǎn)品生產(chǎn)每件產(chǎn)品IIII需占用設(shè)備分別為需占用設(shè)備分別為2 2、2 2、0 0、4h4h；已知各設(shè)備計(jì)劃期內(nèi)用于生產(chǎn)兩種產(chǎn)品的能力分別為已知各設(shè)備計(jì)劃期內(nèi)用于生產(chǎn)兩種產(chǎn)品的能力分別為1212、8 8、1616、12h12h0,124164821222. .32max2121212121xxxxxxxxtsxxz表表1-21-2分析：分析：問題的目標(biāo)是什么？問題的目標(biāo)是什么？ 通過三種煤的組合實(shí)現(xiàn)混合煤的價格通過三種煤的組合實(shí)現(xiàn)混合煤的價格最低最低問

3、題目標(biāo)實(shí)現(xiàn)的約束條件是什么？問題目標(biāo)實(shí)現(xiàn)的約束條件是什么？ 含硫量和發(fā)熱量含硫量和發(fā)熱量0,1025. 003. 005. 001. 017000180002000016000. .767080min321321321321321xxxxxxxxxxxxtsxxxz目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件表表1-31-3），；，（321j321i0252010152551. .15080100901207012010080minij332313322212312111332331322221312111332331322221312111xxxxxxxxxxxxxxxxxxxtsxxxxxxxxxz0

4、,18231224. .500300max21212121xxxxxxtsxxz0,.,),(.),(.),(. .maxmin21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz）或（nmmnmmnnnccbbbaaaaaaaaamxxx212121222211121121c21價值系數(shù)動活資源決策變量決策變量及各類系數(shù)之間的對應(yīng)關(guān)系決策變量及各類系數(shù)之間的對應(yīng)關(guān)系),.,1(0),.,2 , 1(),(. .maxminj11njxmibxatsxczinjjijnjjj）或（),.,1(0),(P

5、.CXmaxminj1njxbxtsznjjj）或（mmjjjjnnbbbbnjaaaPxxxXccc.);,.,2 , 1( ,.;.;,.,C21212121）（式中：0X),(AX. .CXmaxminbtsz）或（mnmmnnaaaaaaaaa.A212222111211式中：A A為約束方程組（約束為約束方程組（約束條件）的條件）的系數(shù)矩陣系數(shù)矩陣。),.,1(0),.,2, 1(.maxj11njxmibxatsxczinjjijnjjj),.,1(0),.,2, 1(.maxj11njxmibxatsxczinjjijnjjjnjjjxcz1minnjjjxcz1max0, 0

6、xxxxx，取值無約束，3213213213213210,-63-2-342392.32-minxxxxxxxxxxxxtsxxxz0,63323-4223932. .00332max54 3321 33215 33214 332154 3321xxxxxxxxxxxxxxxxxxxxtsxxxxxxz63323, 422329),0, 0(, 3321 33215 33214 33 333xxxxxxxxxxxxxxxxxxxzz令X4X4為松弛變量為松弛變量X5X5為剩余變量為剩余變量0,24261553. .2max21212121xxxxxxtsxxz0,24261553. .002m

7、ax43214213214321xxxxxxxxxxtsxxxxz無約束43214321432143214321, 0,2232x-1432-24. .5243-minxxxxxxxxxxxxxxxtsxxxxz0,2)(232x-143224-. .00)(5243max 443216 443215 44321 4432165 44321xxxxxxxxxxxxxxxxxxxxxtsxxxxxxxz)0, 0(, 44 444xxxxxzz令）（）（）（）（40,3515216411222. .32max21212121xxxxxxtsxxz）（）（）（）（40,3515216411222.

8、 .32max21212121xxxxxxtsxxzx1x1x2x2Q4Q4Q3Q3Q2Q2Q1Q1）（）（）（）（40,3515216411222. .32max21212121xxxxxxtsxxzx1x1x2x2Q4Q4Q3(3,3)Q3(3,3)Q2 (4,2)Q2 (4,2)Q1Q1從圖形中我們看到陰影部從圖形中我們看到陰影部分的圖形是凸的，以后我分的圖形是凸的，以后我們要證明，如果線性規(guī)劃們要證明，如果線性規(guī)劃問題存在可行域，則可行問題存在可行域，則可行域一定是一個凸集。域一定是一個凸集。）（）（）（）（40,3515216411222. .32max21212121xxxxxxt

9、sxxz）（）（）（）（40,3515216411222. .32max21212121xxxxxxtsxxzx1x1x2x233212zxxZ=6Z=6）（）（）（）（40,3515216411222. .32max21212121xxxxxxtsxxzx1x1x2x2Q4Q4Q3(3,3)Q3(3,3)Q2 (4,2)Q2 (4,2)Q1Q1）（）（）（）（40,3515216411222. .33max21212121xxxxxxtsxxzx1x1x2x2Q4Q4Q3(3,3)Q3(3,3)Q2 (4,2)Q2 (4,2)Q1Q1）（）（）（）（40,3515216411222. .33

10、max21212121xxxxxxtsxxz0,24-2. .2max2112121xxxxxtsxxzx1x1x2x2如圖：此問題有可行域，但為無界解（無最優(yōu)解）如圖：此問題有可行域，但為無界解（無最優(yōu)解）其原因是由于在建立實(shí)際問題的數(shù)學(xué)模型時遺漏了某些其原因是由于在建立實(shí)際問題的數(shù)學(xué)模型時遺漏了某些必要的資源約束。必要的資源約束。0,4126. .32max21212121xxxxxxtsxxzx1x1x2x2用圖解法求解時找不到滿足所有約束條件的公共范圍，用圖解法求解時找不到滿足所有約束條件的公共范圍，這時此問題無可行解。原因是模型本身有錯誤，約束條這時此問題無可行解。原因是模型本身有錯

11、誤，約束條件相互矛盾，應(yīng)檢查修正。件相互矛盾，應(yīng)檢查修正。（a）（b）（c）（d）),.,1(0),.,2 , 1(. .maxzj11njxmibxatsxcinjjijnjjj（a a）（b b）（c c）),.,1(0),.,2 , 1(. .maxzj11njxmibxatsxcinjjijnjjj（a a）（b b）（c c）mnmmnnaaaaaaaaa.212222111211）（mmmmmPPaaaa,.,.B11111B B中的每一個列向量中的每一個列向量P Pj j（j=1,mj=1,m）稱為）稱為基向量基向量，與基，與基向量向量P Pj j對應(yīng)的變量對應(yīng)的變量x xj j

12、稱為稱為基變量基變量。線性規(guī)劃中除基變。線性規(guī)劃中除基變量以外的其他變量稱為量以外的其他變量稱為非基變量非基變量。),.,2 , 1(. .1mibxatsinjjij基基基向量基向量mnmmnnaaaaaaaaaA112222111211顯然，顯然，r r ( ( A A ) ) min ( min ( m m , , n n ) ; ) ; r r ( ( A AT T ) = ) = r r ( ( A A ) ) . . 求矩陣求矩陣 A A 的秩，其中的秩，其中.174532321A : :在在 A A 中，容易看出階子式中，容易看出階子式,013221而而 A A 的三階子式只有一

13、個的三階子式只有一個 , 0|A因此因此. 2)(Ar)5,.,2 , 1(02261035. .-2-4max53214321321jxxxxxxxxxtsxxxzj102610-011-15A610-15B1010-15B2110-05B3261-1B41201-B80211-B71601B60911B51001B9由線性代數(shù)知道，基矩陣由線性代數(shù)知道，基矩陣B B必為非必為非奇異矩陣，即奇異矩陣，即|B|0|B|0。當(dāng)矩陣。當(dāng)矩陣B B的的行列式等于零是就不是基。行列式等于零是就不是基。010-15B2102610-011-15A),.,1(0),.,2 , 1(. .maxzj11nj

14、xmibxatsxcinjjijnjjj（a a）（b b）（c c）對某一特定的基對某一特定的基B B，令非基變量等于零，令非基變量等于零，利用（利用（b b）求解出基變量，）求解出基變量，則這組解成為基則這組解成為基B B的基本解。的基本解。)1 (22112222212111212111nnnnnnnnnnbxaxaxabxaxaxabxaxaxa0det212222111211nnnnnnaaaaaaaaaAnjABxjj, 2, 1,detdet),.,1(0),.,2 , 1(. .maxzj11njxmibxatsxcinjjijnjjj（a a）（b b）（c c）)5,.,2

15、 , 1(02261035. .-2-4max53214321321jxxxxxxxxxtsxxxzj610-15B12610352121xxxxT000152），（)5,.,2 , 1(02261035. .-2-4max53214321321jxxxxxxxxxtsxxxzj21035141xxxT040051-），（010-15B2T)1(000152），（XT)2(040051-），（XT1272100），（X對應(yīng)的基對應(yīng)的基B1B1稱為可行基稱為可行基基本最優(yōu)解基本最優(yōu)解基本可行解基本可行解最優(yōu)解最優(yōu)解基本解基本解可行解可行解箭尾的解一定是箭頭的解，否則不一定成立箭尾的解一定是箭頭的

16、解，否則不一定成立)5,.,1(01551641222. .00032max524132154321jxxxxxxxxtsxxxxxzj標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型)5,.,1(01551641222. .00032max524132154321jxxxxxxxxtsxxxxxzj100500100400122AP1P1P2P2P3P3P4P4P5P5矩陣矩陣A A的秩的秩33。所以只要。所以只要找出找出3 3個列向量組成的矩陣個列向量組成的矩陣滿秩，這滿秩，這3 3個向量就是線性個向量就是線性規(guī)劃問題的一個基。規(guī)劃問題的一個基。100500100400122AP1P1P2P2P3P3P4P4P5P5令與基對

17、應(yīng)的變量為基變量，其余變量為非基變量，令與基對應(yīng)的變量為基變量，其余變量為非基變量，令非基變量等于零，求解方程組就可以找出基解。令非基變量等于零，求解方程組就可以找出基解。下表中列出本線性規(guī)劃問題的全部基、基解。下表中列出本線性規(guī)劃問題的全部基、基解。每生產(chǎn)一件產(chǎn)品每生產(chǎn)一件產(chǎn)品可獲利可獲利2 2元，每生產(chǎn)一件產(chǎn)品元，每生產(chǎn)一件產(chǎn)品可可獲利獲利3 3元，問應(yīng)如何安排計(jì)劃使該工廠獲利最多元，問應(yīng)如何安排計(jì)劃使該工廠獲利最多? ? 0124164823221212121x ,xxxxx:xxzmax約束條件目標(biāo)函數(shù)) 11 (00032max54321xxxxxz5 , 2 , 10124)21

18、(164825241321jxxxxxxxxj約約束束條條件件100010040004121,54321PPPPPA100,010,001543PPP100010001,543PPPB124)21 (164825241321xxxxxxx)31 (412416282514213xxxxxxx從從(1-2)(1-2)式中可式中可以得到（以得到（1-31-3）) 11 (00032max54321xxxxxz)41 (32021xxz到這里，完成了單純形法的第一個環(huán)節(jié)：確定初始基到這里，完成了單純形法的第一個環(huán)節(jié)：確定初始基本可行解；然后再確定這個基本可行解是否是最優(yōu)的，本可行解；然后再確定這個基

19、本可行解是否是最優(yōu)的，如果不是，則還要繼續(xù)去尋找最優(yōu)解！如果不是，則還要繼續(xù)去尋找最優(yōu)解！)31 (412416282514213xxxxxxx)41 (32021xxz)51 (041201602825423xxxxx)31 (412416282514213xxxxxxx)31 (412416282514213xxxxxxx )61 (312424161825214123xxxxxxx 713413241612125214513xxxxxxx）（ 8-1432951xxz2143maxxxz0,303402212121xxxxxx43210043maxxxxxz0,3034024321421

20、321xxxxxxxxxx10310112,4321PPPPA1001,43PPB基變量為：基變量為：x3x3，x4x4非基變量為：非基變量為：x1x1，x2x2令非基變量令非基變量x1=x2=0 x1=x2=0，代入約束方程中，代入約束方程中0,3034024321421321xxxxxxxxxx得到：得到：x3=40 x3=40，x4=30 x4=30則初始基本可行解為：則初始基本可行解為：X X（0 0）= =（0 0，0 0，4040，3030）T T基變量的檢驗(yàn)數(shù)為零基變量的檢驗(yàn)數(shù)為零40/140/130/330/340/140/130/330/3X2X2希望變成希望變成1 1希望變

21、成希望變成0 0這樣，形成的基就是單位矩陣。因此，對增廣矩陣進(jìn)這樣，形成的基就是單位矩陣。因此，對增廣矩陣進(jìn)行行初等變換初等變換！ 4 440401010增廣矩陣的第增廣矩陣的第2 2行中的每個元素都行中的每個元素都3 3 得：如圖所示得：如圖所示1/31/31 11/31/31010增廣矩陣的第增廣矩陣的第1 1行行- -第第2 2行行 得：如圖所示得：如圖所示5/35/3 0 0-1/3-1/33030經(jīng)過增廣矩陣的初等變換后，基變成了單位矩陣經(jīng)過增廣矩陣的初等變換后，基變成了單位矩陣40401010確定基可行解確定基可行解X X（1 1）= =？令非基變量令非基變量x1=x4=0 x1=

22、x4=0，基變量，基變量x2=10 x2=10，x3=30 x3=30所以所以X X（1 1）= =（0 0，1010，3030，0 0）T T基可行解是否是最優(yōu)解？基可行解是否是最優(yōu)解？因?yàn)橐驗(yàn)?=03=0了，所以只需要將了，所以只需要將22變換為變換為0 0。方法：矩陣的第。方法：矩陣的第3 3行行- -第第2 2行行4 4-40-40 0 0 5/35/3-4/3-4/3得出：得出：X X（1 1）= =（0 0，1010，3030，0 0）T T不是最優(yōu)解不是最優(yōu)解下一步：確定換入變量和換出變量下一步：確定換入變量和換出變量請大家自己運(yùn)算，直到確定最優(yōu)解。請大家自己運(yùn)算，直到確定最優(yōu)解

23、。30301818x1x13 3將基（將基（P1 P2P1 P2）初等變換為單位矩陣）初等變換為單位矩陣方法：方法： 5/3 5/3 - -1/31/3確定基本可行解確定基本可行解X X（2 2）= =（1818，4 4，0 0，0 0）T T最優(yōu)性性判斷？最優(yōu)性性判斷？ - -5/35/3看到所有的檢驗(yàn)數(shù)都小于看到所有的檢驗(yàn)數(shù)都小于0 0，所以，所以X X（2 2）是最優(yōu)解是最優(yōu)解同時目標(biāo)函數(shù)值為同時目標(biāo)函數(shù)值為7070 1 13/53/5-1/5-1/51818 0 0-1/5-1/52/52/54 4 0 0 -1 -1 -1 -1 -70 -70-z-z0,24261553. .2ma

24、x21212121xxxxxxtsxxz0,212665. .22min2121212121xxxxxxxxtsxxz0,2-10242-. .42ax2121212121xxxxxxxxtsxxzm5432100042maxxxxxxz0,201242-54321521421321xxxxxxxxxxxxxx初始單純形表如下：初始單純形表如下：X X（0 0）= =（0 0，0 0，4 4，1010，2 2）T T2 24 40 00 00 00 0判斷是否最優(yōu)？判斷是否最優(yōu)？不是最優(yōu)！不是最優(yōu)！換基方案？換基方案？換入變量：換入變量：x2x2，2 25 5換出變量：換出變量：x3x3543

25、2100042maxxxxxxz0,201242-54321521421321xxxxxxxxxxxxxx經(jīng)初等變換，將（經(jīng)初等變換，將（P2P2，P4P4，P5P5）變換為單位矩陣）變換為單位矩陣判斷是否最優(yōu)？判斷是否最優(yōu)？-1/2-1/2 2 21/21/2 1 1 0 0 0 01/21/2 -1 -11/21/2基本解為基本解為X X（1 1）= =（0 0，2 2，0 0，6 6，4 4）T T 2 2 6 6 4 4不是最優(yōu)解！不是最優(yōu)解！ 4 4 0 0 -2 -2 -8 -8換基方案？換基方案？ 換入變量：換入變量：x1x1， 3 3 8 8換出變量：換出變量：x4x4經(jīng)初等變

26、換，將（經(jīng)初等變換，將（P1P1，P2P2，P5P5）變換為單位矩陣）變換為單位矩陣判斷是否最優(yōu)？判斷是否最優(yōu)？基本解為基本解為X X（2 2）= =（3 3，7/27/2，0 0，0 0，5/25/2）T T是最優(yōu)解！是最優(yōu)解！ 0 0 1 1 0 0 1/4 1/4-1/2-1/23/4 3/4 1/4 1/41/21/2-1/4 -1/4 7/2 7/2 3 3 5/2 5/2 -2 -2-20-20 0 0 0 0目標(biāo)函數(shù)值為目標(biāo)函數(shù)值為z=20z=20但是這時，非基變量但是這時，非基變量x3x3的檢驗(yàn)數(shù)為零，表示原問題還有其他的最的檢驗(yàn)數(shù)為零，表示原問題還有其他的最優(yōu)解，也就是說這是

27、多重最優(yōu)解的情況。還可以進(jìn)一步迭代！優(yōu)解，也就是說這是多重最優(yōu)解的情況。還可以進(jìn)一步迭代！換基方案？換基方案？ 換入變量：換入變量：x3x3， 換出變量：換出變量：x5x5 14 14 10/3 10/3 x3 x3經(jīng)初等變換，將（經(jīng)初等變換，將（P1P1，P2P2，P3P3）變換為單位矩陣）變換為單位矩陣基本解為基本解為X X（3 3）= =（14/314/3，8/38/3，10/310/3，0 0，0 0）T T 1 1 0 0 0 01/31/31/31/3-1/3-1/3-1/3-1/32/32/34/34/38/38/314/314/310/310/3基本解為基本解為X X（3 3）

28、是最優(yōu)解！是最優(yōu)解！ 目標(biāo)函數(shù)值目標(biāo)函數(shù)值z=20z=200,25 . 01. .00 x22ax43214213214321xxxxxxxxxxtsxxxzm因?yàn)閱栴}是最大化問題，這時非基變量因?yàn)閱栴}是最大化問題，這時非基變量x1x1的檢驗(yàn)數(shù)的檢驗(yàn)數(shù)=2=2（00），可以作為進(jìn)基變量，但是增廣矩陣中），可以作為進(jìn)基變量，但是增廣矩陣中x1x1對應(yīng)對應(yīng)的系數(shù)都小于的系數(shù)都小于0 0，所以目標(biāo)函數(shù)無上界，問題無最優(yōu)解！，所以目標(biāo)函數(shù)無上界，問題無最優(yōu)解！0|minikikiaab0,122102434. .23max321321321321321xxxxxxxxxxxxtsxxxz)5,.,1(

29、0122102434. .0023max3215321432154321jxxxxxxxxxxxxtsxxxxxzj0012-21021-101-134-A系數(shù)矩陣系數(shù)矩陣A A為：為：系數(shù)矩陣系數(shù)矩陣A A中不包含單位矩陣，中不包含單位矩陣，因此增加人工變量去構(gòu)造單位因此增加人工變量去構(gòu)造單位矩陣，但增加的人工變量不能矩陣，但增加的人工變量不能影響目標(biāo)函數(shù)。影響目標(biāo)函數(shù)。)7,.,1(0122102434. .0023max73215321643217654321jxxxxxxxxxxxxxxtsMxMxxxxxxzj)5,.,1(0122102434. .0023max3215321432

30、154321jxxxxxxxxxxxxtsxxxxxzj0012-21021-101-134-A)7,.,1(0122102434. .0023max73215321643217654321jxxxxxxxxxxxxxxtsMxMxxxxxxzj100012-2001021-10101-134-A系數(shù)矩陣系數(shù)矩陣A A為：為：有有1 1單位子矩陣單位子矩陣）（7, 5, 6100010001BPPP系數(shù)為負(fù)數(shù)，我們知道在換基時，系數(shù)為負(fù)數(shù)，我們知道在換基時，會把它們置換出來，這樣就不會影會把它們置換出來，這樣就不會影響目標(biāo)函數(shù)了響目標(biāo)函數(shù)了)7,.,1(0122102434. .0023max

31、73215321643217654321jxxxxxxxxxxxxxxtsMxMxxxxxxzj)7,.,1(0122102434. .0023max73215321643217654321jxxxxxxxxxxxxxxtsMxMxxxxxxzj3-4M3-4M 2+3M2+3M -1+M-1+M-M-M0 03-2M3-2M2+M2+M -1+2M-1+2M-M-M0 0換基：換入變量換基：換入變量x3x3，換出變量，換出變量x7x70 0-6-6 5 50 0-3-3 3 33 38 85M5M 0 0 5-6M5-6M換基：換入變量換基：換入變量x2x2，換出變量，換出變量x6x6換基：

32、換入變量換基：換入變量x1x1，換出變量，換出變量x5x51 1-6/5-6/5-1/5-1/50 03/53/53/53/50 0-2/5-2/53/53/531/531/5-2/5-2/511/511/50 0 5 5 0 0X=(31/3,13,19/3,0,0)X=(31/3,13,19/3,0,0)T T最優(yōu)值最優(yōu)值z=152/3z=152/3 1 1 1 15/35/331/331/3 0 0 1 1 2 21313 0 0 0 02/32/319/319/3-5-5-25/3-25/3 0 0miiR1wmin0,122102434. .23max321321321321321xxxxxxxxxxxxtsxxxz)5,.,1(0122102434. .0023max3215321432154321jxx