工程碩士運(yùn)籌學(xué)考試

1、一判斷下述說法的正誤（每題2分共20分）（1） 線性規(guī)劃（LP）問題的最優(yōu)解一定是基本可行解。（ ）（2） 若LP對(duì)偶問題有可行解，則原問題必有有限最優(yōu)解。（ ）（3） 若X是某個(gè)LP問題的基本可行解，則X必是可行域頂點(diǎn)。 （ ）（4） 若增加極小化LP模型的約束方程個(gè)數(shù), 則可能會(huì)使其最優(yōu)值變大（ ）（5） 在LP靈敏度分析中，改變Ci只影響Xi的檢驗(yàn)數(shù)。（ ）（6） 凡是多段決策問題都可用動(dòng)態(tài)規(guī)劃予以求解。 （ ）（7） 適合用DP求解的決策問題，目標(biāo)函數(shù)應(yīng)關(guān)于階段效應(yīng)可分離。（ ）（8） 由P個(gè)點(diǎn)，P-1個(gè)邊構(gòu)成的圖G就是樹。 （ ）（9） 沒有負(fù)回路的網(wǎng)絡(luò)最短路問題，都可以用Dijks

2、tra算法求解。 （ ）（10） 網(wǎng)絡(luò)最大流算法中的流量增廣鏈上必?zé)o飽和弧。（ ）二選擇題：（15分）（1）已知X1 = (1, 2), X2 = (2, 4)是某LP的兩個(gè)基本可行解, 則_必不是該LP的可行解. A) X = (3, 4) B) X = (1.5, 3) C) X = (2.5, 5) D) X = (5, 2)（2）影子價(jià)格的定義是 ，其計(jì)算公式為 ，經(jīng)濟(jì)含義為 。A）B-1b B）單純形乘子C）單位資源市場價(jià)格D）CBB-1 E）對(duì)偶問題最優(yōu)解 F）資源的邊際效用（3） 某連通圖G的各個(gè)頂點(diǎn)的次分別為2，1，3，2，3，2，1，2，2，2，則G 。A） 是樹B）不是樹C

3、）無法判斷（4）當(dāng)需求量增加50%時(shí)，經(jīng)濟(jì)訂購批量將 ：A) 約增加50%； B) 約減少100%； C) 約增加22.5%； D) 約減少22.5%（5）在用福德福克遜方法求得網(wǎng)絡(luò)最大流時(shí)，設(shè)為最小割，則在網(wǎng)絡(luò)中從S到的弧都應(yīng)是 （ ）A) 零流??； B) 飽和弧； C)非飽和??； D)非零流??；三簡答題（每題5分，共10分）1簡要描述表上作業(yè)法求解運(yùn)輸問題時(shí)確定初始調(diào)運(yùn)方案的原則；（50字左右）2簡要描述動(dòng)態(tài)規(guī)劃求解過程；（50字左右）四建模題（每題10分，共20分）1有一艘貨輪，分前后兩個(gè)艙位，它們的容積與最大載重量如下表所示?，F(xiàn)有三種物品需要裝船運(yùn)走，有關(guān)數(shù)據(jù)如表所示。為了安全，要求前

4、后倉的貨物重量之比與載重能力之比的偏差不超過10%，試建立LP模型。（不求解）前艙后艙最大允許載重量（噸）22003300容積（立方米）45005500商品數(shù) 量（件）每件體積（立方米/件）每件重量（噸/件）運(yùn)價(jià)（元/件）A5001081000B70015161700C400171416002 某甲工廠廠長欲為所生產(chǎn)的A、B、C 三種產(chǎn)品制定第一季度的生產(chǎn)銷售計(jì)劃。在生產(chǎn)計(jì)劃討論會(huì)上，各部門匯報(bào)的信息如下： 生產(chǎn)部:： A, B, C 三種產(chǎn)品的生產(chǎn)成本依次為36, 43, 52元；生產(chǎn)單位產(chǎn)品所需原材料1依次為2, 1, 2公斤；原材料2依次為3, 2, 1公斤, 所需工時(shí)依次為3, 2,

5、3；工廠第一季度可使用的最大工時(shí)數(shù)為300000。 物資部：工廠第一季度可使用的原材料1為250000公斤，原材料2為 350000公斤。原材料的購入價(jià)依次為6, 7元。 銷售部：A, B, C 三種產(chǎn)品的銷售成本依次為4, 4, 3元；銷售價(jià)格依次為75, 64, 83元；根據(jù)已經(jīng)簽定的購貨意向協(xié)議，各產(chǎn)品需求量依次為25000, 15000, 10000；其中若采用促銷手段, 則可使B產(chǎn)品的市場容量增加6,000, 增加部分的銷售成本6元, 價(jià)格為61元。 倉庫：A, B, C 三種產(chǎn)品的現(xiàn)有庫存量依次為1500, 800, 1500；第一季度末的保險(xiǎn)庫存量依次為1800, 1000, 1

