第二線性規(guī)劃與單純形法PPT課件

1、1 1線性規(guī)化問題及其數(shù)學(xué)模型線性規(guī)化問題及其數(shù)學(xué)模型設(shè)備設(shè)備原材料原材料A A原材料原材料B B1 14 40 02 20 04 48 8 臺時臺時16 kg16 kg12 kg12 kg利潤利潤2 23 32132xxz max8221 xx1641 x1242 x021 xx ， 目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件 1.1 問題的提出問題的提出x1x2z第1頁/共65頁例例2 2：靠近某河流有兩個化工廠，流經(jīng)第一化：靠近某河流有兩個化工廠，流經(jīng)第一化工廠的河流流量為每天工廠的河流流量為每天500500萬萬m m3 3, ,在兩個化工之間在兩個化工之間有一條河流量為每天有一條河流量為每天20

2、0200萬萬m m3 3的支流的支流, ,第一化工廠第一化工廠每天排放含某種有害物質(zhì)的工業(yè)污水每天排放含某種有害物質(zhì)的工業(yè)污水2 2萬萬m m3 3, ,第二化第二化工廠排放這種工業(yè)污水工廠排放這種工業(yè)污水1.41.4萬萬m m3 3, ,從第一化工廠排從第一化工廠排出的工業(yè)污水流到第二化工廠之前，有出的工業(yè)污水流到第二化工廠之前，有20%20%可以自可以自然凈化。根據(jù)環(huán)保要求河流中工業(yè)污水的含量應(yīng)然凈化。根據(jù)環(huán)保要求河流中工業(yè)污水的含量應(yīng)不大于不大于0.2%0.2%。這兩個化工廠都需處理一部分工業(yè)。這兩個化工廠都需處理一部分工業(yè)污水。第一化工廠處理工業(yè)污水的成本為污水。第一化工廠處理工業(yè)污水

3、的成本為10001000元元/ /萬萬m m3 3, ,第二化工廠處理工業(yè)污水的成本為第二化工廠處理工業(yè)污水的成本為800800元元/ /萬萬m m3 3。問在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多。問在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使兩個化工廠處理工業(yè)污水的總成少工業(yè)污水，使兩個化工廠處理工業(yè)污水的總成本最小。本最小。第2頁/共65頁500萬萬m3200萬萬m3工廠工廠1 1工廠工廠2 22萬萬m31000元元/萬萬m31.4萬萬m3800元元/萬萬m3小于小于0.2%自然凈化自然凈化20%20%218001000 xxz min11 x6 . 18 . 021 xx4 .

