線性規(guī)劃及單純形PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)11.1 線性規(guī)劃的數(shù)學(xué)模型 第1頁(yè)/共110頁(yè)合理安排，以最少的資源來(lái)完成它。第2頁(yè)/共110頁(yè)設(shè)備設(shè)備ABCD邊際利潤(rùn)利潤(rùn)產(chǎn)品甲產(chǎn)品甲21402元元產(chǎn)品乙產(chǎn)品乙22043元元有效有效臺(tái)時(shí)數(shù)臺(tái)時(shí)數(shù)1281612第3頁(yè)/共110頁(yè)n同理，對(duì)設(shè)備B、C、D也可以得到以下不等式：8 16 12考慮到實(shí)際意義，不可能為負(fù)值，即021,xx2122xx 212xx 14x24x21,xx21,xx第4頁(yè)/共110頁(yè)max3221xxZ2132maxxxZ21,xx212xx 14x24x21,xx2122xx 第5頁(yè)/共110頁(yè)2132maxxxZ21,xx212xx 14x24x21,xx21

2、22xx 設(shè)備設(shè)備ABCD邊際利利潤(rùn)潤(rùn)產(chǎn)品甲產(chǎn)品甲21402元元產(chǎn)品乙產(chǎn)品乙22043元元有效有效臺(tái)時(shí)數(shù)臺(tái)時(shí)數(shù)1281612其中 必須滿足以下條件 12 8s.t. 16 12 0第6頁(yè)/共110頁(yè)第7頁(yè)/共110頁(yè)2134maxxxz16002221 xx25005 . 2521xx1x02xs.t.,4001x第8頁(yè)/共110頁(yè)成年人每天需要從食物中攝取的營(yíng)養(yǎng)以及四種食品所含營(yíng)養(yǎng)和價(jià)格見下表。問(wèn)如何選擇食品才能在滿足營(yíng)養(yǎng)的前提下使購(gòu)買食品的費(fèi)用最?。渴称访Q 熱量(kcal) 蛋白質(zhì)(g) 鈣（mg） 價(jià)格（元） 豬肉 1000 50 400 14 雞蛋 800 60 200 6 大米 9

3、00 20 300 3 白菜 200 10 500 2 營(yíng)養(yǎng)需求量 3000 55 800 第9頁(yè)/共110頁(yè)0,800500300200400551020605030002009008001000. .23614min43214321432143214321xxxxxxxxxxxxxxxxt sxxxxz第10頁(yè)/共110頁(yè)第11頁(yè)/共110頁(yè) 方案長(zhǎng)度一x1二x2三x3四x4五x52.92.11.513210221213合計(jì)（米）料頭（米）7.407.30.17.20.27.10.36.60.8第12頁(yè)/共110頁(yè)5 , 4 , 3 , 2 , 1, ixi0,10032310022100

4、2. .8 . 03 . 02 . 01 . 00 . 0min54321532154342154321xxxxxxxxxxxxxxxtsxxxxxz第13頁(yè)/共110頁(yè)nxxx,21第14頁(yè)/共110頁(yè) 12 8 s.t. 16 12 02132maxxxZ212xx 14x24x21,xx2122xx 目標(biāo)函數(shù)約束條件第15頁(yè)/共110頁(yè)nnxcxcxcZ2211max(min)0,2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxas.t.約束條件目標(biāo)函數(shù)決策變量?jī)r(jià)值系數(shù)技術(shù)系數(shù)限定系數(shù)第16頁(yè)/共110頁(yè)第17頁(yè)/共110頁(yè)

5、0;, 2 , 1, 0max221122222121112121112211iimnmnmmnnnnnnbnixbxaxaxabxaxaxabxaxaxaxcxcxczs.t極大化型約束方程為等式所有的決策變量為非負(fù)值約束方程的右端項(xiàng)系數(shù)為非負(fù)值第18頁(yè)/共110頁(yè)1、極大化型2、約束方程為等式3、所有的決策變量為非負(fù)值4、約束方程的右端項(xiàng)系數(shù)為非負(fù)值n形式線性規(guī)劃標(biāo)準(zhǔn)數(shù)學(xué)模型的特征第19頁(yè)/共110頁(yè)njxbxptsxczjnjjjnjjj, 2 , 1, 0. .max11第20頁(yè)/共110頁(yè)0.maxXbAXtsCXz第21頁(yè)/共110頁(yè)nmnmmnnpppaaaaaaaaaA2121