6、000。 廠辦公室：接乙工廠電話, 該廠請(qǐng)甲廠轉(zhuǎn)讓一部分原材料1, 轉(zhuǎn)讓價(jià)格為7.8元/公斤。 試建立此問題的LP模型. 五計(jì)算題： 1 （15分）某工廠生產(chǎn)A、B、C三種產(chǎn)品，每種產(chǎn)品都需要工時(shí)和材料兩種資源，以總利潤最大為目標(biāo)，所建立的生產(chǎn)計(jì)劃線性規(guī)劃模型如下：其中x1, x2, x3為A、B、C的生產(chǎn)數(shù)量(單位：噸)，下表中給出了最優(yōu)生產(chǎn)計(jì)劃對(duì)應(yīng)的單純型表(只保留三位小數(shù))。 CB XB cj810300 qxjb x1x2x3x4x58x17.5100.750.417-0.08310x27.501-0.25-0.25025-13500-0.5-0.833-1.833試分別回答以下問題：

7、（1） 由于市場原因，A產(chǎn)品的單位利潤由8千元改變?yōu)?.5千元，你將做何決策？（2） 若可以再購買10單位的原材料，則單位價(jià)格超過多少時(shí)購買是不經(jīng)濟(jì)的？ （3） 若企業(yè)又有一筆資金要投入到購買原材料和工時(shí)上，你有什么建議？2（10分）某網(wǎng)絡(luò)圖上各個(gè)結(jié)點(diǎn)之間的距離如下圖所示, Li,j 表示Vi與Vj之間的一步距離。V2V4V3V7591096647V568V16V681011V8選用合適的網(wǎng)絡(luò)最短路方法求解V1到V8的最短距離和最短路線。3（10分）某羽毛球俱樂部每周需要給會(huì)員提供60打羽毛球，羽毛球的市場價(jià)格是每打10元；俱樂部保存羽毛球的年費(fèi)用是采購單價(jià)的2%，每次訂貨需要10元錢的訂貨費(fèi)

8、；由于業(yè)務(wù)需要，俱樂部需要保留60打的最低庫存；訂貨提前期1周。要求： 1) 畫出庫存量變化圖；2) 計(jì)算經(jīng)濟(jì)訂貨批量(每年按48周計(jì)算)；3) 計(jì)算訂貨點(diǎn)。一判斷下述說法的正誤（每題2分共20分）1（F）2（F）3（T）4（T） 5（F）6（F）7（T）8（F）9（F）10（F）二選擇題：（15分）1（C） 2（E、D、F） 3（B） 4（C） 5（B）三簡答題（每題5分，共10分）1原則： a基變量的值均為非負(fù)，且總數(shù)恰好為m+n-1個(gè)； b所有的約束條件均得到滿足； c所得的變量不構(gòu)成閉回路。2在構(gòu)建出動(dòng)態(tài)規(guī)劃模型后，首先利用動(dòng)態(tài)規(guī)劃基本方程逆序求出條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集

9、合，然后順序地求出最優(yōu)目標(biāo)值、最優(yōu)策略和最優(yōu)路線。四建模題（每題10分，共20分）1、用i =1，2，3 依次表示A、B、C三種商品，用j =1，2依次表示前、后兩個(gè)艙位。設(shè)xji為i商品裝入j艙位的數(shù)量，目標(biāo)函數(shù)為總運(yùn)費(fèi)收入Z，則模型為22 用xi, i =1，2，3 依次表示A、B、C三種產(chǎn)品的生產(chǎn)量；用yj, j =1，2，3, 4 依次表示A銷售量、B的正常銷售量、B的促銷量、C銷售量；用w表示原材料1的轉(zhuǎn)讓數(shù)量。則銷售收入為；生產(chǎn)成本為；銷售成本為；轉(zhuǎn)讓原材料1的收益為；最終，模型為五計(jì)算題： 1 （1）由表格可計(jì)算出保持原生產(chǎn)計(jì)劃不變的A的單位利潤的變化范圍為(7.333, 30)

10、產(chǎn)品，所以應(yīng)繼續(xù)執(zhí)行原計(jì)劃。（2）由表格可知，原材料的影子價(jià)格為1.833,故原材料的購買價(jià)格不應(yīng)高于1.833。（3） 應(yīng)將資金投放到（資源的影子價(jià)格-購買資源的價(jià)格），即邊際效益高的資源上；但應(yīng)注意到資源的邊際效益會(huì)隨著資源的增加而下降，所以同時(shí)應(yīng)隨時(shí)比較資源的邊際效益的變化。2V1到V8的最短距離為18，最短路線為V1，V3，V5 ，V83（10分）1) 庫存量變化圖；QTtQ0602) 經(jīng)濟(jì)訂貨批量；, h = 0.2 , k=103) 訂貨點(diǎn)=60+60=120，即庫存量降至120打時(shí)發(fā)出訂單。1. 判斷下述論述的正誤(在括號(hào)填入T 或F ) 或填空:(1) 凸集的頂點(diǎn)個(gè)數(shù)必為有限個(gè)

