運籌學(xué)填空題

1、第二章線性規(guī)劃的基本概念填空題1 線性規(guī)劃問題是求一個線性目標函數(shù)一在一組線性約束條件下的極值問題。2. 圖解法適用于含有兩個變量的線性規(guī)劃問題。3 .線性規(guī)劃問題的可行解是指滿足所有約束條件的解。4 在線性規(guī)劃問題的基本解中，所有的非基變量等于零。_5. 在線性規(guī)劃問題中，基可行解的非零分量所對應(yīng)的列向量線性無關(guān)6 .若線性規(guī)劃問題有最優(yōu)解，則最優(yōu)解一定可以在可行域的頂點(極點)達到。7 .線性規(guī)劃問題有可行解，則必有基可行解。8 如果線性規(guī)劃問題存在目標函數(shù)為有限值的最優(yōu)解，求解時只需在其基可行解 的集合中進行搜索即可得到最優(yōu)解。9 .滿足非負條件的基本解稱為基本可行解。10 .在將線性規(guī)

2、劃問題的一般形式轉(zhuǎn)化為標準形式時，引入的松馳數(shù)量在目標函數(shù)中的系數(shù)為零。11. 將線性規(guī)劃模型化成標準形式時，“胡”約束條件要在不等式左端加入松弛變量。12 .線性規(guī)劃模型包括決策(可控)變量，約束條件，目標函數(shù)三個要素。13 .線性規(guī)劃問題可分為目標函數(shù)求極大值和極小 值兩類。14 .線性規(guī)劃問題的標準形式中，約束條件取等式，目標函數(shù)求極大值，而所有變量必須非負。 15 .線性規(guī)劃問題的基可行解與可行域頂點的關(guān)系是頂點多于基可行解16 .在用圖解法求解線性規(guī)劃問題時，如果取得極值的等值線與可行域的一段邊界重合，則這段邊界 的一切點都是最優(yōu)解。4用大M法求目標函數(shù)為極大值的線性規(guī)劃問題時，引入

3、的人工變量在目標函數(shù)中的系數(shù)應(yīng)為一 5在單純形迭代中，可以根據(jù)最 _表中人工變量不為零判斷線性規(guī)劃問題無解。6 在線性規(guī)劃典式中，所有基變量的目標系數(shù)為0。7當線性規(guī)劃問題的系數(shù)矩陣中不存在現(xiàn)成的可行基時，一般可以加入人工變量構(gòu)造可行基。8在單純形迭代中，選岀基變量時應(yīng)遵循最小比值B法則。9線性規(guī)劃典式的特點是基為單位矩陣，基變量的目標函數(shù)系數(shù)為0。10.對于目標函數(shù)求極大值線性規(guī)劃問題在非基變量的檢驗數(shù)全部6jWO問題無界時，問題無解時情況下,單純形迭代應(yīng)停止。11在單純形迭代過程中，若有某個6 k>0對應(yīng)的非基變量xk的系數(shù)列向量Pk_< 0_時，則此問題是無界的。12在線性規(guī)

4、劃問題的典式中，基變量的系數(shù)列向量為單位列向量_13. 對于求極小值而言，人工變量在目標函數(shù)中的系數(shù)應(yīng)取14. （單純形法解基的形成來源共有三種15. 在大M法中，M表示充分大正數(shù)。第四章 線性規(guī)劃的對偶理論填空題1 線性規(guī)劃問題具有對偶性，即對于任何一個求最大值的線性規(guī)劃問題，都有一個求最小值/極小值的線性規(guī)劃問題與之對應(yīng)，反之亦然。2 .在一對對偶問題中，原問題的約束條件的右端常數(shù)是對偶問題的目標函數(shù)系數(shù)。3如果原問題的某個變量無約束，則對偶問題中對應(yīng)的約束條件應(yīng)為等式。4 .對偶問題的對偶問題是原問題 _。5 若原問題可行，但目標函數(shù)無界，則對偶問題不可彳 6 若某種資源的影子價格等于k