4、12 x021 xx ，目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件21 x%2.050021 x%2 . 0200500)4 . 1 ()2( 8 . 021xx1x2x第3頁/共65頁特征：特征：1.1. 每一個問題都用一組決策變量每一個問題都用一組決策變量（ x1， x2， ，xn ）表示某一個方案；表示某一個方案；2.2. 存在一定的約束條件，這些約束條件可以用一存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示；組線性等式或線性不等式來表示；3.3. 都有一個要求達到的目標(biāo)，它可以用決策變量都有一個要求達到的目標(biāo)，它可以用決策變量的線性函數(shù)來表示，按問題的不同，要求目標(biāo)的線性函

5、數(shù)來表示，按問題的不同，要求目標(biāo)函數(shù)實現(xiàn)最大化或最小化。函數(shù)實現(xiàn)最大化或最小化。218001000 xxz min11 x6 . 18 . 021 xx4 . 12 x021 xx ，21 x 01241648232max21212121xxxxxxxxz，第4頁/共65頁 線性規(guī)劃問題的數(shù)學(xué)模型的一般形式為：線性規(guī)劃問題的數(shù)學(xué)模型的一般形式為： nnxcxcxcz 2211max(min)11212111)(bxaxaxann ，22222121)(bxaxaxann ，mnmnmmbxaxaxa)(2211 ，021 nxxx， 目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件 線性規(guī)劃問題解的概念線性規(guī)

6、劃問題解的概念可行解可行解： 若（若（x1，x2，xn）滿足上述約束條件，）滿足上述約束條件，則稱（則稱（x1，x2，xn）為線性規(guī)劃問題的可行解。）為線性規(guī)劃問題的可行解?？尚杏蚩尚杏颍?所有可行解組成的集合稱為可行域。所有可行解組成的集合稱為可行域。最優(yōu)解：最優(yōu)解： 使目標(biāo)函數(shù)達到最大或最小的可行解稱為使目標(biāo)函數(shù)達到最大或最小的可行解稱為最優(yōu)解。最優(yōu)解。第5頁/共65頁1.2 1.2 圖解法圖解法Z= 2Z= 6Z=10Q(4, 2)x2x10 1 2 3 4 54321Z=14X*= (4，2) Z*=14 01241648232max21212121xxxxxxxxz，第6頁/共65頁

7、 線性規(guī)劃圖解法解題步驟線性規(guī)劃圖解法解題步驟 4 4 將最優(yōu)解代入目標(biāo)函數(shù)，求出最優(yōu)目標(biāo)函數(shù)值。將最優(yōu)解代入目標(biāo)函數(shù)，求出最優(yōu)目標(biāo)函數(shù)值。 1 1 在直角平面坐標(biāo)系中畫出所有的約束等式，并在直角平面坐標(biāo)系中畫出所有的約束等式，并找出所有約束條件的公共部分，即可行域，可行域中找出所有約束條件的公共部分，即可行域，可行域中的點即為可行解。的點即為可行解。 2 2 標(biāo)出目標(biāo)函數(shù)值增加的方向。標(biāo)出目標(biāo)函數(shù)值增加的方向。 3 3 若求最大（?。┲?，則令目標(biāo)函數(shù)等值線沿若求最大（?。┲担瑒t令目標(biāo)函數(shù)等值線沿（逆）目標(biāo)函數(shù)值增加的方向平行移動，找與可行域（逆）目標(biāo)函數(shù)值增加的方向平行移動，找與可行域最后相

8、交的點，該點就是最優(yōu)解。最后相交的點，該點就是最優(yōu)解。第7頁/共65頁X2X10 1 2 3 4 54321X2X10 1 2 3 4 54321無窮多最優(yōu)解無窮多最優(yōu)解無界解無界解AB 唯一最優(yōu)解唯一最優(yōu)解 無窮多最優(yōu)解無窮多最優(yōu)解 無界解無界解 無可行解無可行解有最優(yōu)解有最優(yōu)解無最優(yōu)解無最優(yōu)解第8頁/共65頁 1.3 1.3 線性規(guī)化問題的標(biāo)準(zhǔn)型式線性規(guī)化問題的標(biāo)準(zhǔn)型式nnxcxcxcz 2211max11212111bxaxaxann 22222121bxaxaxann mnmnmmbxaxaxa 2211021 nxxx， 目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件 mnmmnnaaaaaaaa

9、aA212222111211 mbbbb21 ncccC21 nxxxX21 mjjjjaaaP21第9頁/共65頁 njxbxPCXjnjjj，210max njxmibxaxcjnjijijnjjj，21021max0max XbAXCX標(biāo)準(zhǔn)型的其它表示形式標(biāo)準(zhǔn)型的其它表示形式第10頁/共65頁 如何化標(biāo)準(zhǔn)型如何化標(biāo)準(zhǔn)型1.1. 目標(biāo)函數(shù)求最小目標(biāo)函數(shù)求最小minz = CX ?？苫癁??？苫癁椋?max (-z) = -CX。2.2. 約束條件為不等式約束條件為不等式。對于對于“”不等式不等式，在不不等式的左邊加上非負松馳變量后變?yōu)榈仁?；對等式的左邊加上非負松馳變量后變?yōu)榈仁剑粚τ谟?“”

10、不等式，在不等式的左邊減去非負剩不等式，在不等式的左邊減去非負剩余變量后變?yōu)榈仁?。余變量后變?yōu)榈仁健?.3. 變量變量 xk 無約束?？闪顭o約束?？闪?xk = xk -xk 無約束無約束，32132132132132105232732minxxxxxxxxxxxxxxxz例例： 05)(232)(7)()(32)max543321332153321433213321xxxxxxxxxxxxxxxxxxxxxxxxz，（第11頁/共65頁 1.4 線性規(guī)化問題的基可行解線性規(guī)化問題的基可行解 032274326325max4321432143214321xxxxxxxxxxxxxxxxz， 0

