運籌學總復習題

1、線性規(guī)劃部分1. 試述線性規(guī)劃問題的可行解、基礎解、基可行解、最優(yōu)解的概念及其相互關(guān)系2. 對偶問題和對偶變量(即影子價值)的經(jīng)濟意義是什么? 什么是資源的影子價格?它與相應的市場價格有什么區(qū)別?3. 如何根據(jù)原問題和對偶問題之間的對應關(guān)系,找出兩個問題變量之間、解及檢驗數(shù)之間的關(guān)系?4. 試述整數(shù)規(guī)劃分枝定界法的思路5.線性規(guī)劃具有無界解是指 (C) A.可行解集合無界    B.有相同的最小比值  C.存在某個檢驗數(shù)D.最優(yōu)表中所有非基變量的檢驗數(shù)非零6.線性規(guī)劃具有唯一最優(yōu)解是指  (A)  A.最優(yōu)表中非基變量檢驗數(shù)全部非零 

2、  B.不加入人工變量就可進行單純形法計算  C.最優(yōu)表中存在非基變量的檢驗數(shù)為零 D.可行解集合有界7.線性規(guī)劃具有多重最優(yōu)解是指 (B)    A.目標函數(shù)系數(shù)與某約束系數(shù)對應成比例  B.最優(yōu)表中存在非基變量的檢驗數(shù)為零  C.可行解集合無界    D.基變量全部大于零8.線性規(guī)劃的退化基可行解是指 (B)  A.基可行解中存在為零的非基變量  B.基可行解中存在為零的基變量  C.非基變量的檢驗數(shù)為零 D.所有基變量不等于零 9.線性規(guī)劃無可行解是指 (C)

3、  A.第一階段最優(yōu)目標函數(shù)值等于零   B.進基列系數(shù)非正   C.用大M法求解時,最優(yōu)解中還有非零的人工變量    D.有兩個相同的最小比值10.若線性規(guī)劃不加入人工變量就可以進行單純形法計算 (B) A.一定有最優(yōu)解  B.一定有可行解  C.可能無可行解  D.全部約束是小于等于的形式11.線性規(guī)劃可行域的頂點一定是 (A)  A.可行解  B.非基本解 C.非可行 D.是最優(yōu)解12.X是線性規(guī)劃的基本可行解則有 (A) A.X

4、中的基變量非負，非基變量為零  B.X中的基變量非零，非基變量為零    C. X不是基本解    D.X不一定滿足約束條件 13.下例錯誤的說法是 (C)A.標準型的目標函數(shù)是求最大值 B.標準型的目標函數(shù)是求最小值C.標準型的常數(shù)項非正D.標準型的變量一定要非負14.為什么單純形法迭代的每一個解都是可行解？答：因為遵循了下列規(guī)則 (A)    A.按最小比值規(guī)則選擇出基變量 B.先進基后出基規(guī)則   C.標準型要求變量非負規(guī)則 D.按檢驗數(shù)最大的變量進基規(guī)則15

5、.線性規(guī)劃標準型的系數(shù)矩陣Am×n，要求 (B)    A.秩(A)=m并且m<n    B.秩(A)=m并且m<=n    C.秩(A)=m并且m=n   D.秩(A)=n并且n<m 16.下例錯誤的結(jié)論是 (D)  A.檢驗數(shù)是用來檢驗可行解是否是最優(yōu)解的數(shù)   B.檢驗數(shù)是目標函數(shù)用非基變量表達的系數(shù)  C.不同檢驗數(shù)的定義其檢驗標準也不同   

6、;D.檢驗數(shù)就是目標函數(shù)的系數(shù) 17.對偶單純形法的最小比值規(guī)劃則是為了保證 (B)   A.使原問題保持可行   B.使對偶問題保持可行 C.逐步消除原問題不可行性  D.逐步消除對偶問題不可行性18.互為對偶的兩個線性規(guī)劃問題的解存在關(guān)系 (A)A.一個問題具有無界解，另一問題無可行解   B原問題無可行解，對偶問題也無可行解C.若最優(yōu)解存在，則最優(yōu)解相同        D.一個問題無可行解，則另一個問題具有無界解19.原問題與對偶問題都有可行解，則

7、(D)A. 原問題有最優(yōu)解，對偶問題可能沒有最優(yōu)解   B. 原問題與對偶問題可能都沒有最優(yōu)解C.可能一個問題有最優(yōu)解，另一個問題具有無界解       D.原問題與對偶問題都有最優(yōu)解20.某個常數(shù)bi波動時，最優(yōu)表中引起變化的有 (A)  A.B1b       B.      C.B1      D.B1N21.當基變量xi