5、。在其他條件不變的情況下（假設(shè)原問題的最佳基不變），當該種資源增加3個單位時。相應(yīng)的目標函數(shù)值將增加3k。7 線性規(guī)劃問題的最優(yōu)基為 B,基變量的目標系數(shù)為 Cb,則其對偶問題的最優(yōu)解 Y*。8 .若X和Y*分別是線性規(guī)劃的原問題和對偶問題的最優(yōu)解，則有CX*三丫 b。9 若X、Y分別是線性規(guī)劃的原問題和對偶問題的可行解，則有C程Ybo10.若X*和Y分別是線性規(guī)劃的原問題和對偶問題的最優(yōu)解，則有CX*三Y*bo11 設(shè)線性規(guī)劃的原問題為 maxZ三CX Ax< b X>0則其對偶問題為 min三Yb YAcY0 。12. 影子價格實際上是與原問題各約束條件相聯(lián)系的對偶變量的數(shù)量表

6、現(xiàn)。13. 線性規(guī)劃的原問題的約束條件系數(shù)矩陣為A,則其對偶問題的約束條件系數(shù)矩陣為Alo14. 在對偶單純形法迭代中，若某b<0,且所有的aj0=1，2，-n），則原問題 無解。第五章線性規(guī)劃的靈敏度分析填空題1、靈敏度分析研究的是線性規(guī)劃模型的原始、最優(yōu)解數(shù)據(jù)變化對產(chǎn)生的影響。2、 在線性規(guī)劃的靈敏度分析中，我們主要用到的性質(zhì)是可行性，正則性。3在靈敏度分析中，某個非基變量的目標系數(shù)的改變，將引起該非基變量自身的檢驗數(shù)的變化。4如果某基變量的目標系數(shù)的變化范圍超過其靈敏度分析容許的變化范圍，則此基變量應(yīng)岀基。_5. 約束常數(shù)b:的變化，不會引起解的正則性的變化。6. 在某線性規(guī)劃問題

7、中，已知某資源的影子價格為丫1,相應(yīng)的約束常數(shù) b1，在靈敏度容許變動范圍內(nèi)發(fā)生厶b1的變化，則新的最優(yōu)解對應(yīng)的最優(yōu)目標函數(shù)值是Z*+yiAb （設(shè)原最優(yōu)目標函數(shù)值為 Z* ）7若某約束常數(shù)bi的變化超過其容許變動范圍，為求得新的最優(yōu)解， 需在原最優(yōu)單純形表的基礎(chǔ)上運用對_ 偶單純形法求解。8已知線性規(guī)劃問題，最優(yōu)基為B,目標系數(shù)為Cb,若新增變量xt，目標系數(shù)為 系數(shù)列向量為Pt,則當Ct三巳時，xt不能進入基底。9如果線性規(guī)劃的原問題增加一個約束條件，相當于其對偶問題增加一個變量。_10、若某線性規(guī)劃問題增加一個新的約束條件，在其最優(yōu)單純形表中將表現(xiàn)為增加二行，一列。11 線性規(guī)劃靈敏度分

8、析應(yīng)在最優(yōu)單純形表的基礎(chǔ)上，分析系數(shù)變化對最優(yōu)解產(chǎn)生的影響12. 在某生產(chǎn)規(guī)劃問題的線性規(guī)劃模型中，變量x的目標系數(shù)C代表該變量所對應(yīng)的產(chǎn)品的利潤，則當某一非基變量的目標系數(shù)發(fā)生增大變化時，其有可能進入基底。六章物資調(diào)運規(guī)劃運輸問題填空題1 .物資調(diào)運問題中，有m個供應(yīng)地，Ai,A2,Am,Aj的供應(yīng)量為a«i=1, 2，m）,n個需求地B1, B2,B，mnB的需求量為bj（j=1，2，n），則供需平衡條件為ai=bii 1 j 12 物資調(diào)運方案的最優(yōu)性判別準則是：當全部檢驗數(shù)非負時前的方案一定是最優(yōu)方案。3 .可以作為表上作業(yè)法的初始調(diào)運方案的填有數(shù)字的方格數(shù)應(yīng)為m+n 1個（

