運(yùn)籌學(xué)復(fù)習(xí)題

1、運(yùn)籌學(xué) - 學(xué)習(xí)指南一、名詞解釋1 松弛變量為將線性規(guī)劃問題的數(shù)學(xué)模型化為標(biāo)準(zhǔn)型而加入的變量。2 可行域滿足線性約束條件的解（ x,y ）叫做可行解，由所有可行解組成的集合叫做可行域。3 人工變量亦稱人造變量. 求解線性規(guī)劃問題時(shí)人為加入的變量。用單純形法求解線性規(guī)劃問題，都是在具有初始可行基的條件下進(jìn)行的 , 但約束方程組的系數(shù)矩陣A 中所含的單位向量常常不足m個(gè)，此時(shí)可加入若干（至多m）個(gè)新變量，稱這些新變量為人工變量。4 對偶理論每一個(gè)線性規(guī)劃問題都存在一個(gè)與其對偶的問題， 在求出一個(gè)問題解的同時(shí)， 也給出了另一個(gè)問題的解。研究線性規(guī)劃中原始問題與對偶問題之間關(guān)系的理論5 靈敏度分析研究

2、與分析一個(gè)系統(tǒng) （或模型） 的狀態(tài)或輸出變化對系統(tǒng)參數(shù)或周圍條件變化的敏感程度的方法。 在最優(yōu)化方法中經(jīng)常利用靈敏度分析來研究原始數(shù)據(jù)不準(zhǔn)確或發(fā)生變化時(shí)最優(yōu)解的穩(wěn)定性。通過靈敏度分析還可以決定哪些參數(shù)對系統(tǒng)或模型有較大的影響。6 影子價(jià)格反映資源配置狀況的價(jià)格。影子價(jià)格是指在其他資源投入不變的情況下, 每增加一單位的某種資源的投入所帶來的追加收益。 即影子價(jià)格等于資源投入的邊際收益。 只有在資源短缺的情況下 , 每增加一單位的投入才能帶來收益的增加7 產(chǎn)銷平衡運(yùn)輸一種特殊的線性規(guī)劃問題。 產(chǎn)品的銷售過程中， 產(chǎn)銷平衡是指工廠產(chǎn)品的產(chǎn)量等于市場上的銷售量。8 西北角法是運(yùn)籌學(xué)中制定運(yùn)輸問題的初始

3、調(diào)運(yùn)方案 （即初始基可行解） 的基本方法之一。 也就是從運(yùn)價(jià)表的西北角位置開始，依次安排m個(gè)產(chǎn)地和n個(gè)銷地之間的運(yùn)輸業(yè)務(wù)，從而得到一個(gè)初始調(diào)運(yùn)方案的方法。9 最優(yōu)性檢驗(yàn)檢驗(yàn)當(dāng)前調(diào)運(yùn)方案是不是最優(yōu)方案的過程。10 動態(tài)規(guī)劃解決多階段決策過程優(yōu)化問題的方法：把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個(gè)求解11 狀態(tài)轉(zhuǎn)移方程從階段 K 到 K+1 的狀態(tài)轉(zhuǎn)移規(guī)律的表達(dá)式12 逆序求解法在求解時(shí)， 首先逆序求出各階段的條件最優(yōu)目標(biāo)函數(shù)和條件最優(yōu)決策， 然后反向追蹤， 順序地求出改多階段決策問題的最優(yōu)策略和最優(yōu)路線。13 最短路問題最短路徑問題是圖論研究中的一個(gè)經(jīng)典算法問題， 旨在尋找

