運籌學(xué)-1、線性規(guī)劃

1、1運籌學(xué)運籌學(xué)Operations Research2 運籌學(xué)運籌學(xué)是一門應(yīng)用科學(xué)是一門應(yīng)用科學(xué) ，它廣泛應(yīng)用現(xiàn)有的，它廣泛應(yīng)用現(xiàn)有的科學(xué)技術(shù)知識和數(shù)學(xué)方法，解決實際中提出的?？茖W(xué)技術(shù)知識和數(shù)學(xué)方法，解決實際中提出的專門問題，為決策者選擇最優(yōu)決策提供定量依據(jù)門問題，為決策者選擇最優(yōu)決策提供定量依據(jù)。 運籌學(xué)作為一門新興的學(xué)科是在第二次世界大運籌學(xué)作為一門新興的學(xué)科是在第二次世界大戰(zhàn)期間出現(xiàn)的戰(zhàn)期間出現(xiàn)的 。當時英美成立了名為當時英美成立了名為“運作研究運作研究” ( Oprtational Research)小組，通過科學(xué)方法的運用小組，通過科學(xué)方法的運用成功地解決了許多非常復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問

2、題。成功地解決了許多非常復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問題。3 例如如何合理運用雷達有效地對付德國空襲；例如如何合理運用雷達有效地對付德國空襲；對商船隊如何進行編隊護航，在船隊遭受德國潛艇對商船隊如何進行編隊護航，在船隊遭受德國潛艇攻擊時使船隊損失最少；反潛深水炸彈在各種情況攻擊時使船隊損失最少；反潛深水炸彈在各種情況下如何調(diào)整其爆炸深度，才能增加對德國潛艇的殺下如何調(diào)整其爆炸深度，才能增加對德國潛艇的殺傷力等傷力等 ；軍隊營養(yǎng)物質(zhì)供應(yīng)問題。；軍隊營養(yǎng)物質(zhì)供應(yīng)問題。 運籌學(xué)課程的一般內(nèi)容有：運籌學(xué)課程的一般內(nèi)容有：線性規(guī)劃、整數(shù)規(guī)線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃、圖與網(wǎng)絡(luò)分析、排隊劃、非線性規(guī)劃、動

3、態(tài)規(guī)劃、圖與網(wǎng)絡(luò)分析、排隊論、對策論、存貯論、決策論等。論、對策論、存貯論、決策論等。4線性規(guī)劃線性規(guī)劃56 例例1: :( (生產(chǎn)計劃問題生產(chǎn)計劃問題) )某工廠生產(chǎn)某工廠生產(chǎn) I I、IIII 兩種產(chǎn)兩種產(chǎn)品品。每件產(chǎn)品的單位利潤，所消耗的兩種材料數(shù)、每件產(chǎn)品的單位利潤，所消耗的兩種材料數(shù)、設(shè)備工時及這兩種材料、設(shè)備工時的限額如下表：設(shè)備工時及這兩種材料、設(shè)備工時的限額如下表： I IIIII資源限量資源限量 設(shè)備設(shè)備材料材料A A材料材料B B1402048臺時臺時16kg12kg 利潤利潤23712121212max2328416.412,0Zxxxxxstxx x解：解：設(shè)設(shè) x1、

4、x2分別表示兩種產(chǎn)品的產(chǎn)量，那么該問分別表示兩種產(chǎn)品的產(chǎn)量，那么該問題的數(shù)學(xué)模型可以表示為：題的數(shù)學(xué)模型可以表示為：8第第i 種資源的擁有量為種資源的擁有量為bi ;i=1,2,m ,生產(chǎn)一個單位第生產(chǎn)一個單位第j種產(chǎn)品需要消耗第種產(chǎn)品需要消耗第i 種資源的數(shù)量為種資源的數(shù)量為aij;第第j種產(chǎn)品的利潤（單價種產(chǎn)品的利潤（單價,產(chǎn)值）為產(chǎn)值）為cj 。j =1,2,n。上述問題推廣到一般情況：上述問題推廣到一般情況：有有m種不同資源（例如原材料，動力資源，資金，勞力種不同資源（例如原材料，動力資源，資金，勞力等）可以用來生產(chǎn)等）可以用來生產(chǎn)n種不同產(chǎn)品。假設(shè)有關(guān)的數(shù)據(jù)為：種不同產(chǎn)品。假設(shè)有關(guān)的

5、數(shù)據(jù)為：設(shè)設(shè)x1、x2、xn 分別表示分別表示n種產(chǎn)品的產(chǎn)量，則其數(shù)種產(chǎn)品的產(chǎn)量，則其數(shù)學(xué)模型為：學(xué)模型為：91 12211 11221121 1222221 12212max.,0nnnnnnmmmnnmnZc xc xc xa xa xa xba xa xa xbsta xaxaxbx xx10 例例2： (配料問題配料問題) 一飼養(yǎng)場飼養(yǎng)動物出售，每只一飼養(yǎng)場飼養(yǎng)動物出售，每只動物每天至少需要動物每天至少需要700克蛋白質(zhì)克蛋白質(zhì)， 30克礦物質(zhì)，克礦物質(zhì)，100毫克維生素?，F(xiàn)有四種飼料可供選用，各種飼料每公毫克維生素?，F(xiàn)有四種飼料可供選用，各種飼料每公斤營養(yǎng)成分含量及單價如下表所示；斤

6、營養(yǎng)成分含量及單價如下表所示； 飼料飼料營養(yǎng)成分營養(yǎng)成分 需要量需要量蛋白質(zhì)蛋白質(zhì)3 2 1 5700克克礦物質(zhì)礦物質(zhì)1 0.5 0.2 230克克維生素維生素0.5 1 0.3 2.5100毫克毫克單價單價(元元/公公斤斤)0.8 1.2 0.6 2 四種飼料各采購多少，才能使總費用最?。克姆N飼料各采購多少，才能使總費用最??？11 解：解：設(shè)設(shè) x1、x2、 x3、 x4分別表示四種飼料的采分別表示四種飼料的采購量，那么該問題的數(shù)學(xué)模型可以表示為：購量，那么該問題的數(shù)學(xué)模型可以表示為：12341234123412341234min0.81.20.623257000.50.2230.0.50.

