運籌學(xué)思考練習(xí)題答案

1、第一章 L.P及單純形法練習(xí)題答案、判斷下列說法是否正確.線性規(guī)劃模型中增加一個約束條件，可行域的范圍一般將縮小，減少一個約束條件， 可行域的范圍一般將擴(kuò)大。（）.線性規(guī)劃問題的每一個基解對應(yīng)可行域的一個頂點。（）.如線性規(guī)劃問題存在某個最優(yōu)解，則該最優(yōu)解一定對應(yīng)可行域邊界上的一個點。（）.單純形法計算中，如不按最小比值原則選取換出變量，則在下一個基可行解中至少有一個基變量的值為負(fù)。（）. 一旦一個人工變量在迭代中變?yōu)榉腔兞亢?，該變量及相?yīng)列的數(shù)字可以從單純形表中刪除，而不影響計算結(jié)果。（）.若X1、X2分別是某一線性規(guī)劃問題的最優(yōu)解，則X =%X1十九2X2也是該線性規(guī)劃問題的最優(yōu)解，其中

2、斯、%為正的實數(shù)。（）.線性規(guī)劃用兩階段法求解時，第一階段的目標(biāo)函數(shù)通常寫為 MinZ=Xai（Xai為人工變 量），但也可寫為MinZ =kiXai,只要所有ki均為大于零的常數(shù)。（）.對一個有n個變量、m個約束的標(biāo)準(zhǔn)型的線性規(guī)劃問題，其可行域的頂點恰好為C：個。（）.線性規(guī)劃問題的可行解如為最優(yōu)解，則該可行解一定是基可行解。（）.若線性規(guī)劃問題具有可行解，且其可行域有界，則該線性規(guī)劃問題最多具有有限個數(shù) 的最優(yōu)解。（）二、求得L.P問題MaxZ =2x1 3x2x1 +2x2 F= 8j 4x1+x4=164x2+x5 =12Xj 0; j =1,2,111,5的解如下：X=（0,3,2,

3、16,G）T;X=（4,3,-2,0,0）T;X=（3.5,2,0.5,2,4）T;X二（8,0,0,-16,12）T;=（4.5,2,-0.5,-2,4）T; X=（3,2,1,4,4）T;X=（4,2,0,0,4）T。要求：分別指出其中的基解、可行解、基可行解、非基可行解。答案：基解：X、X，X% X，可行解：X、X、X、X，基可行解：X、X、非基可行解:X，X（或非基可行解:X、X、X、X、X6）。三、求解下列線性規(guī)劃問題:MinZ =-5x1 -4x2 x1 +2x2 6 2x1 -x2 4 s.t.5xi 3x2 15xi ,x2 -0化為標(biāo)準(zhǔn)型:MaxZ = 5x1 4x2x1 +

4、 2x2 + x3 = 62x1-x2+x4=4 s.t.5x1 3x2 x5 = 15“叢2叢3叢4M5 -0得初始單純形表并求解:cj540004CbX BbXiX2X3X4X50*361210060 x442-10102T0Xs155300131Q . c . Z . jcjzj0540000X3405/21-1/208/55Xi21-1/201/20一0X550m20-5/2110/11Tc. = c _ z jcjzj-10013/20-5/200X319/11001近-5/1119/7T5Xi27/111003/111/1194X210/11010-5/112/11一%=cj -z

