運(yùn)籌學(xué)_判斷題和模擬試卷

1、.注意：1、運(yùn)籌學(xué)考1、2、5、6章，題目都是書上的例題， 這是判斷題。2、題型:填空，選擇，判斷，建模，計(jì)算。3、發(fā)現(xiàn)選擇題中一個(gè)錯(cuò)誤，第6章第2題，答案應(yīng)該C。4、大部分建立模型和計(jì)算是第一章內(nèi)容，加選擇判斷題目已經(jīng)發(fā)給你們了，主要考對概念，性質(zhì)，原理，算法的理解。判斷題一、 線性規(guī)劃1.若線性規(guī)劃存在最優(yōu)解則一定存在基本最優(yōu)解2.若線性規(guī)劃無界解則其可行域無界3.可行解一定是基本解4.基本解可能是可行解5.線性規(guī)劃的可行域無界則具有無界解6.最優(yōu)解不一定是基本最優(yōu)解7.xj 的檢驗(yàn)數(shù)表示變量 xj 增加一個(gè)單位時(shí)目標(biāo)函數(shù)值的改變量8.可行解集有界非空時(shí),則在極點(diǎn)上至少有一點(diǎn)達(dá)到最優(yōu)值9.

2、若線性規(guī)劃有三個(gè)最優(yōu)解X(1)、X(2)、X(3)，則X=X(1)+(1-)X(3)及X=1X(1)+2X(2)+3X(3)均為最優(yōu)解,其中10. 任何線性規(guī)劃總可用大M單純形法求解11. 凡能用大M法求解也一定可用兩階段法求解12.兩階段法中第一階段問題必有最優(yōu)解13.兩階段法中第一階段問題最優(yōu)解中基變量全部非人工變量,則原問題有最優(yōu)解14.任何變量一旦出基就不會再進(jìn)基15.人工變量一旦出基就不會再進(jìn)基16.普通單純形法比值規(guī)則失效說明問題無界15.將檢驗(yàn)數(shù)表示為CBB-1AC的形式,則求極大值問題時(shí)基可行解是最優(yōu)解的充要條件是018.當(dāng)最優(yōu)解中存在為零的基變量時(shí),則線性規(guī)劃具有多重最優(yōu)解1

3、9.當(dāng)最優(yōu)解中存在為零的非基變量時(shí),則線性規(guī)劃具唯一最優(yōu)解20.可行解集不一定是凸集21.將檢驗(yàn)數(shù)表示為的形式,則求極小值問題時(shí),基可行解為最優(yōu)解當(dāng)且僅當(dāng)j0，j1,2,，n22.若線性規(guī)劃存在基本解則也一定存在基本解可行解23.線性規(guī)劃的基本可行解只有有限多個(gè)24.在基本可行解中基變量一定不為零25. 是一個(gè)線性規(guī)劃數(shù)學(xué)模型二 對偶規(guī)劃1.任何線性規(guī)劃都存在一個(gè)對應(yīng)的對偶線性規(guī)劃2.原問題(極大值)第i個(gè)約束是“”約束，則對偶變量yi03.互為對偶問題，或者同時(shí)都有最優(yōu)解，或者同時(shí)都無最優(yōu)解4.對偶問題有可行解，則原問題也有可行解5.原問題有多重解，對偶問題也有多重解在以下610中，設(shè)X*、

4、Y*分別是 的可行解6.則有CX*Y*b7.CX*是w的下界8.當(dāng)X*、Y*為最優(yōu)解時(shí)，CX*=Y*b；9.當(dāng)CX*=Y*b時(shí)，有Y*Xs+YsX*=0成立10.X*為最優(yōu)解且B是最優(yōu)基時(shí)，則Y*=CBB1是最優(yōu)解11.對偶問題有可行解，原問題無可行解，則對偶問題具有無界解12.原問題無最優(yōu)解，則對偶問題無可行解13.對偶問題不可行，原問題無界解14.原問題與對偶問題都可行，則都有最優(yōu)解15.原問題具有無界解，則對偶問題不可行16.若某種資源影子價(jià)格為零，則該資源一定有剩余17.原問題可行對偶問題不可行時(shí)，可用對偶單純形法計(jì)算18.對偶單純法換基時(shí)是先確定出基變量，再確定進(jìn)基變量19.對偶單純