7、32.5100,0Zxxxxxxxxxxxxstxxxxx x x x12上述模型推廣到一般情況為：上述模型推廣到一般情況為：每只動物每天至少需要每只動物每天至少需要有有m種不同種不同營養(yǎng)成分營養(yǎng)成分bi；有有n種飼料可供選用，每公斤種飼料可供選用，每公斤第第j種種飼料所含飼料所含第第i種種營營養(yǎng)成分量為養(yǎng)成分量為aij;第第j種種飼料的單價飼料的單價為為cj 。i=1,2,m， j=1,2,n。設(shè)設(shè)x1、x2、xn 分別表示分別表示n種種飼料飼料的采購量，則其的采購量，則其數(shù)學(xué)模型為：數(shù)學(xué)模型為：如何采購才能使總費用最小？如何采購才能使總費用最?。?31 12211 11221121 122

8、2221 12212min.,0nnnnnnmmmnnmnZc xc xc xa xa xa xba xa xa xbsta xaxaxbx xx14 例例3：（運輸問題）運輸問題）設(shè)有兩個磚廠設(shè)有兩個磚廠A1 、A2 ，產(chǎn)，產(chǎn)量分別為量分別為23萬塊、萬塊、27萬塊，現(xiàn)將其產(chǎn)品聯(lián)合供應(yīng)三萬塊，現(xiàn)將其產(chǎn)品聯(lián)合供應(yīng)三個施工現(xiàn)場個施工現(xiàn)場B1 、 B2 、 B3 ，其需要量分別為，其需要量分別為17萬萬塊、塊、18萬塊、萬塊、15萬塊。各產(chǎn)地到各施工現(xiàn)場的單位萬塊。各產(chǎn)地到各施工現(xiàn)場的單位運價如下表：運價如下表：問如何調(diào)運才能使總運費最省？問如何調(diào)運才能使總運費最??？ 現(xiàn)場現(xiàn)場磚廠磚廠 B1 B2

9、 B3A15147A2618915解：解：設(shè)設(shè)xijij表示從磚廠表示從磚廠A Ai運往現(xiàn)場運往現(xiàn)場B Bj j的數(shù)量的數(shù)量 ( (i=1=1，2;j=1,22;j=1,2，3),3),則其數(shù)學(xué)模型如下：則其數(shù)學(xué)模型如下：111213212223111213212223112112221323min51476189232717.18150(1,2,1,2,3)ijZxxxxxxxxxxxxxxstxxxxxij1617 1 12211 11221121 1222221 12212max(min).( , ).( , ).( , ),.,0nnnnnnmmmnnmnZc xc xc xa xa

10、xa xba xa xa xba xaxaxbx xx 18 例例4： （投資問題（投資問題 ） 某投資公司在第一年初有某投資公司在第一年初有100萬元資金，每年都有如下的投資方案可供考慮采萬元資金，每年都有如下的投資方案可供考慮采納：納：“假使第一年投入一筆資金，第二年又繼續(xù)投入假使第一年投入一筆資金，第二年又繼續(xù)投入此資金的此資金的50%，那么到第三年就可回收第一年投入資，那么到第三年就可回收第一年投入資金的兩倍金額金的兩倍金額” 。投資公司要設(shè)法決定最優(yōu)的投資策。投資公司要設(shè)法決定最優(yōu)的投資策略使第六年所掌握的資金最多。略使第六年所掌握的資金最多。解：解：設(shè)設(shè)x1為第一年的投資為第一年的

11、投資; x2為為 第一年的保留資金；第一年的保留資金；100 ：21 xx則設(shè)設(shè)x3為第二年新的投資；為第二年新的投資； x4為第二年的保留資金；為第二年的保留資金；2431)2( ：xxxx則19設(shè)x5為第三年新的投資；為第三年新的投資；x6為第三年的保留資金；為第三年的保留資金；146532)2( ：xxxxx則368752)2( ：xxxxx則設(shè)設(shè)x7為第四年新的投資；第四年的保留資金為為第四年新的投資；第四年的保留資金為x8；設(shè)設(shè)x9為第五年的保留資金：第五年不再進行新的投資，因為第五年的保留資金：第五年不再進行新的投資，因為這筆投資要到第七年才能回收。為這筆投資要到第七年才能回收。

12、589722 ：xxxx則約束條件保證每年滿足如下的關(guān)系：追加投資金約束條件保證每年滿足如下的關(guān)系：追加投資金額額+新投資金額新投資金額+保留資金保留資金=可利用的資金總額?？衫玫馁Y金總額。20到第六年實有資金總額為到第六年實有資金總額為x9+2x7，整理后得到，整理后得到下列線性規(guī)劃模型：下列線性規(guī)劃模型：7912123413456356785789m ax2100222042220.4222042200,1, 2,9jZxxxxxxxxxxxxxs txxxxxxxxxxj21 例例5：（下料問題）下料問題） 某一機床需要用甲、乙、某一機床需要用甲、乙、丙三種規(guī)格的鋼軸各一根，這些軸的規(guī)

13、格分別是丙三種規(guī)格的鋼軸各一根，這些軸的規(guī)格分別是2.9,2.1, 1.5(m),這些鋼軸需要用同一種圓鋼來做，圓這些鋼軸需要用同一種圓鋼來做，圓鋼長度為鋼長度為7.4m?，F(xiàn)在要制造?，F(xiàn)在要制造100臺機床，最少要用多臺機床，最少要用多少根圓鋼來生產(chǎn)這些鋼軸？少根圓鋼來生產(chǎn)這些鋼軸？ 解：解：第一步：設(shè)一根圓鋼切割成甲、乙、丙三第一步：設(shè)一根圓鋼切割成甲、乙、丙三種鋼軸的根數(shù)分別為種鋼軸的根數(shù)分別為y1,y2,y3，則切割方式可用不等，則切割方式可用不等式式2.9y1+2.1y2+1.5y37.4 表示，求這個不等式的有實表示，求這個不等式的有實際意義的非負整數(shù)解共有際意義的非負整數(shù)解共有8組

14、，也就是有組，也就是有8種不同的種不同的下料方式，如下表所示：下料方式，如下表所示：22 方案方案規(guī)格規(guī)格12345678y1(2.9m)21110000y2(2.1m)02103210y3(1.5m)10130234余料余料0.10.30.901.10.20.81.4設(shè)設(shè)x1、x2、x8 表示按表示按8 8種方案下料的圓種方案下料的圓鋼鋼根數(shù)，根數(shù)，則問題的數(shù)學(xué)模型為：則問題的數(shù)學(xué)模型為： 2387654321minxxxxxxxxZ1234235671346782100232100323410001 28.,jxxxxxxxxxs txxxxxxxj，24251 12211 1122112

15、1 1222221 12212max(min).( , ).( , ).( , ),.,0nnnnnnmmmnnmnZc xc xc xa xa xa xba xa xa xba xaxaxbx xx 262711221111221121122222112212max .,.,0 nnnnnnmmmnnmnZc xc xc xa xaxaxbaxaxaxbs taxaxaxbxxx目標函目標函數(shù)最大數(shù)最大約束條約束條件等式件等式?jīng)Q策變決策變量非負量非負28 11max 1,2,.0 1,2,.,njjjnijjijjZc xa xbims txjn291max.0 1,2,.njjjjZCXP

