運(yùn)籌學(xué)填空題

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

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

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

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

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

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

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

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

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

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

11、的含義是該檢驗(yàn)數(shù)所在格單位調(diào)整量。13.運(yùn)輸問(wèn)題的初始方案中的基變量取值為正。14表上作業(yè)法中，每一次調(diào)整1個(gè)“入基變量”。 15.在編制初始方案調(diào)運(yùn)方案及調(diào)整中，如出現(xiàn)退化，則某一個(gè)或多個(gè)點(diǎn)處應(yīng)填入數(shù)字016運(yùn)輸問(wèn)題的模型中，含有的方程個(gè)數(shù)為n+M個(gè)。17表上作業(yè)法中，每一次調(diào)整，“出基變量”的個(gè)數(shù)為1個(gè)。18給出初始調(diào)運(yùn)方案的方法共有三種。19.運(yùn)輸問(wèn)題中，每一行或列若有閉回路的頂點(diǎn)，則必有兩個(gè)。第七章 整數(shù)規(guī)劃填空題1用分枝定界法求極大化的整數(shù)規(guī)劃問(wèn)題時(shí)，任何一個(gè)可行解的目標(biāo)函數(shù)值是該問(wèn)題目標(biāo)函數(shù)值的下界。2在分枝定界法中，若選Xr=43進(jìn)行分支，則構(gòu)造的約束條件應(yīng)為X11，X12。3已

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

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

14、樹(shù)問(wèn)題就是在網(wǎng)絡(luò)圖中，找出若干條邊，連接所有結(jié)點(diǎn)，而且連接的總長(zhǎng)度最小。7最小樹(shù)的算法關(guān)鍵是把最近的未接_結(jié)點(diǎn)連接到那些已接結(jié)點(diǎn)上去。8求最短路問(wèn)題的計(jì)算方法是從0fijcij開(kāi)始逐步推算的，在推算過(guò)程中需要不斷標(biāo)記平衡和最短路線。動(dòng)態(tài)規(guī)劃石油輸送管道鋪設(shè)最優(yōu)方案的選擇問(wèn)題：如圖所示，其中A為出發(fā)點(diǎn)，E為目的地，B、C、D分別為三個(gè)必須建立油泵加壓站的地區(qū)，其中的B1、B2、B3;C1、C2、C3;D1、D2分別為可供選擇的各站站點(diǎn)。圖中的線段表示管道可鋪設(shè)的位置，線段旁的數(shù)字為鋪設(shè)管線所需要的費(fèi)用，問(wèn)如何鋪設(shè)管道才使總費(fèi)用最?。?AED2D1C3C2C1B3B2 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最小生成樹(shù)問(wèn)題 某大學(xué)準(zhǔn)備對(duì)其所屬的7個(gè)學(xué)院辦公室計(jì)算機(jī)聯(lián)網(wǎng)，這個(gè)網(wǎng)絡(luò)的可能聯(lián)通的途徑如圖所示，圖中V1，V7表示7

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

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

18、按照什么路線送貨才能使送貨時(shí)間最短。下圖給出了配送中心到快餐店的交通圖，圖中V1，V7表示7個(gè)地名，其中V1表示配送中心，V7表示快餐店，點(diǎn)之間的聯(lián)線表示兩地之間的道路，邊所賦的權(quán)數(shù)表示開(kāi)車送原料通過(guò)這段道路所需要的時(shí)間（單位：分鐘）（27,5）（25,4）（24,3）（4,1）V4（16,2）（0,S）5V26V26V28V27V22V212V216V218V24V2V1V7（快餐店）（配送中心）V5V3V6V2解：給起始點(diǎn)V1標(biāo)號(hào)為（0，S） I=V1,J= V2，V3，V4，V5，V6 ,V7 ，邊的集合Vi，Vj Vi，Vj兩點(diǎn)中一點(diǎn)屬于I,而另一點(diǎn)屬于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)號(hào)的點(diǎn)V2 標(biāo)以（4，1），表示從V1 到V2 的距離為4，并且在V1到V2的最短路徑上V2的前面的點(diǎn)為V1.這時(shí)I=V1 ，V2,J=V3，V4，V5，V6 ,V7，邊的集合Vi，Vj Vi，Vj兩點(diǎn)中一點(diǎn)屬于I,而另一點(diǎn)屬于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)號(hào)的點(diǎn)V3 標(biāo)以

20、（16，2）這時(shí)I=V1 ，V2 ，V3,J=V4，V5，V6 ,V7，邊的集合Vi，Vj Vi，Vj兩點(diǎn)中一點(diǎn)屬于I,而另一點(diǎn)屬于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)號(hào)的點(diǎn)V4 標(biāo)以（18，3）這時(shí)I=V1 ，V2 ，V3 ，V4,J=V5，V6 ,V7，邊的集合Vi，Vj Vi，Vj兩點(diǎn)中一點(diǎn)屬于I,而另一點(diǎn)屬于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)號(hào)的點(diǎn)V5 標(biāo)以（24，3）這時(shí)I=V1 ，V2 ，V3 ，V4 ，V5 ,J= V6 ，V7，邊的集合Vi，Vj Vi，Vj兩點(diǎn)中一點(diǎn)屬于I,而另一點(diǎn)屬于J= V5，V7， V4，V6 ，并有S57=L5+C57=22+5=27 ；min (S57,S46)= S46 =25給邊 V4，V6中的未標(biāo)號(hào)的點(diǎn)V6 標(biāo)以（25，4）這時(shí)I=V1 ，V2 ，V3 ，V4 ，V5 ，V6 ,J= V7，邊的集合Vi，Vj Vi，Vj兩點(diǎn)中一點(diǎn)屬于I,而另一點(diǎn)屬于J=

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

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

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

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

26、555000V40564V6V5V2V1V34第五次迭代：選擇路為V1V3V4V5V6 ?；。╒1 ，V3）的順流流量為3，決定了pf=3，改進(jìn)的網(wǎng)絡(luò)流量圖如圖所示：第五次迭代后的總流量222203111523111474222088060606500V45V6V5V2V1V3在通過(guò)第五次迭代后在圖中已找不到從發(fā)點(diǎn)到收點(diǎn)的一條路上的每一條弧順流容量都大于零，運(yùn)算停止。我們已得到此網(wǎng)絡(luò)的從 V1到V6的最大流量，最大流量為22，也就是公路的最大流量為每小時(shí)通過(guò)22千輛車。最小費(fèi)用最大流問(wèn)題請(qǐng)求下面網(wǎng)路圖中的最小費(fèi)用最大流,圖中弧(Vi , Vj)的賦權(quán)（Cij , bij），其中Cij為從Vi 到Vj 的流量，bij 為Vi 到Vj 的單位流量的費(fèi)用。（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)解、無(wú)窮多最優(yōu)解、 無(wú)界解 和無(wú)可行解四種