運籌學(xué)總結(jié)復(fù)習(xí)計劃題

運籌學(xué)總結(jié)復(fù)習(xí)計劃題運籌學(xué)總結(jié)復(fù)習(xí)計劃題PAGE29運籌學(xué)總結(jié)復(fù)習(xí)計劃題運籌學(xué)-學(xué)習(xí)指南一、名詞解說廢弛變量為將線性規(guī)劃問題的數(shù)學(xué)模型化為標準型而加入的變量?？尚杏蛑憔€性拘束條件的解（x,y）叫做可行解，由全部可行解構(gòu)成的會合叫做可行域。人工變量亦稱人造變量.求解線性規(guī)劃問題時人為加入的變量。用純真形法求解線性規(guī)劃問題，都是在擁有初始可行基的條件下進行的,但拘束方程組的系數(shù)矩陣A中所含的單位向量常常不足m個，此時可加入若干(至多m)個新變量，稱這些新變量為人工變量。對偶理論每一個線性規(guī)劃問題都存在一個與其對偶的問題，在求出一個問題解的同時，也給出了另一個問題的解。研究線性規(guī)劃中原始問題與對偶問題之間關(guān)系的理論敏捷度分析研究與分析一個系統(tǒng)（或模型）的狀態(tài)或輸出變化對系統(tǒng)參數(shù)或四周條件變化的敏感程度的方法。在最優(yōu)化方法中常常利用敏捷度分析來研究原始數(shù)據(jù)不正確或發(fā)生變化時最優(yōu)解的堅固性。經(jīng)過敏捷度分析還能夠夠決定哪些參數(shù)對系統(tǒng)或模型有較大的影響。6影子價錢反應(yīng)資源配置狀況的價錢。影子價錢是指在其余資源投入不變的狀況下種資源的投入所帶來的追加利潤。即影子價錢等于資源投入的邊沿利潤。

,每增添一單位的某只有在資源欠缺的狀況下,每增添一單位的投入才能帶來利潤的增添產(chǎn)銷均衡運輸一種特其余線性規(guī)劃問題。產(chǎn)品的銷售過程中，產(chǎn)銷均衡是指工廠產(chǎn)品的產(chǎn)量等于市場上的銷售量。西北角法是運籌學(xué)中制定運輸問題的初始調(diào)運方案（即初始基可行解）的基本方法之一。也就是從運價表的西北角地點開始，挨次安排m個產(chǎn)地和n個銷地之間的運輸業(yè)務(wù)，進而獲得一個初始調(diào)運方案的方法。最優(yōu)性查驗查驗?zāi)壳罢{(diào)運方案能否是最優(yōu)方案的過程。動向規(guī)劃解決多階段決議過程優(yōu)化問題的方法：把多階段過程轉(zhuǎn)變?yōu)橐幌盗袉坞A段問題，利用各階段之間的關(guān)系，逐一求解狀態(tài)轉(zhuǎn)移方程從階段K到K+1的狀態(tài)轉(zhuǎn)移規(guī)律的表達式12逆序求解法在求解時，第一逆序求出各階段的條件最優(yōu)目標函數(shù)和條件最優(yōu)決議，地求出改多階段決議問題的最優(yōu)策略和最優(yōu)路線。

此后反向追蹤，次序13最短路問題最短路徑問題是圖論研究中的一個經(jīng)典算法問題，兩結(jié)點之間的最短路徑。