16、 xbstxjn111222jjjnmmjaxbaxbX P b .xba其中：其中：12nC(c ,c ,.c )30C價值向量價值向量b資源向量資源向量X決策變量向量決策變量向量A資源消耗系數(shù)矩陣資源消耗系數(shù)矩陣11121212221212 ( ,.,)nnnmmmnaaaaaaAP PPaaamaxs.t 0ZCXAXbX311) 若目標函數(shù)為：若目標函數(shù)為：minZ=CX，則令，則令Z= - -Z ,于是得于是得到到max Z= - -CX 2) 若若約束條件約束條件為：為：1 122,kkknnka xa xa xb引進松弛變量引進松弛變量xn+1 , 使：使：1 1221kkknn

17、nka xa xa xxb顯然：顯然：11 1220.nkkkknnxba xa xa x32若若約束條件約束條件為：為：1 122,kkknnka xa xa xb引進松弛變量引進松弛變量xn+1 , 使：使：1 1221kkknnnka xa xa xxb顯然：顯然：11 1220nkkknnkxa xa xa xb若若xk無無非負約束非負約束 ，則令：，則令：/,0,0kkkkkxxxxx33123123123123123min3283325,0Zxxxxxxxxxxxxx xx 、 無約束例例1：將下列線性規(guī)劃化為標準形將下列線性規(guī)劃化為標準形解：解：標準形為：標準形為：1233123

18、34123351233123345max3328332()50Zxxxxxxxxxxxxxxxxxxxxxxxx、 、 、 、 、34可行解可行解：滿足：滿足AX=b, XAX=b, X0 0的解的解X X稱為線性稱為線性規(guī)劃問題的規(guī)劃問題的可行解可行解?？尚杏蚩尚杏颍嚎尚薪獾娜w稱為：可行解的全體稱為可行域可行域。最優(yōu)解最優(yōu)解：使：使Z=CXZ=CX達到最大值的可行解稱達到最大值的可行解稱為為最優(yōu)解最優(yōu)解。 max . 0ZCXAXbstX標準型標準型35標準形的假定標準形的假定( ),0,010.irank Ammnbbi(1)矩陣A的秩(2).若有可對第 個約束方程兩邊同時乘以.36基基

19、：若若B是矩陣是矩陣A中中mm階非奇異子矩陣，則稱階非奇異子矩陣，則稱B是線性規(guī)劃問題的一個是線性規(guī)劃問題的一個基基。不妨設(shè)：。不妨設(shè)：11121212221212 ( ) mmmmmmmaaaaaaBP PPaaa,1,2,jP jm,1,2,jxjm,1,2,jxjmmn 基向量 基變量 非基變量37,( ,),(,),BBNNXAB N CC CXX此時max.0ZCXAXbstXmax(,)( ,).,0BBNNBNBNXZCCXXB NbXstXX38max.,0BBNNBNBNZC XC XBXNXbstXX兩邊同時左乘兩邊同時左乘B-1-1得到：得到： 11BNXB bB NX1

20、120,( ,)TNBmXXB bb bb令則 約束方程化為：約束方程化為：BNBXbNX12( ,0,0,0)TmXb bb于是得解：于是得解：39基本解基本解：上面求出的：上面求出的X稱為對應(yīng)基稱為對應(yīng)基B下的下的基本解基本解基本可行解基本可行解：非負的基解：非負的基解X X稱為稱為基本可行解基本可行解可行基可行基：對應(yīng)基可行解的基稱為：對應(yīng)基可行解的基稱為可行基可行基基本最優(yōu)解基本最優(yōu)解：最優(yōu)的基可行解稱為：最優(yōu)的基可行解稱為基本最優(yōu)解基本最優(yōu)解最優(yōu)基最優(yōu)基：對應(yīng)基本最優(yōu)解的基稱為：對應(yīng)基本最優(yōu)解的基稱為最優(yōu)基最優(yōu)基4012345123142512345max230002 84 16.

