運籌學2020最新試卷帶答案

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

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

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

4、2）約束條件是決策變量的線性（不）等式；（3）決策變量連續(xù)變化。利用0-1變量表示下列約束條件（要求說明0-1變量的意義）:x取值0，2，4，6，8中的一個答案：設y.= 1為取第j個數(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.寫出求極大值的運輸問題的產銷平衡表B1 .B2B3B4產量A17891030A21716151420A3534615銷量15101520答案：令新表中單位運價為Cj = 17 -匕，總產量=6560=總銷量，增加一個虛擬

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

6、 _ 10(1)32 _ _9(-1)_ _10 _A38(10)_51411(12)_6_ _ 22 _銷量_8_1412_14-48檢驗數(shù)。24 =-1 0，當前方案不是最優(yōu)，調整如下：f-銷地B1B2B3 | B4| 產量-產地-一一_-A1_4(0)12(2)41211141162810(2)3(1)92110-A3_一 8(9) _-5F141 _一 11(12) 一-6_一 22 銷量814121448所有檢驗數(shù)非負，當前方案為最優(yōu)方案.有非基變量檢驗數(shù)為0,有無窮多最優(yōu)解。(4)用圖解法求下列目標規(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上任意點，其中G點(2,4),D點(10/3,10/3),因為GD上任意點對應的 d - = 0 3(5)設圖中各弧上數(shù)為距離，求該網(wǎng)絡(看作無向圖)的最小生成樹。13.解：(113.解：(1)破圈法或加邊法，過程略*如上圖，為該網(wǎng)絡(看作無向圖)的

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

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

10、 + 4 y 312七+7七3、y1, y2 0其最優(yōu)解為原問題最優(yōu)單純表中檢驗數(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解：對偶模型為234y + y =134又因為七=9 - 2 - 2 - 4 = 1 0 ,故 y4= 0從而 y3 = 1, y1 = 2/5, y2 = 4/5，所以對偶的最優(yōu)解為X*=(2,2,4,0)，根據(jù)對偶理論求出對偶問題最優(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設對偶問題最優(yōu)解為K* = (y, y , y , y )。因為原問題最優(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)目標值為14.75.對(L)分別增加條件x2 3,得兩個子問題(L1)和(L2)，用圖解法(略)得子問題(L1)的最優(yōu)解為(3.5,2)，最優(yōu)目標值為14.5,子問題(L2)的最優(yōu)解為(2.5,3)，最優(yōu)目標值為 13.5.因為解(3.5,2)滿足氣為整數(shù)條件，并且目標函數(shù)值是兩個子問題中最大，故原問題的最優(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、此時其中(3)608110MT40M-9 0003費用最小，Z* = 3 + 5 + 5 + 8 = 21丙做第一事，甲做第二事，乙做第二事戌做第四事求解0-1規(guī)劃問題:(2)從甲，乙，丙，丁，戊五人中挑選四人去完成四項工作，已知每人完成各項工作的時間如 下表所示。規(guī)定每項工作只能由一個人去單獨完成，每個人最多承擔一項工作，假定甲必須 保證分配到工作，丁因某種原因不同意承擔第四項工作。在滿足上述條件下，如何

14、分配工作， 使完成四項工作總的花費時間最少。(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ù)為距離，求七到七的最短距離與最短路徑。(2(2)設圖中各弧上數(shù)為容量，

15、求七到七的最大流量。標號過程：略；最短路為：V v2v6v9，最短距離為8.5標號過程：略；最大流量為 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下面二題選一：卜表為一機械加工工序，試畫出PERT網(wǎng)絡

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

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

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