1、中南大學(xué)考試試題2013 -2014 學(xué)年 下 學(xué)期 時(shí)間120分鐘 運(yùn)籌學(xué) 課程 48 學(xué)時(shí) 3 學(xué)分 考試形式： 閉 卷 專(zhuān)業(yè)年級(jí)： 商學(xué)院12級(jí) 總分100分，占總評(píng)成績(jī)70%一、 對(duì)下列線性規(guī)劃模型（1）求上述線性規(guī)劃的最優(yōu)解（20分）（2） 寫(xiě)出上述線性規(guī)劃的對(duì)偶規(guī)劃模型，并求出其最化解（15分）答案及評(píng)分標(biāo)準(zhǔn)：（1）無(wú)最優(yōu)解標(biāo)準(zhǔn)化正確 5分利用對(duì)偶單純形法，大M法或二階段單純形法求解結(jié)果正確 15分方法正確結(jié)果不正確 8-15分使用對(duì)偶單純形法求解 0分。（2）上述規(guī)劃問(wèn)題無(wú)解。寫(xiě)出對(duì)偶單純形 10分指出無(wú)解 5分。二、某工廠要對(duì)一種產(chǎn)品制定今后三個(gè)時(shí)期的生產(chǎn)計(jì)劃，據(jù)估計(jì)在今后的三

2、個(gè)時(shí)期內(nèi)，市場(chǎng)對(duì)該產(chǎn)品的需求量如下：時(shí)期(k)123需求量234假定該廠生產(chǎn)每批次產(chǎn)品的固定成本為3(千元)，如不生產(chǎn)就為0；每單位產(chǎn)品成本為1（千元）；每個(gè)時(shí)期生產(chǎn)能力所允許的最大生產(chǎn)批量不超過(guò)5個(gè)單位；每個(gè)時(shí)期期末未售出的產(chǎn)品，每單位需付存儲(chǔ)費(fèi)0.5（千元）。還假定在第一個(gè)時(shí)期的初始庫(kù)存量為0，第三個(gè)時(shí)期之末的庫(kù)存量也為0。試問(wèn)該廠該如何安排各個(gè)時(shí)期的生產(chǎn)與庫(kù)存，才能在滿(mǎn)足市場(chǎng)需要的條件下，使總成本最小。答案及評(píng)分標(biāo)準(zhǔn)：解：需求量 D1=2；D2=3；D3=4。（1）階段n: 1,2,3,4（2）狀態(tài)Sn: S1=0; S2=S1+X1-D1=0,1,2,3; S3=S2+X2-D2=0,

3、1,2,3,4; S4=S3+X3-D3=0; （得分點(diǎn)：4分）（3）決策 X1=2,3,4,5; X2=0,1,2,3,4,5; X3=0,1,2,3,4 （得分點(diǎn)：3分）（4）狀態(tài)轉(zhuǎn)移方程：Sn+1=Sn+Xn-Dn （得分點(diǎn)：1分）（5）階段指標(biāo)函數(shù)：rn(Xn)=3+1*Xn+0.5Sn, Xn0 =0.5Sn, Xn=0 （得分點(diǎn)：2分）（6）指標(biāo)函數(shù)遞推方程：, （得分點(diǎn)：2分）利用表格計(jì)算，從最后一個(gè)階段開(kāi)始, n=3時(shí)：S3+X3-D3=0， 即X3=4-S3 （得分點(diǎn)：2分） X3 S30123407+0=77416+0.5=6.56.5325+0.5*2=66234+0.5

4、*3=5.55.5140+0.5*4=220n=2時(shí)：S2+X2D2=3， 即X23-S2；S3=S2+X2-3 （得分點(diǎn)：3分） X2 S201234506+7=137+6.5=13.58+6=1413315.5+7=12.56.5+6.5=137.5+6=13.58.5+5.5=1412.5225+7=126+6.5=12.57+6=138+5.5=13.59+2=1111531.5+7=8.55.5+6.5=126.5+6=12.57.5+5.5=138.5+2=10.58.50n=1時(shí)：S1+X1D1=2， 即X12；X1=5; S2=S1+X1-2=X1-2 （得分點(diǎn)：1分） X1