9、設(shè)問題中含有m個供應(yīng)地和n個需求地）4 若調(diào)運方案中的某一空格的檢驗數(shù)為1,則在該空格的閉回路上調(diào)整單位運置而使運費增加。5 .調(diào)運方案的調(diào)整是要在檢驗數(shù)岀現(xiàn)負值的點為頂點所對應(yīng)的閉回路內(nèi)進行運量的調(diào)整。6 按照表上作業(yè)法給岀的初始調(diào)運方案，頁每一空格岀發(fā)可以找到且僅能找到_1條閉回路7 在運輸問題中，單位運價為Cj位勢分別用Ui, Vj表示，則在基變量處有 q Cj=ui+V。8、供大于求的、供不應(yīng)求的不平衡運輸問題，分別是指mai _> “ b的運輸 ai _< n b的運輸問題。i 1 j 1i 1j 1 i10 在表上作業(yè)法所得到的調(diào)運方案中，從某空格岀發(fā)的閉回路的轉(zhuǎn)角點所

10、對應(yīng)的變量必為基變量。11 .在某運輸問題的調(diào)運方案中， 點（2,2）的檢驗數(shù)為負值，（調(diào)運方案為表所示）則相應(yīng)的調(diào)整量應(yīng)為 300。InmIVa300100300B400C60030012. 若某運輸問題初始方案的檢驗數(shù)中只有一個負值：-2,則這個-2的含義是該檢驗數(shù)所在格單位調(diào)整量。13. 運輸問題的初始方案中的基變量取值為正。_14表上作業(yè)法中，每一次調(diào)整 1個“入基變量”。15. 在編制初始方案調(diào)運方案及調(diào)整中，如岀現(xiàn)退化，則某一個或多個點處應(yīng)填入數(shù)字 016運輸問題的模型中，含有的方程個數(shù)為n+M個。17表上作業(yè)法中，每一次調(diào)整，出基變量”的個數(shù)為1o18給出初始調(diào)運方案的方法共有三

11、種。19.運輸問題中，每一行或列若有閉回路的頂點，則必有兩個。第七章整數(shù)規(guī)劃填空題1 用分枝定界法求極大化的整數(shù)規(guī)劃問題時，任何一個可行解的目標函數(shù)值是該問題目標函數(shù)值的下界。2 在分枝定界法中，若選 Xr=4/3進行分支，則構(gòu)造的約束條件應(yīng)為X1< 1, X1> 2。3 .已知整數(shù)規(guī)劃問題 P0,其相應(yīng)的松馳問題記為 Po'若問題P0無可行解，則問題 P。無可行解。4 .在0 - 1整數(shù)規(guī)劃中變量的取值可能是0或1 o5 對于一個有n項任務(wù)需要有n個人去完成的分配問題，其解中取值為1的變量數(shù)為n個。6 分枝定界法和割平面法的基礎(chǔ)都是用_線性規(guī)劃方法求解整數(shù)規(guī)劃。7 若在對

12、某整數(shù)規(guī)劃問題的松馳問題進行求解時，得到最優(yōu)單純形表中，由X。所在行得 X1+1/7x3+2/7X5=13/7,則以X1行為源行的割平面方程為 一一二一 X3 - X5< 0_o8 在用割平面法求解整數(shù)規(guī)劃問題時，要求全部變量必須都為整數(shù)o _9 用割平面法求解整數(shù)規(guī)劃問題時，若某個約束條件中有不為整數(shù)的系數(shù)，則需在該約束兩端擴大適當倍數(shù)，將全部系數(shù)化為整數(shù)。10.求解純整數(shù)規(guī)劃的方法是割平面法。求解混合整數(shù)規(guī)劃的方法是分枝定界法_o11 求解0 1整數(shù)規(guī)劃的方法是隱枚舉法。求解分配問題的專門方法是匈牙利法。12. 在應(yīng)用匈牙利法求解分配問題時，最終求得的分配元應(yīng)是獨立零 _o13. 分