11、. （ 如圓等） （錯(cuò)）(1) 任何凸集均可找到一LP模型與之對(duì)應(yīng). （表面為曲面或者曲線就不行了） (錯(cuò))(2) LP模型的可行域的頂點(diǎn)必為有限個(gè). (對(duì))(3) LP模型的基本可行解必為有限個(gè). (對(duì)) 頂點(diǎn)和基本可行解一一對(duì)應(yīng)(4) 某LP模型有且僅有兩個(gè)最優(yōu)解. （要么唯一，要么無窮多個(gè)） (錯(cuò))(5) 某LP模型有且僅有有限個(gè)(大于等于2)最優(yōu)解. (錯(cuò))(6) 某LP模型有無窮多個(gè)最優(yōu)解. （任何線性規(guī)劃模型都有無窮多個(gè)是錯(cuò)的） (對(duì))(7) 若LP模型存在可行解, 則必存在最優(yōu)解 （無有限最優(yōu)解的情況存在） (錯(cuò))(8) 若LP模型的可行域非空有界, 則其頂點(diǎn)中必存在最優(yōu)解 (對(duì)

12、)(9) 若LP模型的可行域非空, 則其頂點(diǎn)中必存在最優(yōu)解 （無界） (錯(cuò))(10) 若X是某LP模型的最優(yōu)解, 則X必為該LP模型可行域的某一個(gè)頂點(diǎn). （有可能在邊界上） (錯(cuò))(11) 若X是某LP模型的基本解, 則X必為該LP模型可行域的某一個(gè)頂點(diǎn). (錯(cuò))(12) 某LP的兩個(gè)基本可行解中零分量的個(gè)數(shù)必相同. (基變量等于零的個(gè)數(shù)不一定相同，退化的基本可行解) (錯(cuò))(13) 在單純形算法中, 采用最小比值原則確定換出變量是為了保持解的可行性. (對(duì))(14) 對(duì)偶單純形算法中, 采用最小比值原則確定換出變量是為了保持對(duì)偶解的可行性.（改善解的可行性） (錯(cuò))(15) 若增加極大化LP

13、模型的約束方程個(gè)數(shù), 則可能會(huì)使其最優(yōu)值變大. (錯(cuò))(16) 若增加極小化LP模型的約束方程個(gè)數(shù), 則可能會(huì)使其最優(yōu)值變小. (錯(cuò))(15) 若減少極大化LP模型的約束方程個(gè)數(shù), 則可能會(huì)使其最優(yōu)值變大. (對(duì))(16) 若減少極小化LP模型的約束方程個(gè)數(shù), 則可能會(huì)使其最優(yōu)值變小. (對(duì)) 增加約束條件個(gè)數(shù)，最優(yōu)值變差，減少約束條件個(gè)數(shù)，最優(yōu)值變好！(17) 在運(yùn)輸問題中, 任一組M+N個(gè)變量必含有閉回路. （M+N-1） (對(duì))(18) 在運(yùn)輸問題中, 可任選一組M+N-1個(gè)變量作為基變量. （不能任選） (錯(cuò))增廣路概念2個(gè)條件：1）正向非飽和 U+ 2）反向非零流 U- (19) 設(shè)

14、是用FORT-FULKERSON方法求解網(wǎng)絡(luò)最大流過程中所的得一條增廣路，則+ 上必?zé)o零流弧. (錯(cuò))(20) 設(shè)為是用FORT-FULKERSON方法求解網(wǎng)絡(luò)最大流過程中所的得一條增廣路,則- 上必?zé)o飽和弧. (錯(cuò))(21) 用Dijkstra算法求網(wǎng)絡(luò)的最短路時(shí), 使用條件是該網(wǎng)絡(luò)不含負(fù)回路. （負(fù)權(quán)，權(quán)重非負(fù)，fude算法是不含負(fù)回路，可以有負(fù)權(quán)） (錯(cuò))(22) 由P個(gè)頂點(diǎn), P-1條邊組成的圖G必為樹. （連通圖，或者無圈圖可以） (錯(cuò)) (24) 某連通圖G的各頂點(diǎn)的次分別為 2, 3, 1, 2, 1, 2, 1, 2, 則G A A) 是樹 B) 不是樹 C) 不一定是樹 D)

15、 條件不夠, 無法判斷.(24) 某圖G的頂點(diǎn)數(shù) p 等于其邊數(shù) q + 1, 則G _C_. (不知道是否連通，是否無圈) a 是樹 b 不是樹 c 條件不夠, 無法判斷.(24) 連通圖G的可達(dá)陣M的元素mij 必為1. ( )(24) 點(diǎn)vi 是圖G的孤立點(diǎn), 則圖G的可達(dá)陣M的元素mij 必為0. ( ) (26) 用對(duì)偶法求解最大流-最小費(fèi)用問題的過程中, 均可用Dijkstra算法求所繪 的增廣費(fèi)用網(wǎng)絡(luò)的最短路（第一個(gè)可以用） (錯(cuò)) (31) 建立動(dòng)態(tài)規(guī)劃模型的四個(gè)要素一個(gè)方程是指:_1）動(dòng)態(tài)規(guī)劃模型2）狀態(tài)變量1）動(dòng)態(tài)規(guī)劃基本方程_ _ _. (33) 用表上作業(yè)法求解運(yùn)輸問題