4、圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。14 最小費(fèi)用最大流在一個(gè)網(wǎng)絡(luò)中每段路徑都有“容量”和“費(fèi)用”兩個(gè)限制的條件下，此類問題的研究試圖尋找出：流量從A到B,如何選擇路徑、分配經(jīng)過路徑的流量，可以達(dá)到所用的費(fèi)用最小的要求。15 排隊(duì)論排隊(duì)論 （queueing theory）, 或稱隨機(jī)服務(wù)系統(tǒng)理論, 是通過對服務(wù)對象到來及服務(wù)時(shí)間的統(tǒng)計(jì)研究，得出這些數(shù)量指標(biāo)（等待時(shí)間、排隊(duì)長度、忙期長短等）的統(tǒng)計(jì)規(guī)律，然后根據(jù)這些規(guī)律來改進(jìn)服務(wù)系統(tǒng)的結(jié)構(gòu)或重新組織被服務(wù)對象， 使得服務(wù)系統(tǒng)既能滿足服務(wù)對象的需要，又能使機(jī)構(gòu)的費(fèi)用最經(jīng)濟(jì)或某些指標(biāo)最優(yōu)。二、選擇題1. 用圖解法求解一個(gè)關(guān)于最大利潤的線

5、性規(guī)劃問題時(shí)， 若其等利潤線與可行解區(qū)域相交，但不存在可行解區(qū)域最邊緣的等利潤線，則該線性規(guī)劃問題 （ B ）。A 、有無窮多個(gè)最優(yōu)解 B 、有可行解但無最優(yōu)解C 、有可行解且有最優(yōu)解 D 、無可行解2. 若線性規(guī)劃問題的最優(yōu)解同時(shí)在可行解域的兩個(gè)頂點(diǎn)處達(dá)到，則此線性規(guī)劃問題的最優(yōu)解為（ B ）A、兩個(gè) B 、無窮多個(gè)C、零個(gè) D、過這的點(diǎn)直線上的一切點(diǎn)3. 用圖解法求解一個(gè)關(guān)于最小成本的線性規(guī)劃問題時(shí)，若其等成本線與可行解區(qū)域的某一條邊重合，則該線性規(guī)劃問題 （ A ） 。A.有無窮多個(gè)最優(yōu)解B、有有限個(gè)最優(yōu)解C.有唯一的最優(yōu)解D.無最優(yōu)解4. 在求極小值的線性規(guī)劃問題中，引入人工變量之后，

6、還必須在目標(biāo)函數(shù)中分別為它們配上系數(shù)，這些系數(shù)值應(yīng)為 （ A ）。A、很大的正數(shù) B 、較小的正數(shù) C、1 D、05. 對 LP 問題的標(biāo)準(zhǔn)型： maxZ CX , AX b,X 0 ，利用單純形表求解時(shí)，每做一次換基迭代，都能保證它相應(yīng)的目標(biāo)函數(shù)值Z 必為（ B ）A 增大B 不減少C 減少D 不增大6. 若 LP 最優(yōu)解不唯一，則在最優(yōu)單純形表上（ A ）A 非基變量的檢驗(yàn)數(shù)必有為零者B 非基變量的檢驗(yàn)數(shù)不必有為零者C 非基變量的檢驗(yàn)數(shù)必全部為零D 以上均不正確7. 求解線性規(guī)劃模型時(shí)，引入人工變量是為了（ B ）A 使該模型存在可行解B 確定一個(gè)初始的基可行解C 使該模型標(biāo)準(zhǔn)化D 以上均

7、不正確11 . 用大 M 法求解LP 模型時(shí)，若在最終單純形表上基變量中仍含有非零的人工變量，則原模型（ C ）A 有可行解，但無最優(yōu)解B 有最優(yōu)解C 無可行解D 以上都不對12 . 已知x1（2,4） ， x2 （4,8） 是某 LP 的兩個(gè)最優(yōu)解，則（ D ）也是 LP 的最優(yōu)解。Ax（4,4）Bx（1,2）Cx（2,3）D 無法判斷13 、線性規(guī)劃問題的靈敏度分析研究（ BC ）A 、對偶單純形法的計(jì)算結(jié)果；B 、目標(biāo)函數(shù)中決策變量系數(shù)的變化與最優(yōu)解的關(guān)系；C 、資源數(shù)量變化與最優(yōu)解的關(guān)系；D 、最優(yōu)單純形表中的檢驗(yàn)數(shù)與影子價(jià)格的聯(lián)系。14、對偶單純形法迭代中的主元素一定是負(fù)元素（A ）