13、枝定界法一般每次分枝數(shù)量為2個.第八章圖與網(wǎng)絡(luò)分析填空題1 .圖的最基本要素是點、點與點之間構(gòu)成的邊2.在圖論中，通常用點表示，用邊或有向邊表示研究對象，以及研究對3. 在圖論中，通常用點表示研究對象，用邊或有向邊表示研究對象之間具有某種特定的關(guān)系。4 .在圖論中，圖是反映研究對象 之間特定關(guān)系的一種工具。5 .任一樹中的邊數(shù)必定是它的點數(shù)減1。6 最小樹問題就是在網(wǎng)絡(luò)圖中，找出若干條邊，連接所有結(jié)點，而且連接的總長度最小。7 最小樹的算法關(guān)鍵是把最近的未_結(jié)點連接到那些已接結(jié)點上去。8求最短路問題的計算方法是從 亙互j開始逐步推算的，在推算過程中需要不斷標記平衡和最短路線。動態(tài)規(guī)劃石油輸送管

14、道鋪設(shè)最優(yōu)方案的選擇問題：如圖所示，其中A為出發(fā)點，E為目的地，B、C、D分別為三個必須建立油泵加壓站的地區(qū)，其中的Bi、B2、B3C1、C2、Ca;Di、D分別為可供選擇的各站站點。圖中的線段表示管道可鋪設(shè)的位置，線段旁的數(shù)字為鋪設(shè)管線所需要的費用，問如何鋪設(shè)管道才使總費用最??？第三階段：Ci Di E 5; C2 D2 E 8; C3 Di E 8; C3 D2 E 8;第二階段：BiCi Di E ii; Bi C2 D2 E ii; B2Ci Di E 8;B3 Ci Di E 9 ; B3C2 D2 E 9;第一階段：A Bi Ci Di E I4; A Bi C2 D2 E I4;

15、A B2 G Di E i3; A B3 Ci Di E i3;A B3 C2 D2 E i3;最優(yōu)解： A B2Ci Di E; A B3 Ci Di E; A B3 C2 D2 E最優(yōu)值：I3最小生成樹問題某大學(xué)準備對其所屬的 7個學(xué)院辦公室計算機聯(lián)網(wǎng)，這個網(wǎng)絡(luò)的可能聯(lián)通的途徑如圖所示，圖中VI,，V7表示7個學(xué)院辦公室，圖中的邊為可能聯(lián)網(wǎng)的途徑，邊上的所賦權(quán)數(shù)為這條路線的長度，單位為百米。請設(shè)計 一個網(wǎng)絡(luò)能聯(lián)通7個學(xué)院辦公室，并使總的線路長度為最短。V2i2I0V6V5V2i3343V72358GiV6V5解：在G中找到一個圈(Vi, V7, V6, Vi)，并知在此圈上邊Vi, V6的

16、權(quán)數(shù)I0為最大，在G中去掉 邊Vi, V6得圖Gi，如上圖所示在G2中找到一個圈(V2, V3, V , V7, V2),去掉其中權(quán)數(shù)最大的邊V5, V6，得圖G4，如上圖所示 在G4中找到一個圈(V2, V3， V7, V2)，去掉其中權(quán)數(shù)最大的邊V3，V7，得圖G5，如上圖所示 在G5中已找不到任何一個圈了，可知G即為圖G的最小生成樹。這個最小生成樹的所有邊的總權(quán)數(shù)為3+3+3+1+2+7=19(13 )某一個配送中心要給一個快餐店送快餐原料，應(yīng)按照什么路線送貨才能使送貨時間最短。下圖給岀了配送中心到快餐店的交通圖，圖中VI，V7表示7個地名，其中V1表示配送中心，V7表示快餐店，點之間的

