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