《運籌學(xué)》復(fù)習(xí)資料分析.doc

1、運籌學(xué)綜合復(fù)習(xí)資料一、判斷題1、LP 問題的可行域是凸集。2、LP 問題的基可行解對應(yīng)可行域的頂點。3、LP 問題的最優(yōu)解一定是可行域的頂點, 可行域的頂點也一定是最優(yōu)解。4、若 LP 問題有兩個最優(yōu)解 , 則它一定有無窮多個最優(yōu)解 .5、求解 LP 問題時 , 對取值無約束的自由變量， 通常令 x jx j x j , 其中 x jx j0 ,在用單純形法求得的最優(yōu)解中 , 有可能同時出現(xiàn) x j x j0 .6、在 PERT計算中，將最早節(jié)點時刻等于最遲節(jié)點時刻、 且滿足 tL ( j ) t(i , j )t E (i )0節(jié)點連接而成的線路是關(guān)鍵線路P N tnt net7、在一個隨機

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

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

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

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

6、狀態(tài)變量、決策變量并寫出狀態(tài)轉(zhuǎn)移方程； (2) 寫出規(guī)范的（形式）基本方程； (3) 求解。5銷地B1B2B3B4產(chǎn)量產(chǎn)地A141158A2126110A375143銷量8563(1) 求其最優(yōu)解（可取初始調(diào)運方案為： x122 , x13 6 , x217 , x223 , x31 1 , x34 3 ）；(2) 若價值系數(shù) C2,4 由 1 變?yōu)?3,所求最優(yōu)解是否仍為最優(yōu)解； (3) 若所有價值系數(shù)均增加1,最優(yōu)解是否改變？6有一輛卡車最大載重為10 噸，用以裝載 3 種貨物，每種貨物的單位重量及相應(yīng)的單位價值如下表所示，問如何裝載可使運輸貨物的總價值最大？貨物編號單位重量（噸）345單

7、位價值456三、建立模型并計算1. 設(shè)有 A，B，C，D 四個工人，可以完成 1，2，3，4 四項工作任務(wù)，由于每個工人完成不同的任務(wù)成本不同，試建立總成本最低的指派模型并求解。工人 任務(wù)1234A79813B16161511C16191015D1617141632. 某采油區(qū)已建有 n 個計量站 B1，B2 Bn，各站目前尚未被利用的能力為 b1，b2 bn（噸液量 / 日）。為適應(yīng)油田開發(fā)的需要，規(guī)劃在該油區(qū)打m 口調(diào)整井 A1，A2Am，且這些井的位置已經(jīng)確定。根據(jù)預(yù)測，調(diào)整井的產(chǎn)量分別為a1，a2 am（噸液量 / 日）。考慮到原有計量站富余的能力，決定不另建新站，而用原有老站分工管轄

8、調(diào)整井。按規(guī)劃要求，每口井只能屬于一個計量站。假定 Ai 到 Bj 的距離 dij 已知，試確定各調(diào)整井與計量站的關(guān)系，使新建集輸管線總長度最短。 (設(shè)定變量，寫出模型 )。3不允許缺貨、補充時間無限短的確定型存儲模型的假設(shè)條件是：不允許缺貨補充時間無限短需求是連續(xù)的且需求速率為常數(shù)單位物資單位時間的存儲費用1 是常數(shù)每次定購費 3（不考慮貨款）是常數(shù)試：（）畫出存儲量變化曲線； （2）分析費用，建立總平均費用最低的訂貨模型（訂貨周期、訂貨量）。四、繪圖并計算某工程的 PERT數(shù)據(jù)如下表工序緊前工序作業(yè)時間工序緊前工序作業(yè)時間A_3FC8BA4GC4CA5HD,E2DB,C7IG3EB,C7J

9、H,I2(1) 畫出網(wǎng)絡(luò)圖并予節(jié)點以正確的編號； (2) 計算最早 . 最遲節(jié)點時刻； (3) 據(jù)所畫網(wǎng)絡(luò)圖填寫計算下表。ij作業(yè)代號teseflslftf關(guān)鍵工序4運籌學(xué)綜合復(fù)習(xí)資料參考答案一、判斷題題目12345678910答案xx題目11121314151617答案xx二、計算題1. 參考答案：2. 參考答案：x131x146x234x313x326x3403. 參考答案：(1)x17x23z17222(2)y10y21y3 12，短缺資源為設(shè)備 B 與調(diào)試工序。4(3)x13x22z815 415 23(4)x330 2 101 41 241，故產(chǎn)品值得生產(chǎn)。01 43 224.參考答

10、案：(1)設(shè)狀態(tài)變量sk 表示 k 階段開始時，可供分配的機器臺數(shù)；決策變量xk 表示 k 階段分配給 k 工廠機器臺數(shù)，則狀態(tài)轉(zhuǎn)移方程為：sk 1 sk xk5f 4 (s4 )0(2)f k (sk )max vk sk , xkf k 1 sk 1k 3,2,10 xk sks k 1 sk xk(3) x1 0 x2 2 x3 1 f1 3 145參考答案：（ 1）最優(yōu)調(diào)運方案：x12=2x13=6X21=4x22=3x23=3X31=4（ 2）是（ 3）不改變6參考答案：運送第一種貨物2 件，運送第二種貨物1 件，共重 10 砘，可達最大價值為13。三、建立模型并計算1. 參考答案：

11、x111x241x331x4212. 參考答案：設(shè) xij 表示 i 井是否連到 j 站mnMin zdij xiji1j 1ns.t.xij1i1mj 1mai xijb jj1ni1var iable positive3參考答案：S0tT平均存儲費用：6平均存儲量1t1RttRtdt20平均存儲費用1 RC t21訂貨費：一個周期內(nèi)的平均每天的訂貨費C 3t總平均費用：C t1 RC1 t C 32t模型的建立：令 dC t1 RC1C30（其中d 22C3 t 3）dt2tdt 2則得 :2C3Q*2RC3C t *2C1C3 Rt*C1RC1四、繪圖并計算參考答案：6471 29358節(jié)點最早節(jié)點時刻最遲節(jié)點時刻節(jié)點最早節(jié)點時刻最遲節(jié)點時刻10061515233715153