旨在找尋圖（由結(jié)點和路徑構(gòu)成的）中最小開銷最大流在一個網(wǎng)絡(luò)中每段路徑都有“容量”和“開銷”兩個限制的條件下，此類問題的研究試圖找尋出：流量從A到B，怎樣選擇路徑、分派經(jīng)過路徑的流量，能夠達到所用的開銷最小的要求。排隊論排隊論(queueingtheory),或稱隨機服務(wù)系統(tǒng)理論,是經(jīng)過對服務(wù)對象到來及服務(wù)時間的統(tǒng)計研究，得出這些數(shù)目指標（等候時間、排隊長度、忙期長短等）的統(tǒng)計規(guī)律，此后依據(jù)這些規(guī)律來改良服務(wù)系統(tǒng)的構(gòu)造或從頭組織被服務(wù)對象，使得服務(wù)系統(tǒng)既能知足服務(wù)對象的需要，又能使機構(gòu)的開銷最經(jīng)濟或某些指標最優(yōu)。二、選擇題1.用圖解法求解一個對于最大利潤的線性規(guī)劃問題時，若其等利潤線與可行解地區(qū)訂交，但不存在可行解地區(qū)最邊沿的等利潤線，則該線性規(guī)劃問題(B)。A、有無量多個最優(yōu)解B、有可行解但無最優(yōu)解C、有可行解且有最優(yōu)解D、無可行解若線性規(guī)劃問題的最優(yōu)解同時在可行解域的兩個極點處達到，則此線性規(guī)劃問題的最優(yōu)解為（B）A、兩個B、無量多個C、零個D、過這的點直線上的全部點用圖解法求解一個對于最小成本的線性規(guī)劃問題時，若其等成本線與可行解地區(qū)的某一條邊重合，則該線性規(guī)劃問題(A)。A．有無量多個最優(yōu)解B、有有限個最優(yōu)解C．有獨一的最優(yōu)解D．無最優(yōu)解在求極小值的線性規(guī)劃問題中，引入人工變量此后，還必然在目標函數(shù)中分別為它們配上系數(shù)，這些系數(shù)值應(yīng)為(A)。A、很大的正數(shù)B、較小的正數(shù)C、1D、05.對問題的標準型：maxZCX,AXb,X0，利用純真形表求解時，每做一次換基迭代，都能保證它相應(yīng)的目標函數(shù)值Z必為（B）A增大B不減少C減少D不增大6.若最優(yōu)解不獨一，則在最優(yōu)純真形表上（A）非基變量的查驗數(shù)必有為零者非基變量的查驗數(shù)不用有為零者非基變量的查驗數(shù)必全部為零以上均不正確7.求解線性規(guī)劃模型時，引入人工變量是為了（B）使該模型存在可行解確立一個初始的基可行解使該模型標準化以上均不正確用大M法求解模型時，若在最后純真形表上基變量中仍含有非零的人工變量，則原模型（C）有可行解，但無最優(yōu)解有最優(yōu)解無可行解以上都不對12.已知x1(2,4)，x2(4,8)是某的兩個最優(yōu)解，則（D）也是的最優(yōu)解。Ax(4,4)Bx(1,2)Cx(2,3)沒法判斷13、線性規(guī)劃問題的敏捷度分析研究（BC）A、對偶純真形法的計算結(jié)果；B、目標函數(shù)中決議變量系數(shù)的變化與最優(yōu)解的關(guān)系；C、資源數(shù)目變化與最優(yōu)解的關(guān)系；D、最優(yōu)純真形表中的查驗數(shù)與影子價錢的聯(lián)系。14、對偶純真形法迭代中的主元素必然是負元素（A）A、正確B、錯誤C、不用然D、沒法判斷15、對偶純真形法求解極大化線性規(guī)劃時，在下一個解中最罕有一個變量為正（B）A、換出變量

假如不依據(jù)最小化比值的方法采納什么變量則B、換入變量C、非基變量D、基變量16、影子價錢是指（A、查驗數(shù)

D）B、對偶問題的基本解C、解答列取值D、對偶問題的最優(yōu)解17、影子價錢的經(jīng)濟解說是（C）A、判斷目標函數(shù)能否獲得最優(yōu)解B、價錢確立的經(jīng)濟性C、拘束條件所付出的代價D、產(chǎn)品的產(chǎn)量能否合理18、在總運輸利潤最大的運輸方案中，若某方案的空格的改良指數(shù)分別為IWB=50元，IWC=-80元，IYA元，IXCA)為調(diào)整格。=0=20元，則最好精選(A、WB格B、WC格C、YA格D、XC格19、在一個運輸方案中，從任一數(shù)字格開始，(B)一條閉合回路。A．能夠形成最少B．不可以夠形成C、能夠形成D．有可能形成20、運輸問題能夠用

(

B)法求解。A、定量展望

B、純真形

C、求解線性規(guī)劃的圖解

D、重點線路21、在運輸問題的表上作業(yè)法選擇初始基本可行解時，必然注意（

AD

）。A、針對產(chǎn)銷均衡的表；B、位勢的個數(shù)與基變量個數(shù)同樣；C、填寫的運輸量要等于行、列限制中較大的數(shù)值；D、填寫的運輸量要等于行、列限制中較小的數(shù)值。22、用增添虛設(shè)產(chǎn)地或許虛設(shè)銷地的方法可將產(chǎn)銷不均衡的運輸問題化為產(chǎn)銷均衡的運輸問題（A）A、正確B、錯誤C、不用然D、沒法判斷23、經(jīng)過什么方法或許技巧能夠把產(chǎn)銷不均衡運輸問題轉(zhuǎn)變?yōu)楫a(chǎn)銷均衡運輸問題

