第二線性規(guī)劃與單純形法學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1第二第二(d r)線性規(guī)劃與單純形法線性規(guī)劃與單純形法第一頁，共65頁。1 1線性規(guī)化問題線性規(guī)化問題(wnt)(wnt)及其及其數(shù)學(xué)模型數(shù)學(xué)模型設(shè)備設(shè)備原材料原材料A A原材料原材料B B1 14 40 02 20 04 48 8 臺(tái)時(shí)臺(tái)時(shí)16 kg16 kg12 kg12 kg利潤利潤2 23 32132xxz max8221 xx1641 x1242 x021 xx ， 目標(biāo)目標(biāo)(mbio)函函數(shù)數(shù)約束條件約束條件 1.1 問題(wnt)的提出x1x2z第1頁/共65頁第二頁，共65頁。第2頁/共65頁第三頁，共65頁。500萬萬m3200萬萬m3工廠工廠(gng(gngchng

2、)chng)1 1工廠工廠(gn(gngchgchng)2ng)22萬萬m31000元元/萬萬m31.4萬萬m3800元元/萬萬m3小于小于0.2%自然自然(zrn)(zrn)凈化凈化20%20%218001000 xxz min11 x6 . 18 . 021 xx4 . 12 x021 xx ，目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件21 x%2.050021 x%2 . 0200500)4 . 1 ()2( 8 . 021xx1x2x第3頁/共65頁第四頁，共65頁。218001000 xxz min11 x6 . 18 . 021 xx4 . 12 x021 xx ，21 x 01241648

3、232max21212121xxxxxxxxz，第4頁/共65頁第五頁，共65頁。nnxcxcxcz 2211max(min)11212111)(bxaxaxann ，22222121)(bxaxaxann ，mnmnmmbxaxaxa)(2211 ，021 nxxx， 目標(biāo)目標(biāo)(mbio)函數(shù)函數(shù)約束條件約束條件 線性規(guī)劃問題(wnt)解的概念可行解可行解： 若（若（x1，x2，xn）滿足上述約束條件，則）滿足上述約束條件，則稱（稱（x1，x2，xn）為線性規(guī)劃問題的可行解。）為線性規(guī)劃問題的可行解?？尚杏蚩尚杏颍核锌尚薪饨M成的集合稱為可行域。所有可行解組成的集合稱為可行域。最優(yōu)解：最優(yōu)解

4、： 使目標(biāo)函數(shù)達(dá)到最大或最小的可行解稱為最優(yōu)解。使目標(biāo)函數(shù)達(dá)到最大或最小的可行解稱為最優(yōu)解。第5頁/共65頁第六頁，共65頁。Z= 2Z= 6Z=10Q(4, 2)x2x10 1 2 3 4 54321Z=14X*= (4，2) Z*=14 01241648232max21212121xxxxxxxxz，第6頁/共65頁第七頁，共65頁。 線性規(guī)劃線性規(guī)劃(xin xn u hu)(xin xn u hu)圖解法解題步驟圖解法解題步驟 4 4 將最優(yōu)解代入目標(biāo)將最優(yōu)解代入目標(biāo)(mbio)(mbio)函數(shù)，求出最優(yōu)目函數(shù)，求出最優(yōu)目標(biāo)標(biāo)(mbio)(mbio)函數(shù)值。函數(shù)值。 1 1 在直角平面

5、坐標(biāo)系中畫出所有的約束等式，并在直角平面坐標(biāo)系中畫出所有的約束等式，并找出所有約束條件的公共找出所有約束條件的公共(gnggng)(gnggng)部分，即可行域，部分，即可行域，可行域中的點(diǎn)即為可行解?？尚杏蛑械狞c(diǎn)即為可行解。 2 2 標(biāo)出目標(biāo)函數(shù)值增加的方向。標(biāo)出目標(biāo)函數(shù)值增加的方向。 3 3 若求最大（?。┲?，則令目標(biāo)函數(shù)等值線沿（逆）若求最大（?。┲?，則令目標(biāo)函數(shù)等值線沿（逆）目標(biāo)函數(shù)值增加的方向平行移動(dòng)，找與可行域最后相交的點(diǎn)，目標(biāo)函數(shù)值增加的方向平行移動(dòng)，找與可行域最后相交的點(diǎn)，該點(diǎn)就是最優(yōu)解。該點(diǎn)就是最優(yōu)解。第7頁/共65頁第八頁，共65頁。X2X10 1 2 3 4 54321X

6、2X10 1 2 3 4 54321無窮無窮(wqing)多最優(yōu)解多最優(yōu)解無界解無界解AB 唯一唯一(wi y)最優(yōu)解最優(yōu)解 無窮多最優(yōu)解無窮多最優(yōu)解 無界解無界解 無可行解無可行解有最優(yōu)解有最優(yōu)解無最優(yōu)解無最優(yōu)解第8頁/共65頁第九頁，共65頁。nnxcxcxcz 2211max11212111bxaxaxann 22222121bxaxaxann mnmnmmbxaxaxa 2211021 nxxx， 目標(biāo)目標(biāo)(mbio)函函數(shù)數(shù)約束條件約束條件 mnmmnnaaaaaaaaaA212222111211 mbbbb21 ncccC21 nxxxX21 mjjjjaaaP21第9頁/共65頁

7、第十頁，共65頁。 njxbxPCXjnjjj，210max njxmibxaxcjnjijijnjjj，21021max0max XbAXCX標(biāo)準(zhǔn)型的其它標(biāo)準(zhǔn)型的其它(qt)表示形式表示形式第10頁/共65頁第十一頁，共65頁。 無約束無約束，32132132132132105232732minxxxxxxxxxxxxxxxz例例： 05)(232)(7)()(32)max543321332153321433213321xxxxxxxxxxxxxxxxxxxxxxxxz，（第11頁/共65頁第十二頁，共65頁。 032274326325max4321432143214321xxxxxxxxx

