運(yùn)籌學(xué)自測題(含答案)

1、運(yùn)籌學(xué)復(fù)習(xí)題（A）一、單項(xiàng)選擇（將唯一正確答案前面的字母填入題后的括號里。正確得 2 分，選錯、多選或不選得0 分。共30 分）1、在線性規(guī)劃模型中，沒有非負(fù)約束的變量稱為 （C ）A 多余變量 B 松弛變量 C 自由變量 D 人工變量2、約束條件為AX=b，X0 的線性規(guī)劃問題的可行解集是 （B ）A 補(bǔ)集 B 凸集 C 交集 D 凹集3、線性規(guī)劃問題若有最優(yōu)解，則一定可以在可行域的 （C ）上達(dá)到。A 內(nèi)點(diǎn) B 外點(diǎn) C 極點(diǎn) D 幾何點(diǎn)4、對偶問題的對偶是 （D ）A 基本問題 B 解的問題 C 其它問題 D 原問題5、若原問題是一標(biāo)準(zhǔn)型，則對偶問題的最優(yōu)解值就等于原問題最優(yōu)表中松弛變量

2、的 （C ）A 值 B 個數(shù) C 機(jī)會費(fèi)用 D 檢驗(yàn)數(shù)6、若運(yùn)輸問題已求得最優(yōu)解，此時(shí)所求出的檢驗(yàn)數(shù)一定是全部 （ A）A 大于或等于零 B 大于零 C 小于零 D 小于或等于零7、設(shè)V 是一個有n 個頂點(diǎn)的非空集合，V=v1，v2，vn，E 是一個有m條邊的集合，E=e1，e2，em，E 中任意一條邊e 是V 的一個無序元素對u，v，（uv），則稱V 和E 這兩個集合組成了一個 （D ）A 有向樹 B 有向圖 C 完備圖 D 無向圖8、若開鏈Q(jìng) 中頂點(diǎn)都不相同，則稱Q 為 （B ）A 基本鏈 B 初等鏈 C 簡單鏈 D 飽和鏈9、若圖G 中沒有平行邊，則稱圖G 為 （A ）A 簡單圖 B 完

3、備圖 C 基本圖 D 歐拉圖11、若Q 為f 飽和鏈，則鏈中至少有一條后向邊為f （B ）A 正邊 B 零邊 C 鄰邊 D 對邊12、若f 是G 的一個流，K 為G 的一個割，且Valf=CapK，則K 一定是 （A ）A 最小割 B 最大割 C 最小流 D 最大流13、對max 型整數(shù)規(guī)劃，若最優(yōu)非整數(shù)解對應(yīng)的目標(biāo)函數(shù)值為Zc，最優(yōu)整數(shù)解對應(yīng)的目標(biāo)值為Zd，那么一定有 (D)A Zc Zd B Zc =Zd C Zc Zd D Zc Zd14、若原問題中xI 為自由變量，那么對偶問題中的第i 個約束一定為 （ A）A 等式約束 B “”型約束 C “”約束 D 無法確定15、若f*為滿足下列

4、條件的流：Valf*=maxValf |f 為G 的一個流，則稱f*為G的 （C ）A 最小值 B 最大值 C 最大流 D 最小流二、多項(xiàng)選擇題（每題至少有一個答案是正確的。選對得2 分；多選、少選或不選得0 分。共10 分）1、就課本范圍內(nèi)，解有“”型約束方程線性規(guī)劃問題的方法有 （ABE ）A 大M 法 B 兩階段法 C 標(biāo)號法 D 統(tǒng)籌法 E 對偶單純型法2、線性規(guī)劃問題的一般模型中可以出現(xiàn)下面幾種約束 （ ABC）A = B C D E 3、線性規(guī)劃問題的主要特征有 （ABCD ）A 目標(biāo)是線性的 B 約束是線性的 C 求目標(biāo)最大值 D 求目標(biāo)最小值E 非線性4、圖解法求解線性規(guī)劃問題

5、的主要過程有 （ABCE ）A 畫出可行域 B 求出頂點(diǎn)坐標(biāo) C 求最優(yōu)目標(biāo)值D 選基本解 E 選最優(yōu)解5、就課本內(nèi)容，求解0-1 規(guī)劃常用的方法有 （AB ）A 全枚舉法 B 隱枚舉法 C 單純型法 D 位勢法 E 差值法三、簡答題（每道題 5 分。共20 分）1、何謂線性規(guī)劃問題的基礎(chǔ)解？何謂基礎(chǔ)可行解？解：設(shè)B為A中的一個基，令A(yù)x=b，中所有的非基變量（n-m個）為0，得出的解x，稱為是B的基礎(chǔ)解。滿足變量非負(fù)條件（1-6）的基礎(chǔ)解稱為基礎(chǔ)可行解。2、當(dāng)線性規(guī)劃數(shù)學(xué)模型中引用人工變量數(shù)時(shí)，分別采用哪兩種方法迭代出基變量？在何種情況下采用？在實(shí)際問題中有些模型并不含有單位矩陣，為了得到一