8、A正確日錯(cuò)誤C不一定D無法判斷15 、 對偶單純形法求解極大化線性規(guī)劃時(shí)， 如果不按照最小化比值的方法選取什么變量則在下一個(gè)解中至少有一個(gè)變量為正（ B ）A換出變量日換入變量C非基變量D基變量16 、影子價(jià)格是指（D）A檢驗(yàn)數(shù)日對偶問題的基本解C解答列取值D對偶問題的最優(yōu)解17 、影子價(jià)格的經(jīng)濟(jì)解釋是（ C ）A、判斷目標(biāo)函數(shù)是否取得最優(yōu)解以價(jià)格確定的經(jīng)濟(jì)性C約束條件所付出的代價(jià)D產(chǎn)品的產(chǎn)量是否合理18 、 在總運(yùn)輸利潤最大的運(yùn)輸方案中， 若某方案的空格的改進(jìn)指數(shù)分別為 I WB=50 元， I WC=-80元，I YA=0 元，I XC=20 元，則最好挑選 （ A ） 為調(diào)整格。A、W由

9、 B、W骼 C、YA格 D、XC格19 、在一個(gè)運(yùn)輸方案中，從任一數(shù)字格開始， （ B ） 一條閉合回路。A.可以形成至少 B .不能形成C、可以形成D .有可能形成20、運(yùn)輸問題可以用 （ B ） 法求解。A 、定量預(yù)測 B 、單純形C 、求解線性規(guī)劃的圖解D 、關(guān)鍵線路21、在運(yùn)輸問題的表上作業(yè)法選擇初始基本可行解時(shí)，必須注意（ AD ） 。A 、針對產(chǎn)銷平衡的表；B 、位勢的個(gè)數(shù)與基變量個(gè)數(shù)相同；C 、填寫的運(yùn)輸量要等于行、列限制中較大的數(shù)值；D 、填寫的運(yùn)輸量要等于行、列限制中較小的數(shù)值。22 、 用增加虛設(shè)產(chǎn)地或者虛設(shè)銷地的方法可將產(chǎn)銷不平衡的運(yùn)輸問題化為產(chǎn)銷平衡的運(yùn)輸問題 （ A

10、）A、正確B、錯(cuò)誤C、不一定D、無法判斷23、通過什么方法或者技巧可以把產(chǎn)銷不平衡運(yùn)輸問題轉(zhuǎn)化為產(chǎn)銷平衡運(yùn)輸問題 （ C ）A、非線性問題的線性化技巧B、靜態(tài)問題的動態(tài)處理C、引入虛擬產(chǎn)地或者銷地D、引入人工變量24、動態(tài)規(guī)劃方法不同于線性規(guī)劃的主要特點(diǎn)是（ AD ） 。A、動態(tài)規(guī)劃可以解決多階段決策過程的問題；B、動態(tài)規(guī)劃問題要考慮決策變量；C它的目標(biāo)函數(shù)與約束不容易表示；D它可以通過時(shí)間或空間劃分一些問題為多階段決策過程問題。25、用DP方法處理資源分配問題時(shí)，通?？偸沁x階段初資源的擁有量作為決策變量（B ）A、正確B、錯(cuò)誤C、不一定D、無法判斷26、用DP方法處理資源分配問題時(shí)，每個(gè)階段

