運籌學復習題

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

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

3、表的西北角位置開始，依次安排m個產地和n個銷地之間的運輸業(yè)務，從而得到一個初始調運方案的方法。 9最優(yōu)性檢驗檢驗當前調運方案是不是最優(yōu)方案的過程。10動態(tài)規(guī)劃解決多階段決策過程優(yōu)化問題的方法：把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解11狀態(tài)轉移方程從階段K到K+1的狀態(tài)轉移規(guī)律的表達式12逆序求解法在求解時，首先逆序求出各階段的條件最優(yōu)目標函數(shù)和條件最優(yōu)決策，然后反向追蹤，順序地求出改多階段決策問題的最優(yōu)策略和最優(yōu)路線。13最短路問題最短路徑問題是圖論研究中的一個經典算法問題， 旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。14最小費用最大流在一個網絡中每段

4、路徑都有“容量”和“費用”兩個限制的條件下，此類問題的研究試圖尋找出：流量從A到B，如何選擇路徑、分配經過路徑的流量，可以達到所用的費用最小的要求。15排隊論排隊論(queueing theory), 或稱隨機服務系統(tǒng)理論, 是通過對服務對象到來及服務時間的統(tǒng)計研究，得出這些數(shù)量指標（等待時間、排隊長度、忙期長短等）的統(tǒng)計規(guī)律，然后根據(jù)這些規(guī)律來改進服務系統(tǒng)的結構或重新組織被服務對象，使得服務系統(tǒng)既能滿足服務對象的需要，又能使機構的費用最經濟或某些指標最優(yōu)。二、選擇題1. 用圖解法求解一個關于最大利潤的線性規(guī)劃問題時，若其等利潤線與可行解區(qū)域相交，但不存在可行解區(qū)域最邊緣的等利潤線，則該線性規(guī)

5、劃問題( B )。 A、有無窮多個最優(yōu)解 B、有可行解但無最優(yōu)解 C、有可行解且有最優(yōu)解 D、無可行解2. 若線性規(guī)劃問題的最優(yōu)解同時在可行解域的兩個頂點處達到，則此線性規(guī)劃問題的最優(yōu)解為（ B ）A、兩個 B、無窮多個C、零個 D、過這的點直線上的一切點3. 用圖解法求解一個關于最小成本的線性規(guī)劃問題時，若其等成本線與可行解區(qū)域的某一條邊重合，則該線性規(guī)劃問題( A )。A有無窮多個最優(yōu)解B、有有限個最優(yōu)解C有唯一的最優(yōu)解D無最優(yōu)解4. 在求極小值的線性規(guī)劃問題中，引入人工變量之后，還必須在目標函數(shù)中分別為它們配上系數(shù)，這些系數(shù)值應為( A )。A、很大的正數(shù) B、較小的正數(shù) C、1 D、0

6、5. 對問題的標準型：，利用單純形表求解時，每做一次換基迭代，都能保證它相應的目標函數(shù)值必為（ B ）A 增大 B 不減少 C 減少 D 不增大6. 若最優(yōu)解不唯一，則在最優(yōu)單純形表上（ A ）A 非基變量的檢驗數(shù)必有為零者 B 非基變量的檢驗數(shù)不必有為零者C 非基變量的檢驗數(shù)必全部為零 D 以上均不正確7. 求解線性規(guī)劃模型時，引入人工變量是為了（ B ）A 使該模型存在可行解 B 確定一個初始的基可行解C 使該模型標準化 D 以上均不正確11. 用大法求解模型時，若在最終單純形表上基變量中仍含有非零的人工變量，則原模型（ C ）A 有可行解，但無最優(yōu)解 B 有最優(yōu)解C 無可行解D 以上都不

7、對12. 已知，是某的兩個最優(yōu)解，則（ D ）也是的最優(yōu)解。A B C D 無法判斷13、線性規(guī)劃問題的靈敏度分析研究（ BC ） A、對偶單純形法的計算結果； B、目標函數(shù)中決策變量系數(shù)的變化與最優(yōu)解的關系； C、資源數(shù)量變化與最優(yōu)解的關系； D、最優(yōu)單純形表中的檢驗數(shù)與影子價格的聯(lián)系。14、對偶單純形法迭代中的主元素一定是負元素（ A ）A、正確B、錯誤C、不一定D、無法判斷15、對偶單純形法求解極大化線性規(guī)劃時，如果不按照最小化比值的方法選取什么變量則在下一個解中至少有一個變量為正（ B ）A、換出變量B、換入變量C、非基變量D、基變量16、影子價格是指（D）A、檢驗數(shù)B、對偶問題的基本

8、解C、解答列取值D、對偶問題的最優(yōu)解17、影子價格的經濟解釋是（ C ）A、判斷目標函數(shù)是否取得最優(yōu)解B、價格確定的經濟性C、約束條件所付出的代價D、產品的產量是否合理18、在總運輸利潤最大的運輸方案中，若某方案的空格的改進指數(shù)分別為IWB=50元，IWC=-80元，IYA=0元，IXC=20元，則最好挑選( A )為調整格。 A、WB格 B、WC格 C、YA格 D、XC格19、在一個運輸方案中，從任一數(shù)字格開始，( B )一條閉合回路。A可以形成至少 B不能形成C、可以形成 D有可能形成20、運輸問題可以用( B )法求解。 A、定量預測 B、單純形 C、求解線性規(guī)劃的圖解 D、關鍵線路21

