12-13運(yùn)籌學(xué)32答案

1、上海海洋大學(xué)試卷學(xué)年學(xué)期2012_ 20 13學(xué)年第1學(xué)期考核方式閉卷課程名稱運(yùn)籌學(xué)A/B卷(B)卷課程號(hào)1107401學(xué)分2學(xué)時(shí)32題號(hào)-一一二三四五六七八九十總分分?jǐn)?shù)閱卷人誠(chéng)信考試承諾書本人鄭重承諾：我已閱讀且透徹理解了“上海海洋大學(xué)學(xué)生考場(chǎng)規(guī)則”和“上海海洋大學(xué)學(xué)生違反校紀(jì)校規(guī)處理規(guī)定”，承諾在考試中自覺遵守，如有違反，按有關(guān)條款接受處理。承諾人簽I期一、（10分）寫岀下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題：IMin Z = -5%! - 6X2 -7X3考生姓名：學(xué)號(hào)：專業(yè)班名：Xy + 5 尤 2 3 退一15-5Xj -6X2+10X3 < 20s.*1 *2 *3t.<= 5X1

2、 <0,X2>0,X3不受限制Maxw = 15y x +20y2 -5y3-y-5y 2 + y3 <-5解 5ji 6y2-y3 <-6-3）1 + 10,2-,3 = -7M >0,y2<0,y3不受限制、（15分）、已知線性規(guī)劃問(wèn)題：Max Z =耳 + 2X2 + 3X3 + 4x4尤+ 2X2 + 2X3 + 3X4 < 202x +X2 + 3x3 + 2x4 < 20x. > 0 , i 其對(duì)偶問(wèn)題的最優(yōu)解為 YM. 2, 丫 2*二0.2，試用對(duì)偶的互補(bǔ)松弛性求解原問(wèn)題的最優(yōu) 解。Max w = 20A + 20y2Ai+

3、2y 2 >1解：2 + % Z 2 2*+3s?t? <為 2 3 3A+2A >47i 2 0,光 2 0%+2 力- *舄 =1 2 乂 + y2 -y& = 2 2 乂+3 兜一 乂，=3變?yōu)闃?biāo)準(zhǔn)型為3 乂+2%一打=4 丁 1，力，七，乂 2，劣，尺，NO因?yàn)樽顑?yōu)解為 丫1*=1.2,=。丫 2*=0. 2,所以 ysi = 0.4, 乂，= 0.6,舄=°，兒根據(jù)對(duì)偶的互補(bǔ)松弛性，.%七+工 2義，+ 土以3 +4兒=0 ,所以X=£ =02x,+3x4=20 %C 所以 3X3+ 2X4 = 2CC，解得土 = 了 4=4三、(15分

4、)給定線性規(guī)劃問(wèn)題min z = _ 邑 + 2X2 +X3+ X2 + X3 < 6s.t.< 2x1 -X2 <4xy>0( j = 1,2,3)它的最優(yōu)表如下：XIX2X3X4X5bX2111106X53011110考慮下面兩個(gè)問(wèn)題：（1）把q=-1改為4,求原問(wèn)題的最優(yōu)解C2）討論c?在什么范圍內(nèi)變化時(shí)原來(lái)的最優(yōu)解也是原問(wèn)題的最優(yōu)解。解：（1）在最優(yōu)單純形表中，由于也是非基變量，因此，改變叫對(duì)應(yīng)的判別數(shù)G,在現(xiàn)行基下，也的判別數(shù)為九-zc = 3 - （-1-4） = -2 < 0 ,在此基礎(chǔ)上繼續(xù)迭代XIX2X3X4X5bX21111 06X53011