21、4 12,0Zxxxxxxxxxxstxxx x x x x例例7: 解：解：系數(shù)矩陣為：系數(shù)矩陣為：1 0 0 4 00 1 0 0 40 0 1 2 1),.,(521PPPA41易知：易知：都是基。都是基。72458345(,),(,)BP P PBP P P112321243125( ,),( ,),( ,),BP P PBP P PBP P P413551456234( ,),( ,),(,),BP P PBP P PBP P P相應(yīng)基本解及目標函數(shù)值為：相應(yīng)基本解及目標函數(shù)值為：913410235( ,),(,)BP P PBP P P不是基。不是基。42 可以看到可以看到B2、B

22、3、B4、B6、B7、B8是是可行基，可行基， B3是最是最優(yōu)基優(yōu)基, B1、B5不是不是可行基?？尚谢?。 基基x1x2x3x4x5ZB14 43 3-2-20 00 01717B22 23 30 08 80 01313B34 42 20 00 04 41414B44 40 04 40 012128 8B58 80 00 0-16-1612123232B60 03 32 216160 09 9B70 04 40 016165 51212B80 00 08 8161612120 043 線性規(guī)劃解的關(guān)系圖線性規(guī)劃解的關(guān)系圖可行解可行解 基可行解基可行解 基本最優(yōu)解基本最優(yōu)解4412121212m

23、ax2328416.412,0Zxxxxxstxx x例例2:2:454 3 2 1 0 x2| | | | |12 3 45x1x1 + 2x2 84x1 164 x2 122x1 + 3x2 5等值線等值線可行域可行域(4,2)CABD最優(yōu)解最優(yōu)解X=(4,2)T最優(yōu)值最優(yōu)值Z=14Z= 2x1 + 3x2 x1 + 2x2 84x1 164x2 12(1,1)46(2,3)4 3 2 1 0 x2| | | | |12 3 45x1CABD最優(yōu)解最優(yōu)解X(1)=(4,2)TX(2)=(2,3)T最優(yōu)值最優(yōu)值Z=16(4,2)當當=0.5時時X =0.5(4,2)T+0.5(2,3)T=(

24、3, 2.5)T 12121212max2428416.412,0Zxxxxxs txx x有無窮多個最優(yōu)解即具有多重解,通解為X=X(1)+(1-) X(2) 01例例3:47246x1x2246最優(yōu)解最優(yōu)解X=(3,1)T最優(yōu)值最優(yōu)值Z=5(3,1)例例4:1212121212min2364.3600Zxxxxxxstxxxx、48246x1x2246無界解無界解(無最優(yōu)解無最優(yōu)解)例例5:1212121212max2364.3600Zxxxxxxstxxxx、49x1x2O10203040102030405050無可行解無可行解即無最優(yōu)解即無最優(yōu)解例例6:1212121212max342

25、401.530.500,0Zxxxxxxstxxxx5051由以上例題可知，由以上例題可知，線性規(guī)劃的解有線性規(guī)劃的解有4種形式種形式：2.有無窮多最優(yōu)解有無窮多最優(yōu)解3.有無界解有無界解4.無可行解無可行解1、2情形為有最優(yōu)解情形為有最優(yōu)解3、4情形為無最優(yōu)解情形為無最優(yōu)解1.有唯一最優(yōu)解有唯一最優(yōu)解52 凸集凸集：設(shè)設(shè)K是是n維歐氏空間維歐氏空間En的一個點集。若任的一個點集。若任意兩點意兩點X(1)、X(2)K的連線上的一切點的連線上的一切點X(1)+(1- -)X(2)K，01 ，則稱，則稱K為為凸集凸集。 53 凸組合凸組合： 設(shè)設(shè)X(1)、 X(2)、 、X(k)是是n n維歐氏空

26、間維歐氏空間En的的k k個點，若存在個點，若存在1、 2、 、k ,且且0 i 1, 1+ 2+ +k =1，使得：，使得：X=1X(1) + 2X(2) + +k X(k)則稱則稱X是是X(1)、 X(2)、 、X(k)的的凸組合凸組合。 頂點頂點： 設(shè)設(shè)K是凸集，是凸集，XK；若；若X不能用不能用K中中不同的兩點不同的兩點X(1)、 X(2)的的線性組合表示為：線性組合表示為：則則X 稱為稱為K的一個的一個頂點頂點(或或極點極點)。X=X(1)+(1- -)X(2)， 0 1 。 X54定理定理1 1：若：若LPLP問題存在可行解，則其可行域問題存在可行解，則其可行域1,0njjjjDX

27、p xb x證證: 設(shè)設(shè)(1)(1)(1)(1)12,TnXxxx(2)(2)(2)(2)12,TnXxxx是是D內(nèi)的任意兩點，且內(nèi)的任意兩點，且X(1) X(2)。 是凸集。是凸集。55則有則有 ：(1)(1)1,0,1,2,njjjjp xb xjn(2)(2)1,0,1,2,njjjjp xb xjn令令X=(x1, x2, ，xn)T為為X(1)、 X(2)連線上的任連線上的任意一點，即：意一點，即：X=X(1)+(1- -)X(2)， 0 1 。 X的分量是的分量是xj=xj(1)+(1-1-) xj(2) ，將它代入約束條件，得到將它代入約束條件，得到56(1)(2)111nnjj

28、jjjjp xp x1bbb(1)(2)11(1)nnjjjjjjjp xpxx又因又因 xj(1)、xj(2) 0，0，1- -0，所以所以xj 0 ，j=1、2 、 、n 。于是于是X為可行解，即為可行解，即D是凸集。是凸集。57 定理定理：如果如果LP問題存在可行解問題存在可行解，則則一定存一定存在在基可行解基可行解。 若若1, 2, ，k線性相關(guān)，即存在一組不全線性相關(guān)，即存在一組不全為零的數(shù)為零的數(shù)i ,i=1、2 、 、k （其中至少有一個正（其中至少有一個正數(shù)）數(shù)）, 使得使得:證證:設(shè)設(shè)X=(x1 , x2 , , xk , 0 , , 0)T為為可行解可行解，若，若向量向量1

29、, 2, ，k線性無關(guān)，則線性無關(guān)，則X就是一個就是一個基可基可行解。否則，可通過下列步驟一個構(gòu)造出一個基行解。否則，可通過下列步驟一個構(gòu)造出一個基可行解可行解。 由下式定義一個新的點，令由下式定義一個新的點，令1 1220kkPPPX58其中其中于是有于是有,1,2,0,1,jjjjxxjkxjkn min|0jsjjsxx0,1,2,jjjxxjk 特別地特別地：0sssxx 將代入約束條件將代入約束條件X1110nknjjjjjjjjj kAXP xPxP 59110kkjjjjjjP xPbb 由此可見是一個可行解，但的正分由此可見是一個可行解，但的正分量比的量比的正分量少一個。若的正

30、分量所對應(yīng)正分量少一個。若的正分量所對應(yīng)的系數(shù)列向量是線性無關(guān)的，則就是一個基的系數(shù)列向量是線性無關(guān)的，則就是一個基可行解，如若不然，繼續(xù)以上步驟直到得到一個可行解，如若不然，繼續(xù)以上步驟直到得到一個基可行解?；尚薪?。 XXXX60定理定理3：LP問題的可行解問題的可行解X=(x1 , x2 , , xn)T為基為基可行解的充要條件是可行解的充要條件是X的正分量所對應(yīng)的系數(shù)列的正分量所對應(yīng)的系數(shù)列向量是線性無關(guān)的。向量是線性無關(guān)的。 證證: 1) 1)必要性：由基可行解的定義可知。必要性：由基可行解的定義可知。 2）充分性充分性：設(shè)可行解：設(shè)可行解X的的正分量正分量x1,x2,xk所對所對應(yīng)