16、時(shí), 常用的確定初始方案的兩個(gè)方法是:西北角法 _ _和_最小元素法_, 常用的確定檢驗(yàn)數(shù)的兩個(gè)方法是: _閉回路法_和_衛(wèi)氏法_.(34) 已知X1 = (1, 2), X2 = (2, 3)是某LP的兩個(gè)可行解, 則_B_也是該LP的可行解. a. X = (3, 4) b. X = (1.5, 2.5) c. X = (1.2, 1.8) d. 條件不夠, 無法判斷. (34) 已知X1 = (1, 2), X2 = (2, 4)是某LP的兩個(gè)基本可行解, 則_C_必不是該LP的可行解. 在線上，且不在兩個(gè)點(diǎn)之間（即在延長線上的） A) X = (3, 4) B) X = (1.5, 3

17、) C) X = (2.5, 5) D) X = (5, 2) E) 條件不夠, 無法判斷.(35) 在單純形的最優(yōu)表上, 最優(yōu)解不唯一, 則_A_ (至少有一個(gè)非基變量的檢驗(yàn)數(shù)為零) a. 非基變量的檢驗(yàn)數(shù)必有為零者 b. 非基變量的檢驗(yàn)數(shù)不必有為零者.(36) 已知原問題有可行解, 但無最優(yōu)解. 則原問題的對(duì)偶問題_A_. (都有可行解都有最優(yōu)解) a. 無可行解 b. 有可行解, 但無最優(yōu)解 c. 有可行解且有最優(yōu)解(37) 已知某極大化LP問題及其對(duì)偶問題均有可行解, 而Y1 , Y2 為對(duì)偶問題的兩個(gè)可行解, 它們對(duì)應(yīng)的目標(biāo)函數(shù)值分別為4, 7. 則原問題的最優(yōu)值Z滿足_A_ （極大

18、化原問題<最小的可行解；極小化原問題<最大可行解） a. Z < 4 b. 7 < Z c. 4 < Z < 7（一定不可能）(38) 極小化(MinZ)LP問題可轉(zhuǎn)化為目標(biāo)函數(shù)取極大化即_B_的問題求解. 而原問 題的目標(biāo)函數(shù)值等于_C_. a. MaxZ b. Max(-Z) c. -Max(-Z) d. -MaxZ(39) 對(duì)產(chǎn)銷不平衡的運(yùn)輸問題, 可通過_引入虛擬產(chǎn)地_或_引入虛擬需求點(diǎn)（產(chǎn)量等于供需缺口來平衡）_ 的方法, 將其轉(zhuǎn)化產(chǎn)銷平衡的運(yùn)輸問題求解.(40) 通常, 運(yùn)輸問題的變量個(gè)數(shù)為_B_, 其基由_C_個(gè)變量組成. a. M + N b

19、. M * N c. M + N - 1 d. M + N + 1(41) 在網(wǎng)絡(luò)分析中, 所求得的最大流_C_唯一(最大流量一定相同的), 所求得的最短路_C_唯一. a. 一定 b. 一定不 c. 不一定1. 求解LP的單純形法中，先確定 入基 變量，后確定 出基 變量。入基變量是按照 的原則確定的，其目的是 ，出基變量是按照 確定的，是為了 。A) 使目標(biāo)函數(shù)值得到改善；B) 保持解的可行性；C) 決策變量小于零；D) 檢驗(yàn)數(shù)大于零；E) 最小比值法；F)消除解的不可行性；G) 入基變量； H)出基變量2. 求解線性規(guī)劃模型時(shí)，引入人工變量是為了 B (敲門轉(zhuǎn)，使得問題可以繼續(xù)解決，最后

20、人工變量都是要出基的！如果最后沒有出基，那就問題沒有可行解) 。A) 使該模型存在可行解；B) 確定一個(gè)初始的基本可行解；C) 使該模型標(biāo)準(zhǔn)化；3. 影子價(jià)格的定義是 B ，其計(jì)算公式是 D ，經(jīng)濟(jì)含義是 E 。A) B-1b；B) 對(duì)偶問題的最優(yōu)解；C) 單純形乘子；D) CBB-1；E) 購買單位資源時(shí)企業(yè)所付出的代價(jià)；F) 約束條件所付出的代價(jià)；4. 建立動(dòng)態(tài)規(guī)劃模型的要素包括有： 4大要素，一個(gè)方程。 5. 容量網(wǎng)絡(luò)上滿足 C F 條件的 G 稱為可行流.A) 費(fèi)用最??；B) 無重邊也無環(huán)；C) 容量限制；D) 弧上的流；E) 正向飽和反向非零流；F) 中間點(diǎn)平衡條件；G) 圖上的流；

21、H) 最大流最小割定理；I) 線性約束條件6. 在求解網(wǎng)絡(luò)最大流的標(biāo)記化算法中，增廣路是滿足 F C 的從源頂點(diǎn)到匯頂點(diǎn)的一條通路。A) 增廣路上的弧均為非零流弧；B) 增廣路上的弧均非飽和弧；C) 增廣路上反向弧均為非零流弧；D) 增廣路上的正向弧均為非零流??；E) 增廣路上反向弧均為非飽和??；F) 增廣路上的正向弧均為非飽和??；7. 求最小費(fèi)用最大流的對(duì)偶法求解思路是始終保持 E 是 G ,通過不斷調(diào)整, 使 C 逐步 A , 最終成為最小費(fèi)用最大流。A) 增大； B) 減少； C)流量； D)費(fèi)用； E)可行流； F)最大流；G)最小費(fèi)用流；8. 運(yùn)輸問題的模型的變量個(gè)數(shù)為 A ，其中基