8、xxxxxxxz， 003113101221327212121，Xxxxx 051105201231327323131，Xxxxx 6110031022413227434141，Xxxxx例：例：第12頁/共65頁第十三頁，共65頁。 003113101221327212121，Xxxxx 051105201231327323131，Xxxxx 6110031022413227434141，Xxxxx)0120(01132373243232， Xxxxx無窮多解無窮多解02142327424242 xxxx 1100021433274354343， Xxxxx1 z3 z基基*543 z第13

9、頁/共65頁第十四頁，共65頁。基可行解：滿足非負(fù)條件的基解稱為基可行解?？尚谢? 對(duì)應(yīng)于基可行解的基稱為可行基。注：基解的個(gè)數(shù)最多是Cnm個(gè)，基可行解的個(gè)數(shù)一般要小于基解的個(gè)數(shù)。第14頁/共65頁第十五頁，共65頁。1 1 可行可行(kxng)(kxng)解與最解與最優(yōu)解：優(yōu)解：最優(yōu)解一定最優(yōu)解一定(ydng)(ydng)是可行解，但可行解不一定是可行解，但可行解不一定(ydng)(ydng)是最優(yōu)解。是最優(yōu)解。線性規(guī)劃(xin xn u hu)解之間的關(guān)系基解不一定是可行解，可行解也不一定是基解?；獠灰欢ㄊ强尚薪?，可行解也不一定是基解。2 2 可行解與基解：可行解與基解：3 3 可行解與

10、基可行解：可行解與基可行解：基可行解一定是可行解，但可行解不一定是基解。基可行解一定是可行解，但可行解不一定是基解?；尚薪庖欢ㄊ腔?，基可行解一定是基解，但基解不一定是基可行解。但基解不一定是基可行解。4 4 基解與基可行解：基解與基可行解：5 5 最優(yōu)解與基解：最優(yōu)解與基解：最優(yōu)解不一定是基解，最優(yōu)解不一定是基解，基解也不一定是最優(yōu)解?；庖膊灰欢ㄊ亲顑?yōu)解。問題：最優(yōu)解與基本可行解？問題：最優(yōu)解與基本可行解？非可行解可行解基本可行解基本解第15頁/共65頁第十六頁，共65頁。X1X2X1X2X1X22. 凸組合凸組合(zh)：3 . 頂 點(diǎn)頂 點(diǎn)(dngdin)：1.1.凸集：凸集： 凸集

