運籌學復習題型(推薦)

1、基本要求一、將線性規(guī)劃化為標準型和寫出相應的對偶規(guī)劃；二、用圖解法求解具有兩個決策變量的線性規(guī)劃問題；三、用單純形方法及人工變量法求解線性規(guī)劃問題；四、靈敏度分析；五、整數(shù)規(guī)劃與分枝定界法，0-1規(guī)劃與隱枚舉法，指派問題六、求解產(chǎn)銷平衡的運輸問題和產(chǎn)銷不平衡的運輸問題；七、動態(tài)規(guī)劃與求解。例題選講例：某工廠在計劃期內(nèi)要安排生產(chǎn)I、n兩種產(chǎn)品，這些產(chǎn)品分別需要在A、B、C、D四種不同的設(shè)備上加工。按工藝規(guī)定：產(chǎn)品I和n在個設(shè)備上所需要的加工時數(shù)于下表中。已知各設(shè)備在計劃期內(nèi)的有效臺時數(shù)分別是12、8、16和12。該工廠每生產(chǎn)一件產(chǎn)品I可得利潤2圓，每生產(chǎn)一件產(chǎn)品n可得利潤3圓，問：應如何安排生產(chǎn)

2、，可獲得最大利潤。產(chǎn)品設(shè)備ABCDI2142n3214解設(shè)生產(chǎn)產(chǎn)品I和n分別為Xj和x2件，則由條件可得關(guān)系maxz2x13x22x13x212x12x284x1x162x14x212xi0,i1,2標準型的概念：目標函數(shù)為極大化；資源常數(shù)bi0；約束條件關(guān)系為等式；決策變量x0。例：將下面的線性規(guī)劃化為標準型min3x14x22x3 5x44x1X22x3x4x1x23x3 x4 142x13x2x32x42x10,x20,x30,x4無非負限制解maxzz3x14x92x35x75x84x1x92x3x7x82x1x93x3x7xx5142x13x9%2x72%x62x1,x3,x5,x6

3、,x7,x8,x90.二、圖解法例用圖解法求解線性規(guī)劃問題極大化z2x13x2x12x284x1164x212xi0,i1,2解：最優(yōu)解X(4,2),z14三、單純形方法對于具有兩個以上決策變量的線性規(guī)劃問題，我們采用單純形方法進行求解。具體過程是：建立單純形表，在單純形表中，務必使基變量的價值系數(shù)為零，則檢驗數(shù)行是價值系數(shù)行的相反數(shù)；若檢驗數(shù)0,則當前解為最優(yōu)解(當前解是基變量取相應的資源常數(shù)，非基變量取為零)；若存在檢驗數(shù)0,則要進行相應的換基，即：迭代；進基：進基變量xs：sminii0出基：出基變量xk為第r行所對應的基變量,r由下面的關(guān)系確定br-n一八-z-minais0arsai

4、s以主元0rs進行迭代，目標：主元化為1,該列的其余元化為零。再一次判定當前解是否為最優(yōu)解。例用單純形法求解線性規(guī)劃極大化z2x13x25x3x1X2x372%5x23x310X0,i1,2,3解引入松弛變量X4,X5,得到原規(guī)劃的標準型極大化z2x13x25x30x40x5x1x2x3x472x15x23%x510x0,i1,2,3,4,5單純形表為xx1x2x3x4x5c23500x4111107x2530110235000x2111107x70851451083021所以，最優(yōu)解為(0,7,0);最優(yōu)解值為如人工變量法對于約束條彳中沒有m階單位陣的線性規(guī)劃，通過引入適當?shù)娜斯ぷ兞?，再加?/p>

5、求解。1 .大M法在大M法中，引入的人工變量的價值系數(shù)為M，而相應的約束條件系數(shù)向量為單位向量。2 .二階段法例用人工變量法求解線性規(guī)劃。maxz4x13x2s.t.x14x22x1x2x363x32為，x20,x3符號不限。例求解規(guī)劃maxz3x12x23x3x4,x12x23x3152x1x23x320,x1x2x3x410,xi0,i1,2,3,4.建立對偶規(guī)劃的要點原規(guī)劃是極大化，則對偶規(guī)劃是極小化；原規(guī)劃的價值系數(shù)是對偶規(guī)劃中的資源常數(shù)；原規(guī)劃與對偶規(guī)劃的約束條件系數(shù)矩陣為矩陣的轉(zhuǎn)置關(guān)系；原規(guī)劃中的第i個決策變量無非負限制，則對偶規(guī)劃中的第i個約束條件為等式；原規(guī)劃中的第i個決策變量

