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

運(yùn)籌學(xué)自測(cè)題（含答案）運(yùn)籌學(xué)復(fù)習(xí)題（A）□一、單項(xiàng)選擇（將唯一正確答案前面的字母填入題后的括號(hào)里。正確得2分，選錯(cuò)、多選或不選得0分。共30分）1、在線性規(guī)劃模型中，沒有非負(fù)約束的變量稱為（C）A多余變量B松弛變量C自由變量D人工變量2、約束條件為AX=b,X20的線性規(guī)劃問(wèn)題的可行解集是（B）A補(bǔ)集B凸集C交集D凹集3、線性規(guī)劃問(wèn)題若有最優(yōu)解，則一定可以在可行域的（C）上達(dá)到。A內(nèi)點(diǎn)B外點(diǎn)C極點(diǎn)D幾何點(diǎn)4、對(duì)偶問(wèn)題的對(duì)偶是（D）A基本問(wèn)題B解的問(wèn)題C其它問(wèn)題D原問(wèn)題5、若原問(wèn)題是一標(biāo)準(zhǔn)型，則對(duì)偶問(wèn)題的最優(yōu)解值就等于原問(wèn)題最優(yōu)表中松弛變量的（C）A值B個(gè)數(shù)C機(jī)會(huì)費(fèi)用D檢驗(yàn)數(shù)6、若運(yùn)輸問(wèn)題已求得最優(yōu)解，此時(shí)所求出的檢驗(yàn)數(shù)一定是全部（A）A大于或等于零B大于零C小于零D小于或等于零7、設(shè)V是一個(gè)有n個(gè)頂點(diǎn)的非空集合，V={v1,v2,……，vn}，E是一個(gè)有m條邊的集合，E={e1，e2， em}，E中任意一條邊e是V的一個(gè)無(wú)序元素對(duì)［u，v］，（uWv），則稱V和E這兩個(gè)集合組成了一個(gè)（D）A有向樹B有向圖C完備圖D無(wú)向圖8、若開鏈Q(jìng)中頂點(diǎn)都不相同，則稱Q為（B）A基本鏈B初等鏈C簡(jiǎn)單鏈D飽和鏈9、若圖G中沒有平行邊，則稱圖G為（A）A簡(jiǎn)單圖B完備圖C基本圖D歐拉圖11、若Q為f飽和鏈，則鏈中至少有一條后向邊為f（B）A正邊B零邊C鄰邊D對(duì)邊12、若f是G的一個(gè)流，K為G的一個(gè)割，且Valf二CapK，則K一定是（A）A最小割B最大割C最小流D最大流13、對(duì)max型整數(shù)規(guī)劃，若最優(yōu)非整數(shù)解對(duì)應(yīng)的目標(biāo)函數(shù)值為Zc,最優(yōu)整數(shù)解對(duì)應(yīng)的目標(biāo)值為Zd,那么一定有（D）AZceZdBZc=ZdCZc<ZdDZc2Zd口14、若原問(wèn)題中xI為自由變量，那么對(duì)偶問(wèn)題中的第i個(gè)約束一定為(A)A等式約束B“W”型約束C“2”約束D無(wú)法確定口15、若f*為滿足下列條件的流：Valf*=max{Valf|f為G的一個(gè)流}，則稱f*為G的(C)A最小值B最大值C最大流D最小流二、多項(xiàng)選擇題(每題至少有一個(gè)答案是正確的。選對(duì)得2分；多選、少選或不選得0分。共10分)1、就課本范圍內(nèi)，解有“2”型約束方程線性規(guī)劃問(wèn)題的方法有(ABE)A大M法B兩階段法C標(biāo)號(hào)法D統(tǒng)籌法E對(duì)偶單純型法2、線性規(guī)劃問(wèn)題的一般模型中可以出現(xiàn)下面幾種約束(ABC)A=B2C<D??EA口3、線性規(guī)劃問(wèn)題的主要特征有(ABCD)A目標(biāo)是線性的B約束是線性的C求目標(biāo)最大值D求目標(biāo)最小值E非線性4、圖解法求解線性規(guī)劃問(wèn)題的主要過(guò)程有(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位勢(shì)法E差值法三、簡(jiǎn)答題(每道題5分。共20分)1、何謂線性規(guī)劃問(wèn)題的基礎(chǔ)解？何謂基礎(chǔ)可行解？n解：□maxz??cjxj(1?4)j?1?n(1?5)??aijxj?bi,i?1,2,?m?j?1?x?0,j?1,2,?,n(1?6)?j?B?0?B是系數(shù)矩陣A中的m?m階非奇異子矩陣口稱B為線性規(guī)劃問(wèn)題的基。a12?a1m??a11??aa?a?21222m?B???P1,P2,?Pm?????????aam2?amm?m1??Pj(j?1,2,?m)為基向量，xj(j?1,2,?m)為基變量。設(shè)B為A中的一個(gè)基，令A(yù)x=b,中所有的非基變量(n-m個(gè))為0,得出的解x,稱為是B的基礎(chǔ)解。□滿足變量非負(fù)條件(1-6)的基礎(chǔ)解稱為基礎(chǔ)可行解。2、當(dāng)線性規(guī)劃數(shù)學(xué)模型中引用人工變量數(shù)時(shí)，分別采用哪兩種方法迭代出基變量？在何種情況下采用？在實(shí)際問(wèn)題中有些模型并不含有單位矩陣，為了得到一組基向量和初始基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加入的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解?！鯇?duì)于無(wú)初始可行解的問(wèn)題可用大M法求解。方法：化為標(biāo)準(zhǔn)型的同時(shí)，將＞以及二的約束條件中，加入人工變量（虛擬變量），將目標(biāo)函數(shù)中虛擬變量的稀疏設(shè)定為M?！醯谴驧法如在計(jì)算機(jī)上運(yùn)作，M就只能用很大的數(shù)來(lái)代替，這樣可能會(huì)出現(xiàn)錯(cuò)誤。此時(shí)需要兩階段法求解。3、什么是線性規(guī)劃問(wèn)題的靈敏度分析？線性規(guī)劃模型的確定是以仃仃為已知常數(shù)作為基礎(chǔ)的，但在實(shí)際問(wèn)題中，這些數(shù)據(jù)本身不僅很難準(zhǔn)確得到，而且往往還要受到諸如市場(chǎng)價(jià)格波動(dòng)，資源供應(yīng)量變化，企業(yè)的技術(shù)改造的因素的影響，因此，很自然地要提出這樣的問(wèn)題，當(dāng)這些數(shù)據(jù)有一個(gè)或多個(gè)發(fā)生變化時(shí)，對(duì)已找到的最優(yōu)解或最優(yōu)基會(huì)產(chǎn)生怎樣的影響；或者說(shuō)這些數(shù)據(jù)在什么范圍內(nèi)變化，已找到的最優(yōu)解或最優(yōu)基不變；a,b,c以及在原最優(yōu)解或最優(yōu)基不在是最優(yōu)基時(shí)，如何用最簡(jiǎn)單的方法求出新的最優(yōu)解或最優(yōu)基。這就是線性規(guī)劃問(wèn)題的靈敏度分析?！酢酢?、什么是整數(shù)規(guī)劃？并寫出其數(shù)學(xué)模型？□□□四、計(jì)算題（共40分）1、（6分）化為標(biāo)準(zhǔn)型□解：令Z'=-Z，x1'=-x1,x3=x4-x5,其中x420，x520，則問(wèn)題的標(biāo)準(zhǔn)形式為：maxZ’=-2x1’+x2-2x4+2x5x1’+x2+x4-x5 =4s.t．x1’+x2-x4+x5+x6=6x1’，x2,x4,x5,x620口<□2、（10分）某廠生產(chǎn)甲、乙、丙三種產(chǎn)品，已知有關(guān)數(shù)據(jù)如下表所示：□求使該廠獲利最大的生產(chǎn)計(jì)劃。解：設(shè)生產(chǎn)甲、乙、丙三種產(chǎn)品的數(shù)量各為xl,x2,x3,依題意得，口maxZ=4x1+x2+5x36x1+3x2+5x3^450s.t. 3x1+4x2+5x3^300x1,x2,x3200對(duì)該方程求解得， x1=5.3x2=0x3=5.3所以，最優(yōu)生產(chǎn)計(jì)劃為生產(chǎn)甲、丙各5.3公斤，不生產(chǎn)乙產(chǎn)品。3、（8分）目標(biāo)函數(shù)為maxZ=28x4+x5+2x6,約束形式為“W”，且x1,x2,x3為松弛變量，表中的解代入目標(biāo)函數(shù)中得Z=14,求出a~g的值，并判斷是否最優(yōu)解口□解：由圖表可知，表中的解為x4=0,x5=0,x6=a。由題意，表中的解帶入目標(biāo)函數(shù)得Z=14，可得maxZ=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)解，若不是，請(qǐng)求出最優(yōu)解。（x13,x14,x21,x22,x32,x34）=（5，2，3，1，5，4）解：該解不是最優(yōu)解。下面運(yùn)用最小元素法求解。銷地B1B2B3產(chǎn)地A1A23115 3