5、j-175/110005/11-13/110X419/70011/71-5/75Xi12/710-3/702/74X215/7015/70-1/7% =(cj -zj-120/700-5/70-6/70所有檢驗數(shù)叫 0 ,已得最優(yōu)解：X* = y,y,0,y,0 1 , MinZ120第二章對偶理論與靈敏度分析練習(xí)題答案1.判斷下列說法是否正確：(1)任何線性規(guī)劃問題存在并具有惟一的對偶問題；() 根據(jù)對偶問題的性質(zhì)，當(dāng)原問題為無界解時，其對偶問題無可行解，反之，當(dāng)對偶問題 無可行解時，其原問題具有無界解；()(3)設(shè)？j, %分別為標(biāo)準(zhǔn)形式的原問題與對偶問題的可行解，Xj, yi分別為其最優(yōu)

6、解，則包 TOC o 1-5 h z nnmm有 Cj?j 0 ,說明在最優(yōu)生產(chǎn)計劃中第i種資源已 完全耗盡；() * . . . . . 一. . * . . . . . 、 . .(6)已知yi為線性規(guī)劃的對偶問題的最優(yōu)解， 若yi =0 ,說明在最優(yōu)生產(chǎn)計劃中第i種資源一 定有剩余；()(7)若某種資源的影子價格等于k,在其他條件不變的情況下，當(dāng)該種資源增加5個單位時，相應(yīng)的目標(biāo)函數(shù)值將增大5k；()(8)應(yīng)用對偶單純形法計算時，若單純形表中某一基變量 Xi 0,又xi所在行的元素全部大于 或等于零，則可以判斷其對偶問題具有無界解；()(9)若線性規(guī)劃問題中的bi, Cj值同時發(fā)生變化，

7、反映到最終單純形表中，不會出現(xiàn)原問題與 對偶問題均為非可行解的情況；()(10)在線性規(guī)劃問題的最優(yōu)解中，如某一變量 xj為非基變量，則在原來問題中，無論改變它 在目標(biāo)函數(shù)中的系數(shù)cj或在各約束中的相應(yīng)系數(shù)aij,反映到最終單純形表中，除該列數(shù)字有 變化外，將不會引起其他列數(shù)字的變化。()2,下表是某一約束條件用連接的線性規(guī)劃問題最優(yōu)單純形表格，其中X4、X5為松弛變量。XbbX1X2X3X4X5X3r 5/201/2111/210X15/21-1/20-1/61/3j0-40-4-2要求：(1)寫出原線性規(guī)劃問題及其對偶問題的數(shù)學(xué)模型；(2)直接由表寫出對偶問題的最優(yōu)解；(3)其它條件不變時

8、，約束條件右端項 b1在何范圍內(nèi)變化，上述最優(yōu)基不變。(4)若以單價2.5購入第一種資源是否值得，為什么？若有人愿意購買第二種資源應(yīng)要價多少，為什么？答案：注：該問題得解法非唯一，以下解法只是其中一種（各解法原理相同）。由題意已知原線性規(guī)劃問題目標(biāo)函數(shù)為 Max （因q00為最優(yōu)），且C4、C5為0 （松弛變 量目標(biāo)函數(shù)系數(shù)為0）。根據(jù)%=Cj _CbBP知:。一;1 。3一2160-13，得：A|b =根據(jù)B1 A|b =12112/20-160130l32 1051 0 1 10則原線性規(guī)劃問題的數(shù)學(xué)模型為:其對偶問題的數(shù)學(xué)模型為:MaxZ =6x1 -2x2 10 x3Min . = 5

9、y1 10y2rx2 +2x3 5 3y 2 2 6s.t.43x1x2 +x3 =(B-1b)i = B,得Abr的變化范圍為：呻刈-6/a同0組“叩-5/為同0,其中：就=（屋）,。則:5 1.5Max _+_ WAb1 Min (_),即-5 ib1 0,表中已得最優(yōu)解：x14 =10 , x15 =90 (就地貯存)，x21 = 50 , x22 = 50 , 人八|=t t 、一 Ttr一 *x32 =20 , x33 =60 , x34 =70 ,其余 Xij =0 ；取小運費：Z =2260。但考慮非基變量X23的檢驗數(shù) 公=0,該問題有無窮多最優(yōu)解，用閉回路法調(diào)整得另一最 優(yōu)解

10、：x14=10 ,x15 =90(就地貯存)，x21=50,x23 = 50,x32=70 ,x33= 10,x34=70,其余xj =0。(見下表)三、針對目標(biāo)規(guī)劃模型：MinZ =P1dl P2d3 P3d2f4x1 +2x2 +d1d1 =4 x1 -2x2 +drd/=4 x1 2x2 dJ-d3 =83xi +2x2 12(1)用圖解法求出問題的滿意解。(2)若將目標(biāo)函數(shù)改為：MinZ = Rd； P2d2 P dd3xi，x2 -0;di-,di -0,i =1,2,3滿意解會如何變化。(1)滿意解為圖中A(4,0)、B(6,1)、C(2,3)所圍成的區(qū)域。X2B(6,1)XiA(

11、4,0)ndrC(2,3)Xi -2x2 =4 -1+ x1 2x2 =8 滿意解為B(6,1)、C(2,3)線。第五章整數(shù)規(guī)劃練習(xí)題答案判斷下列說法是否正確.用分枝定界法求解一個極大化的整數(shù)規(guī)劃問題時，任何一個可行整數(shù)解的目標(biāo)函數(shù)值是 該問題目標(biāo)函數(shù)值的下界。（） TOC o 1-5 h z .用割平面法求解整數(shù)規(guī)劃時，構(gòu)造的割平面有可能切去一些不屬于最優(yōu)解的整數(shù)解。（）.用割平面法求解純整數(shù)規(guī)劃時，要求包括松弛變量在內(nèi)的全部變量必須取整數(shù)值。（）.指派問題數(shù)學(xué)模型的形式與運輸問題十分相似，故也可以用表上作業(yè)法求解。（）答案:二.設(shè)有五項工作要分派給五個工人，每人的作業(yè)產(chǎn)值如下表所示，為了使

12、總產(chǎn)值最大，問 應(yīng)如何分配這五項工作，并求得最大產(chǎn)值。25、-105314、00425104252-1 T02641T015-15130454795747;101 6 42 5 1B = ； 1 3 76 2 49 5 7-1 -1-14 24 01 50 24 61 30 34 00 34 6 ,0 334t 116領(lǐng)領(lǐng)34214.一1542.一464額42目3 / 10310，力。3-3 4 0 0-1巧一-4_4l =m115 4”5-203-6 0 2 0。4646/ 10 3 5 32、3035;1。2.一3542一300m=5=n,得最優(yōu)解。解矩陣X*= 00535；10 0 10

13、、0 10 00 0 0 1 o10 0 00 0 0 0工作 工人、ABCDE甲94685乙P 859106丙97358丁:48695戊105363設(shè)原矩陣為A,因求極大問題，令B=M-aij,其中M=Maxaij=10,則:即，甲 TD,乙TC,丙TE, 丁TB,戊TA,最大產(chǎn)值=10+8+9+8+8=43三.對整數(shù)規(guī)劃MaxZ = 8x1 5x22x1 3x2 121: x1 x2 6 6x1 ,x2之0,整數(shù)解得其松弛問題最優(yōu)表如下:Qr 85009CbXbbX1X2X3X45x23/2011/4r-1/48Xi15/4-10 :1/83/875/200-9/4-7/4要求：用割平面法

14、完成求解過程。答案：(1)產(chǎn)生高莫雷約束：根據(jù) Maxfi,應(yīng)選取 xi 所在行為源行：+1x3+3x4=33 ,即，)x+lO+-+- j)4=3+- TOC o 1-5 h z 884884、 、一 ,3 13產(chǎn)生高莫雷約束為：3 -2x3 -3x4 0 04 88(2)將高莫雷約束加入松弛變量x5,寫入原表最后一行形成下表并用對偶單純形法求解：Cj850009CbXbbX1X2X3X4X55X23/2011/4-1/408X115/4101/83/800X5-3/400-1/8-3/81一75/200-9/4-7/4 T0Cj850009CbXbbX1X2X3X4X55X22011/30