6、非正，則對偶規(guī)劃中的第i個約束條件取反向不等式；例求下面問題的對偶規(guī)劃極大化z3x12x25x37x42x13x22x37x42x1+2x32x432x1x24x3x48x10,x20,x30,x4無非負限制。解極小化w2y13y28y32y1y22y333y1y322%2y24y357yi2y2y37yi0,y20,y30對偶單純形法基本要求：檢驗數(shù)0；資源常數(shù)存在負值。解法：1 .列出對偶單純形表；2 .將基變量在目標函數(shù)中系數(shù)化為零，檢驗數(shù)為新目標函數(shù)中系數(shù)的相反數(shù)；3 .判斷，若0,b0,則當前解為最優(yōu)解；若0,且b中存在負項，則進行迭代，確定出基和進基變量;出基：記brminbib0

7、,xk為第r行對應的變量；進基：/dmina1ari0,xs為進基變量；以ars為主元進行迭代。目標：將主元化為1,該列的其余元化為0。靈敏度分析靈敏度分析的任務：確定各個變量使得最優(yōu)解保持不變的變化范圍；以及在最優(yōu)解改變的時候求出相應的最優(yōu)解。非基變量x的價值系數(shù)c的變化范圍，使最優(yōu)解保持不變。cii基變量xi的價值系數(shù)ci的變化范圍，使最優(yōu)解保持不變。ci:maxarj0cminaj0.arjarj若最優(yōu)解改變，則對兩種情況有c.資源常數(shù)bk變化范圍使最優(yōu)基不變：bk ： maxikikminbiikik 0 k 1,2,L ,m非基變量xk的系數(shù)向量k的增量k的變化范圍使最優(yōu)解不變：kk

8、cBB1k0，增加新的決策變量使最優(yōu)解保持不變：kCbB1kck0例：設(shè)線性規(guī)劃maxz10xi6x24x3x1x2x3100,10x14x25x3600,2x12x26x3300,xi0,i1,2,3.求：1.最優(yōu)解；2 .確定c1,c2,c3的范圍，使最優(yōu)解不變；取C3，求最優(yōu)解；63 .確定b1，b2,b3的范圍，使最優(yōu)基不變，取b1100,求最優(yōu)解；T4 .引入x7,P71,4,3,c78求最優(yōu)解；解1.由單純形方法得xX1X2X3X4X5x6c1064000X4111100100x51045010600x62260013001064000311X4010405210211為10060

9、5210x606501118055021010600015510200X26363101210100為6363x6004201100810222000003333T7100200c2200即，原問題的最優(yōu)解為X,0,z2.因X3為非基變量，故當C338時，即C320時，最優(yōu)解不變；33X,x2為基變量，由公式，當4c15,2c24,最優(yōu)解不變，即6c115,4c210時，最優(yōu)解不變現(xiàn)對c320,最優(yōu)解改變，此時38 133 35一,原最優(yōu)表為35063xX1X2X3X4x5x625c1063000015510200x2一6363101210100X16363x60042011000051020

10、220033330102515275X2126246100711175X1126246X3001101252422325503123002即相應的最優(yōu)解為X175 275,2523253.此時40n 50,200b2400,z2000 ,b31003100100b3,最優(yōu)基不變.即60 bi150,400b21000,b3200，最優(yōu)基不變10050,最優(yōu)解改變，此時51n700020036200321100b600,bB1b0600363300300201100b此時最優(yōu)表為x x1 x2 x3x4c 10 6 40X5x600x20156x110-6x6004532321 c 700 06

11、31八10006301100x20256x110x400212316160056131232003jT15005032859003即最優(yōu)解為X0,150,0T,z900.4.此時CbB1P7C71102一,一,0486820,故最優(yōu)解改變33P7B1P710，相應的最優(yōu)表為1xx1x2x3x4c10640X5X6X7008x20156/八1x110-6x600453232103200310031002cc2200-0233x701x11X6019113133203例用分枝定界法求解整數(shù)規(guī)劃maxzX1X29x1一x2142x1x2511413,為？20且為整數(shù).用隱枚舉法求解0-1規(guī)劃minz

12、4x13x22天200130變3c100032600032x15x23x34,4x1X23x33,X2x31,xi01,i1,2,3.運輸問題（產(chǎn)銷平衡）的求解方法：表上作業(yè)法1 .用最小元素法求初始解；2 .用位勢法求出當前解所對應的位勢：若xj為基變量，則行位勢和列位勢滿足關(guān)系qUiVj3 .用位勢法計算非基變量的影響系數(shù)：若xj為非基變量，則影響系數(shù)與行位勢和列位勢滿足關(guān)系ijCijUiVj4 .最優(yōu)解的判定：若影響系數(shù)j0則當前解為最優(yōu)解；否則通過解的調(diào)整求出最優(yōu)解；5 .解的調(diào)整：記：stminijij0,令xst為st所對應的非基變量，以xst為當前變量，構(gòu)造閉回路；在閉回路上確定