6、2222111211mnbbbbxxxX2121,ncccC21第22頁(yè)/共110頁(yè)非標(biāo)準(zhǔn)形式如何轉(zhuǎn)換成標(biāo)準(zhǔn)形式1、目標(biāo)函數(shù)是極小化的轉(zhuǎn)化321723z minxxx321723, xxxzzz則目標(biāo)函數(shù)轉(zhuǎn)換為等價(jià)變換：令maxminzz )0(1647616476 ) 1 (2444321321cxxxxxxxx為松弛變量如：約束方程為轉(zhuǎn)換、約束方程為不等式的xz-z第23頁(yè)/共110頁(yè))0(1232712327 )2(444321321cxxxxxxxx為剩余變量如：約束方程為無(wú)非負(fù)約束如：jx無(wú)非負(fù)限制的轉(zhuǎn)換決策變量jx. 3jjjjjxxxxx 令引入, 0, 0第24頁(yè)/共110頁(yè)4

7、.決策變量有上下界的轉(zhuǎn)換4, 0 , 1 5 , 1, 51 3333333xxxxxxx則令如：無(wú)非負(fù)約束例：21332121321, 0 6 1 5 7 s.t 23min xxxxxxxxxxxz7)( .4221 xxxxts) 1()(23max3221 xxxxz4)(53221 xxxxx563xx0,6543221 xxxxxxx1, -23 33222321 xxxxxxxxz令：第25頁(yè)/共110頁(yè)0,124164821222000032max616251421321654321xxxxxxxxxxxxxxxxxxzs.t第26頁(yè)/共110頁(yè)0,40025005 . 251

8、6002200034max515142132154321xxxxxxxxxxxxxxxzs.t第27頁(yè)/共110頁(yè)第28頁(yè)/共110頁(yè) 12 8 s.t. 16 12 02132maxxxZ212xx 14x24x21,xx2122xx 第29頁(yè)/共110頁(yè)O123456132456782x1x0,21xx第30頁(yè)/共110頁(yè)412345613256O782x1x122221 xx第31頁(yè)/共110頁(yè)54R1234561326O782x1x122221 xx8221 xx第32頁(yè)/共110頁(yè)4QR12345613256O782x1x122221 xx8221 xx1641x1242xPS第33

9、頁(yè)/共110頁(yè)P(yáng)QRS123456132456O782x1x122221 xx8221 xx1641x1242x第34頁(yè)/共110頁(yè)P(yáng)QRS123456132456O782x1x122221 xx8221 xx1641x1242x2132xxZ第35頁(yè)/共110頁(yè)P(yáng)QRS123456132456O782x1x122221 xx8221 xx1641x1242x(4,2)第36頁(yè)/共110頁(yè)第37頁(yè)/共110頁(yè)O123456132456782x1x第38頁(yè)/共110頁(yè)P(yáng)QRS123456132456O782x1x122221 xx8221 xx1641x1242x可行域第39頁(yè)/共110頁(yè)P(yáng)QR

10、S123456132456O782x1x122221 xx8221 xx1641x1242x(4,2)可行域n思考：當(dāng)目標(biāo)函數(shù)改為時(shí)，最優(yōu)解是什么？2142maxxxZ第40頁(yè)/共110頁(yè)第41頁(yè)/共110頁(yè)第42頁(yè)/共110頁(yè)第43頁(yè)/共110頁(yè)第44頁(yè)/共110頁(yè)第45頁(yè)/共110頁(yè)是否為可行解？）（，）（，）（判斷TTTXXXxxxxxxtsxxz1 23 11 5 0, 42 63 .23 max21212121第46頁(yè)/共110頁(yè)的約束方程系數(shù)矩陣為該例：LP 1 0 2- 10 1- 3 1 4 2 6 3 421321Axxxxxx第47頁(yè)/共110頁(yè) 1 0 2- 10 1-

11、3 1 4 2 6 3 421321Axxxxxx系數(shù)矩陣?yán)?2- 13 11B0 11- 12B1 0 0 1 1 2-0 3 0 2-1- 3 654BBB1 10 13B需要扣除奇異矩陣為：基矩陣的個(gè)數(shù)（最多）,)!( ! mnmnCmn第48頁(yè)/共110頁(yè)4 2- 16 3 1462- 13 1 21增廣矩陣如上例：xxbBXB2- 5- 06 3 1初等變換52 1 06 3 152 1 0524 0 152 52421xxTX0 0 52 524)1(TX0) 2- 0 4()2(TX2)- 0 0 6()3(TTTXXX4) 6- 0 0( 8) 0 2 0( 0) 12- 2

