線性規(guī)劃單純形法運籌學學習教案

1、會計學1線性規(guī)劃線性規(guī)劃(xin xn u hu)單純形法運單純形法運籌學籌學第一頁，共53頁。3、圖解法的基本(jbn)步驟：的圖形上做出可行域、在直角坐標系Soxx211（一般(ybn)是一個凸多邊形）,2k給定的常數(shù)、令目標函數(shù)值取一個kxcxcZ2211做等值線,max3由小變大問題，令目標函數(shù)值、對k即讓等值線向上平移，點邊界線上的點均是最優(yōu)的一條邊界重合，此時若與點，則該點就是所求的最優(yōu)的一個頂點），是最后交于一個點（一般若它與可行域SSS，即得最優(yōu)解立求解，邊界線所代表的方程聯(lián)、將最優(yōu)點所在的兩條*4X*CXZX值帶入目標函數(shù)，得最優(yōu)把最優(yōu)解注意(zh y)：若是求目標函數(shù)的最小

2、值，目標函數(shù)直線向下移動第2頁/共53頁第二頁，共53頁。4、線性規(guī)劃(xin xn u hu)解的結(jié)論：1、若（LP）問題有可行(kxng)解，則可行(kxng)域是一個凸多邊形（或凸多面體）。它可能是有界的；也可能是無界的。2、若（LP）問題有最優(yōu)解，則最優(yōu)解可能是唯一的；也可能 是無窮多個(du )。如果是唯一的，這個解一定在該凸多邊形的某 個頂點上；如果是無窮多個(du )，則這些最優(yōu)解一定充滿凸多邊 形的一條邊界（包括此邊界的兩個頂點）總之，若（LP）問題有最優(yōu)解，則最優(yōu)解一定可以在凸多邊形的某個頂點達到3、若（LP）問題有可行解，但沒有有限最優(yōu)解，此時凸多邊形 是無界的（反之不成立

