【正文】 一、填空題 1．用分枝定界法求極大化的整數(shù)規(guī)劃問(wèn)題時(shí)，任何一個(gè)可行解的目標(biāo)函數(shù)值是該問(wèn)題目標(biāo)函數(shù)值的 下界 。 2．在分枝定界法中，若選 Xr=4／ 3進(jìn)行分支，則構(gòu)造的約束條 件應(yīng)為 X1≤ 1， X1≥ 2。 3．已知整數(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+1／ 7x3+2／ 7x5=13／ 7，則以 X1行為源行的割平面方程為 _76 － 71 X3－ 72 X5≤ 0_。 8．在用割平面法求解整數(shù)規(guī)劃問(wèn)題時(shí)，要求全部變量必須都 為 整數(shù) 。 9．用割平面法求解整數(shù)規(guī)劃問(wèn)題時(shí)，若某個(gè)約束條件中有 不為整數(shù) 的系數(shù)，則需在該約束兩端擴(kuò)大適當(dāng)倍數(shù)，將 全部系數(shù) 化為整數(shù)。 10．求解純整數(shù)規(guī)劃的方法是 割平面法 。求解混合整數(shù)規(guī)劃的方法是 分枝定界法 _。 11．求解 0— 1整數(shù)規(guī)劃的方法是 隱枚舉法 。求解分配問(wèn)題的專(zhuān)門(mén)方法 是 匈牙利法 。 12．在應(yīng)用匈牙利法求解分配問(wèn)題時(shí)，最終求得的分配元 應(yīng)是 獨(dú)立零元素 _。 2個(gè) . 二、單選題 1．整數(shù)規(guī)劃問(wèn)題中，變量的取值可能是 D。 A．整數(shù) B． 0或 1C．大于零的非整數(shù) D．以上三種都可能 2．在下列整數(shù)規(guī)劃問(wèn)題中，分枝定界法和割平面法都可 以采用的是 A 。 A．純整數(shù)規(guī)劃 B．混合 整數(shù)規(guī)劃 C． 0— 1規(guī)劃 D．線性規(guī)劃 3．下列方法中用于求解分配問(wèn)題的是 D_。 A．單純形表 B．分枝定界法 C．表上作業(yè)法 D．匈 牙利法 三、多項(xiàng)選擇 1．下列說(shuō)明 不 正確的是 ABC。 A．求解整數(shù)規(guī)劃可以采用求解其相應(yīng)的松馳問(wèn)題，然后對(duì)其非整數(shù)值的解四舍五入的方法得到整數(shù)解。 B．用分枝定界法求解一個(gè)極大化的整數(shù)規(guī)劃問(wèn)題，當(dāng)?shù)玫蕉嘤谝粋€(gè)可行解時(shí)，通常任取其中一個(gè)作為下界。 C．用割平面法求解整數(shù)規(guī)劃時(shí)，構(gòu)造的割平面可能割去一些不屬于最優(yōu)解的整數(shù)解。 D．用割平面法求解整數(shù)規(guī)劃問(wèn)題時(shí)，必須首先將 原問(wèn)題的非整數(shù)的約束系數(shù)及右端常數(shù)化為整數(shù)。 2．在求解整數(shù)規(guī)劃問(wèn)題時(shí)，可能出現(xiàn)的是 ABC。 A．唯一最優(yōu)解 B．無(wú)可行解 C．多重最佳解 D．無(wú)窮多個(gè)最優(yōu)解 3．關(guān)于分配問(wèn)題的下列說(shuō)法正確的是 _ ABD。 A．分配問(wèn)題是一個(gè)高度退化的運(yùn)輸問(wèn)題 B．可以用表上作業(yè)法求解分配問(wèn)題 C．從分配問(wèn)題的效益矩陣中逐行取其最小元素，可得到最優(yōu)分配方案 D．匈牙利法所能求解的分配問(wèn)題，要求規(guī)定一個(gè)人只能完成一件工作，同時(shí)一件工作也只給一個(gè)人做。 （ CDE ） A 線性規(guī)劃 B 非線性規(guī)劃 C 純整數(shù)規(guī)劃 D 混合整數(shù)規(guī)劃 E 0— 1規(guī)劃 （ ABCDE ） A 求其松弛問(wèn)題 B 在其松弛問(wèn)題中增加一個(gè)約束方程 C 應(yīng)用單形或圖解法 D 割去部分非整數(shù)解 E多次切割 三、名詞 純整數(shù)規(guī)劃：如果要求所有的決策變量都取整數(shù)，這樣的問(wèn)題成為純整數(shù)規(guī)劃問(wèn)題。 0— 1 規(guī)劃問(wèn)題：在線性規(guī)劃問(wèn)題中，如果要求所有的決策變量只能取 0 或 1，這樣的問(wèn)題稱(chēng)為 0— 1 規(guī)劃。 混合整數(shù)規(guī)劃：在線 性規(guī)劃問(wèn)題中，如果要求部分決策變量取整數(shù)，則稱(chēng)該問(wèn)題為混合整數(shù)規(guī)劃。 四、用分枝定界法求解下列整數(shù)規(guī)劃問(wèn)題： (提示 :可采用圖解法 ) maxZ=40x1+90x2 五、用割平面法求解 六、下列整數(shù)規(guī)劃問(wèn)題 說(shuō)明能否用先求解相應(yīng)的線性規(guī)劃問(wèn)題然后四舍五入 的辦法來(lái)求得該整數(shù)規(guī)劃的一個(gè)可行解。 答： 不考慮整數(shù)約束，求解相應(yīng)線性規(guī)劃得最優(yōu)解為 x1=10/3， x2=x3=0，用四舍五人法時(shí)，令 x1=3， x2=x3=0， 其中第 2個(gè)約束無(wú)法滿足，故不可行。 七 、若某鉆井隊(duì)要從以下 10 個(gè)可供選擇的井位中確定 5 個(gè)鉆井探油。使總的鉆探費(fèi)用為最小。若 10個(gè)井位的代號(hào)為 S1,S2． ? ， S10相應(yīng)的鉆探費(fèi)用為 C1 ,C2 ,? C10，并且井位選 擇要滿足下列限制條件： (1)在 s1， s2， S4中至多只能選擇兩個(gè)； (2)在 S5， s6中至少選擇一個(gè)； (3)在 s3， s6，S7， S8中至少選擇兩個(gè)； 試建立這個(gè)問(wèn)題的整數(shù)規(guī)劃模型 八 、有四項(xiàng)工作要甲、乙、丙、丁四個(gè)人去完成．每項(xiàng)工作 只允許一人去完成。每個(gè)人只完成其中一項(xiàng)工作，已知每個(gè)人完成各項(xiàng)工作的時(shí)間如下表。問(wèn)應(yīng)指派每個(gè)人完成哪項(xiàng)工作，使總的消耗時(shí)間最少 ? 工作 人 I Ⅱ Ⅲ Ⅳ 甲 乙 丙 丁 15 19 6 19 18 23 7 21 2l 22 16 23 24 18 19 17 第八章 圖與網(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．最小樹(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ì)算方法是從 0≤ fij≤ cij 開(kāi)始逐步推算的，在推算過(guò)程中需要不斷標(biāo)記 平衡 和最短路線。 二、單選題 關(guān)于圖論中圖的概念，以下敘述 (B)正確。 A圖中的有向邊表示研究對(duì)象，結(jié)點(diǎn)表示銜接關(guān)系。 B圖中的點(diǎn)表示研究對(duì)象，邊表示點(diǎn)與點(diǎn)之間的關(guān)系。 C圖中任意兩點(diǎn)之間必有邊。 D圖的邊數(shù)必定等于點(diǎn)數(shù)減 1。 2．關(guān)于樹(shù)的概念，以下敘述 (B)正確。 A 樹(shù)中的點(diǎn)數(shù)等于邊數(shù)減 1 B 連通無(wú)圈的圖必定是樹(shù) C 含 n 個(gè)點(diǎn)的樹(shù)是唯 一的 D任一樹(shù)中，去掉一條邊仍為樹(shù)。 3．一個(gè)連通圖中的最小樹(shù) (B)，其權(quán) (A)。 A是唯一確定的 B可能不唯一 C可能不存在 D一定有多個(gè)。 4．關(guān)于最大流量問(wèn)題，以下敘述 (D)正確。 A一個(gè)容量網(wǎng)絡(luò)的最大流是唯一確定的 B達(dá)到最大流的方案是唯一的 C當(dāng)用標(biāo)號(hào)法求最大流時(shí)，可能得到不同的最大流方案 D當(dāng)最大流方案不唯一時(shí)，得到的最大流量亦可能不相同。 5．圖論中的圖，以下敘述 (C)不 正確。 A．圖論中點(diǎn)表示研究對(duì)象，邊或有向邊表示研究 對(duì)象之間 的特定關(guān)系。 B．圖論中的圖，用點(diǎn)與點(diǎn)的相互位置，邊的長(zhǎng)短曲直來(lái)表示研究對(duì)象的相互關(guān)系。 C．圖論中的邊表示研究對(duì)象，點(diǎn)表示研究對(duì)象之間的特定關(guān)系。 D．圖論中的圖，可以改變點(diǎn)與點(diǎn)的相互位置。只要不改變點(diǎn)與點(diǎn)的連接關(guān)系。 6．關(guān)于最 小樹(shù)，以下敘述 (B)正確。 A．最小樹(shù)是一個(gè)網(wǎng)絡(luò)中連通所有點(diǎn)而邊數(shù)最少的圖 B．最小樹(shù)是一個(gè)網(wǎng)絡(luò)中連通所有的點(diǎn)，而權(quán)數(shù)最少的圖 C．一個(gè)網(wǎng)絡(luò)中的最大權(quán)邊必不包含在其最小樹(shù)內(nèi) D．一個(gè)網(wǎng)絡(luò)的最小樹(shù)一般是不唯一的。 7．關(guān)于可行流，以下敘述 (A)不 正確。 A．可行流的流量大于零 而小于容量限制條件 B．在網(wǎng)絡(luò)的任一中間點(diǎn)，可行流滿足流人量 =流出量。 C．各條有向邊上的流量均為零的流是一個(gè)可行流 D．可行流的流量小于容量限制條件而大于或等于零。 三、多選題 1．關(guān)于圖論中圖的概念，以下敘述 (123)正確。 (1)圖中的邊可以 是有向邊，也可以是無(wú)向邊 (2)圖中的各條邊上可以標(biāo)注權(quán)。 (3)結(jié)點(diǎn)數(shù)等于邊數(shù)的連通圖必含圈 (4)結(jié)點(diǎn)數(shù)等于邊數(shù)的圖必連通。 2．關(guān)于樹(shù)的概念，以下敘述 (123)正確。 1)樹(shù)中的邊數(shù)等于點(diǎn)數(shù)減 1(2)樹(shù)中再添一條邊后必含圈。 (3)樹(shù)中刪去一條邊后必不連通 (4)樹(shù)中兩點(diǎn)之間的通路可能不唯一。 3．從連通圖中生成樹(shù)，以下敘述 (134)正確。 (1)任一連通圖必有支撐樹(shù) (2)任一連通圖生成的支撐樹(shù)必唯一 (3)在支撐樹(shù)中再增加一條邊后必含圈 (4)任一連通圖生成的各個(gè)支撐樹(shù)其邊數(shù)必相同 4．在下圖中， (abcd)不是根據(jù) (a)生成的支撐樹(shù)。 5．從賦權(quán)連通圖中生成最小樹(shù)，以下敘述 (124)不正確。 (1)任一連通圖生成的各個(gè)最小樹(shù)，其總長(zhǎng)度必相等 (2)任一連通圖生成的各個(gè)最小樹(shù)，其邊數(shù)必相等。 (3)任一連通圖中具有最小權(quán)的邊必包含在生成 的最小樹(shù)上。 (4)最小樹(shù)中可能包括連通圖中的最大權(quán)邊。 6．從起點(diǎn)到終點(diǎn)的最短路線，以下敘述 (123)不 正確。 1)從起點(diǎn)出發(fā)的最小權(quán)有向邊必含在最短路線中。 (2)整個(gè)圖中權(quán)最小的有向邊必包含在最短路線中。 (3)整個(gè)圖中權(quán)最大的有向邊可能含在最短路線中 (4)從起點(diǎn)到終點(diǎn)的最短路線是唯一的。 7．關(guān)于帶收發(fā)點(diǎn)的容量網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)的一條增廣路，以下敘述 ( 123)不 正確。 (1)增廣路上的有向邊的方向必須是從發(fā)點(diǎn)指向收點(diǎn)的 (2)增廣路上的有向邊，必須 都是不飽和邊 (3)增廣路上 不能有零流邊 (4)增廣路上與發(fā)點(diǎn)到收點(diǎn)方向一致的有向邊不能是飽和邊，相反方向的有向邊不能是零流邊 8．關(guān)于樹(shù)，以下敘述 (ABCE)正確。 A．樹(shù)是連通、無(wú)圈的圖 B．任一樹(shù)，添加一條邊便含圈 C．任一樹(shù)的邊數(shù)等于點(diǎn)數(shù)減 1。D．任一樹(shù)的點(diǎn)數(shù)等于邊數(shù)減 1E．任一樹(shù)，去掉 _條邊便不連通。 9．關(guān)于最短路，以下敘述 (ACDE)不正確。 A 從起點(diǎn)出發(fā)到終點(diǎn)的最短路是唯一的。 B．從起點(diǎn)出發(fā)到終點(diǎn)的最短路不一定是唯 一的，但其最短路線的長(zhǎng)度是確定的。 C．從起點(diǎn)出發(fā)的有向邊中的最小權(quán)邊，一定 包含在起點(diǎn)到 終點(diǎn) 的最短路上 D．從起點(diǎn)出發(fā)的有向邊中的最大權(quán)邊，一定不包含在起點(diǎn)到終點(diǎn)的最短路上。 E．整個(gè)網(wǎng)絡(luò)的最大權(quán)邊的一定不包含在從起點(diǎn)到終點(diǎn)的最短路線上。 10．關(guān)于增廣路，以下敘述 (BC )正確。 A．增廣路是一條從發(fā)點(diǎn)到收點(diǎn)的有向路，這條路上各條邊的方向必一致。 B．增廣路是一條從發(fā)點(diǎn)到收點(diǎn)的有向路，這條路上各條邊的方向可不一致。 C．增廣路上與發(fā)點(diǎn)到收點(diǎn)方向一致的邊必須是非飽和邊，方向相反的邊必須是流量大于零的邊。 D．增廣路上與發(fā)點(diǎn)到收點(diǎn)方向一致的邊必須是流量小于容量的邊，方向相反的邊必須是流量等于零的邊 。 E．增廣路上與發(fā)點(diǎn)到收點(diǎn)方向一致的邊必須是流量為零的邊，方向相反的邊必須是流量大于零的邊。 四、名詞解釋 樹(shù) :在圖論中， 具有 連通 和 不含圈 特點(diǎn)的圖稱(chēng)為樹(shù)。 2． 權(quán)： 在圖中， 邊 旁標(biāo)注的數(shù)字稱(chēng)為 權(quán) 。 3． 網(wǎng)絡(luò)： 在圖論中，給邊或有向邊賦了權(quán)的圖稱(chēng)為 網(wǎng)絡(luò) 4．最大流問(wèn)題 ： 最大流問(wèn)題是指在網(wǎng)絡(luò)圖中，在單位時(shí)間內(nèi)，從 發(fā) 點(diǎn)到 收 點(diǎn)的最大流量 5．最大流問(wèn)題中流量 ： 最大流問(wèn)題中流量是指單位時(shí)間的發(fā)點(diǎn)的 流出 量或收點(diǎn)的 流入 量。 6． 容量： 最大流問(wèn)題中，每條有向邊單位時(shí)間的最大通過(guò)能力稱(chēng)為 容量 7． 飽合 邊 ： 容量與流量相等的有向邊稱(chēng)為 飽合 邊。 8零流 邊 ： 流量為零的有向邊稱(chēng)為 零流 邊 ：若樹(shù) T 是無(wú)向圖 G 的生成樹(shù)，則稱(chēng) T 是 G 的生成樹(shù)。 .。 10 根：有向圖 G 中可以到達(dá)圖中任一頂點(diǎn)的頂點(diǎn) u 稱(chēng)為 G 的根。 11 枝：樹(shù)中的邊稱(chēng)為枝。 ：具有相同端點(diǎn)的邊叫平行邊。 13 根樹(shù)：若有向圖 G 有根 u，且它的基本圖是一棵樹(shù)，則稱(chēng) G 為以 u 為根的根樹(shù)。 四、計(jì)算題 1．下圖是 6 個(gè)城市的交通圖，為將部分道路改造成高速 公路，使各個(gè)城市均能通達(dá)，又要使高速公路的總長(zhǎng)度最小，應(yīng)如 何做 ?最小的總長(zhǎng)度是多少 ? 2．對(duì)下面的兩個(gè)連通圖，試分別求出最小樹(shù)。 第 1題中的交通圖，求城市 A到 D沿公路走的最短 路的路長(zhǎng)及路徑。 4．對(duì)下面兩圖，試分別求出從起點(diǎn)到終點(diǎn)的最短路線。 5．分別