31、的列應(yīng)的列向量向量p1, p2, ,pk線性無關(guān)，則必有線性無關(guān)，則必有km；當；當k=m時，它們恰好構(gòu)成一個基，從而時，它們恰好構(gòu)成一個基，從而X=(x1,x2, ,xk , 0, ,0)T為相應(yīng)的基可行解。為相應(yīng)的基可行解。 當當km時，則一定可以從其余的列向量中取出時，則一定可以從其余的列向量中取出m-k個列向量與個列向量與p1, p2, ,pk構(gòu)成最大的線性無關(guān)向量組構(gòu)成最大的線性無關(guān)向量組,其對應(yīng)的基解恰為其對應(yīng)的基解恰為X，由定義可知它是基可行解。，由定義可知它是基可行解。61定理定理4 4：線性規(guī)劃問題的線性規(guī)劃問題的基可行解基可行解對應(yīng)于可行域?qū)?yīng)于可行域的的頂點頂點。 證：證

32、： 不失一般性，假設(shè)可行解不失一般性，假設(shè)可行解X的前的前k個分量為正個分量為正。1(1)kjjjP xb現(xiàn)在分兩步來證明，分別用反證法。現(xiàn)在分兩步來證明，分別用反證法。 1)若若X不是基可行解，則它一定不是可行域的頂點。不是基可行解，則它一定不是可行域的頂點。根據(jù)根據(jù)定理定理2，若，若X不是基可行解，則其正分量所對應(yīng)的不是基可行解，則其正分量所對應(yīng)的列向量列向量p1, p2, ，pk線性相關(guān)，即存在一組不全為零線性相關(guān)，即存在一組不全為零的數(shù)的數(shù)i ,i=1、2 、 、k , 使得使得: :故故62用一個用一個0的數(shù)乘式的數(shù)乘式(2)式再分別與式再分別與(1)式相加式相加和相減，這就得到和相

33、減，這就得到現(xiàn)取現(xiàn)取11220(2)kkPPP111222()()()kkkxPxPxPb111222()()()kkkxPxPxPb(1)1122(),(),(),0,0TkkXxxx(2)1122(),(),(),0,0TkkXxxx由由X(1)、 X(2)可以得到：可以得到：(1)(2)1122XXX即表示即表示X是是X(1)、 X(2)連線的中點。連線的中點。63另一方面，當另一方面，當 充分小時，可保證充分小時，可保證 即即X(1)、 X(2)是可行解。是可行解。 這就證明了這就證明了X不是可行域不是可行域D的頂點。的頂點。(1)(1)(1)(1)12(,)TnXxxx(2)(2)(

34、2)(2)12(,)TnXxxx2) 2) 若若X不是可行域不是可行域D的頂點，的頂點，則它一定不是基則它一定不是基可行解：可行解：0 ,1,2,iixik 因為因為X不是可行域不是可行域D D的頂點，則在可行域的頂點，則在可行域D D中可找到不同的兩個點中可找到不同的兩個點X(1) X(2) ：使得使得 X=X(1)+(1- -)X(2)， 0 0 時，時， Z02x13x2只要取只要取x1 100或或x2 20 0 , Z Z 的值可能增大。的值可能增大。 2376第第4 4步步 基變換基變換換入變量 （即選最大檢驗數(shù)對應(yīng)的變量）一般選取一般選取 對應(yīng)的變量12(,)max12,xx12,

35、0,均可均可換入。2x77 換出變量換出變量使換入的變量越大越好使換入的變量越大越好同時，新的解要可行。同時，新的解要可行。選非負選非負的最小者對應(yīng)的變量換出的最小者對應(yīng)的變量換出312415282164 12 4 xxxxxxx2x為換入變量，應(yīng)換出為換入變量，應(yīng)換出 ？ 變量。變量。為換出變量變量：為換入變量，確定換出522542323)4/12,2/8min( 04 12 0 16 02 8 xxxxxxxx思考：思考： 當當a/k2k20 0 時會怎時會怎樣？樣？5min(8/2, ,12/4)3x為換出變量78 轉(zhuǎn)第轉(zhuǎn)第2步：基變量用非基變量表示。步：基變量用非基變量表示。 第第3步

36、：最優(yōu)性判斷步：最優(yōu)性判斷 檢驗數(shù)檢驗數(shù) 存在正，按第存在正，按第4步換基繼續(xù)迭代步換基繼續(xù)迭代 均非正，停止均非正，停止 （這時的解即是最優(yōu)解）（這時的解即是最優(yōu)解）2x為換入變量，應(yīng)換出為換入變量，應(yīng)換出 變量。變量。為換出變量變量：為換入變量，確定換出522542323)4/12,2/8min( 04 12 0 16 02 8 xxxxxxxx1342()BPPP因此，基由因此，基由 0345()BPPP變?yōu)樽優(yōu)?9轉(zhuǎn)轉(zhuǎn) 第第2步步進基315412512 2164 1 3 4xxxxxxx153 924Zxx代入目標函數(shù)15342(1)0,2,16,3(0,3,2,16,0)Txxxxx

37、X令：則得一基可行解312415282164 12 4 xxxxxxxZ02x13x2803154125122164 1 3 4xxxxxxxmin(2 1,16 4, )2 13,xx故 進基出基因此，基由因此，基由 l確定換出變量確定換出變量1342()BPPP2142()BPPP變?yōu)樽優(yōu)?11352435125428423xxxxxxxx135142(2)0,2,8,3(2,3,0,8,0)TxxxxxX令：則得一基可行解進基進基153154125392412 2164 1 3 4Zxxxxxxxxx351 1324Zxx代入目標函數(shù)基變量用非基變量表示為：基變量用非基變量表示為：821