15、-2/38X13100010X42001/31-8/33400-5/30-14/3b列均為整數(shù)，所有 s均非負(fù)，已得最優(yōu)整數(shù)解：X*=(3, 2)T, Z*=34第六章動態(tài)規(guī)劃的基本方法習(xí)題1,已知網(wǎng)絡(luò)圖各段路線所需費用如圖所示:試求從0圖中A線和B線上的數(shù)字分別代表相應(yīng)點的有關(guān)費用A線到B線的最小費用路線及其總費用。1417312152310161A線21 B線、12 、2|33156.彳4317 TOC o 1-5 h z 采取順序標(biāo)號法解得最小費用路線有兩條，即圖中的粗實線，具費用為17。2,用動態(tài)規(guī)劃方法求解22MaXZ =X1X2X3X1 x2x3 -6S.tX -0, i =1,2

16、,3S1、S2、S3、S4；并t己 S1ss6；按問題的變量個數(shù)劃分為一個三階段決策問題；設(shè)狀態(tài)變量為 取問題中的變量XI、X2、X3為決策變量；各階段指標(biāo)函數(shù)按乘積方式結(jié)合； 令最優(yōu)值函數(shù)fk(Sk) 表示為第k階段的初始狀態(tài)為Sk,從k階段到3階段所得到的最大值。設(shè)各階段狀態(tài)轉(zhuǎn)移方程為：S1=X1+X2+X3ss6, S2=S1-X1 , S3=S2-X2, S4=S3-X3=0（即 S3=X3）則有各階段允許決策集合：x3=S3 , 0 22, 0 X1用逆推法，從后向前依次有:自會二巧考僅二4及最優(yōu)解七二, fa) = Max 乂 f3底)】=Max x2 s20 手 90 2 ;S2

