運籌學復習題精選

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

2、統(tǒng)（或模型）的狀態(tài)或輸出變化對系統(tǒng)參數(shù)或周圍條件變化的敏感程度的方法。 在最優(yōu)化方法中經常利用靈敏度分析來研究原始數(shù)據不準確或發(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最短路問題 最短路徑問題是圖論研究屮的一個經典算法問題，旨在尋找圖（由結點和路徑組成的）屮兩結點之間 的最短路徑

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

5、 在可行解區(qū)域最邊緣的等利潤線，則該線性規(guī)劃問題（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、很大的

6、正數(shù) B、較小的正數(shù)C、1 D、05. 對LP問題的標準型：max Z 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ī)劃模型時，引入人工變量是為了（ B ）A使該模型存在可行解B確定一個初始的基可行解C使該模型標準化D以上均不正確II.用大M法求解LP模型時，若在最終單純形表上基變量中仍含有非零的人工變量，則 原模型（c ）A有可行解，但無最

7、優(yōu)解B有最優(yōu)解C無可行解D以上都不對12.已fV(2,4),2 （4,8）是某LP的兩個最優(yōu)解，D ）也是LP的最優(yōu)解。AX(4, 4)BX(1,2)CX(2, 3)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

8、、換入變量C、非基變量D、基變量16、影子價格是指（D）A、檢驗數(shù)B、對偶問題的基本解C、解答列取值D、對偶問題的最優(yōu)解17、影子價格的經濟解釋是（ C ）A、判斷目標函數(shù)是否取得最優(yōu)解B、價格確定的經濟性C、約束條件所付出的代價D、18、19、20、21、產品的產量是否合理在總運輸利潤最大的運輸方案中，若某方案的空格的改進指數(shù)分別為I wc二-80元，Iya二0元，Ixc二20元，則最好挑選（A ）為調整格。 A、 WB 格 B、 WC 格 C、 YA 格在一個運輸方案中，A 可以形成至少C、可以形成運輸問題可以用（A、定量預測在運輸問題的表上作業(yè)法選擇初始基本可行解時，必須注意（D、XC

9、格（B ） 一條閉合回路。Iwb=50 元,BB、從任一數(shù)字格開始，B 不能形成D 有可能形成）法求解。單純形 C、求解線性規(guī)劃的圖解D、關鍵線路AD ） oA、針對產銷平衡的表；B、位勢的個數(shù)與基變量個數(shù)相同;C、填寫的運輸量要等于行、列限制中較大的數(shù)值;D、填寫的運輸量要等于行、列限制屮較小的數(shù)值。22、用增加虛設產地或者虛設銷地的方法可將產銷不平衡的運輸問題化為產銷平衡的運輸 問題（A ）A正確B、錯誤C、不一定D、無法判斷23、通過什么方法或者技巧可以把產銷不平衡運輸問題轉化為產銷平衡運輸問題（C ）A、非線性問題的線性化技巧B、靜態(tài)問題的動態(tài)處理C、引入虛擬產地或者銷地D、引入人工變

10、量24、動態(tài)規(guī)劃方法不同于線性規(guī)劃的主要特點是（AD ）。A、動態(tài)規(guī)劃可以解決多階段決策過程的問題；B、動態(tài)規(guī)劃問題要考慮決策變量；C、它的目標函數(shù)與約束不容易表示；D、它可以通過時間或空間劃分一些問題為多階段決策過程問題。25、用DP方法處理資源分配問題時，通?？偸沁x階段初資源的擁有量作為決策變量（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ī)劃的

11、核心是什么原理的應用（ A ）A、最優(yōu)化原理B、逆向求解原理C、最大流最小割原理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.

12、在網絡計劃技術中，進行時間與成本優(yōu)化時，一般地說，隨著施工周期的縮短，直接費word.用是（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 ） o1400D、仃00A 、1200 B、C、 1300在求最短路線問題中，已知起點到A, B,

13、 C三相鄰結點的距離分別為25km,則（D） oA、最短路線一定通過A點B、最短路線疋通過 B點C、最短路線疋通過 C點D、不能判斷最短路線通過哪一點15km, 20 km38.在一棵樹中，如果在某兩點間加上條邊，則圖一定（A ）A、存在一個圈B、存在兩個圈C、存在三個圈D、不含圈）工程完工期。39網絡圖關鍵線路的長度（CA .大于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)轉移速度矩陣中，每一列的元素之和等于0o （ 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 ）A