11、資源的投放量作為狀態(tài)變量（ B ）A、正確B、錯(cuò)誤C、不一定D、無法判斷27、 動態(tài)規(guī)劃最優(yōu)化原理的含義是：最優(yōu)策略中的任意一個(gè)K- 子策略也是最優(yōu)的（ A ）A、正確B、錯(cuò)誤C、不一定D、無法判斷28動態(tài)規(guī)劃的核心是什么原理的應(yīng)用（ A ）A、最優(yōu)化原理B、逆向求解原理C、最大流最小割原理D、網(wǎng)絡(luò)分析原理29動態(tài)規(guī)劃求解的一般方法是什么？（ C ）A圖解法B、單純形法C、逆序求解D、標(biāo)號法30 用動態(tài)規(guī)劃求解工程線路問題時(shí)， 什么樣的網(wǎng)絡(luò)問題可以轉(zhuǎn)化為定步數(shù)問題求解（ B ）A、任意網(wǎng)絡(luò)B、無回路有向網(wǎng)絡(luò)C、混合網(wǎng)絡(luò)D、容量網(wǎng)絡(luò)31 .動態(tài)規(guī)劃的求解的要求是什么（ ACD ）A、給出最優(yōu)狀態(tài)

12、序列B、給出動態(tài)過程C、給出目標(biāo)函數(shù)值D、給出最優(yōu)策略32 .用動態(tài)規(guī)劃解決生產(chǎn)庫存的時(shí)候，應(yīng)該特別注意哪些問題？ （ BC ）A、生產(chǎn)能力B、狀態(tài)變量的允許取值范圍C、決策變量的允許取值范圍D、庫存容量33 .在網(wǎng)絡(luò)計(jì)劃技術(shù)中，進(jìn)行時(shí)間與成本優(yōu)化時(shí)，一般地說，隨著施工周期的縮短，直接 費(fèi)用是（C ）。A、降低的 B 、不增不減的C 、增加的D 、難以估計(jì)的34 .最小枝權(quán)樹算法是從已接接點(diǎn)出發(fā)，把 （C ）的接點(diǎn)連接上A、最遠(yuǎn) B 、較遠(yuǎn) C、最近 D、較近35 .在箭線式網(wǎng)絡(luò)固中，（D ）的說法是錯(cuò)誤的。A、結(jié)點(diǎn)不占用時(shí)間也不消耗資源B、結(jié)點(diǎn)表示前接活動的完成和后續(xù)活動的開始C、箭線代表活

13、動D、結(jié)點(diǎn)的最早出現(xiàn)時(shí)間和最遲出現(xiàn)時(shí)間是同一個(gè)時(shí)間36 .如圖所示，在鍋爐房與各車間之間鋪設(shè)暖氣管最小的管道總長度是（C ）。A 、 1200 B 、 1400C 、 1300 D 、 170037 .在求最短路線問題中，已知起點(diǎn)到A, B, C三相鄰結(jié)點(diǎn)的距離分別為15km, 20 km25km,貝U （ D ）。A、最短路線一定通過 A點(diǎn)B、最短路線一定通過 B點(diǎn)G最短路線一定通過 C點(diǎn)D、不能判斷最短路線通過哪一點(diǎn)38 .在一棵樹中，如果在某兩點(diǎn)間加上條邊，則圖一定 （A ）A、存在一個(gè)圈B、存在兩個(gè)圈G存在三個(gè)圈口不含圈39網(wǎng)絡(luò)圖關(guān)鍵線路的長度（C ） 工程完工期。A .大于B .小于

14、C .等于D .不一定等于40. 在計(jì)算最大流量時(shí)，我們選中的每一條路線（C ）。A、一定是一條最短的路線B 、一定不是一條最短的路線C、是使某一條支線流量飽和的路線D、是任一條支路流量都不飽和的路線41. 從甲市到乙市之間有公路網(wǎng)絡(luò)，為了盡快從甲市驅(qū)車趕到乙市，應(yīng)借用（ C ）A、樹的逐步生成法B、求最小技校樹法G求最短路線法D 、求最大流量法42. 為了在各住宅之間安裝一個(gè)供水管道若要求用材料最省，則應(yīng)使用 （ B ）。A、求最短路法B、求最小技校樹法C、求最大流量法D、樹的逐步生成法43排隊(duì)系統(tǒng)狀態(tài)轉(zhuǎn)移速度矩陣中，每一列的元素之和等于0 。 （ B ）A正確日錯(cuò)誤C不一定D、無法判斷44

