江蘇大學(xué)運(yùn)籌學(xué)樣卷3

1、江蘇大學(xué)運(yùn)籌學(xué)期末考試任課老師:張懷勝 考試日期:2012-06-06；班級:工業(yè)09；學(xué)號:3090804031；姓名:徐峰；上機(jī)IP:202.195.169.154；上機(jī)總得分:71 題目填空題判斷題選擇題計(jì)算題1計(jì)算題2計(jì)算題3計(jì)算題4計(jì)算題5計(jì)算題6計(jì)算題7計(jì)算題8應(yīng)用題總分題分510108988888810100得分25389848878171一、填空題（每題1分,共5分；徐峰得分:2分） 1、 已知線性規(guī)劃max Z=3x1+4x2+x3,x1+2x2+x310,2x1+2x2+x316,x1,x2,x30的最優(yōu)基為約束條件系數(shù)矩陣的第一、第二兩列，則最優(yōu)解(x1,x2)= (6,

2、2) 。 +1分 2、 若一個(gè)線性規(guī)劃為無界解，則其對偶問題一定 無可行解 。 +1分 3、 用0-1變量x1、x2、x3分別表示A1、A2、A3的選與不選，值為1表示選中，否則為不選，則A1，A2，A3中必須選兩個(gè)的表達(dá)式為 x1+x2+x32 。×!參考答案:x1+x2+x3=2 4、 一個(gè)可行流為最大流的充要條件是存在一個(gè)截集使其截量 大于 網(wǎng)絡(luò)流的流量。×!參考答案:= 5、 報(bào)童模型中的損失h增加，會(huì)使得最優(yōu)進(jìn)貨量Q0 減小 。×!參考答案:減少或不變 - 二、判斷題（每題1分,共10分；徐峰得分:5分） 1、 在基本可行解中非基變量一定為零。 (正確)

3、 +1分 2、 若線性規(guī)劃的原問題有無窮多最優(yōu)解，則其對偶問題也一定有無窮多最優(yōu)解。 (錯(cuò)誤) +1分 3、 變量取0或1的規(guī)劃是整數(shù)規(guī)劃 (正確) +1分 4、 運(yùn)輸問題的檢驗(yàn)數(shù)就是對偶問題的松馳變量的值。 (錯(cuò)誤)× 5、 最大流問題是找一條從發(fā)點(diǎn)到收點(diǎn)的路，使得通過這條路的流量最大。 (正確)× 6、 m+n1個(gè)變量構(gòu)成基變量組的充要條件是它們不包含閉回路。 (正確) +1分 7、 單位存儲(chǔ)費(fèi)和訂購費(fèi)同時(shí)增加i%，則總成本也增加i% (錯(cuò)誤) +1分 8、 LP 問題的基本可行解對應(yīng)可行域的頂點(diǎn)。 (錯(cuò)誤)× 9、 定義狀態(tài)時(shí)應(yīng)保證各個(gè)階段中所做的決策相互獨(dú)

4、立 (錯(cuò)誤)× 10、 在其他費(fèi)用不變的條件下，隨著單位缺貨費(fèi)用的增加，最優(yōu)訂貨批量將相應(yīng)增加 (正確)× - 三、單項(xiàng)選擇題（每題1分,共10分；徐峰得分:3分） 1、 設(shè)X是一個(gè)線性規(guī)劃問題的基本可行解，如果其中一個(gè)分量xj>0，則： 1)、只有解不退化時(shí)，xj才是一個(gè)基變量選擇 × 2)、只有解退化時(shí)，xj才是一個(gè)基變量 3)、xj是非基變量正確 4)、無論解是否退化，xj一定是一個(gè)基變量2、 設(shè)一目標(biāo)為極大化的線性規(guī)劃有最優(yōu)解，其對偶解的某一個(gè)分量大于零，則該分量對應(yīng)的原問題的約束條件： 1)、可能是緊約束，也可能是松約束正確 2)、不可能是松約束，