11、03113101221327212121，Xxxxx 051105201231327323131，Xxxxx 6110031022413227434141，Xxxxx例：例：第12頁/共65頁 003113101221327212121，Xxxxx 051105201231327323131，Xxxxx 6110031022413227434141，Xxxxx)0120(01132373243232， Xxxxx無窮多解無窮多解02142327424242 xxxx 1100021433274354343， Xxxxx1 z3 z基基*543 z第13頁/共65頁 1.4 線性規(guī)化問題的基可行

12、解線性規(guī)化問題的基可行解 基：基：設(shè)設(shè)A A是約束方程組的是約束方程組的m mn n階系數(shù)矩陣，其秩階系數(shù)矩陣，其秩為為m m，B B是矩陣是矩陣A A中中m mm m階非奇異子矩陣（階非奇異子矩陣（|B|0|B|0），），則稱則稱B B是線性規(guī)劃問題的一個基。是線性規(guī)劃問題的一個基。 基基B B的列的列P Pj j稱為稱為基向量基向量，與基向量對應(yīng)的變量，與基向量對應(yīng)的變量x xj j稱為稱為基變量基變量，否則稱為，否則稱為非基變量非基變量。 基解：基解：令非基變量為零，由約束方程令非基變量為零，由約束方程AX=bAX=b求得求得的解稱為基解。的解稱為基解。 基可行解：基可行解：滿足非負條件

13、的基解稱為基可行解。滿足非負條件的基解稱為基可行解。 可行基可行基: : 對應(yīng)于基可行解的基稱為可行基。對應(yīng)于基可行解的基稱為可行基。 注：基解的個數(shù)最多是注：基解的個數(shù)最多是CnCnm m個，基可行解的個個，基可行解的個數(shù)一般要小于基解的個數(shù)。數(shù)一般要小于基解的個數(shù)。 第14頁/共65頁1 1 可行解與最優(yōu)解：可行解與最優(yōu)解：最優(yōu)解一定是可行解，但可行解不一定是最優(yōu)解。最優(yōu)解一定是可行解，但可行解不一定是最優(yōu)解。線性規(guī)劃解之間的關(guān)系基解不一定是可行解，可行解也不一定是基解?；獠灰欢ㄊ强尚薪?，可行解也不一定是基解。2 2 可行解與基解：可行解與基解：3 3 可行解與基可行解：可行解與基可行解

14、：基可行解一定是可行解，但可行解不一定是基解?；尚薪庖欢ㄊ强尚薪?，但可行解不一定是基解?；尚薪庖欢ㄊ腔猓尚薪庖欢ㄊ腔?，但基解不一定是基可行解。但基解不一定是基可行解。4 4 基解與基可行解：基解與基可行解：5 5 最優(yōu)解與基解：最優(yōu)解與基解：最優(yōu)解不一定是基解，最優(yōu)解不一定是基解，基解也不一定是最優(yōu)解。基解也不一定是最優(yōu)解。問題：最優(yōu)解與基本可行解？問題：最優(yōu)解與基本可行解？非可行解可行解基本可行解基本解第15頁/共65頁X1X2X1X2X1X22 2 線性規(guī)化問題的幾何意義線性規(guī)化問題的幾何意義 2.1 2.1 基本概念基本概念 2. 凸組合：凸組合：3. 頂點：頂點：1.1.凸

15、集：凸集： 凸集：設(shè)凸集：設(shè)K是是n維歐氏空間維歐氏空間的一個點集，若任意兩點的一個點集，若任意兩點X(1)， X(2)K的連線上的一切點的連線上的一切點X=X(1)+(1-)X(2) K ，（，（0 1），則稱），則稱K為凸集。為凸集。 凸組合：設(shè)凸組合：設(shè)X(1) ，X(2) X(k) 是是n維歐氏空間的維歐氏空間的k個點，若存在個點，若存在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)的的凸組合。凸組合。 頂 點 ： 設(shè)頂 點 ： 設(shè) K 是 一 凸 集 ，是 一 凸

16、 集 ， XK，若，若X不能表示成不能表示成K中不同中不同兩點兩點X(1) ， X(2)的凸組合的凸組合 X=X(1)+(1-)X(2) （01）則則X稱為稱為K的頂點或極點。的頂點或極點。第16頁/共65頁 2.2 2.2 基本定理基本定理 定理定理1 1：若線性規(guī)劃問題存在可行域，則可行：若線性規(guī)劃問題存在可行域，則可行域一定是凸集。域一定是凸集。0| XbAXXD，則有則有內(nèi)的任意兩點，內(nèi)的任意兩點，是是，設(shè)設(shè),)2()1()2()1(XXDXX 0,)1()1( XbAX0,)2()2( XbAX連線上的任一點，則連線上的任一點，則，是是令令)2()1(XXX）（）（10-1X)2()