13、最大調(diào)整量；求出新解6 .重新判定當前解是否為最優(yōu)解。產(chǎn)銷不平衡的運輸問題的求解方法：設(shè)置虛擬產(chǎn)地或銷地以達到產(chǎn)銷平衡指派問題的求解:1 .mn的指派問題的最小值解的求解方法:用行縮減和列縮減在每行和每列至少產(chǎn)生一個零;用劃線法判定是否有n個獨立的零；如果有n個獨立的零，則可以求出最小值解；若沒有n個獨立的零，重新進行調(diào)整，以求出n個獨立的零。2 .mn的指派問題的最小值解的求解方法：設(shè)置虛擬變量，其價值系數(shù)取為零。3 .指派問題中的最大值求解。例求下面運輸問題的最小值解：12341311310721923437410593656解：由最小元素法得到初始解:v1=2V2=9V3=3V4=101

14、934u1=01311341037U2=-121392134U3=-53746105393656則：111,122,221,246,3110,3312,最小值為-6,非II1222243133基變量為x24,閉回路x24:x24x23%。%，最大調(diào)整量為1,得6,x34 3,新解：x135,x142,x213,x241,x32重新計算位勢及影響系數(shù)，得下表:V1=8V2=9V3=3V4=101234U1=01311351027u2=-721392314u3=-53746105393656115,122,227,236,314,3312,最小值為-5,非基變量為看閉回路對：。x112,x135,

15、x211,x243,X326,x343x14x24X21%1,最大調(diào)整為2,得新解:重新計算位勢及影響系數(shù)，得下表:v1=3v2=4v3=3V4=51234u1=01321135107u2=-221192334u3=03746105393656127,145,227,231,314,337,此時，ij°，故當前解為最優(yōu)解。最優(yōu)解值為:Y32351133465370o產(chǎn)銷不平衡的運輸問題：對產(chǎn)銷不平衡的運輸問題，求解的基本方法是設(shè)置虛擬變量，其單位運輸成本為0,從中求出最優(yōu)解。例：求下面運輸問題的最小運費解:123412113472103595378127234612341327650

16、2752360325452560402015例：求解運輸問題例：求下面指派問題的最小值解：12797989666717121412151466104107106解：1279798966671712141215146610410710670202430000835311800404140故最優(yōu)解為：x12X24X3150202230000105759800406362X43x551,最優(yōu)解值為Y7676632。例：求下面指派問題的最小值及最大值解:1518212419232218C,C26171619192123172151341041415914161378119例：求下面指派問題的最大值解:

17、7968105109887969886498例：最短路問題：求下面從A到E的最短線路和最短距離:解：k4:f4(D1)30,f4(D2)40k3:f3(C1)mind(C1,D1)f(D1),d(C1,D2)f(D2)min1030,404040f3(C2) mind(C2, D1)f(D1),d(C2,D2) f(D2)min60 30,30 40 70f3(C3) mind(C3, D1)f (D1),d(C3,D2) f (D2)min3030,304060；所以：f3(C1)40,C1D1E,f3(C2)70,C2D2Ef3(C3)60,C3D1Ek2:f2(B1)mind(B1,C1

18、)f3(C1),d(B1,C2)f3(C2)d(B1,C3)f3(C3)min7040,4070,5060110f2(B2)mind(B2,G)f3(C)d(B2,C2)fs©)d(B2c3)f3(C3)min3040,2070,406070f2(B3)mind(R,G)f3(Ci),d(RC)feC)d(B3,C3)f3(C3)min4040,1070,506080所以：f2(B1)110,BC1D1E,f2(B2)70BC1D1Ef3(B3)80BC1D1Ek1:f1(A)mind(A,B)f2(Bi),d(AB)fzB)d(A,B3)f2(B3)min20110,4070,3080110,AB2GD1E。例：設(shè)有某種肥料共6個單位，準備給4塊糧田用，其每塊糧田施肥數(shù)量與增產(chǎn)糧食的關(guān)系如下表所示。試求對每塊田施多少單位重量的肥料，才能使總的糧食增產(chǎn)最多。施肥糧田1234120251828242453947360576165475657874585709080690739585