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

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

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

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

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

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

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

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

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

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

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

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

13、3)z值過濾條件約束條件修正過濾條件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)值z8。Vi到V9的最短距離與最短路徑。(2)設圖中各弧上數(shù)為容量，求必到丫9的最大流量。4.(10分)(二選一)(1)設圖中各弧上數(shù)為距離，求(1)標號過程：略；最短路為：V1一V2V6一V9,最短距離為8.5(2)標號過程：略；最大流量為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,其余為零。卜面二題選一：卜表為一機械加工工序，試畫出PER刖絡圖，并計算時間參數(shù)和確定關鍵路線。作業(yè)代碼作業(yè)名稱緊前作業(yè)作業(yè)時間(天)A項目設計一4B外購包裝材料A8C清理場地A7D外購零配件A6E機加工2人員培訓1A9F木模、鑄件C15G機加工1D12H機加工2JD、E8I工裝制造G10J裝配、調試B、F、H、I4關鍵工序：A,C,F,J關鍵路線：12378工程完工期限：38某農場要

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

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