運(yùn)籌學(xué)2020最新試卷帶答案

1、運(yùn)籌學(xué)樣卷參考答案（48課時(shí)）一、判斷題（對(duì)的記/,錯(cuò)的記乂，共10分，每小題2分）線性規(guī)劃模型中增加一個(gè)約束條件，可行域的范圍一般將縮小，減少一個(gè)約束條件，可 TOC o 1-5 h z 行域的范圍一般將擴(kuò)大；（）已知y *為線性規(guī)劃的對(duì)偶問題的最優(yōu)解，若匕0說明在最優(yōu)生產(chǎn)計(jì)劃中第i種資源已完全耗盡；（）運(yùn)輸問題是一種特殊的線性規(guī)劃模型，因而求解結(jié)果也可能出現(xiàn)下列四種情況之一：有惟一最優(yōu)解、有無窮多最優(yōu)解、無界解和無可行解；（）求解整數(shù)規(guī)劃是可以先不考慮變量的整數(shù)約束，而是先求解相應(yīng)的線性規(guī)劃問題，然后 對(duì)求解結(jié)果中的非整數(shù)的變量湊整即得最優(yōu)解。（）11個(gè)公司之間可能只有4個(gè)公司與偶數(shù)個(gè)公司

2、有業(yè)務(wù)聯(lián)系；（）答案：1. T； 2. T；3. F； 4. F； 5. F二、選擇題（共15分，每小題3分）在利用圖解法求解最大利潤(rùn)問題中中，通過各極點(diǎn)作與目標(biāo)函數(shù)直線斜率相同的平行線，這些平行線稱之為。（）可行解B.可行域C.等利潤(rùn)線D.等成本線用單純形法求解線性規(guī)劃問題時(shí)引入的松弛變量在目標(biāo)函數(shù)中的系數(shù) 。（）0B.很大的正數(shù)C.很大的負(fù)數(shù)D.1以下關(guān)系中，不是線性規(guī)劃與其對(duì)偶問題的對(duì)應(yīng)關(guān)系的 。（）約束條件組的系數(shù)矩陣互為轉(zhuǎn)置矩陣一個(gè)約束條件組的常數(shù)列為另一個(gè)目標(biāo)函數(shù)的系數(shù)行向量?jī)蓚€(gè)約束條件組中的方程個(gè)數(shù)相等約束條件組的不等式反向需求量大于供應(yīng)量的運(yùn)輸問題需要做的。（）A.虛設(shè)一個(gè)需求

3、點(diǎn)B.刪去一個(gè)供應(yīng)點(diǎn)虛設(shè)一個(gè)供應(yīng)點(diǎn)，取虛設(shè)供應(yīng)量為恰當(dāng)值令供應(yīng)點(diǎn)到虛設(shè)的需求點(diǎn)的單位運(yùn)費(fèi)為0對(duì)一個(gè)求目標(biāo)函數(shù)最大的混合整數(shù)規(guī)劃問題，以下命題中不正確的 。（）其線性規(guī)劃松弛問題的最優(yōu)解可能是該整數(shù)規(guī)劃問題的最優(yōu)解。該問題可行解的個(gè)數(shù)一定是有限的；任一可行解的目標(biāo)函數(shù)值不可能大于其線性規(guī)劃松弛問題的目標(biāo)函數(shù)值；該問題可行解中可能存在不取整數(shù)值的變量。答案：6.C7.A 8.C 9.C 10.B三、簡(jiǎn)答題（每題5分，共15分）線性規(guī)劃問題的三個(gè)要素是什么？線性規(guī)劃模型有哪些特征？答案：線性規(guī)劃問題的三個(gè)要素是決策變量、目標(biāo)函數(shù)和約束條件。線性規(guī)劃模型的特征有：（1）目標(biāo)函數(shù)是決策變量的線性函數(shù)；（

4、2）約束條件是決策變量的線性（不）等式；（3）決策變量連續(xù)變化。利用0-1變量表示下列約束條件（要求說明0-1變量的意義）:x取值0，2，4，6，8中的一個(gè)答案：設(shè)y.= 1為取第j個(gè)數(shù)，否則必=0.則工=0 y + 2 y + 4 y + 6 y + 8)1234=1,5y + y + y + y + y=1,512345y = 0 or 1, j = 1,2,3.i j3.寫出求極大值的運(yùn)輸問題的產(chǎn)銷平衡表B1 .B2B3B4產(chǎn)量A17891030A21716151420A3534615銷量15101520答案：令新表中單位運(yùn)價(jià)為Cj = 17 -匕，總產(chǎn)量=6560=總銷量，增加一個(gè)虛擬

