運籌學復習題

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

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

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

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

5、用最經(jīng)濟或某些指標最優(yōu)。、選擇題若其等利潤線與可行解區(qū)域相交， （ B ） 。1. 用圖解法求解一個關(guān)于最大利潤的線性規(guī)劃問題時， 但不存在可行解區(qū)域最邊緣的等利潤線，則該線性規(guī)劃問題A 、有無窮多個最優(yōu)解 B 、有可行解但無最優(yōu)解C 、有可行解且有最優(yōu)解 D 、無可行解2. 若線性規(guī)劃問題的最優(yōu)解同時在可行解域的兩個頂點處達到，則此線性規(guī)劃問題的最 優(yōu)解為（ B ）A、兩個 B 、無窮多個C、零個 D 、過這的點直線上的一切點3. 用圖解法求解一個關(guān)于最小成本的線性規(guī)劃問題時，若其等成本線與可行解區(qū)域的某 一條邊重合，則該線性規(guī)劃問題 （ A ） 。A有無窮多個最優(yōu)解B、有有限個最優(yōu)解C有唯

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

7、 B ）A 使該模型存在可行解B 確定一個初始的基可行解C 使該模型標準化D 以上均不正確11. 用大 M 法求解 LP 模型時，若在最終單純形表上基變量中仍含有非零的人工變量， 則原模型（ C ）A 有可行解，但無最優(yōu)解B 有最優(yōu)解C 無可行解D 以上都不對12. 已知x1 （2,4） ， x2 （4,8）是某LP的兩個最優(yōu)解，則（ D ）也是LP的最優(yōu)解。 A x （4,4）B x （1,2）C x （2,3）D 無法判斷13 、線性規(guī)劃問題的靈敏度分析研究（BC ）A 、對偶單純形法的計算結(jié)果；B 、目標函數(shù)中決策變量系數(shù)的變化與最優(yōu)解的關(guān)系；C 、資源數(shù)量變化與最優(yōu)解的關(guān)系；D 、最優(yōu)

8、單純形表中的檢驗數(shù)與影子價格的聯(lián)系。14、對偶單純形法迭代中的主元素一定是負元素（ A ）A、正確B、錯誤C、不一定D、無法判斷15 、對偶單純形法求解極大化線性規(guī)劃時， 如果不按照最小化比值的方法選取什么變量則 在下一個解中至少有一個變量為正（ B ）A、換出變量B、換入變量C、非基變量D、基變量16 、影子價格是指（ D）A、檢驗數(shù)B、對偶問題的基本解C、解答列取值D、對偶問題的最優(yōu)解17 、影子價格的經(jīng)濟解釋是（ C ）A、判斷目標函數(shù)是否取得最優(yōu)解B、價格確定的經(jīng)濟性C、約束條件所付出的代價D、產(chǎn)品的產(chǎn)量是否合理18、在總運輸利潤最大的運輸方案中， 若某方案的空格的改進指數(shù)分別為I W

9、B=50元，I WC=-80元， I YA=0元， I XC=20 元，則最好挑選 （ A ） 為調(diào)整格。A、WB格 B 、 WC格 C 、YA格 D 、XC格19 、在一個運輸方案中，從任一數(shù)字格開始，（ B ） 一條閉合回路。A可以形成至少 B 不能形成C、可以形成D 有可能形成20、運輸問題可以用 （ B ） 法求解。A 、定量預測 B 、單純形 C 、求解線性規(guī)劃的圖解 D 、關(guān)鍵線路21、在運輸問題的表上作業(yè)法選擇初始基本可行解時，必須注意（AD ）。A 、針對產(chǎn)銷平衡的表；B 、位勢的個數(shù)與基變量個數(shù)相同；C 、填寫的運輸量要等于行、列限制中較大的數(shù)值；D 、填寫的運輸量要等于行、

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

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

12、、任意網(wǎng)絡B、無回路有向網(wǎng)絡C、混合網(wǎng)絡D、容量網(wǎng)絡 31動態(tài)規(guī)劃的求解的要求是什么(ACD )A、給出最優(yōu)狀態(tài)序列B、給出動態(tài)過程C、給出目標函數(shù)值D、給出最優(yōu)策略32用動態(tài)規(guī)劃解決生產(chǎn)庫存的時候，應該特別注意哪些問題？(BC )A、生產(chǎn)能力B、狀態(tài)變量的允許取值范圍C、決策變量的允許取值范圍D、庫存容量33. 在網(wǎng)絡計劃技術(shù)中，進行時間與成本優(yōu)化時，一般地說，隨著施工周期的縮短，直接 費用是 ( C ) 。A、降低的 B 、不增不減的 C 、增加的 D 、難以估計的34. 最小枝權(quán)樹算法是從已接接點出發(fā)，把 ( C ) 的接點連接上A 、最遠 B 、較遠 C 、最近 D 、較近35. 在箭