8、的系數(shù)ci波動時，最優(yōu)表中引起變化的有 (B)A.  最優(yōu)基B B.所有非基變量的檢驗數(shù)  C.第i列的系數(shù) D.基變量XB 22.當非基變量xj的系數(shù)cj波動時，最優(yōu)表中引起變化的有 (C )    A.00單純形乘子 B.目標值 C.非基變量的檢驗數(shù)  D. 常數(shù)項23.若線性規(guī)劃問題的最優(yōu)解同時在可行解域的兩個頂點處達到，那么該線性規(guī)劃問題最優(yōu)解為（ C ）A.兩個 B.零個 C.無窮多個 D.有限多個24.原問題與對偶問題的最優(yōu)（B ）相同。 A解 B目標值 C 解結(jié)構(gòu) D解的分量個數(shù)25.若原問題中為自由變量，那么對偶問題中

9、的第個約束一定為 （ A ） A等式約束 B“”型約束 C“”約束 D無法確定      26.線性規(guī)劃中，滿足非負條件的基本解，稱為_基本可行解_，對應的基稱為_可行基。27.線性規(guī)劃的目標函數(shù)的系數(shù)是其對偶問題的_最右邊_；而若線性規(guī)劃為最大化問題，則對偶問題為_最小化_。28.考慮線性規(guī)劃問題：（a）：寫出其對偶問題；（b）：用單純形方法求解原問題；（c）：用對偶單純形方法求解其對偶問題；（d）：比較（b）（c）計算結(jié)果。29.試述單純形法的計算步驟，并說明如何在單純形表上判斷問題是具有唯一最優(yōu)解、無窮多最優(yōu)解和無有限最優(yōu)解。30.設線性規(guī)劃的約束

10、條件為 則基本可行解為（C）    A(0, 0, 4, 3)        B(3, 4, 0, 0)    C(2, 0, 1, 0)        D(3, 0, 4, 0)31互為對偶的兩個線性規(guī)劃 及, 對任意可行解X 和Y，存在關(guān)系（D）     AZ > W       

11、0;   BZ = W     CZW            DZW32.互為對偶的兩個線性規(guī)劃問題的解存在關(guān)系（B）    A原問題無可行解，對偶問題也無可行解    B對偶問題有可行解，原問題可能無可行解    C若最優(yōu)解存在，則最優(yōu)解相同    D一個問題無可行解，則另一個問題具有無界解33.已知最優(yōu)基 ，CB=

12、（3，6)，則對偶問題的最優(yōu)解是（  3，0  ）34.在資源優(yōu)化的線性規(guī)劃問題中，某資源有剩余，則該資源影子價格等于（  0 ）35.將目標函數(shù)轉(zhuǎn)化為求極小值是（-Z=-x1+5x2）36.原問題有5個變量3個約束，其對偶問題(    A)     A有3個變量5個約束        B有5個變量3個約束    C有5個變量5個約束    

13、60;    D有3個變量3個約束37.互為對偶的兩個問題存在關(guān)系(   D )    A 原問題無可行解，對偶問題也無可行解    B 對偶問題有可行解，原問題也有可行解    C 原問題有最優(yōu)解解，對偶問題可能沒有最優(yōu)解    D 原問題無界解，對偶問題無可行解38.對偶變量的最優(yōu)解就是（    影子）價格運輸問題部分1.有6個產(chǎn)地7個銷地的平衡運輸問題模型的對偶模型具有特征 （D）

14、  A 有12個變量 B 有42個約束 C. 有13個約束 D有13個基變量2.有5個產(chǎn)地4個銷地的平衡運輸問題 （D） m+n-1    A.有9個變量 B.有9個基變量 C. 有20個約束 D有8個基變量3.m+n1個變量構(gòu)成一組基變量的充要條件是 (B) A.m+n1個變量恰好構(gòu)成一個閉回路  B.m+n1個變量不包含任何閉回路 C.m+n1個變量中部分變量構(gòu)成一個閉回路  D.m+n1個變量對應的系數(shù)列向量線性相關(guān) 4.運輸問題 (A)  A.是線性規(guī)劃問題 B.不是線性規(guī)劃問題

15、60; C.可能存在無可行解  D.可能無最優(yōu)解5.若運輸問題已求得最優(yōu)解，此時所求出的檢驗數(shù)一定是全部（D）  目標函數(shù)最小化問題            A小于或等于零 B大于零 C小于零 D大于或等于零 6.對于m個發(fā)點、n個收點的運輸問題，敘述錯誤的是( D )A該問題的系數(shù)矩陣有m×n列B該問題的系數(shù)矩陣有m+n行C該問題的系數(shù)矩陣的秩必為m+n-1D該問題的最優(yōu)解必唯一5.下列結(jié)論正確的有 （A）A 運輸問題的運價表第r行的每個cij同時加上一個非零常數(shù)k，其最優(yōu)調(diào)運方案不變