11、：設(shè)凸集：設(shè)K是是n維歐氏空間的維歐氏空間的一個(gè)點(diǎn)集，若任意兩點(diǎn)一個(gè)點(diǎn)集，若任意兩點(diǎn)X(1)， X(2)K的連線上的一切點(diǎn)的連線上的一切點(diǎn)X=X(1)+(1-)X(2) K ，（，（0 1），則稱），則稱K為凸集。為凸集。 凸組合：設(shè)凸組合：設(shè)X(1) ，X(2) X(k) 是是n維維歐氏空間的歐氏空間的k個(gè)點(diǎn)，若存在個(gè)點(diǎn)，若存在1，2 k， 且且0 i 1， i=1，2 k， i =1，使，使X=1 X(1) + 2 X(2) + +k X(k)則稱則稱X為為X(1) ， X(2) ， X(k)的凸的凸組合。組合。 頂點(diǎn)：設(shè)頂點(diǎn)：設(shè)K是一凸集，是一凸集， XK，若，若X不能表示成不能表示成K

12、中不同兩點(diǎn)中不同兩點(diǎn)X(1) ， X(2)的凸組合的凸組合 X = X( 1 )+ ( 1 - ) X( 2 ) （01）則則X稱為稱為K的頂點(diǎn)或極點(diǎn)。的頂點(diǎn)或極點(diǎn)。第16頁/共65頁第十七頁，共65頁。0| XbAXXD，則有則有內(nèi)的任意兩點(diǎn)，內(nèi)的任意兩點(diǎn)，是是，設(shè)設(shè),)2()1()2()1(XXDXX 0,)1()1( XbAX0,)2()2( XbAX連線上的任一點(diǎn)，則連線上的任一點(diǎn)，則，是是令令)2()1(XXX）（）（10-1X)2()1( XX-1AX)2()1(XXA）（ )2()1(-1AXAX）（ bb）（ -1 b 0 X又又DX 是凸集是凸集D證：證：行域，則其可行域?yàn)樾?/p>

13、域，則其可行域?yàn)槿艟€性規(guī)劃問題存在可若線性規(guī)劃問題存在可第17頁/共65頁第十八頁，共65頁。第18頁/共65頁第十九頁，共65頁。bxPmjjj 定定不不是是可可行行域域的的頂頂點(diǎn)點(diǎn)。不不是是基基可可行行解解，則則它它一一若若X)1(02211 mmPPP ）兩式的）兩式的），（），（由（由（，設(shè)設(shè)210 證：證：個(gè)分量為正。個(gè)分量為正。的前的前行解行解不失一般性，假設(shè)基可不失一般性，假設(shè)基可mX則有則有使得使得，的數(shù)的數(shù)存在一組不全為存在一組不全為數(shù)列向量線性相關(guān)。即數(shù)列向量線性相關(guān)。即的正分量所對(duì)應(yīng)的系的正分量所對(duì)應(yīng)的系知知例例不是基可行解，則由引不是基可行解，則由引若若mXX 2101

14、bPxPxPxmmm )()()(222111bPxPxPxmmm )()()(222111第19頁/共65頁第二十頁，共65頁。bPxPxPxmmm )()()(222111bPxPxPxmmm )()()(22211100)()()(2211)1(，mmxxxX 00)()()(2211)2(，mmxxxX 0)2()1( XX，充充分分小小時(shí)時(shí)，可可保保證證當(dāng)當(dāng) 是是可可行行解解。，即即)2()1(XX，又又知知)2()1(2121XXX 連連線線的的中中點(diǎn)點(diǎn)。是是即即)2(1),XXX。一一定定不不是是可可行行域域的的頂頂點(diǎn)點(diǎn)X第20頁/共65頁第二十一頁，共65頁。它它一一定定不不是

