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

1、運(yùn)籌學(xué)綜合復(fù)習(xí)資料一、判斷題1、LP問題的可行域是凸集。2、LP問題的基可行解對應(yīng)可行域的頂點(diǎn)。3、LP問題的最優(yōu)解一定是可行域的頂點(diǎn)，可行域的頂點(diǎn)也一定是最優(yōu)解。4、若LP問題有兩個最優(yōu)解，則它一定有無窮多個最優(yōu)解.5、 求解LP問題時,對取值無約束的自由變量，通常令Xj =Xj -Xj ,其中：Xj Xj _0, 在用單純形法求得的最優(yōu)解中，有可能同時出現(xiàn)x/ x/ 0.6、在PERT計算中，將最早節(jié)點(diǎn)時刻等于最遲節(jié)點(diǎn)時刻、且滿足如（j） - t（i, j） - tE（i） = 0節(jié) 點(diǎn)連接而成的線路是關(guān)鍵線路pN（t ）= n=匕丄，7、在一個隨機(jī)服務(wù)系統(tǒng)中，當(dāng)其輸入過程是一普阿松流時，

2、即有n! ,則同一時間區(qū)間內(nèi)，相繼兩名顧客到達(dá)的時間間隔是相互獨(dú)立且服從參數(shù)為 入的負(fù)指數(shù) 分布，即有P X =t = e&分枝定界求解整數(shù)規(guī)劃時，分枝問題的最優(yōu)解不會優(yōu)于原（上一級）問題的最優(yōu)解9、對偶問題的對偶問題一定是原問題。10、運(yùn)輸問題是一種特殊的LP問題，因而其求解結(jié)果也可能會有唯一的最優(yōu)解或無窮 多個最優(yōu)解。11、動態(tài)規(guī)劃中，定義狀態(tài)變量時應(yīng)保證在各個階段中所做決策的相互獨(dú)立性。12、用割平面法求解整數(shù)規(guī)劃時，每次增加一個割平面/線性約束條件后，在新的線性 規(guī)劃可行域中，除了割去一些不屬于整數(shù)解的可行解外，還割去了上級問題不屬于整數(shù) 解的最優(yōu)解。13、在求解目標(biāo)規(guī)劃時，遵循的基本

3、原則就是在考慮低級目標(biāo)時，不能破壞已經(jīng)滿足的 咼級目標(biāo)。14、根據(jù)對偶問題的性質(zhì)，當(dāng)原問題為無界解時，其對偶問題無可行解，反之，當(dāng)對偶 問題無可行解時，其原問題具有無界解。15、 已知y*為線性規(guī)劃的對偶問題的最優(yōu)解，若 y* =0,說明在最優(yōu)生產(chǎn)計劃中第i 種資源一定有剩余。16、表上作業(yè)法中，按最小元素法給出的初始調(diào)運(yùn)方案，從每一空格出發(fā)可以找出而且僅能找出唯一的閉回路。17、目標(biāo)規(guī)劃中正偏差變量應(yīng)取正值，負(fù)偏差變量應(yīng)取負(fù)值二、計算題1. 某LP模型為：Max z = 9為 8x250x319x4s.t. 3x1 2x2 10x3 4x4 -182x30.5x4 _ 3洛，X2, X3,

4、X4 一 0單純形表已解至如下表：9X18X250X319X40S10S2bX424/301213-10/32X3-1/2-1/310-1/64/31ZjC - Z填上表中尚缺數(shù)據(jù)，回答該問題的最優(yōu)解，最優(yōu)目標(biāo)函數(shù)值。2.某運(yùn)輸問題的運(yùn)價及各產(chǎn)地、銷地的數(shù)據(jù)如下表，試確定總運(yùn)費(fèi)最低的運(yùn)輸方案。B1B2B3B4供應(yīng)A1311457A277384A3121069需求3656203. 某公司計劃制造I、U兩種家電產(chǎn)品，已知各制造一件時分別占用的設(shè)備A、B的臺時、調(diào)試時間及每天可用的設(shè)備能力和單件產(chǎn)品的獲利情況如下表：產(chǎn)品I產(chǎn)品U每天可用能力設(shè)備A （小時）0515設(shè)備B （小時）6224調(diào)試工序（小

5、時）115利潤（元）21（1）建立獲利最大的線性規(guī)劃模型并求解（可不考慮整數(shù)要求）（2）對上問中獲利最大的線性規(guī)劃模型建立其對偶規(guī)劃模型，并回答其最優(yōu)解和說明該 公司的短缺資源是哪些？（3）如獲利最大的線性規(guī)劃模型要求其變量為整數(shù)，試用割平面法解之。T 如該公司新研制的產(chǎn)品川對三種資源的單位產(chǎn)品消耗是（3 4 2），預(yù)期盈利為3元/件，試判斷且僅判斷產(chǎn)品川是否值得生產(chǎn)？4. 某公司有某種高效率設(shè)備3臺，擬分配給所屬甲、乙、丙工廠，各工廠得到設(shè)備后, 獲利情況如下表，試建立最優(yōu)分配方案。獲利設(shè)備臺數(shù)甲乙丙0000135427106391111（1）正確設(shè)定狀態(tài)變量、決策變量并寫出狀態(tài)轉(zhuǎn)移方程；（