15、. 排隊(duì)系統(tǒng)中狀態(tài)是指系統(tǒng)中的顧客數(shù)（ A ）A、正確B、錯(cuò)誤C、不一定D、無法判斷45排隊(duì)系統(tǒng)的組成部分有（ABC ）A、輸入過程B、排隊(duì)規(guī)則C、服務(wù)機(jī)構(gòu)D、服務(wù)時(shí)間46排隊(duì)系統(tǒng)中，若系統(tǒng)輸入為泊松流，則相繼到達(dá)的顧客間隔時(shí)間服從什么分布（D ）A、正態(tài)分布B、愛爾朗分布C、泊松流D、負(fù)指數(shù)分布47研究排隊(duì)模型及數(shù)量指標(biāo)的思路是首先明確系統(tǒng)的意義，然后（ABC ）A、寫出狀態(tài)概率方程B、寫出狀態(tài)轉(zhuǎn)移速度矩陣C、畫出狀態(tài)轉(zhuǎn)移速度圖D、寫出相應(yīng)的微分方程48排隊(duì)系統(tǒng)的狀態(tài)轉(zhuǎn)移速度矩陣中（B ）元素之和等于零。A、每一列B、每一行C、對角線D、次對角線三、計(jì)算題1. 用圖解法求解下列 LP 問題

16、maxz x1 2x22X1 2X2 12Xi 2X2 8s.t 4X1 16 4X2 12 X1，X2 0答案：依題有可得最優(yōu)解集合為（ X1，X2）I（X1，X2）a（2,3）（1 a）（4,2），0 a 1也即（ X1, X2） 1 （X1, X2） （4 2a,2 a）,0 a 1最優(yōu)值為 z 8 （詳細(xì)求解過程略去）2.用分枝界定法求解下列線性規(guī)劃問題maX f （x） 6x 4X22X1 4x2132x1X27X1,X20且為整數(shù)答案：松弛問題的最優(yōu)解為X1=, X2=2, OB«=23max f (x) 6x 4x2問題I2X12X14X2 13X27問題II2x1 4

17、x2132x1 x27X 3X1,X20且為整數(shù)問題I問題IIX123X29/41f(x)2122X1, X220且為整數(shù)各個(gè)分枝問題的松弛解為問題II的解即原整數(shù)問題的最優(yōu)解由X1=得到兩個(gè)分枝如下:max f （x） 6x1 4x23、已知線性規(guī)劃問題max z5X1 6X2 7X3X1 5X2 3X3 15s.t.5X1 6X2 10X3 20X1 X2 X35Xi, X2 0，X3無約束要求：(1)化為標(biāo)準(zhǔn)型式(2)列出用兩階段法求解時(shí)第一階段的初始單純形表解：令 X1' X;X3X3' X3''，X3' X3'' Q z z&#

18、39;原模型可以轉(zhuǎn)化為X1X；X3X3 X3''，X3X3''0z z'X1' 5X2 3X3 3X3'' X4 X6 155X16X210X3 10X3'' X520X1 X2 X3 X3 X7 5X1'，X2, X3'，X3''，X4，X5, X6，X7 0(2)見下表00-1 " X1X2 X3X3X4X5 X6X7-1X61510X5205-1X7515-33-1-610-10011-10Cj - zj26-22-14、求下列線性規(guī)劃問題，并寫出LP問題的對偶問題m

19、aXz 3X1 2X2X1 2X2 4s.t.3X1 2X2 14X1 X2 3X1，X2答案：r5 13X 2 715 T 0maXZ 4對偶問題：min w 4y1 14y2 3y3Vi 3y2 y. 3s.t. 2yi 2y2 y. 2yi % 05、求出下列問題的對偶問題并分別隊(duì)原問題及對偶問題求解 原問題：max f (x) 5x1 3x2 6x3Xi 2x2 x3 182xi x2 3x3 16s.tX x2 x3 10X,x20,x3 不限答案：對偶問題：ming(y) 18yl 16y2 10y3V、2y2 y35,2 x y2 y3 3s.ty13 y2 y36y1,y20,