(C

)A、非線性問題的線性化技巧B、靜態(tài)問題的動向辦理C、引入虛假產(chǎn)地或許銷地D、引入人工變量24、動向規(guī)劃方法不同樣于線性規(guī)劃的主要特色是（

AD

）。A、動向規(guī)劃能夠解決多階段決議過程的問題；B、動向規(guī)劃問題要考慮決議變量；C、它的目標函數(shù)與拘束不簡單表示；D、它能夠經(jīng)過時間或空間區(qū)分一些問題為多階段決議過程問題。25、用DP方法辦理資源分派問題時，平常老是選階段初資源的擁有量作為決議變量

（B）A、正確B、錯誤C、不用然D、沒法判斷26、用DP方法辦理資源分派問題時，每個階段資源的投放量作為狀態(tài)變量（

B）A、正確B、錯誤C、不用然D、沒法判斷27、．動向規(guī)劃最優(yōu)化原理的含義是：最優(yōu)策略中的隨意一個

K-子策略也是最優(yōu)的（

A）A、正確B、錯誤C、不用然D、沒法判斷28．動向規(guī)劃的核心是什么原理的應(yīng)用（A、最優(yōu)化原理

A）B、逆向求解原理C、最大流最小割原理D、網(wǎng)絡(luò)分析原理29．動向規(guī)劃求解的一般方法是什么（A、圖解法

C）B、純真形法C、逆序求解D、標號法30．用動向規(guī)劃求解工程線路問題時，

什么樣的網(wǎng)絡(luò)問題能夠轉(zhuǎn)變?yōu)槎ú綌?shù)問題求解

（

B

）A、隨意網(wǎng)絡(luò)B、無回路有向網(wǎng)絡(luò)C、混淆網(wǎng)絡(luò)D、容量網(wǎng)絡(luò)31．動向規(guī)劃的求解的要求是什么（

ACD

）A、給出最優(yōu)狀態(tài)序列B、給出動向過程C、給出目標函數(shù)值D、給出最優(yōu)策略32．用動向規(guī)劃解決生產(chǎn)庫存的時候，應(yīng)當(dāng)特別注意哪些問題（

BC