13、線式網(wǎng)絡固中， ( D ) 的說法是錯誤的。A、結(jié)點不占用時間也不消耗資源B、結(jié)點表示前接活動的完成和后續(xù)活動的開始C、箭線代表活動D、結(jié)點的最早出現(xiàn)時間和最遲出現(xiàn)時間是同一個時間36. 如圖所示，在鍋爐房與各車間之間鋪設暖氣管最小的管道總長度是 ( C ) 。 A 、1200 B 、 1400C 、1300 D 、170037.A， B， C三相鄰結(jié)點的距離分別為15km， 20 km25km，則( D)。A 、最短路線定通過A點B 、最短路線一定通過B點C、最短路線一定通過C點D 、不能判斷最短路線通過哪一點在求最短路線問題中，已知起點到38. 在一棵樹中，如果在某兩點間加上條邊，則圖一定

14、 ( A ) A 、存在一個圈 B 、存在兩個圈 C、存在三個圈D、不含圈39 網(wǎng)絡圖關(guān)鍵線路的長度 ( C ) 工程完工期。A 大于 B 小于C 等于 D 不一定等于40. 在計算最大流量時，我們選中的每一條路線 ( C ) 。A、一定是一條最短的路線B 、一定不是一條最短的路線C、是使某一條支線流量飽和的路線D 、是任一條支路流量都不飽和的路線41. 從甲市到乙市之間有公路網(wǎng)絡，為了盡快從甲市驅(qū)車趕到乙市，應借用（ C ）A 、樹的逐步生成法B 、求最小技校樹法C、求最短路線法D 、求最大流量法42. 為了在各住宅之間安裝一個供水管道若要求用材料最省，則應使用 （ B ） 。A、求最短路法

15、 B 、求最小技校樹法 C 、求最大流量法 D 、樹的逐步生成法 43排隊系統(tǒng)狀態(tài)轉(zhuǎn)移速度矩陣中，每一列的元素之和等于0。（ B ）A、正確B、錯誤C、不一定D、無法判斷44. 排隊系統(tǒng)中狀態(tài)是指系統(tǒng)中的顧客數(shù)（ A ）A、正確B、錯誤C、不一定D、無法判斷45排隊系統(tǒng)的組成部分有（ ABC ）A、輸入過程B、排隊規(guī)則C、服務機構(gòu)D、服務時間46排隊系統(tǒng)中，若系統(tǒng)輸入為泊松流，則相繼到達的顧客間隔時間服從什么分布（D ）A、正態(tài)分布B、愛爾朗分布C、泊松流D、負指數(shù)分布 47研究排隊模型及數(shù)量指標的思路是首先明確系統(tǒng)的意義，然后（ABC ）A、寫出狀態(tài)概率方程B、寫出狀態(tài)轉(zhuǎn)移速度矩陣C、畫出狀

16、態(tài)轉(zhuǎn)移速度圖D、寫出相應的微分方程48排隊系統(tǒng)的狀態(tài)轉(zhuǎn)移速度矩陣中（B ）元素之和等于零。A、每一列B、每一行C、對角線D、次對角線三、計算題1. 用圖解法求解下列 LP 問題 maxz x1 2x22x1 2x2 12 x1 2x2 8s.t. 4x1 164x2 12x1,x2 0 答案：依題有可得最優(yōu)解集合為( x1,x2)|(x1,x2) a(2,3) (1 a)(4,2),0 a 1也即( x1, x2) | ( x1, x2) (4 2a,2 a),0 a 1 最優(yōu)值為 z 8 (詳細求解過程略去)2. 用分枝界定法求解下列線性規(guī)劃問題 maxf (x) 6x1 4x2 2x1 4

17、x2 13 2x1 x2 7 x1,x2 0 且為整數(shù) 答案：松弛問題的最優(yōu)解為 x1=, x2=2, OBJ=23 由 x1= 得到兩個分枝如下：max f(x) 6x1 4x2max f (x) 6x14x22x14x2 13和2x14x2 13問題 I 2x1x2 7問題 II 2x1x2 7x12x13x1,x20 且為整數(shù)x1,x20 且為整數(shù)各個分枝問題的松弛解為問題 I問題 IIx123x29/41f(x)2122問題 II 的解即原整數(shù)問題的最優(yōu)解3、已知線性規(guī)劃問題max z 5x1 6x2 7x3x1 5x2 3x3 15s.t. 5x1 6x2 10x3 20 s.t.x

