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

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

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

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

4、性規(guī)劃模型的特征有：（1）目標(biāo)函數(shù)是決策變量的線性函數(shù)；（2）約束條件是決策變量的線性（不）等式；（3）決策變量連續(xù)變化。2 .利用0-1變量表示下列約束條件（要求說(shuō)明0-1變量的意義）x取值0,2,4,6,8中的一個(gè)答案：設(shè)yj=1為取第j個(gè)數(shù)，否則，yj=0.則x0yi2y24y36y48y5yiy2y3y,y5iyj0or1,j1,2,|,53 .寫出求極大值的運(yùn)輸問(wèn)題的產(chǎn)銷平衡表B1B2B3B4A17891030A21716151420A3534615銷量15101520答案：令新表中單位運(yùn)價(jià)為Cij17Cij,總產(chǎn)量=65>60=總銷量，增加一個(gè)虛擬的銷地，銷量為5.B1B2B

5、3B4B5A110987030A20123020A312141311015銷量151015205（10分=5分+5分）某產(chǎn)品有三個(gè)產(chǎn)地、四個(gè)銷地，各產(chǎn)地的產(chǎn)量、各銷地的銷量以及產(chǎn)地到銷地之間的單位運(yùn)價(jià)見(jiàn)下表，用表上作業(yè)法求該運(yùn)輸問(wèn)題的最優(yōu)調(diào)運(yùn)方案。肖地產(chǎn)地、BiB2B3B4產(chǎn)量A141241116A22103910A38511622銷量8141214答案：為了簡(jiǎn)便，表中口中的數(shù)為運(yùn)行方案，（）中的數(shù)為檢驗(yàn)數(shù)。最小元素法：，理地產(chǎn)地、BiB2B3B4產(chǎn)量Ai4(1)12(2)41011616A228一10(1)32_一9(-1)10A38(10)51411(12)6822銷量814121448檢

6、驗(yàn)數(shù)2410,當(dāng)前方案不是最優(yōu)，調(diào)整如下:Ai4(0)12(2)41211416A22810(2)39210A38(9)51411(12)6822銷量814121448所有檢驗(yàn)數(shù)非負(fù)，當(dāng)前方案為最優(yōu)方案.有非基變量檢驗(yàn)數(shù)為0,有無(wú)窮多最優(yōu)解。(4)用圖解法求下列目標(biāo)規(guī)劃的滿意解：minzP1dl+P2(d2d2)P3d32x1x211(a)x1x2d1d10(b)x12x2d2d210(c)8x110x2d3d356(d)x1，x2，di,di0(i1,2,3)圖略，滿意解是線段GD上任意點(diǎn)，其中G點(diǎn)(2,4),D點(diǎn)(10/3,10/3),因?yàn)镚D上任意點(diǎn)對(duì)應(yīng)的d30(5)設(shè)圖中各弧上數(shù)為距離

7、，求該網(wǎng)絡(luò)(看作無(wú)向圖)的最小生成樹(shù)。13.解：(1)破圈法或加邊法，過(guò)程略如上圖，為該網(wǎng)絡(luò)(看作無(wú)向圖)的最小生成樹(shù)，總的權(quán)重為18二、解答題(共50分)1. (10分)某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，從工藝資料知道：每生產(chǎn)一噸產(chǎn)品甲需用資源A3個(gè)單位，資源B5個(gè)單位，每生產(chǎn)一噸產(chǎn)品乙需用資源A4個(gè)單位，資源B2個(gè)單位。若一噸產(chǎn)品的甲和乙的經(jīng)濟(jì)價(jià)值分別為10千元和6千元，每天原料供應(yīng)的能力分別為10,12單位，企業(yè)應(yīng)該如何安排生產(chǎn)計(jì)劃，使得一天的總利潤(rùn)最大？解：設(shè)每天生產(chǎn)甲、乙各x1,x2噸，則maxz10x16x23x14x210s.t5x12x212x1,x20圖解法求解：略最優(yōu)解為：X=(2

8、,1),最優(yōu)目標(biāo)值為z=26.答：每天生產(chǎn)甲、乙各2噸和1噸，使得一天的總利潤(rùn)最大2.下面三題選一：(1)已知線性規(guī)劃問(wèn)題(P)maxz2x13x23x3x1x2x33s.tx14x27x39xj0,j1,2,3的一個(gè)單純形表如下。Cj23300CBXbbX1X2X3X4X52X1110-14/3-1/33X22012-1/31/3j00-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ì)偶模型為minw3y