16、B 運輸問題的運價表第p列的每個cij同時乘以一個非零常數(shù)k，其最優(yōu)調(diào)運方案不變  C.運輸問題的運價表的所有cij同時乘以一個非零常數(shù)k, 其最優(yōu)調(diào)運方案變化  D不平衡運輸問題不一定存在最優(yōu)解6.在運輸問題模型中，個變量構(gòu)成基變量的充要條件m+n1個變量不包含任何閉回路。7.在求運費最少的調(diào)度運輸問題中，如果某一非基變量的檢驗數(shù)為4，則說明如果在該空格中增加一個運量，運費將增加  4 。8設運輸問題求最大值，則當所有檢驗數(shù)（   小于等于0 ）時得到最優(yōu)解。9.用表上作業(yè)法求解下表中的運輸問題： 目標規(guī)劃1.要求不超過第一目標值、

17、恰好完成第二目標值，目標函數(shù)是 （B） A.         B.  C.   D.2.目標函數(shù)的含義是 （A）A. 首先第一和第二目標同時不低于目標值，然后第三目標不低于目標值  B.第一、第二和第三目標同時不超過目標值  C.第一和第二目標恰好達到目標值，第三目標不超過目標值    D.首先第一和第二目標同時不超過目標值，然后第三目標不超過目標值3.下列線性規(guī)劃與目標規(guī)劃之間錯誤的關(guān)系是 （B） A.線

18、性規(guī)劃的目標函數(shù)由決策變量構(gòu)成，目標規(guī)劃的目標函數(shù)由偏差變量構(gòu)成 B.線性規(guī)劃模型不包含目標約束，目標規(guī)劃模型不包含系統(tǒng)約束C.線性規(guī)劃求最優(yōu)解，目標規(guī)劃求滿意解D.線性規(guī)劃模型只有系統(tǒng)約束，目標規(guī)劃模型可以有系統(tǒng)約束和目標約束  E.線性規(guī)劃求最大值或最小值，目標規(guī)劃只求最小值5.某計算機公司生產(chǎn)A,B,C 3種型號的筆記本電腦。這3種筆記本電腦需要在復雜的裝配線上生產(chǎn),生產(chǎn)一臺A,B,C型號的筆記本電腦分別需要5小時、8小時、12小時。公司裝配線正常的生產(chǎn)時間是每月1 700小時,公司營業(yè)部門估計A,B,C 3種筆記本電腦每臺的利潤分別是1 000元、1 440元、2

19、520元,而公司預測這個月生產(chǎn)的筆記本電腦能夠全部售出。公司經(jīng)理考慮以下目標。第一目標:充分利用正常的生產(chǎn)能力,避免開工不足;第二目標:優(yōu)先滿足老客戶的需求,A,B,C 3種型號的電腦各為50臺、50臺、80臺,同時根據(jù)3種電腦的純利潤分配不同的加權(quán)系數(shù);第三目標:限制裝配線加班時間,最好不超過200小時;第四目標:滿足各種型號電腦的銷售目標,A,B,C 3種型號分別為100臺、120臺、100臺,再根據(jù)3種電腦的純利潤分配不同的加權(quán)系數(shù);第五目標:裝配線加班時間盡可能少。請列出相應的目標規(guī)劃模型,并用LINGO軟件求解。6.已知3個工廠生產(chǎn)的產(chǎn)品供應給4個客戶,各工廠生產(chǎn)量、用戶需求量及從各

20、工廠到用戶的單位產(chǎn)品的運輸費用如表所示。由于總生產(chǎn)量小于總需求量,上級部門經(jīng)研究后,制定了調(diào)配方案的8個目標,并規(guī)定了重要性的次序。表 工廠產(chǎn)量用戶需求量及運費單價單位:元/單位用戶工廠用戶1用戶2用戶3用戶4生產(chǎn)量工廠15267工廠23546工廠34523需求量(單位)200100450250第一目標:用戶4為重要部門,需求量必須全部滿足;第二目標:供應用戶1的產(chǎn)品中,工廠3的產(chǎn)品不少于100個單位;第三目標:每個用戶的滿足率不低于80%;第四目標:應盡量滿足各用戶的需求;第五目標:新方案的總運費不超過原運輸問題(線性規(guī)劃模型)的調(diào)度方案的10%;第六目標:因道路限制,工廠2到用戶4的路線應