20、 y3 不限用單純型法求解過程CCbXbb536-600Mx1x2x' 3x" 3x4x5x60x4180x516Mx610121110021(3)30101111001OBJ=10MCj - z jMMMM00M5+M3+M6+M-6-M0000x438/36x' 316/3Mx614/31/35/30011/302/31/31101/301/3(2/3)0001/31OBJ= 32-14M/3Cj - z j4-M/32-2M/36602+M/3M1+M/31+2M/3000-2-M/300x416x' 333x271/200011/25/2(1/2)01

21、101/23/21/210001/23/2OBJ=39Cj - z j9/236603/23/21/200003/2 -M-3/20x445x163x2400111131022011011(1)012OBJ=42Cj - z j5377021001102-M+10x485x114010010112000136X"340111012OBJ=465466013Cj - z j010001-M 3對偶問題最優(yōu)解：y4=0y5=1y6=0yi=0y2=1y3=3原問題最優(yōu)解：Xi =14, X2=0, X3=-4, X4=8, x 5=0, x 6=0, OBJ=466、運(yùn)輸問題的數(shù)據(jù)如下表

22、:B8B3B4A2237500A4359600A1678300銷量300200500400求最優(yōu)運(yùn)輸方案。答案：最優(yōu)方案： f * = 6000B 1B2B3B4A100400500A200400600A300300銷量3002005004007、對于以下運(yùn)輸問題，如何用最小元素法求出初始調(diào)運(yùn)方案?單位、銷地產(chǎn)加、E：*即產(chǎn)量*W11+10PW即和A產(chǎn)7a務(wù),10*銷甲3卡如5/p答案：求解過程如下。表中“口”內(nèi)數(shù)字為刪除線出現(xiàn)的先后順序。8、判斷下表中給出的調(diào)運(yùn)方案能否作為表上作業(yè)法求解的初始方案？為什么?產(chǎn)*ABiB2B3B4B5心且 J小A2525A2201030A32020A52530

23、銷量2020301025105答案：不能作為初始方案。因?yàn)閿?shù)字格只有6個(gè)，而n m 1 89、某奶牛站希望通過投資來擴(kuò)大牛群數(shù)，開始只有5000元資金，現(xiàn)在已知可購入 A或者B兩個(gè)品種的奶牛，對于A種牛每投入1000元，當(dāng)年及以后每年可以獲得 500元和2頭小牛， 對B種牛每投入1000元，當(dāng)年及以后每年可以獲得200元和3頭小牛。問：(1)在今后的四年內(nèi)應(yīng)該如何分配投資使奶牛群最大(2)到第四年底奶牛站將有多少頭奶牛。答案：狀態(tài)Sn為階段n可利用的資金；決策dn為階段n向A種牛投入的資金數(shù)；Sn d n為階段n向B種牛投入的資金數(shù)；則轉(zhuǎn)移函數(shù)為sn 1 0.2Sn 0.3d n遞推函數(shù)：f n(Sn)“(dn)九Q1)r n 1000(3Sn dn)；r表示在階段n出生的小牛數(shù)I nS4 5000；第四年末牧場主應(yīng)擁有的牛的頭數(shù)為70頭10.求下面容量網(wǎng)絡(luò)的最大流，弧邊上括號內(nèi)第一個(gè)數(shù)為容量，第二個(gè)數(shù)為流量。(1)、根據(jù)標(biāo)號過程找出增廣鏈，確定流量修正量£；(2)、調(diào)整流量，畫出最大流圖，說明最大流量是多少；(3)、根據(jù)標(biāo)號和求解過程確定最小割并算出最小割容量;、解：1.增廣鏈:1 min 2,1,31(