5、且當(dāng)右邊項(xiàng)增加時(shí)，其目標(biāo)函數(shù)值上升選擇 × 3)、只能是緊約束，且當(dāng)右邊項(xiàng)增加時(shí)，其目標(biāo)函數(shù)值下降 4)、只能是松約束，且當(dāng)右邊項(xiàng)發(fā)生變化時(shí)目標(biāo)函數(shù)值不會(huì)變化3、 對一個(gè)求目標(biāo)函數(shù)最大的混合整數(shù)規(guī)劃問題，以下命題中不正確的是：選擇 × 1)、任一可行解的目標(biāo)函數(shù)值不可能大于其松弛問題的目標(biāo)函數(shù)最優(yōu)值正確 2)、該問題可行解的個(gè)數(shù)是有限的 3)、該問題可行解中可能存在不取整數(shù)值的變量 4)、其松弛問題的最優(yōu)解可能是該整數(shù)規(guī)劃問題的最優(yōu)解4、 求總銷量小于總產(chǎn)量的運(yùn)輸問題不需要做的是 1)、虛設(shè)一個(gè)銷地 2)、令產(chǎn)地到虛設(shè)的銷地的單位運(yùn)費(fèi)為0選擇正確 3)、刪去一個(gè)產(chǎn)地 +1分

6、 4)、取虛設(shè)的銷地的需求量為恰當(dāng)值5、 設(shè)P是圖G從vs到vt的最短路，則有正確 1)、P的長度等于P的每條邊的長度之和 2)、P的最短路長等于vs到vt的最大流量選擇 × 3)、P的長度等于G的每條邊的長度之和 4)、P有n個(gè)點(diǎn)n-1條邊6、 下列關(guān)于運(yùn)輸問題的說法正確的是選擇 × 1)、運(yùn)輸問題的對偶問題不一定存在最優(yōu)解 2)、平衡運(yùn)輸問題的對偶問題的變量非負(fù) 3)、若變量組B包含有閉回路，則B中的變量對應(yīng)的列向量線性無關(guān)正確 4)、第i行的位勢Ui是第i個(gè)對偶變量7、 某商店經(jīng)銷某種飲料，據(jù)統(tǒng)計(jì)，飲料日需求量(單位：箱)的概率分布為：P(100)=0.1,P(120

7、)=0.25,P(150)=0.35,P(180)=0.2,P(200)=0.1。每天進(jìn)貨一次，進(jìn)價(jià)為6元/箱，零售價(jià)是9元/箱。若當(dāng)天不能售完，則第二天可以4元/箱售完 。為獲得最大利潤，商店每天應(yīng)進(jìn)飲料 1)、120箱 2)、180箱選擇正確 3)、150箱 +1分 4)、200箱8、 下例錯(cuò)誤的說法是選擇 × 1)、標(biāo)準(zhǔn)型的目標(biāo)函數(shù)是求最小值 2)、標(biāo)準(zhǔn)型的目標(biāo)函數(shù)是求最大值 3)、標(biāo)準(zhǔn)型的變量一定要非負(fù)正確 4)、標(biāo)準(zhǔn)型的常數(shù)項(xiàng)非正9、 在生產(chǎn)與存儲(chǔ)問題中選擇正確 1)、狀態(tài)變量為存儲(chǔ)量，決策變量是生產(chǎn)量 +1分 2)、狀態(tài)變量為生產(chǎn)量，決策變量是存儲(chǔ)量 3)、階段指標(biāo)函數(shù)是

8、從第k階段到第n階段的總成本 4)、過程指標(biāo)函數(shù)是從第k階段到下一階段的總成本10、 已知某一求極大值的線性規(guī)劃的最優(yōu)目標(biāo)函數(shù)值，如果加入一個(gè)新約束，則： 1)、無論加入什么樣的約束，最優(yōu)目標(biāo)函數(shù)值不會(huì)下降選擇 × 2)、只有新約束是小于等于約束時(shí)，最優(yōu)目標(biāo)函數(shù)值會(huì)下降正確 3)、無論加入什么樣的約束，最優(yōu)目標(biāo)函數(shù)值不會(huì)上升 4)、只有新約束是大于等于約束時(shí)，最優(yōu)目標(biāo)函數(shù)值會(huì)下降- 四、計(jì)算題 題目1:用圖解法求解下列線性規(guī)劃問題(題分:8，徐峰得分:8)max z=x1+9x24x1+3x2123x1+2x26x1-x2-1x1,x20做題記錄(見圖1)：可行域見圖1中灰色區(qū)域；目

