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

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

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

3、表的西北角位置開(kāi)始，依次安排m個(gè)產(chǎn)地和n個(gè)銷(xiāo)地之間的運(yùn)輸業(yè)務(wù)，從而得到一個(gè)初始調(diào)運(yùn)方案的方法。 9最優(yōu)性檢驗(yàn)檢驗(yàn)當(dāng)前調(diào)運(yùn)方案是不是最優(yōu)方案的過(guò)程。10動(dòng)態(tài)規(guī)劃解決多階段決策過(guò)程優(yōu)化問(wèn)題的方法：把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wè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)決策，然后反向追蹤，順序地求出改多階段決策問(wèn)題的最優(yōu)策略和最優(yōu)路線。13最短路問(wèn)題最短路徑問(wèn)題是圖論研究中的一個(gè)經(jīng)典算法問(wèn)題， 旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。14最小費(fèi)用最大流在一個(gè)網(wǎng)絡(luò)中每段

4、路徑都有“容量”和“費(fèi)用”兩個(gè)限制的條件下，此類(lèi)問(wèn)題的研究試圖尋找出：流量從A到B，如何選擇路徑、分配經(jīng)過(guò)路徑的流量，可以達(dá)到所用的費(fèi)用最小的要求。15排隊(duì)論排隊(duì)論(queueing theory), 或稱隨機(jī)服務(wù)系統(tǒng)理論, 是通過(guò)對(duì)服務(wù)對(duì)象到來(lái)及服務(wù)時(shí)間的統(tǒng)計(jì)研究，得出這些數(shù)量指標(biāo)（等待時(shí)間、排隊(duì)長(zhǎng)度、忙期長(zhǎng)短等）的統(tǒng)計(jì)規(guī)律，然后根據(jù)這些規(guī)律來(lái)改進(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)于最大利潤(rùn)的線性規(guī)劃問(wèn)題時(shí)，若其等利潤(rùn)線與可行解區(qū)域相交，但不存在可行解區(qū)域最邊緣的等利潤(rùn)線，則該線性規(guī)

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

