2017年河北工業(yè)大學土木工程學院863運籌學（I）［專業(yè)碩士］考研題庫（一）說明：①本資料為VIP包過學員內(nèi)部使用資料。涵蓋了歷年考研?？碱}型和重點題型。一、判斷題TOC\o"1-5"\h\zI■在任一圖G中，當點集、確定后，樹圖是（；中邊數(shù)最少的連通圖。（ >【答案】x【解析】連通且不含圈的無向圖稱為樹。2.指派問題效率矩陣的每個元素乘以同一大于0的常數(shù)k,將不影響最優(yōu)指派方案。（ ）【答案】V【解析】效率矩陣每個元素乘以同一大于0的常數(shù)k,即目標函數(shù)的系數(shù)同時増大k倍，不會影響最優(yōu)基的變化，故不影響最優(yōu)指派方案。.結(jié)點最早時間同最遲時間相等的點連接的線路就是關(guān)鍵路線。（ ）【答案】V［解析】關(guān)縫路線是指總時差為零的工作鏈，而該工作鏈是由一系列最早時間同最遲時間相等的點連接而成的。.若X、X2分別是某一線性規(guī)劃問題的最優(yōu)解,則X頊的也是該線性規(guī)劃問題的最優(yōu)解'其中*入2為正實數(shù)。（ ）【答案】x［解析］入I入不但應(yīng)該是正實數(shù)，還應(yīng)該滿足入L入2=1。.如果線性規(guī)劃問題有最優(yōu)解，則它一定是基可行解。（ ）【答案】V［解析】基解且可行才倒能是最優(yōu)解。二、計算題已知下列資料。表r.fr緊arrir工序時向工序?I?X序工序時間工序緊前匸序工序時間AG,M3Ec51A.L2BH4FA.E5KF.lIcrGB,C2LB.C7DL3H—3MC3

要求:（1）繪制網(wǎng)絡(luò)圖;（2）用圖上計算法計算各項時間參數(shù)（『除外）；（3）確定關(guān)鍵路線。【答案】（I）由題意繪制網(wǎng)絡(luò)圖如圖所示。圖（3）總時差為零的工序為關(guān)鍵工序，所以關(guān)鍵路線為①一③一④-⑤一⑥一⑦一⑩一?，對應(yīng)的工為H—B—G—A—F—K。某廠生產(chǎn)A、B兩種產(chǎn)品，需經(jīng)過金工和裝配兩個車間加工，有關(guān)數(shù)據(jù)如表所示.產(chǎn)品B無論生產(chǎn)批量大小，每件產(chǎn)品生產(chǎn)成本總為400元。產(chǎn)品A的生產(chǎn)成本分段線性第1件至第70件,每件成本為200元；從第71件開始,每件成本為190元。試建立線性整數(shù)規(guī)劃模型’使該廠生產(chǎn)產(chǎn)品的總利潤最大。表r時定額（小時/件）產(chǎn)品廠有效「吋A B金「車間 裝配4 32 5480500售價（元/件）【答案】設(shè)XI，X2為產(chǎn)品A300 520'B的個數(shù)巖則建立線性整數(shù)規(guī)劃模型如下：maxz=$x[70*(300-200)+(300-190)*(丐-70)]+(!-<?)?(300-200吊+(520-400)與4玉+3工2《480SJ2x,+5x2<500SJx,>0,x2>0且均為整數(shù)