6、2）寫出規(guī)范的（形式）基本方程；（3）求解。5.銷地 產(chǎn)地B1B2B3B4產(chǎn)量A141158A2126110A337514銷量8563（1）求其最優(yōu)解（可取初始調(diào)運(yùn)方案為：X!2= 2 , X!3= 6, X21= 7, X22= 3, X31= 1, X34= 3）；若價值系數(shù)C2,4由1變?yōu)?,所求最優(yōu)解是否仍為最優(yōu)解；若所有價值系數(shù)均增加 1,最優(yōu)解是否改變？6.有一輛卡車最大載重為10噸，用以裝載3種貨物，每種貨物的單位重量及相應(yīng)的單 位價值如下表所示，問如何裝載可使運(yùn)輸貨物的總價值最大？貨物編號In出單位重量（噸）345單位價值456三、建立模型并計算1.設(shè)有A，B，C, D四個工人

7、，可以完成1, 2, 3, 4四項(xiàng)工作任務(wù)，由于每個工人完 成不同的任務(wù)成本不同，試建立總成本最低的指派模型并求解。工人任務(wù)1234A79813B16161511C16191015D161714162. 某采油區(qū)已建有n個計量站Bi, B2-Bn,各站目前尚未被利用的能力為bi, b?b （噸 液量/日）。為適應(yīng)油田開發(fā)的需要，規(guī)劃在該油區(qū)打 m 口調(diào)整井Ai, Az-Am，且這些井 的位置已經(jīng)確定。根據(jù)預(yù)測，調(diào)整井的產(chǎn)量分別為ai, az-am （噸液量/日）?？紤]到原有計量站富余的能力，決定不另建新站，而用原有老站分工管轄調(diào)整井。按規(guī)劃要求， 每口井只能屬于一個計量站。假定 Ai到Bj的距

8、離dj已知，試確定各調(diào)整井與計量站的 關(guān)系，使新建集輸管線總長度最短。（設(shè)定變量，寫出模型）。3 不允許缺貨、補(bǔ)充時間無限短的確定型存儲模型的假設(shè)條件是：不允許缺貨補(bǔ)充時間無限短需求是連續(xù)的且需求速率R為常數(shù)單位物資單位時間的存儲費(fèi)用C 1是常數(shù)每次定購費(fèi)C 3 （不考慮貨款）是常數(shù)試：（1）畫出存儲量變化曲線；（2）分析費(fèi)用，建立總平均費(fèi)用最低的訂貨模型（訂 貨周期、訂貨量）。四、繪圖并計算某工程的PERT數(shù)據(jù)如下表：工序緊前工序作業(yè)時間工序緊前工序作業(yè)時間A3FC8BA4GC4CA5HD,E2DB,C7IG3EB,C7JH,l2（1）畫出網(wǎng)絡(luò)圖并予節(jié)點(diǎn)以正確的編號；（2）計算最早.最遲節(jié)點(diǎn)

9、時刻；（3）據(jù)所畫網(wǎng) 絡(luò)圖填寫計算下表。ij作業(yè)代號tesefIslftf關(guān)鍵工序運(yùn)籌學(xué)綜合復(fù)習(xí)資料參考答案、判斷題題目12345678910答案VVXVXVVVVV題目11121314151617答案VVVXVVX、計算題1. 參考答案:9X850心190力0S2b19X424/3012/3-10/3250xj-1/2-U30-1/64/31Zj1326/30013/310/388Cj坷-2 300133-10 32. 參考答案:X13 = 1X-14 = 6X23 = 4X32 =63. 參考答案：Xk表示k階段分配給k工(1) Xi二7? X2= 32z =17 2(2) %=0y 14

10、y 12，短缺資源為設(shè)備B與調(diào)試工序。(3)X1 =3X2 =2z =815/4-15/23(4)3=3_(0 21)0 1/4-1/24=1，故產(chǎn)品川值得生產(chǎn)。2 -1/4 324.參考答案：(1)設(shè)狀態(tài)變量sk表示k階段開始時，可供分配的機(jī)器臺數(shù)；決策變量廠機(jī)器臺數(shù)，則狀態(tài)轉(zhuǎn)移方程為:f4(S4)=0fk(Sk)=0max Vk Sk,Xkfk 1 Sk 1 k =3,2,10芻仝kSk 1 仝k -xkXr=0 x?=2 X3=1 3=145 參考答案：(1 )最優(yōu)調(diào)運(yùn)方案：x12=2 x13=6X21=4 X22= 3 x23 =3X31=4(2 )是(3)不改變6 參考答案：運(yùn)送第一

11、種貨物2件，運(yùn)送第二種貨物1件，共重10砘，可達(dá)最大價值為13三、建立模型并計算1.參考答案：2.參考答案：設(shè)Xj表示i井是否連到j(luò)站m nMin z _ dij xiji壬j生ns.t. Xjj = 1 i = T mj 1m，二 aixij 乞 bj j = 1 ni =1variable positive3 參考答案：平均存儲費(fèi)用:平均存儲量平均存儲費(fèi)用訂貨費(fèi)：1 tRtdt t 01RC12一個周期內(nèi)的平均每天的訂貨費(fèi)Rt2C3t總平均費(fèi)用:1 C3C tRGt 2 t模型的建立：心Jrgdt 2（其中djdt2二 2C3 t)則得:t* 二Q*Ci2RC3C t* = 2C1C3R四、繪圖并計算參考答案：節(jié)點(diǎn)最早節(jié)點(diǎn)時刻最遲節(jié)點(diǎn)時刻節(jié)點(diǎn)最早節(jié)點(diǎn)時刻最遲節(jié)點(diǎn)時刻100615152337151