38、48min( ,3)4254,xx故 進基出基1352435125428423xxxxxxxx1l確定換出變量確定換出變量因此，基由因此，基由 2142()BPPP3152()BPPP變?yōu)樽優(yōu)?31441534211234284422xxxxxxxx134152(3)0,4,4,2(4,2,0,0,4)TxxxxxX令：得一基可行解0最優(yōu)解最優(yōu)解14Z 最優(yōu)值1352435125428423xxxxxxxx13431 1428Zxx代入目標函數(shù)3511324Zxx基變量用非基變量表示為：基變量用非基變量表示為：84下面我們用矩陣的初等變換來表示上述求解過程。下面我們用矩陣的初等變換來表示上述求

39、解過程。 12345 b 812100164001001200014230000PPP P PbAC12345121434 b 2010164001030100900120PPPPP12345121144 b 2101080041301001300220PPPPP12345141211283128 b 4100040021201014000PPPPP85 x2x1(1)(0,3,2,16,0)TX 結(jié)合圖形法分析(單純形法的幾何意義)(0) (0,0,8,16,12) TXA(0,3)B(2,3)C(4,2)O(0,0)( 0 )( 0 , 0 , 3 ,1 6 ,1 2 )X(2)(2,3,

40、0,8,0)TX(3)(4,2,0,0,4)TX86 為書寫規(guī)范和便于計算，對單純形法為書寫規(guī)范和便于計算，對單純形法的計算設(shè)計了單純形表。每一次迭代對應(yīng)的計算設(shè)計了單純形表。每一次迭代對應(yīng)一張單純形表，含初始基可行解的單純形一張單純形表，含初始基可行解的單純形表稱為初始單純形表，含最優(yōu)解的單純形表稱為初始單純形表，含最優(yōu)解的單純形表稱為最終單純形表。下面介紹用單純形表稱為最終單純形表。下面介紹用單純形表計算線性規(guī)劃問題的原理。表計算線性規(guī)劃問題的原理。87 設(shè)設(shè) 是一個可行基，是一個可行基，12( )mBP PP1 12211 11221121 1222221 12212max .,.,0

41、nnnnnnmmmnnmnZc xc xc xa xa xa xba xa xa xbsta xaxaxbx xx88121111121111221222212121 mmnmmnmmnmmmmmmmmnbxxxxxbaaaaabaaaaabaaaaa初等行變換初等行變換89用矩陣表示為：用矩陣表示為：1111()()()Bb ABb BB b I B N N121111122121 111mmnmnmnmmmmnbxxxxxbaabaabaa112212, ,0mmmmxb xbxbxxxn由此得基可行解：由此得基可行解：是否為最優(yōu)，是否為最優(yōu)，如何由表得到如何由表得到判斷？判斷？90( ,

42、)BNXAXB NbX(,) BBNBBNNNXZCCC XC XX檢驗數(shù)的計算：檢驗數(shù)的計算：BNBXNXb11BNXB bB NX11()BNNNCB bB NXC X11()NBBNCCBXCbB N0NNZX911(1,2, )jjBjcC B P jmmn110(1,2,)iiBiiBcC B PcCim 1(1,2, )iiBicC B P in非基變量的檢驗數(shù)為：非基變量的檢驗數(shù)為：基變量的檢驗數(shù)為：基變量的檢驗數(shù)為：故所有變量的檢驗數(shù)統(tǒng)一表示為：故所有變量的檢驗數(shù)統(tǒng)一表示為：92 單純形表：單純形表：1211111221210121 11 1mmnmnmnmmmmnmmnbxx

43、xxxbaabaabaazE單位陣單位陣B-1N非基陣非基陣基變量基變量XB非基變量非基變量XNN01111BBB bB AC B bCC B A11110BNBB bIB NC B bCC B N93xxxxmn12 2 1 0 0 0 jc BCbBX檢驗數(shù) 1mbbxxm1ccm1單純形表結(jié)構(gòu) 單純形表單純形表 24/65/1minA0znmcccc21C94xxxxmn12 2 1 0 0 0 24/65/1C檢驗數(shù)1 mbbxxm1ccm1單純形表結(jié)構(gòu) 單純形表單純形表A0z1( ,0,0)TmXbb基可行解：jc BCbBXmin95單純形表結(jié)構(gòu) 單純形表單純形表xxxxmn12

44、2 1 0 0 0 24/65/1C檢驗數(shù)1mbbxxm1ccm1A0z10BCZB bjc BCbBXmin96單純形表結(jié)構(gòu)單純形表結(jié)構(gòu)xxxxmn12 2 1 0 0 0 24/65/1C檢驗數(shù)bbm1xxm1ccm1A0zjcmjjaa1jjc BCbBXmin00 iijiiji Bi Bjjjjji Bzcbzc aczZZx令：令：檢驗數(shù) 單純形表單純形表97單純形表結(jié)構(gòu) 單純形表單純形表xxxxmn12 2 1 0 0 0 24/65/1C檢驗數(shù) 1mbbxxm1ccm1A0zkmmkmaa, 1km 0設(shè)此設(shè)此為主列為主列0minilimkiimklmkbbaaal主行主行jc

45、 BCbBXmin98單純形表結(jié)構(gòu)單純形表結(jié)構(gòu) 單純形表單純形表xxxxmn12 2 1 0 0 0 24/65/1C檢驗數(shù) 1mbbxxm1ccm1Akmmkmaa, 1km lkmla,主元主元jc BCbBXmin0z99max , b0 . 0ZCXAXbstX對資源約束模型對資源約束模型100max0 . ,0sssZCXXAXI XbstX X 化標準型后化標準型后()AA I易知易知 B B = =I I 是可行基。是可行基。對應(yīng)對應(yīng)00bAIC101用單純形表求解LP問題122121212max25156224.5,0Zxxxxxs txxxx例例2:2: 用單純形表求解用單純