5、的銷地，銷量為5.B1B2B3B4B5產(chǎn)量A110987030A20123020A312141311015銷量151015205（10分=5分+5分）某產(chǎn)品有三個(gè)產(chǎn)地、四個(gè)銷地，各產(chǎn)地的產(chǎn)量、各銷地的銷量以及產(chǎn)地到 銷地之間的單位運(yùn)價(jià)見下表，用表上作業(yè)法求該運(yùn)輸問題的最優(yōu)調(diào)運(yùn)方案。、銷地B1Bb3_B4. 產(chǎn)量產(chǎn)地、一3_A1_ _412411_ _16A2一21039_ _10A3一85116_ _22銷量 _8_1412_14答案：為了簡(jiǎn)便，表中口中的數(shù)為運(yùn)行方案，（）中的數(shù)為檢驗(yàn)數(shù)。最小兒素法：銷地BiB2B3_b4一 產(chǎn)量產(chǎn)地y1234A14(1)12(2)41011_16_ A22_

6、 _ 10(1)32 _ _9(-1)_ _10 _A38(10)_51411(12)_6_ _ 22 _銷量_8_1412_14-48檢驗(yàn)數(shù)。24 =-1 0，當(dāng)前方案不是最優(yōu)，調(diào)整如下：f-銷地B1B2B3 | B4| 產(chǎn)量-產(chǎn)地-一一_-A1_4(0)12(2)41211141162810(2)3(1)92110-A3_一 8(9) _-5F141 _一 11(12) 一-6_一 22 銷量814121448所有檢驗(yàn)數(shù)非負(fù)，當(dāng)前方案為最優(yōu)方案.有非基變量檢驗(yàn)數(shù)為0,有無窮多最優(yōu)解。(4)用圖解法求下列目標(biāo)規(guī)劃的滿意解： TOC o 1-5 h z HYPERLINK l bookmark

7、43 o Current Document minz = Pd + + P(d + d +) + Pd - 1 12223 32 七 + % 右11(。)X -X + d-d + = 0 (b) HYPERLINK l bookmark46 o Current Document 1211 0(i = 1,2,3)l12 i i圖略，滿意解是線段GD上任意點(diǎn)，其中G點(diǎn)(2,4),D點(diǎn)(10/3,10/3),因?yàn)镚D上任意點(diǎn)對(duì)應(yīng)的 d - = 0 3(5)設(shè)圖中各弧上數(shù)為距離，求該網(wǎng)絡(luò)(看作無向圖)的最小生成樹。13.解：(113.解：(1)破圈法或加邊法，過程略*如上圖，為該網(wǎng)絡(luò)(看作無向圖)的

8、最小生成樹，總的權(quán)重為18、解答題(共50分)（10分）某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，從工藝資料知道：每生產(chǎn)一噸產(chǎn)品甲需用資源A 3個(gè)單位，資源B 5個(gè)單位，每生產(chǎn)一噸產(chǎn)品乙需用資源A 4個(gè)單位，資源B 2個(gè) 單位。若一噸產(chǎn)品的甲和乙的經(jīng)濟(jì)價(jià)值分別為10千元和6千元，每天原料供應(yīng)的能力 分別為10，12單位，企業(yè)應(yīng)該如何安排生產(chǎn)計(jì)劃，使得一天的總利潤(rùn)最大？解：設(shè)每天生產(chǎn)甲、乙各氣,% 噸，則max z -10 x + 6 x 12& + 4 x 10 1 2 s.t 5x + 2x 012圖解法求解：略最優(yōu)解為：X=（2, 1 ），最優(yōu)目標(biāo)值為z=26.答：每天生產(chǎn)甲、乙各2噸和1噸，使得一天的總

9、利潤(rùn)最大下面三題選一:（1）已知線性規(guī)劃問題（P）max z - 2x + 3x + 3x123x + x + x 3 1 2 3s.t x + 4x + 7x 02 j = 132,3 1 j的一個(gè)單純形表如下。C23300CBXBb2X1X2玉A2X110-14/3-1/332012-1/31/3L00-1-5/3-1/3（a）寫出（P）此時(shí)的基本可行解，并判斷該解是否為最優(yōu)解；（b）寫出（P）的對(duì)偶模型及其最優(yōu)解。答案：（1）基變量為X1,X2，故當(dāng)前基本可行解為（1，2, 0，0，0），因?yàn)樗袡z驗(yàn)數(shù) 非正，故為最優(yōu)解。（2）（P）的對(duì)偶模型為min w = 3 y + 9 yL 2y