9、l9y2V iV22V i4y23%7y23V 1,V205/3,1/3)其最優(yōu)解為原問(wèn)題最優(yōu)單純表中檢驗(yàn)數(shù)的相反數(shù)，即(maxz2x14x2x3x4(2)已知線性規(guī)劃問(wèn)題:x13x22x1x2x2xix2xj0(jx3x3x48669的最優(yōu)解為X*=(2,2,4,0),根據(jù)對(duì)偶理論求出對(duì)偶問(wèn)題最優(yōu)解。minw8yl6y26y39y4解：對(duì)偶模型為Vi2y2y423y1y2y3y43y3y41yiy41y1,y2,y3,y40設(shè)對(duì)偶問(wèn)題最優(yōu)解為Y*(y1,y2,V3,V4)。因?yàn)樵瓎?wèn)題最優(yōu)解為%2y2y423y1y2y3y43V3V41又因?yàn)閤s4922410,故y40,從而y31,y1問(wèn)題的

10、最優(yōu)解為(2/5,4/5,1,0)3.下面三題選一：(1)用分枝定界法求解整數(shù)規(guī)劃問(wèn)題:解：該問(wèn)題的松弛問(wèn)題(L)為用圖解法(略)得松弛問(wèn)題(L)的最優(yōu)解為X(L)分別增加條件x2和x23,1，l|h4)X*=(2,2,4,0),故2/5,y24/5,所以對(duì)偶maxz3x12x22x,3x214x10.5x24.5x1,x20且x2為整數(shù)maxz3x12x22為3x214x10.5x24.5x1,x20(3.25,2.5),最優(yōu)目標(biāo)值為14.75.得兩個(gè)子問(wèn)題(L1)和(L2),用圖解法(略)得子問(wèn)題(L1)的最優(yōu)解為(3.5,2),最優(yōu)目標(biāo)值為14.5,子問(wèn)題(L2)的最優(yōu)解為(2.5,3)

11、,最優(yōu)目標(biāo)值為13.5.因?yàn)榻?3.5,2)滿足X2為整數(shù)條件，并且目標(biāo)函數(shù)值是兩個(gè)子問(wèn)題中最大，故原問(wèn)題的最優(yōu)解為(3.5,2).(2)從甲，乙，丙，丁，戊五人中挑選四人去完成四項(xiàng)工作，已知每人完成各項(xiàng)工作的時(shí)間如下表所示。規(guī)定每項(xiàng)工作只能由一個(gè)人去單獨(dú)完成，每個(gè)人最多承擔(dān)一項(xiàng)工作，假定甲必須1051520M、831012M:5079M-3、210515008070-0T1_0T0-3151413011395011139501527M01302M-801302M-8094158072100071!10-0-M18.解:8M-3、0913608110此時(shí)，費(fèi)用最小，其中，丙做第一事,4(M-9

12、0Z3)15甲做第二事,21乙做第三事,戌做第四事保證分配到工作，丁因某種原因不同意承擔(dān)第四項(xiàng)工作。在滿足上述條件下，如何分配工作,使完成四項(xiàng)工作總的花費(fèi)時(shí)間最少。(20分)人工作一一三四甲1051520乙210515丙3151413丁15276戊94158(3)求解0-1規(guī)劃問(wèn)題:maxz3x12x25x3x12x2x3x14x2x3s.tx1x24x2x36x1,x2,x30或1解：易看出(xi,x2,x3)(0,0,0)滿足約束條件，故為一個(gè)可行解，且相應(yīng)的目標(biāo)函數(shù)值為0。因?yàn)槭乔髽O大值問(wèn)題，應(yīng)增加一個(gè)約束條件(目標(biāo)值下界)：3xi2x25x30,求解過(guò)程可由下表來(lái)表示:(Xi,X2,X

13、3)z值過(guò)濾條件約束條件修正過(guò)濾條件abcdea(0,0,0)0一VVVVz0(0,0,1)5VVVVVz5(0,1,0)-2x(0,1,1)3x(1,0,0)3x(1,0,1)8VV7V7V7V7V7z8(1,1,0)1x(1,1,1)6X從而得最優(yōu)解x(1,0,1)T,最優(yōu)值z(mì)8。Vi到V9的最短距離與最短路徑。(2)設(shè)圖中各弧上數(shù)為容量，求必到丫9的最大流量。4.(10分)(二選一)(1)設(shè)圖中各弧上數(shù)為距離，求(1)標(biāo)號(hào)過(guò)程：略；最短路為：V1一V2V6一V9,最短距離為8.5(2)標(biāo)號(hào)過(guò)程：略；最大流量為6,最小割集為：(S,T)=(V1,V2),(V4,V7),其中S=v1,V4,