3、）4、若（LP）問題沒有可行解，則該問題沒有最優(yōu)解第3頁/共53頁第三頁，共53頁。定義1.3 在（LP）問題中，A的任意一個mm階 的非奇異子方陣(fn zhn)B（即|B|0）稱為 （LP）問題的一個基0,0.max)(bXbAXtsCXzLP問題對設r(A)=m0基本(jbn)可行解非退化基本可行解退化基本可行解退化基本可行解：基本可行解中，存在取0值的基變量非退化基本可行解：基本可行解中，基變量的取值均0對應的基稱為退化基對應的基稱為非退化基，即001bBX01bB線性規(guī)劃問題非退化的線性規(guī)劃問題退化的線性規(guī)劃問題：存在退化基：所有基均非退化mBxxxX21得, bAX 即對01nmN

4、xxX令m第7頁/共53頁第七頁，共53頁。0,0.max)(bXbAXtsCXzLP問題對若有可行(kxng)解，則可行(kxng)域是一個凸多邊形若（LP）問題有最優(yōu)解，則最優(yōu)解一定(ydng)可以在凸多邊形的某個頂點達到基本可行解與可行域的頂點(dngdin)的關(guān)系?第8頁/共53頁第八頁，共53頁。0,2162.7max211212121xxxxxxxtsxxz對線性規(guī)劃問題例01x2x.6221xx21x121 xx結(jié)論(jiln):1.可行(kxng)域為一個凸集2.凸集上有5個頂點(dngdin)7721 xx3.最優(yōu)解在頂點產(chǎn)生0,2162.7max54321514213212

5、1xxxxxxxxxxxxxtsxxz其標準型為100010101100121A系數(shù)矩陣基的個數(shù)35C=10基的個數(shù)=9基本可行解的個數(shù)基本解的個數(shù)=基的個數(shù)最優(yōu)解第9頁/共53頁第九頁，共53頁。0,2162.7max211212121xxxxxxxtsxxz對線性規(guī)劃問題例0,2162.7max543215142132121xxxxxxxxxxxxxtsxxz其標準型為100010101100121A系數(shù)矩陣5431PPPB 基211PPN 非基5431xxxXB基變量211xxXN非基變量0211xxXN令非基變量216543xxx，得216001X基本解基本可行解01x2x.6221x

6、x21x121 xx.凸多邊形的頂點(dngdin)最優(yōu)解第10頁/共53頁第十頁，共53頁。0,2162.7max211212121xxxxxxxtsxxz對線性規(guī)劃問題例0,2162.7max543215142132121xxxxxxxxxxxxxtsxxz其標準型為100010101100121A系數(shù)矩陣3212PPPB 基542PPN 非基3212xxxXB基變量542xxXN非基變量0542xxXN令非基變量212321xxx，得002122X基本解基本可行解01x2x.6221xx21x.121 xx第11頁/共53頁第十一頁，共53頁。0,2162.7max211212121xx

7、xxxxxtsxxz對線性規(guī)劃問題例0,2162.7max543215142132121xxxxxxxxxxxxxtsxxz其標準型為100010101100121A系數(shù)矩陣01x2x.6221xx21x.121 xx5413PPPB 基5413xxxXB基變量323PPN非基323xxXN非基變量0323xxXN令非基變量450063X得一基本解該基本(jbn)解不是基本(jbn)可行解不在可行(kxng)域中第12頁/共53頁第十二頁，共53頁。4214PPPB 基534PPN 非基4214xxxXB基變量534xxXN非基變量0534xxXN令非基變量122421xxx，得010224X

8、基本解基本可行解0,2162.7max211212121xxxxxxxtsxxz對線性規(guī)劃問題例0,2162.7max543215142132121xxxxxxxxxxxxxtsxxz其標準型為100010101100121A系數(shù)矩陣01x2x.6221xx21x.121 xx.第13頁/共53頁第十三頁，共53頁。5425PPPB 基315PPN 非基5425xxxXB基變量315xxXN非基變量0315xxXN令非基變量243542xxx，得240305X基本解基本可行解0,2162.7max211212121xxxxxxxtsxxz對線性規(guī)劃問題例0,2162.7max543215142

9、132121xxxxxxxxxxxxxtsxxz其標準型為100010101100121A系數(shù)矩陣01x2x.6221xx21x.121 xx.第14頁/共53頁第十四頁，共53頁。5316PPPB 基426PPN 非基5316xxxXB基變量426xxXN非基變量0426xxXN令非基變量151531xxx，得105016X基本解基本可行解0,2162.7max211212121xxxxxxxtsxxz對線性規(guī)劃問題例0,2162.7max543215142132121xxxxxxxxxxxxxtsxxz其標準型為100010101100121A系數(shù)矩陣01x2x.6221xx21x.121

10、 xx.第15頁/共53頁第十五頁，共53頁。0,2162.7max211212121xxxxxxxtsxxz對線性規(guī)劃問題例0,2162.7max543215142132121xxxxxxxxxxxxxtsxxz其標準型為100010101100121A系數(shù)矩陣01x2x.6221xx21x.121 xx. 基 基本解5431PPPB 216001X5413PPPB 450063X4214PPPB 010224X240305X5425PPPB 105016X5316PPPB 3212PPPB 002122X5217PPPB 3 / 2003 / 53 / 87X4318PPPB 014028

11、X208109X5329PPPB 結(jié)論(jiln):頂點(dngdin)基本(jbn)可行解第16頁/共53頁第十六頁，共53頁。總結(jié)(zngji):1.若（LP）問題有可行(kxng)解，則可行(kxng)域是一個凸多邊形2.若（LP）問題(wnt)有最優(yōu)解，則最優(yōu)解一定可以在凸多邊 形的某個頂點達到4.基本可行解的個數(shù)是有限的3.頂點與基本可行解是一一對應的若（LP）問題有最優(yōu)解，則最優(yōu)解一定可以在某個 基本可行解達到0,0.max)(bXbAXtsCXzLP 問題對找最優(yōu)解可從一個基本可行解入手，通過某種方法，調(diào)整基變量，轉(zhuǎn)到另一個基本可行解，并使目標函數(shù)值不斷增大，通過有限次的迭代就能

12、找到最優(yōu)解單純形法第17頁/共53頁第十七頁，共53頁。第18頁/共53頁第十八頁，共53頁。0.maxXbAXtsCXz對問題單純形法的基本思路：1、找出一個可行基，并得到(d do)一個基本可行解2、檢驗該基本可行解是否(sh fu)是最優(yōu)解，即目標函數(shù)值 是否(sh fu)最大，或看看是否(sh fu)存在目標函數(shù)值比它大的 基本可行解3、換一個目標(mbio)函數(shù)值比他大的基本可行解4、重復以上步驟，直至找不到更好的基本可行解第19頁/共53頁第十九頁，共53頁。0,4252323632.34max21212212121xxxxxxxxxtsxxz求解線性規(guī)劃問題例0,42520323

13、632.34max65432162152142132121xxxxxxxxxxxxxxxxxxtsxxz其標準型為第20頁/共53頁第二十頁，共53頁。100012010020001023000132A第一步：尋找第一個基本(jbn)可行解（初始基本(jbn)可行解）654321PPPPPP4)(,6543ArPPPP線性無關(guān)，且顯然，65430PPPPB 初始基6543,xxxx基變量21,xx非基變量0,42520323632.34max65432162152142132121xxxxxxxxxxxxxxxxxxtsxxz其標準型為第21頁/共53頁第二十一頁，共53頁。得基本解，令021

14、 xx4536000XX0為基本(jbn)可行解對應目標(mbio)函數(shù)值00Z是否為最優(yōu)解二、判斷0X就還沒取到最優(yōu)解量系數(shù)中有一個只要目標函數(shù)的非基變, 0ic作為基變量取由于121, 0 xcc作為入基變量則取為非基變量且入基變量：若00,0|max) 1 (ijjjixxccc三、換基迭代(di di)0,42520323632.34max65432162152142132121xxxxxxxxxxxxxxxxxxtsxxz65430PPPPB初始基6543,xxxx基變量對應的解為基本可行解盡可能的大，同時又使使既能中哪個作為非基變量，原來的基變量問題：16543xxxxx第22頁/

15、共53頁第二十二頁，共53頁。仍為非基變量2x0, 3, 023111111xabxa才能使必須由于0, 0, 034121xxa就有只需由于0, 0531xa有由于0, 2, 026414141xabxa才能使必須由于414110|minabaabiii為出基變量取第四個方程的基變量6x0,42520323632.34max65432162152142132121xxxxxxxxxxxxxxxxxxtsxxz, 201x要得到基本可行解，0,261xx時且當取做非基變量(binling)4250336261514131xxxxxxxx解為基本可行解的大，同時又使對應的盡可能變量，既能使中哪個

16、作為非基，原來的基變量問題：16543xxxxx62,xx ，非基變量5431,PPPP得新的可行基在第四個方程02x令第23頁/共53頁第二十三頁，共53頁。0,42520323632.34max65432162152142132121xxxxxxxxxxxxxxxxxxtsxxz26,xx非基變量062 xx令1X得基本可行解1543,xxxx基變量1Z目標函數(shù)值4100012501002030010236000132221000211501002030010236000132221000211501002092301027021001202212152932722.62152642632

17、xxxxxxxxxxxts0592021X82134xxzZxx2134是否為最優(yōu)解四、判斷1XZ0000348200010z8262Zxx6228xxZ還沒取到最優(yōu)解, 02c作為入基變量取2xZ000034Zxxxxx5432100034第24頁/共53頁第二十四頁，共53頁。0,42520323632.34max65432162152142132121xxxxxxxxxxxxxxxxxxtsxxz2212152932722.62152642632xxxxxxxxxxxts6228xxZ26,xx非基變量062 xx令1X得基本可行解1543,xxxx基變量0592021X不是最優(yōu)解12,

18、 0 Xc 作為入基變量取2x五、循環(huán)(xnhun)迭代出基變量(binling)的確定：為入基變量若0jx000000|minjiiijijiabaab出基變量個方程對應的基變量為則第0i1211ab12275. 25 . 392222ab5 . 2253233ab45 . 024244ab作為出基變量取3x5421,xxxx得新的基變量非基變量，即63,xx第25頁/共53頁第二十五頁，共53頁。2212152932722.62152642632xxxxxxxxxxxts6228xxZ36,xx非基變量22100021150100209301027021001208200010z22100

19、02115010020930102701210021108200010z23430041013110100211419014700121002110923002100z23434132114194712121.631653643632xxxxxxxxxxxxts6323219xxZ063 xx令非基變量2X得基本可行解92Z目標函數(shù)值1.5105.530最優(yōu)解第26頁/共53頁第二十六頁，共53頁。100012010020001023000132A654321PPPPPP0,4252323632.34max21212212121xxxxxxxxxtsxxz求解線性規(guī)劃問題0,425203236

20、32.34max65432162152142132121xxxxxxxxxxxxxxxxxxtsxxz其標準型為第一步：尋找(xnzho)初始基本可行解65430PPPPB 初始基6543,xxxx基變量21,xx非基變量，得一基本可行解令021 xx4536000X00Z是否為最優(yōu)解第二步：判斷0X不是最優(yōu)解基變量的系數(shù)標準：若目標函數(shù)中非, 0ic第三步：換基迭代(di di)確定入基變量：) 1 (作為入基變量則取0ix,0|max0jjiccc若為入基變量取1,x（2）確定(qudng)出基變量：000000|minjiiijijiabaab為入基變量若0jx出基變量個方程對應的基變量

21、為第0i第27頁/共53頁第二十七頁，共53頁。確定入基變量：) 1 (作為基變量取1x（2）確定(qudng)出基變量：為入基變量若0jx000000|minjiiijijiabaab求出基變量個方程對應的基變量為第0i三、換基迭代(di di)242426min，由在第4個方程(fngchng)為出基變量6x為非基變量，即62,xx是否為最優(yōu)解四、判斷1X0,42520323632.34max65432162152142132121xxxxxxxxxxxxxxxxxxt sxxz2212152632722.62152642632xxxxxxxxxxxts6228xxZ062 xx令0592

22、021X得基本可行解81Z目標函數(shù)值還沒取到最優(yōu)解, 02c作為入基變量取2x五、循環(huán)迭代：11211ab75. 22222ab5 . 23233ab44244ab1mini作為出基變量取3x為非基變量，即63xx第28頁/共53頁第二十八頁，共53頁。2212152632722.62152642632xxxxxxxxxxxts6228xxZ為非基變量，取63xx234341321154712121.631653643632xxxxxxxxxxxxts6323219xxZ063 xx令非基變量035 . 5015 . 12X得基本可行解92Z目標函數(shù)值是否為最優(yōu)解判斷2X, 0, 063cc由

23、于為最優(yōu)解所以2X9,2Z最優(yōu)值第29頁/共53頁第二十九頁，共53頁。單純形法的基本(jbn)思想：（1）入基變量(binling)：設ck=maxci | ci 0,取xk為入基變量(binling) 000000|minjiiijijiabaab為入基變量若0jx出基變量個方程對應的基變量為第0i得到(d do)新的非基變量目標函數(shù)表示成新非基變量的函數(shù)，4、把約束方程化為每個方程只含一個新的基變量令非基變量取零的一新的基本可行解X（2）出基變量：1、找到一個基本可行解X此時的約束方程每個方程只含一個基變量目標函數(shù)必須表示成非基變量的函數(shù)2、判斷X是否為最優(yōu)解：若目標函數(shù)中有非基變量的系

24、數(shù)ci0,則X不是最優(yōu)解。3、換基迭代第30頁/共53頁第三十頁，共53頁。0,42520323632.34max65432162152142132121xxxxxxxxxxxxxxxxxxtsxxz對X1X2X3X4X5X6常數(shù)(chngsh)項2 3 1 0 0 0 6-3 2 0 1 0 0 30 2 0 0 1 0 52 1 0 0 0 1 46543PPPP6543xxxx基變量(binling)4 3 0 0 0 0 z4536000X初始基本可行解單純形表326224主元素(yun s)b1543xxxx1 0.5 0 0 0 0.5 20 2 1 0 0 -1 20 3.5 0

25、 1 0 1.5 90 2 0 0 1 0 50 1 0 0 0 -2 z-80592022X得基本可行解12257. 25 . 395 . 22545 . 02檢驗行第31頁/共53頁第三十一頁，共53頁。b1543xxxx1 0.5 0 0 0 0.5 20 2 1 0 0 -1 20 3.5 0 1 0 1.5 90 2 0 0 1 0 50 1 0 0 0 -2 z-812257. 25 . 395 . 22545 . 02b1542xxxx0 1 0.5 0 0 -0.5 10 0 -1.75 1 0 3.25 5.5 0 0 -1 0 1 1 31 0 -0.25 0 0 0.75

26、 1.50 0 -0.5 0 0 -1.5 z-9035 . 5015 . 13X得基本可行解為最優(yōu)解. 1, 5 . 121xx原問題的最優(yōu)解為09 Z最優(yōu)值9z即9Z最優(yōu)值第32頁/共53頁第三十二頁，共53頁。0,82442.4max2121212121xxxxxxxxtsxxz求解線性規(guī)劃問題例0,82442.4max5432152142132121xxxxxxxxxxxxxxtsxxz其標準型為常數(shù)(chngsh)項 4 1 0 0 0 Z -1 1 1 0 0 21 -4 0 1 0 41 -2 0 0 1 8543xxx842001X初始基本可行解48第33頁/共53頁第三十三頁

27、，共53頁。513xxx1 -4 0 1 0 4 0 -3 1 1 0 60 2 0 -1 1 4 0 17 0 -4 0 Z-16 1 0 0 -1 2 12 0 0 1 -1/2 3/2 120 1 0 -1/2 1/2 2 0 0 0 9/2 -17/2 Z-48 213xxx無界!常數(shù)(chngsh)項 4 1 0 0 0 Z -1 1 1 0 0 21 -4 0 1 0 41 -2 0 0 1 8543xxx48第34頁/共53頁第三十四頁，共53頁。1 0 0 -1 2 12 0 0 1 -1/2 3/2 120 1 0 -1/2 1/2 2 0 0 0 9/2 -17/2 Z-4

28、8 213xxx對應(duyng)的線性規(guī)劃問題無界122321543xxx482172954zxx122541xxx22121542xxx543232112xxx542172948xxz541212xxx54221212xxx0045Mxx，令），（得解0211221212*MMMMXMz2948*其目標函數(shù)值無限增大，無限增大上時，當ZM0* X為可行解*X所以(suy)，該線性規(guī)劃問題無界第35頁/共53頁第三十五頁，共53頁。3、將約束方程化為每個方程只含一個(y )基變量 目標函數(shù)表示成非基變量的函數(shù) 單純形法步驟：1、化標準型 2、選定一個可行(kxng)基，并得一基本可行(kxn

29、g)解X？5、判斷X是否為最優(yōu)解：若目標函數(shù)(hnsh)行中所有檢驗數(shù)ci0, 則X為 最優(yōu)解。若存在某個cj0,且所有的aij 0,取xk為入基變量 （2）出基變量： kiiikikiabaab000|min出基變量個方程對應的基變量為則第0i7、對單純形表做初等行變換：把基變量對應的列化為 單位向量，目標函數(shù)的基變量系數(shù)化為零，得一新的基本可行解X。轉(zhuǎn)第4步第36頁/共53頁第三十六頁，共53頁。0,3035202102.22max5432154153152154321xxxxxxxxxxxxxxt sxxxxxz例如：對線性規(guī)劃問題432PPPB，取基03020100,，得基本X3035

30、202102541531521xxxxxxxxx由5145135123530220210 xxxxxxxxx310051010220011A系數(shù)矩陣可行(kxng)0,3035202102.8750max5432154153152151xxxxxxxxxxxxxxt sxxz典則形式(xngsh)第37頁/共53頁第三十七頁，共53頁。0,3035202102.22max5432154153152154321xxxxxxxxxxxxxxtsxxxxxz求解線性規(guī)劃問題例不是(b shi)單純形表初始(ch sh)單純形表 1 0 0 2 2 z-10 11 0 0 0 8 z+50 第38頁/

31、共53頁第三十八頁，共53頁。0,2421252.24max2121212121xxxxxxxxtsxxz求解線性規(guī)劃問題例0,2421252.24max5432152142132121xxxxxxxxxxxxxxtsxxz其標準型為典則形式(xngsh)b 4 2 0 0 0 z2 1 0 1 0 42 5 1 0 0 12-1 1 0 0 1 2543xxx 6 2b 0 0 0 -2 0 z-81 0.5 0 0.5 0 20 4 1 -1 0 80 1.5 0 0.5 1 4513xxx408021，最優(yōu)解X8Z最優(yōu)值b 0 0 0 -2 0 z-8 1 0 -0.125 0.125

32、0 1 0 1 0.25 0.25 0 2 0 0 -0.375 0.375 0 1 512xxx010212，最優(yōu)解X8Z最優(yōu)值第39頁/共53頁第三十九頁，共53頁。本題(bnt)說明：1、最優(yōu)解不唯一，但最優(yōu)值唯一無窮多個最優(yōu)解時，問題有，最優(yōu)解、當問題有兩個不同的212XX10121XXX）（取211CXCXXCZ）（*1ZZ）（*Z也是最優(yōu)解）（即211XXX多個最優(yōu)解有無窮多，所以有無窮由于3、在實際(shj)應用中，有多種方案可供選擇均為最優(yōu)解時，因為當21XX且，即有, 002121XXbAXbAX*21ZCXCX，且則0XbXXAXA)1 (21第40頁/共53頁第四十頁，共

33、53頁。單純形法的矩陣(j zhn)形式：0.maxXbAXtsCXz對問題nmmPPPPPA121mPPPB21設可行基nmPPN1非基mBxxxX21基變量nmNxxX1非基變量mBcccC21nmNccC1NBA，則NBXXXNBCCC,第41頁/共53頁第四十一頁，共53頁。0.maxXbAXtsCXz對問題mPPPB21取基nmPPN1非基mBxxxX21基變量nmNxxX1非基變量bAX 于是bXXNBNBbNXBXNBB 可逆bBNXBXNB11NBNBXXCCZ且NNBBXCXCNNNBXCNXBbBC)(11NBNBXNBCCbBC)(11mBcccC21nmNccC1NBA

34、，則NBXXXNBCCC,第42頁/共53頁第四十二頁，共53頁。0.maxXbAXtsCXz對問題mPPPB21取可行基NBNBXNBCCbBCZ)(max11bBNXBXNB110, 0NBXX關(guān)于可行(kxng)基B的典則形式對應的基本可行解：對應的目標函數(shù)值：0XObBX10bBCZB10第43頁/共53頁第四十三頁，共53頁。?1bBCBmmccc121mmB11mb=一個(y )數(shù)Z0bBCB10.maxXbAXtsCXz對問題mPPPB21可行基NBNBXNBCCbBCZ)(max110, 0NBXX:1：目標函數(shù)常數(shù)(chngsh)ObBX10基本可行解：?1NBCCBNbBN

35、XBXNB11第44頁/共53頁第四十四頁，共53頁。0.maxXbAXtsCXz對問題mPPPB21可行基NBNBXNBCCbBCZ)(max110, 0NBXX)(121mnnmmNcccCnmmPPPN21)(mnmNBCB1)(1mnQmnmmmmBNBC1)1()(11)(mnBNNBCCnmm21NBNXNBCC)(1nmm21nmmxxx21nnmmmmxxx2211jjBNNBCC)(1行向量ObBX,10基本可行解：的系數(shù)非基變量jx檢驗(jinyn)數(shù)bBNXBXNB11第45頁/共53頁第四十五頁，共53頁。：約束方程2bBNXBEXNB11,21mENB1nmPPB11

36、nmPBPB111bBNXBEXNB11m21mxxx21nmPBPB111bBxxnm11bBxPBxPBxxxnnmmmm111112211bBNXBXNB11nmmjpBxjj, 2, 1,:1的系數(shù)非基變量0.maxXbAXtsCXz對問題mPPPB21可行基NBNBXNBCCbBCZ)(max110, 0NBXXObBX,10基本可行解：bBNXBXNB11的系數(shù)：基變量ixmii,2, 1,第46頁/共53頁第四十六頁，共53頁。NBNBXNBCCbBCZ)(max110, 0NBXX設B為一個(y )可行基B的典則形式(xngsh)為：bBNXBXNB11bBNXBEXNB11bBCZXNBCCXBNBNB11)(0NBNBXNBCCbBCZ)(11BXENB1bB10NBCCBN1bBCZB1010bBX基本可行解常數(shù)項bBNXBXNB11第47頁/共53頁第四十七頁，共53頁。BXENB1bB10NBCCBN1bBCZB1常數(shù)(chngsh)項0最優(yōu)值 最優(yōu)解最優(yōu)單純形表0*1bBXbBCZB1*0第48頁/共53頁第四十八頁，共53頁。0.maxXbAXtsCXz對問題NBNBXNBCCbBCZ)(max110, 0NBXX設B為一個(y )可行基B