22、變量個(gè)數(shù)為 C ；用表上作業(yè)法求解該模型時(shí)，常用的確定初始調(diào)運(yùn)方案的方法有 ，求檢驗(yàn)數(shù)的方法有 ；A) m+n；B) m´n；C) m+n-1；D) 人工變量法；E) 行最小法；F) 閉回路法；G) 西北角法；H) 最小元素法；I) 行變換法；J) 位勢法；9. 若可行域是空集,則表明存在矛盾的約束條件。( 對(duì) )10. 用表格單純形法求解LP問題，若最終表上非基變量的檢驗(yàn)數(shù)均非正（要求嚴(yán)格小于零），則該模型一定有唯一的最優(yōu)解。( 錯(cuò) )13. 用表格單純形法求解LP問題，若最終表上某非基變量的檢驗(yàn)數(shù)為零（是必要條件，非充分條件，除非加上“基變量都大于零”），則該模型有無窮多個(gè)最優(yōu)解

23、。(錯(cuò) )11. 單純形法的思路是保持基的可行性, 逐步迭代達(dá)到基的對(duì)偶可行性。(對(duì))12. 對(duì)偶單純形法的思路是：保持對(duì)偶問題的基的可行性, 逐步迭代達(dá)到原問題的基的可行性。(對(duì))13. 若原問題存在可行解，但無有限最優(yōu)解,則對(duì)偶問題可行解不存在。(對(duì))14. 當(dāng)有負(fù)權(quán)（無負(fù)權(quán)）時(shí),可用D氏標(biāo)號(hào)法求網(wǎng)絡(luò)最短路問題, 當(dāng)存在負(fù)回路時(shí),可以用列表法(FORD算法)或函數(shù)迭代法求解最短路問題。( 錯(cuò) )15. 適合用動(dòng)態(tài)規(guī)劃模型求解的多段決策問題的目標(biāo)函數(shù)，必須具有關(guān)于階段效應(yīng)的可分離形式。 ( 對(duì) )16. 線性規(guī)劃靈敏度分析中，若變量在目標(biāo)函數(shù)中的系數(shù)發(fā)生變化，只影響最終單純形表中該變量的檢驗(yàn)

24、數(shù)。 ( 錯(cuò) )二、建模題(共20分，每小題10分)1. 某工廠生產(chǎn)A、B、C三種產(chǎn)品，現(xiàn)欲根據(jù)訂貨合同以及生產(chǎn)狀況制定5月份的生產(chǎn)計(jì)劃。已知合同甲為：A產(chǎn)品1000件，單件價(jià)格為500元，違約金為100元/件；合同乙：B產(chǎn)品500件，單件價(jià)格為400元，違約金為120元/件；合同丙：B產(chǎn)品600件，單件價(jià)格為420元，違約金為130元/件；C產(chǎn)品600件，單件價(jià)格為400元，違約金為90元/件；有關(guān)各產(chǎn)品生產(chǎn)過程所需工時(shí)以及原材料的情況見表1，試以利潤為目標(biāo)，建立該工廠的生產(chǎn)計(jì)劃線性規(guī)劃模型（不求解）。表1工序1工序2工序3原材料1原材料2其它成本/件產(chǎn)品A2323410產(chǎn)品B1132310

25、產(chǎn)品C2124210總工時(shí)（原材料）460040006000100008000工時(shí)原材料成本（元某單位擬將四種物品從救災(zāi)現(xiàn)場搶運(yùn)到另一城市，其運(yùn)輸工具為一架運(yùn)輸機(jī)，且只能運(yùn)輸一趟。該飛機(jī)的載重能力為45噸，貨艙空間為20m3。已知4種物品的有關(guān)數(shù)據(jù)如表2所示。試為該單位制定使總價(jià)值為最大的運(yùn)輸方案。只建立動(dòng)態(tài)規(guī)劃模型，不求解。 表2物 品重 量 (kg)體 積 (m3)價(jià) 值 (元)13000.41500022000.3800031000.2900041500.26000三. 現(xiàn)有40臺(tái)某種大型成套設(shè)備要裝入一艘遠(yuǎn)洋貨輪運(yùn)走，每套該設(shè)備由兩大部件組成，各部件的重量、體

26、積如下表1所示。已知貨輪有兩個(gè)貨艙，每個(gè)貨艙的載重量與容積如下表2所示。每套設(shè)備的運(yùn)費(fèi)為40萬元，裝不走的設(shè)備可以留下，航行安全要求各艙的實(shí)際載重之比與它們的載重能力之比的誤差不超過10，試建立線性規(guī)劃模型以確定使裝載運(yùn)費(fèi)收入最大的裝運(yùn)方案（不求解；忽略整數(shù)要求）。表2表1部件重量（噸）體積(m3 )125070280100貨艙載重（噸）容積(m3 )160002500240002500四、某公司需要將50萬元技改資金根據(jù)下屬甲、乙、丙三個(gè)工廠的技改項(xiàng)目進(jìn)行分配。已知各工廠申報(bào)的技改項(xiàng)目如下：甲工廠：項(xiàng)目A：需投資10萬元，預(yù)計(jì)可增加年利潤2萬元；項(xiàng)目B：需投資15萬元，預(yù)計(jì)可增加年利潤4萬元

