【正文】 元。 五、給出線性規(guī)劃問題 用單純形表求解得單純形表如下，試分析下列各種條件 變化下最優(yōu)解 (基 )的變化： xl x2 x3 x4 x5 xB Z 8 0 0 3 5 1 xl x2 1 2 1 0 1 4 1 0 1 2 1 1 (1)分別確定目標(biāo)函數(shù)中變量 X1和 X2的系數(shù) C1， c2在什么范圍內(nèi)變動時(shí)最優(yōu)解不變； (2)目 標(biāo) 函 數(shù) 中 變 量 X3 的 系 數(shù) 變 為 6 ； (3) 增添新的約束 X1+2x2+x3≤4 解： (1)3/4≤ C1≤ 3 2≤ C2≤ 8 (2)X*=(2， 0， 1， 0， 0， 0)T Z*=10 (3)X*=(2， 1， 0， 0， 1， 0)T Z*=7 (4)X*=(0， 2， 0， 0， 0， 1/3)T Z*=25/3 第六章 物資調(diào)運(yùn)規(guī)劃運(yùn)輸問題 一、填空題 1． 物資調(diào)運(yùn)問題中，有 m 個(gè)供應(yīng)地， Al， A2? ， Am， Aj 的供應(yīng)量為 ai(i=1， 2? ， m)， n個(gè)需求地 B1， B2， ?B n， B的需求量為 bj(j=1， 2， ? ， n)，則 供需平衡條件為 ??mi ia1=??nj ib1 2．物資調(diào)運(yùn)方案的最優(yōu)性判別準(zhǔn)則是：當(dāng)全部檢驗(yàn)數(shù) 非負(fù) 時(shí)，當(dāng)前的方案一定是最優(yōu)方案。 5．調(diào)運(yùn)方案的調(diào)整是要在檢驗(yàn)數(shù)出現(xiàn) 負(fù)值 的點(diǎn)為頂點(diǎn)所對應(yīng)的 閉回路 內(nèi)進(jìn)行運(yùn)量的調(diào)整。 供大于求的 、 供不應(yīng)求的不平衡運(yùn)輸問題， 分別 是指 ??mi ia1_＞ ??nj ib1的運(yùn) 輸問題 、 ??mi ia1_＜ ??nj ib1的運(yùn) 輸問題。 11．在某運(yùn)輸問題的調(diào)運(yùn)方 案 中，點(diǎn) (2， 2)的檢驗(yàn)數(shù)為負(fù) 值， (調(diào)運(yùn)方案為表所示 )則相應(yīng)的調(diào)整量應(yīng)為 300_。 正 。 ，如出現(xiàn)退化，則某一個(gè)或多個(gè)點(diǎn)處應(yīng)填入 數(shù)字 0 16 運(yùn)輸問題的模型中，含有的方程個(gè)數(shù)為 n+M個(gè)。 18 給出初始調(diào)運(yùn)方案的方法共有 三種 。 二、單選題 在運(yùn)輸問題中，可以作為表上作業(yè)法的初始基可行解 的調(diào)運(yùn)方案應(yīng)滿足的條件是 D。 A．發(fā)生變化 B．不發(fā)生變化 C． A、 B都有可能 3．在表上作業(yè)法求解運(yùn)輸問題中，非基變量的檢驗(yàn)數(shù) D。 A 任意值 B最大值 C絕對值最大 D絕對值最小 ，因而初始調(diào)運(yùn)方案的給出就相當(dāng)于找到一個(gè) C A 基 B 可行解 C 初始基本可行解 D最優(yōu)解 15 平衡運(yùn)輸問題即是指 m個(gè)供應(yīng)地的總供應(yīng)量 D n個(gè)需求地的總需求量。 A、 惟一最優(yōu)解 B．無窮多最優(yōu)解 C．退化解 D．無可行解 2．下列說法正確的是 ABD。 A．仍然可以應(yīng)用表上作業(yè)法求解 B．在應(yīng)用表上作業(yè)法之前，應(yīng)將其轉(zhuǎn)化為平衡的運(yùn)輸問題 C．可以虛設(shè)一個(gè)需求地點(diǎn)，令其需求量為供應(yīng)量與需求量之差。 D．令虛設(shè)的需求地點(diǎn)與各供應(yīng) 地之間運(yùn)價(jià)為 M(M為極大的正數(shù) ) E. 可以虛設(shè)一個(gè) 庫存 ，令其 庫存 量為 0 三、判斷表 (a)(b)(c)中給出的調(diào)運(yùn)方案能否作為表上作 業(yè)法求解時(shí)的初始解，為什么 ? (a) Bl B2 B3 B4 B5 B6 產(chǎn)量 Al 20 10 30 A2 30 20 50 A3 10 10 50 5 75 A4 20 20 銷量 20 40 30 10 50 25 (b) (c) Bl B2 B3 B4 B5 B6 產(chǎn)量 Bl B2 B3 B4 產(chǎn)量 Al 30 30 Al 6 5 11 A2 20 30 50 A2 5 4 2 11 A3 10 30 10 25 75 A3 5 3 8 A4 20 20 銷量 5 9 9 7 銷量 20 40 30 10 50 25 (a)可作為初始方案； (b)中填有數(shù)字的方格數(shù)少于 9(產(chǎn)地?cái)?shù) +銷地?cái)?shù)－ 1)，不能作為初始方案； (c)中存在以非零元素為頂點(diǎn)的閉回路，不能作為初始方案 四、已知某運(yùn)輸問題的產(chǎn)銷平衡表。也說明理由。 七、名詞 平衡運(yùn)輸問題： m 個(gè)供應(yīng)地的供應(yīng)量等于 n 個(gè)需求地的總需求量，這樣的運(yùn)輸問題稱平衡運(yùn)輸問題。 第七章 整數(shù)規(guī)劃 一、填空題 1．用分枝定界法求極大化的整數(shù)規(guī)劃問題時(shí)，任何一個(gè)可行解的目標(biāo)函數(shù)值是該問題目標(biāo)函數(shù)值的 下界 。 3．已知整數(shù)規(guī)劃問題 P0，其相應(yīng)的松馳問題記為 P0’ ，若問題 P0’ 無可行解，則問題 P。 4．在 0 1整數(shù)規(guī)劃中變量的取值可能是 _0 或 1。 6．分枝定界法和割平面法的基礎(chǔ)都是用 _線性規(guī)劃 方法求解整數(shù)規(guī) 劃。所在行得 X1+1／ 7x3+2／ 7x5=13／ 7，則以 X1行為源行的割平面方程為 _76 － 71 X3－ 72 X5≤ 0_。 9．用割平面法求解整數(shù)規(guī)劃問題時(shí)，若某個(gè)約束條件中有 不為整數(shù) 的系數(shù)，則需在該約束兩端擴(kuò)大適當(dāng)倍數(shù)，將 全部系數(shù) 化為整數(shù)。求解混合整數(shù)規(guī)劃的方法是 分枝定界法 _。求解分配問題的專門方法 是 匈牙利法 。 2個(gè) . 二、單選題 1．整數(shù)規(guī)劃問題中，變量的取值可能是 D。 A．純整數(shù)規(guī)劃 B．混合 整數(shù)規(guī)劃 C． 0— 1規(guī)劃 D．線性規(guī)劃 3．下列方法中用于求解分配問題的是 D_。 A．求解整數(shù)規(guī)劃可以采用求解其相應(yīng)的松馳問題，然后對其非整數(shù)值的解四舍五入的方法得到整數(shù)解。 C．用割平面法求解整數(shù)規(guī)劃時(shí)，構(gòu)造的割平面可能割去一些不屬于最優(yōu)解的整數(shù)解。 2．在求解整數(shù)規(guī)劃問題時(shí)，可能出現(xiàn)的是 ABC。 A．分配問題是一個(gè)高度退化的運(yùn)輸問題 B．可以用表上作業(yè)法求解分配問題 C．從分配問題的效益矩陣中逐行取其最小元素，可得到最優(yōu)分配方案 D．匈牙利法所能求解的分配問題，要求規(guī)定一個(gè)人只能完成一件工作，同時(shí)一件工作也只給一個(gè)人做。 0— 1 規(guī)劃問題：在線性規(guī)劃問題中，如果要求所有的決策變量只能取 0 或 1，這樣的問題稱為 0— 1 規(guī)劃。 四、用分枝定界法求解下列整數(shù)規(guī)劃問題： (提示 :可采用圖解法 ) maxZ=40x1+90x2 五、用割平面法求解 六、下列整數(shù)規(guī)劃問題 說明能否用先求解相應(yīng)的線性規(guī)劃問題然后四舍五入 的辦法來求得該整數(shù)規(guī)劃的一個(gè)可行解。 七 、若某鉆井隊(duì)要從以下 10 個(gè)可供選擇的井位中確定 5 個(gè)鉆井探油。若 10個(gè)井位的代號為 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è)問題的整數(shù)規(guī)劃模型 八 、有四項(xiàng)工作要甲、乙、丙、丁四個(gè)人去完成．每項(xiàng)工作 只允許一人去完成。問應(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)表示 ，用邊或有向邊表示 研究對象 ，以及 研究對象之間具有特定關(guān)系 。 4．在圖論中，圖是反映 研究對象 _之間 _特定關(guān)系 的一種工具。 6．最小樹問題就是在網(wǎng)絡(luò)圖中，找出若干條邊，連接 所有 結(jié)點(diǎn)，而且 連接的總長度 最小。 8．求最短路問題的計(jì)算方法是從 0≤ fij≤ cij 開始逐步推算的，在推算過程中需要不斷標(biāo)記 平衡 和最短路線。 A圖中的有向邊表示研究對象，結(jié)點(diǎn)表示銜接關(guān)系。 C圖中任意兩點(diǎn)之間必有邊。 2．關(guān)于樹的概念，以下敘述 (B)正確。 3．一個(gè)連通圖中的最小樹 (B)，其權(quán) (A)。 4．關(guān)于最大流量問題，以下敘述 (D)正確。 5．圖論中的圖，以下敘述 (C)不 正確。 B．圖論中的圖，用點(diǎn)與點(diǎn)的相互位置，邊的長短曲直來表示研究對象的相互關(guān)系。 D．圖論中的圖，可以改變點(diǎn)與點(diǎn)的相互位置。 6．關(guān)于最 小樹，以下敘述 (B)正確。 7．關(guān)于可行流，以下敘述 (A)不 正確。 C．各條有向邊上的流量均為零的流是一個(gè)可行流 D．可行流的流量小于容量限制條件而大于或等于零。 (1)圖中的邊可以 是有向邊，也可以是無向邊 (2)圖中的各條邊上可以標(biāo)注權(quán)。 2．關(guān)于樹的概念，以下敘述 (123)正確。 (3)樹中刪去一條邊后必不連通 (4)樹中兩點(diǎn)之間的通路可能不唯一。 (1)任一連通圖必有支撐樹 (2)任一連通圖生成的支撐樹必唯一 (3)在支撐樹中再增加一條邊后必含圈 (4)任一連通圖生成的各個(gè)支撐樹其邊數(shù)必相同 4．在下圖中， (abcd)不是根據(jù) (a)生成的支撐樹。 (1)任一連通圖生成的各個(gè)最小樹，其總長度必相等 (2)任一連通圖生成的各個(gè)最小樹，其邊數(shù)必相等。 (4)最小樹中可能包括連通圖中的最大權(quán)邊。 1)從起點(diǎn)出發(fā)的最小權(quán)有向邊必含在最短路線中。 (3)整個(gè)圖中權(quán)最大的有向邊可能含在最短路線中 (4)從起點(diǎn)到終點(diǎn)的最短路線是唯一的。 (1)增廣路上的有向邊的方向必須是從發(fā)點(diǎn)指向收點(diǎn)的 (2)增廣路上的有向邊，必須 都是不飽和邊 (3)增廣路上 不能有零流邊 (4)增廣路上與發(fā)點(diǎn)到收點(diǎn)方向一致的有向邊不能是飽和邊，相反方向的有向邊不能是零流邊 8．關(guān)于樹，以下敘述 (ABCE)正確。D．任一樹的點(diǎn)數(shù)等于邊數(shù)減 1E．任一樹，去掉 _條邊便不連通。 A 從起點(diǎn)出發(fā)到終點(diǎn)的最短路是唯一的。 C．從起點(diǎn)出發(fā)的有向邊中的最小權(quán)邊，一定 包含在起點(diǎn)到 終點(diǎn) 的最短路上 D．從起點(diǎn)出發(fā)的有向邊中的最大權(quán)邊，一定不包含在起點(diǎn)到終點(diǎn)的最短路上。 10．關(guān)于增廣路，以下敘述 (BC )正確。 B．增廣路是一條從發(fā)點(diǎn)到收點(diǎn)的有向路，這條路上各條邊的方向可不一致。 D．增廣路上與發(fā)點(diǎn)到收點(diǎn)方向一致的邊必須是流量小于容量的邊，方向相反的邊必須是流量等于零的邊 。 四、名詞解釋 樹 :在圖論中， 具有 連通 和 不含圈 特點(diǎn)的圖稱為樹。 3． 網(wǎng)絡(luò)： 在圖論中，給邊或有向邊賦了權(quán)的圖稱為 網(wǎng)絡(luò) 4．最大流問題 ： 最大流問題是指在網(wǎng)絡(luò)圖中，在單位時(shí)間內(nèi)，從 發(fā) 點(diǎn)到 收 點(diǎn)的最大流量 5．最大流問題中流量 ： 最大流問題中流量是指單位時(shí)間的發(fā)點(diǎn)的 流出 量或收點(diǎn)的 流入 量。 8零流 邊 ： 流量為零的有向邊稱為 零流 邊 ：若樹 T 是無向圖 G 的生成樹，則稱 T 是 G 的生成樹。 10 根：有向圖 G 中可以到達(dá)圖中任一頂點(diǎn)的頂點(diǎn) u 稱為 G 的根。 ：具有相同端點(diǎn)的邊叫平行邊。 四、計(jì)算題 1．下圖是 6 個(gè)城市的交通圖，為將部分道路改造成高速 公路，使各個(gè)城市均能通達(dá)，又要使高速公路的總長度最小，應(yīng)如 何做 ?最小的總長度是多少 ? 2．對下面的兩個(gè)連通圖，試分別求出最小樹。 4．對下面兩圖，試分別求出從起點(diǎn)到終點(diǎn)的最短路