17、 ,-2=Max x2 (S2 -x2) 0 32 ：S2一=Max h2 (s2,x2)0 x2 S2r dhc,、2由 =(s2 -x2) -2x2 (s2 -x2) = G - x2) (s2 一3x2 )=0 得 dx2= S2(舍去)S2p d2h2又2-二-4s2 6 x2 d&=-2S2 ： 0S2貝 U： f2(S2) = S3271及取優(yōu)斛“甘之 f1 (s1) = Max x120仝1青-f2 (s2 ) | =一 2 4Max x1 0 步 i127324s2 = Max x1 (s x1)J 0 1 m 273 = Max h1 (s1 ,x1)*至dh1dx1x1(S

18、1 -xj3 .x：”(S1 )2=& 272727x1(s1 一 x1 )2(2sl 5x1) = 0 得x1 = 0(舍去)2x1 二= S15x1 = s (舍去)d2h dx124 ,、28=為6 -x1)(2s1 5x1)一去不佃-x 1 )(2s 一5x)20,、2一”(百 一 xj27d2h1dx1220 2,2、28 3 cs1)S1 0227 5 1 1 5 175 1x1普貝 U： f1) = Max x2 (S! - x1)3 =-4s2 (S1 -S1)30 冬冬 IL 2725275163125由于00 16不知道其具體值，故須再對S1求一次fi(si)的極值：Max

19、 f1(S1)= Max 16S13125 TOC o 1-5 h z 6 5165顯然，S1=6時fi(si)才能達(dá)到最大值。所以 f1(s)= f1 (6 )=Si =父6 =39.813123125312522按計算的順序反推，可求得最優(yōu)解為：x = S =父6 =2.4 , f1(s) =39.81312 ;55114 Q 4QS2 =S1-x*=6 -2.4 =3.6 貝x2= -s2=一父3.6 =1.2 ,f2(s2)=s；= 父 3.63 =6.912332727S3 =S2- x2=3.6 1.2 =2.4 則x3= S3=2.4 ,f3(Ss)=S2= 2.42 = 5.7

20、622即取優(yōu)解為：x1 =2.4 , x2=1.2, x3=2.4, MaxZ = x x2% = 39.81312。10第八章圖與網(wǎng)絡(luò)優(yōu)化練習(xí)題答案、判斷下列說法是否正確.在任一圖G中，當(dāng)點集V確定后，樹圖是G中邊數(shù)最少的連通圖。（）.若圖中某點vi有若干個相鄰點，與其距離最遠(yuǎn)的相鄰點為vj,則邊v, vj必不包含在最小支 撐樹內(nèi)。（）.若圖中從vi至各點均有惟一的最短路，則連接 vi至其他各點的最短路在去掉重復(fù)部分后， 恰好構(gòu)成該圖的最小支撐樹。（）.求網(wǎng)絡(luò)最大流的問題可歸結(jié)為求解一個線性規(guī)劃模型。（）二、有一項工程，要埋設(shè)電纜將中央控制室與 15個控制點連通。下圖中標(biāo)出了允許挖電纜溝 的

21、地點和距離（單位：hm）0若電纜線100元/m,挖電纜溝（深1m,寬0.6m） 土方30元/m3,其它材料和施工費用50元/m,76611412555844124請作出該項工程預(yù)算的最少費用。55911中央控制室6200m求出其最小支撐樹為:埋設(shè)電纜的最優(yōu)方案為總長所以最少工程預(yù)算費為 6200X（100+0.6 X 30+50=元11、用Dijkstra標(biāo)號法求出下圖中vi到各點的最短距離與最短路徑。圖中的粗線即為的數(shù)字。四、所給網(wǎng)絡(luò)中弧旁數(shù)字為該弧容量，求網(wǎng)絡(luò)最大流與最小截集。答案：第一次迭代:得增廣鏈：(Vs, vi, vt);按 依7調(diào)整，如上圖第二次迭代：12得增廣鏈：(vs, V1

22、, V4, vt);按0=4調(diào)整，如上圖第三次迭代：得增廣鏈：(Vs, V2, V4, Vt)；按k2調(diào)整，如上圖第四次迭代：得增廣鏈：(Vs, V1, V2, V4, Vt)；按k2調(diào)整，如上圖第五次迭代：得增廣鏈：(Vs, V3, V4, Vt)；按0=4調(diào)整，如上圖第六次迭代：13(-V2,2)(7,7)(13,13) _(3,2)(4,4)(V4,2)/vt(0,+ 8)(2,2)(V3,2)工/ V2(6,6)76)(3)Z(4,4) . 、7 V3 / 1(vs,2)得增廣鏈：(Vs, V3, V2, V4, Vt)；按0=2調(diào)整，如上圖。第七次迭代：V4X22)(15,14)所有fsj=Csj (均為飽和弧)標(biāo)號無法繼續(xù)，解題結(jié)束。圖中可行流即為所求最大流，最大流量為：V(