5、S1234505+13=186+12.5=18.57+11=188+8.5=16.516.55最優(yōu)策略為：X*=X1*,X2*,X3*=5,0,4 （得分點(diǎn)：1分）Z*=16.5 （得分點(diǎn)：1分）三、現(xiàn)從A1，A2，A3三個(gè)產(chǎn)糧區(qū)向B1，B2，B3，B4四個(gè)地區(qū)運(yùn)送糧食，已知三個(gè)產(chǎn)糧區(qū)可提供的糧食分別為9，5，7（萬(wàn)噸），四個(gè)地區(qū)的糧食需求量分別為3，8，4，6（萬(wàn)噸），產(chǎn)糧地到需求地的單位運(yùn)價(jià)（萬(wàn)元）如下表所示，請(qǐng)問(wèn)如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最??？（15分）銷(xiāo)地產(chǎn)糧地B1B2B3B4產(chǎn)量A1291189A214525A395367需求量3846解：（1）用最小元素法得到初始調(diào)運(yùn)方案如下： 銷(xiāo)地產(chǎn)糧

6、地B1B2B3B4產(chǎn)量A1549A2325A3347需求量3846 21總運(yùn)費(fèi)：Z(1) = 59 + 48 + 31 + 22 +35 +43 = 111（2）求得空格的檢驗(yàn)數(shù)如下：l11=5，l13=4，l22=1，l23=4，l31=6，l34=2選l11=5對(duì)應(yīng)的空格x11入基，在x11的閉回路中，標(biāo)正號(hào)的格子增加3，標(biāo)負(fù)號(hào)的格子減少3，得新調(diào)運(yùn)方案如下：銷(xiāo)地產(chǎn)糧地B1B2B3B4產(chǎn)量A13519A255A3347需求量3846 21總運(yùn)費(fèi)：Z(2) = 32 + 59 +18 + 52 +35 +43 =96（3）求得新調(diào)運(yùn)方案空格的檢驗(yàn)數(shù)如下：l13=4，l21=5，l22=1，l

7、23=4，l31=11，l34=2全部空格檢驗(yàn)數(shù)均為非負(fù)，當(dāng)前調(diào)運(yùn)方案為最優(yōu)： x11 = 3，x12 = 5，x14= 1，x24= 5，x32= 3，x33= 4 Z* = 32 + 59 +18 + 52 +35 +43 =96四、有5項(xiàng)工作要分派給5個(gè)人完成，每人只能作一項(xiàng)工作，每項(xiàng)工作也只能由一個(gè)人完成，各人完成各項(xiàng)工作獲得的利潤(rùn)見(jiàn)下表。請(qǐng)問(wèn)應(yīng)如何安排人選才能使完成這5項(xiàng)工作所獲得的總利潤(rùn)最大？（15分）任務(wù)人員 利潤(rùn)ABCDE甲乙丙丁戊513101513127491081461116121391377128145解： 5 12 8 12 7 13 7 14 13 12 10 4 6

8、 9 8 （Cij） 15 9 11 13 14 13 10 16 7 5縮減矩陣B： 11 4 8 4 9 3 9 2 3 4 6 12 10 7 8 B（bij） 1 7 5 3 2 3 6 0 9 11 7 0 4 0 4 1 7 0 1 1 0 6 4 1 1 0 6 4 2 0 3 6 0 9 10 7 0 5 0 4 0 6 0 0 0 0 6 5 1 1 0 6 5 2 0 2 5 0 8 9 即：甲B，乙D，丙A，丁E，戊C最大利潤(rùn)：Z*=12+13+10+14+16=65五、求下列容量網(wǎng)絡(luò)從源點(diǎn)S到匯點(diǎn)T的最大流和最小割，弧旁權(quán)值為弧容量。（15分）82154936752198535S12435T67 解：第一步，給出初始可行流，如下圖所示 （5分）58,3+3+22,11,15,54,29,53,36,5+17,55,52,01,09,2+5+18,5+35,03,3S12435T67第二步，判斷初始可行流是否最大流，由于找不到增廣鏈，所以初始可行流為最大流。 （5分）第三步，求最小割和最大流量，在可以標(biāo)號(hào)的點(diǎn)集S,1,2,3,4,5,6,7和不能標(biāo)號(hào)的點(diǎn)集T之間畫(huà)一條割線，形成最小割Smin=(