12、- 0()6(5)4(第49頁(yè)/共110頁(yè)可行解基本解基本可行解結(jié)論：若LP問(wèn)題存在最優(yōu)解，則一定可以在 基本可行解中找到。第50頁(yè)/共110頁(yè)）最優(yōu)解）基本可行解；）所有的基本解；求：?jiǎn)栴}如下：練習(xí)：有3 2 14 , 3 , 2 , 1 0 30332 50542 . 423max 432143214321jxxxxxxxxxtsxxxxzLPj第51頁(yè)/共110頁(yè)3- 31 5 3- 21 4 3 25 4 3- 11 2 3 15 2) 154321BBBBB基矩陣：解：TTTXXXXX710- 0 790 0710- 0 0 71800 10 0 0)2)4(2)5()3(1（退化解

13、）基本解：）（)5()3(1,)3XXX）（基本可行解：10z 0 10 0 0)4*T*）（最優(yōu)解：X2 14 20*B第52頁(yè)/共110頁(yè)* LP問(wèn)題存在可行解，則問(wèn)題的可行域是凸集* LP問(wèn)題的基本可行解X對(duì)應(yīng)LP問(wèn)題可行域的頂點(diǎn)* LP問(wèn)題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解第53頁(yè)/共110頁(yè)單純形法思路初始基可行解新的基可行解最優(yōu)性條件最優(yōu)解換基迭代YN第54頁(yè)/共110頁(yè)第55頁(yè)/共110頁(yè)0,40025005 . 2516002200034max515142132154321xxxxxxxxxxxxxxxz第56頁(yè)/共110頁(yè)4001000125000105 . 251600

14、0012254321bxxxxx1000100011B第57頁(yè)/共110頁(yè)n目標(biāo)函數(shù)與最優(yōu)性檢驗(yàn)543,xxx152142134005 . 252500221600 xxxxxxxxTX400,2500,1600,0 ,0154321100034xxxxxZ第58頁(yè)/共110頁(yè)1x400140050052500800216004001000125000105 . 2516000012254321bxxxxx5x對(duì)目標(biāo)函數(shù)貢獻(xiàn)大（價(jià)值系數(shù)高）受資源的約束，400所對(duì)應(yīng)的資源最緊張第59頁(yè)/共110頁(yè)1005102012B143,xxx400100015005105 . 2080020120543