5、110-2012 021XX4X5bXl2X3X2012/32/31-1/38/3X5101/31/31/30/'13A005/38/32/36513最優(yōu)解為（!,x2,x3）= （ a， §o）,目標(biāo)函數(shù)的最優(yōu)值為C2）由于想是基變量，因此，改變W對(duì)應(yīng)的判別數(shù) C2,因此改變C2將影響各個(gè)判別數(shù)，設(shè) C2改變?yōu)镃;于是有:'3 + （ c； -2）= I + c ；I + （ c； -2）*l = -1 + c ；'2 + （ c； -2）*l = c ；0 + （ c； -2）*0 = 0令所有判別數(shù)大于等于0解得c；>1,因此當(dāng)c; 21時(shí)原來(lái)的最

6、優(yōu)解也是新問(wèn)題的最優(yōu)解。四、(20分)已知運(yùn)輸表如下:銷地產(chǎn)地BiB3B4供應(yīng)量4 1241132A22103920A38511644需求量1628282496(1) 用最小元素法確定初始調(diào)運(yùn)方案；(2) 基于(1)的初始解用位勢(shì)法確定最優(yōu)運(yùn)輸方案及最低運(yùn)費(fèi)用最小元素法求一個(gè)運(yùn)輸方案銷地產(chǎn)地BiB2B3B4供應(yīng)量Ai24832A16420A3281644需求量16286282496(2)運(yùn)用位勢(shì)法求的 = 0 , % = -1 , "3 = 5,3 = 3 , V2 = 10 , v3所以 4=1,7A2=2 ,久 2 = 1 ,冬 4 = 1 , 41=13, %2 = 運(yùn)用閉回路

7、法進(jìn)行調(diào)整得新的分配為銷地產(chǎn)地BiB2B3B4供應(yīng)量Ai28432A16420A3281644需求量16286282496運(yùn)用位勢(shì)法求的"=0 , W2 = 2 , U3 = 5 , % = 4 , V2 = 10 , V3 = 4 , V4 = 11 所以九產(chǎn)。，&2=2, a22 = 2 , a23 = 1,=9,在=12因此達(dá)到最優(yōu)解，其總運(yùn)費(fèi)最少為28x4 + 11x4 +4x9 + 16x2 +28x5+ 16x6 = 460五、（15分）已知某實(shí)際問(wèn)題的線性規(guī)劃模型為max z = lOChq + 50x 2'2%! + 2X2 < 36（資源 1）

8、< 2%! + X2 < 38 （資源 2） x,X9 > 0假定重新確定這個(gè)問(wèn)題的目標(biāo)為：R: Z的值應(yīng)不低于1800Pr-資源1必須全部利用1）將此問(wèn)題轉(zhuǎn)換為目標(biāo)規(guī)劃問(wèn)題，列岀數(shù)學(xué)模型；2）圖解法找岀此目標(biāo)規(guī)劃問(wèn)題的滿意解?！窘狻?）數(shù)學(xué)模型為min z = Pd" + p2 （d2+ d ；）100%, + 50X2 + d;-=18002%| + 2X9 + d d := 36< -1 -2% + X2 < 38x, X2, d； , d； > 0,i = 1,2,2）滿意解 X= （18, 0）（15分）需要指派5人去做5項(xiàng)工作，每人做各

9、項(xiàng)工作所消耗的時(shí)間如下表工、員/Z .1ABCDE、作人4871512乙79171410丙691287T6714610戊6912106問(wèn)指派哪個(gè)人去完成哪項(xiàng)工作，可使總的消耗時(shí)間最?。吭囉眯傺览椒ń鉀Q之。 87151 4318一 30187 917 14 2(AII0 21730 1 7 6) 3006 9128703621023116 71461>01804006056 9121000364001330T解：對(duì)其效率矩陣進(jìn)行化簡(jiǎn)得TD,戊 TE。因此達(dá)到最優(yōu)解，所有最有方案為甲TC,乙tB,（10分）求解下列 0-1規(guī)劃問(wèn)題丙TA,max z = 3 工 1 + 2x2 一 5x3一 2x4 + 3x 5 尤+ X