【正文】 為 C 負值 的點 所在的閉回路 內(nèi)進行 。 A 任意值 B 最大值 C 絕對值最大 D 絕對值最小 業(yè)法的基本思想和步驟與單純形法類似，因而初始調(diào)運方案的給出就相當于找到一個 C A 基 B 可行解 C 初始基本可行解 D 最優(yōu)解 15 平衡運輸問題即是指 m 個供應(yīng)地的總供應(yīng)量 D n 個需求地的總需求量。 A 大于 B 大于等于 C 小于 D 等于 三、多選題 1．運輸問題的求解結(jié)果中可能出現(xiàn)的是 ABC _。 A、 惟一最優(yōu)解 B．無窮多最優(yōu)解 C．退化解 D．無可行解 2．下列說法正確的是 ABD。 A．表上作業(yè)法也是從尋找初始基可行解開始的 B．當一個調(diào)運方案的檢驗數(shù)全部為正值時，當前方案一定是最佳方案 C．最小元素法所求得的運輸?shù)倪\量是最小的 D．表上作業(yè)法中一張供需平衡表對應(yīng)一個基可行 解 3．對于供過于求的不平衡運輸問題，下列說法正確的 是 ABC。 A．仍然可以應(yīng)用表上作業(yè)法求解 B．在應(yīng)用表上作業(yè)法之前，應(yīng)將其轉(zhuǎn)化為平衡的運輸問題 C．可以虛設(shè)一個需求地點，令其需求量為供應(yīng)量與需求量之差。 D．令虛設(shè)的需求地點與各供應(yīng) 地之間運價為 M(M 為極大的正數(shù) ) 4．下列關(guān)于運輸問題模型特點的說法正確的是 ABD A． 約束方程矩陣具有稀疏結(jié)構(gòu) B．基變量的個數(shù)是 m+n1 個 C．基變量中不能有零 D．基變量不構(gòu)成閉回路 ，下列說法正確的 是 ABC A．仍然可以應(yīng)用表上作業(yè)法求解 B．在應(yīng)用表上作業(yè)法之前，應(yīng)將其轉(zhuǎn)化為平衡的運輸問題 C．可以虛設(shè)一個需求地點，令其需求量為供應(yīng)量與需求量之差。 D．令虛設(shè)的需求地點與各供應(yīng) 地之間運價為 M(M 為極大的正數(shù) ) E. 可以虛設(shè)一個 庫存 ，令其 庫存 量為 0 三、判斷表 (a)(b)(c)中給出的調(diào)運方案能否作 為表上作 業(yè)法求解時的初始解，為什么 ? (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)地數(shù) +銷地數(shù)－ 1)，不能作為初始方案； (c)中存在以非零元素為頂點的閉回路，不能作為初始方案 四、已知某運輸問題的產(chǎn)銷平衡表。單位運價表及給出的 一個調(diào)運方案分別見表 (a)和 (b)，判斷給出的調(diào)運方案是否 為最優(yōu) ?如是說明 理由；如否。也說明理由。 表 (a)產(chǎn)銷平衡表及某一調(diào)運方案 單位運價表 銷地 產(chǎn)地 Bl B2 B3 B4 B5 B6 產(chǎn)量 l 30 20 50 A2 30 10 40 A3 10 40 10 60 A4 20 11 31 銷量 30 50 20 40 30 11 五、給出如下運輸問題 運價 產(chǎn) B1 B2 B3 B4 產(chǎn)量 Al 5 3 10 4 90 A2 1 6 9 6 40 A3 20 10 5 7 70 銷量 30 50 80 40 200 (1)應(yīng)用最小元素法求其初始方案； (2)應(yīng)用位勢法求初始方案的檢驗數(shù)，并檢驗該方案是否為最優(yōu)方案 六、用表上作業(yè)法求給出的運輸問題的最優(yōu)解 甲 乙 丙 丁 產(chǎn)量 1 10 6 7 12 4 2 16 0 5 9 9 3 5 4 10 10 4 銷量 5 2 4 6 甲 乙 丙 丁 產(chǎn)量 1 1 2 1 4 2 3 6 9 3 4 4 銷量 5 2 4 6 在最優(yōu)調(diào)運方案下的運輸費用最小為 118。 七、名詞 平衡運輸問題： m 個供應(yīng)地的供應(yīng)量等于 n 個需求地的總需求量，這樣的運輸問題稱平衡運輸問題。 銷 不平衡運輸問題： m 個供應(yīng)地的供應(yīng)量不等于 n 個需 求地的總需求量，這樣的運輸問題稱不平衡運輸問題。 第七章 整數(shù)規(guī)劃 一、填空題 1．用分枝定界法求極大化的整數(shù)規(guī)劃問題時，任何一個可行解的目標函數(shù)值是該問題目標函數(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－71X3－72X5≤ 0_。 8．在用割平面法求解整數(shù)規(guī)劃問題時，要求全部變量必須都 為 整數(shù) 。 9．用割平面法求解整數(shù)規(guī)劃問題時，若某個約束條件中有 不為整數(shù) 的系 數(shù)，則需在該約束兩端擴大適當倍數(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ī)劃問題，當?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 個鉆井探油。使總的鉆探費用為最小。若