17、聯(lián)線表示兩地之間的道路，邊所賦的權(quán)數(shù)表示開車送原料通過這段道路所需要的時間(單位：分鐘) 匸Vi,J=也V3,V，V5,V6 ,V7，邊的集合Vi，Vj|Vi，Vj兩點中一點屬于I,而另一點屬于J= Vi,V2，Vi , V3，并有Si2=Li+Ci2=0+4=4 ;Si3=Li+Ci3=0+18=18min (S12,S13)= S12 =4給邊Vi,V2中的未標號的點V2標以(4, 1),表示從Vi到V2的距離為4，并且在Vi到V2的最短路徑上V2的前面的點為Vi. 這時l=Vi,V2,J=V3,V4,V5,V V，邊的集合Vi,VjIVi,Vj兩點中一點屬于I,而另一點屬于J= Vi,V

18、3, V2, V3, V2, V4，并有S23=L2+C23=4+i2=i6 ; S24=L2+C24=4+i6=20 ; min (S23,S24 , Si3)= S23=i6給邊V2, V3中的未標號的點 V3標以(i6, 2) 這時I=Vi,V2,V3,J=VbV5,V6 ,V7,邊的集合Vi,VjIVi,Vj兩點中一點屬于I,而另一點屬于J= V2,V4, V3, V4, V3, V5，并有S34=L3+C34=i6+2=i8 ； S35=L3+C35=i6+6=22 ； S24=L2+C24=4+i6=20min (S34,S35,S24)= S4 =i8給邊V3 , V4中的未標號

