運籌學(xué)填空題

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

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

3、若化為標(biāo)準(zhǔn)形式，需要引入一松弛變量。19.如果某個變量Xj為自由變量，則應(yīng)引進兩個非負(fù)變量Xj , Xj, 同時令XjXj Xj。20.表達線性規(guī)劃的簡式中目標(biāo)函數(shù)為max(min)Z=cijxij。第三章 線性規(guī)劃的基本方法填空題1線性規(guī)劃的代數(shù)解法主要利用了代數(shù)消去法的原理，實現(xiàn)基可行解的轉(zhuǎn)換，尋找最優(yōu)解。2標(biāo)準(zhǔn)形線性規(guī)劃典式的目標(biāo)函數(shù)的矩陣形式是_ maxZ=CBB1b+(CNCBB1N)XN 。3對于目標(biāo)函數(shù)極大值型的線性規(guī)劃問題，用單純型法求解 時，當(dāng)基變量檢驗數(shù)j_0時，當(dāng)前解為最優(yōu)解。4用大M法求目標(biāo)函數(shù)為極大值的線性規(guī)劃問題時，引入的人工變量在目標(biāo)函數(shù)中的系數(shù)應(yīng)為M。5在單純形

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

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

6、相應(yīng)的目標(biāo)函數(shù)值將增加3k 。7線性規(guī)劃問題的最優(yōu)基為B，基變量的目標(biāo)系數(shù)為CB，則其對偶問題的最優(yōu)解Y= CBB1。8若X和Y分別是線性規(guī)劃的原問題和對偶問題的最優(yōu)解，則有CX= Yb。9若X、Y分別是線性規(guī)劃的原問題和對偶問題的可行解，則有CXYb。10若X和Y分別是線性規(guī)劃的原問題和對偶問題的最優(yōu)解，則有CX=Y*b。 11設(shè)線性規(guī)劃的原問題為maxZ=CX，Axb，X0，則其對偶問題為min=Yb YAcY0_。 12影子價格實際上是與原問題各約束條件相聯(lián)系的對偶變量的數(shù)量表現(xiàn)。 13線性規(guī)劃的原問題的約束條件系數(shù)矩陣為A，則其對偶問題的約束條件系數(shù)矩陣為AT 。 14在對偶單純形法迭

7、代中，若某bi<0，且所有的aij0(j=1，2，n)，則原問題_無解。第五章 線性規(guī)劃的靈敏度分析填空題1、靈敏度分析研究的是線性規(guī)劃模型的原始、最優(yōu)解數(shù)據(jù)變化對產(chǎn)生的影響。2、在線性規(guī)劃的靈敏度分析中，我們主要用到的性質(zhì)是_可行性，正則性。3在靈敏度分析中，某個非基變量的目標(biāo)系數(shù)的改變，將引起該非基變量自身的檢驗數(shù)的變化。4如果某基變量的目標(biāo)系數(shù)的變化范圍超過其靈敏度分析容許的變化范圍，則此基變量應(yīng)出基。5約束常數(shù)b；的變化，不會引起解的正則性的變化。6在某線性規(guī)劃問題中，已知某資源的影子價格為Y1，相應(yīng)的約束常數(shù)b1，在靈敏度容許變動范圍內(nèi)發(fā)生b1的變化，則新的最優(yōu)解對應(yīng)的最優(yōu)目標(biāo)

8、函數(shù)值是Z*+yib (設(shè)原最優(yōu)目標(biāo)函數(shù)值為Z)7若某約束常數(shù)bi的變化超過其容許變動范圍，為求得新的最優(yōu)解，需在原最優(yōu)單純形表的基礎(chǔ)上運用對偶單純形法求解。8已知線性規(guī)劃問題，最優(yōu)基為B，目標(biāo)系數(shù)為CB，若新增變量xt，目標(biāo)系數(shù)為ct，系數(shù)列向量為Pt，則當(dāng)CtCBB1Pt時，xt不能進入基底。9如果線性規(guī)劃的原問題增加一個約束條件，相當(dāng)于其對偶問題增加一個變量。10、若某線性規(guī)劃問題增加一個新的約束條件，在其最優(yōu)單純形表中將表現(xiàn)為增加一行，一列。11線性規(guī)劃靈敏度分析應(yīng)在最優(yōu)單純形表的基礎(chǔ)上，分析系數(shù)變化對最優(yōu)解產(chǎn)生的影響12在某生產(chǎn)規(guī)劃問題的線性規(guī)劃模型中，變量xj的目標(biāo)系數(shù)Cj代表該變