15、21bxxxxx第60頁(yè)/共110頁(yè)TX0,500,800,0,4002522524316003)400(4xxxxZ第61頁(yè)/共110頁(yè)2x4x2005 . 25004002800400100015005105 . 208002012054321bxxxxx不考慮零與負(fù)值第62頁(yè)/共110頁(yè)v新基v新的基變量：v新的基本可行解10055.202213B123,xxx4001000120024 . 001040028 . 010054321bxxxxx第63頁(yè)/共110頁(yè)v基本可行解v目標(biāo)函數(shù)TX0,0,400,200,400354545322 . 12200)24 . 0200(3)400(

16、4xxxxxZ第64頁(yè)/共110頁(yè)v確定入基變量：v確定出基變量：5x3x400140020024004001000120024 . 001040028 . 010054321bxxxxx不考慮零與負(fù)值第65頁(yè)/共110頁(yè)10155.202204B125,xxx20004 . 05 . 00160004 . 00 . 11020014 . 05 . 00054321bxxxxx第66頁(yè)/共110頁(yè)。TX200,0,0,600,200443434344 . 02600)4 . 0600(3)4 . 05 . 0200(4xxxxxxZ第67頁(yè)/共110頁(yè)nixbAxxptscxxcziniiin

17、iii, 3 , 2 , 1, 0)(. .)(max11第68頁(yè)/共110頁(yè)NBNxbBxNBNxBbBx11NNBBxCxCzminmjjmiijijiiNBNBNNNBxaccbcxNBCCbBCxCNxBbBCz1111111)()()(NBxxxNBA,第69頁(yè)/共110頁(yè)miiiBbcbBCz110miijijBjBjacPBCNBCz111)(jjjzc nmjjjxzz10第70頁(yè)/共110頁(yè)第71頁(yè)/共110頁(yè)430000001600250040025122.5010001000180050040043000jcBcBx1x2xjjjzc 3x4x5x3x4x5xbBCB1b

18、B1第72頁(yè)/共110頁(yè)430000001600250040025122.50100010001800500400043000jcBCBx1x2x3x4x5x3x4x5xjjjzc bBCB1bB1第73頁(yè)/共110頁(yè)4300000480050040000122.50100010-2-514002000不算不算16000300-4jcBCBx1x2x3x4x5x3x4x1xjjjzc bB1330202.54016000800+0500+4400第74頁(yè)/共110頁(yè)43000034400200400001010100-0.80.402-21200負(fù)值負(fù)值 不算不算4002200000-1.22

19、jcBCBx1x2x3x4x5x3x2x1xjjjzc bB1第75頁(yè)/共110頁(yè)430000342006002000010100.51-0.5-0.4-0.40.4100260000-1-0.40jcBCBx1x2x3x4x5x5x2x1xjjjzc bB1第76頁(yè)/共110頁(yè)第77頁(yè)/共110頁(yè)單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論1、無(wú)界解、無(wú)界解4 , 3 , 2 , 1 0 4 3- 2 s.t 32max j2421132121jxlxxxlxxxxxz例：O1x2x2l1lz第78頁(yè)/共110頁(yè)cj2300bcBxBx1x2x3x400 x3x41-110-310124j230

20、020 x1x41-1100-231210j05-20結(jié)論：結(jié)論：若若j0,對(duì)應(yīng)的系數(shù)列向量對(duì)應(yīng)的系數(shù)列向量0，則該，則該LP存在無(wú)存在無(wú)界解。界解。第79頁(yè)/共110頁(yè)2、多個(gè)解22112121 2127 2172 144max lxxlxx s.txxz例：x1x2l2l1OABC第80頁(yè)/共110頁(yè) cj4 14 0 0b cB xBx1 x2 x3 x300 x3X42 7 1 07 2 0 121213j4 14 0 014 0 x2x42/7 1 1/7 045/7 0 -2/7 1315j 0 0 -2 0z=4221/27/314 4x2x1 0 1 7/45 -2/45 1

21、0 2/45 7/457/37/3j 0 0 -2 0z=4221/2第81頁(yè)/共110頁(yè)42)01 ()1 (0 0 37 37,15 0 3 0*)2()1(*)2()1(zXXXXXTT結(jié)論：若某個(gè)非基變量的檢驗(yàn)系數(shù)為零，則該 LP存在多個(gè)最優(yōu)解。當(dāng)所有的檢驗(yàn)數(shù)全部小于等于零時(shí),若有某個(gè)非基變量的檢驗(yàn)數(shù)也是零,則該線性規(guī)劃有無(wú)窮多組解,否則有唯一解.第82頁(yè)/共110頁(yè)3、退化解0, 3 4 2 2 . 5 . 12max 321321312131xxxxxxxxxxtsxxz例：第83頁(yè)/共110頁(yè)cj2 0 1.5 0 0 0bcBxBx1 x2 x3 x4 x5 x6000 x4x

22、5x61 -1 0 1 0 02 0 1 0 1 01 1 1 0 0 1243223j2 0 1.5 0 0 0200 x1x5x61 -1 0 1 0 00 2 1 -2 1 00 2 1 -1 0 1201j0 2 1.5 -2 0 0基本可行解中基變量等于零第84頁(yè)/共110頁(yè)*在單純形法的計(jì)算過(guò)程中，確定換出基變量時(shí)存在在單純形法的計(jì)算過(guò)程中，確定換出基變量時(shí)存在兩兩個(gè)或兩個(gè)以上的最小比值，這時(shí)會(huì)出現(xiàn)退化解個(gè)或兩個(gè)以上的最小比值，這時(shí)會(huì)出現(xiàn)退化解。特征：基本可行解中，基變量等于零特征：基本可行解中，基變量等于零*有時(shí)，退化會(huì)造成計(jì)算過(guò)程的循環(huán)，永遠(yuǎn)達(dá)不到有時(shí)，退化會(huì)造成計(jì)算過(guò)程的循環(huán)

23、，永遠(yuǎn)達(dá)不到最優(yōu)解最優(yōu)解。4,.,2 , 1 0 1 03211221 09841s.t 6212043min6.j3432143214321jxxxxxxxxxxxxxxzBealeE次后又回到初始解）代給出的循環(huán)例子：（迭由*用勃蘭特法則一定可以避免出現(xiàn)循環(huán)用勃蘭特法則一定可以避免出現(xiàn)循環(huán)第85頁(yè)/共110頁(yè)為避免循環(huán),常采用1976年R.G.Bland提出Bland法則:單純形表中有若干個(gè)檢驗(yàn)數(shù)大于零大于零 時(shí),取下取下標(biāo)號(hào)小標(biāo)號(hào)小的非基變量為換入基變量入基變量; 用 法則選取換出基出基變量時(shí),若比值相同,則選取下標(biāo)號(hào)小下標(biāo)號(hào)小的基變量為換出基變量. 勃蘭特（Bland）法則第86頁(yè)/共

24、110頁(yè)4、無(wú)可行解（大M法）0, 40 30 150103 . 3020max212112121xxxxxxxtsxxz例：第87頁(yè)/共110頁(yè) cj20 30 0 0 0 -MbcBxBx1 x2 x3 x4 x5 x6 00-Mx3x4x63 10 1 0 0 01 0 0 1 0 01 1 0 0 -1 11503040j20+M 30+M 0 0 -M 0 3020-Mx2x1x60 1 1/10 -3/10 0 01 0 0 1 0 00 0 -1/10 -7/10 -1 1 6 30 4 j0 0 3-M/10 -11-7M/10 M 0第88頁(yè)/共110頁(yè)xBx1x2x3x4x

25、5bx2x3x5110-40-201-30300a153dj-3000討論題討論題在求解極大化在求解極大化LP問(wèn)題中，得到如下單純形表：?jiǎn)栴}中，得到如下單純形表：1、當(dāng)前解為最優(yōu)解時(shí)，各參數(shù)應(yīng)滿足的條件；、當(dāng)前解為最優(yōu)解時(shí)，各參數(shù)應(yīng)滿足的條件；2、原問(wèn)題存在無(wú)界解時(shí)，各參數(shù)應(yīng)滿足的條件；、原問(wèn)題存在無(wú)界解時(shí)，各參數(shù)應(yīng)滿足的條件；3、原問(wèn)題存在多個(gè)解時(shí)，各參數(shù)應(yīng)滿足的條件；、原問(wèn)題存在多個(gè)解時(shí)，各參數(shù)應(yīng)滿足的條件；4、當(dāng)、當(dāng)x4作為進(jìn)基變量取代作為進(jìn)基變量取代x5時(shí)，目標(biāo)值的增量為多少？時(shí)，目標(biāo)值的增量為多少？結(jié)論：結(jié)論：若基變量中有非零的人工變量，則該若基變量中有非零的人工變量，則該LP無(wú)可行

26、解。無(wú)可行解。第89頁(yè)/共110頁(yè)第90頁(yè)/共110頁(yè) 標(biāo)準(zhǔn)型j0,maxXbAXCXz0,minXbAXCXzjjzc 00第91頁(yè)/共110頁(yè)0,18231224. .53max21212121xxxxxxtsxxz第92頁(yè)/共110頁(yè)0,18231224. .)(053max43212142314321xxxxxxxxxxtsxxxxz第93頁(yè)/共110頁(yè)0,18231224. .)(053max521521423154321xxxxxxxxxxtsMxxxxxz第94頁(yè)/共110頁(yè)3500-Mb00-M41218103022100010001 4 6-18M3+3M5+2M000jcBcBx1x2xjjjzc 3x4x5x5x4x3x第95頁(yè)/共110頁(yè)3500-Mb30-M412610002210-30100016312-6M05+2M-3-M00jcBcBx1x2xjjjzc 3x4x5x5x4x1x第96頁(yè)/共110頁(yè)3500-Mb30546310000113-1.50100-10.54227