46、形表求解LPLP問題問題102解解: : 化標準形化標準形123452312412515max20005156224.5,0Zxxxxxxxxxxstxxxxx則則B=(P3 P4P5)是一個可行基。是一個可行基。初始單純形表為：初始單純形表為：103cj 2 1 0 0 0 CB XB b x1 x2 x3 x4 x5 min 0 0 0 x3 x4 x5 15 24 5 0 6 1 5 2 1 1 0 0 0 1 0 0 0 0 0 1 24/6 5/1 cj- -zj 0 2 1 0 0 0 0 0 主元化為1主列單位向量x4換出,x1換入表表1：列初始單純形表：列初始單純形表 （單位矩

47、陣對應(yīng)的變量為基變量）（單位矩陣對應(yīng)的變量為基變量）檢驗數(shù)中最大者檢驗數(shù)中最大者對應(yīng)的列為主列對應(yīng)的列為主列104cj 2 1 0 0 0 CB XB b x1 x2 x3 x4 x5 min 0 0 0 x3 x4 x5 15 24 5 0 6 1 5 2 1 1 0 0 0 1 0 0 0 0 0 1 24/6 5/1 cj- -zj 0 2 1 0 0 0 0 0 0 2 0 x3 x1 x5 15 4 1 0 1 0 5 1/3 2/3 1 0 0 0 1/6 - -1 1/ /6 6 0 0 0 1 15/5 12/1 3/2 cj- -zj -8 0 1/3 0 - -1 1/ /

48、3 3 0 0 表表2：換基：換基 （初等行變換，主列化為單位向量，主元為（初等行變換，主列化為單位向量，主元為1）1050檢驗數(shù)最優(yōu)解為最優(yōu)解為X=(7/2,3/2,15/2,0,0)=(7/2,3/2,15/2,0,0)T T最優(yōu)目標函數(shù)值最優(yōu)目標函數(shù)值maxZ=17/2maxZ=17/2106問題：線性規(guī)劃問題：線性規(guī)劃問題化為標準形時，問題化為標準形時，若約束條件的系數(shù)若約束條件的系數(shù)矩陣中不存在單位矩陣中不存在單位矩陣，如何構(gòu)造矩陣，如何構(gòu)造初始可行基？初始可行基？ 10711221111221121122222112212 Z.,.,0nnnnnnmmmnnmnmaxc xc xc

49、 xa xaxaxbaxaxaxbs taxaxaxbxxx加入加入人工變量人工變量設(shè)線性規(guī)劃問題的標準形為：設(shè)線性規(guī)劃問題的標準形為：10811 112211121 12222221 122121,. . . ,.,.,nnnnnnmmmnnn mmnnn ma xa xa xxba xa xa xxba xa xa xxbx xx xx0加入人工變量加入人工變量, ,構(gòu)造初始可行基構(gòu)造初始可行基. .109是一初始基可行解。則：為非基變量，為基變量，令： ),.,0,.0 ,0(,., ,.,21)0(2121TmnmnnnbbbXxxxxxx約束條件已改變，目標函數(shù)如何調(diào)整？1101 1

50、、大、大 M M 法法目標函數(shù)中添加目標函數(shù)中添加“罰因子罰因子”-M-M（M M是任意大的正數(shù)）是任意大的正數(shù)）為人工變量系數(shù)，只要人為人工變量系數(shù)，只要人工變量工變量00，則目標函數(shù)，則目標函數(shù)不可能實現(xiàn)最優(yōu)不可能實現(xiàn)最優(yōu)。人工變量在目標函數(shù)中的系數(shù)為人工變量在目標函數(shù)中的系數(shù)為 - -M, 其中，其中，M 為任意大的正數(shù)。為任意大的正數(shù)。1110.,., . . ., 1212211222222121111212111mnnnmmnnmnmmnnnnnnxxxxxbxxaxaxabxxaxaxabxxaxaxa1 1221 Z.nnnn mmaxc xc xc xMxMx構(gòu)造新的線性規(guī)劃

51、：構(gòu)造新的線性規(guī)劃：112目標函數(shù)中添加目標函數(shù)中添加“罰因子罰因子”-M-M為人工變量系數(shù)，只要人為人工變量系數(shù)，只要人工變量工變量00，則目標函數(shù)，則目標函數(shù)不可能實現(xiàn)最優(yōu)。不可能實現(xiàn)最優(yōu)。求解結(jié)果出現(xiàn)檢驗數(shù)非正求解結(jié)果出現(xiàn)檢驗數(shù)非正 .用單純形法求解用單純形法求解1) 若基變量中含非零的人工變量，若基變量中含非零的人工變量， 則原問題無可行解；則原問題無可行解；0j2) 若基變量中不含非零的人工變量，若基變量中不含非零的人工變量，則原問題有最優(yōu)解。則原問題有最優(yōu)解。113123123123131233 2 114 23.2 1,0minZxxxxxxxxxstxxx x x 例例3: 求

52、解線性規(guī)劃問題求解線性規(guī)劃問題11412345123412351312345max3002 11423. 2 1,0Zxxxxxxxxxxxxxstxxx x x x x 解解: :加入松弛變量標準化為：加入松弛變量標準化為：1151234567max300ZxxxxxMxMx l加入人工變量構(gòu)造初始可行基加入人工變量構(gòu)造初始可行基. . 1234123561371234567 2 1142 3. 2 1,0 xxxxxxxxxstxxxx x x x x x x則則B=(P4 P6 P7)是一個可行基（人造基）是一個可行基（人造基）借用為基變量借用為基變量初始單純形表為：初始單純形表為：1(

53、1,2, )jjBjcC B P jn檢驗數(shù)為116表表1（初始單純形表）（初始單純形表）cj- -zj 4M 3-6M -1+M -1+3M 0 -M 0 0 117118檢驗數(shù)均非正，此為檢驗數(shù)均非正，此為最終單純形表最終單純形表最優(yōu)解為最優(yōu)解為X=(4,1,9,0,0)T ，原規(guī)劃最優(yōu)目標函數(shù)值原規(guī)劃最優(yōu)目標函數(shù)值minZ=-2max2Z 1192 2、兩階段法、兩階段法M在計算機上在計算機上處理處理困難。困難。分階段處理分階段處理先求先求初始可行基，初始可行基，再求解。再求解。1201211 112211121 12222221 12212 . . . ,.,mnnnnmmmnnmmm