9、量所對應(yīng)的產(chǎn)品的利潤，則當(dāng)某一非基變量的目標(biāo)系數(shù)發(fā)生增大變化時，其有可能進入基底。第六章 物資調(diào)運規(guī)劃運輸問題填空題1 物資調(diào)運問題中，有m個供應(yīng)地，Al，A2，Am，Aj的供應(yīng)量為ai(i=1，2，m)，n個需求地B1，B2，Bn，B的需求量為bj(j=1，2，n)，則供需平衡條件為 =2物資調(diào)運方案的最優(yōu)性判別準(zhǔn)則是：當(dāng)全部檢驗數(shù)非負(fù)時，當(dāng)前的方案一定是最優(yōu)方案。3可以作為表上作業(yè)法的初始調(diào)運方案的填有數(shù)字的方格數(shù)應(yīng)為m+n1個(設(shè)問題中含有m個供應(yīng)地和n個需求地)4若調(diào)運方案中的某一空格的檢驗數(shù)為1，則在該空格的閉回路上調(diào)整單位運置而使運費增加1。5調(diào)運方案的調(diào)整是要在檢驗數(shù)出現(xiàn)負(fù)值的點

10、為頂點所對應(yīng)的閉回路內(nèi)進行運量的調(diào)整。6按照表上作業(yè)法給出的初始調(diào)運方案，從每一空格出發(fā)可以找到且僅能找到_1條閉回路7在運輸問題中，單位運價為Cij位勢分別用ui，Vj表示，則在基變量處有cij Cij=ui+Vj 。8、供大于求的、供不應(yīng)求的不平衡運輸問題，分別是指_的運輸問題、_的運輸問題。10在表上作業(yè)法所得到的調(diào)運方案中，從某空格出發(fā)的閉回路的轉(zhuǎn)角點所對應(yīng)的變量必為基變量。 11在某運輸問題的調(diào)運方案中，點(2，2)的檢驗數(shù)為負(fù)值，(調(diào)運方案為表所示)則相應(yīng)的調(diào)整量應(yīng)為300_。IA300100300B400C60030012.若某運輸問題初始方案的檢驗數(shù)中只有一個負(fù)值：2，則這個2

11、的含義是該檢驗數(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ù)為1個。18給出初始調(diào)運方案的方法共有三種。19.運輸問題中，每一行或列若有閉回路的頂點，則必有兩個。第七章 整數(shù)規(guī)劃填空題1用分枝定界法求極大化的整數(shù)規(guī)劃問題時，任何一個可行解的目標(biāo)函數(shù)值是該問題目標(biāo)函數(shù)值的下界。2在分枝定界法中，若選Xr=43進行分支，則構(gòu)造的約束條件應(yīng)為X11，X12。3已

12、知整數(shù)規(guī)劃問題P0，其相應(yīng)的松馳問題記為P0，若問題P0無可行解，則問題P。無可行解。4在0 - 1整數(shù)規(guī)劃中變量的取值可能是_0或1。5對于一個有n項任務(wù)需要有n個人去完成的分配問題，其 解中取值為1的變量數(shù)為n個。6分枝定界法和割平面法的基礎(chǔ)都是用_線性規(guī)劃方法求解整數(shù)規(guī)劃。7若在對某整數(shù)規(guī)劃問題的松馳問題進行求解時，得到最優(yōu)單純形表中，由X。所在行得X1+17x3+27x5=137，則以X1行為源行的割平面方程為_X3X50_。8在用割平面法求解整數(shù)規(guī)劃問題時，要求全部變量必須都為整數(shù)。9用割平面法求解整數(shù)規(guī)劃問題時，若某個約束條件中有不為整數(shù)的系數(shù)，則需在該約束兩端擴大適當(dāng)倍數(shù)，將全部

