運(yùn)籌學(xué)-學(xué)習(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 對(duì)偶理論每一個(gè)線性規(guī)劃問題都存在一個(gè)與其對(duì)偶的問題，在求出一個(gè)問題解的同時(shí)，也給出了另一個(gè)問題的解。研究線性規(guī)劃中原始問題與對(duì)偶問題之間關(guān)系的理論5 靈敏度分析研究與

2、分析一個(gè)系統(tǒng)（或模型）的狀態(tài)或輸出變化對(duì)系統(tǒng)參數(shù)或周圍條件變化的敏感程度的方法。在最優(yōu)化方法中經(jīng)常利用靈敏度分析來研究原始數(shù)據(jù)不準(zhǔn)確或發(fā)生變化時(shí)最優(yōu)解的穩(wěn)定性。通過靈敏度分析還可以決定哪些參數(shù)對(duì)系統(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)輸問題的初始調(diào)運(yùn)方案（即初始基可行

3、解）的基本方法之一。也就是從運(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 動(dòng)態(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)典算法問題，旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)

4、之間的最短路徑。14 最小費(fèi)用最大流A 到 B ，如何選擇路在一個(gè)網(wǎng)絡(luò)中每段路徑都有“容量”和“費(fèi)用”兩個(gè)限制的條件下，此類問題的研究試圖尋找出：流量從徑、分配經(jīng)過路徑的流量，可以達(dá)到所用的費(fèi)用最小的要求。15 排隊(duì)論排隊(duì)論 (queueing theory), 或稱隨機(jī)服務(wù)系統(tǒng)理論 , 是通過對(duì)服務(wù)對(duì)象到來及服務(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ù)對(duì)象，使得服務(wù)系統(tǒng)既能滿足服務(wù)對(duì)象的需要，又能使機(jī)構(gòu)的費(fèi)用最經(jīng)濟(jì)或某些指標(biāo)最優(yōu)。.精品文檔二、選擇題1. 用圖解法求解一個(gè)關(guān)于最大利潤的線性規(guī)劃問題時(shí)，若

5、其等利潤線與可行解區(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ī)劃問題中，引入人工變量之后，還必須在目標(biāo)函數(shù)中分別為它們配上系數(shù)，這些系

6、數(shù)值應(yīng)為 (A )。A 、很大的正數(shù)B、較小的正數(shù)C、 1D 、 05.對(duì) LP 問題的標(biāo)準(zhǔn)型：max ZCX,AXb, X0 ，利用單純形表求解時(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 以上均不正確11.用大 M 法求解 LP 模型時(shí)，若在最終單純形表上基變量

7、中仍含有非零的人工變量，則原模型（C ）A 有可行解，但無最優(yōu)解B 有最優(yōu)解C 無可行解D 以上都不對(duì)12.已知 x1(2,4) ， x2(4,8)是某 LP 的兩個(gè)最優(yōu)解，則（D ）也是 LP 的最優(yōu)解。A x(4,4)Bx (1,2)C x (2,3)D 無法判斷13、線性規(guī)劃問題的靈敏度分析研究（BC）A 、對(duì)偶單純形法的計(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、對(duì)偶單純形法迭代中的主元素一定是負(fù)元素（A）A 、正確B、錯(cuò)誤C、不一定D、無法判斷15、對(duì)偶單純形法求解極大化線性規(guī)劃時(shí)，

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

9、一個(gè)運(yùn)輸方案中，從任一數(shù)字格開始，(B)一條閉合回路。A 可以形成至少B不能形成C、可以形成D 有可能形成20、運(yùn)輸問題可以用(B)法求解。A 、定量預(yù)測(cè)B 、單純形C、求解線性規(guī)劃的圖解D 、關(guān)鍵線路21、在運(yùn)輸問題的表上作業(yè)法選擇初始基本可行解時(shí)，必須注意（AD）。A 、針對(duì)產(chǎn)銷平衡的表；B 、位勢(shì)的個(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 ）A 、正確B 、錯(cuò)誤C、不一定D 、無法判斷23、通過什么方法或者技巧可以

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

11、、不一定D 、無法判斷27、動(dòng)態(tài)規(guī)劃最優(yōu)化原理的含義是：最優(yōu)策略中的任意一個(gè)K- 子策略也是最優(yōu)的（A ）A 、正確B、錯(cuò)誤C、不一定D 、無法判斷28動(dòng)態(tài)規(guī)劃的核心是什么原理的應(yīng)用（A）A 、最優(yōu)化原理B 、逆向求解原理C、最大流最小割原理D、網(wǎng)絡(luò)分析原理29動(dòng)態(tài)規(guī)劃求解的一般方法是什么？（C ）A 、圖解法B、單純形法C、逆序求解D、標(biāo)號(hào)法30用動(dòng)態(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動(dòng)態(tài)規(guī)劃的求解的要求是什么（ACD）A 、給出最優(yōu)狀態(tài)序列B、給出動(dòng)態(tài)過程C、給出目標(biāo)函數(shù)值D 、給出最優(yōu)策略3

12、2用動(dòng)態(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)表示前接活動(dòng)的完成和后續(xù)活動(dòng)的開始C、箭線代表活動(dòng)D 、結(jié)點(diǎn)的最早出現(xiàn)時(shí)間和最遲出現(xiàn)時(shí)間是同一個(gè)時(shí)間36. 如圖所示

13、，在鍋爐房與各車間之間鋪設(shè)暖氣管最小的管道總長度是(C)。A 、 1200B、 1400C、 1300D、 170037. 在求最短路線問題中，已知起點(diǎn)到1A ， B， C 三相鄰結(jié)點(diǎn)的距離分別為 15km ， 20 km25km ，則（ D）。500400A 點(diǎn)B 點(diǎn)A 、最短路線 定通過B 、最短路線一定通過C、最短路線一定通過C 點(diǎn)300D、不能判斷最短路線通過哪一點(diǎn)鍋爐房( A)338. 在一棵樹中，如果在某兩點(diǎn)間加上條邊，則圖一定A 、存在一個(gè)圈B、存在兩個(gè)圈C、存在三個(gè)圈700D 、不含圈 60039網(wǎng)絡(luò)圖關(guān)鍵線路的長度( C)工程完工期。A 大于B 小于2C等于D不一定等于40.

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

15、態(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、對(duì)角線D、次對(duì)角線三、計(jì)算題1.用圖解法求解下列LP 問題max

16、zx 2x122 x12 x212x12x28s.t 4 x1164 x212x1, x2 0答案：依題有可得最優(yōu)解集合為( x1, x2) | ( x1, x2)a(2,3) (1a)(4,2),0a 1也即( x1, x2) | ( x1, x2)(4 2a ,2a ),0 a1最優(yōu)值為z8（詳細(xì)求解過程略去）2. 用分枝界定法求解下列線性規(guī)劃問題max f (x)6x14 x22x14x2132x1x27x1 , x20 且為整數(shù)答案：松弛問題的最優(yōu)解為x12=2.5, x =2, OBJ=23由 x1=2.5得到兩個(gè)分枝如下：.精品文檔max f (x)12max f ( x)6x14

17、x26x4x2x14x21312132x4x2x1x27127和問題2xx問題 IIIx12x13120且為整數(shù)x1 , x20且為整數(shù)x , x各個(gè)分枝問題的松弛解為問題 I問題 IIx123x29/41f(x)2122問題 II的解即原整數(shù)問題的最優(yōu)解3、已知線性規(guī)劃問題max z5x1 6x27x3x1 5x23x315s.t.5x16x210x320x1x2 x35x1, x20 , x3無約束要求：（ 1）化為標(biāo)準(zhǔn)型式（ 2）列出用兩階段法求解時(shí)第一階段的初始單純形表解：（ 1）令x1'x;x3x3'x3'',x3'、''0，

18、z z 'x3原模型可以轉(zhuǎn)化為x1 ' x; x3x3 'x3 '', x3 '、，zz 'x3 ''0x1 ' 5x 2 3x3 ' 3x3 '' x4x6 155x1 ' 6x2 10 x3 ' 10 x3 '' x520x1 ' x2x3 ' x3 '' x75x1 ', x2, x3 ', x3 '', x4, x5, x6, x70（ 2）見下表000000-11x1 'x2 &

19、#39;x3 'x3 ''x4 'x5 'x6 'x7 '-1x61515-33-10100x5205-610-100100-1x75111-10001cj-zj26-22-10004、求下列線性規(guī)劃問題，并寫出LP 問題的對(duì)偶問題.精品文檔max z 3x12 x 2x 12 x 24s.t.3 x12 x 214x1x 23答案：x1, x 20X51315000244max Z4對(duì)偶問題：min w4 y114 y23 y3y13y2y33s.t. 2 y12 y2y32y10, y2,305、求出下列問題的對(duì)偶問題并分別隊(duì)原問題及

20、對(duì)偶問題求解原問題 : max f ( x)5x13 x26x3x12x2x3182 x1x23x316st.x2x310x1x1 , x20, x3不限答案：對(duì)偶問題 : min g ( y)18y116y2 10y3y12 y2y352 y1y2y33s.t3y2y36y1y1 , y20, y3不限用單純型法求解過程Cj536-600MCBXBbx1x2x'3x" 3x4x5x60x41812111000x51621(3)3010Mx6101111001OBJ=10MMMMM00Mcj - zj5+M3+M6+M-6-M0000x438/31/35/30011/306x

21、'316/32/31/31101/30Mx614/31/3(2/3)0001/31OBJ=32-14M/34-M/32-2M/36602+M/3Mcj - zj1+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/20x4400111135x1610220113x24011(1)012OBJ=425377021.精品文檔cj- z001102-M+1j0x4801001015x11412000136x&

22、quot; 340111012OBJ=465466013cj- z010001-M 3j對(duì)偶問題最優(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、 運(yùn)輸問題的數(shù)據(jù)如下表：B1B2B3B4產(chǎn)量A12237500A24359600A31678300銷量300200500400求最優(yōu)運(yùn)輸方案。答案：最優(yōu)方案：f * = 6000B 1B 2B 3B4產(chǎn)量A 1100400500A 2200400600A 3300300銷量3002005004007、 對(duì)于以下運(yùn)輸問題，如何用

23、最小元素法求出初始調(diào)運(yùn)方案？答案：求解過程如下。表中“”內(nèi)數(shù)字為刪除線出現(xiàn)的先后順序。.精品文檔8、判斷下表中給出的調(diào)運(yùn)方案能否作為表上作業(yè)法求解的初始方案？為什么？運(yùn)銷地B1B 2B3B 4B 5產(chǎn)量量產(chǎn)地A12525A2201030A32020A452530銷量2020301025105答案：不能作為初始方案。因?yàn)閿?shù)字格只有 6個(gè)，而 n m189、某奶牛站希望通過投資來擴(kuò)大牛群數(shù)，開始只有5000 元資金，現(xiàn)在已知可購入A 或者 B 兩個(gè)品種的奶牛，對(duì)于A 種牛每投入 1000元，當(dāng)年及以后每年可以獲得500元和 2頭小牛，對(duì)B 種牛每投入 1000元，當(dāng)年及以后每年可以獲得200 元和

24、 3頭小牛。問：（ 1）在今后的四年內(nèi)應(yīng)該如何分配投資使奶牛群最大（ 2）到第四年底奶牛站將有多少頭奶牛。答案：狀態(tài) Sn 為階段 n 可利用的資金；決策 dn 為階段 n 向 A 種牛投入的資金數(shù)；Sndn 為階段 n 向 B 種牛投入的資金數(shù)；則轉(zhuǎn)移函數(shù)為 Sn 10.2Sn0.3d n遞推函數(shù)：f n(Sn)r n(d n)f n 1(Sn 1)r nn(3Sn d n );1000r n 表示在階段 n 出生的小牛數(shù)S5000；4第四年末牧場主應(yīng)擁有的牛的頭數(shù)為70 頭10. 求下面容量網(wǎng)絡(luò)的最大流，弧邊上括號(hào)內(nèi)第一個(gè)數(shù)為容量，第二個(gè)數(shù)為流量。（ 1）、根據(jù)標(biāo)號(hào)過程找出增廣鏈，確定流量

25、修正量；（ 2）、調(diào)整流量，畫出最大流圖，說明最大流量是多少；（ 3）、根據(jù)標(biāo)號(hào)和求解過程確定最小割并算出最小割容量；V 2V 4(3,2)(4,1)V 1(3,1)(1,1)(3,1)V 6(2,0)(2,2)(3,1)(2,2)V 3V 5、解：1.增廣鏈：+V 41 min 2,1,31V 1V 2V 6213（ V,2）（ 3,3）（ V2V,14） （ 4,2）（ -,）1V2（ V4 ,3）（ 3,2）.V 1(1,1)（ 2,0）（ 3,1）V 6精品文檔（ 2,2）V3（3,1）V（ 2,2）5(V2,1)圖 1（ V2,2）(V4, 2)(V3, 2)2.（ V1 ,1）（ V5 ,1）（ -,）V 2（ 3,3）V 4（ 4,3）（ 3,3）（ V4 ,2）V 1(1,1)（ 2,1） （ 3,0）V 6（ 2,2）V 3（ 3,1）V 5（ 2,2）圖 2（ V2 ,2）增廣鏈V 1+V2+V 5-+V 6121V 42 min1,2,1, 21