）A、生產(chǎn)能力B、狀態(tài)變量的贊成取值范圍C、決議變量的贊成取值范圍D、庫存容量在網(wǎng)絡(luò)計劃技術(shù)中，進行時間與成本優(yōu)化時，一般地說，跟著施工周期的縮短，直接開銷是(C)。A、降低的B、不增不減的C、增添的D、不可以預(yù)計的最小枝權(quán)樹算法是從已接接點出發(fā)，把(C)的接點連結(jié)上A、最遠B、較遠C、近來D、較近在箭線式網(wǎng)絡(luò)固中，(D)的說法是錯誤的。A、結(jié)點不占用時間也不用耗費源B、結(jié)點表示前接活動的達成和后續(xù)活動的開始C、箭線代表活動D、結(jié)點的最早出現(xiàn)時間和最遲出現(xiàn)時間是同一個時間36.以以下圖，在鍋爐房與各車間之間鋪設(shè)暖氣管最小的管道總長度是(C)。A、1200B、1400C、1300D爐房3003700600237.在求最短路線問題中，已知起點到A，B，C三相鄰結(jié)點的距離分別為15km，20km25km，則（D）。A、最短路線—定經(jīng)過A點B、最短路線必然經(jīng)過B點C、最短路線必然經(jīng)過C點D、不可以夠判斷最短路線經(jīng)過哪一點38.在一棵樹中，假如在某兩點間加上條邊，則圖必然(A)A、存在一個圈B、存在兩個圈C、存在三個圈D、不含圈39網(wǎng)絡(luò)圖重點線路的長度(C)工程竣工期。A．大于B．小于C．等于D．不用然等于40.在計算最大流量時，我們選中的每一條路線(C)。A、必然是一條最短的路線B、必然不是一條最短的路線C、是使某一條支線流量飽和的路線D、是任一條支路流量都不飽和的路線41.從甲市到乙市之間有—公路網(wǎng)絡(luò)，為了趕快從甲市驅(qū)車趕到乙市，應(yīng)借用（C）A、樹的逐漸生成法B、求最小技校樹法C、求最短路線法D、求最大流量法42.為了在各住所之間安裝一個供水管道．若要求用資料最省，則應(yīng)使用(B)。A、求最短路法B、求最小技校樹法C、求最大流量法D、樹的逐漸生成法43．排隊系統(tǒng)狀態(tài)轉(zhuǎn)移速度矩陣中，每一列的元素之和等于0。（B）A、正確B、錯誤C、不用然D、沒法判斷44.排隊系統(tǒng)中狀態(tài)是指系統(tǒng)中的顧客數(shù)（A）A、正確B、錯誤C、不用然D、沒法判斷45．排隊系統(tǒng)的構(gòu)成部分有（ABC）A、輸入過程B、排隊規(guī)則C、服務(wù)機構(gòu)D、服務(wù)時間46．排隊系統(tǒng)中，若系統(tǒng)輸入為泊松流，則接踵抵達的顧客間隔時間遵照什么散布（D）A、正態(tài)散布B、愛爾朗散布C、泊松流D、負指數(shù)散布47．研究排隊模型及數(shù)目指標的思路是第一明確系統(tǒng)的意義，此后（ABC）A、寫出狀態(tài)概率方程B、寫出狀態(tài)轉(zhuǎn)移速度矩陣C、畫出狀態(tài)轉(zhuǎn)移速度圖D、寫出相應(yīng)的微分方程48．排隊系統(tǒng)的狀態(tài)轉(zhuǎn)移速度矩陣中（B）元素之和等于零。A、每一列B、每一行C、對角線D、次對角線三、計算題1..用圖解法求解以下LP問題maxzx2x122x12x212x12x28s..t4x1164x212x1,x20答案：依題有可得最優(yōu)解會合為{(x1,x2)|(x1,x2)a(2,3)(1a)(4,2),0a1}也即{(x1,x2)|(x1,x2)(42a,2a),0a1}最優(yōu)值為z8（詳盡求解過程略去）用分枝界定法求解以下線性規(guī)劃問題maxf(x)6x14x22x14x2132x1x27x1,x20且為整數(shù)答案：廢弛問題的最優(yōu)解為x12=,x=2,OBJ=23由x1=獲得兩個分枝以下：maxf(x)6x14x2maxf(x)6x124x14x2132x14x2132x和2x1x271x272x問題II問題I23x1x1120且為整數(shù)x1,x20且為整數(shù)x,x各個分枝問題的廢弛解為問題I問題IIx123x29/41f(x)2122問題II的解即原整數(shù)問題的最優(yōu)解3、已知線性規(guī)劃問題maxz5x16x27x3x15x23x3155x16x210x320s.t.5x1x2x3x1,x20,x3無拘束要求：（1）化為標準型式（2）列出用兩階段法求解時第一階段的初始純真形表解：（1）令x1'x;x3x3'x3'',x3'、''0，zz'x3原模型能夠轉(zhuǎn)變?yōu)?、，zz'x1'x;x3x3'x3'',x3'x3''0x1'5x23x3'3x3''x4x6155x1'6x210x3'10x3''x520x1'x2x3'x3''x75x1',x2,x3',x3'',x4,x5,x6,x70（2）見下表000000-11x1'x2'x3'x3''x4'x5'x6'x7'-1x61515-33-10100x5205-610-100100-1x75111-10001cj-zj26-22-10004、求以下線性規(guī)劃問題，并寫出LP問題的對偶問題maxz3x12x2x12x24s.t.3x12x214x1x23答案：x1,x20X[51300150]244maxZ4對偶問題：minw4y114y23y3y13y2y33s.t.2y12y2y32y10,y2,305、求出以下問題的對偶問題并分別隊原問題及對偶問題求解原問題:maxf(x)5x13x26x3x12x2x3182x1x23x316st..x1x2x310x1,x20,x3不限答案：對偶問題:ming(y)18y116y210y3y12y2y35s..t2y1y2y33y13y2y36y1,y20,y3不限用純真型法求解過程C536-600MjCBXBbx1x2x'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/3Mc-z1+M/31+2M/3000-2-M/30jj0x411/200011/25/26x'33(1/2)01101/23/23x271/210001/23/2OBJ=399/236603/23/2c-z1/200003/2-M-3/2jj0x4400111135x1610220113x24011(1)012OBJ=425377021cj-zj001102-M+10x4801001015x11412000136x"340111012OBJ=465466013cj-zj010001-M3對偶問題最優(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ù)以下表：B1B2B3B4產(chǎn)量A12237500A435960021678300A3銷量300200500400求最優(yōu)運輸方案。答案：最優(yōu)方案：f*=6000BBBB產(chǎn)量1234A1200100400500A4006002300300A3銷量3002005004007、對于以下運輸問題，怎樣用最小元素法求出初始調(diào)運方案答案：求解過程以下。表中“□”內(nèi)數(shù)字為刪除線出現(xiàn)的先后次序。8、判斷下表中給出的調(diào)運方案能否作為表上作業(yè)法求解的初始方案為何運銷地量產(chǎn)地A1A2A3A4銷量