15、是基基可可行行解解。不不是是可可行行域域的的頂頂點(diǎn)點(diǎn)，則則）若若（X2兩兩點(diǎn)點(diǎn)的的可可在在可可行行域域中中找找到到不不同同不不是是可可行行域域的的頂頂點(diǎn)點(diǎn)，則則若若X)()1()1(2)1(1)1(，nxxxX )()2()2(2)2(1)2(，nxxxX 10)1()2()1( XXX使使是基可行解，是基可行解，假設(shè)假設(shè)X線性無關(guān)。線性無關(guān)。，知知?jiǎng)t由引例則由引例mPPP2110j)2()1( jjjxxxm時(shí)，有時(shí)，有當(dāng)當(dāng)是可行域中的兩點(diǎn)是可行域中的兩點(diǎn)，)2()1(XX mjjjmjjjbxPbxP)2()1(，0)()2()1( mjjjjxxP第21頁/共65頁第二十二頁，共65頁。

16、是基可行解，是基可行解，假設(shè)假設(shè)X0j)2()1( jjjxxxm時(shí)，有時(shí)，有當(dāng)當(dāng)是可行域中的兩點(diǎn)是可行域中的兩點(diǎn)，)2()1(XX mjjjmjjjbxPbxP)2()1(，0)()2()1( mjjjjxxP21XX 0)()2()1(不全為不全為jjxx 線性相關(guān)。線性相關(guān)。，mPPP11不是基可行解。不是基可行解。知知由引例由引例X1這和假設(shè)相矛盾。這和假設(shè)相矛盾。假設(shè)不真。假設(shè)不真。一定不是基可行解。一定不是基可行解。X線性無關(guān)。線性無關(guān)。，知知?jiǎng)t由引例則由引例mPPP211第22頁/共65頁第二十三頁，共65頁。證：證：。函數(shù)的最優(yōu)解一定存在函數(shù)的最優(yōu)解一定存在若可行域有界，則目標(biāo)

17、若可行域有界，則目標(biāo)是可行域的所有頂點(diǎn)。是可行域的所有頂點(diǎn)。，設(shè)設(shè))(2)(1)XXXk點(diǎn)達(dá)到最優(yōu)。點(diǎn)達(dá)到最優(yōu)。設(shè)目標(biāo)函數(shù)在設(shè)目標(biāo)函數(shù)在(0)X理理得得證證；是是可可行行域域的的頂頂點(diǎn)點(diǎn)，則則定定若若(0)X點(diǎn)的凸組合，即點(diǎn)的凸組合，即可表示為頂可表示為頂知知由引理由引理不是可行域的頂點(diǎn)，則不是可行域的頂點(diǎn)，則若若)0(0)2XX kiiikiiiX10X)(0) ， kiiikiiiCXXC)()(0)CX 第23頁/共65頁第二十四頁，共65頁。 kiiikiiiCXXC)()(0)CX ，則，則，令令)(i)21|maxCXmCXki kimimikiiCXCXCX)()()(0)CX

18、)(0)CXmCX 即即是最大值是最大值又又(0)CX)(0)CXmCX )(0)CXmCX 達(dá)達(dá)到到最最優(yōu)優(yōu)。即即目目標(biāo)標(biāo)函函數(shù)數(shù)在在頂頂點(diǎn)點(diǎn))(mX 1. 1. 如果目標(biāo)如果目標(biāo)(mbio)(mbio)函數(shù)在多個(gè)頂點(diǎn)上達(dá)到最優(yōu)，則目函數(shù)在多個(gè)頂點(diǎn)上達(dá)到最優(yōu)，則目標(biāo)標(biāo)(mbio)(mbio)函數(shù)在這些頂點(diǎn)的凸組合上也達(dá)到最優(yōu)。函數(shù)在這些頂點(diǎn)的凸組合上也達(dá)到最優(yōu)。 2. 2. 如果如果(rgu)(rgu)可行域?yàn)闊o界，則可能有最優(yōu)解，也可能無最優(yōu)解，可行域?yàn)闊o界，則可能有最優(yōu)解，也可能無最優(yōu)解，若有最優(yōu)解，則必在某個(gè)頂點(diǎn)上達(dá)到最優(yōu)。若有最優(yōu)解，則必在某個(gè)頂點(diǎn)上達(dá)到最優(yōu)。第24頁/共65頁第二十

19、五頁，共65頁。線性規(guī)劃問題的幾何線性規(guī)劃問題的幾何(j h)意義：意義： 4. 4.如果目標(biāo)函數(shù)在多個(gè)頂點(diǎn)上達(dá)到最優(yōu)，則目標(biāo)如果目標(biāo)函數(shù)在多個(gè)頂點(diǎn)上達(dá)到最優(yōu)，則目標(biāo)函數(shù)在這些頂點(diǎn)的凸組合上也達(dá)到最優(yōu)函數(shù)在這些頂點(diǎn)的凸組合上也達(dá)到最優(yōu), ,即線性規(guī)劃即線性規(guī)劃(xin xn u hu)(xin xn u hu)問題有無群多最優(yōu)解。問題有無群多最優(yōu)解。第25頁/共65頁第二十六頁，共65頁。 X1 CX1 X2 CX2 X3 CX3 Xn CXn*B1B2B3Bn1. 1. 初始基初始基B1B1及所對(duì)應(yīng)基可行及所對(duì)應(yīng)基可行(kxng)(kxng)解解X1X1的確定；的確定； 2. Xj 2. X

