管理運籌學復習題及參考答案-資料下載頁

　　

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