13、系數(shù)化為整數(shù)。10求解純整數(shù)規(guī)劃的方法是割平面法。求解混合整數(shù)規(guī)劃的方法是分枝定界法_。11求解01整數(shù)規(guī)劃的方法是隱枚舉法。求解分配問題的專門方法是匈牙利法。 12在應(yīng)用匈牙利法求解分配問題時，最終求得的分配元應(yīng)是獨立零元素_。13.分枝定界法一般每次分枝數(shù)量為2個.第八章 圖與網(wǎng)絡(luò)分析填空題1圖的最基本要素是點、點與點之間構(gòu)成的邊 2在圖論中，通常用點表示，用邊或有向邊表示研究對象，以及研究對象之間具有特定關(guān)系。3在圖論中，通常用點表示研究對象，用邊或有向邊表示研究對象之間具有某種特定的關(guān)系。4在圖論中，圖是反映研究對象_之間_特定關(guān)系的一種工具。5任一樹中的邊數(shù)必定是它的點數(shù)減1。6最小

14、樹問題就是在網(wǎng)絡(luò)圖中，找出若干條邊，連接所有結(jié)點，而且連接的總長度最小。7最小樹的算法關(guān)鍵是把最近的未接_結(jié)點連接到那些已接結(jié)點上去。8求最短路問題的計算方法是從0fijcij開始逐步推算的，在推算過程中需要不斷標(biāo)記平衡和最短路線。動態(tài)規(guī)劃石油輸送管道鋪設(shè)最優(yōu)方案的選擇問題：如圖所示，其中A為出發(fā)點，E為目的地，B、C、D分別為三個必須建立油泵加壓站的地區(qū)，其中的B1、B2、B3;C1、C2、C3;D1、D2分別為可供選擇的各站站點。圖中的線段表示管道可鋪設(shè)的位置，線段旁的數(shù)字為鋪設(shè)管線所需要的費用，問如何鋪設(shè)管道才使總費用最??？3AED2D1C3C2C1B3B2 B1 6 2 55 3 23

15、 3 4 5 7 4 4 4 4 1 5 4 5 解：第四階段：D1E 3；D2E 4；第三階段：C1D1E 5；C2D2E 8；C3D1E 8；C3D2E 8；第二階段：B1C1D1E 11；B1C2D2E 11；B2C1D1E 8； B3C1D1E 9 ；B3C2D2E 9；第一階段：AB1C1D1E 14；AB1C2D2E 14； AB2C1D1E 13；AB3C1D1E 13；AB3C2D2E 13；最優(yōu)解：AB2C1D1E；AB3C1D1E；AB3C2D2E最優(yōu)值：13最小生成樹問題 某大學(xué)準(zhǔn)備對其所屬的7個學(xué)院辦公室計算機聯(lián)網(wǎng)，這個網(wǎng)絡(luò)的可能聯(lián)通的途徑如圖所示，圖中V1，V7表示7

16、個學(xué)院辦公室，圖中的邊為可能聯(lián)網(wǎng)的途徑，邊上的所賦權(quán)數(shù)為這條路線的長度，單位為百米。請設(shè)計一個網(wǎng)絡(luò)能聯(lián)通7個學(xué)院辦公室，并使總的線路長度為最短。584723431031V7V4V5V6V1V2V3G 5847234331V7V4V5V6V1V2V3G1 解：在G中找到一個圈（V1，V7，V6，V1）,并知在此圈上邊V1，V6的權(quán)數(shù)10為最大，在G中去掉邊V1，V6得圖G1 ，如上圖所示 5472343131V7V4V5V6V1V2V3G2 472343131V7V4V5V6V1V2V3G3 在G1中找到一個圈（V3，V4，V5，V7，V3），去掉其中權(quán)數(shù)最大的邊 V4，V5，得圖G2 ，如上圖

