江蘇大學運籌學樣卷2

1、江蘇大學運籌學期末考試任課老師:張懷勝考試日期:2012-06-06；班級:工業(yè)09；學號:3090804013；姓名：孫鵬飛；上機IP:202.195.169.161；上機總得分：93題目填空 題判斷 題選擇 題計算 題1計算 題2計算 題3計算 題4計算 題5計算 題6計算 題7計算 題8應用 題總分題分510108988888810100得分478898888871093一、填空題（每題1分，共5分；孫鵬飛得分:4分）1、 若線性規(guī)劃有無窮多最優(yōu)解，則其最優(yōu)表格中至少有一個非基變量的檢驗 數等于零。V +1分2、設 max Z=3x +4x +x ,x +2x +x 10,2x +2x

2、+x 16,x ,x ,x NO,則在最優(yōu)基123123123123不變時，請用區(qū)間表示b1的允許取值范圍10,16。X!參考答案：8,163、用分枝定界法求解最大化的純整數規(guī)劃問題，某分枝得到整數可行解，則其 目標值可作為其它分枝的目標值的下界。V +1分4、 一個無圈并且連的無向圖稱為樹。V +1分 5、采用（s,S）存貯策略的模型時，若檢查出的存貯量x=s時，則訂貨量為S-xV +1分二、判斷題（每題1分，共10分；孫鵬飛得分:7分）1、人工變量一旦出基就不會再進基。（正確）V +1分2、若X*、Y*分別是原問題與對偶問題的最優(yōu)解，則X*二Y* （正確）X3、求最大值問題的目標函數值是各

3、分枝函數值的上界（錯誤）X4、運輸問題中的位勢就是其對偶變量。（正確）V +1分5、最大流問題是找一條從發(fā)點到收點的路，使得通過這條路的流量最大。（錯 誤）V +1分6、將指派問題的效率矩陣每行分別加上一個數后最優(yōu)解不變（正確）+1分7、在不允許缺貨，邊生產邊供應的存儲模型要比瞬時供應的存儲模型下的經濟 批量要?。ㄥe誤）V +1分8、LP問題的基本可行解對應可行域的頂點。（正確）V +1分9、若某種資源影子價格為零，則該資源一定有剩余。（正確）X10、在其他費用不變的條件下，隨著單位缺貨費用的增加，最優(yōu)訂貨批量將相 應增加（錯誤）V +1分三、單項選擇題（每題1分，共10分；孫鵬飛得分：8分）

4、1、線性規(guī)劃具有無界解是指正確1）、存在某個檢驗數0,且此檢驗數所在的列上的系數均不0選擇X 2）、可行解集合無界3）、有相同的最小比值4）、最優(yōu)表中所有非基變量的檢驗數非零2、兩個互為對偶問題的線性規(guī)劃，（LP）為原問題，（DP）為對偶問題，以下論斷 中錯誤的是：選擇正確1）、若（LP）有可行解，則（DP）也必有可行解V +1分2）、若（LP）和（DP）都有可行解，則（LP）和（DP）目標函數最優(yōu)值相等3）、若（LP）有最優(yōu)解，則（DP）也必有最優(yōu)解4）、若（LP）無界，則（DP）無可行解3、max z=3x +x ,4x +3x 7,x +2x 5,x ,x =0 或 1，最優(yōu)解是1)、(

5、0，1)2)、(1，0)3)、(0,0)選擇正確 4）、(1，1) V +1 分121212124、為建立運輸問題的改進方案，在調整路線中調整量應為選擇X 1）、負號格的最大運量正確2）、負號格的最小運量3）、正號格的最小運量4）、正號格的最大運量5、連通圖G有n個點，其生成樹是T,則有1）、T的長度等于G的每條邊的長度之和2）、T有n個點n條邊選擇正確3）、T有n個點n-1條邊V +1分4）、T有n-1個點n條邊6、下列結論正確的有選擇正確1）、運輸問題的運價表第r行的每個c同時加上一個非零常數k,其最優(yōu)調運方案不變V +1分1J2）、運輸問題的運價表第p列的每個ci,同時乘以一個非零常數k