17、1( XX-1AX)2()1(XXA）（ )2()1(-1AXAX）（ bb）（ -1 b 0 X又又DX 是是凸凸集集D證：證：行域，則其可行域為行域，則其可行域為若線性規(guī)劃問題存在可若線性規(guī)劃問題存在可第17頁/共65頁 引理1 線性規(guī)劃問題的可行解X為基可行解的是充要條件是X的正分量所對應(yīng)的系數(shù)列向量是線性獨立的。 引理2 若K是有界凸集，則任何一點X K可表示為 K的頂點的凸組合。第18頁/共65頁 定理定理2 2 線性規(guī)化問題的基可行解對應(yīng)于可行域的線性規(guī)化問題的基可行解對應(yīng)于可行域的頂點。頂點。bxPmjjj 定不是可行域的頂點。定不是可行域的頂點。不是基可行解，則它一不是基可行解

18、，則它一若若X)1(02211 mmPPP ）兩式的）兩式的），（），（由（由（，設(shè)設(shè)210 證：證：個分量為正。個分量為正。的前的前行解行解不失一般性，假設(shè)基可不失一般性，假設(shè)基可mX則有則有使得使得，的數(shù)的數(shù)存在一組不全為存在一組不全為數(shù)列向量線性相關(guān)。即數(shù)列向量線性相關(guān)。即的正分量所對應(yīng)的系的正分量所對應(yīng)的系知知例例不是基可行解，則由引不是基可行解，則由引若若mXX 2101bPxPxPxmmm )()()(222111bPxPxPxmmm )()()(222111第19頁/共65頁bPxPxPxmmm )()()(222111bPxPxPxmmm )()()(22211100)()()

19、(2211)1(，mmxxxX 00)()()(2211)2(，mmxxxX 0)2()1( XX，充充分分小小時時，可可保保證證當(dāng)當(dāng) 是是可可行行解解。，即即)2()1(XX，又又知知)2()1(2121XXX 連連線線的的中中點點。是是即即)2(1),XXX。一一定定不不是是可可行行域域的的頂頂點點X第20頁/共65頁它它一一定定不不是是基基可可行行解解。不不是是可可行行域域的的頂頂點點，則則）若若（X2兩兩點點的的可可在在可可行行域域中中找找到到不不同同不不是是可可行行域域的的頂頂點點，則則若若X)()1()1(2)1(1)1(，nxxxX )()2()2(2)2(1)2(，nxxxX

20、10)1()2()1( XXX使使是基可行解，是基可行解，假設(shè)假設(shè)X線性無關(guān)。線性無關(guān)。，知知則由引例則由引例mPPP2110j)2()1( jjjxxxm時，有時，有當(dāng)當(dāng)是可行域中的兩點是可行域中的兩點，)2()1(XX mjjjmjjjbxPbxP)2()1(，0)()2()1( mjjjjxxP第21頁/共65頁是基可行解，是基可行解，假設(shè)假設(shè)X0j)2()1( jjjxxxm時，有時，有當(dāng)當(dāng)是可行域中的兩點是可行域中的兩點，)2()1(XX mjjjmjjjbxPbxP)2()1(，0)()2()1( mjjjjxxP21XX 0)()2()1(不全為不全為jjxx 線性相關(guān)。線性相關(guān)

21、。，mPPP11不是基可行解。不是基可行解。知知由引例由引例X1這和假設(shè)相矛盾。這和假設(shè)相矛盾。假設(shè)不真。假設(shè)不真。一定不是基可行解。一定不是基可行解。X線性無關(guān)。線性無關(guān)。，知知則由引例則由引例mPPP211第22頁/共65頁 定理定理 若可行域有界，線性規(guī)劃的目標(biāo)函數(shù)一定可以在其可行域的頂點上達到最若可行域有界，線性規(guī)劃的目標(biāo)函數(shù)一定可以在其可行域的頂點上達到最優(yōu)優(yōu)證：證：。函數(shù)的最優(yōu)解一定存在函數(shù)的最優(yōu)解一定存在若可行域有界，則目標(biāo)若可行域有界，則目標(biāo)是可行域的所有頂點。是可行域的所有頂點。，設(shè)設(shè))(2)(1)XXXk點達到最優(yōu)。點達到最優(yōu)。設(shè)目標(biāo)函數(shù)在設(shè)目標(biāo)函數(shù)在(0)X理理得得證證；