5、法是直接解對偶問題問題的一種方法20.對偶單純形法比值失效說明原問題具有無界解21.在最優(yōu)解不變的前提下，基變量目標(biāo)系數(shù)ci的變化范圍可由式 確定22.在最優(yōu)基不變的前提下，常數(shù)br的變化范圍可由式 確定，其中 為最優(yōu)基B的逆矩陣 第r列23.減少一約束，目標(biāo)值不會比原來變差24.增加一個(gè)變量，目標(biāo)值不會比原來變好25.當(dāng)bi在允許的最大范圍內(nèi)變化時(shí)，最優(yōu)解不變?nèi)?、整?shù)規(guī)劃1.整數(shù)規(guī)劃的最優(yōu)解是先求相應(yīng)的線性規(guī)劃的最優(yōu)解然后取整得到2.部分變量要求是整數(shù)的規(guī)劃問題稱為純整數(shù)規(guī)劃3.求最大值問題的目標(biāo)函數(shù)值是各分枝函數(shù)值的上界4.求最小值問題的目標(biāo)函數(shù)值是各分枝函數(shù)值的下界5.變量取0或1的規(guī)劃

6、是整數(shù)規(guī)劃6.整數(shù)規(guī)劃的可行解集合是離散型集合7. 01規(guī)劃的變量有n個(gè)，則有2n個(gè)可行解8.6x1+5x210、15或20中的一個(gè)值，表達(dá)為一般線性約束條件是 6x1+5x210y1+15y2+20y3，y1+y2+y31，y1、y2、y30或19. 高莫雷（R.E.Gomory）約束是將可行域中一部分非整數(shù)解切割掉10.隱枚舉法是將所有變量取0、1的組合逐個(gè)代入約束條件試算的方法尋找可行解四、目標(biāo)規(guī)劃1.正偏差變量大于等于零，負(fù)偏差變量小于等于零2.系統(tǒng)約束中沒有正負(fù)偏差變量3.目標(biāo)約束含有正負(fù)偏差變量4.一對正負(fù)偏差變量至少一個(gè)大于零5.一對正負(fù)偏差變量至少一個(gè)等于零6.要求至少到達(dá)目標(biāo)

7、值的目標(biāo)函數(shù)是max Z=d+7.要求不超過目標(biāo)值的目標(biāo)函數(shù)是 min Z=d-8.目標(biāo)規(guī)劃沒有系統(tǒng)約束時(shí)，不一定存在滿意解9.超出目標(biāo)值的差值稱為正偏差10.未到達(dá)目標(biāo)的差值稱為負(fù)偏差五、運(yùn)輸與指派問題1.運(yùn)輸問題中用位勢法求得的檢驗(yàn)數(shù)不唯一2.平衡運(yùn)輸問題一定有最優(yōu)解3.不平衡運(yùn)輸問題不一定有最優(yōu)解4.產(chǎn)地?cái)?shù)為3，銷地?cái)?shù)為4的平衡運(yùn)輸問題有7個(gè)基變量5.mn1個(gè)變量組構(gòu)成一組基變量的充要條件是它們不包含閉回路6.運(yùn)輸問題的檢驗(yàn)數(shù)就是其對偶變量7.運(yùn)輸問題的檢驗(yàn)數(shù)就是對偶問題的松馳變量8.運(yùn)輸問題的位勢就是其對偶變量9.不包含任何閉回路的變量組必有孤立點(diǎn)10.含有孤立點(diǎn)的變量組一定不含閉回路

8、11.用一個(gè)常數(shù)k加到運(yùn)價(jià)矩陣C的某列的所有元素上，則最優(yōu)解不變12.令虛設(shè)的產(chǎn)地或銷地對應(yīng)的運(yùn)價(jià)為一任意大于零的常數(shù)c(c0),則最優(yōu)解不變13.若運(yùn)輸問題的供給量與需求量為整數(shù)，則一定可以得到整數(shù)最優(yōu)解14.按最小元素法求得運(yùn)輸問題的初始方案, 從任一非基格出發(fā)都存在唯一一個(gè)閉回路15.運(yùn)輸問題中運(yùn)價(jià)表的每一個(gè)元素都分別乘于一個(gè)常數(shù),則最優(yōu)解不變16.運(yùn)輸問題中運(yùn)價(jià)表的每一個(gè)元素都分別加上一個(gè)常數(shù),則最優(yōu)解不變17.5個(gè)產(chǎn)地6個(gè)銷地的平衡運(yùn)輸問題有11個(gè)變量18.5個(gè)產(chǎn)地6個(gè)銷地的平衡運(yùn)輸問題有30個(gè)變量19.5個(gè)產(chǎn)地6個(gè)銷地的銷大于產(chǎn)的運(yùn)輸問題有11個(gè)基變量20.產(chǎn)地?cái)?shù)為3銷地?cái)?shù)為4的平