27、；項(xiàng)目C：需投資20萬元，預(yù)計(jì)可增加年利潤6萬元。乙工廠：項(xiàng)目A：需投資5萬元，預(yù)計(jì)可增加年利潤1.5萬元；項(xiàng)目B：需投資15萬元，預(yù)計(jì)可增加年利潤5萬元；項(xiàng)目C：需投資25萬元，預(yù)計(jì)可增加年利潤5萬元。丙工廠：項(xiàng)目A：需投資15萬元，預(yù)計(jì)可增加年利潤3萬元；項(xiàng)目B：需投資15萬元，預(yù)計(jì)可增加年利潤3.5萬元；項(xiàng)目C：需投資20萬元，預(yù)計(jì)可增加年利潤4萬元；項(xiàng)目D：需投資30萬元，預(yù)計(jì)可增加年利潤5萬元。試建立關(guān)于技改資金分配的動(dòng)態(tài)規(guī)劃模型（不求解）。三段問題，而非十段問題！T1v1v2v3v5(200)(100)(60)(100)(120)(150)(220)(240)(280)v6(80)

28、(110)(150)T2470S(210)(225)六、(20分)如下所示為北大荒某農(nóng)場灌溉系統(tǒng)的網(wǎng)絡(luò)模型。圖中，S為初級(jí)提水泵站，所標(biāo)數(shù)值為泵站的日提水量；vi為具備分流功能的次級(jí)泵站，其中v6的能力為290，其他次級(jí)泵站的能力均超過該泵站輸水管道能力之和；弧為埋藏式地下輸水渠道，所標(biāo)數(shù)值為渠道輸水設(shè)計(jì)能力；T1、T2為兩個(gè)農(nóng)田灌區(qū)，所標(biāo)數(shù)值為各灌區(qū)目前灌溉用水的需求量。1、 在不考慮灌區(qū)目前灌溉用水的需求量的前提下，用計(jì)算機(jī)軟件求出該系統(tǒng)網(wǎng)絡(luò)的最大輸水能力與各個(gè)次級(jí)泵站的分流控制方案，并標(biāo)注在你繪制的網(wǎng)絡(luò)圖上。2、 根據(jù)農(nóng)場發(fā)展規(guī)劃，明年各灌區(qū)水的日需求量將有顯著增加，現(xiàn)有的灌溉系統(tǒng)可能不

29、能夠滿足要求，需要改造。問應(yīng)如何改造？為什么？在改造過程中，應(yīng)注意那些問題？（找到系統(tǒng)中的所有最小割，對(duì)未來需求進(jìn)行預(yù)測，瓶頸問題，投入產(chǎn)出問題）可能求解題類型）線性規(guī)劃靈敏度分析）和運(yùn)輸問題表上作業(yè)法）最短路、最短樹）庫存控制動(dòng)態(tài)規(guī)劃絕對(duì)不會(huì)求解，只會(huì)建模。2. 某甲工廠廠長欲為其所生產(chǎn)的A, B, C 三種產(chǎn)品制定第一季度的生產(chǎn) 銷售計(jì)劃. 各部門匯報(bào)的信息如下: 生產(chǎn)部: A, B, C 三種產(chǎn)品的生產(chǎn)成本依次為56, 31, 42元; 生 產(chǎn)單位產(chǎn)品所需原材料1依次為2, 1, 2公斤; 原材料2依次為3, 2, 1 公斤, 所需工時(shí)依次為3, 2, 3; 工廠第一季度可使用的最大工時(shí)

30、數(shù)為 300000. 物資部: 工廠第一季度可使用的原材料1為200000公斤, 原材料2為 250000公斤. 原材料的購入價(jià)依次為6, 7元. 銷售部: A, B, C 三種產(chǎn)品的銷售成本依次為2, 3, 2元; 銷售價(jià) 格依次為75, 52, 63元;市場容量依次為20000, 10000, 10000; 其中若采用促銷手段, 則可使B產(chǎn)品的市場容量增加5,000, 增加 部分的銷售成本3元, 價(jià)格為50元. 倉庫: A, B, C 三種產(chǎn)品的現(xiàn)有庫存量依次為1000, 800, 1500; 第一季度末的保險(xiǎn)庫存量依次為1500, 1800, 1000. 廠辦公室: 接乙工廠電話, 該廠