19、的點 V4標以(i8 , 3) 這時I=Vi,V2,V3,V4,J=V5,V6 ,V7,邊的集合Vi,VjIVi,Vj兩點中一點屬于I,而另一點屬于J= V4,V6, V4, V5, V3, V5，并有Sw=L4+(>6=i8+7=25 ; S5=L4+C45=i8+8=26 ; min (S46,S45 ,S35)= S35 =24給邊V3 , V5中的未標號的點 V5標以(24, 3) 這時I=Vi,V2,V3,V4,V5 ,J=V5,V7，邊的集合Vi,VjI Vi,Vj兩點中一點屬于I,而另一點屬于J= V5, V7, V4, V6 ，并有S57=L5+C57=22+5=27 ;

20、 min (S57,Sw)= Si6 =25給邊V4, V6中的未標號的點 W標以(25, 4) 這時I=Vi,V2,V3,V4,V5,V6 ,J=V7,邊的集合Vi ,V I Vi,Vj兩點中一點屬于I,而另一點屬于J= V5, V7, V6, V7 ，并有S57=L6+C67=25+6=3i; min (S57,Ss7)= S57=27給邊V5 , V7中的未標號的點 V標以(27 , 5) 此時I=Vi , V2 , V3 , V4 , V5 , V6 , V7,J=空集，邊集合Vi , M I Vi , Vj兩點中一點屬于I,而另一點屬 于J=空集,計算結(jié)束。 得到最短路。從 V7的標

21、號可知從 Vi到V7的最短時間為27分鐘。即：配送路線為：Vi TV2 TV3 T V5 T V7最小生成樹問題某電力公司要沿道路為 8個居民點架設(shè)輸電網(wǎng)絡(luò)，連接8個居民點的道路圖如圖所示，其中 Vi ,V8表示8個居民點，圖中的邊表示可架設(shè)輸電網(wǎng)絡(luò)的道路，邊上的賦權(quán)數(shù)為這條道路的長度，單位為公里，請設(shè)計一個輸 電網(wǎng)絡(luò)，聯(lián)通這8個居民點,并使總的輸電線路長度為最短。 在圖中找到一個圈(Vi, V2 , V5 , V3),并知在此圈上邊Vi , V2和V3 , V5的權(quán)數(shù)4為最大，在圖中去掉邊Vi , V2; 在圖中找到一個圈（V3 , V4 , V8 , V5 , V V1 ）,去掉其中權(quán)數(shù)最

22、大的邊V4 , V8; 在圖中找到一個圈（V3 , V4 , V5, V3）,去掉其中權(quán)數(shù)最大的邊V4 , V5; 在圖中找到一個圈（V，V2，V6, V7，V5）,去掉其中權(quán)數(shù)最大的邊V2，V6； 在圖中找到一個圈（V5，V， v8，v5），去掉其中權(quán)數(shù)最大的邊V5，v8。 在圖中已找不到任何一個圈了，可知此即為圖G的最小生成樹。這個最小生成樹的所有邊的總權(quán)數(shù)為2+2+4+2+3+3+2=18最大流問題某地區(qū)的公路網(wǎng)如圖所示，圖中V1,，V6為地點，邊為公路，邊上所賦的權(quán)數(shù)為該段公路的流量（單位為千輛/小時），請求出Vi到V的最大流量。解：第一次迭代:第二次迭代：選擇路為ViTV2-V5 T

23、V6?；。╒i，V）的順流流量為6,決定了Pf=6,改進的網(wǎng)絡(luò)流量圖如圖所示:11- V160V40 、11第二次迭代 后的總流量第三次迭代 后的總流量第三次迭代：選擇路為 V嚴V4 tV6?；。╓ , V4）的順流流量為6, 決定了 Pf=6,改進的網(wǎng)絡(luò)流量圖如圖所示：V26 0 V40.第四次迭代 后的總流量第四次迭代：選擇路為 Vi- V3TV4 - V2- V5TV6?；。╒2 , V5）的順流流量 為2，決定了 Pf=2,改進的網(wǎng)絡(luò)流量圖如圖所示：V20.第五次迭代：選擇路為 Vi-V3-V4-V5-V6?；。╒1 , V3）的順流流量為3, 決定了 Pf=3,改進的網(wǎng)絡(luò)流量圖如圖所

24、示：在通過第五次迭代后在圖中已找不到從發(fā)點到收點的一條路上的每一條弧順流容量都大于零，運算停止。我們已得到此網(wǎng)絡(luò)的從 V1到 V的最大流量，最大流量為 22，也就是公路的最大流量為每小時通過22千輛車。最小費用最大流問題請求下面網(wǎng)路圖中的最小費用最大流，圖中?。╒i , Vj）的賦權(quán)（Cj ,bij），其中Cj為從Vi到Vj的流量，bij為Vi到Vj的單位流量的費用。、填空題：（每空格2分，共16分）1、線性規(guī)劃的解有唯一最優(yōu)解、無窮多最優(yōu)解、無界解和無可行解四種。2、 在求運費最少的調(diào)度運輸問題中，如果某一非基變量的檢驗數(shù)為4,則說明如果在該空格中增加一個運量運費將增加4。3、 “如果線性規(guī)

25、劃的原問題存在可行解，則其對偶問題一定存在可行解”，這句話對還是錯？錯4、如果某一整數(shù)規(guī)劃：MaxZ=Xi +X2X1+9/14X2W 51/14 -2Xi+X2< 1/3X1,X2> 0且均為整數(shù)所對應(yīng)的線性規(guī)劃（松弛問題）的最優(yōu)解為怡=32，X2=10/3，MaxZ=6/29，我們現(xiàn)在要對X1進行分枝，應(yīng)該分為 X1< 1 和 X1> 25. 在用逆向解法求動態(tài)規(guī)劃時，fk(Sk)的含義是：從第k個階段到第n個階段的最優(yōu)解。6. 假設(shè)某線性規(guī)劃的可行解的集合為D,而其所對應(yīng)的整數(shù)規(guī)劃的可行解集合為B,那么D和B的關(guān)系為D包含B7. 已知下表是制訂生產(chǎn)計劃問題的一張LP最優(yōu)單純形表(極大化問題，約束條件均為“W”型不