B1B2B3B4B5產(chǎn)量25252010302020525302020301025105答案：不可以夠作為初始方案。由于數(shù)字格只有6個，而nm189、某奶牛站希望經(jīng)過投資來擴大牛群數(shù)，開始只有5000元資本，此刻已知可購入A或許B兩個品種的奶牛，對于A種牛每投入1000元，當(dāng)年及此后每年能夠獲得500元和2頭小牛，對B種牛每投入1000元，當(dāng)年及此后每年能夠獲得200元和3頭小牛。問：1）在此后的四年內(nèi)應(yīng)當(dāng)怎樣分派投資使奶牛群最大2）到第四年關(guān)奶牛站將有多少頭奶牛。答案：狀態(tài)S為階段n可利用的資本；n決議dn為階段n向A種牛投入的資本數(shù)；Sn為階段n向B種牛投入的資本數(shù)；dn則轉(zhuǎn)移函數(shù)為Sn1Sndn遞推函數(shù)：fn(Sn)rn(dn)fn1(Sn1)rnn(3Sndn);1000rn表示在階段n出生的小牛數(shù)S5000；4第四年關(guān)牧場主應(yīng)擁有的牛的頭數(shù)為70頭求下邊容量網(wǎng)絡(luò)的最大流，弧邊上括號內(nèi)第一個數(shù)為容量，第二個數(shù)為流量。（1）、依據(jù)標號過程找出增廣鏈，確立流量修正量ε；（2）、調(diào)整流量，畫出最大流圖，說明最大流量是多少；（3）、依據(jù)標號和求解過程確立最小割并算出最小割容量；V2V4(3,2)(4,1)V(3,1)(1,1)(3,1)V16(2,0)(2,2)(3,1)(2,2)VV35、解：1.增廣鏈：+++V1V2V46213Vmin2,1,311（1,2）（V2,14）V2（4,2）V（V（-,∞）3,3）（V4,3）V1（3,2）(1,1)（2,0）（3,1）V6（2,2）V3（3,1）5（2,2）V(V2,1)（V2,2）,2)(V4圖1(V3,2)2.（V1,1）（V5,1）（-,∞）V2（3,3）V4（4,3）（V4,2）（3,3）(1,1)（2,1）（3,0）V