18、1 x2 x3 5x1,x2 0 , x3無約束要求：（1）化為標準型式（2）列出用兩階段法求解時第一階段的初始單純形表解：（1）令 x1 x;x原模型可以轉(zhuǎn)化為3 x3 x3,x3、x30， zzx1x;x3 x3 x3,x3、x3 0，z zx15x2 3x3 3x3 x4 x6 155x1 6x2 10x3 10x3 x5 20x1x2 x3 x3x7 5x1,x2,x3,x3,x4,x5,x6,x7 0（2）見下表000000-11x1 x2x3x7x3x4x5x6-1x6 1515-33-10100205 -610-100100x5-1x7 5111-10001cj-zj26-22-

19、10004、求下列線性規(guī)劃問題，并寫出 LP 問題的對偶問題maxz 3x1 2x2x1 2x2 4s.t.3x1 2x 2 14x1 x 2 3x1,x 2 0答案：5130015X524145 0maxZ4對偶問題：minw 4y1 14y2 3y3y1 3y2 y3 3s.t. 2y1 2y2 y3 2y1 0, y2,3 05、求出下列問題的對偶問題并分別隊原問題及對偶問題求解原問題 : max f (x)5x13x26x3x12x2x3182x1x23x316s.t.x1x2x310x1,x20,x3不限答案：對偶問題 : min g(y) 18y1 16y2 10y3y12y2y3

20、52y1y2y33s.t.y13y2y36y1,y2 0, y3 不限用單純型法求解過程Cj536-600MCBXBbx1x2x 3x3x4x5x60x41812111000x51621(3)3010Mx6101111001OBJ=10MMMMM00Mcj - z j5+M3+M6+M-6-M0000x438/31/35/30011/306x 316/32/31/31101/30Mx614/31/3(2/3)0001/31OBJ=32-14M/34-M/32-2M/36602+M/3Mcj - z j1+M/31+2M/3000-2-M/300x411/200011/25/26x 33(1/2

21、)01101/23/23x271/210001/23/2OBJ=399/236603/23/2cj - z j1/200003/2-M-3/20x4400111135x1610220113x24011(1)012OBJ=425377021cj - z j001102-M+10x4801001015x11412000136x340111012OBJ=465466013cj - z j010001-M 3對偶問題最優(yōu)解：y4=0y5=1y6=0y1=0y2=1 y3=3原問題最優(yōu)解： x1 =14, x2=0, x3=-4, x4=8, x 5=0, x 6=0, OBJ=466、 運輸問題的數(shù)據(jù)

22、如下表：B1B2B3B4產(chǎn)量A12237500A24359600A31678300銷量300200500400求最優(yōu)運輸方案。答案：最優(yōu)方案： f * = 6000B 1B2 B3B4產(chǎn)量A1100 400500A2200400600A3300300銷量300200500 4007、 對于以下運輸問題，如何用最小元素法求出初始調(diào)運方案？答案：求解過程如下。表中“”內(nèi)數(shù)字為刪除線出現(xiàn)的先后順序。8、判斷下表中給出的調(diào)運方案能否作為表上作業(yè)法求解的初始方案？為什么？運 量銷地 產(chǎn) 地量B1B2B3B4B5產(chǎn)量A12525A2201030A32020A452530銷量2020301025105答案：

23、不能作為初始方案。因為數(shù)字格只有 6個，而 n m 1 89、某奶牛站希望通過投資來擴大牛群數(shù)，開始只有5000 元資金，現(xiàn)在已知可購入 A或者 B兩個品種的奶牛， 對于 A種牛每投入 1000 元，當年及以后每年可以獲得 500元和 2 頭小牛， 對B種牛每投入 1000元，當年及以后每年可以獲得 200元和 3頭小牛。問：（1）在今后的四年內(nèi)應該如何分配投資使奶牛群最大（2）到第四年底奶牛站將有多少頭奶牛。答案：狀態(tài) S 為階段 n 可利用的資金；決策 dn為階段 n向 A種牛投入的資金數(shù)；rnS d 為階段 n 向 B 種牛投入的資金數(shù)；遞推函數(shù)：f n(Sn) rn(dn) f n1(

24、Sn1)則轉(zhuǎn)移函數(shù)為 Sn 1 0.2Sn 0.3dn10n00(3Sd n);r 表示在階段 n 出生的小牛數(shù) nS4 5000；第四年末牧場主應擁有的牛的頭數(shù)為 70 頭根據(jù)標號過程找出增廣鏈，確定流量修正量；調(diào)整流量，畫出最大流圖，說明最大流量是多少； 根據(jù)標號和求解過程確定最小割并算出最小割容量；10. 求下面容量網(wǎng)絡的最大流，弧邊上括號內(nèi)第一個數(shù)為容量，第二個數(shù)為流量。（1）、（2）、（3）、解：1. 增廣鏈：(2,2)V2 +V1+V41 min 2,1,3 1V1V2,2 )3,2 )V12,2)-, )V3(V2 ,1)3,3)( 2,0 )(1,1)(3,1)3,1)V6V5(2,2 )V2 ,2)(V4,2)V2V,41 )