9、衡運(yùn)輸中，變量組x11,x13,x22,x33,x34可作為一組基變量六、網(wǎng)絡(luò)模型1.容量不超過流量2.最大流問題是找一條從起點(diǎn)到終點(diǎn)的路，使得通過這條路的流量最大3.容量Cij是?。╥，j）的最大通過能力4.流量fij是?。╥，j）的實(shí)際通過量5.可行流是最大流的充要條件是不存在 發(fā)點(diǎn)到收點(diǎn)的增廣鏈6.截量等于截集中弧的流量之和7.任意可行流量不超過任意截量8.任意可行流量不小于任意截量9.存在增廣鏈說明還沒有得到最大流量10.存在增廣鏈說明已得到最大流11.找增廣鏈的目的是：是否存在一條從 發(fā)點(diǎn)到收點(diǎn)的路，使得可以增加這條路的流量12.狄克斯屈拉算法是求最大流的一種標(biāo)號算法13.破圈法是：

10、任取一圈，去掉圈中最長邊，直到無圈14.避圈法（加邊法）是：去掉圖中所有邊，從最短邊開始添加，加邊的過程中不能形成圈，直到連通（n1條邊）15.連通圖一定有支撐樹16.P是一條增廣鏈，則后向弧上滿足流量 f 017.P是一條增廣鏈，則前向弧上滿足流量 fij Cij18.可行流的流量等于每條弧上的流量之和19.最大流量等于最大流20.最小截集等于最大流量七、網(wǎng)絡(luò)計(jì)劃1.網(wǎng)絡(luò)計(jì)劃中的總工期是網(wǎng)絡(luò)圖中的最短路的長度2.緊前工序是前道工序3.后續(xù)工序是緊后工序4.虛工序不需要資源，是用來表達(dá)工序之間的銜接關(guān)系的虛設(shè)活動5.A完工后B才能開始，稱A是B的緊后工序6. 單時(shí)差為零的工序稱為關(guān)鍵工序7.關(guān)

11、鍵路線是由關(guān)鍵工序組成的一條從網(wǎng)絡(luò)圖的起點(diǎn)到終點(diǎn)的有向路8.關(guān)鍵路線一定存在9.關(guān)鍵路線存在且唯一10.計(jì)劃網(wǎng)絡(luò)圖允許有多個(gè)始點(diǎn)和終點(diǎn)11.事件i的最遲時(shí)間TL（i）是指以事件i為完工事件的工序最早可能結(jié)束時(shí)間12.事件i的最早時(shí)間TE（i）是以事件i為開工事件的工序最早可能開工時(shí)間13.工序（i，j）的事件i與j的大小關(guān)系是 i j14.間接成本與工程的完工期成正比15.直接成本與工程的完工期成正比16. 17.18. 19. 20.1 線性規(guī)劃1= 對2= 對3 = 錯(cuò)4= 對5= 錯(cuò)6 = 對7= 對8= 對9 = 對10= 對11= 對12 = 對13= 錯(cuò)14= 錯(cuò)15= 對16=

12、對17= 對18 = 錯(cuò)19= 錯(cuò)20 = 錯(cuò)21= 對22 = 錯(cuò)23= 對24 = 錯(cuò)25 = 錯(cuò)2對偶問題1=對2= 錯(cuò)3 = 對4= 錯(cuò)5 = 錯(cuò)6= 錯(cuò)7 = 錯(cuò)8= 對9= 對10 = 對11 = 對12= 錯(cuò)13 = 錯(cuò)14 = 對15 = 對16 = 錯(cuò)17 = 錯(cuò)18= 對19 = 錯(cuò)20= 錯(cuò)21= 對22 = 錯(cuò)23= 對24= 錯(cuò)25= 錯(cuò)3 整數(shù)規(guī)劃1= 錯(cuò)2 = 錯(cuò)3 = 對4 = 對5 = 對6= 對7 = 錯(cuò)8= 對9 = 對10= 錯(cuò)4 目標(biāo)規(guī)劃1=錯(cuò)2 = 對3 = 對4 = 錯(cuò)5= 對6 = 錯(cuò)7= 錯(cuò)8 = 錯(cuò)9 = 對10= 對5 運(yùn)輸問題1 = 錯(cuò)2