10、 + 4 y 312七+7七3、y1, y2 0其最優(yōu)解為原問題最優(yōu)單純表中檢驗(yàn)數(shù)的相反數(shù)，即（5/3, 1/3）(2)已知線性規(guī)劃問題:1234x(2)已知線性規(guī)劃問題:1234x+3x+x 81242x+x 612x+x+x 6234x+x+x 0 (j=1,4)max z = 2x + 4x + x + xj解：對(duì)偶模型為234y + y =134又因?yàn)槠?9 - 2 - 2 - 4 = 1 0 ,故 y4= 0從而 y3 = 1, y1 = 2/5, y2 = 4/5，所以對(duì)偶的最優(yōu)解為X*=(2,2,4,0)，根據(jù)對(duì)偶理論求出對(duì)偶問題最優(yōu)解。min w = 8 y + 6 y + 6

11、 y + 9 y1234y + 2 y + y 21243 y + y + y + y 31234y3 + y4 1y + y 114y, y , y , y 01234設(shè)對(duì)偶問題最優(yōu)解為K* = (y, y , y , y )。因?yàn)樵瓎栴}最優(yōu)解為x*=(2,2,4,0)，1234y1 + 2 y2 +y4 = 23 y1 + y + y + y = 3問題的最優(yōu)解為(2/5,4/5,1,0)下面三題選一:(1)用分枝定界法求解整數(shù)規(guī)劃問題:max z = 3 尤 + 2 x122x + 3x 141 2 x + 0.5x 0且x為整數(shù)122解：該問題的松弛問題(L)為max z = 3x +

12、 2 x2x + 3x 141 -2 -x + 0.5x 012用圖解法(略)得松弛問題(L)的最優(yōu)解為(3.25,2.5)，最優(yōu)目標(biāo)值為14.75.對(duì)(L)分別增加條件x2 3,得兩個(gè)子問題(L1)和(L2)，用圖解法(略)得子問題(L1)的最優(yōu)解為(3.5,2)，最優(yōu)目標(biāo)值為14.5,子問題(L2)的最優(yōu)解為(2.5,3)，最優(yōu)目標(biāo)值為 13.5.因?yàn)榻?3.5,2)滿足氣為整數(shù)條件，并且目標(biāo)函數(shù)值是兩個(gè)子問題中最大，故原問題的最優(yōu)解為(3.5,2).18,解:1023159510152415514715201513 M 818,解:1023159510152415514715201513

13、 M 8M 0 0 0 0廣803381302100921012 7 5 M-8 0401270如13079M-3-0T 一-0T-01139501302M-80-7-Z -40-0-1M、此時(shí)其中(3)608110MT40M-9 0003費(fèi)用最小，Z* = 3 + 5 + 5 + 8 = 21丙做第一事，甲做第二事，乙做第二事戌做第四事求解0-1規(guī)劃問題:(2)從甲，乙，丙，丁，戊五人中挑選四人去完成四項(xiàng)工作，已知每人完成各項(xiàng)工作的時(shí)間如 下表所示。規(guī)定每項(xiàng)工作只能由一個(gè)人去單獨(dú)完成，每個(gè)人最多承擔(dān)一項(xiàng)工作，假定甲必須 保證分配到工作，丁因某種原因不同意承擔(dān)第四項(xiàng)工作。在滿足上述條件下，如何