9、、在運輸問題的表上作業(yè)法選擇初始基本可行解時，必須注意（ AD ）。 A、針對產銷平衡的表； B、位勢的個數(shù)與基變量個數(shù)相同； C、填寫的運輸量要等于行、列限制中較大的數(shù)值； D、填寫的運輸量要等于行、列限制中較小的數(shù)值。22、用增加虛設產地或者虛設銷地的方法可將產銷不平衡的運輸問題化為產銷平衡的運輸問題 （ A ）A、正確B、錯誤C、不一定D、無法判斷23、通過什么方法或者技巧可以把產銷不平衡運輸問題轉化為產銷平衡運輸問題( C )A、非線性問題的線性化技巧B、靜態(tài)問題的動態(tài)處理C、引入虛擬產地或者銷地D、引入人工變量24、動態(tài)規(guī)劃方法不同于線性規(guī)劃的主要特點是（ AD ）。A、動態(tài)規(guī)劃可以

10、解決多階段決策過程的問題；B、動態(tài)規(guī)劃問題要考慮決策變量；C、它的目標函數(shù)與約束不容易表示； D、它可以通過時間或空間劃分一些問題為多階段決策過程問題。25、用DP方法處理資源分配問題時，通常總是選階段初資源的擁有量作為決策變量（ 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、最大流

11、最小割原理D、網絡分析原理29動態(tài)規(guī)劃求解的一般方法是什么.（ C ）A、圖解法B、單純形法C、逆序求解D、標號法30用動態(tài)規(guī)劃求解工程線路問題時，什么樣的網絡問題可以轉化為定步數(shù)問題求解（ B ）A、任意網絡B、無回路有向網絡C、混合網絡D、容量網絡31動態(tài)規(guī)劃的求解的要求是什么（ ACD ）A、給出最優(yōu)狀態(tài)序列B、給出動態(tài)過程C、給出目標函數(shù)值D、給出最優(yōu)策略32用動態(tài)規(guī)劃解決生產庫存的時候，應該特別注意哪些問題.（ BC ）A、生產能力B、狀態(tài)變量的允許取值范圍C、決策變量的允許取值范圍D、庫存容量33. 在網絡計劃技術中，進行時間與成本優(yōu)化時，一般地說，隨著施工周期的縮短，直接費用是(

12、 C )。A、降低的 B、不增不減的 C、增加的 D、難以估計的34. 最小枝權樹算法是從已接接點出發(fā)，把( C )的接點連接上 A、最遠 B、較遠 C、最近 D、較近35. 在箭線式網絡固中，( D )的說法是錯誤的。A、結點不占用時間也不消耗資源B、結點表示前接活動的完成和后續(xù)活動的開始C、箭線代表活動D、結點的最早出現(xiàn)時間和最遲出現(xiàn)時間是同一個時間36. 如圖所示，在鍋爐房與各車間之間鋪設暖氣管最小的管道總長度是( C )。 A 、1200 B、1400 C、1300 D、1700600700300500400鍋爐房12337. 在求最短路線問題中，已知起點到A，B，C三相鄰結點的距離分

13、別為15km，20 km25km，則（ D ）。 A、最短路線定通過A點 B、最短路線一定通過B點C、最短路線一定通過C點 D、不能判斷最短路線通過哪一點38. 在一棵樹中，如果在某兩點間加上條邊，則圖一定( A ) A、存在一個圈 B、存在兩個圈C、存在三個圈D、不含圈39 網絡圖關鍵線路的長度( C )工程完工期。 A大于 B小于 C等于 D不一定等于40. 在計算最大流量時，我們選中的每一條路線( C )。A、一定是一條最短的路線 B、一定不是一條最短的路線C、是使某一條支線流量飽和的路線 D、是任一條支路流量都不飽和的路線41. 從甲市到乙市之間有公路網絡，為了盡快從甲市驅車趕到乙市，

14、應借用（ C ） A、樹的逐步生成法 B、求最小技校樹法C、求最短路線法 D、求最大流量法42. 為了在各住宅之間安裝一個供水管道若要求用材料最省，則應使用( B )。A、求最短路法 B、求最小技校樹法 C、求最大流量法 D、樹的逐步生成法43排隊系統(tǒng)狀態(tài)轉移速度矩陣中，每一列的元素之和等于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、服務機構D、服務時間46排隊系統(tǒng)中，若系統(tǒng)輸入為泊松流，則相繼到達的顧客間隔時間服從什么分布（ D ）