14、T=v2,V3,V5,V6,V7,V8,V9割量為：C(S,T)=3+3=6.最大流量方案(答案不唯一"):f3=3,f14=3,f23=3,f39=3,f47=3,f78=1,f79=2,f89=1,其余為零。卜面二題選一：卜表為一機(jī)械加工工序，試畫出PER刖絡(luò)圖，并計(jì)算時(shí)間參數(shù)和確定關(guān)鍵路線。作業(yè)代碼作業(yè)名稱緊前作業(yè)作業(yè)時(shí)間(天)A項(xiàng)目設(shè)計(jì)一4B外購(gòu)包裝材料A8C清理場(chǎng)地A7D外購(gòu)零配件A6E機(jī)加工2人員培訓(xùn)1A9F木模、鑄件C15G機(jī)加工1D12H機(jī)加工2JD、E8I工裝制造G10J裝配、調(diào)試B、F、H、I4關(guān)鍵工序：A,C,F,J關(guān)鍵路線：12378工程完工期限：38某農(nóng)場(chǎng)要

15、決定一塊地中選擇什么作物，條件如下，如何決策?一_利信、旱正常多雨0.20.70.1歌菜100040007000小麥F20001r500030001棉花30006。2000(1)分別用樂(lè)觀法、悲觀法、等可能法與最小后悔值法對(duì)生產(chǎn)方案作出決策。(2)根據(jù)往年天氣資料，旱、正常和多雨三種天氣的概率分別為0.2、0.7和0.1,求利潤(rùn)期望最大和后悔期望最小的策略。答：利潤(rùn)表如下表所示。旱正常多雨Maxmin等可能法利潤(rùn)期望值0.20.70.1蔬菜1000400070007000100040003700小麥2000500030005000200033334200棉花300060002000600020

16、0036676800樂(lè)觀法（大中取大）：最佳方案為：蔬菜悲觀法（小中取大）：最佳方案為：小麥或棉花等可能法：最佳方案為：蔬菜最大利潤(rùn)期望值法：最佳方案為：棉花后悔值如下表所示。旱正常多雨Max損失期望值0.20.70.1蔬菜20002000020001800小麥10001000400040001300棉花0050005000500最小后悔值法：最佳方案為：蔬菜最小損失期望值法：最佳方案為：棉花四、建立下面問(wèn)題的數(shù)學(xué)模型（9分）1,某造船廠根據(jù)合同從當(dāng)年起連續(xù)三年末各提供四條規(guī)格相同的大型客貨輪。已知該廠這答案：設(shè)第i年正常生產(chǎn)Xi艘，加班生產(chǎn)yi艘，交付后儲(chǔ)貯zi艘X廣銷存平衡：ZoVZiZi4,i1,2.32,Z31加工能力限制:0x3,0yi30X25,0V220X32,0V33目標(biāo)函數(shù):w500x1600x2500x3560yl660y2560y330(z0z1z2)已知一個(gè)工廠生產(chǎn)A、B兩類產(chǎn)品，每件產(chǎn)品生產(chǎn)需消耗三種資源，現(xiàn)已知單位產(chǎn)品獲利、單位產(chǎn)品消耗資源和當(dāng)前資源限制如下表：三年內(nèi)生產(chǎn)大型客貨輪的能力及每艘客貨輪成本如下表所示:年度正常生產(chǎn)時(shí)間內(nèi)可完成的客貨輪數(shù)加班生廣時(shí)間內(nèi)引元成的客貨輪數(shù)正常生產(chǎn)時(shí)每艘成本（萬(wàn)元）133500252600323500已知加班生產(chǎn)時(shí)，每艘客貨輪成本比較正常時(shí)高出60萬(wàn)元；又知造出來(lái)的客貨輪若當(dāng)年不交貨，每