13、 = 對3 = 錯(cuò)4 = 錯(cuò)5= 對6 = 錯(cuò)7 = 對8 = 對9= 對10= 錯(cuò)11 = 對12 = 對13 = 對14 = 對15 = 對16 = 對17 = 錯(cuò)18 = 對19 = 對20 = 錯(cuò)6 網(wǎng)絡(luò)模型1 = 錯(cuò)2 = 錯(cuò)3 = 對4 = 對5 = 對6 = 錯(cuò)7 = 對8 = 錯(cuò)9 = 對10 = 錯(cuò)11 = 對12 = 錯(cuò)13 = 對14 = 對15 = 對16 = 錯(cuò)17 = 錯(cuò)18 = 錯(cuò)19 = 錯(cuò)20 = 錯(cuò)7 網(wǎng)絡(luò)計(jì)劃1 = 錯(cuò) 2 = 對3 = 錯(cuò)4 = 對5= 錯(cuò)6 = 錯(cuò)7 = 對8 = 對9= 錯(cuò)10 = 錯(cuò)11 = 錯(cuò)12= 對12= 對14 = 對15

14、= 錯(cuò)16 = 錯(cuò)17 = 對18 = 對19 = 錯(cuò)20 = 對運(yùn)籌學(xué)模擬試題及參考答案一、判斷題(在下列各題中，你認(rèn)為題中描述的內(nèi)容為正確者，在題尾括號內(nèi)寫“”，錯(cuò)誤者寫“”。) 1. 圖解法提供了求解線性規(guī)劃問題的通用方法。( ) 2. 用單純形法求解一般線性規(guī)劃時(shí)，當(dāng)目標(biāo)函數(shù)求最小值時(shí)，若所有的檢驗(yàn)數(shù)Cj-Zj0，則問題達(dá)到最優(yōu)。( ) 3. 在單純形表中，基變量對應(yīng)的系數(shù)矩陣往往為單位矩陣。( ) 4. 滿足線性規(guī)劃問題所有約束條件的解稱為基本可行解。( ) 5. 在線性規(guī)劃問題的求解過程中，基變量和非基變量的個(gè)數(shù)是固定的。( ) 6. 對偶問題的目標(biāo)函數(shù)總是與原問題目標(biāo)函數(shù)相等。(

15、 ) 7. 原問題與對偶問題是一一對應(yīng)的。( ) 8. 運(yùn)輸問題的可行解中基變量的個(gè)數(shù)一定遵循mn1的規(guī)則。( ) 9. 指派問題的解中基變量的個(gè)數(shù)為mn。( ) 10. 網(wǎng)絡(luò)最短路徑是指從網(wǎng)絡(luò)起點(diǎn)至終點(diǎn)的一條權(quán)和最小的路線。( ) 11. 網(wǎng)絡(luò)最大流量是網(wǎng)絡(luò)起點(diǎn)至終點(diǎn)的一條增流鏈上的最大流量。( ) 12. 工程計(jì)劃網(wǎng)絡(luò)中的關(guān)鍵路線上事項(xiàng)的最早時(shí)間和最遲時(shí)間往往不相等。( ) 13. 在確定性存貯模型中不許缺貨的條件下，當(dāng)費(fèi)用項(xiàng)目相同時(shí)，生產(chǎn)模型的間隔時(shí)間比訂購模型的間隔時(shí)間長。( ) 14. 單目標(biāo)決策時(shí)，用不同方法確定的最佳方案往往是一致的。( ) 15. 動態(tài)規(guī)劃中運(yùn)用圖解法的順推方法

