【正文】 為 C 負(fù)值 的點(diǎn) 所在的閉回路 內(nèi)進(jìn)行 。 A 任意值 B 最大值 C 絕對(duì)值最大 D 絕對(duì)值最小 業(yè)法的基本思想和步驟與單純形法類似，因而初始調(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 大于 B 大于等于 C 小于 D 等于 三、多選題 1．運(yùn)輸問題的求解結(jié)果中可能出現(xiàn)的是 ABC _。 A、 惟一最優(yōu)解 B．無窮多最優(yōu)解 C．退化解 D．無可行解 2．下列說法正確的是 ABD。 A．表上作業(yè)法也是從尋找初始基可行解開始的 B．當(dāng)一個(gè)調(diào)運(yùn)方案的檢驗(yàn)數(shù)全部為正值時(shí)，當(dāng)前方案一定是最佳方案 C．最小元素法所求得的運(yùn)輸?shù)倪\(yùn)量是最小的 D．表上作業(yè)法中一張供需平衡表對(duì)應(yīng)一個(gè)基可行 解 3．對(duì)于供過于求的不平衡運(yùn)輸問題，下列說法正確的 是 ABC。 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ù) ) 4．下列關(guān)于運(yùn)輸問題模型特點(diǎn)的說法正確的是 ABD A． 約束方程矩陣具有稀疏結(jié)構(gòu) B．基變量的個(gè)數(shù)是 m+n1 個(gè) C．基變量中不能有零 D．基變量不構(gòu)成閉回路 ，下列說法正確的 是 ABC 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)價(jià)表及給出的 一個(gè)調(diào)運(yùn)方案分別見表 (a)和 (b)，判斷給出的調(diào)運(yùn)方案是否 為最優(yōu) ?如是說明 理由；如否。也說明理由。 表 (a)產(chǎn)銷平衡表及某一調(diào)運(yùn)方案 單位運(yùn)價(jià)表 銷地 產(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 五、給出如下運(yùn)輸問題 運(yùn)價(jià) 產(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àn)數(shù)，并檢驗(yàn)該方案是否為最優(yōu)方案 六、用表上作業(yè)法求給出的運(yùn)輸問題的最優(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)運(yùn)方案下的運(yùn)輸費(fèi)用最小為 118。 七、名詞 平衡運(yùn)輸問題： m 個(gè)供應(yīng)地的供應(yīng)量等于 n 個(gè)需求地的總需求量，這樣的運(yùn)輸問題稱平衡運(yù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ù)值的 下界 。 2．在分枝定界法中，若選 Xr=4／ 3 進(jìn)行分支，則構(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．對(duì)于一個(gè)有 n 項(xiàng)任務(wù)需要有 n 個(gè)人去完成的分配問題，其 解中取值為 1 的變量 數(shù)為 n 個(gè)。 6．分枝定界法和割平面法的基礎(chǔ)都是用 _線性規(guī)劃 方法求解整數(shù)規(guī)劃。 7．若在對(duì)某整數(shù)規(guī)劃問題的松馳問題進(jìn)行求解時(shí)，得到最優(yōu)單純形表中，由 X。所在行得 X1+1／ 7x3+2／ 7x5=13／ 7，則以 X1行為源行的割平面方程為 _76－71X3－72X5≤ 0_。 8．在用割平面法求解整數(shù)規(guī)劃問題時(shí)，要求全部變量必須都 為 整數(shù) 。 9．用割平面法求解整數(shù)規(guī)劃問題時(shí)，若某個(gè)約束條件中有 不為整數(shù) 的系 數(shù)，則需在該約束兩端擴(kuò)大適當(dāng)倍數(shù)，將 全部系數(shù) 化為整數(shù)。 10．求解純整數(shù)規(guī)劃的方法是 割平面法 。求解混合整數(shù)規(guī)劃的方法是 分枝定界法 _。 11．求解 0— 1 整數(shù)規(guī)劃的方法是 隱枚舉法 。求解分配問題的專門方法 是 匈牙利法 。 12．在應(yīng)用匈牙利法求解分配問題時(shí)，最終求得的分配元 應(yīng)是 獨(dú)立零元素 _。 2 個(gè) . 二、單選題 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．匈 牙利法 三、多項(xiàng)選擇 1．下列說明 不 正確的是 ABC。 A．求解整數(shù)規(guī)劃可以采用求解其相應(yīng)的松馳問題，然后對(duì)其非整數(shù)值的解四舍五入的方法得到整數(shù)解。B．用分枝定界法求解一個(gè)極大化的整數(shù)規(guī)劃問題，當(dāng)?shù)玫蕉嘤谝粋€(gè)可行解時(shí)，通常任取其中一個(gè)作為下界。C．用割平面法求解整數(shù)規(guī)劃時(shí)，構(gòu)造的割平面可能割去一些不屬于最優(yōu)解的整數(shù)解。 D．用割平面法求解整數(shù)規(guī)劃問題時(shí)，必須首 先將原問題的非整數(shù)的約束系數(shù)及右端常數(shù)化為整數(shù)。 2．在求解整數(shù)規(guī)劃問題時(shí)，可能出現(xiàn)的是 ABC。 A．唯一最優(yōu)解 B．無可行解 C．多重最佳解 D．無窮多個(gè)最優(yōu)解 3．關(guān)于分配問題的下列說法正確的是 _ ABD。 A．分配問題是一個(gè)高度退化的運(yùn)輸問題 B．可以用表上作業(yè)法求解分配問題 C．從分配問題的效益矩陣中逐行取其最小元素，可得到最優(yōu)分配方案 D．匈牙利法所能求解的分配問題，要求規(guī)定一個(gè)人只能完成一件工作，同時(shí)一件工作也只給一個(gè)人做。 （ CDE ） A 線性規(guī)劃 B 非線性規(guī) 劃 C 純整數(shù)規(guī)劃 D 混合整數(shù)規(guī)劃 E 0— 1 規(guī)劃 （ ABCDE ） A 求其松弛問題 B 在其松弛問題中增加一個(gè)約束方程 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ī)劃的一個(gè)可行解。 答： 不考慮整數(shù)約束，求解相應(yīng)線性規(guī)劃得最優(yōu)解為 x1=10/3， x2=x3=0，用四舍五人法時(shí)，令 x1=3，x2=x3=0， 其中第 2 個(gè)約束無法滿足， 故不可行。 七 、若某鉆井隊(duì)要從以下 10 個(gè)可供選擇的井位中確定 5 個(gè)鉆井探油。使總的鉆探費(fèi)用為最小。若