31、請(qǐng)甲廠轉(zhuǎn)讓一部分原材料1, 轉(zhuǎn)讓價(jià) 格為7.8元/公斤. 試建立此問題的LP模型. (10分)3. 某工廠為其所生產(chǎn)的X1 , X2 , X3 三種產(chǎn)品制定生產(chǎn)計(jì)劃建立了如下所示的LP模型: Max Z = 4X1 + 2X2 + 3X3 s.t. 2X1 + 2X2 + 4X3 < 100 原材料1 3X1 + X2 + 6X3 < 100 原材料2 X1 , X2 , X3 > 0(1) 用表格單純形法求最優(yōu)生產(chǎn)計(jì)劃.(2) 在所得最優(yōu)表的基礎(chǔ)上, 分別就以下情況單獨(dú)發(fā)生時(shí), 進(jìn)行靈敏度分析:(a) 由于市場變化, 產(chǎn)品X1 的單位利潤可能改變, 求此變化保持在那個(gè)范圍內(nèi)

32、時(shí), 最優(yōu)生產(chǎn)計(jì)劃不須改變; 若產(chǎn)品X1 的單位利潤變?yōu)?, 求相應(yīng)的最優(yōu)生產(chǎn)計(jì)劃.(b) 由于原材料市場變化, 原材料1的供應(yīng)量從100個(gè)單位降低為50個(gè)單位, 問此變化是否影響原最優(yōu)生產(chǎn)計(jì)劃? 若影響,求相應(yīng)的最優(yōu)生產(chǎn)計(jì)劃.2.1 某工廠為其所生產(chǎn)的X1 , X2 , X3 三種產(chǎn)品制定生產(chǎn)計(jì)劃建立了如下所示的LP模型: Max Z = 4X1 + 2X2 + 3X3 s.t. 2X1 + 2X2 + 4X3 < 100 3X1 + X2 + 6X3 < 100 3X1 + X2 + 2X3 < 120 X1 , X2 , X3 > 0(1) 用表格單純形法求最優(yōu)生

33、產(chǎn)計(jì)劃.(2) 在所得最優(yōu)表的基礎(chǔ)上, 分別就以下情況單獨(dú)發(fā)生時(shí), 進(jìn)行靈敏度分析:(a) 由于市場變化, 產(chǎn)品Y的單位利潤可能改變, 求此變化保持在那個(gè)范圍內(nèi)時(shí), 最 優(yōu)生產(chǎn)計(jì)劃不須改變; 若產(chǎn)品Y的單位利潤變?yōu)?, 求相應(yīng)的最優(yōu)生產(chǎn)計(jì)劃.(b) 由于原材料市場變化, 原材料1的供應(yīng)量從100個(gè)單位降低為50個(gè)單位, 問此變化是否 影響原最優(yōu)生產(chǎn)計(jì)劃? 若影響,求相應(yīng)的最優(yōu)生產(chǎn)計(jì)劃.(c) 由于生產(chǎn)技術(shù)的改進(jìn), 產(chǎn)品Z的單位利潤, 消耗的工時(shí), 原材料發(fā)生變化, 從原先的3, 4, 6, 2依此變?yōu)?, 2, 2, 1. 求相應(yīng)的最優(yōu)生產(chǎn)計(jì)劃.2.2 某LP問題如下所示: Max Z = -

34、5X1 + 5X2 + 13X3 s.t. -X1 + X2 + 3X3 < 20 (1) 12X1 + 4X2 + 10X3 < 90 (2) X1 , X2 , X3 > 0(1) 用表格單純形法求最優(yōu)解.(2) 在所得最優(yōu)表的基礎(chǔ)上, 分別就以下情況單獨(dú)發(fā)生時(shí), 進(jìn)行靈敏度分析:(a) 目標(biāo)函數(shù)中, X2 的系數(shù)由5變?yōu)?.(b) 約束方程(2)右端的常數(shù)項(xiàng)由90變?yōu)?0.(c) 增加一個(gè)約束方程: 2X1 + 2X2 + 5X3 < 50典型考試題目如下：三、(25分)某工廠制造三種產(chǎn)品A、B和C，需要?jiǎng)趧?dòng)力和原材料兩種資源，為確定總利潤最大的生產(chǎn)計(jì)劃，可列出如

35、下的線性規(guī)劃模型：max Z = 4x1 + x2 + 5x3s.t. 6x1 + 4x2 + 5x3 £ 45(勞動(dòng)力限制) 3x1 + x2 + 5x3 £ 30(原材料限制) x1，x2，x3 ³ 0其中，x1，x2，x3分別是A、B、C的產(chǎn)量。表4為用單純形求解該模型所得到的最終表，表中x4、x5分別為勞動(dòng)力與原材料約束的松弛變量。根據(jù)最終表回答下列問題：C41500CBXBbx1x2x3x4x54x151101/3-1/35x330-2/51-1/52/5-Z-350-10-1/3-2/3（1）當(dāng)產(chǎn)品B的單位利潤由1元/件變?yōu)?元/件時(shí)，問是否必須修改生