16、和網(wǎng)絡(luò)最短路徑的標(biāo)號法上是一致的。( )二、簡述題 1. 用圖解法說明線性規(guī)劃問題單純形法的解題思想。 2. 運(yùn)輸問題是特殊的線性規(guī)劃問題，但為什么不用單純形法求解。 3. 建立動態(tài)規(guī)劃模型時(shí)，應(yīng)定義狀態(tài)變量，請說明狀態(tài)變量的特點(diǎn)。三、填空題 1. 圖的組成要素 ； 。 2. 求最小樹的方法有 、 。 3. 線性規(guī)劃解的情形有 、 、 、 。 4. 求解指派問題的方法是 。 5. 按決策環(huán)境分類，將決策問題分為 、 、 。 6. 樹連通，但不存在 。四、下列表是線性規(guī)劃單純形表（求Zmax），請根據(jù)單純形法原理和算法。1. 計(jì)算該規(guī)劃的檢驗(yàn)數(shù)Cj32000CixBx1x2x3x4x53x131

17、0-102x340111/20z j33.52-20c jz j 2. 計(jì)算對偶問題的目標(biāo)函數(shù)值3. 確定上表中輸入，輸出變量五、已知一個(gè)線性規(guī)劃原問題如下，請寫出對應(yīng)的對偶模型 六、下圖為動態(tài)規(guī)劃的一個(gè)圖示模型，邊上的數(shù)字為兩點(diǎn)間的距離，請用逆推法求出S至F點(diǎn)的最短路徑及最短路長。B110710611A110C18B2125514FS66137C210A29B3七、自己選用適當(dāng)?shù)姆椒?，對下圖求最小(生成)樹。V1233523356V3V2V4V5V6八、用標(biāo)號法求下列網(wǎng)絡(luò)V1V7的最短路徑及路長。V1V7V5V6V4V3V2543531761731九、下圖是某一工程施工網(wǎng)絡(luò)圖(統(tǒng)籌圖)，圖中

18、邊上的數(shù)字為工序時(shí)間(天)，請求出各事項(xiàng)的最早時(shí)間和最遲時(shí)間，求出關(guān)鍵路線，確定計(jì)劃工期。23145651249105094十、某企業(yè)生產(chǎn)三種產(chǎn)品A1 、A2、A3。每種產(chǎn)品在銷售時(shí)可能出現(xiàn)銷路好(S1)，銷路一般(S2)和銷路差(S3)三種狀態(tài)，每種產(chǎn)品在不同銷售狀態(tài)的獲利情況(效益值)如表1所示，請按樂觀法則進(jìn)行決策，選取生產(chǎn)哪種產(chǎn)品最為合適。狀態(tài)效益值產(chǎn)品S1S2S3A13010-6A220129A3151312(表1)十一、已知運(yùn)輸問題的運(yùn)價(jià)表和發(fā)量和收量如表2所示，請用最小元素法求出運(yùn)輸問題的一組可解釋。B1B2B3B4A1291279A213524A31042653546(表2)十

19、二、下列表3是一個(gè)指派問題的效率表(工作時(shí)間表)，其中A i為工作人員(i=1, 2, 3, 4)、Bj為工作項(xiàng)目(j=1, 2, 3, 4)，請作工作安排，使總的工作時(shí)間最小。B1B2B3B4A14174A22235A35643A46324參考答案一、判斷題(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14) (15) 二、簡述題1、在可行域內(nèi)先確定一個(gè)基本可行解，然后通過迭代計(jì)算，逐步使目標(biāo)函數(shù)增大（求Zmax），求出新解，計(jì)算出方案機(jī)會成本后，得出相應(yīng)檢驗(yàn)數(shù)，當(dāng)所有的CjZj0時(shí)即得最優(yōu)解。2、運(yùn)輸問題可以用單純形求解，

20、但由于虛設(shè)的變量多，運(yùn)算復(fù)雜，十分不合算，所以不用單純形法求解，而用簡單的表上作業(yè)法求解。3、由于動態(tài)規(guī)劃的求解過程是一個(gè)多段決定過程，其狀態(tài)變量必須滿足無后效性和可知性的特征要求。三、填空題1.樹2.破圈法和避圈法3.可行解、退化解、無界解、多重解4.匈牙利法5.確定性決策，不確定性決策，風(fēng)險(xiǎn)性決策。6.圈。四.cj320000CiX0bX1X2X3X4X5X6(3)X13101/2-101/2(2)X240111/2-10Zj327/2-2-23/2CjZj00(-7/2)(2)2-3/21.2. Smin=153. X4輸入，Xi輸出。五、Zmax=-7y1+16y2B1SA2710B39C213FC1107A11051112149B28610568(32