9、標(biāo)函數(shù)初始線見圖1中的A1B1線；結(jié)論：此LP有唯一最優(yōu)解:x1=4/5,x2=9/5；目標(biāo)函數(shù)最優(yōu)值為max z=17；圖1:徐峰所作的圖 答案(見圖2)：可行域見圖2的灰色區(qū)域，圖2中直線A1B1為目標(biāo)函數(shù)等值線；此LP有唯一最優(yōu)解：x1=4/5,x2=9/5,目標(biāo)函數(shù)最優(yōu)值為max z=17。1圖2:答案圖 題目2:用單純形法求解下列線性規(guī)劃問題(題分:9，徐峰得分:9)Maxz=-9x1+x2-M -5x1+6x2- + =302x1-x2+ =2x1+ =5做題記錄(已通過標(biāo)準(zhǔn)化):列單純形表計(jì)算如下:cj0-91000-MCBXBbx1x2x3x4x5x6-Mx630-56-100

10、10x422-101000x55100010檢驗(yàn)數(shù)30M-5M-96M+1-M0001x25-5/61-1/6001/60x477/60-1/6101/60x55100010檢驗(yàn)數(shù)-5-49/601/600-1/6-M此LP為無界解參考答案,列單純形表迭代如下：cj0-91000-MCBXBbx1x2x3x4x5x6-Mx630-56-10010x422-101000x55100010檢驗(yàn)數(shù)-5M-96M+1-M0001x25-5/61-1/6001/60x477/60-1/6101/60x55100010檢驗(yàn)數(shù)-49/601/600-M-1/6此LP為無界解 題目3:用對偶單純形法求解下列線

11、性規(guī)劃問題(題分:8，徐峰得分:8)Maxz=-6x1-6x2-4x1+5x2+ =-20-x1+x2+ =-1-4x1-x2+ =-4做題記錄(已通過標(biāo)準(zhǔn)化):列單純形表計(jì)算如下:cj0-6-6000CBXBbx1x2x3x4x50x3-20-451000x4-1-110100x5-4-4-1001檢驗(yàn)數(shù)0-6-6000-6x151-5/4-1/4000x440-1/4-1/4100x5160-6-101檢驗(yàn)數(shù)300-27/2-3/200此LP的最優(yōu)解為:X=(5,0,0,4,16),min z=30參考答案,列單純形表迭代如下：cj0-6-6000CBXBbx1x2x3x4x50x3-20

12、-451000x4-1-110100x5-4-4-1001檢驗(yàn)數(shù)-6-6000-6x151-5/4-1/4000x440-1/4-1/4100x5160-6-101檢驗(yàn)數(shù)0-27/2-3/200此LP的最優(yōu)解為:X=(5,0,0,4,16)' min z=30 題目4:求解下列運(yùn)輸問題,使總運(yùn)費(fèi)最小(題分:8，徐峰得分:4)單位運(yùn)費(fèi)與產(chǎn)量銷量表運(yùn)費(fèi)B1B2B3B4產(chǎn)量A15714910A210157645A315919105銷量8201616""做題過程(加括號的為檢驗(yàn)數(shù),其余為運(yùn)輸量):第1次運(yùn)輸方案與檢驗(yàn):表1B1B2B3B4產(chǎn)量A182(15)(11)10A2

13、(-3)13161645A3(8)5(18)(10)5銷量8201616第2次運(yùn)輸方案與檢驗(yàn):表2B1B2B3B4產(chǎn)量A1()710A285161645A355銷量8201616表2所示運(yùn)輸方案為最優(yōu),最小總運(yùn)費(fèi)為:457×,總運(yùn)費(fèi)計(jì)算錯(cuò)誤!×,調(diào)整后的運(yùn)輸方案不是基本可行解!答案：.第1次運(yùn)輸方案與檢驗(yàn)(加括號的數(shù)字為檢驗(yàn)數(shù),其余的數(shù)字為運(yùn)輸量或產(chǎn)量和銷量):表1B1B2B3B4產(chǎn)量A182(15)(11)10A2(-3)13161645A3(8)5(18)(10)5銷量8201616第2次運(yùn)輸方案與檢驗(yàn):表2B1B2B3B4產(chǎn)量A4(3)10(15)(11)10A585