6、,其 最優(yōu)調運方案不變_3）、運輸問題的運價表的所有七同時乘以一個非零常數k,其最優(yōu)調4）、不平衡運輸問題不一定存在最優(yōu)解7、某單位每年需零件A 5000件。設該零件的單價為5元/件。年存貯費為單價 的20%。不允許缺貨。若每組織采購一次的費用為49元，一次購買10002499 件時，給予3%折扣，購買2500件以上時，給予5%折扣。則最佳采購批量為1）、700 件選擇正確2）、1000件V +1分3）、 750 件4）、 2500件8、線性規(guī)劃標準型的系數矩陣Amxn，要求選擇正確1）、秩（A）=m并且m忍n V +1分2）、秩（A）=m 并且 mVn3）、秩（A）=m 并且 m=n4）、秩

7、（A）=n 并且 nVm9、以下關系中，不是線性規(guī)劃與其對偶問題的對應關系的是選擇正確1）、約束條件組的不等式反向V +1分2）、一個目標函數的系數行向量為另一個約束條件組的常數列3）、一個約束條件組的常數列為另一個目標函數的系數行向量4）、約束條件組的系數矩陣互為轉置矩陣10、某個常數bi波動時，最優(yōu)表中引起變化的有 選擇正確1）、B-1b V +1分2）、CCbB-1N3）、BN1 B4）、B-1N四、計算題 題目1：用圖解法求解下列線性規(guī)劃問題（題分：8,孫鵬飛得分:8）min z=-x1 +3x23x1+8x2244x1+x2 -5w做題記錄（見圖1）：可行域為空，此LP無可行解。圖1

8、：孫鵬飛所作的圖答案（見圖2）：可行域為空，此LP無可行解。1圖2:答案圖題目2:用單純形法求解下列線性規(guī)劃問題（題分:9,孫鵬飛得分:9）Maxz=-xx2-M-7X+6x2 - + =42-8x1+5x2+ =40-2X+3x2+ =6做題記錄（已通過標準化）: 列單純形表計算如下：c.0-1-1000-MCXbxxxxxxBB123456-Mx642-76-10010 x440-8501000 x56-230010檢驗數42M-1-7M6M-1-M000-Mx630-30-10-210 x430-14/3001-5/30-1x22-2/31001/30檢驗數2+30M-5/3-3M0-M

9、01/3-2M0此LP無可行解參考答案，列單純形表迭代如下:cj0-1-1000-MCBXBbx1x2x3x4x5x6-Mx642-76-10010 x440-8501000 x56-230010檢驗數-7M-16M-1-M000-Mx630-30-10-210 x430-14/3001-5/30-1x22-2/31001/30檢驗數-3M-5/30-M0-2M+1/30此LP無可行解題目3:用對偶單純形法求解下列線性規(guī)劃問題（題分:8，孫鵬飛得分:8）Maxz=-6x1-3x23x1-2x2+ =-6x1+x2+ =15x1-4x2+ =20做題記錄（已通過標準化）: 列單純形表計算如下：c

10、.0-6-3000CBXBbx1x2x3x4x50 x3-63-21000 x41110100 x5205-4001檢驗數0-6-3000-3x23-3/21-1/2000 x-25/201/2100 x532-10-201檢驗數9-21/20-3/200此LP無可行解參考答案，列單純形表迭代如下:cj0-6-3000CBXBbx1x2x3x4x50 x3-63-21000 x41110100 x5205-4001檢驗數-6-3000-3x23-3/21-1/2000 x4-25/201/2100 x532-10-201檢驗數-21/20-3/200此LP無可行解題目4:求解下列運輸問題,使總

11、運費最?。}分:8,孫鵬飛得分:8）單位運費與產量銷量表運費B1B2B3B4產量A112112097A21317121130A3611688銷量226512做題過程（加括號的為檢驗數，其余為運輸量）： 第1次運輸方案與檢驗：表1B1B2B3B4產量A1(1)(-4)(9)77A2196(-1)530A33(1)5(4)8銷量226512第3次運輸方案與檢驗:表3B1B2B3B4產量A1(1)6(10)17A214(4)51130A38(5)(1)(4)8銷量226512表3所示運輸方案為最優(yōu)，最小總運費為:486答案：.第1次運輸方案與檢驗（加括號的數字為檢驗數,其余的數字為運輸量或產量和銷量