21、盡量避免運輸任務;第七目標:用戶1和用戶3的滿足率應盡量保持平衡;第八目標:力求減少總運費。請列出相應的目標規(guī)劃模型,并用LINGO軟件求解。7.已知條件如表所示。 工序產(chǎn)品型號每周可用生產(chǎn)時間(小時)AB(小時/臺)56200(小時/臺)3385利潤(元/臺)310455如果工廠經(jīng)營目標的期望值和優(yōu)先等級如下:P1:每周總利潤不得低于10 000元;P2:因合同要求,A型機每周至少生產(chǎn)15臺,B型機每周至少生產(chǎn)20臺;P3:希望工序的每周生產(chǎn)時間正好為200小時,工序的生產(chǎn)時間最好用足,甚至可適當加班。試建立這個問題的目標規(guī)劃模型,并用LINGO軟件求解。整數(shù)規(guī)劃部分1.下列說法正確的是 （

22、D）A.整數(shù)規(guī)劃問題最優(yōu)值優(yōu)于其相應的線性規(guī)劃問題的最優(yōu)值B.用割平面法求解整數(shù)規(guī)劃問題，構(gòu)造的割平面有可能切去一些不屬于最優(yōu)解的整數(shù)解 C.用分枝定界法求解一個極大化的整數(shù)規(guī)劃時，當?shù)玫蕉嘤谝粋€可行解時，通?？扇稳∑渲幸粋€作為下界，再進行比較剪枝D.分枝定界法在處理整數(shù)規(guī)劃問題時，借用線性規(guī)劃單純形法的基本思想，在求相應的線性模型解的同時，逐步加入對各變量的整數(shù)要求限制，從而把原整數(shù)規(guī)劃問題通過分枝迭代求出最優(yōu)解。 2.分枝定界法中 （B）   a.最大值問題的目標值是各分枝的下界     b.最大值問題的目標值是各分枝的上界

23、60;   c.最小值問題的目標值是各分枝的上界     d.最小值問題的目標值是各分枝的下界    e.以上結(jié)論都不對A.   a,b          B.   b,d       C.   c,d        D.   e3.有4名職工,由于各人的能力不同,每個

24、人做各項工作所用的時間不同,所花費時間如表所示。 單位:分鐘時間任務人員ABCD甲15182124乙19232218丙26171619丁19212317問指派哪個人去完成哪項工作,可使總的消耗時間最少?4.某部門一周中每天需要不同數(shù)目的雇員:周一到周四每天至少需要50人,周五至少需要80人,周六周日每天至少需要90人,現(xiàn)規(guī)定應聘者需連續(xù)工作5天,試確定聘用方案,即周一到周日每天聘用多少人,使在滿足需要的條件下聘用總?cè)藬?shù)最少。5.離散性選址問題。某一城區(qū)設有7個分銷網(wǎng)點,它們之間的交通路線情況如圖 所示。求出各分銷商之間的最短距離如表1所示。表1 各分銷商之間的最短距離矩陣ABCDEFGA035

25、57810B3032457C5305679D5250235E7462013F8573102G10795320(1)現(xiàn)規(guī)劃一座倉庫,覆蓋這7個區(qū)域的需求,試用中心法確定倉庫選址,使得運送路徑最短。(2)如果又已知各區(qū)的每周銷售能力如表2列示,公司希望設立一個倉儲中心,向各區(qū)銷售商發(fā)送產(chǎn)品,試尋求網(wǎng)絡重心,使總運輸成本最低。表2各區(qū)的每周銷售能力區(qū)域ABCDEFG周銷售能力400350450300250350500網(wǎng)絡優(yōu)化部分1.是關(guān)于可行流 f 的一條增廣鏈，則在上有 "D"   A.對一切，有     &

26、#160;    B.對一切，有 C.對一切，有            D.對一切，有  2.下列說法正確的是   A.割集是子圖                         B.割量等于割集中弧的流量之和 

27、0; C.割量大于等于最大流量       D.割量小于等于最大流量 3.下列錯誤的結(jié)論是     A.容量不超過流量      B.流量非負   C.容量非負             D.發(fā)點流出的合流等于流入收點的合流4.下列正確的結(jié)論是   A.最大流等于最大流量    &

28、#160;B.可行流是最大流當且僅當存在發(fā)點到收點的增廣鏈    C.可行流是最大流當且僅當不存在發(fā)點到收點的增廣鏈    D.調(diào)整量等于增廣鏈上點標號的最大值5.下列正確的結(jié)論是    A.最大流量等于最大割量     B.最大流量等于最小割量   C.任意流量不小于最小割量    D.最大流量不小于任意割量6.連通圖G有n個點，其部分樹是T，則有   A.T有n個點n條邊               B.T的長度等于G的每條邊的長度之和    C.T有n個點n1條邊           D.T有n