36、產(chǎn)計(jì)劃，為什么？（2）當(dāng)產(chǎn)品A的單位利潤由4元/件變?yōu)?元/件時(shí)，問是否需要修改生產(chǎn)計(jì)劃？若不需修改計(jì)劃，陳述理由；若需修改計(jì)劃，計(jì)算得出新的生產(chǎn)計(jì)劃。（3）假如能以10元的代價(jià)，另外再獲得20個(gè)單位的原材料，通過計(jì)算結(jié)果說明這樣做是否有利？（4）若在原問題中增加一個(gè)設(shè)備約束條件：2x1 + x2 + 3x3 £ 20，這對(duì)于最優(yōu)解和對(duì)偶解有什麼影響？（把現(xiàn)在的最優(yōu)解代入這個(gè)約束條件，滿足沒有影響，不滿足則有影響）（5）若在原問題中，單位產(chǎn)品B消耗勞動(dòng)力的數(shù)量由4工時(shí)/件變?yōu)?工時(shí)/件，問是否需要修改生產(chǎn)計(jì)劃？若不需修改計(jì)劃，陳述理由；若需修改計(jì)劃，計(jì)算得出新的生產(chǎn)計(jì)劃。3. 某運(yùn)輸

37、問題的有關(guān)數(shù)據(jù)如下, 試用表上作業(yè)法制定運(yùn)費(fèi)最小的調(diào)運(yùn)方案. 運(yùn) 銷 價(jià) 地 產(chǎn)地 B1 B2 B3 產(chǎn)量 - A1 3 5 8 30 A2 7 4 2 50 A3 10 3 5 60 - 銷量 40 30 404.1 某公司擬將6萬元技改資金分配給下屬的A, B, C, 3個(gè)子公司, 各子公司在獲得不同數(shù)量的資金后的收益如下表所示. 試建立資金分配的動(dòng)態(tài)規(guī)劃模型, 并據(jù)此求出資金的最優(yōu)分配方案. - 投 資 (萬元) 0 1 2 3 4 5 6 - A 0 2 2 2 3 3 4 收益 B 0 1 2 2 4 5 6 C 0 2 2 3 3 3 4 -4.2 （可靠性問題，考試不會(huì)出了） 某

38、公司擬投入6萬元資金用于研制A1 , A2 , A3 , 3種新產(chǎn)品, 已知第k種新產(chǎn)品研制成功的可能性Pk 與投入的資金量Mk 的關(guān)系分別為: Pk = 1 - 1/( 1 + Rk * Mk ) 其中 R1 = 0.5, R2 = 1.0, R3 = 1.5 Mk = 0, 1, 2, 3, 4, 5, 6 萬元, ( k = 1, 2, 3 )求如何分配資金使三種新產(chǎn)品均研制成功的可能性最大. 試建立此問題的動(dòng)態(tài)規(guī)化模型并求解.四、（最短路問題）(10分)已知某網(wǎng)絡(luò)如下所示，試用Djikstra算法求網(wǎng)絡(luò)起點(diǎn)到終點(diǎn)的最短路。書寫格式盡量簡單，用最簡單的方式表示（表格形式）stv1v2v3

39、v5v6362185363373五、(10分)已知某容量網(wǎng)絡(luò)如下所示，圖中各弧上所標(biāo)數(shù)值依次為容量與可行流流量。試用Ford-Fulkerson標(biāo)記化算法求該網(wǎng)絡(luò)的最大流。必須以給定的可行流為初始流。stv1v2v3v5(12,8)(5,5)(6,4)(7,4)(3,3)(5,4)(7,4)(14,12)(10,8)v6(4,1)(8,4)(5,4)S1tv1v2v3v5(20)(5)(6)(10)(6)(10)(17)(20)(13)v6(6)(8)(12)S2121030六、(13分)如下所示為某城市的污水處理系統(tǒng)的網(wǎng)絡(luò)模型。圖中，si為各個(gè)污水源，si上所標(biāo)數(shù)值為相應(yīng)污水源的排污量； v

40、i為具備分流功能的污水匯集點(diǎn)；弧為排污管道，所標(biāo)數(shù)值為管道容量；t為中心污水處理廠，t上所標(biāo)數(shù)值為污水處理廠的處理能力。3、 試用計(jì)算機(jī)軟件求出該網(wǎng)絡(luò)的最大排污能力與各個(gè)匯集點(diǎn)的分流控制方案，并標(biāo)注在圖上。4、 根據(jù)城市發(fā)展規(guī)劃，若干年后各個(gè)排污點(diǎn)的排污量將有顯著增加，現(xiàn)有的排污管系統(tǒng)可能不能夠滿足要求，需要改造。問應(yīng)如何改造？為什么？在改造過程中，應(yīng)注意那些問題？一、(20分) 某物流公司為擴(kuò)大業(yè)務(wù)范圍并提高服務(wù)效率，考慮在北京、上海、廣州和武漢四個(gè)城市設(shè)立配送中心，這些配送中心將負(fù)責(zé)向華北、華中、華南三個(gè)地區(qū)供貨。配送中心的規(guī)模為兩種，一種月處理貨物為2000件，另一種月處理貨物為3000件。規(guī)模為2000的中心所需月費(fèi)用，在北京為6萬元，上海為8萬元，廣州為9萬元，武漢為5萬元。而規(guī)模為3000的中心所需月費(fèi)用依次為北京8萬元，上海10萬元，廣州11萬元，武漢7萬元。每個(gè)地區(qū)的月平均需求量分別為華北1500件，華中1800件，華南1700件。發(fā)送貨物的運(yùn)輸成本（元/件）見下表：華北華中華南北京200400500上海300250400廣州600350300武漢350150350公司希望在滿足地區(qū)需求