17、所示在G2中找到一個圈（V2，V3，V5，V7，V2），去掉其中權(quán)數(shù)最大的邊 V5，V7，得圖G3 ，如上圖所示72343131V7V4V5V6V1V2V3G47233131V7V4V5V6V1V2V3G5在G3中找到一個圈（V3，V5，V6，V7，V3），去掉其中權(quán)數(shù)最大的邊 V5，V6，得圖G4 ，如上圖所示在G4中找到一個圈（V2，V3， V7，V2），去掉其中權(quán)數(shù)最大的邊 V3，V7，得圖G5 ，如上圖所示在G5中已找不到任何一個圈了，可知G5即為圖G的最小生成樹。這個最小生成樹的所有邊的總權(quán)數(shù)為3+3+3+1+2+7=19（18,3）(13)某一個配送中心要給一個快餐店送快餐原料，應(yīng)

18、按照什么路線送貨才能使送貨時間最短。下圖給出了配送中心到快餐店的交通圖，圖中V1，V7表示7個地名，其中V1表示配送中心，V7表示快餐店，點之間的聯(lián)線表示兩地之間的道路，邊所賦的權(quán)數(shù)表示開車送原料通過這段道路所需要的時間（單位：分鐘）（27,5）（25,4）（24,3）（4,1）V4（16,2）（0,S）5V26V26V28V27V22V212V216V218V24V2V1V7（快餐店）（配送中心）V5V3V6V2解：給起始點V1標(biāo)號為（0，S） I=V1,J= V2，V3，V4，V5，V6 ,V7 ，邊的集合Vi，Vj Vi，Vj兩點中一點屬于I,而另一點屬于J= V1，V2， V1，V3，

19、并有 S12=L1+C12=0+4=4 ； S13=L1+C13=0+18=18min (S12,S13)= S12 =4給邊 V1，V2中的未標(biāo)號的點V2 標(biāo)以（4，1），表示從V1 到V2 的距離為4，并且在V1到V2的最短路徑上V2的前面的點為V1.這時I=V1 ，V2,J=V3，V4，V5，V6 ,V7，邊的集合Vi，Vj Vi，Vj兩點中一點屬于I,而另一點屬于J= V1，V3， V2，V3， V2，V4，并有S23=L2+C23=4+12=16 ；S24=L2+C24=4+16=20 ；min (S23,S24 , S13)= S23 =16給邊 V2，V3中的未標(biāo)號的點V3 標(biāo)以

20、（16，2）這時I=V1 ，V2 ，V3,J=V4，V5，V6 ,V7，邊的集合Vi，Vj Vi，Vj兩點中一點屬于I,而另一點屬于J= V2，V4， V3，V4， V3，V5，并有S34=L3+C34=16+2=18 ； S35=L3+C35=16+6=22 ； S24=L2+C24=4+16=20min (S34,S35,S24)= S34 =18給邊 V3，V4中的未標(biāo)號的點V4 標(biāo)以（18，3）這時I=V1 ，V2 ，V3 ，V4,J=V5，V6 ,V7，邊的集合Vi，Vj Vi，Vj兩點中一點屬于I,而另一點屬于J= V4，V6， V4，V5， V3，V5，并有S46=L4+C46=

21、18+7=25 ； S45=L4+C45=18+8=26 ；min (S46,S45 ,S35)= S35 =24給邊 V3，V5中的未標(biāo)號的點V5 標(biāo)以（24，3）這時I=V1 ，V2 ，V3 ，V4 ，V5 ,J= V6 ，V7，邊的集合Vi，Vj Vi，Vj兩點中一點屬于I,而另一點屬于J= V5，V7， V4，V6 ，并有S57=L5+C57=22+5=27 ；min (S57,S46)= S46 =25給邊 V4，V6中的未標(biāo)號的點V6 標(biāo)以（25，4）這時I=V1 ，V2 ，V3 ，V4 ，V5 ，V6 ,J= V7，邊的集合Vi，Vj Vi，Vj兩點中一點屬于I,而另一點屬于J=

22、 V5，V7， V6，V7 ，并有S67=L6+C67=25+6=31 ；min (S57,S67)= S57 =27給邊 V5，V7中的未標(biāo)號的點V7 標(biāo)以（27，5）此時I=V1 ，V2 ，V3 ，V4 ，V5 ，V6 ，V7,J=空集，邊集合Vi，Vj Vi，Vj兩點中一點屬于I,而另一點屬于J=空集，計算結(jié)束。得到最短路。從V7 的標(biāo)號可知從V1 到V7 的最短時間為27分鐘。 即：配送路線為： V1 V2 V3 V5 V7最小生成樹問題某電力公司要沿道路為8個居民點架設(shè)輸電網(wǎng)絡(luò)，連接8個居民點的道路圖如圖所示，其中V1，V8表示8個居民點，圖中的邊表示可架設(shè)輸電網(wǎng)絡(luò)的道路，邊上的賦權(quán)

