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

運(yùn)籌學(xué)-學(xué)習(xí)指南一、名詞解釋1松弛變量為將線性規(guī)劃問(wèn)題的數(shù)學(xué)模型化為原則型而加入的變量。2可行域滿足線性約束條件的解（x,y）叫做可行解，由所有可行解構(gòu)成的集合叫做可行域。3人工變量亦稱人造變量.求解線性規(guī)劃問(wèn)題時(shí)人為加入的變量。用單純形法求解線性規(guī)劃問(wèn)題，都是在具有初始可行基的條件下進(jìn)行的,但約束方程組的系數(shù)矩陣A中所含的單位向量常常局限性m個(gè)，此時(shí)可加入若干(至多m)個(gè)新變量，稱這些新變量為人工變量。4對(duì)偶理論每一種線性規(guī)劃問(wèn)題都存在一種與其對(duì)偶的問(wèn)題，在求出一種問(wèn)題解的同步，也給出了另一種問(wèn)題的解。研究線性規(guī)劃中原始問(wèn)題與對(duì)偶問(wèn)題之間關(guān)系的理論5敏捷度分析研究與分析一種系統(tǒng)（或模型）的狀態(tài)或輸出變化對(duì)系統(tǒng)參數(shù)或周圍條件變化的敏感程度的措施。在最優(yōu)化措施中常常運(yùn)用敏捷度分析來(lái)研究原始數(shù)據(jù)不精確或發(fā)生變化時(shí)最優(yōu)解的穩(wěn)定性。通過(guò)敏捷度分析還可以決定哪些參數(shù)對(duì)系統(tǒng)或模型有較大的影響。6影子價(jià)格反應(yīng)資源配置狀況的價(jià)格。影子價(jià)格是指在其他資源投入不變的狀況下,每增長(zhǎng)一單位的某種資源的投入所帶來(lái)的追加收益。即影子價(jià)格等于資源投入的邊際收益。只有在資源短缺的狀況下,每增長(zhǎng)一單位的投入才能帶來(lái)收益的增長(zhǎng)7產(chǎn)銷平衡運(yùn)送一種特殊的線性規(guī)劃問(wèn)題。產(chǎn)品的銷售過(guò)程中，產(chǎn)銷平衡是指工廠產(chǎn)品的產(chǎn)量等于市場(chǎng)上的銷售量。8西北角法是運(yùn)籌學(xué)中制定運(yùn)送問(wèn)題的初始調(diào)運(yùn)方案（即初始基可行解）的基本措施之一。也就是從運(yùn)價(jià)表的西北角位置開始，依次安排m個(gè)產(chǎn)地和n個(gè)銷地之間的運(yùn)送業(yè)務(wù)，從而得到一種初始調(diào)運(yùn)方案的措施。9最優(yōu)性檢查檢查目前調(diào)運(yùn)方案是不是最優(yōu)方案的過(guò)程。10動(dòng)態(tài)規(guī)劃處理多階段決策過(guò)程優(yōu)化問(wèn)題的措施：把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題，運(yùn)用各階段之間的關(guān)系，逐一求解11狀態(tài)轉(zhuǎn)移方程從階段K到K+1的狀態(tài)轉(zhuǎn)移規(guī)律的體現(xiàn)式12逆序求解法在求解時(shí)，首先逆序求出各階段的條件最優(yōu)目的函數(shù)和條件最優(yōu)決策，然后反向追蹤，次序地求出改多階段決策問(wèn)題的最優(yōu)方略和最優(yōu)路線。13最短路問(wèn)題最短途徑問(wèn)題是圖論研究中的一種經(jīng)典算法問(wèn)題，意在尋找圖（由結(jié)點(diǎn)和途徑構(gòu)成的）中兩結(jié)點(diǎn)之間的最短途徑。14最小費(fèi)用最大流在一種網(wǎng)絡(luò)中每段途徑均有“容量”和“費(fèi)用”兩個(gè)限制的條件下，此類問(wèn)題的研究試圖尋找出：流量從A到B，怎樣選擇途徑、分派通過(guò)途徑的流量，可以到達(dá)所用的費(fèi)用最小的規(guī)定。15排隊(duì)論排隊(duì)論(queueingtheory),或稱隨機(jī)服務(wù)系統(tǒng)理論,是通過(guò)對(duì)服務(wù)對(duì)象到來(lái)及服務(wù)時(shí)間的記錄研究，得出這些數(shù)量指標(biāo)（等待時(shí)間、排隊(duì)長(zhǎng)度、忙期長(zhǎng)短等）的記錄規(guī)律，然后根據(jù)這些規(guī)律來(lái)改善服務(wù)系統(tǒng)的構(gòu)造或重新組織被服務(wù)對(duì)象，使得服務(wù)系統(tǒng)既能滿足服務(wù)對(duì)象的需要，又能使機(jī)構(gòu)的費(fèi)用最經(jīng)濟(jì)或某些指標(biāo)最優(yōu)。二、選擇題1.用圖解法求解一種有關(guān)最大利潤(rùn)的線性規(guī)劃問(wèn)題時(shí)，若其等利潤(rùn)線與可行解區(qū)域相交，但不存在可行解區(qū)域最邊緣的等利潤(rùn)線，則該線性規(guī)劃問(wèn)題(B)。A、有無(wú)窮多種最優(yōu)解B、有可行解但無(wú)最優(yōu)解C、有可行解且有最優(yōu)解D、無(wú)可行解2.若線性規(guī)劃問(wèn)題的最優(yōu)解同步在可行解域的兩個(gè)頂點(diǎn)處到達(dá)，則此線性規(guī)劃問(wèn)題的最優(yōu)解為（B）A、兩個(gè)B、無(wú)窮多種C、零個(gè)D、過(guò)這的點(diǎn)直線上的一切點(diǎn)3.用圖解法求解一種有關(guān)最小成本的線性規(guī)劃問(wèn)題時(shí)，若其等成本線與可行解區(qū)域的某一條邊重疊，則該線性規(guī)劃問(wèn)題(A)。A．有無(wú)窮多種最優(yōu)解B、有有限個(gè)最優(yōu)解C．有唯一的最優(yōu)解D．無(wú)最優(yōu)解4.在求極小值的線性規(guī)劃問(wèn)題中，引入人工變量之后，還必須在目的函數(shù)中分別為它們配上系數(shù)，這些系數(shù)值應(yīng)為(A)。A、很大的正數(shù)B、較小的正數(shù)C、1D、05.對(duì)問(wèn)題的原則型：，運(yùn)用單純形表求解時(shí)，每做一次換基迭代，都能保證它對(duì)應(yīng)的目的函數(shù)值必為（B）A增大B不減少C減少D不增大6.若最優(yōu)解不唯一，則在最優(yōu)單純形表上（A）A非基變量的檢查數(shù)必有為零者B非基變量的檢查數(shù)不必有為零者C非基變量的檢查數(shù)必所有為零D以上均不對(duì)的7.求解線性規(guī)劃模型時(shí)，引入人工變量是為了（B）A使該模型存在可行解B確定一種初始的基可行解C使該模型原則化D以上均不對(duì)的11.用大法求解模型時(shí)，若在最終單純形表上基變量中仍具有非零的人工變量，則原模型（C）A有可行解，但無(wú)最優(yōu)解B有最優(yōu)解C無(wú)可行解D以上都不對(duì)12.已知，是某的兩個(gè)最優(yōu)解，則（D）也是的最優(yōu)解。ABCD無(wú)法判斷13、線性規(guī)劃問(wèn)題的敏捷度分析研究（BC）A、對(duì)偶單純形法的計(jì)算成果；B、目的函數(shù)中決策變量系數(shù)的變化與最優(yōu)解的關(guān)系；C、資源數(shù)量變化與最優(yōu)解的關(guān)系；D、最優(yōu)單純形表中的檢查數(shù)與影子價(jià)格的聯(lián)絡(luò)。14、對(duì)偶單純形法迭代中的主元素一定是負(fù)元素（A）A、對(duì)的B、錯(cuò)誤C、不一定D、無(wú)法判斷15、對(duì)偶單純形法求解極大化線性規(guī)劃時(shí)，假如不按照最小化比值的措施選用什么變量則在下一種解中至少有一種變量為正（B）A、換出變量B、換入變量C、非基變量D、基變量16、影子價(jià)格是指（D）A、檢查數(shù)B、對(duì)偶問(wèn)題的基本解C、解答列取值D、對(duì)偶問(wèn)題的最優(yōu)解17、影子價(jià)格的經(jīng)濟(jì)解釋是（C）A、判斷目的函數(shù)與否獲得最優(yōu)解B、價(jià)格確定的經(jīng)濟(jì)性C、約束條件所付出的代價(jià)D、產(chǎn)品的產(chǎn)量與否合理18、在總運(yùn)送利潤(rùn)最大的運(yùn)送方案中，若某方案的空格的改善指數(shù)分別為IWB=50元，IWC=-80元，IYA=0元，IXC=20元，則最佳挑選(A)為調(diào)整格。A、WB格B、WC格C、YA格D、XC格19、在一種運(yùn)送方案中，從任一數(shù)字格開始，(B)一條閉合回路。A．可以形成至少B．不能形成C、可以形成D．有也許形成20、運(yùn)送問(wèn)題可以用(B)法求解。A、定量預(yù)測(cè)B、單純形C、求解線性規(guī)劃的圖解D、關(guān)鍵線路21、在運(yùn)送問(wèn)題的表上作業(yè)法選擇初始基本可行解時(shí)，必須注意（AD）。A、針對(duì)產(chǎn)銷平衡的表；B、位勢(shì)的個(gè)數(shù)與基變量個(gè)數(shù)相似；C、填寫的運(yùn)送量要等于行、列限制中較大的數(shù)值；D、填寫的運(yùn)送量要等于行、列限制中較小的數(shù)值。22、用增長(zhǎng)虛設(shè)產(chǎn)地或者虛設(shè)銷地的措施可將產(chǎn)銷不平衡的運(yùn)送問(wèn)題化為產(chǎn)銷平衡的運(yùn)送問(wèn)題（A）A、對(duì)的B、錯(cuò)誤C、不一定D、無(wú)法判斷23、通過(guò)什么措施或者技巧可以把產(chǎn)銷不平衡運(yùn)送問(wèn)題轉(zhuǎn)化為產(chǎn)銷平衡運(yùn)送問(wèn)題(C)A、非線性問(wèn)題的線性化技巧B、靜態(tài)問(wèn)題的動(dòng)態(tài)處理C、引入虛擬產(chǎn)地或者銷地D、引入人工變量24、動(dòng)態(tài)規(guī)劃措施不一樣于線性規(guī)劃的重要特點(diǎn)是（AD）。A、動(dòng)態(tài)規(guī)劃可以處理多階段決策過(guò)程的問(wèn)題；B、動(dòng)態(tài)規(guī)劃問(wèn)題要考慮決策變量；C、它的目的函數(shù)與約束不輕易表達(dá)；D、它可以通過(guò)時(shí)間或空間劃分某些問(wèn)題為多階段決策過(guò)程問(wèn)題。25、用DP措施處理資源分派問(wèn)題時(shí)，一般總是選階段初資源的擁有量作為決策變量（B）A、對(duì)的B、錯(cuò)誤C、不一定D、無(wú)法判斷26、用DP措施處理資源分派問(wèn)題時(shí)，每個(gè)階段資源的投放量作為狀態(tài)變量（B）A、對(duì)的B、錯(cuò)誤C、不一定D、無(wú)法判斷27、．動(dòng)態(tài)規(guī)劃最優(yōu)化原理的含義是：最優(yōu)方略中的任意一種K-子方略也是最優(yōu)的（A）A、對(duì)的B、錯(cuò)誤C、不一定D、無(wú)法判斷28．動(dòng)態(tài)規(guī)劃的關(guān)鍵是什么原理的應(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ī)劃求解工程線路問(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ī)劃的求解的規(guī)定是什么（ACD）A、給出最優(yōu)狀態(tài)序列B、給出動(dòng)態(tài)過(guò)程C、給出目的函數(shù)值D、給出最優(yōu)方略32．用動(dòng)態(tài)規(guī)劃處理生產(chǎn)庫(kù)存的時(shí)候，應(yīng)當(dā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)用是(C)。A、減少的B、不增不減的C、增長(zhǎng)的D、難以估計(jì)的34.最小枝權(quán)樹算法是從已接接點(diǎn)出發(fā)，把(C)的接點(diǎn)連接上A、最遠(yuǎn)B、較遠(yuǎn)C、近來(lái)D、較近35.在箭線式網(wǎng)絡(luò)固中，(D)的說(shuō)法是錯(cuò)誤的。A、結(jié)點(diǎn)不占用時(shí)間也不消耗資源B、結(jié)點(diǎn)表達(dá)前接活動(dòng)的完畢和后續(xù)活動(dòng)的開始C、箭線代表活動(dòng)D、結(jié)點(diǎn)的最早出現(xiàn)時(shí)間和最遲出現(xiàn)時(shí)間是同一種時(shí)間36.如圖所示，在鍋爐房與各車間之間鋪設(shè)暖氣管最小的管道總長(zhǎng)度是(C)。A、1200B、1400C、1300D、1700600600700300500400鍋爐房12337.在求最短路線問(wèn)題中，已知起點(diǎn)到A，B，C三相鄰結(jié)點(diǎn)的距離分別為15km，20km25km，則（D）。A、最短路線—定通過(guò)A點(diǎn)B、最短路線一定通過(guò)B點(diǎn)C、最短路線一定通過(guò)C點(diǎn)D、不能判斷最短路線通過(guò)哪一點(diǎn)38.在一棵樹中，假如在某兩點(diǎn)間加上條邊，則圖一定(A)A、存在一種圈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ū)車趕到乙市，應(yīng)借用（C）A、樹的逐漸生成法B、求最小技校樹法C、求最短路線法D、求最大流量法42.為了在各住宅之間安裝一種供水管道．若規(guī)定用材料最省，則應(yīng)使用(B)。A、求最短路法B、求最小技校樹法C、求最大流量法D、樹的逐漸生成法43．排隊(duì)系統(tǒng)狀態(tài)轉(zhuǎn)移速度矩陣中，每一列的元素之和等于0。（B）A、對(duì)的B、錯(cuò)誤C、不一定D、無(wú)法判斷44.排隊(duì)系統(tǒng)中狀態(tài)是指系統(tǒng)中的顧客數(shù)（A）A、對(duì)的B、錯(cuò)誤C、不一定D、無(wú)法判斷45．排隊(duì)系統(tǒng)的構(gòu)成部分有（ABC）A、輸入過(guò)程B、排隊(duì)規(guī)則C、服務(wù)機(jī)構(gòu)D、服務(wù)時(shí)間46．排隊(duì)系統(tǒng)中，若系統(tǒng)輸入為泊松流，則相繼抵達(dá)的顧客間隔時(shí)間服從什么分布（D）A、正態(tài)分布B、愛(ài)爾朗分布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、寫出對(duì)應(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)題IIx123x29/41f(x)2122問(wèn)題II的解即原整數(shù)問(wèn)題的最優(yōu)解3、已知線性規(guī)劃問(wèn)題規(guī)定：（1）化為原則型式（2）列出用兩階段法求解時(shí)第一階段的初始單純形表解：（1）令原模型可以轉(zhuǎn)化為（2）見(jiàn)下表000000-11-11515-33-10100205-610-100100-15111-10001-26-22-10004、求下列線性規(guī)劃問(wèn)題，并寫出問(wèn)題的對(duì)偶問(wèn)題答案：對(duì)偶問(wèn)題：5、求出下列問(wèn)題的對(duì)偶問(wèn)題并分別隊(duì)原問(wèn)題及對(duì)偶問(wèn)題求解答案：用單純型法求解過(guò)程Cj536-600MCBXBbx1x2x'3x"3x4x5x60x41812111000x51621(3)3010Mx6101111001OBJ=10MMMMM00Mcj-zj5+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-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=425377021cj-zj001102-M+10x4801001015x11412000136x"340111012OBJ=465466013cj-zj010001-M3對(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=46運(yùn)送問(wèn)題的數(shù)據(jù)如下表：B1B2B3B4產(chǎn)量A1A2A3223743591678500600300銷量300200500400求最優(yōu)運(yùn)送方案。答案：最優(yōu)方案：f*=6000B1B2B3B4產(chǎn)量A1A2A3100400200400300500600300銷量3002005004007、對(duì)于如下運(yùn)送問(wèn)題，怎樣用最小元素法求出初始調(diào)運(yùn)方案？答案：求解過(guò)程如下。表中“□”內(nèi)數(shù)字為刪除線出現(xiàn)的先后次序。8、判斷下表中給出的調(diào)運(yùn)方案能否作為表上作業(yè)法求解的初始方案？為何？銷銷地運(yùn)量產(chǎn)地產(chǎn)量2525201030202052530銷量2020301025105答案：不能作為初始方案。由于數(shù)字格只有6個(gè)，而9、某奶牛站但愿通過(guò)投資來(lái)擴(kuò)大牛群數(shù)，開始只有5000元資金，目前已知可購(gòu)入A或者B兩個(gè)品種的奶牛，對(duì)于A種牛每投入1000元，當(dāng)年及后來(lái)每年可以獲得500元和2頭小牛，對(duì)種牛每投入1000元，當(dāng)年及后來(lái)每年可以獲得200元和3頭小牛。問(wèn)：（1）在此后的四年內(nèi)應(yīng)當(dāng)怎樣分派投資使奶牛群最大（2）到第四年終奶牛站將有多少頭奶牛。答案：狀態(tài)為階段可運(yùn)用的資金；決策為階段向種牛投入的資金數(shù)；為階段向種牛投入的資金數(shù)；則轉(zhuǎn)移函數(shù)為遞推函數(shù)：表達(dá)在階段出生的小牛數(shù)；第四年末牧場(chǎng)主應(yīng)擁有的牛的頭數(shù)為70頭10.求下面容量網(wǎng)絡(luò)的最大流，弧邊上括號(hào)內(nèi)第一種數(shù)為容量，第二個(gè)數(shù)為流量。（1）、根據(jù)標(biāo)號(hào)過(guò)程找出增廣鏈，確定流量修正量ε；（2）、調(diào)整流量，畫出最大流圖，闡明最大流量是多少；（3）、根據(jù)標(biāo)號(hào)和求解過(guò)程確定最小割并算出最小割容量；V2V4(3,2)(4,1)V1(3,1)(1,1)(3,1)V6(2,0)(2,2)(3,1)(2,2)V3V5、解：V1V1V22+V4V63+1+（,1）（,2）（,1）（,2）V2V4（,3）（3,3）（4,2）（-,∞）（,3）（3,3）（4,2）（-,∞）V1V6（3,2）(1,1)V1V6（3,2）(1,1)（3,1）（2,0）V3V5（2,2）V3V5（2,2）（3,1）（2,2）（,2）（,2）圖1圖1（,1）（（,1）（,1）V2V2V4（,2）（3,3）（4,3）（-,∞）（,2）（3,3）（4,3）（-,∞）V1V6（3,3）V1V6（3,3）（3,0）（2,1）(1,1)(1,1)V3V5（2,2）V3V5（2,2）（3,1）（2,2）（,2）（,2）圖2圖2+V6V4-+2++V6V4-+2+2V511V2V12V511V2V1標(biāo)號(hào)過(guò)程中，圖2為最大流圖，最大流量3.其節(jié)點(diǎn)均屬則最小割為，最小割容量為3+2=511、一臺(tái)研磨