22、是是可可行行域域的的頂頂點點，則則定定若若(0)X點的凸組合，即點的凸組合，即可表示為頂可表示為頂知知由引理由引理不是可行域的頂點，則不是可行域的頂點，則若若)0(0)2XX kiiikiiiX10X)(0) ， kiiikiiiCXXC)()(0)CX 第23頁/共65頁 kiiikiiiCXXC)()(0)CX ，則，則，令令)(i)21|maxCXmCXki kimimikiiCXCXCX)()()(0)CX )(0)CXmCX 即即是是最最大大值值又又(0)CX)(0)CXmCX )(0)CXmCX 達達到到最最優(yōu)優(yōu)。即即目目標(biāo)標(biāo)函函數(shù)數(shù)在在頂頂點點)(mX 1. 1. 如果目標(biāo)函數(shù)在

23、多個頂點上達到最優(yōu)，則目標(biāo)函如果目標(biāo)函數(shù)在多個頂點上達到最優(yōu)，則目標(biāo)函數(shù)在這些頂點的凸組合上也達到最優(yōu)。數(shù)在這些頂點的凸組合上也達到最優(yōu)。 2. 2. 如果可行域為無界，則可能有最優(yōu)解，也可能無如果可行域為無界，則可能有最優(yōu)解，也可能無最優(yōu)解，若有最優(yōu)解，則必在某個頂點上達到最優(yōu)。最優(yōu)解，若有最優(yōu)解，則必在某個頂點上達到最優(yōu)。第24頁/共65頁 1.1.線性規(guī)劃問題的所有可行解構(gòu)成的集合可行域是凸集，也可能是無界域；線性規(guī)劃問題的所有可行解構(gòu)成的集合可行域是凸集，也可能是無界域； 2.2.可行域有有限個頂點，線性規(guī)劃問題的每個基可行解對應(yīng)于可行域的一個頂點；可行域有有限個頂點，線性規(guī)劃問題的每

24、個基可行解對應(yīng)于可行域的一個頂點； 3.3.若線性規(guī)劃問題有最優(yōu)解，必在可行域的某頂點上達到。若線性規(guī)劃問題有最優(yōu)解，必在可行域的某頂點上達到。線性規(guī)劃問題的幾何意義：線性規(guī)劃問題的幾何意義： 4.4.如果目標(biāo)函數(shù)在多個頂點上達到最優(yōu)，則如果目標(biāo)函數(shù)在多個頂點上達到最優(yōu)，則目標(biāo)函數(shù)在這些頂點的凸組合上也達到最優(yōu)目標(biāo)函數(shù)在這些頂點的凸組合上也達到最優(yōu), ,即即線性規(guī)劃問題有無群多最優(yōu)解。線性規(guī)劃問題有無群多最優(yōu)解。第25頁/共65頁3 3 單純形法單純形法 單純形法的基本思路：單純形法的基本思路： X1 CX1 X2 CX2 X3 CX3 Xn CXn*B1B2B3Bn1. 1. 初始基初始基B

25、1及所對應(yīng)基可行解及所對應(yīng)基可行解X1的確定；的確定； 2. 2. Xj 的最優(yōu)性判定；的最優(yōu)性判定； 4. 4. 求下一個頂點求下一個頂點 Xj+1 。3. 3. 基變換基變換 ；Bj Bj+1第26頁/共65頁 3.1 3.1 實例分析實例分析 例：例： 01241648232max54321524132121xxxxxxxxxxxxxxz， 2154311xxXxxxXNB， 124164825241321xxxxxxx2x換入變量換入變量5x換出變量換出變量 0121680011 zX，4/3* zxx 2132第27頁/共65頁 2154311xxXxxxXNB， 124164825

26、241321xxxxxxx2x換入變量換入變量5x換出變量換出變量 0121680011 zX，4/3* zxx 2132 5124322xxXxxxXNB， 34152 xx943251 zxx16441 xx221531 xxx 901623022 zX，24/1x換入變量換入變量3x換出變量換出變量*1 第28頁/共65頁 5124322xxXxxxXNB， 34152 xx943251 zxx16441 xx221531 xxx 901623022 zX，24/1x換入變量換入變量3x換出變量換出變量*1 5324133xxXxxxXNB， 34152 xx1341253 zxx824

27、543 xxx221531 xxx 130803233 zX，/4125x換入變量換入變量4x換出變量換出變量* 第29頁/共65頁 5324133xxXxxxXNB， 34152xx1341253 zxx824543 xxx221531 xxx 130803233 zX，/4125x換入變量換入變量4x換出變量換出變量* 4325144xxXxxxXNB， 28121432 xxx14812343 zxx4212543 xxx44141 xx 1440024*4*4 zX， 第30頁/共65頁34152xx943251zxx16441 xx221531xxx24/*1NoImage12416

28、4825241321xxxxxxx4/3* zxx2132/ 94300023410010160100422101011 000032121004016010048001214第31頁/共65頁28121432xxx14812343zxx4212543xxx44141xx34152xx1341253zxx824543xxx/412* 221531xxx 1408123002081211041212004041001 13410200341001082140022101012第32頁/共65頁Q2 (4, 2)X2X10 1 2 3 4 54321 0121680011 zX， 90162302

29、2 zX， 130803233 zX， 144002444 zX，Q1(4, 0)Q3(2, 3)Q4(0, 3)OQ4Q2Q3*第33頁/共65頁 3.2 3.2 初始可行解的確定初始可行解的確定 1.1.觀察法觀察法：通過：通過觀察確定初始可行解，例如觀察確定初始可行解，例如下列線性規(guī)劃問題：下列線性規(guī)劃問題：0max XbAXCXz0max XbXAXCXzS化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型則初始可行解為 mbbbX，21000 2.2.人造基法人造基法：每個約束條件加上一個非負人工變：每個約束條件加上一個非負人工變量后組成一個人造基。具體方法下節(jié)討論。量后組成一個人造基。具體方法下節(jié)討論。第34頁

30、/共65頁 3.3 最優(yōu)性檢驗與解的判別最優(yōu)性檢驗與解的判別 檢驗數(shù)：檢驗數(shù)：目標(biāo)函數(shù)用非基變量表達后，非基變目標(biāo)函數(shù)用非基變量表達后，非基變量的系數(shù)稱為檢驗數(shù)。量的系數(shù)稱為檢驗數(shù)。 1. 最優(yōu)解的判別定理最優(yōu)解的判別定理：若：若X(0)是線性規(guī)劃問題是線性規(guī)劃問題的一個基可行解，如果對應(yīng)的非基變量的檢驗數(shù)都的一個基可行解，如果對應(yīng)的非基變量的檢驗數(shù)都小于等于零，則小于等于零，則X(0)為最優(yōu)解。為最優(yōu)解。 2. 無窮多最優(yōu)解的判別定理無窮多最優(yōu)解的判別定理：若：若X(0)是線性規(guī)是線性規(guī)劃問題的一個基可行解，如果對應(yīng)的非基變量的檢劃問題的一個基可行解，如果對應(yīng)的非基變量的檢驗數(shù)都小于等于零，

31、又存在某個非基變量的檢驗數(shù)驗數(shù)都小于等于零，又存在某個非基變量的檢驗數(shù)等于零，則線性規(guī)劃問題有無窮多最優(yōu)解。等于零，則線性規(guī)劃問題有無窮多最優(yōu)解。 3. 無界解判別定理無界解判別定理：若：若X(0)是線性規(guī)劃問題的是線性規(guī)劃問題的一個基可行解，若存在一非基變量的檢驗數(shù)大于零，一個基可行解，若存在一非基變量的檢驗數(shù)大于零，而該非基變量的系數(shù)向量小于等于零，則該線性規(guī)而該非基變量的系數(shù)向量小于等于零，則該線性規(guī)劃問題有無界解。劃問題有無界解。第35頁/共65頁 3.4 3.4 基變換基變換 1.1.換入變量的確定：所有大于等于零的檢驗數(shù)中最大的對應(yīng)的變量為換入變量。換入變量的確定：所有大于等于零的

32、檢驗數(shù)中最大的對應(yīng)的變量為換入變量。但也可以任選。但也可以任選。 2.2.換出變量的確定：用換入變量的系數(shù)去除對應(yīng)的常數(shù)項得換出變量的確定：用換入變量的系數(shù)去除對應(yīng)的常數(shù)項得，的正分量中最小的正分量中最小的對應(yīng)的基變量為換出變量。的對應(yīng)的基變量為換出變量。 設(shè)換入變量為設(shè)換入變量為xk，換出變量為，換出變量為xl，則，則alk 稱為主元素，它所在的列稱為主元列，它所稱為主元素，它所在的列稱為主元列，它所在的行稱為主元行。在的行稱為主元行。第36頁/共65頁 3.5 迭代 利用高斯消去法或矩陣的初等變換將主元素變?yōu)?主元列的其它元素變?yōu)榱愕倪^程稱為迭代。 迭代的形式包括：約束方程組法，系數(shù)矩陣法

33、和單純表法。 011ln111111000100010001zzbaaabaaabaaankmmmnmkmmllklmnkm 011ln1111110000101010001zzabaaaabaaabaaaanmlkkmmmnmmlkmkllmlknmlkk 第37頁/共65頁4 4 單純形法的計算步驟單純形法的計算步驟 4.1 4.1 單純形表單純形表 為了便于理解計算關(guān)系，以系數(shù)矩陣法為基礎(chǔ)設(shè)計一種計算表來實現(xiàn)迭代過程。為了便于理解計算關(guān)系，以系數(shù)矩陣法為基礎(chǔ)設(shè)計一種計算表來實現(xiàn)迭代過程。這種計算表稱為單純形表。這種計算表稱為單純形表。第38頁/共65頁01zbbbml 011ln1111

34、11000100010001zzbaaabaaabaaankmmmnmkmmllklmnkm zxxxml1XBb1xlxmx1 mxkxnx ml 1zxxxmk1nmlkkmmnmmlkmknllmlknmlkkaaaaaaaaaaaa 0000101010001111111101zbbbml 第39頁/共65頁 4.2 4.2 單純形法的計算步驟單純形法的計算步驟 1. 1. 找出初始可行基，確定初始可行解，建立初始單純形表。找出初始可行基，確定初始可行解，建立初始單純形表。 2. 2. 檢驗非基變量的檢驗數(shù)檢驗非基變量的檢驗數(shù)，如果所有非基變量的檢驗數(shù)都小于等于零，則，如果所有非基變量

35、的檢驗數(shù)都小于等于零，則已得到最優(yōu)解，停止計算，否則，轉(zhuǎn)入下一步。已得到最優(yōu)解，停止計算，否則，轉(zhuǎn)入下一步。 3. 3. 確定換入變量或確定是否為無界解。確定換入變量或確定是否為無界解。 4. 4. 計算計算，確定換出變量。，確定換出變量。 5. 5. 迭代，即利用高斯消去法或矩陣初等變換，把主元素變成迭代，即利用高斯消去法或矩陣初等變換，把主元素變成1 1，主元列的其，主元列的其他元素變成他元素變成0 0。 6.6.重復(fù)重復(fù)2 26 6步。步。第40頁/共65頁 01241648232max54321524132121xxxxxxxxxxxxxxz，b2x3x4x5xBXBC1x543xxx

36、 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/4 3/4000 300302/42124/z z z 第41頁/共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

37、/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頁5 5 單純形法的進一步討論單純形法的進一步討論 5.1 5.1 人工變量法人工變量法nnxcxcxcz 2211max11212111bxaxaxann 22222121bxaxaxann mmnnmnmmbxxaxaxa 2211021 nxxx， 111212111bxxaxaxannn 222222121bxxaxaxannn mnmnmmbxaxaxa 2211 第43頁/共

38、65頁 1.大M法nnxcxcxcz 2211maxmnnnMxMxMx 21例例 0123241123max32131321321321xxxxxxxxxxxxxxz，114 x35 x365 xx1 17 x11 mmnnmnmmbxxaxaxa 2211111212111bxxaxaxannn 222222121bxxaxaxannn 021 nxxx，67MxMx第44頁/共65頁例例 0123241123max32131321321321xxxxxxxxxxxxxxz，114 x35 x365 xx1 17 x11 67MxMxb2x3x4x5xBXBC1x 6x7x1 1 00C3

39、M 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 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頁324xx

40、x110/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 -1/3 -1/3 1/3-M 2/3-Mb2x3x4x5xBXBC1x 6x7x 2*00914* ZX，z z 第46頁/共65頁2. 兩階段法第一階段：mnnnxxxz 21max第二階段：第二階段：nnxcxcxcz 2211max第一階段的最終單純

41、形表第一階段的最終單純形表mmnnmnmmbxxaxaxa 2211111212111bxxaxaxannn 222222121bxxaxaxannn 021 nxxx，第47頁/共65頁b2x3x4x5xBXBC1x 6x7x0000C01 1 764xxx364xxx324xxx1-1-001-000012/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

42、-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頁324xxx110 /4 12 3 0 0 1 -2 1 -2 0 1 0 0 1 0 1 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頁6

43、6 應(yīng)用舉例應(yīng)用舉例 一般講，一個經(jīng)濟、管理問題滿足以下條件時，才能建立線性規(guī)劃模型 1. 1. 要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù)； 2. 2. 存在著多種方案； 3. 3. 要求達到的目標(biāo)是在一定約束條件下實現(xiàn)的，這些約束條件可用線性等式或不等式來描述。一、建模條件一、建模條件第50頁/共65頁二、建模步驟二、建模步驟 1 確定決策變量：即需要我們作出決策或選擇的量。一般情況下，題目問什么就設(shè)什么為決策變量。 2 找出所有限定條件：即決策變量受到的所有的約束； 3 寫出目標(biāo)函數(shù)：即問題所要達到的目標(biāo)，并明確是max 還是 min。第51頁/共65頁三、建模案例三、建模案例

44、三、建模案例三、建模案例 C 工序工序 產(chǎn)產(chǎn)品品 A B 銷售銷售 報廢報廢 工時限工時限制制 工序工序 1 2 3 12 工序工序 2 3 4 24 單位利潤單位利潤 （百元）（百元） 4 10 3 2 注：每生產(chǎn)單位產(chǎn)品注：每生產(chǎn)單位產(chǎn)品 B 可得到可得到 4 單位副產(chǎn)品單位副產(chǎn)品 C，據(jù)預(yù)測，市場上產(chǎn)品據(jù)預(yù)測，市場上產(chǎn)品 C 的最大銷量為的最大銷量為 5 單位，若單位，若產(chǎn)品產(chǎn)品 C 銷售不出去，則報廢。銷售不出去，則報廢。 解：設(shè)總利潤為解：設(shè)總利潤為z，A、B產(chǎn)品銷量為產(chǎn)品銷量為x1、x2，產(chǎn)品產(chǎn)品C的銷售量為的銷售量為x3，報廢量為報廢量為x4，則：，則： 2 x1 + 3x2 1

45、2 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)A、B兩種產(chǎn)品，有關(guān)資料如下表所示：第52頁/共65頁船只種類船只種類船只數(shù)船只數(shù)拖拖 輪輪30A型駁船型駁船34B型駁船型駁船52航線號航線號合同貨運量合同貨運量12002400航線航線號號船隊船隊類型類型編隊形式編隊形式貨運成本貨運成本（千元隊）（千元隊）貨運量貨運量（千噸）（千噸）拖輪拖輪A型型駁船駁船B型型駁船駁船1112362521436202322472404142720 例例2 某航運局現(xiàn)有船只種

46、類、數(shù)量以及計劃期內(nèi)各某航運局現(xiàn)有船只種類、數(shù)量以及計劃期內(nèi)各條航線的貨運量、貨運成本如下表所示：條航線的貨運量、貨運成本如下表所示：問：應(yīng)如何問：應(yīng)如何編隊，才能既完成合同任務(wù)，又使總貨運成本為最??？編隊，才能既完成合同任務(wù)，又使總貨運成本為最小？第53頁/共65頁 解：設(shè)解：設(shè) xj 為第為第 j 號類型船隊的隊數(shù)號類型船隊的隊數(shù)( j = 1,2,3,4 ), z 為總貨運成本為總貨運成本,則：則： min z = 36x1 + 36x2 + 72x3 + 27x4 x1 + x2 + 2x3 + x4 30 2x1 + 2x3 34 4x2 + 4x3 + 4x4 5225x1 + 2

47、0 x2 200 40 x3 + 20 x4 400 xj 0 j = 1,2,3,4 用單純形法可求得：用單純形法可求得：x1 = 8，x2 = 0 ，x3 = 7， x4 = 6 最優(yōu)值：最優(yōu)值：z = 954，即：四種船隊類型的隊數(shù)分別是，即：四種船隊類型的隊數(shù)分別是8、0、7、6，此時可使總貨運成本為最小，為，此時可使總貨運成本為最小，為954千元。千元。第54頁/共65頁例3 合理利用線材問題現(xiàn)要做100100套鋼架，每套用長2.9m2.9m，2.1m2.1m，1.5m1.5m，的圓鋼各一根。已知原料長7.4m7.4m，問應(yīng)如何下料，使用的原材料最省？解：所有下料方案如下表： 方案方

48、案長度長度m 2.9 2.1 1.5 合計合計 料頭料頭2017.30.11207.10.31116.50.91037.40.00306.31.10227.20.20136.60.80046.01.41x2x3x4x5x6x7x8x第55頁/共65頁 方案方案長度長度m 2.9 2.1 1.5 合計合計 料頭料頭2017.30.11207.10.31116.50.91037.40.00306.31.10227.20.20136.60.80046.01.41x2x3x4x5x6x7x8x876543214 . 18 . 02 . 01 . 109 . 03 . 01 . 0minxxxxxxxx

49、z 010043203010001230201000000287654321876543218765432187654321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx，第56頁/共65頁產(chǎn)品名稱產(chǎn)品名稱規(guī)規(guī) 格格 要要 求求單價（元單價（元/kg）AC不少于不少于50%，P不超過不超過25%50BC不少于不少于25%，P不超過不超過50%35D不限不限25原材料名稱原材料名稱每天最多供應(yīng)量（每天最多供應(yīng)量（kg）單價（元單價（元/kg）CPH10010060652535 例4 配料問題。 某工廠要用三種原材料C、P、H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A、B、D。已知產(chǎn)品的規(guī)格

50、要求，產(chǎn)品單價，每天供應(yīng)的原材料數(shù)量及原材料單價如下表，該廠應(yīng)如何安排生產(chǎn)，使利潤收入為最大？第57頁/共65頁 解： 原料原料產(chǎn)品產(chǎn)品 C P H 單單 價價ABD503525單單 價價 65 25 35)(25. 0AHAPACAPxxxx BHBPBCxxxDHDPDCxxxDHDPDCBHBPBCAHAPACxxxxxxxxxz1004001030152515max )(50. 0AHAPACACxxxx )(50. 0BHBPBCBPxxxx AHAPACxxx)(25. 0BHBPBCBCxxxx 100 DCBCACxxx100 CPBPAPxxx60 DHBHAHxxxHPCJDBAixij,0 321xxx第58頁/共65頁 例5 連續(xù)投資問題。 某部門在今后5年內(nèi)給下列項目投資，已知： 項目A，從第一年到第四年初需要投資，并于次年末回收本利115%； 項目B，第三年初需要投資，到第五年末回收本利125%；但規(guī)定最大投