54、inyyya xa xa xyba xa xa xybsta xaxa xybx xx1,.,0nmyy 目標函數(shù)僅含目標函數(shù)僅含人工變量，并要求人工變量，并要求實現(xiàn)最小化。實現(xiàn)最小化。 若其最優(yōu)解的若其最優(yōu)解的目標函數(shù)值不為目標函數(shù)值不為0，也即最優(yōu)解的基，也即最優(yōu)解的基變量中含有非零的變量中含有非零的人工變量，則原線人工變量，則原線性規(guī)劃問題無可行性規(guī)劃問題無可行解。解。第一階段第一階段: : 構(gòu)造如下的線性規(guī)劃問題構(gòu)造如下的線性規(guī)劃問題 （稱為輔助規(guī)劃）（稱為輔助規(guī)劃） 121 1) 若若0，則原問題無可行解。，則原問題無可行解。2) 若若=0，進入第二階段。，進入第二階段。a. 若基變

55、量中不含人工變量，則此最優(yōu)若基變量中不含人工變量，則此最優(yōu)基就是原問題的一個可行基；基就是原問題的一個可行基；b. 若基變量中含有人工變量，則還原為若基變量中含有人工變量，則還原為方程方程:0rrjjrn iijiya xay用單純形法求解用單純形法求解122若這時所有的若這時所有的 全為全為0.即即 則表明原問題中第則表明原問題中第r個方程是多余的，可以去個方程是多余的，可以去掉掉多余方程多余方程。0rrn iiiyay求和式中的變量皆為非基變量求和式中的變量皆為非基變量.rja 若至少有某個若至少有某個 不為不為0.則以其為主元做則以其為主元做換基迭代換基迭代,可將可將yr從基變量中去掉從

56、基變量中去掉.rja123例例4：123123123131233 2 114 23.2 1,0minZxxxxxxxxxstxxx x x 124解解: :加入松弛變量標準化為：加入松弛變量標準化為：12345123412351312345max3002 11423. 2 1,0Zxxxxxxxxxxxxxstxxx x x x x 125671234123561371234567 min 2 114 2 3.2 1,0 xxxxxxxxxxxstxxxx x x x x x x構(gòu)造第一階段輔助規(guī)劃并求解構(gòu)造第一階段輔助規(guī)劃并求解則則B=(P4 P6 P7)是一個可行基（人造基）是一個可行基（

57、人造基）初始單純形表為：初始單純形表為：1(1,2, )jjBjcC B P jn檢驗數(shù)為126cj 0 0 0 0 0 -1 -1 CB XB b x1 x2 x3 x4 x5 x6 x7 min 0 -1 -1 x4 x6 x7 11 3 1 1 -4 -2 -2 1 0 1 2 1 1 0 0 0 -1 0 0 1 0 0 0 0 0 1 11/1 3/2 1/1 cj- -zj 0 0 0 0 0 -1 -1 0 -1 0 x4 x6 x3 10 1 1 3 0 -2 -2 1 0 0 0 1 1 0 0 0 -1 0 0 1 0 - -1 1 -2 1 1/1 cj- -zj 1 0

58、 1 0 0 -1 0 - -3 3 第一階段、求第一階段、求min cj- -zj 4 -6 1 3 0 -1 0 0 127得到輔助規(guī)劃的最終表，由此進入第二階段。得到輔助規(guī)劃的最終表，由此進入第二階段。128輔助規(guī)劃的最終表輔助規(guī)劃的最終表不含人工變量不含人工變量且且=0=0129cj 3 -1 -1 0 0 CB XB b x1 x2 x3 x4 x5 min 0 -1 -1 x4 x2 x3 12 1 1 3 0 -2 0 1 0 0 0 1 1 0 0 -2 -1 0 12/3 cj- -zj 3 -1 -1 0 0 130最優(yōu)解為最優(yōu)解為X=(4,1,9,0,0)T ，原規(guī)劃最優(yōu)

59、目標函數(shù)值原規(guī)劃最優(yōu)目標函數(shù)值minZ=-2檢驗數(shù)均非正，此為檢驗數(shù)均非正，此為最終單純形表最終單純形表max2Z 131 例：例：某工廠利用三種資源生產(chǎn)兩種產(chǎn)品，某工廠利用三種資源生產(chǎn)兩種產(chǎn)品， 有關(guān)數(shù)據(jù)如下表有關(guān)數(shù)據(jù)如下表：一、對偶問題的提出一、對偶問題的提出原料原料A原料原料B設(shè)備設(shè)備C利潤利潤(百元百元)0612521115公斤公斤24公斤公斤 5臺時臺時產(chǎn)品產(chǎn)品產(chǎn)品產(chǎn)品資源限量資源限量132如何安排生產(chǎn)，如何安排生產(chǎn)，使獲利最多使獲利最多？廠廠家家設(shè)設(shè) 產(chǎn)量產(chǎn)量 產(chǎn)量產(chǎn)量1x2x122121212m ax251 5622 4. 5 ,0zxxxxxs txxxx廠家考慮將資源轉(zhuǎn)讓出去

60、？廠家考慮將資源轉(zhuǎn)讓出去？133 設(shè)：原料設(shè)：原料A A 百元公斤百元公斤 原料原料B B 百元公斤百元公斤 設(shè)備設(shè)備C C 百元臺時百元臺時1y2y3y收收購購方方 付出的代價最小，付出的代價最小， 且讓對方能接受。且讓對方能接受。出讓收益應(yīng)不低于出讓收益應(yīng)不低于用同等數(shù)量的資源用同等數(shù)量的資源自己生產(chǎn)的利潤。自己生產(chǎn)的利潤。134 原料原料A 原料原料B設(shè)備設(shè)備C利潤利潤(百元百元)0612521115公斤公斤24公斤公斤 5臺時臺時資源限量資源限量 廠家能接受的條件：廠家能接受的條件：123min15245wyyy單位產(chǎn)品單位產(chǎn)品出讓出讓收入不低于收入不低于2 2百元百元單位產(chǎn)品單位產(chǎn)品