6、組基向量和初始基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加入的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解。對于無初始可行解的問題可用大M法求解。方法：化為標(biāo)準(zhǔn)型的同時(shí)，將>以及=的約束條件中，加入人工變量(虛擬變量)，將目標(biāo)函數(shù)中虛擬變量的稀疏設(shè)定為M。但是大M法如在計(jì)算機(jī)上運(yùn)作，M就只能用很大的數(shù)來代替，這樣可能會出現(xiàn)錯誤。此時(shí)需要兩階段法求解。3、什么是線性規(guī)劃問題的靈敏度分析？線性規(guī)劃模型的確定是以 為已知常數(shù)作為基礎(chǔ)的，但在實(shí)際問題中，這些數(shù)據(jù)本身不僅很難準(zhǔn)確得到，而且往往還要受到諸如市場價(jià)格波動，資源供應(yīng)量變化，企業(yè)的技術(shù)改造的

7、因素的影響，因此，很自然地要提出這樣的問題，當(dāng)這些數(shù)據(jù)有一個或多個發(fā)生變化時(shí)，對已找到的最優(yōu)解或最優(yōu)基會產(chǎn)生怎樣的影響；或者說這些數(shù)據(jù)在什么范圍內(nèi)變化，已找到的最優(yōu)解或最優(yōu)基不變；以及在原最優(yōu)解或最優(yōu)基不在是最優(yōu)基時(shí)，如何用最簡單的方法求出新的最優(yōu)解或最優(yōu)基。這就是線性規(guī)劃問題的靈敏度分析。4、什么是整數(shù)規(guī)劃？并寫出其數(shù)學(xué)模型？四、計(jì)算題 （共40 分）1、（6 分）化為標(biāo)準(zhǔn)型解：令Z=- Z，x1=- x1, x3= x4- x5,其中x4 0，x50，則問題的標(biāo)準(zhǔn)形式為：max Z=-2x1+x2-2x4+2x5x1+x2+x4-x5 =4s.t x1+x2-x4+x5+x6=6x1,x2

8、,x4,x5,x602、（10 分）某廠生產(chǎn)甲、乙、丙三種產(chǎn)品，已知有關(guān)數(shù)據(jù)如下表所示：求使該廠獲利最大的生產(chǎn)計(jì)劃。解：設(shè)生產(chǎn)甲、乙、丙三種產(chǎn)品的數(shù)量各為x1，x2，x3，依題意得，max Z=4x1+x2+5x36x1+3x2+5x345s.t 3x1+4x2+5x330x1,x2,x30對該方程求解得， x1=5.3x2=0 x3=5.3所以，最優(yōu)生產(chǎn)計(jì)劃為生產(chǎn)甲、丙各5.3公斤，不生產(chǎn)乙產(chǎn)品。3、（8 分）目標(biāo)函數(shù)為max Z =28x4+x5+2x6，約束形式為“”，且x1，x2，x3 為松弛變量,表中的解代入目標(biāo)函數(shù)中得Z=14，求出ag 的值，并判斷是否最優(yōu)解解：由圖表可知，表中的

9、解為x4=0,x5=0,x6=a。由題意，表中的解帶入目標(biāo)函數(shù)得Z=14,可得max Z =28x0+0+2xa=14解之得，a=7.另由圖表知，最終的基向量為x6,x2,x4.故c=g=0,d=1,e=0.因x1,x2,x3是虛擬變量，故計(jì)算可得b=-6，f=1/3.將所求得的值帶入表格中，驗(yàn)證可得，x4=0,x5=0,x6=7是線性規(guī)劃的最優(yōu)解。4、（7 分）根據(jù)所給的表和一組解判斷是否最優(yōu)解，若不是，請求出最優(yōu)解。（x13, x14, x21, x22, x32, x34）=（5，2，3，1，5，4）解：該解不是最優(yōu)解。下面運(yùn)用最小元素法求解。銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311 5 32 107 A23 1 91 2 84 A3 76 4 103 59 銷