8.判斷表1和表2中給出的調(diào)運方案能否作為用表上作業(yè)法求解時的初始解?為什么?表1 表2、、、知他產(chǎn)地、'、、、知他產(chǎn)地、'、、、134，頊10151521525355鑰*515151012345頊!15025。400220030050035030049021030058020100的駁24041055033070【答案】表1中有5個基格，而要作為初始解，應(yīng)有m+n?l=3+4?l=6個基格，所以表給出的調(diào)運方案不能作為表上作業(yè)法的初始解；表2中，有1()個數(shù)基格’而理論上只應(yīng)有m+n?l=9個，多出了—,所以表2給出的調(diào)運方案不能作為表上作業(yè)法的初始解。9.—個小型計算機服務(wù)系統(tǒng)’處理外來任務(wù)’平均每項任務(wù)的處理時間是20分鐘，外來任務(wù)按泊松流到達，平均每小時到達21頁任務(wù)，設(shè)處理任務(wù)的時間服從負指數(shù)分布，先來先服務(wù)。求：(I)系統(tǒng)內(nèi)空閑和系統(tǒng)內(nèi)任務(wù)數(shù)超過3項(>3)的概率。(2)系統(tǒng)內(nèi)彳壬務(wù)的平均數(shù)和任務(wù)在系統(tǒng)內(nèi)的平均逗留時間。(3)若規(guī)定每項任務(wù)到系統(tǒng)，在1小時之內(nèi)處理完畢’貝!］收費50元。在1至2小時內(nèi)處理完畢，收費40元。處理時間超過2小時則收費20元?；卦撓到y(tǒng)平均1天(以8小時計算)可收費多少？212Px=p(y-p)=-x-=-宀2(頃專)4=壽5*)=眾=§.財撈艘過三項的概率為：(2)Ls=—^—=—=2吧=丄=丄=1s”人3-2I3-2(3)任務(wù)在系統(tǒng)內(nèi)逗留時間服從參數(shù)為〃一2=I的負損數(shù)分布,分布函數(shù)為:F(w)=\-e~w:.P(w<l|=F(l)=l-e_,=0.632P{w<2}=F(2)=1-廣=0.865P{wv2}=l-P{wv2}=l-0.865=0.135/.P(1<vp<2)=I-P{w>2)-P{h^<1)=1-0.135-0.632=0.233.?.每天可收斐用為：8x2x(0.632x50+0.135x20+0.233x40)=697.9(元)10.某廠生產(chǎn)三種產(chǎn)品I，II.HIo每種產(chǎn)品要經(jīng)過A,B兩道工序加工。設(shè)該廠有兩種規(guī)格的設(shè)備能完成A工序，它們以A”A2表示:有三種規(guī)格的設(shè)備能完成B工序，它們以B（,B2,B3表示。產(chǎn)品I可在A，B任何一種規(guī)格設(shè)備上加工。產(chǎn)品II可在任何規(guī)格的A設(shè)備上加工，但完成B工序時，只能在Bi設(shè)備上加工;產(chǎn)品III只能在A2與設(shè)備上加工。已知各種設(shè)備的單件工時,原材料費，產(chǎn)品銷售價格，各種設(shè)備有效臺時以及滿負荷操作時設(shè)備的費用如表所示。要求安排最優(yōu)的生產(chǎn)計劃，使該廠利潤最大。表設(shè)備產(chǎn)品設(shè)備有效臺時滿負荷時的設(shè)備費用《元）1IIIDA,5106000300A>7912[(XXX)321B>684000250&4117000783&740CX)200頃料費（元/件〉0.250.350.50單價（兀/件）1.252.002.80【答案】設(shè)旳，X2分別為用A|,A2加町品I的件數(shù)，X3,X4,X5分別用0,B2,B3加工產(chǎn)品I的件數(shù)；X6,幻分別為用A|,A2加工產(chǎn)品II的件數(shù)’則X6+X7為用0加工產(chǎn)品II的件數(shù);X8為用I及％加工產(chǎn)品m的件數(shù)。由題意’可建立數(shù)學規(guī)劃模型：maxz=(L25-0.25)(X|+上)+(2-0.35)(.匕+.七)+(2.8-0.5).上—膘(5*“0?門)一識(7“一-—(6志+8a-6+8a7)一-—(x4+llx8)一-—x7x5TOC\o"1-5"\h\z4000 3 6 7 7000' 8 4000 35x>+ 0007x24 4-12X.C1O0006x3+?(+工。頑0005.t.-4x.3II.r. 000得X；=1200.x：=230,A-；=0,x：=859,x；=571,兄=0,*=500,*=324;得=1147。即用A[加工產(chǎn)品11200件，用A?加工產(chǎn)品I230件，用Bi加工產(chǎn)品10件，用B?加工產(chǎn)品1859件，用B3加工？23品】571件，用Ai加工產(chǎn)品II。件，用A?加工?^品11500件，用B|加工產(chǎn)品11500件，用A2及B?加工產(chǎn)品III324件，可獲得最大利潤1147元。11.某公司有五臺新設(shè)備，將有選擇地分配給三個工廠，所得的收益如表所示11.某公司有五臺新設(shè)備，將有選擇地分配給三個工廠，所得的收益如表所示表表【答案】將問題按工廠的個數(shù)分為3個階段，設(shè)火表示為分配給第k個工廠到第n個工廠的新設(shè)備數(shù)目,冷表示為分配給第k個工F的新設(shè)備數(shù)目，則=邕寸為分配給第k+1個工廠至第n個工廠的設(shè)備數(shù)目，4(叫)表示為Xk個新設(shè)備分配給第k個工廠所得的收益,fk(%)表示為sk個設(shè)備分配給第k個工廠到第n個工廠時所得到的最大收益。因而可寫出逆推關(guān)系式為A(s*)=max[Pt(玉戚h(&叫)],k=3,2,1Z.(s4)=o下面從最后一階段開始向前逆推計算：第三階段：第二階段:

\以七）X；0123410+4—4020+75+07030+10—5+47+01004——5+77+49+01225——5+107+79+4152第一階段:得到最優(yōu)分酉己方案為:分配給工廠I兩臺新設(shè)備;工T3三臺新設(shè)備，可得最大收益為16。mP455初始偵T(vp0oooo8oooo第1次選代P<v()+wu0+10+20+oo0+80+-oo卩怫號[]T(vPrn2CO8第2次迭代P<v,)+wQ1+31+314-001+7〃標號[]T(v,>⑵4co8第3次迭代p(u)+w.,2+22+22+8卩標號[]TCwJC4]48第4次送代PS+w?4+do4+3卩標號[]T(v,>U37第5次送代/>(u)+4+6P妹號】1TtvPm從表可以得出任意一點到另外任一點的最短路。（1）從V|開始到各點的最短路。d（v\,血）=1，最短路為（5,辺）；

d（s,陰）=1,最短路為（m*v3）；d（功，以）=4,最短路有2條、分別為（功，s,%）或（功，防，叫）；d（5泓）=4,最短路為e?Vj?u5）?d（功g）=7,最短路為（叫，％,以泓）.（2） 從V2開始到Vj的最短路。dSs）=3,最短路為S"d（m，山）=3,最短路為（"2，％）；，咨）=5,最短路為（此，明?Vs）id（巧，W）=6,最短路為（巧，叩外）./不能到達V，故對V2而言，叫為不可達點。（3） MV3M發(fā)到各點的最短路。d（S，辺）=2,最短路為3?以）$d（巧，外〉=2.最短路為E」（巧，W）=5,最短路為（勺，明，強）.V3不能到達M和V2,故V|,V2為V3的不可達點。（4）從V4出發(fā)，只有一^路（％V6）,且d（v4,v6）=3。（5）從V5岀發(fā),只有一^路（v5,V6）,且d（V5,v6）=6O（6）從V6出發(fā)，則無路。13.舉例說明，當運輸問題的最優(yōu)解中所有的基變量均大于零時，該運輸問題有無窮多最優(yōu)解;【答案】舉例如下：、^地B.、^地B.B?A,311a2L3764銷量36Bi瓦產(chǎn)最532107l2IZ141035956對非基變量求檢驗數(shù)，如表所示:如表中空格（1,I）的檢驗數(shù)是0,其他檢驗數(shù)都大于0,表明有無窮多最優(yōu)解。2017年河北工業(yè)大學土木工程學院863運籌學（I）［專業(yè)碩士］考研題庫（二）說明：①本資料為VIP包過學員內(nèi)部使用資料。涵蓋了歷年考研?？碱}型和重點題型。一、判斷題?如果線性規(guī)劃問題無最優(yōu)解，則它也一定沒有基可行解。（ ）【答案】x【解析】當問題的解為為無界時’此時該規(guī)劃問題無最優(yōu)解,但存在基可行解。.若需將某工程項目工期縮短到了10天,簡單可行的方法是任意找出該項目網(wǎng)絡(luò)中一條關(guān)鍵路線，采取必要措施將其縮短到10天即可?！敬鸢浮縑［解析】若網(wǎng)絡(luò)計劃圖的計算工期大于上級要求的工期時，必須根據(jù)要求計劃的進度，縮短工程項目的完工工期。主要采取以下措施，增加對關(guān)鍵工作的投入，以便離關(guān)鍵工作的持續(xù)時間，實現(xiàn)工期縮短。①采取技術(shù)措施’提高工效，縮短關(guān)鍵工作的持續(xù)時間，使關(guān)鍵線路的時間縮短；②采取組織措施，充分利用非關(guān)縫工作的總時差，合理調(diào)配人力、物力和資金等資源。.繃4規(guī)劃問題的每一個基解對應(yīng)可行域的一個頂點。（ ）【答案】x【解析】基解不一定是可行解,基可行解對應(yīng)著可行域的頂點。對于一個有n個變量,m個約束方程的標準線性規(guī)劃SLP,其基可行解的數(shù)目恰好是（個。（）【答案】x【解析】其基解的個數(shù)最多是個，且一般情況下，基可行解的數(shù)目小于基解的個數(shù)。目標規(guī)劃問題的日標函數(shù)都是求最大化問題的。（ ）【答案】x【解析】當每一目標值確定后’決策者的要求是盡可能縮小偏離目標值，因此目標規(guī)劃的目標函數(shù)只能是最小化的。二、計算題6.在圖中,(1)用Dijkstra方法求從、倒各點的最短路；(2)指出對v來說.哪些頂點是不可到達的。圖【答案】(1)P(片)=0,(小=+00(丿=2.3,???,8)計算從引到各點的最短路的步驟如下：V1已經(jīng)獲得P標號，(卩|,卩2)，(片，卩5)，(卩1，卩7)€丹，修改\2v5,v7的T標號T(s)=P3)+心2=0+4=4,T()=P(vi)4~wI5=0+1=1T(v7)=P(vl)+wi7=0+3=3因為min{T(v2),T(v5)?T(v7))=1=T(v5),所以有p(v<)=i0v5已經(jīng)獲得P標號，(v5,v6)eA,改寫v6的T標號為丁(卩6)=戶(的)+使6=7，因為rnin{7'(衫)，丁(％)，丁(S)>=3=丁(s)，所以有P(v7)=3。*已經(jīng)P標號，因^min{T(v2),T(v6)}=T(v2)=4,所以有P(*)=4°％己經(jīng)P標號，所以有P(v6)=7o*己經(jīng)P標號，(*,*)仕人，改寫卩8的T標號為「(*)=戶伉)+%T°，故P(V8)=10。于是，有V|到各點V2,V5,V7'V6.V8的最短路為d(切,/)=?(/)=4,d(趴，捲)=P(p5)=l，dWi,e)=F(功)=34(凹，P6)=P(t0=7,d(5,s)=P(0)=l。(2)V|不能到達V3及V4。7-已知圖表示7個城市間擬建一條連接各個城市的通信線路，各邊的權(quán)數(shù)表示兩個城市之間的修建費用，求連接各城市通信線路最小修建費用方案。B52圖CB52圖C【答案】最優(yōu)方案為:

4242可使修建費用為最少。x.試用步長加速法(模矢法)求下述函數(shù)/?京)=藥+2成一x.試用步長加速法(模矢法)求下述函數(shù)/?京)=藥+2成一4勾一2七血的極小點，初

050始點對=(3,1/，步長禹=~00.50并繪圖表示整個迭代過程?！敬鸢浮堪凑疹}目要求，采用步長加速法進行迭代，迭代過程如表所示。

表kB./(Bt)八曷+4“河一AQ111/(Th+3：)/(Tu-Az)B：=Ti2f(B:)](3.1)T-76.75-6.75(3.I)T-7.5—(3.I.5)T-7.5k孔/CT.o+di)叫碼f)=烏/(B*4-1)2(3,2)丁-7-7.75(3.5.2),-6.75-7.75(3.5,1.5),-7.753(4.1.5)T一7.5—6.75一7.75(3.5,1.5)T-7.75—《3.5,2)1-7.754(3.5,2.5)T-7(4.2.5P-6-8(4.2>T5-7.75—8(4.2)r-7.75-7.5(4,2)T-8注：表中的叩‘表示其值不必計算。B6= =(4,2卩，此時應(yīng)在點B6=B5=(4.2)1附近搜索，縮小步長以求得符合精度要求的結(jié)果。所以，最優(yōu)解為(4,2)丁其迭代過程如圖所示。9.企業(yè)A是位于南京路的一家專供某類零部件的加工企業(yè)，生產(chǎn)產(chǎn)品DXF,正常生產(chǎn)條件下可生產(chǎn)12百件/天，每百件定價8萬元。根據(jù)供貨合同，需按9百件/天供貨。存貯費每百件0.16萬元/天,允許缺貨’缺貨費為每件0.65萬元/天,每次生產(chǎn)準備費為80萬元。要求：(1)繪出存儲狀態(tài)圖，并說明存儲過程；(2)求最優(yōu)存儲策略。

【答案】由題意可知，P=12.R=9,Q=0.16.G=0.65,C3=8O,K(Q)二8,訂購費為C‘+K(Q)最優(yōu)存貯策略各參數(shù)為：最優(yōu)存貯周期:「 2x80x0.81=12V0.16x0.65x9經(jīng)濟生產(chǎn)批量:。?=肝=108歹時間";備E最大存貯量:AJ金;J87最大缺貨量：￡=盧當/=22C]+02平均總費用為：b=專=14存貯狀態(tài)圖如圖所示。10.(1)每月需要某種機械零件2000件，每件成本150元，每年的存儲費用為成本的16%,每次訂購費100元’求E.O.Q及最小費用。(2)在題(1)中如允許缺貨，求存儲量s,及最大缺貨量，設(shè)缺貨費為C2=200元。【答案】(1)用"不允許缺貨，生產(chǎn)時間很短”的模型求解。已知C廣100,R=2000x12=24000,C,=150xl6%=24oX100X24000=447（件）24X100X24000=447（件）24最小費用為( (% 聲=24X岑十100X號釋eio733(元)所以，最佳批量為447件，最小費用約為10733元。(2)用“允許缺貨,生產(chǎn)時間很短“的模型求解。己知0=24,@=200,C3=100,R=24000,故2C2CsRs?2C2CsR最大缺貨量為Q—S=2RQGG（G+G）1最大缺貨量為Q—S=2RQGG（G+G）12x24000x24x100V200x（24+200）所以庫存量S為423件，最大缺貨量為50件。II.某公司要將一批貨從二個產(chǎn)地運到四個銷地，有關(guān)數(shù)據(jù)如表所示。表B.&耳H,供應(yīng)量A|7379560A?265II400A36425750需求最320240480380現(xiàn)要求制定調(diào)運計劃，且依次滿足：(1)B3的供應(yīng)量不低于誕量；(2)其余銷地的供應(yīng)量不低于85%;A3給母的供應(yīng)量不低于200;A2盡可能少給所;(5)銷地B2、B.,的供應(yīng)量盡可能保持平衡。(6)使總運費最小。試建立該問題的目標規(guī)劃數(shù)學模型?！敬鸢浮吭O(shè)乂訐為A到耳的運量，數(shù)學模型為ninz=Pxdx+P2(d2+</3+￡)++乙"；4(〃7+』；)+SJ.<Xl3+工23+*33+4 d；=480x11+x2I+x31+J2--J：=274SJ.<X\2+x22+X32+d；-d；=204玉4+如+知+d；-d；=323x33+d；-d；=200知-d；=02xn+2x2I+2x31_丹2一x22一血+d；-d；=0內(nèi)一瓜=°J=l七20= …,8）;B3保證供應(yīng)Bi需求的85%B?需求的85%需求的85%A3對B3A?對BiB2與B3的平衡運費最小12.某公司從兩個不同的倉庫向三個客戶提供某種產(chǎn)品，由于在計劃期內(nèi)供不應(yīng)求，公司決定重點保證某些客戶的需要，同時又使總運輸費用最低’現(xiàn)已知各倉庫的供應(yīng)量（噸），各客戶的需求量（噸）及從各倉庫到每一客戶的單位運費（元濺>相關(guān)娜如表所示。根據(jù)供求關(guān)系和公司經(jīng)營的條件,公司確定了以下目標變量：Pi表示客戶幾的需要；R表示至少滿足各客戶75%的需要；P3表示使總運費最少；P4表示從倉庫I至客戶B|,只能用船運貨，最小運量為1000噸：P5表示從倉庫A2至客戶B],從倉庫戊至客戶殘之間的公路正在大修，運貨量應(yīng)盡量少；P6表示平衡用于B和B?之間的供貨滿意水平。試建立該問題的目標規(guī)劃模型?！敬鸢浮吭O(shè)Xij為倉庫i到用戶j的運輸量（i=I,2；j=l,2,3）;d「，d：為第i個目標約束條件中，未達到規(guī)定目標的負偏差變量和超過目標的正偏差變量。由題意可建立如下的目標規(guī)劃模型：minZ=*邳+與（右+邳+邳）+烏尤+￡打+烏（1.2/￡+端）+叢（弗+端）xn+xn+m+d「=3000x31+x22+如=4000xn+勺1+邳=2000xl2+x22+d\=1500xn+x?=5000%+d；-d；=1000亦11+5+邳一d；=1500s￡<x12+也+応一邳=1125x13+工23+邳一邳=3750知=o工勾-茍=03曲-4如+3叫】-4閂+端-噸=010xn+4x12+12xb+8冷］+10x22+3^23一d占=0%"J=12丿=1,2,3邳，邳N0J=12…,1313.某公司預(yù)計下3個月對某種產(chǎn)品的需要量分別為150件、250件和300件。下3個月各月生產(chǎn)能力和生產(chǎn)費用等有關(guān)數(shù)據(jù)如表所示。產(chǎn)品的存儲費為20元/件。試回答如下問題：表月份生產(chǎn)能力(件)費用(元/件)第1月29050第1月加班10080弟2月24050第3月20060(1)將其看作運輸問題，畫出其網(wǎng)絡(luò)圖；(2)建立使總費用最小的生產(chǎn)與存儲方案的數(shù)學模型；(3)寫出該問題的運輸問題調(diào)運表,并用最小元素法列出問題的初始基可行解?！敬鸢浮?1)看作運輸問題時，其網(wǎng)絡(luò)圖見圖：產(chǎn)地銷地產(chǎn)地銷地SJ3月生產(chǎn)圖(2)根據(jù)(1)中的網(wǎng)絡(luò)圖，令產(chǎn)地i的產(chǎn)量為ah銷地j的銷量為頃產(chǎn)地i到銷地j的運輸量為臨、單位運費為c*由于該問題為產(chǎn)大于銷的運輸問題，于是可建立如下數(shù)學模型：43minx=￡￡c內(nèi)1=1>1￡七Kq(i=l,2,3,4)史易珀(J=123)瑚七20(3)該問題的運輸問題調(diào)運表為由于該問題為產(chǎn)大于銷的運輸問題，所以增加一個虛擬的銷地4,其銷量為130,各產(chǎn)地到寶抓穌返的單位運價為0。得到產(chǎn)銷平衡表為：

用最小元素法列岀問題的初始基可行解為：表X1234產(chǎn)毆11501013029021001003240240470130200銷量1502503001302017年河北工業(yè)大學土木工程學院863運籌學(I)［專業(yè)碩士］考研題庫(三)說明：①本資料為VIP包過學員內(nèi)部使用資料。涵蓋了歷年考研?？碱}型和重點題型。一、 判斷題?己知V為線性規(guī)劃的對偶問題的最優(yōu)解，若yi=o,說明在最優(yōu)生產(chǎn)計劃中第i種資源一定還TOC\o"1-5"\h\z有剩余。( )【答案】X【解析】在生產(chǎn)過程中,如果某種資源乓未得到充分利用時，該種資源的影子價格為零。但是影子價格為零并不單表該種資源一定有剩余。.網(wǎng)絡(luò)圖中任何一個結(jié)點都表示前一工序的結(jié)束和后一工序的開始。( )【答案】x［解析】網(wǎng)絡(luò)圖的起始點只表示一工序的開始，結(jié)束點只表示一工序的結(jié)束。.假如到達排隊系統(tǒng)的顧客為普阿松流，則依次到達的兩名顧客之間的間隔時間服從負指數(shù)分布。( )【答案】V【解析】設(shè)N(t＞為時間［0,t］內(nèi)到達系統(tǒng)的顧客數(shù)，貝!J{N(t),20}為參數(shù)入的普阿松流的充要條件是：相繼到達時間間隔服從相互獨立的參數(shù)為入的負指數(shù)分布。.整數(shù)規(guī)劃問題最優(yōu)解的目標函數(shù)值一定優(yōu)于其相應(yīng)線性規(guī)劃問題最優(yōu)解的目標函數(shù)值。()【答案】x［解析】因為附加了整數(shù)條件，其可行域比其相應(yīng)線性規(guī)劃問題的可行域減小，故整數(shù)規(guī)劃問題最優(yōu)解的目標函數(shù)值一定不優(yōu)于其相應(yīng)線性規(guī)劃問題最優(yōu)解的目標函數(shù)值。.如果圖T是樹，則T中一定存在兩個頂點，它們之間存在兩條不同的鏈。( )【答案】x［解析】連通且不含圈的無向圖稱為樹。因此任意兩點間必定只有一條鏈。二、 計算題.國內(nèi)某電纜公司利用包括5個分銷中心、8個客戶區(qū)域的分銷系統(tǒng)來銷售其產(chǎn)品。配給每個客戶區(qū)域一個專門的資源供應(yīng)商?且其所有電纜產(chǎn)品都來自同一分銷中心。為了能平衡分銷中心的客戶需求和雇員的工作量，公司負責物流的副總裁特別指明一個分銷中心最多負責3個客戶區(qū)。如下表就是從5個分銷中心到8個客戶區(qū)域的供給成本(單位:1000美元、求：(I)使總成本最小的分銷中心一§戶區(qū)域的組合方式；

如果有’哪一》銷中心沒有任務(wù)分派；若進一步規(guī)定每個分銷中心最多只能負責2個區(qū)域，那么新的分配方案又是什么?【答案】(I)由題意知該題為指派問題，添加虛擬的人,【答案】(I)由題意知該題為指派問題，添加虛擬的人,用匈牙利解法，具體過程如下:(2)由上一小題可知,第二(2)由上一小題可知,第二2、5、7沒有修7047225398212713、(5134940868140、75381958903440265619039711521715783782111402932063226796251417602383982363245 V521503174282437454029758625II37—>3429186475140260000000000000000000000000000000000000000,00000000?0000000r001000001000000000010000->00000010010000000000\000k0000010u6、(3)表弋域中客戶區(qū)域1客戶區(qū)域2客戶區(qū)域3客戶區(qū)域4客戶區(qū)域5客戶區(qū)域6客戶區(qū)域7客戶區(qū)域8中心I7047225398212713中心27538195890344026中心315783782111402932中心4602383982363245中心54540297586251137.將下列線性規(guī)劃問題變換成標準型，并列出初始單純形表。(1)min-=一3小+4.弓-2玉+5x44jv,-x2+眼3_龍1=一2.V)+尋+3.q <14sJ.<-—2x1+3.r,一也+2x4>2.v(,x2?20,也無約束(2)maxs=zk!pk，imS.!.<=T(i=1,2,???,〃)S.!.<k=\xik>0(7=12??〃:k=L2.???m)【答案】(1)乩=x/-x4,?.且J”20；在第一個約束條件兩邊同時乘以-1后引入人工變量X5,在第二個約束條件右端加上松弛變量X6；在第三個約束條件右端減去剩余變量X7,同時加入人工變量細將目標函數(shù)最小化變換為最大化，得該線性規(guī)劃的標準型maxz'=3x(-4.1,+2x,-5(.r4'-x4")-Mxs-Mvs一4與+x2-2x3+.v4 n+x5=2x+x2+3x.-x.*+"+x=14sJA一2.%+3x2-Xj+2,v4一2.q‘一七+玉=2xpx2,xv.r4'，七”,與,七,與，必20其中，M為充分大的正數(shù)，對應(yīng)的初始單純形表如表所示。表_42-55-M00-MCBXrbZ|XIXiXixiX5XTXlxi 2—4I-21-110000X6 H113—110100-Mxa2-232-20071-6M+34M—4-3M+23M-5一3M+500一M0(2)在上述約束條件兩邊同時乘以-1,然后分別引入人工變量X|,X2，…,Xn，得該線性規(guī)劃的標準型maxs=—￡￡aikxik-Mx}-Mx2 MxnPk?=i*=i其中’M為充分大的正數(shù)。對應(yīng)的初始單純形表如表所示。表-M???-Ma\\/f>ba\^/pk???5/ph偵/phChxubXlXl丁?工n???X|M???X?|???1—_M110―01100-M工2101000???.??:????一M-Tr100100???116nM0…0a\\/ph+M…a\」p./M???a^\/pk+M???8.某季節(jié)性商品必須在銷售之前進行產(chǎn)品的生產(chǎn)決策。當需求量是D時，生產(chǎn)X件商品的利潤(元)為：|2x DfiX)=[2D-xx>D設(shè)D只有4個可能的值，100、200、300和400件，且它們的概率均為0.25。(I)列出該決策問題的決策表；(2)若要求利潤最大，生產(chǎn)者應(yīng)該如何生產(chǎn)？(3)若生產(chǎn)的產(chǎn)量只有100,250和400件三種可能，請用后悔值法作出決策；(4)在第(3)問的基礎(chǔ)上，若要求潤大于等于500元的概率最大，生產(chǎn)者應(yīng)該如何生產(chǎn)?【答案】(1)表決策收益表收\需'益\求1002003004000.250.250.250.251002002002002002000400400400300-KX)1006006004002000200800(2)當策略為生產(chǎn)100件時,期望收益為200x0.25+200x0.25+200x0.25+200x0.25=2000當策略為生產(chǎn)200件時，期望收益為0x().25+4(X)x0.25+400x0.25+4()0x0.25=300。當策略為生產(chǎn)300件時’期望收益為-100x0.25+100x0.25+6()0x0.25+600x0.25=300當策略為生產(chǎn)400件時，期望收益為-200x0.25+0x0.25+200x0.25+800x0.25=200(3)當生產(chǎn)的產(chǎn)量只有100,250和400件三種可能時，決策收益表如表所示。表決策收益表收\需1002003004000.250.250.250.2510020020020()200250-50150500500400-200020()800韻直表如表林表后悔值表

故在后悔值準則下的決策為生產(chǎn)250件。(4)由(3)中的決策收益表知當策略為生產(chǎn)100件時’利潤大于等于500元的概率為0;當策略為生產(chǎn)250件時，利潤大于等于500元的概率為0.5;當策略為生產(chǎn)400件時，利潤大于等于500元的概率為0.2。所以，此時的決策為生產(chǎn)250件。9.設(shè)有線性規(guī)劃LP：mixz=cixl+c2x2s.t.+al2x2^b}在第一二約束電分別加入松弛變量X"由(》0)，并用單純形法求解，得到最優(yōu)單純形表如表基變量Xl基變量XlXjXi10X201-z(crq)00x3X4常數(shù)項4/5-1/531/51/51-21/5-1/5-17%【答案】(1)宀%%腐)=卩03)%呸4%【答案】(1)宀%%腐)=卩03)%呸4丿>I丿原規(guī)劃為Lp:maxZ=4.r+5.r,(2)LD.minw=4.V］十處C=4(1)求出原規(guī)劃LP。(2)寫出LP的對偶規(guī)劃LD。(3)求LD的最優(yōu)解最優(yōu)目標值。X〔+.弓至4x^x2>0其_力24SJ-yl+4v2>5凹_丹20(3)Lp的最優(yōu)解為(3,1)T,最優(yōu)目標值為4x3+5x1=17由強對偶性minw=max<=174 21凹一力=4Ji=y凹+4力=5y2=|10.試用可行方向法求解minf(X)=2xf+2妨—2刀火—4工【一6再儼i+舟W2s.t.J+5工2<5(xl［答案］原非線性規(guī)劃問題可改寫為：min/(X)=2xi+2藥一2耳Xj—4xi—6x2Xi(.￥)=~<X|+x：)+220s.t.k：(X)=—6+5心)+5N0可,飛2。0取精度氣0=勺=°丄初始可行點泌‘二(0,0)「。則」工1r4xi—2x?—41W(X)= *= *a/ L4x?—2j|—6J"x)=(n)T,女m-ipr因為⑷)=2?g：(X>=5>0,所以J(x(°>)為空集。而IW(X)I；=16+36=52>ex?不是近似極小點。取搜索方向D^=-Vf(X'°?)=(4.6)\貝iJ|r,=X<0,4-AD<0,=(4A.6A)T，將其代枱束條件，并令⑴)=G彳爭”=0.2;令饑(*⑴)=0,彳事2=5/34<0.2。又f(X(l>)=32人2+72A2-4822-162-36A=56A2一522,令堂零12=0,即56X2』一52=0,解得人=崩>蕓因此為=人=5'34,X"=(10/17,15/17)、/(Xa,)=-1860/289=—6.436Vf(X)(-58/17■-62/17)。贏(X"')=9/17>0,g」X⑵)=0

則構(gòu)成下述線性規(guī)劃問題:minv1-58

u為便于用單純形法求解，令yi=4+1，北=』2+1，、3=一），從而得到min(—y3)s.1.58.62 ，、120心'少2。引入剩余變量y，，松弛變量ys，*，y?及人工變量加，得線性規(guī)劃問題:mm(—*十My.)58?/17+62“/17—y,—y+^8=120/17、+5、2+乂+，5=6s.t.yi+>6=2>：+)7=2其最優(yōu)解為:力=2,>2=2449,y=76/49,乂=為=乂=0,以=74/49,少=0?=一”=一76/49,而?|=76/49>&。搜索方向為刀2」L北一1」L—25/49.所以rz,=ru+AO,,>-（10/17,15/17）t+A（1,-25/49）t心卜2（卽）、2借噎）T即俏嗚）-4（即）一6（書一斜令四W，貝以=0.551。（IX于是= .2953.耳一爵X0.2953）'=（0.8835.0.7317）T因為&（X⑵）=0.26〉0,82（X⑵）=0.856a0,所以W為可行點,/（x⑵）=-6.583。11.試用牛頓法求解max了0)=/+，+2,取初始點X'°)=(4,0)「，用最佳步長進行迭代。然后采用固定步長入二1，觀察迭代情況’并加以分析說明?！敬鸢浮苛頕(X)=—=云+￡+2,要求f(X)的極大點即求F(X)的極小點。仿照的J\^)解法，可得「201VF(X(8,O)LfHro,)=,/￡(^0>)_,=Lo2Jx=嵌-心r [彳i/2][o]=[o]即極大點為x?=(o,o)‘‘=由上可知，步長入=1。故采用固定步長入=1與采用最佳步長情形一致。。12.寫出下列線性規(guī)劃問題的對偶問題。（1）minz=2Xj+2x2+4x32玉+3x2+5x3>2s.f.<3玉+x?+7x3<3s.f.<-V|+4.y2+6.q<5（2）maxw=玉+2x2+3x3+4x4+x2-Xy-3x4=56.v,+7x,+3x}-5x4>812x,-9x2一9x3+9x4<20>0,Aj<0,土無約束■ mn（3）minZ=￡￡q內(nèi)7尸1（丿=1.2,??.〃）（j=1?（丿=1.2,??.〃）（j=1?2,???.，〃：丿=1.2,???.〃）maxSJ.4<-%"Z-用2.￡勺丐=4(j=SJ.4<-%"Z-用2./-IXj>0(J=l.2.-,nl;nl^n)x無約束(/="]+頃+2,…?〃)［答案］(1)設(shè)對應(yīng)于各約束條件的對偶變量為刃，y2,y3,則其對偶問題為:max6j=2y,+3y,+5j3?〃)2凹+3巧+又《23凹+、2+4必《25y,+7v2+6y3<4y\no,力，為二o(2)設(shè)對應(yīng)于各約束條件的對偶變量為無，y2,y3,則其對偶問題為：min口=50+8*+20y,-乂+6力+12丹21凹+7力-9%22sj.-乂+3)，2-9丹<3-3^-5刈+9%=4凹無約束，為丁0,為20為:(3)設(shè)對應(yīng)于各約束條件的對偶變量為皿=12???,沖，刈仃=1.2,???,〃)，則其對偶問題為:max/= 丿/=ij=iX+y^j*(i=1,2,???,/n;J=12??,〃)sy,,無約束?=1,2,??m；J=1,2,??m)(4)設(shè)對應(yīng)于各約束條件的對偶變量為\;(i=1,2,???.，”)，則其對偶問題為:所min("=￡b,y,/?I心sj.\Eauyi=ci(/=%+1,外+2,???,〃)M叫20(/=1,2,-??,??])其無約束 。=叫+1,吧+2,???,，〃)

13.用破圈法和避圈法求下列圖中各圖的最小樹。（al）采用避圈法。首先從圖（al）中選取最小邊e13=l,以后每一步從未選出的邊中選出一個邊上權(quán)最小的邊，并使之與前面己選的邊不構(gòu)成圈（若在某一步中，有兩條或兩條以上的最小權(quán)的邊時，貝！J從中任選取T＞直到不能選出為止。于是’以｛陽eI5,e3,e9,e10,%w｝為邊構(gòu)成的圖恰好就是—支撐樹,如圖（a2）所示,其權(quán)為16。（a2）采用破圈法。在圖（汨）中任取一個圈，例如（V”V2,V3）,從中去掉權(quán)最大的邊（此處

去掉邊e2=8）,在余下的圖中，重復(fù)上述步驟，直到此圖不再含圈為止。其具體過程如下:取圈（V[,V2，V3）,去掉最大邊。2=8；取圈（V[,V2，V3,v4）..去掉最大邊ei=7;取圈（V2，V3,V7）,去掉最大邊。8=2；取圈（V2，v4,v6）,去掉最大邊e?=7;⑤取圈（V3,v7?V8⑤取圈（V3,v7?V8）,去掉最大邊en=3;⑥取圈（V|,V4,V5），去掉最大邊E；⑦取圈(V6,V7,V8）,去掉最大邊ei2=5:⑧取圈（⑧取圈（V2，V4,V6，V8，V7,V3>去掉最Xifiei6=4；⑨取圈（⑨取圈（V|,V4,V5,V6）,去掉最大邊e（,=4;⑩取圈V5,V6，V8）,去掉最大邊ei4=6。在圖（al）中通過10次破圈后留下來的圖仍然還是（a2）,這就是一個最小支撐樹。(bl)(bl)（2）給圖（b）中的頂點和邊編號v,和勺，如圖（bl）所示。①采用避圈法。類似于（1）的避圈法’最后’由邊集合｛。3,e2,e5,e”％,e?｝構(gòu)成的子圖（見圖（b2））是f最小支撐樹，其權(quán)為12。②采用破圈法。與（1）中的破圈思路相同，通過破去圖中帰e4,e6,ei。和叫;這五條邊以后余下的邊集｛也，。3,e5,e7,e9,電構(gòu)成的子圖就是原圖的一個最小支撐樹’此最小支撐圖正是先前的圖（b2I（3）給圖（c）中的頂點和邊編號H和印如圖（cl）所示。(cl)（c2）采用避圈法。按照圖中的邊的權(quán)的大小，依次從小到大逐步選取邊,并使之不構(gòu)成圈，直到不能選取時’經(jīng)過九次選取后，得至啲邊集合｛e“e2,e5,e6,e8,e9,e!0,eM,e、｝構(gòu)成的圖即為圖c的fB小支撐樹，如圖（c2）所示，此支撐樹的權(quán)為19。采用破圈法。應(yīng)用破圈原理,經(jīng)過七次破圈’去掉了權(quán)數(shù)較大的七條邊:。3,e4,”，％,ei4?e”和eg。而余下的邊集合B，e2,e5,e6,e7,e8,e,0,e,He^｝構(gòu)成了一個無圈的圖即為圖4（c）的另一個最小支撐樹,如圖（c3）所示。此支撐樹的權(quán)仍然為19,這說明，圖（c）的最小支撐樹不惟一’但其總權(quán)均為19。（d2）（4）給圖（d）中的頂點和邊編號V和勺如圖（dl）所示。采用避圈法。依照圖的邊的權(quán)從小到大依次選取,并與先前選出的邊不構(gòu)成圈的原則，逐次選邊，直到不能再選為止。經(jīng)過六次選邊，得到的邊集合｛5,e2,eI0,e8,e6,e’｝構(gòu)成了如圖（d2）所示的最小支撐樹,此支撐樹的權(quán)為17。采用破圈法。應(yīng)用破圈法的原理，經(jīng)過六次破圈，共破去圖中邊。3,S臨%,E和余下的邊集合｛ei，e2,e10,e8,e6,功構(gòu)成的圖即為原圖的最小支撐樹，（d2）其總權(quán)為17。2017年河北工業(yè)大學土木工程學院863運籌學（I）［專業(yè)碩士］考研題庫（四）說明：①本資料為VIP包過學員內(nèi)部使用資料。涵蓋了歷年考研常考題型和重點題型。一、 判斷題?運輸問題按照最小元素法給出的初始基可行解，從每一空格出發(fā)可以找出且僅能找出惟_的閉合回路。（ ）【答案】V【解析】從每一空格出發(fā)一定存在和可以找到惟一的閉回路。因（m+n-1）個數(shù)字格（基變量）對應(yīng)的系數(shù)向量是一個基。任一空格（非基變量）對應(yīng)的系數(shù)向量是這個基的線性組合。而這些向量構(gòu)成了閉回路。TOC\o"1-5"\h\z.如果線性規(guī)劃問題無最優(yōu)解，貝!1它的對偶問題也一定沒有最優(yōu)解。（ ）【答案】V【解析】它的對偶問題可能無解，也可能有無界解。3.已知神為線性規(guī)劃問題的對偶問題的最優(yōu)解?若y/>0,則說明在最優(yōu)生產(chǎn)計劃中第i種資源己經(jīng)完全耗盡。（ ）【答案】V【解析】對偶問題互補松弛性質(zhì)中才內(nèi)d：W>。時，有￡。內(nèi)=如表明在最優(yōu)生產(chǎn)計劃加 萬1中第j種資源已經(jīng)完全耗盡。4.用動態(tài)規(guī)劃方法求最優(yōu)解時，都是在行進方向規(guī)定后?均要順著這個規(guī)定的行進方向，逐段找出最優(yōu)途徑。（ ）【答案】V［解析】用遞推法求解動態(tài)規(guī)劃問題，首先將過程分成幾個相互聯(lián)系的階段，選取狀態(tài)變量和決策變量并定義最優(yōu)值函數(shù)，然后寫出基本的遞推關(guān)系式?口基本方程。其行進方向的規(guī)定，即選擇用逆推法還是JI廁?去。因為動態(tài)規(guī)劃的狀態(tài)具有無后效性，所以必須按規(guī)定的行進方向逐段找出最優(yōu)途徑。5.如果線性規(guī)劃問題有最優(yōu)解，則它對偶問題也一定有最優(yōu)解。（ ）【答案】V【解析】由對偶定理知’原命題為真’且線性規(guī)劃問題與它的對偶問題的最優(yōu)值相等。二、 計算題

6.對表所示的運輸問題(表內(nèi)的數(shù)字表示單位貨物從供應(yīng)地i運到需求地j的運價，表右面和下面的數(shù)字分別表示供應(yīng)量和需求量X(I)用西北角法計算初始耕岀可行解；(2)從這個基礎(chǔ)可行解出發(fā)，求出這個問題的最優(yōu)解；表jZTrnj91-isjZZ1jZTrnj91-isjZZ1--sJ.工|7T110152031【答案】(1)地1234產(chǎn)段11515302531945350504252515203i84150(2)用位勢法計算初始可行解的檢驗數(shù)為：表地1234U|11011-697150221312169I3-111-58-1071024-114-313-812135V10II158用閉回路法對上述初始解進行改進，得到表yi234產(chǎn)量1151530254045331195042525銷位勢法計算可行解的檢驗數(shù)為:

用閉回路法對上述解進行改進，得到表\鏘地1234產(chǎn)量1151530245453531145042525銷位勢法計算可行解的檢驗數(shù)為:用閉回路法對上述解進行改進，得到產(chǎn)1234產(chǎn)量115153()2454532016145042525銷位勢法計算可行解的檢驗數(shù)為：表產(chǎn)航、＞\1234Ui1101II93150261351210169-333118710-24314213212131V)1010912上述得到的解中所有非基變量的檢驗數(shù)均不為負數(shù)，故得到最優(yōu)解，見上表。7.某建筑公司最近幾年的發(fā)展重點是承接中東等地區(qū)的建筑項目。公司需要一種大型的建筑設(shè)備’該設(shè)備今后4年的購買價格(預(yù)測值)分別為(5.0,5.3,5.7,6.0)(萬元)(產(chǎn)品購買價+運輸?shù)焦さ氐馁M用］L如該設(shè)備連續(xù)使用，其第i年的使用費及維修費分別為(1，1.7,2,5.3.3)(萬元>由于路途遙遠?淘汰后的設(shè)備就在當?shù)卣蹆r處理了,使用滿i年的設(shè)備處理價格為(33.2.5,1.5,0.8)(萬元).公司在制定一個4年的設(shè)備購買計劃，你有什么建議？(限用圖論理論.寫出算法，計算過程，最終結(jié)論,最佳總費用)【答案】可以把這個問題轉(zhuǎn)化為最短路問題，根據(jù)題意繪制如下賦權(quán)有向圖。圖采用Dijksra算法計算圖1中的最短路為：(I)對起點1進行P標號’即P(I)=0；對其余點進行T標號，alHJ)=+<X)(J=2.3，?…5)0檢查點1，進行T標號：r(2)=2.7;T⑶=5.2;7\4)=8.7;T(5)=12.7點2獲得P標號，.且P(2)=2.7檢查點2,修改T標號：r(4)=8.2；r(5)=11.7。點3獲得P標號，旦P(3)=5.2檢查點3,修改T標號：7(5)=11.1,點4獲得P標號，且P(4)=8.2檢查點4,無需修改T標號。(5)點5獲得P標號，)且P(5)=11.1,求解結(jié)束。上圖中的最短路為1—3->5。即第一年初購進一臺設(shè)備,第三年初淘汰掉并購置新設(shè)備，直至第四年末淘汰掉。最佳總費用II-1萬元。8.一個辦事員核對登記的申請書時，必須依次檢查8張表格，核對每份申請書需1min。顧客到達率為每小時6人，服務(wù)時間和到達間隔均為負指數(shù)分布.試求：(I)辦事員空閑的概率；(2)匚七,叱,吧。［答案］因為該辦事員核對登記的申請書時，必須依次檢查8張表格，且核對每張表格花費的服務(wù)時間服從負指數(shù)分布,則總的服務(wù)月眥Ek分布，此排隊系統(tǒng)為M/EV1排隊系統(tǒng)。&=8,〃=60人/h,=6人/h，P=十=￡=僉(I)辦事員空閑的概率為："o=l_p=l_&=O?9

（2）L=p+以-W（2）L=p+以-W2虹l_p）L8+E（*）' -?1017160=0.105. irn=0.00532X8（f）麗。,3+W_（8+l）X（￡）. irn=0.00532X8（f）麗?！?奴l_p）W,=3=Vh=0.0025h叭=牛=快里h=0.0009hA 0.建立數(shù)學模型一家汽車制造商有5家過時的工廠’管理層考慮更新這些工廠以生產(chǎn)一種新型轎車的發(fā)動機組、變速器和一種主要配件A。更新每個工廠的成本和更新后的生產(chǎn)能力如表所示:表工廠成本（萬元）發(fā)動機組（萬個）變速器（萬個）配件A（萬個）1250503070235080 ?40903370408010044009060905240403050工廠可用于更新的資金為1300萬元,工廠3和工廠4位于同一地區(qū)，最多只能更新一個工廠,此夕卜工廠I與工廠5具有相關(guān)性，工廠5所需要的某些零件必須由工廠1生產(chǎn)?，F(xiàn)計劃需要180萬個發(fā)動機、150萬個變速器及200萬個配件A,管理層應(yīng)決定更新哪些工F以達到計劃生產(chǎn)需要，并使總成本最小。試建立該問題的數(shù)學模型。［答案］設(shè)Xi=l表示更新工廠i,Xj=0表示不更新工廠i。根據(jù)題意，可建立如下數(shù)學模型:minz=250x,+350x2+370x3+400x4+240x5250x,+350旦+370賜+400心+240賜<1300x3+x4<1X\—SJ.<50可+80x2+40x3+90x4+40a5>180SJ.<30、+40x2+80%+60x4+30x5>15070%!+90x2+100x3+90x4+50x5>200x.=0,1;/=1,2,3,4.5.解下列0-1規(guī)劃問題。（I）minz=4.V,+3x,+2x32x,-5x2+3x3<4.VJ.4.r,+x2+3a:,>3.VJ.x2+Xj>1X|.x2.x3=0或1(2)minc=2.r,+5x2+3.%+4x4-4x)+x2+x3+x4>0-2%+4a\+2xy+4.r424A,+x2-Xj+x421xpx2,x3,x4=0或1【答案】(1)通過觀察可知(o,o,1)「為可行解’相應(yīng)的z=2,故增加約束條件4a;+3x2+2x,<2◎進行枚舉及選擇，如表所示。表點、條 作H標值rOCD(0.0.1)v/*?5/2(0.1.U)X(0.1.1)X(1.0.0)X<1.0.0X<1.1.0)Xci.1.1)X(0.0,0)>/X由表可判定，最優(yōu)解為x'=(0,0,1)。3=2(2)通過觀察可知(0,0,0,1)丁為可行解，相應(yīng)的z=4,故增加約束條件,2玉+5x2+3.q+4.v4<4 ◎進行枚舉及選擇，如表所示?！鯟.ri,力i?瑜}： j巻、&二件<o?Q,a?xi:x.'x/'..4：T^v-■XCOHE..X-一:X：(C.1.4.釦!??-?.,tou4.*i.X...一?—廠 一-~?幻^<?,€?-；..>''ci.i,>.o>',,}"一"I由表可判定最優(yōu)解為X?=(0,0.0,1)「?f=4.用圖解法找出以下目標規(guī)劃問題的滿意解。⑴minz=x,-10x,+<-d；=503多+5心+d；一d；=20'〔8叫+6.弓+/-d；=100.rt.x2,d(?d；^O.i=1.2.3(2)minm=a(d；+d：)+p.d+p3d:+p4(￡+1.5/)-v,+x2+d「—d：=40為+JC,+d；-d；=100aJ.j：, +d；_d；=30x2-J/=15xl,x2,dl.d,'>()./=1.2.3,4(3)minz=A(4+d；p2d2+p遙'j,+x2+或_d；=103玉+4x2+d；_d；=50'.8叫+10旦+打_"；=300§,.弓0 20J=1,2.3【答案】(1)令各偏差變量為0,作岀所有的約束直線，并標示出各偏差量增加對約束直線的影響，如圖所示。圖從圖中可以看到，在考慮具有“的目標實現(xiàn)后，Xi,X2的取值在直線土-l().q=5()及電20上;考慮P2的目標要求實現(xiàn)時，因為+的權(quán)系數(shù)大于過的權(quán)系數(shù)，故考慮mindd2+,所以點A為滿意解，其坐標為(50,0),即滿意解是(50,0)\(2)令各偏差變量為0,作岀所有的約束直線，并標示出各偏差量增加對約束直線的影響，如圖所示。圖從圖中可以看到’在考慮具有pi的目標實現(xiàn)后,"X2的取值范圍為OADFO;考慮P2的目標要求實現(xiàn)后’xi，X?的取值范圍為OABEFO;考慮P3的目標要求實現(xiàn)后，陽，X2的取值范圍為BE;考慮囚的目標要求實現(xiàn)時，因為山一不的權(quán)系數(shù)大于d3一的權(quán)系數(shù)，故考慮mind/,所以點E為滿意解’其坐標為(25,15),即滿意解是(25,15)\(3)令各偏差變量為0,作岀所有的約束直線，并標示岀各偏差量增加對約束直線的影響，如圖所示。圖從圖中可以看到，在考慮具有Pl的目標實現(xiàn)后，"X2的取值范圍為直線AB；考慮P2的目標要求實現(xiàn)時，要實現(xiàn)mindn從圖中可以看出，只有B點可使d?最小，所以B點為滿足目標規(guī)劃問題的滿意解，其坐標為(10,0)，即滿意解是(10,0)\

12.某省農(nóng)業(yè)主管部門為了滿足本省對某種農(nóng)副產(chǎn)品的需求，決定建立生產(chǎn)基地，初步有四個地點A】、A,A3、A,可供選擇，他們的產(chǎn)量分別是"恥a*a4.它們的建設(shè)費用分別為dC2、C3、％有五個地點Bi、B2%BkB4%B5需要這種農(nóng)副產(chǎn)品，它們的需求量分別為也、b2.b"%、b5.從產(chǎn)地八需求地馬的單位運費為Cij。(1)試決定選擇建場的基地與各生產(chǎn)基地到各需求地的運量，使得既滿足各地的需求又使得建設(shè)和運輸?shù)目傎M用最小，這里假定如>i>,??I >1(2)若在(1)的基礎(chǔ)上要求A和A?不能同時入選為生產(chǎn)基地，1、侃、Z、人中至少有兩個入選，且若么I被選中則A4也一定要入選，則相應(yīng)的數(shù)學模型又是什么？【答案】(1)設(shè)句=<【答案】(1)設(shè)句=<1 選擇第代個地點建生產(chǎn)基地yij為第人個基地運送到馬個地點的運量4二號minz=Yx'ci+￡耳匂?為°l<-<-灰.>-fs;1/I5Erl4z:￡;E:Er=l4z-?-l°l<-<-灰.>-fs;1/I5Erl4z:￡;E:Er=l4z-?-l>-x-1如~>-2yr如>-y/4O>-為(2)設(shè)耳=]何不選擇第A.個地點建生產(chǎn)基地

選擇第(2)設(shè)耳=]4 1=4^3minz二〉＞￡"EWiej=i0<-yu5Z/=I2<-0<-yu5Z/=I2<-奶<-<->->-改^/J/1X2hs￡-:z-iu4l.:￡z-iz〔>-43>-X-4>-15x（+x2<1.vl+x2+x3+x4>2土二0或]為"13.某廠每年需要某種元件5000個,每次訂購費C3=50元,保管費每件每年0=1元,不允許缺貨’元件單價k隨采購數(shù)量的不同而變化’問公司每次應(yīng)該訂購多少？總的采購成本是多少？[2.0元，QV1500"）=7一]1.9兀，2>1500【答案】利用E.O.Q公式計算分別計算每次訂購707個和1500個元件，平均單位元件所需費用：C（707）=lx1x^51+—+2.0^2.1414（元/個）' 72 5000707C（1500）=-xlx—+—+1.9^2.0833（元/個）2 50001500因為C（1500）<C（707），所以，最佳訂購量為1500。一年內(nèi)總的采購成本為1500x2.1414=3212.1元。2017年河北工業(yè)大學土木工程學院863運籌學(I)［專業(yè)碩士］考研題庫(五)說明：①本資料為VIP包過學員內(nèi)部使用資料。涵蓋了歷年考研?？碱}型和重點題型。一、 判斷題?運輸問題是一種特殊的線性規(guī)劃模型，因而其求解結(jié)果也可能出現(xiàn)四種情況之_：有惟一Bffi解，有無窮多最優(yōu)解?無界解，無可行解。( )【答案】X【解析】運輸問題是一種特殊的線性規(guī)劃模型’它總存在可行解,或是存在惟一最優(yōu)解，或是有無窮ft｛尤解。.利用破圈法求賦權(quán)圖的最小支撐樹時，每次都是任取一個圈并去掉其中權(quán)最小的邊，直到該TOC\o"1-5"\h\z賦權(quán)圖不再含圈時，便得到最小支撐樹。( )【答案】x［解析］利用破圈法求最小支撐樹時，每次任取一個圈，去掉圈中權(quán)最大的邊。.對自由變量Xk，通常令！=xA其中xk>0.xk>0在用單純型法求得的最優(yōu)解中不可能同時出現(xiàn)x>0.x；>0o( )【答案】V【解析】因為払=?.-??,所以知虹'不能同時為基變量，則至少有一個為0。故最優(yōu)解中不可能同時出現(xiàn)%>0，x；>0。.任一圖G=(V,E)都存在支撐子圖和支撐樹。( )【答案】x【解析】當圖中存在一個頂點，其次為。時’則該圖不存在湖樹。若線性規(guī)劃問題的可行解為最優(yōu)解’則該可行解必定是基可行解。( )【答案】x［解析］基解且可行才倒能璧優(yōu)解。二、 計算題某晝夜服務(wù)的公交線路每天各時間區(qū)段內(nèi)所需司機和乘務(wù)人員數(shù)如表所示。設(shè)司機和乘務(wù)人員分別在各時間區(qū)段一開始時上班’并連續(xù)工作8h,問該公交線路至少需配備多少名司機和乘務(wù)人員。列出這個問題的線性規(guī)劃模型。聲修韻囲顆浪丄用5￥《刼爭困冷坦*t/OI=（切0=｛（。）。，（￡）9化）0，（【）"u叫實留Mt(.2)3(3)3Mt(.2)3(3)3-<1)3-（b'￡'乙（b'￡'乙’l=!）’V孝草垓冴:刼噩明區(qū)m'卻弟逐翹實d，卻車喜臨孩混區(qū)1印【孝另】（空旦）砲'峯（空旦）砲'峯。生詳4,現(xiàn)累翊王囹。峑世喜職象混毋推蠶目姓三善9殖冴G63罠’亦手&一碑柬。-L0V".???"x()￡5+*0乙W&+*OS<^+頃rs09衣+*0Z.^:r+'r09<政+丫9r+?x+*x+zx+he=2uiiu:實瓶誕涼不鬟回m'瀚y関曽巖mm/怛囲sn刼ifMBS!齢y區(qū)（9，…z，【=!）成溟【孝易】0￡00:9—00'290ZOO*2—OO'ZZc^0G(XPZ”-00*81I-09OO*R1--00*H￡0ZOO*VI—OO'OlZ0900101--00,9IY/XfY驊的nvXi iff

8.給出如下線性規(guī)劃問題的最優(yōu)單純型表如表所示，其中$、S2分別為兩個約束條件的松弛變量maxZ=6xi+2x2+12xj4-r, +3x3<242%|+6x2+3x3<30[ME%2°表cl6 212oOc?Xa—bX,X?x?S,s.12Xj84/31/3I1/3o0S,6-250-11-96-10-2o-4o要求：(1)求出使最優(yōu)基不變的也的變化范圍;(2)求出使最優(yōu)解不變的C2的變化范圍；(3)在原線性規(guī)劃的約束條件上，增加約束條件:xi+2xi+2X3^12,其最優(yōu)解是否變化?如變化，試求岀最優(yōu)解?！敬鸢浮?1)假設(shè)加變化后的最優(yōu)解為Xb,只要XrNO,因最終表中檢驗數(shù)不變’故最優(yōu)基不變，但最優(yōu)解的值發(fā)生了變化。設(shè)b2變化了入，貝！| =所以當b>o時問題最優(yōu)基不變’解得入20故b2N30(2)由題意知C2-420得C2*(3)約束條件可變?yōu)閤1+2x2+2x3+S3=I2列出單純形表cBXb-b621200012x384/31/311/30120s26-250-110012122001-10-20-40-1012X.84/31/311/30120S26-250-1100-4-5/34/30-21301-10-20-40-1()12Xj24/507/51-1/504/50S36/5017/50-1/51-6/56XI12/51-4/502/50-3/50-10000-48/5最優(yōu)解(12/5,0,24/5)

9.設(shè)有三個電視機廠生產(chǎn)同一種彩色電視機，日生產(chǎn)能力分別是50,60.50(臺)，供應(yīng)三個門市部，日銷售量分別是60,40.60(臺)?從各分廠運往個門市部的單位運費如表所示，試安排一個運費最低的運輸計劃。若工廠1到門市部I的運價由9減為6,試尋求最優(yōu)運輸計劃。表門市部1門市部2門市部3產(chǎn)量工廠1912950工廠273760工廠365950需求童604060【答案】(I)此問題是運輸平衡問題。第一步，用伏格爾法尋找得到初始基可行答:表門市1門市2門市3產(chǎn)量工廠15050工廠210401060工廠35050需求量604060160第二步，用位勢法計算各空格處的檢驗數(shù)為:從所有非基變量的檢驗數(shù)可以看出都是非負數(shù)，其中存在f0的檢驗數(shù)，說明該題有多重最優(yōu)解。(2)若工廠1到門市部1的運價由9減到6時，代入計算得第一步，用伏格爾法尋找得到初始基可行表門市1門市2門市3產(chǎn)量工廠15050工廠2402060工廠3104050需求敏60406()16()第二步，用位勢法計算各空格處的檢驗數(shù)為:

從所有非基變量的檢驗數(shù)可以看出都是非負數(shù)，其中存在兩個0的檢驗數(shù)，說明該題有多重最優(yōu)解。10.有一運輸問題’它有3個重載點和2個車場’其運輸表如表所示。表中小方框內(nèi)的數(shù)字為兩點間的車輛空駛距離?L2和3三項運輸業(yè)務(wù)的重載里程（己將裝卸車時間折算在內(nèi)）分別為7,8和9,其他有關(guān)情況如表中所示。此外，要求車輛的每條行車路線總長度（包括重駛、空駛及裝卸車所用時間的折算長度）L在45~60之間。試用本章給出的車輛優(yōu)化調(diào)度啟發(fā)式算法，求出其滿意的可接受可行解，并據(jù)此?出行車路線。發(fā)空堂、、敝裁點車場發(fā)車數(shù)12345重點111F—K109■"EItTc63FLi11nsH7車場4FH|M<45T3~E<6收1E敦106<8W7【答案】（1）首先只考慮重載點的情況’利用伏格爾法進行求解，并且用位勢法進行檢驗,得到只考慮重載點的最優(yōu)解為器=10..*=6..輩=6忑）=1逑=*；」灣=專二階=0(2)解的擴展支艾一4。"=4.瓦■=務(wù)一=6—0=6b\=b\ ;80?8.65=b\— =7—0=7=min(c,h-0}?min，,丨占；>0}—=rnin(6?14)+min(8.10}—4=6+8?4=10.6=41/=4dji=min'、<h.-0?nun,b\>0}—c:l=min(6.8}+niin{6t10}—80itrnm(Ci,I>0)r0itrnm(Ci,I>0)ry-~min{4*2}Imini14?2>—44C?<1=2+2-4 ... _8”?mm<c.b.>0*jnm(ch|6；>0}=min(6?8}+min(14f2)—€按照^由小到大順序?qū)M行調(diào)整Ijx'<；—min<工；？，屋,及}=6—min(6?6,7}=0?/："+min(jr；；',S-，及}=0+min(6,6,7}=6■ x,-'+nun(zt；,$，片;)=0+min(6,6,7}=66-=0；—￡了"=&—x5s*=7—6=1MH=1,；min()0；)=1—min(1,4.1}=0?r； 瓦0；}=O+min(l?4,l}=l■x.-C：+min〈a；.B；}=6+jnin(l,4,l)=7h=b,—￡]：；'=板一勇;’=4—1=3rZi=工；：—miNz；；',萬：)=6—min{6,3,8}=3"=*；十0)=l+min(6,3,8}=4z.=無； )=0+min{6?3.8}=3&=M—支h：：‘=如一乂；>=4—4=0方；=0；_X-*D；—￡?=?8—3—5> .7J—mini.*'.Z?<.64}=10—mini10.0,5}=10:.r,-i：?4niinlx；；1,b,，方：>=04-min(10,0,5}=0?1rii*imini*'?R0：)i()+min(10,0,5)=0(3)解的收縮因為S史式」工:？+ =4+6=10<4+6=10l|Atj5方■"xf"+■ ==3+7=]。<4