20、j 的最優(yōu)性判定的最優(yōu)性判定(pndng)(pndng)； 4. 4. 求下一個(gè)求下一個(gè)(y )(y )頂點(diǎn)頂點(diǎn) Xj+1 Xj+1 。3. 3. 基變換基變換 ；Bj Bj+1第26頁/共65頁第二十七頁，共65頁。 01241648232max54321524132121xxxxxxxxxxxxxxz， 2154311xxXxxxXNB， 124164825241321xxxxxxx2x換入變量換入變量5x換出變量換出變量 0121680011 zX，4/3* zxx 2132第27頁/共65頁第二十八頁，共65頁。 2154311xxXxxxXNB， 124164825241321xxx

21、xxxx2x換入變量換入變量5x換出變量換出變量 0121680011 zX，4/3* zxx 2132 5124322xxXxxxXNB， 34152 xx943251 zxx16441 xx221531 xxx 901623022 zX，24/1x換入變量換入變量3x換出變量換出變量*1 第28頁/共65頁第二十九頁，共65頁。 5124322xxXxxxXNB， 34152 xx943251 zxx16441 xx221531 xxx 901623022 zX，24/1x換入變量換入變量3x換出變量換出變量*1 5324133xxXxxxXNB， 34152 xx1341253 zxx8

22、24543 xxx221531 xxx 130803233 zX，/4125x換入變量換入變量4x換出變量換出變量* 第29頁/共65頁第三十頁，共65頁。 5324133xxXxxxXNB， 34152xx1341253 zxx824543 xxx221531 xxx 130803233 zX，/4125x換入變量換入變量4x換出變量換出變量* 4325144xxXxxxXNB， 28121432 xxx14812343 zxx4212543 xxx44141 xx 1440024*4*4 zX， 第30頁/共65頁第三十一頁，共65頁。34152xx943251zxx16441 xx221