12、）:表1B1B2B3B4產量A1(1)(-4)(10)77A21465530A38(1)(1)(4)8銷量226512第2次運輸方案與檢驗:表2B1B2B3B4產量A4(1)6(10)17A514(4)51130A68(5)(1)(4)8銷量226512第2次檢驗數無負數，故第2次運輸方案為最優(yōu)，最小總運費為486題目5:用匈牙利法求解下列指派問題（題分:8,孫鵬飛得分:8）完成任務所需時間表人任務任務1任務2任務3任務4第1人93107第2人1391213第3人2186第4人78137做題記錄:9310T6（)44 ,5(0)33 1391213-A-(41(0)421861(）45(0)0

13、34781374:3-e-023（0）最優(yōu)指派方案為：1一2，23，3一1，4一4,目標函數最小值為24答案：9310 76 (445 (0) 3313 912 13-4(）（。）441 (0) 421861 ()45(0) 0347 813 7 J:3023 (0)最優(yōu)指派方案為：1一2，2一3，3一1，4一4，目標函數最小值為24題目7:求下圖中v1至其它各點的最短路（題分:8,孫鵬飛得分:8）做題過程：以P表示最短路標號，T表示一般路程標號，標號過程如下:P(vs)=0，T(v ) = 14，T(v ) = 13，T(v )=9，P(v )=9， P(v )來自于點 v ; 423331

14、T(v6) = 12，T(v5)=23，P(v6) = 12， P(v6)來自于點 v3;T(v7) = 19，T(v8)=17，T(v5)=21，P(v2) = 13，P(v2)來自于點 vP(v4)=14，P(v4)來自于點 v1;P(v8)=17，P(v8)來自于點 v ;6P(v,=19, P(v7)來自于點 v6;P(v,=21, P(v?來自于點 v6;點；到其它各點的最短路見下圖:答案：標號過程如下：P(vi)=0， TOC o 1-5 h z T(v ) = 13，T(v )=9，T(v )=14，P(v )=9， P(v )來自于點 v 234331T(v ) = 13，T(

15、v) = 14，T(v )=23，T(v) = 12，P(v)=12，P(v )來自于點 v 2456663T(v ) = 13，T(v) = 14，T(v )=21，T(v) = 19，T(v8)=17，P(v) = 13，P(v )來自于點 v 2457221T(v4) = 14，T(v5)=21，T(v7) = 19，T(v8) = 17，P(v4)=14，P(v4)來自于點 v1T(v5)=21，T(v7) = 19，T(v8)=17，P(v8) = 17，P(v8)來自于點 v6T(v5)=21，T(v7) = 19，P(v7) = 19，P(v7)來自于點 v6T(v5)=21，P

16、(v5)=21，P(v5)來自于點 v6點v到其它各點的最短路見下圖：6 TOC o 1-5 h z 題目8:求下圖所示網絡中v至v的最大流，并找出一個最小截集(題分:8,孫鵬 飛得分：8)18做題記錄：第 1 次標號：s(0,+8),4(s,15),2( -4,6),7(2,6),t(7,6);第1次增廣鏈：vlv4-V2-V7-v8 1次調整后的可行流如下圖：(13J)73,3)第 2 次標號：s(0,+8),4(s,9),7(4,1),6(7,1),2( -6,1),3(2,1);已是最大流，最大流量為22,最小截集為：(v ,v ),(v ,v ),(v ,v8),(v ,v8)。25

17、3567答案：第 1 次標號：v (0,+8),v (v ,15),v (-v ,6),v (v ,6),v8(v ,6);14124727第1次增廣鏈：vlv4-V2-V7-v8 1次調整后的可行流如下圖：第 2 次標號：v (0,+8),v (v ,9),v (v ,1),v (-v ,1),v (v ,1),v (v ,1)；至此標號中斷，收點 v141742767328得不到標號；已無增廣鏈，故調整后的流是最大流，最大流量為22,最小截集為：(v ,v8),(v ,v ),(v ,v8),(v ,v )。 725635題目9:用動態(tài)規(guī)劃方法求解下列資源分配問題(題分:8，孫鵬飛得分:7)分配的資源數01234甲創(chuàng)的效益012161719乙創(chuàng)的效益09111315丙創(chuàng)的效益011151819做題記錄:s01234f3(s)011151819u *01234f2(s)011202427u2*00111u101234u1*=1,2s=40+2712+2416+2017+1119+0f 4)=36最優(yōu)分配方案為：u*=(1,1,2),最大總效益為x答案:s01234f3(s)011151819u *01234f2(s)011202427u2*00111u101234*=1,2s=40+2712+2416