15、A、正態(tài)分布B、愛爾朗分布C、泊松流D、負指數(shù)分布47研究排隊模型及數(shù)量指標的思路是首先明確系統(tǒng)的意義，然后（ ABC ）A、寫出狀態(tài)概率方程B、寫出狀態(tài)轉移速度矩陣C、畫出狀態(tài)轉移速度圖D、寫出相應的微分方程48排隊系統(tǒng)的狀態(tài)轉移速度矩陣中（ B ）元素之和等于零。A、每一列B、每一行C、對角線D、次對角線三、計算題1.用圖解法求解下列問題答案：依題有可得最優(yōu)解集合為 也即最優(yōu)值為 （詳細求解過程略去）2. 用分枝界定法求解下列線性規(guī)劃問題答案：松弛問題的最優(yōu)解為 x1=2.5, x2=2, OBJ=23 由x1=2.5 得到兩個分枝如下： 和 各個分枝問題的松弛解為問題I問題IIx123x

16、29/41f(x)2122問題II的解即原整數(shù)問題的最優(yōu)解3、已知線性規(guī)劃問題要求：（1）化為標準型式（2）列出用兩階段法求解時第一階段的初始單純形表解：（1）令 原模型可以轉化為（2）見下表000000-11-11515-33-10100205-610-100100-15111-10001-26-22-10004、求下列線性規(guī)劃問題，并寫出問題的對偶問題答案： 對偶問題：5、求出下列問題的對偶問題并分別隊原問題及對偶問題求解答案：用單純型法求解過程Cj 536-600-MCBXBbx1x2x3x3x4x5x60x418121-11000x51621(3)-3010-Mx610111-1001

17、OBJ=-10M-M-M-MM00-Mcj - zj5+M3+M6+M-6-M0000x438/31/35/3001-1/306x316/32/31/31-101/30-Mx614/31/3(2/3)000-1/31OBJ=32-14M/34-M/32-2M/36-602+M/3-Mcj - zj1+M/31+2M/3000-2-M/300x41-1/200011/2-5/26x33(1/2)01-101/2-3/23x271/21000-1/23/2OBJ=399/236-603/23/2cj - zj1/20000-3/2-M-3/20x44001-111-35x16102-201-13x

18、2401-1(1)0-12OBJ=42537-702-1cj - zj00-110-2-M+10x48010010-15x11412000-13-6x3401-110-12OBJ=46546-6013cj - zj0-1000-1-M-3對偶問題最優(yōu)解：y4=0y5=1y6=0y1=0y2=1y3=3原問題最優(yōu)解：x1=14, x2=0, x3=-4, x4=8, x5=0, x6=0, OBJ=466、 運輸問題的數(shù)據(jù)如下表： B1 B2 B3 B4產量A1A2A3 2 2 3 7 4 3 5 9 1 6 7 8500600300銷量 300 200 500 400求最優(yōu)運輸方案。答案：最優(yōu)

19、方案： f * = 6000 B1 B2 B3 B4產量A1A2A3 100 400 200 400 300 500600300銷量 300 200 500 4007、 對于以下運輸問題，如何用最小元素法求出初始調運方案. 答案：求解過程如下。表中“”內數(shù)字為刪除線出現(xiàn)的先后順序。8、判斷下表中給出的調運方案能否作為表上作業(yè)法求解的初始方案.為什么.銷地運量產地產量2525201030202052530銷量2020301025105答案：不能作為初始方案。因為數(shù)字格只有6個，而9、某奶牛站希望通過投資來擴大牛群數(shù)，開始只有5000元資金，現(xiàn)在已知可購入A或者B兩個品種的奶牛，對于A種牛每投入1

20、000元，當年及以后每年可以獲得500元和2頭小牛，對種牛每投入1000元，當年及以后每年可以獲得200元和3頭小牛。問：（1）在今后的四年內應該如何分配投資使奶牛群最大（2）到第四年底奶牛站將有多少頭奶牛。答案：狀態(tài)為階段可利用的資金；決策為階段向種牛投入的資金數(shù)；為階段向種牛投入的資金數(shù)；則轉移函數(shù)為遞推函數(shù)：表示在階段出生的小牛數(shù)；第四年末牧場主應擁有的牛的頭數(shù)為70頭10.求下面容量網絡的最大流，弧邊上括號內第一個數(shù)為容量，第二個數(shù)為流量。（1）、根據(jù)標號過程找出增廣鏈，確定流量修正量；（2）、調整流量，畫出最大流圖，說明最大流量是多少；（3）、根據(jù)標號和求解過程確定最小割并算出最小割

21、容量； V2 V4 (3,2) (4,1) V1 (3,1) (1,1) (3,1) V6 (2,0) (2,2) (3,1) (2,2) V3 V5、解：V1V22+V4V63+1+ 1.增廣鏈：（,1）（,2）V2V4（,3）（3,3）（4,2）（-,）V1V6（3,2）(1,1)（3,1）（2,0）V3V5（2,2）（3,1）（2,2）（,2）圖1（,1）（,1） 2.V2V4（,2）（3,3）（4,3）（-,）V1V6（3,3）（3,0）（2,1）(1,1)V3V5（2,2）（3,1）（2,2）（,2）圖2+V6V4-+2+2V511V2V1增廣鏈 標號過程中，圖2為最大流圖，最大流量3. 其節(jié)點均屬則最小割為，最小割容量為3+2=511、一臺研磨機對某種工件進行加工，研磨一個工件的時間服從負指數(shù)分布，平均需要2分鐘。