14、161645A6(11)5(18)(10)5銷量8201616第2次檢驗(yàn)數(shù)無負(fù)數(shù)，故第2次運(yùn)輸方案為最優(yōu)，最小總運(yùn)費(fèi)為 478 題目5:用匈牙利法求解下列指派問題(題分:8，徐峰得分:8)完成任務(wù)所需時(shí)間表人任務(wù)任務(wù)1任務(wù)2任務(wù)3任務(wù)4第1人810717第2人111239第3人771316第4人7667做題記錄：最優(yōu)指派方案為：11，23，32，44，目標(biāo)函數(shù)最小值為25答案：最優(yōu)指派方案為：11，23，32，44，目標(biāo)函數(shù)最小值為25 題目7:求下圖中v1至其它各點(diǎn)的最短路(題分:8，徐峰得分:8)做題過程：以P表示最短路標(biāo)號，T表示一般路程標(biāo)號，標(biāo)號過程如下：P(vs)=0，T(v3)=5

15、，T(v4)=6，T(v2)=13，P(v3)=5，P(v3)來自于點(diǎn)v1;T(v5)=10，P(v4)=6，P(v4)來自于點(diǎn)v1;T(v7)=14，T(v6)=21，P(v5)=10，P(v5)來自于點(diǎn)v3;T(v6)=20，T(v8)=13，P(v2)=13，P(v2)來自于點(diǎn)v1;P(v8)=13，P(v8)來自于點(diǎn)v5;P(v7)=14，P(v7)來自于點(diǎn)v4;T(v6)=18，P(v6)=18，P(v6)來自于點(diǎn)v7;點(diǎn)v1到其它各點(diǎn)的最短路見下圖:答案：標(biāo)號過程如下：P(v1)=0，T(v2)=13，T(v3)=5，T(v4)=6，P(v3)=5，P(v3)來自于點(diǎn)v1T(v2)

16、=13，T(v4)=6，T(v5)=10，P(v4)=6，P(v4)來自于點(diǎn)v1T(v2)=13，T(v5)=10，T(v6)=21，T(v7)=14，P(v5)=10，P(v5)來自于點(diǎn)v3T(v2)=13，T(v6)=20，T(v7)=14，T(v8)=13，P(v2)=13，P(v2)來自于點(diǎn)v1T(v6)=20，T(v7)=14，T(v8)=13，P(v8)=13，P(v8)來自于點(diǎn)v5T(v6)=20，T(v7)=14，P(v7)=14，P(v7)來自于點(diǎn)v4T(v6)=18，P(v6)=18，P(v6)來自于點(diǎn)v7點(diǎn)v1到其它各點(diǎn)的最短路見下圖:題目8:求下圖所示網(wǎng)絡(luò)中v1至v8的

17、最大流，并找出一個(gè)最小截集(題分:8，徐峰得分:7)做題記錄:第1次標(biāo)號: s(0,+),2(s,3),6(2,1),t(6,1);×點(diǎn)v6標(biāo)號錯(cuò)誤;第1次增廣鏈: v1v2v6v8;第1次調(diào)整后的可行流如下圖:第2次標(biāo)號: s(0,+),2(s,2),6(2,2),7(-6,2),t(7,2);第2次增廣鏈: v1v2v6v7v8;第2次調(diào)整后的可行流如下圖:第3次標(biāo)號: s(0,+);已是最大流,最大流量為11,最小截集為:(v1,v4),(v1,v2),(v1,v3)。答案：第1次標(biāo)號: v1(0,+),v2(v1,3),v6(v2,3),v7(-v6,3),v8(v7,3);

18、第1次增廣鏈: v1v2v6v7v8;第1次調(diào)整后的可行流如下圖：第2次標(biāo)號: v1(0,+)；至此標(biāo)號中斷,收點(diǎn)v8得不到標(biāo)號;已無增廣鏈,故調(diào)整后的流是最大流,最大流量為11,最小截集為:(v1,v2),(v1,v3),(v1,v4)。題目9:用動(dòng)態(tài)規(guī)劃方法求解下列資源分配問題(題分:8，徐峰得分:8)分配的資源數(shù)01234甲創(chuàng)的效益09111414乙創(chuàng)的效益0471012丙創(chuàng)的效益011141717做題記錄:s01234f3(s)011141717u3*01234f2(s)011151821u2*001'1,2''1,2,3'u101234u1*=1s=40+219+1811+1514+1114+0f1(4)=27最優(yōu)分配方案為: u*=(1,1,2),最大總效益為27 答案:s01234f3(s)011141717u3*01234f2(s)011151821u2*0011,21,2,3u101234u1*=