14、分配工作， 使完成四項(xiàng)工作總的花費(fèi)時(shí)間最少。(20分)工作人一四甲1051520乙210515丙3151413丁15276戊94158max z - 3 x - 2 x + 5 xx + 2 x - x 2x1+4 x2+x3 4st x + x 34 x + x 0(0,0,1)5VV V V Vz 5(0,1,0)-2X(0,1,1)3X(1,0,0)3X(1,0,1)8VV V V V Vz 8(1,1,0)1X(1,1,1)6X從而得最優(yōu)解n = (1,0,1)，最優(yōu)值Z* = 8。(10分)(二選一)設(shè)圖中各弧上數(shù)為距離，求七到七的最短距離與最短路徑。(2(2)設(shè)圖中各弧上數(shù)為容量，

15、求七到七的最大流量。標(biāo)號(hào)過程：略；最短路為：V v2v6v9，最短距離為8.5標(biāo)號(hào)過程：略；最大流量為 6，最小割集為：(S,T)=(Vi，v2),(v4,v7)，其中 S=V,v4，T=v2,v3,v5,v6,v7,v8,v9 割量為：C(S,T)=3+3=6.最大流量方案(答案不唯一)：f =3 f =3f =3f =3f =3f =1f =2f =1, 其余為零cy V1JIL I 虹 y J* III P-*，：1Q ,A A ,4。二 Q,4qC, 4/17,4 = 070 匕,QC，(、刀J y。131423394/787989下面二題選一：卜表為一機(jī)械加工工序，試畫出PERT網(wǎng)絡(luò)

16、圖，并計(jì)算時(shí)間參數(shù)和確定關(guān)鍵路線。作業(yè)代碼作業(yè)名稱緊前作業(yè)作業(yè)時(shí)間（天）A項(xiàng)目設(shè)計(jì)4B外購包裝材料A8C清理場(chǎng)地A7D外購零配件A6E機(jī)加工2人員培訓(xùn)A9F木模、鑄件C15G機(jī)加工1D12H機(jī)加工2D、E8I工裝制造G10J裝配、調(diào)試B、 F、 H、 I4關(guān)鍵工序：A,C,F,J關(guān)鍵路線：132333738工程完工期限：38某農(nóng)場(chǎng)要決定一塊地中選擇什么作物，條件如下，如何決策?旱正常多雨0.20.70.1蔬菜100040007000r力、麥200050003000棉花300060002000（1）分別用樂觀法、悲觀法、等可能法與最小后悔值法對(duì)生產(chǎn)方案作出決策。（2）根據(jù)往年天氣資料，旱、正常和

17、多雨三種天氣的概率分別為）.2、0.7和0.1，求利潤(rùn)期 望最大和后悔期望最小的策略。答：利潤(rùn)表如下表所示。旱正常多雨Maxmin等可能法利潤(rùn)期 望值0.20.70.1蔬菜1000400070007000100040003700小麥2000500030005000200033334200棉花3000600020006000200036676800樂觀法（大中取大）：最佳方案為：蔬菜悲觀法（小中取大）：最佳方案為：小麥或棉花等可能法：最佳方案為：蔬菜最大利潤(rùn)期望值法：最佳方案為：棉花后悔值如下表所示。旱正常多雨Max損失期望值0.20.70.1蔬菜20002000020001800小麥10001

18、000400040001300棉花0050005000500最小后悔值法：最佳方案為：蔬菜 最小損失期望值法：最佳方案為：棉花四、建立下面問題的數(shù)學(xué)模型（9分）1.某造船廠根據(jù)合同從當(dāng)年起連續(xù)三年末各提供四條規(guī)格相同的大型客貨輪。已知該廠這三年內(nèi)生產(chǎn)大型客貨輪的能力及每艘客貨輪成本如下表所示:年度正常生產(chǎn)時(shí)間內(nèi)可完 成的客貨輪數(shù)加班生產(chǎn)時(shí)間內(nèi)可完成的客貨輪數(shù)正常生產(chǎn)時(shí)每艘成本（萬元）133500252600323500已知加班生產(chǎn)時(shí)，每艘客貨輪成本比較正常時(shí)高出60萬元；又知造出來的客貨輪若當(dāng)年不交 貨，每艘每年積壓一年造成損失為30萬元。在簽定合同時(shí)，該廠已積壓了兩艘未交貨的客貨 輪，而該廠希望在第三年未完成合同還能儲(chǔ)存一艘備用。問該廠如何安排每年客貨輪的生產(chǎn) 量，在滿足上述各項(xiàng)要求的情況下總的生產(chǎn)費(fèi)用最少？答案：設(shè)第i年正常生產(chǎn)艘，加班生產(chǎn)*艘，交付后儲(chǔ)貯R艘產(chǎn)銷存平衡:x + j + z = z + 4, i = 1,2,3產(chǎn)銷存平衡:i ii-1iZ0 = 2, z3 = 10 x 3,0 j 3加工能力限制：0 x2 5,0 七 20 x 2,0 j 3