23、數(shù)為這條道路的長度，單位為公里，請設(shè)計一個輸電網(wǎng)絡(luò)，聯(lián)通這8個居民點，并使總的輸電線路長度為最短 。275623432524V8V7V6V5V4V3V1V2G在圖中找到一個圈（V1，V2，V5，V3）,并知在此圈上邊V1，V2和V3，V5的權(quán)數(shù)4為最大，在圖中去掉邊V1，V2 ；在圖中找到一個圈（V3，V4，V8 ，V5 ，V3, V1），去掉其中權(quán)數(shù)最大的邊 V4，V8；在圖中找到一個圈（V3，V4， V5，V3），去掉其中權(quán)數(shù)最大的邊 V4，V5；在圖中找到一個圈（V5，V2，V6，V7 ，V5），去掉其中權(quán)數(shù)最大的邊 V2，V6；在圖中找到一個圈（V5，V7， V8，V5），去掉其中權(quán)數(shù)

24、最大的邊 V5，V8。在圖中已找不到任何一個圈了，可知此即為圖G的最小生成樹。這個最小生成樹的所有邊的總權(quán)數(shù)為2+2+4+2+3+3+2=18最大流問題某地區(qū)的公路網(wǎng)如圖所示，圖中V1，V6為地點，邊為公路，邊上所賦的權(quán)數(shù)為該段公路的流量（單位為千輛/小時），請求出V1 到V6 的最大流量。 65125641066V6V5V2V4V1V38 解：第一次迭代：選擇路為V1 V3 V6 ?；。╒3 ，V6）的順流流量為5，決定了pf=5，改進的網(wǎng)絡(luò)流量圖如圖所示：第一次迭代后的總流量55555000000V4000065125641066V6V5V2V1V380第二次迭代：選擇路為V1 V2 V5

25、 V6 ?；。╒1 ，V2）的順流流量為6，決定了pf=6，改進的網(wǎng)絡(luò)流量圖如圖所示：第二次迭代后的總流量111106266655500000V40006512 6466V6V5V2V1V380第三次迭代：選擇路為V1V4 V6 。?。╒1 ，V4）的順流流量為6，決定了pf=6，改進的網(wǎng)絡(luò)流量圖如圖所示：第三次迭代后的總流量171706060626665550000V40065646V6V5V2V1V3第四次迭代：選擇路為V1V3V4 V2V5V6 ?；。╒2 ，V5）的順流流量為2，決定了pf=2，改進的網(wǎng)絡(luò)流量圖如圖所示：第四次迭代后的總流量19193742220880606062666

26、555000V40564V6V5V2V1V34第五次迭代：選擇路為V1V3V4V5V6 。?。╒1 ，V3）的順流流量為3，決定了pf=3，改進的網(wǎng)絡(luò)流量圖如圖所示：第五次迭代后的總流量222203111523111474222088060606500V45V6V5V2V1V3在通過第五次迭代后在圖中已找不到從發(fā)點到收點的一條路上的每一條弧順流容量都大于零，運算停止。我們已得到此網(wǎng)絡(luò)的從 V1到V6的最大流量，最大流量為22，也就是公路的最大流量為每小時通過22千輛車。最小費用最大流問題請求下面網(wǎng)路圖中的最小費用最大流,圖中弧(Vi , Vj)的賦權(quán)（Cij , bij），其中Cij為從Vi 到Vj 的流量，bij 為Vi 到Vj 的單位流量的費用。（5，2）（1，2）（2，4）（1，1）（3，3）（4，1）（5，3）（2，4）V6V5V4V3V2V1（1，2）一、填空題：（每空格2分，共16分）1、線性規(guī)劃的解有唯一最優(yōu)解、無窮多最優(yōu)解、 無界解 和無可行解四種