6、5. 對(duì)問(wèn)題的標(biāo)準(zhǔn)型：，利用單純形表求解時(shí)，每做一次換基迭代，都能保證它相應(yīng)的目標(biāo)函數(shù)值必為（ B ）A 增大 B 不減少 C 減少 D 不增大6. 若最優(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. 用大法求解模型時(shí)，若在最終單純形表上基變量中仍含有非零的人工變量，則原模型（ C ）A 有可行解，但無(wú)最優(yōu)解 B 有最優(yōu)解C 無(wú)可行解D 以上都不

7、對(duì)12. 已知，是某的兩個(gè)最優(yōu)解，則（ D ）也是的最優(yōu)解。A B C D 無(wú)法判斷13、線性規(guī)劃問(wèn)題的靈敏度分析研究（ 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、無(wú)法判斷15、對(duì)偶單純形法求解極大化線性規(guī)劃時(shí)，如果不按照最小化比值的方法選取什么變量則在下一個(gè)解中至少有一個(gè)變量為正（ B ）A、換出變量B、換入變量C、非基變量D、基變量16、影子價(jià)格是指（D）A、檢驗(yàn)數(shù)B、對(duì)偶問(wèn)題的基本

8、解C、解答列取值D、對(duì)偶問(wèn)題的最優(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)輸利潤(rùn)最大的運(yùn)輸方案中，若某方案的空格的改進(jìn)指數(shù)分別為IWB=50元，IWC=-80元，IYA=0元，IXC=20元，則最好挑選( A )為調(diào)整格。 A、WB格 B、WC格 C、YA格 D、XC格19、在一個(gè)運(yùn)輸方案中，從任一數(shù)字格開(kāi)始，( B )一條閉合回路。A可以形成至少 B不能形成C、可以形成 D有可能形成20、運(yùn)輸問(wèn)題可以用( B )法求解。 A、定量預(yù)測(cè) B、單純形 C、求解線性規(guī)劃的圖解 D、關(guān)鍵線路21

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

10、解決多階段決策過(guò)程的問(wèn)題；B、動(dòng)態(tài)規(guī)劃問(wèn)題要考慮決策變量；C、它的目標(biāo)函數(shù)與約束不容易表示； D、它可以通過(guò)時(shí)間或空間劃分一些問(wèn)題為多階段決策過(guò)程問(wèn)題。25、用DP方法處理資源分配問(wèn)題時(shí)，通?？偸沁x階段初資源的擁有量作為決策變量（ B ）A、正確B、錯(cuò)誤C、不一定D、無(wú)法判斷 26、用DP方法處理資源分配問(wèn)題時(shí)，每個(gè)階段資源的投放量作為狀態(tài)變量（ B ）A、正確B、錯(cuò)誤C、不一定D、無(wú)法判斷27、動(dòng)態(tài)規(guī)劃最優(yōu)化原理的含義是：最優(yōu)策略中的任意一個(gè)K-子策略也是最優(yōu)的（ A ）A、正確B、錯(cuò)誤C、不一定D、無(wú)法判斷28動(dòng)態(tài)規(guī)劃的核心是什么原理的應(yīng)用（ A ）A、最優(yōu)化原理B、逆向求解原理C、最大流

11、最小割原理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ī)劃求解工程線路問(wèn)題時(shí)，什么樣的網(wǎng)絡(luò)問(wèn)題可以轉(zhuǎn)化為定步數(shù)問(wèn)題求解（ B ）A、任意網(wǎng)絡(luò)B、無(wú)回路有向網(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)過(guò)程C、給出目標(biāo)函數(shù)值D、給出最優(yōu)策略32用動(dòng)態(tài)規(guī)劃解決生產(chǎn)庫(kù)存的時(shí)候，應(yīng)該特別注意哪些問(wèn)題.（ BC ）A、生產(chǎn)能力B、狀態(tài)變量的允許取值范圍C、決策變量的允許取值范圍D、庫(kù)存容量33. 在網(wǎng)絡(luò)計(jì)劃技術(shù)中，進(jìn)行時(shí)間與成本優(yōu)化時(shí)，一般地說(shuō)，隨著施工周期的縮短，直接費(fèi)用是(

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

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

14、應(yīng)借用（ C ） A、樹(shù)的逐步生成法 B、求最小技校樹(shù)法C、求最短路線法 D、求最大流量法42. 為了在各住宅之間安裝一個(gè)供水管道若要求用材料最省，則應(yīng)使用( B )。A、求最短路法 B、求最小技校樹(shù)法 C、求最大流量法 D、樹(shù)的逐步生成法43排隊(duì)系統(tǒng)狀態(tài)轉(zhuǎn)移速度矩陣中，每一列的元素之和等于0。（ B ）A、正確B、錯(cuò)誤C、不一定D、無(wú)法判斷44. 排隊(duì)系統(tǒng)中狀態(tài)是指系統(tǒng)中的顧客數(shù)（ A ）A、正確B、錯(cuò)誤C、不一定D、無(wú)法判斷45排隊(duì)系統(tǒng)的組成部分有（ ABC ）A、輸入過(guò)程B、排隊(duì)規(guī)則C、服務(wù)機(jī)構(gòu)D、服務(wù)時(shí)間46排隊(duì)系統(tǒng)中，若系統(tǒng)輸入為泊松流，則相繼到達(dá)的顧客間隔時(shí)間服從什么分布（ D ）

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

16、29/41f(x)2122問(wèn)題II的解即原整數(shù)問(wèn)題的最優(yōu)解3、已知線性規(guī)劃問(wèn)題要求：（1）化為標(biāo)準(zhǔn)型式（2）列出用兩階段法求解時(shí)第一階段的初始單純形表解：（1）令 原模型可以轉(zhuǎn)化為（2）見(jiàn)下表000000-11-11515-33-10100205-610-100100-15111-10001-26-22-10004、求下列線性規(guī)劃問(wèn)題，并寫(xiě)出問(wèn)題的對(duì)偶問(wèn)題答案： 對(duì)偶問(wèn)題：5、求出下列問(wèn)題的對(duì)偶問(wèn)題并分別隊(duì)原問(wèn)題及對(duì)偶問(wèn)題求解答案：用單純型法求解過(guò)程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對(duì)偶問(wèn)題最優(yōu)解：y4=0y5=1y6=0y1=0y2=1y3=3原問(wèn)題最優(yōu)解：x1=14, x2=0, x3=-4, x4=8, x5=0, x6=0, OBJ=466、 運(yùn)輸問(wèn)題的數(shù)據(jù)如下表： B1 B2 B3 B4產(chǎn)量A1A2A3 2 2 3 7 4 3 5 9 1 6 7 8500600300銷(xiāo)量 300 200 500 400求最優(yōu)運(yùn)輸方案。答案：最優(yōu)

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

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

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增廣鏈 標(biāo)號(hào)過(guò)程中，圖2為最大流圖，最大流量3. 其節(jié)點(diǎn)均屬則最小割為，最小割容量為3+2=511、一臺(tái)研磨機(jī)對(duì)某種工件進(jìn)行加工，研磨一個(gè)工件的時(shí)間服從負(fù)指數(shù)分布，平均需要2分鐘。