運(yùn)籌學(xué) 試卷及答案 卷6

課程名稱:課程名稱:運(yùn)籌學(xué)題號(hào)一二三四五六七八九十總分得分評(píng)分人一、（10分）設(shè)有如下線性規(guī)劃問題：（1）寫出其對(duì)偶問題；（2）利用對(duì)偶問題的性質(zhì)證明原問題目標(biāo)函數(shù)值。二、（15分）用順序法或逆序法，求解Ａ到Ｅ的最長(zhǎng)路問題。三、（15分）運(yùn)用表上作業(yè)法求解下列運(yùn)輸問題，表格中間的數(shù)字為運(yùn)價(jià)。產(chǎn)銷甲乙丙丁產(chǎn)量A9181109B11681810C14122166銷量4975學(xué)院：專業(yè)：學(xué)號(hào)：姓名：裝訂線四、（15分）求如下最大指派問題，系數(shù)矩陣為：五、（10分）用圖解法求解目標(biāo)規(guī)劃問題六、（20分）已知線性規(guī)劃問題用單純形法求的最終單純形表如下3/2015/14-3/14110-1/72/700-5/14-25/14若價(jià)值系數(shù)=13，該問題的最優(yōu)解如何改變。（10分）右端項(xiàng)由變?yōu)闀r(shí)，該問題的最優(yōu)解如何變化？（10分）七、（15分）下圖為一網(wǎng)絡(luò)圖：若不考慮方向時(shí)，邊上數(shù)字為邊的長(zhǎng)度，求該圖的最小支撐樹；（5分）若邊上數(shù)字為容量，求從頂點(diǎn)v1到頂點(diǎn)v8的最大流。（7分）求最小割（3分）VV1V2V4V3V5V7V6V85679446459754課程名稱:運(yùn)籌學(xué)一（10分）解：（1）設(shè)對(duì)偶變量分別為y1，y2，y3，則對(duì)偶規(guī)劃為：（min1分，目標(biāo)函數(shù)系數(shù)1分，右端向量1分，約束系數(shù)矩陣1分，變量取值范圍1分）（2）證明：令y=(1,0,2)，易證滿足上述對(duì)偶問題的所有約束條件所以y=(1,0,2)是對(duì)偶問題的一個(gè)可行解，（可行解3分）代入對(duì)偶問題的目標(biāo)函數(shù)得w=2×1+5×0+2×2=6由弱對(duì)偶性得：原問題目標(biāo)函數(shù)值z(mì)≤w=6.得證（弱對(duì)偶性2分）二（15分）方法一：（逆序法標(biāo)號(hào)）AAB1B2B3C1C3C2D1D2E1025115137105675713414(18)(18)(26)(0)(1)(4)(8)(8)(9)(24)（12分）所以，A到E最長(zhǎng)路為26（1分）路徑為A→B1→C1→D2→E（2分）方法二：分4個(gè)階段，k=1,2,3,4K=4時(shí)，（1.5分）K=3時(shí)，（1.5分）（1.5分）（1.5分）K=2時(shí)，（1.5分）（1.5分）（1.5分）K=1時(shí)，（1.5分）所以，A到E最長(zhǎng)路為26（1分）路徑為A→B1→C1→D2→E（2分）四（15分）解：首先變成最小化指派問題。B=(41-Cij)5×5矩陣變換（3分）矩陣變換（3分）（3分）（試指派3分，劃直線1分）調(diào)整（2分）所以（1分）調(diào)整（2分）（再指派1分）此時(shí)最大值W=33+19+41+35+19=147（1分）三（15分）解：由最小元素法得初始運(yùn)輸方案如下表所示：（初始解4分，檢驗(yàn)數(shù)4分）甲乙丙丁產(chǎn)量uiA918110902(14)7(-1)B11681810219(5)(5)C1412216651(3)(-4)5銷量4975Vj94111因?yàn)棣?4，σ33＜0，所以該方案不是最優(yōu)方案。進(jìn)行調(diào)整：（調(diào)整2分，新檢驗(yàn)數(shù)2分）甲乙丙丁產(chǎn)量uiA918110903(14)6(-5)B11681810219(5)(1)C141221661(4)(7)15銷量4975Vj94115因?yàn)棣?4＜0，所以該方案不是最優(yōu)方案，再調(diào)整。新方案如下：（再調(diào)整1分，檢驗(yàn)數(shù)1分）甲乙丙丁產(chǎn)量uiA918110903(14)15B11681810219(5)(6)C141221661(4)(7)6(5)銷量4975Vj94110因?yàn)椋栽摲桨甘亲顑?yōu)方案?？傔\(yùn)費(fèi)為155。（1分）五（10分）解：圖解法見下圖X111X1111055.65.5d1+Bx1-x2=02x1+x2=118x1+10x2=56x1+2x2=10d2+d3-7X211Ad2-由圖知目標(biāo)規(guī)劃的滿意解為線段AB，A(2,4),B(10/3,10/3)，即滿意解為：α1(2,4)+α2(10/3,10/3)=(2α1+10/3α2,4α1+10/3α2)其中0≤α1，α2≤1，α1+α2=1（坐標(biāo)系：1分，絕對(duì)約束1分，三個(gè)目標(biāo)約束2分×3=6分，結(jié)果2分）六（20分）解：（1）當(dāng)c1變?yōu)?3時(shí)，代入最終單純型表得：Cj→13500θCBXBbx1x2x3x45x23/201[5/14]-3/1410/213x1110-1/72/7-σj001/14-31/14（4分）0x321/5014/51-3/513x18/51201/5σj0-1/50-2/5（4分）因?yàn)棣襧≤0，所以X*=（8/5，0，21/5，0）T，Z*=104/2（2分）（2）當(dāng)右邊向量b變?yōu)?8,9)T時(shí)，（8分）所以X*=（10/7，13/14，0，0）T，Z*=265/14（2分）V1V2V1V2V4V3V5V7V6V85544454（4分）最小樹的權(quán)數(shù)為：5+5+5+4+4+4+4=31（1分）（2）增廣鏈流量調(diào)整量V1→V2→V4→V6→V84（2分）V1→V3→V5→V7→V86（2分）V1VV1V2V4V3V5V7V6V8(5,0)(6,6)(7,6)(9,6)(4,0)