15、、正態(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.用圖解法求解下列LP問題J 2問題1問題IIX123X29/41f(x)2122問題II的解即原整數(shù)問題的最優(yōu)解(xi, x2)l(xi，x2)a(2,3)(1 a) (4, 2), 0 a 1也即( Y， V ) i (V Y)(4 2a, 2 a), 0 a oAi A2

16、Ai A2最優(yōu)值為z 8 (詳細求解過程略去)2.用分枝界定法求解下列線性規(guī)劃問題 max f (x) 6X1 4x22xi 4x2132xi X2兒， 0且為整數(shù)答案：松弛問題的最優(yōu)解為Xi二2. 5, X2二2, 0BJ-23由Xi二2. 5得到兩個分枝如下：max f (x) 6x. 4x?2尢 4X=13問題込 X： 7Xx 2X., X： 0且為整數(shù) 各個分枝問題的松弛解為2兒4x213和2XX271問題IIX 3Xr, X:0且為整數(shù)max f (x) 6x 4x23、己知線性規(guī)劃問題5y 6V 7Vmaxz Ai A2 A3s. t.XT 、T5要求：（1）化為標準型式（2）列出

17、用兩階段法求解時第一階段的初始單純形解：（1 ）令.原模型可以X； X3 X * X3 心 轉化為% 6X2 % %，X50 Z Z1520（2）見卜表000000-11X/X/XITX/X/X/-1x61515-33-10100x5205_610-100100-1X.5111-10001C/乙26-22-10004、求下列線性規(guī)劃問題，并寫出 LP問題的對偶問題maXZY 2V4Ai A23y. 2y 14S t oXx X2 3X】，X2 0答案：513 c ciC /|X 1 20 0_L. 04才max Z4對偶問題:minw 4Yi 14丫2 3丫3y迥2出彳2 2 Tr 2s.t.

18、 Yi y2 y0yi $2,35、求出下列問題的對偶問題并分別隊原問題及對偶問題求解原問題:max f (x)5x3X26X3Xi 2x=X3182xi X：3x316c tX X：X310x, X： 0,X3不限答案:對偶問題:ming(y) 18y 16y?叭,2yi*3J%, 丫 2 0, ys 不限c 4-Vi 3y2V3 6單純型法求解過*2y： V3 5flCbc；5Xi3X26Xl-6X30X40X5MX6Xbb0X41812111000X51621(3)3010MX6101111001OBJ 二10MMMMM00MCj - Zj5+M3+M6+M-6-M0000X438/31

19、/35/30011/306X，316/32/31/31101/30MX614/31/3(2/3)0001/31OBJ 二32-14M/34-M/32-2M/36602+M/3MCj - Zjl+M/31+2M/3000-2-M/300X411/200011/25/26X，33(1/2)01101/23/23X271/210001/23/2OBJ 二399/236603/23/2Cj - Zj1/200003/2-M-3/20X-i400111135Xi610220113X24011(1)012OBJ 二125377021Cj - Zj001102-M+l0X4801001015Xi141200

20、0136X340111012OBJ 二465466013Cj - Zj i 010001 -M 3對偶問題最優(yōu)解： y4=0 y5=ly6二0yi二0 y2二 1 y3二3原冋題最優(yōu)解：xi 二 i4, X2 二 0, X3 二-4, X4 二& X5 二 0, Xe=O, OB J 二 466、運輸問題的數(shù)據如下表:BiB2BsBi產量Ai2237500A24359600A31678300銷量300200500400求最優(yōu)運輸方案。答案：最優(yōu)方案：f *二6000BiB2B3Bi產皿ai r100400500A2200400600A3300300銷量3002005004007、對于以下運輸問

21、題，如何用最小元素法求出初始調運方案?單隹、銷地；產量*11+IE豹非AJQ%10*答案：求解過程如下。表屮數(shù)字為刪除線出現(xiàn)的先后順序。t= t舅運方案耒單位飛孵-1乍 匸B2*B尹1.S114-f*可AIP V 4 V6I 匚一n 1匚2 1-2.增廣鏈2 min 1,2,1,21標號過程中，圖2為最大流圖，最大流量 fmax 3 2 53.S Vi 其節(jié)點均屬s 則最小割為(S, S) (VM), MM),最小割容量為3+2二511、一臺研磨機對某種工件進行加工，研磨一個工件的時間服從負指數(shù)分布，平均需要2分鐘。工件的到達服從泊松分布，平均每小時到達25件。試求：該研磨機空閑的概率和恰巧有5件工件等待研磨的概率？每件工