運(yùn)籌學(xué)總復(fù)習(xí)題

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

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

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

4、中的基變量非負(fù)，非基變量為零  B.X中的基變量非零，非基變量為零    C. X不是基本解    D.X不一定滿足約束條件 13.下例錯(cuò)誤的說(shuō)法是 (C)A.標(biāo)準(zhǔn)型的目標(biāo)函數(shù)是求最大值 B.標(biāo)準(zhǔn)型的目標(biāo)函數(shù)是求最小值C.標(biāo)準(zhǔn)型的常數(shù)項(xiàng)非正D.標(biāo)準(zhǔn)型的變量一定要非負(fù)14.為什么單純形法迭代的每一個(gè)解都是可行解？答：因?yàn)樽裱讼铝幸?guī)則 (A)    A.按最小比值規(guī)則選擇出基變量 B.先進(jìn)基后出基規(guī)則   C.標(biāo)準(zhǔn)型要求變量非負(fù)規(guī)則 D.按檢驗(yàn)數(shù)最大的變量進(jìn)基規(guī)則15

5、.線性規(guī)劃標(biāo)準(zhǔn)型的系數(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.下例錯(cuò)誤的結(jié)論是 (D)  A.檢驗(yàn)數(shù)是用來(lái)檢驗(yàn)可行解是否是最優(yōu)解的數(shù)   B.檢驗(yàn)數(shù)是目標(biāo)函數(shù)用非基變量表達(dá)的系數(shù)  C.不同檢驗(yàn)數(shù)的定義其檢驗(yàn)標(biāo)準(zhǔn)也不同   

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

7、(D)A. 原問(wèn)題有最優(yōu)解，對(duì)偶問(wèn)題可能沒(méi)有最優(yōu)解   B. 原問(wèn)題與對(duì)偶問(wèn)題可能都沒(méi)有最優(yōu)解C.可能一個(gè)問(wèn)題有最優(yōu)解，另一個(gè)問(wèn)題具有無(wú)界解       D.原問(wèn)題與對(duì)偶問(wèn)題都有最優(yōu)解20.某個(gè)常數(shù)bi波動(dòng)時(shí)，最優(yōu)表中引起變化的有 (A)  A.B1b       B.      C.B1      D.B1N21.當(dāng)基變量xi

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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