23、531xxx24/*1NoImage124164825241321xxxxxxx4/3* zxx2132/ 94300023410010160100422101011 000032121004016010048001214第31頁/共65頁第三十二頁，共65頁。28121432xxx14812343zxx4212543xxx44141xx34152xx1341253zxx824543xxx/412* 221531xxx 1408123002081211041212004041001 13410200341001082140022101012第32頁/共65頁第三十三頁，共65頁。Q2 (4,

24、2)X2X10 1 2 3 4 54321 0121680011 zX， 901623022 zX， 130803233 zX， 144002444 zX，Q1(4, 0)Q3(2, 3)Q4(0, 3)OQ4Q2Q3*第33頁/共65頁第三十四頁，共65頁。0max XbAXCXz0max XbXAXCXzS化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型則初始則初始(ch sh)可行解為可行解為 mbbbX，21000 2.人造基法：每個(gè)約束條件加上一個(gè)非負(fù)人工變量人造基法：每個(gè)約束條件加上一個(gè)非負(fù)人工變量后組成后組成(z chn)一個(gè)人造基。具體方法下節(jié)討論。一個(gè)人造基。具體方法下節(jié)討論。第34頁/共65頁第三十五

25、頁，共65頁。性規(guī)劃問題有無窮多最優(yōu)解。 3. 無界解判別定理：若X(0)是線性規(guī)劃問題的一個(gè)基可行解，若存在(cnzi)一非基變量的檢驗(yàn)數(shù)大于零，而該非基變量的系數(shù)向量小于等于零，則該線性規(guī)劃問題有無界解。第35頁/共65頁第三十六頁，共65頁。(binling)xlalk 素，它所在的列稱為主元列，它所在的行稱為主元行。第36頁/共65頁第三十七頁，共65頁。 011ln111111000100010001zzbaaabaaabaaankmmmnmkmmllklmnkm 011ln1111110000101010001zzabaaaabaaabaaaanmlkkmmmnmmlkmkllml

26、knmlkk 第37頁/共65頁第三十八頁，共65頁。第38頁/共65頁第三十九頁，共65頁。01zbbbml 011ln111111000100010001zzbaaabaaabaaankmmmnmkmmllklmnkm zxxxml1XBb1xlxmx1 mxkxnx ml 1zxxxmk1nmlkkmmnmmlkmknllmlknmlkkaaaaaaaaaaaa 0000101010001111111101zbbbml 第39頁/共65頁第四十頁，共65頁。 5. 5. 迭代，即利用高斯消去法迭代，即利用高斯消去法或矩陣初等變換，把主元素變成或矩陣初等變換，把主元素變成1 1，主元列的其

27、他元素變成主元列的其他元素變成0 0。 6. 6.重復(fù)重復(fù)2626步。步。第40頁/共65頁第四十一頁，共65頁。 01241648232max54321524132121xxxxxxxxxxxxxxz，b2x3x4x5xBXBC1x543xxx 8 1 2 1 0 0 16 4 0 0 1 0 12 0 4 0 0 1 0 2 3 0 0 0 243xxx241xxx2 1 0 1 0 -1/2 16 4 0 0 1 0 3 0 1 0 0 1/4 -9 2 0 0 0 -3/4 2 1 0 1 0 -1/2 8 0 0 -4 1 2 3 0 1 0 0 1/4 -13 0 0 -2 0 1

28、/4 3/4000 300302/42124/z z z 第41頁/共65頁第四十二頁，共65頁。 2 1 0 1 0 -1/2 8 0 0 -4 1 2 3 0 1 0 0 1/4 -13 0 0 -2 0 1/4 302124/z 241xxx 4 1 0 1 1/4 0 4 0 0 -2 1/2 1 2 0 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0 302z 251xxxb2x3x4x5xBXBC1x 14*40024* ZX，第42頁/共65頁第四十三頁，共65頁。nnxcxcxcz 2211max11212111bxaxaxann 22222121bxaxax

29、ann mmnnmnmmbxxaxaxa 2211021 nxxx， 111212111bxxaxaxannn 222222121bxxaxaxannn mnmnmmbxaxaxa 2211 第43頁/共65頁第四十四頁，共65頁。nnxcxcxcz 2211maxmnnnMxMxMx 21例例 0123241123max32131321321321xxxxxxxxxxxxxxz，114 x35 x365 xx1 17 x11 mmnnmnmmbxxaxaxa 2211111212111bxxaxaxannn 222222121bxxaxaxannn 021 nxxx，67MxMx第44頁/共

30、65頁第四十五頁，共65頁。例例 0123241123max32131321321321xxxxxxxxxxxxxxz，114 x35 x365 xx1 17 x11 67MxMxb2x3x4x5xBXBC1x 6x7x1 1 00C3M M 764xxx364xxx324xxxMM01M0113 12/311/1/4 4M 3-6M -1+M -1+3M 0 -M 0 0 11 1 -2 1 1 0 0 0 3 -4 1 2 0 -1 1 0 1 -2 0 1 0 0 0 1 10 3 -2 0 1 0 0 -1 1 0 1 0 0 -1 1 -2 1 -2 0 1 0 0 0 1 12 3

31、 0 0 1 -2 2 -5 1 -2 -2 1 0 0 0 1 1 0 1 0 0 -1 1 -21+M 1 -1+M 0 0 -M 0 1-3M 2 1 0 0 0 -1 1-M -1-M 0z z z 第45頁/共65頁第四十六頁，共65頁。324xxx110/4 12 3 0 0 1 -2 2 -5 1 -2 0 1 0 0 0 1 1 0 1 0 0 -1 1 -2 2 1 0 0 0 -1 1-M -1-M 321xxx113 4 1 0 0 1/3 -2/3 2/3 -5/3 9 0 0 1 2/3 -4/3 4/3 7/3 1 0 1 0 0 -1 1 -2 -2 0 0 0

32、-1/3 -1/3 1/3-M 2/3-Mb2x3x4x5xBXBC1x 6x7x 2*00914* ZX，z z 第46頁/共65頁第四十七頁，共65頁。mnnnxxxz 21max第二階段：第二階段：nnxcxcxcz 2211max第一階段的最終第一階段的最終(zu zhn)單純形單純形表表mmnnmnmmbxxaxaxa 2211111212111bxxaxaxannn 222222121bxxaxaxannn 021 nxxx，第47頁/共65頁第四十八頁，共65頁。b2x3x4x5xBXBC1x 6x7x0000C01 1 764xxx364xxx324xxx1-1-001-000

33、012/311/1/ 4 -6 1 3 0 -1 0 0 11 1 -2 1 1 0 0 0 3 -4 1 2 0 -1 1 0 1 -2 0 1 0 0 0 1 10 3 -2 0 1 0 0 -1 1 0 1 0 0 -1 1 -2 1 -2 0 1 0 0 0 1 12 3 0 0 1 -2 2 -5 1 -2 -2 1 0 0 0 1 1 0 1 0 0 -1 1 -2 1 0 1 0 0 -1 0 -3 0 0 0 0 0 0 -1 -1 0z z z 第48頁/共65頁第四十九頁，共65頁。324xxx110 /4 12 3 0 0 1 -2 1 -2 0 1 0 0 1 0 1

34、0 0 -1 2 1 0 0 0 -1 321xxx113 4 1 0 0 1/3 -2/3 9 0 0 1 2/3 -4/3 1 0 1 0 0 -1 -2 0 0 0 -1/3 -1/3 b2x3x4x5xBXBC1x 2*00914* ZX，1 1 003第二階段：第二階段：C0z z 第49頁/共65頁第五十頁，共65頁。一、建模條一、建模條件件(tiojin)第50頁/共65頁第五十一頁，共65頁。二、建模步驟二、建模步驟(bzhu) 1 確定決策確定決策(juc)變量：即需要我們作出決策變量：即需要我們作出決策(juc)或選擇的量。一般情況下，題目問什么就設(shè)或選擇的量。一般情況下，

35、題目問什么就設(shè)什么為決策什么為決策(juc)變量。變量。 2 找出所有找出所有(suyu)限定條件：即決策變量限定條件：即決策變量受到的所有受到的所有(suyu)的約束；的約束； 3 寫出目標(biāo)函數(shù)：寫出目標(biāo)函數(shù)：即問題所要達(dá)到的目標(biāo)，并明確即問題所要達(dá)到的目標(biāo)，并明確是是max 還是還是 min。第51頁/共65頁第五十二頁，共65頁。三、建模案例三、建模案例(n l)三、建模案例三、建模案例(n l) C 工序工序 產(chǎn)產(chǎn)品品 A B 銷售銷售 報(bào)廢報(bào)廢 工時(shí)限工時(shí)限制制 工序工序 1 2 3 12 工序工序 2 3 4 24 單位利潤單位利潤 （百元）（百元） 4 10 3 2 注：每生產(chǎn)單

36、位產(chǎn)品注：每生產(chǎn)單位產(chǎn)品 B 可得到可得到 4 單位副產(chǎn)品單位副產(chǎn)品 C，據(jù)預(yù)測(cè)，市場(chǎng)上產(chǎn)品據(jù)預(yù)測(cè)，市場(chǎng)上產(chǎn)品 C 的最大銷量為的最大銷量為 5 單位，若單位，若產(chǎn)品產(chǎn)品 C 銷售不出去，則報(bào)廢。銷售不出去，則報(bào)廢。 解：設(shè)總利潤解：設(shè)總利潤(lrn)為為z，A、B產(chǎn)品銷量為產(chǎn)品銷量為x1、x2，產(chǎn)品，產(chǎn)品C的銷售的銷售量為量為x3，報(bào)廢量為，報(bào)廢量為x4，則：則： 2 x1 + 3x2 12 3x1 + 4x2 24 4x2 +x3 + x4 = 0 x3 5 x1、x2 、x3 、x4 0max z = 4 x1 + 10 x2 + 3 x3 2 x4 例例1 某工廠生產(chǎn)某工廠生產(chǎn)A、B兩

37、種產(chǎn)品，有關(guān)資料如下表所示：兩種產(chǎn)品，有關(guān)資料如下表所示：第52頁/共65頁第五十三頁，共65頁。船只種類船只種類船只數(shù)船只數(shù)拖拖 輪輪30A型駁船型駁船34B型駁船型駁船52航線號(hào)航線號(hào)合同貨運(yùn)量合同貨運(yùn)量12002400航線航線號(hào)號(hào)船隊(duì)船隊(duì)類型類型編隊(duì)形式編隊(duì)形式貨運(yùn)成本貨運(yùn)成本（千元隊(duì)）（千元隊(duì)）貨運(yùn)量貨運(yùn)量（千噸）（千噸）拖輪拖輪A型型駁船駁船B型型駁船駁船1112362521436202322472404142720 例例2 某航運(yùn)某航運(yùn)(hngyn)局現(xiàn)有船只種類、數(shù)量以及計(jì)劃期內(nèi)各條航線的局現(xiàn)有船只種類、數(shù)量以及計(jì)劃期內(nèi)各條航線的貨運(yùn)量、貨運(yùn)成本如下表所示：問：應(yīng)如何編隊(duì)，才能既

38、完成合同任務(wù)，又貨運(yùn)量、貨運(yùn)成本如下表所示：問：應(yīng)如何編隊(duì)，才能既完成合同任務(wù)，又使總貨運(yùn)成本為最??？使總貨運(yùn)成本為最??？第53頁/共65頁第五十四頁，共65頁。 解：設(shè)解：設(shè) xj 為第為第 j 號(hào)類型船隊(duì)號(hào)類型船隊(duì)(chun du)的隊(duì)數(shù)的隊(duì)數(shù)( j = 1,2,3,4 ), z 為總貨運(yùn)成本為總貨運(yùn)成本,則：則： min z = 36x1 + 36x2 + 72x3 + 27x4 x1 + x2 + 2x3 + x4 30 2x1 + 2x3 34 4x2 + 4x3 + 4x4 5225x1 + 20 x2 200 40 x3 + 20 x4 400 xj 0 j = 1,2,3,4

39、用單純形法可求得：用單純形法可求得：x1 = 8，x2 = 0 ，x3 = 7， x4 = 6 最最優(yōu)值：優(yōu)值：z = 954，即：四種船隊(duì)類型的隊(duì)數(shù)分別是，即：四種船隊(duì)類型的隊(duì)數(shù)分別是8、0、7、6，此時(shí)，此時(shí)(c sh)可使總貨運(yùn)成本為最小，為可使總貨運(yùn)成本為最小，為954千元。千元。第54頁/共65頁第五十五頁，共65頁。 方案方案長度長度m 2.9 2.1 1.5 合計(jì)合計(jì) 料頭料頭2017.30.11207.10.31116.50.91037.40.00306.31.10227.20.20136.60.80046.01.41x2x3x4x5x6x7x8x第55頁/共65頁第五十六頁，

40、共65頁。 方案方案長度長度m 2.9 2.1 1.5 合計(jì)合計(jì) 料頭料頭2017.30.11207.10.31116.50.91037.40.00306.31.10227.20.20136.60.80046.01.41x2x3x4x5x6x7x8x876543214 . 18 . 02 . 01 . 109 . 03 . 01 . 0minxxxxxxxxz 010043203010001230201000000287654321876543218765432187654321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx，第56頁/共65頁第五十七頁，共65頁。產(chǎn)品名稱產(chǎn)

41、品名稱規(guī)規(guī) 格格 要要 求求單價(jià)（元單價(jià)（元/kg）AC不少于不少于50%，P不超過不超過25%50BC不少于不少于25%，P不超過不超過50%35D不限不限25原材料名稱原材料名稱每天最多供應(yīng)量（每天最多供應(yīng)量（kg）單價(jià)（元單價(jià)（元/kg）CPH10010060652535第57頁/共65頁第五十八頁，共65頁。 原料原料產(chǎn)品產(chǎn)品 C P H 單單 價(jià)價(jià)ABD503525單單 價(jià)價(jià) 65 25 35)(25. 0AHAPACAPxxxx BHBPBCxxxDHDPDCxxxDHDPDCBHBPBCAHAPACxxxxxxxxxz1004001030152515max )(50. 0AHAP

42、ACACxxxx )(50. 0BHBPBCBPxxxx AHAPACxxx)(25. 0BHBPBCBCxxxx 100 DCBCACxxx100 CPBPAPxxx60 DHBHAHxxxHPCJDBAixij,0 321xxx第58頁/共65頁第五十九頁，共65頁。第59頁/共65頁第六十頁，共65頁。 年份年份項(xiàng)目項(xiàng)目123455年末年末ABCD1Ax2Ax3Ax4Ax415. 1Ax3Bx2Cx2Dx3Dx4Dx5Dx506. 1Dx1Dx106. 1Dx2315. 106. 1ADxx1215. 106. 1ADxx3415. 106. 1ADxx10325. 1Bx240. 1Cx年初年初(ninch)擁有擁有 資金資金523406. 140. 125. 115. 1maxDCBAxxx