運籌學期末復習題

1、運籌學期末考試試卷（A）學院班級學號題號一二三四五六七八九總分得分、填空題以下是關(guān)于目標函數(shù)求最大值的單純行表的一些結(jié)論，請根據(jù)所表述的意思判斷解的情況：1 .所有的檢驗數(shù)非正，這時的解是。2 .有一個正檢驗數(shù)所對應的列系數(shù)均非正，這時線性規(guī)劃的解。3 .非基變量檢驗數(shù)中有一個為零時，線性規(guī)劃的解。4 .在兩階段法中，如果第一階段的最優(yōu)表中的基變量中有人工變量，則該線性規(guī)劃。6 .基變量取值為負時的解為o7 .最優(yōu)表中的非基變量檢驗數(shù)的相反數(shù)就是。8 .已知一個線性規(guī)劃兩個最優(yōu)解是：3,2，和5,9，請寫出其他解：9 .線性規(guī)劃的解有唯一最優(yōu)解、無窮多最優(yōu)解、無界解和無可行解四種。10 .在求

2、運費最少的調(diào)度運輸問題中，如果某一非基變量的檢驗數(shù)為4,則說明如果在該空格中增加一個運量運費將增加4。11 .“如果線性規(guī)劃的原問題存在可行解，則其對偶問題一定存在可行解”，這句話對還是錯？_Jt12 .如果某一整數(shù)規(guī)劃：MaxZ=)+為X+9/14X2051/14-2Xi+%01/3Xi,X20且均為整數(shù)所對應的線性規(guī)劃松弛問題的最優(yōu)解為X=3/2,%=10/3,MaxZ=6/29,我們現(xiàn)在要對Xi進行分枝，應該分為X101和X1)2。13 .在用逆向解法求動態(tài)規(guī)劃時，fk(sk)的含義是：從第k個階段到第n個階段的最優(yōu)解。14 .假設某線性規(guī)劃的可行解的集合為D,而其所對應的整數(shù)規(guī)劃的可行

3、解集合為B,那么D和B的關(guān)系為D包含B15 .已知下表是制訂生產(chǎn)計劃問題的一張LP最優(yōu)單純形表極大化問題，約束條件均為Y型不等式其中X3,X4,X5為松馳變量。XbbXX>X3X4X5X41300：-21r3X14/310-1/302/3X21101100r-1C-Zj00-50-23213問：1寫出B-1=1/3,02/3001對偶問題的最優(yōu)解：工=5,0,23,0,0T16 .線性規(guī)劃問題如果有無窮多最優(yōu)解，則單純形計算表的終表中必然有_果一個非基變量的檢驗數(shù)為0;17 .極大化的線性規(guī)劃問題為無界解時，則對偶問題_無解;18 .假設整數(shù)規(guī)劃的松馳問題的最優(yōu)解不符合整數(shù)要求，假設X=

4、b不符合整數(shù)要求，INTbi是不超過bi的最大整數(shù)，則構(gòu)造兩個約束條件：X三INTbi+1和Xi<INTbi,分別將其并入上述松馳問題中，形成兩個分支，即兩個后繼問題。19 .知下表是制訂生產(chǎn)計劃問題的一張LP最優(yōu)單純形表極大化問題，約束條件均為型不等式其中X4,X5,X6為松馳變量。XbbXXX3X4X5X6X12110201X32/3001104X5:10r-20116C-Zj000-40-9問：（1）對偶問題的最優(yōu)解：丫=（4,0,9。0,0）2寫出B-1=20110411620 .線性規(guī)劃問題MaxZ=CX;AX=b,X>0A為kxl的矩陣，且l>k的基的最多個數(shù)為，

5、基的可行解白最多個數(shù)為.21 .指派問題的最優(yōu)解的性質(zhì)22 .線性規(guī)劃問題的所有可行解構(gòu)成的集合是，它們有有限個線性規(guī)劃問題的每個基可行解對應可行域的假設線性規(guī)劃問題有最優(yōu)解，必在得到。23 .影子價格的經(jīng)濟含義在完全市場經(jīng)濟的條件下，當某種資源的市場價格低于影子價格時，企業(yè)應該資源，而當某種資源的市場價格高于影子價格時，則企業(yè)應_該資源，可見影子價格對市場有作用。24 .運輸問題的產(chǎn)銷平衡表中有m個產(chǎn)地n個銷地，其決策變量的個數(shù)有個,其數(shù)值格有個二、不定項選擇題（每題2分，共6分）1 .線性規(guī)劃的標準型有特點。A、右端項非零；B、目標求最大；C、有等式或不等式約束；D、變量均非負。2 .一個

6、線性規(guī)劃問題P與它的對偶問題D有關(guān)系，AP無可行解則D一定無可行解；BP、D均有可行解則都有最優(yōu)解；C、P的約束均為等式，則D的所有變量均無非負限制；D、假設D是P的對偶問題，則P是D的對偶問題試卷A共4頁第3頁3關(guān)于動態(tài)規(guī)劃問題的以下命題中是錯誤的。A、動態(tài)規(guī)劃階段的順序與求解過程無關(guān)；B、狀態(tài)是由決策確定的；C、用逆序法求解動態(tài)規(guī)劃問題的重要基礎之一是最優(yōu)性原理；D列表法是求解某些離散變量動態(tài)規(guī)劃問題的有效方法。4. 最早運用運籌學理論的是A二次世界大戰(zhàn)期間，英國軍事部門將運籌學運用到軍事戰(zhàn)略部署B(yǎng)美國最早將運籌學運用到農(nóng)業(yè)和人口規(guī)劃問題上C二次世界大戰(zhàn)期間，英國政府將運籌學運用到政府制定

7、計劃D50年代，運籌學運用到研究人口，能源，糧食，第三世界經(jīng)濟發(fā)展等問題上5. 以下哪些不是運籌學的研究范圍A質(zhì)量控制B動態(tài)規(guī)劃C排隊論D系統(tǒng)設計6. 對于線性規(guī)劃問題，以下說法正確的選項是A線性規(guī)劃問題可能沒有可行解B在圖解法上，線性規(guī)劃問題的可行解區(qū)域都是“凸”區(qū)域C線性規(guī)劃問題如有最優(yōu)解，則最優(yōu)解可在可行解區(qū)域頂點上到達D上述說法都正確7. 下面哪些不是線性規(guī)劃問題的標準形式所具備的A所有的變量必須是非負的B所有的約束條件變量的非負約束除外必須是等式C添加新變量時，可以不考慮變量的正負性D求目標函數(shù)的最小值8. 在求解運輸問題的過程中運用到以下哪些方法A西北角法B位勢法C閉回路法D以上都

8、是三、判斷題1.假設某種資源的影子價格等于k,在其他條件不變的情況下，當該種資源增加5個單位時，相應的目標函數(shù)值將增大5k個單位。2 .如果運輸問題單位運價表的某一行或某一列元素分別加上一個常數(shù)k,最優(yōu)調(diào)運方案將不會發(fā)生變化。3 運輸問題是一種特殊的線性規(guī)劃模型，因而求解結(jié)果也可能出現(xiàn)以下四種情況之一：有唯一最優(yōu)解，有無窮多最優(yōu)解，無界解，無可行解。4 用割平面法求解純整數(shù)規(guī)劃問題時，要求包括松弛變量在內(nèi)的全部變量必須取整數(shù)值。5如圖中某點vi有假設干個相鄰點，與其距離最遠的相鄰點為vj，則邊i,j必不包含在最小支撐樹內(nèi)。6 .用兩階段法求解線性規(guī)劃時，如果第一階段的最終表中基變量出現(xiàn)人工變量

9、，則該問題一定無解?！綱17 .運輸問題一定存在有限的最優(yōu)解；【，】8 .如果某種資源的影子價格等于零，說明該種資源一定已經(jīng)用完?！綳】9 .單純形法只適合求解線性規(guī)劃，對偶單純形法只適合求解對偶規(guī)劃X10 .分枝定界法求解最大化問題中，如果某個分支的目標值少于已經(jīng)得到整數(shù)解的目標值，則這一分支將被減去而不再往下求解?！?，】11 .運輸問題表上作業(yè)法的最優(yōu)判別標準是所有的檢驗數(shù)應該小于等于0?！綳】12 .分枝定界法和割平面法一樣適用于線性規(guī)劃的求解?！綳】13 .如果原規(guī)劃無可行解，則其對偶規(guī)劃也必將無可行解【X114 .如果原問題最優(yōu)解的某個分量非零，則其對偶規(guī)劃對應的約束條件一定是等式I

10、V】4，而該資源的市場價格為3。則應買進該資源投入生產(chǎn)IV】16 .最優(yōu)表中如果某個非基變量檢驗數(shù)為零，說明該問題有多重解【，】17 .對偶單純形法應用的前提是對偶問題可行，原規(guī)劃不可行【V】試卷 A 共4頁第5頁X 18 .線性規(guī)劃問題的解只有唯一最優(yōu)解、無解和無界解幾種情況n-1條邊的圖一定是樹【，】20 .線性規(guī)劃原問題和對偶問題都有可行解，則該線性規(guī)劃問題一定有唯一最優(yōu)解IV】21 .運輸問題表上作業(yè)法的最優(yōu)判別標準是所有的檢驗數(shù)應該大于等于00IV22 .用兩階段法求解線性規(guī)劃時，如果該線性規(guī)劃問題存在最優(yōu)解，則第一階段最終表中的基變量中一定不會出現(xiàn)人工變量?！俊岸ń纭钡哪康氖羌涌旖?/p>

11、的搜索速度?！尽?4.用閉回路法計算的檢驗數(shù)如果等于3,說明沿該閉回路調(diào)整一個單位運量可以節(jié)約3個單位成本?！尽克摹⒈碇薪o出的是某極大化問題的單純型表，試根據(jù)下面的問題，確定表中0r丐，£期上的值或取值范圍。(1)計算a2的值。(2)計算目標函數(shù)值。Pb=il(3)已知9初始，求d的值。(4)該線性規(guī)劃問題具有無界解，則ai,Ci的取值范圍是多少？(5)表中解為無窮多最優(yōu)解之一，則表中Ci等于多少？(6)寫出對偶規(guī)劃的解和第二種資源的影子價格。表1213000CBX5X1X2X3X4X5X62X141-5002a23X310-710100X4d0a10104(Tj0C100-4-2五

12、、考慮以下線性規(guī)劃：maxz3x15x2x34xi2x2&14x1x2x34xj0,j1,2,3其最優(yōu)單純形表為:CBXBbx1X2x3x4x50x4620-11-25又2411101-Z-20-20-40-51、寫出此線性規(guī)劃的最優(yōu)解、最優(yōu)值;2、求線性規(guī)劃的對偶問題的最優(yōu)解；3、試求c2在什么范圍內(nèi)，此線性規(guī)劃的最優(yōu)解不變；4、假設b,14變?yōu)?,最優(yōu)解及最優(yōu)值是什么？例：設線性規(guī)劃maxz10x16x24x3x1x2x3100,10x14x25x3600,2x12x26x3300,xi0,i1,2,3.求：1.最優(yōu)解；G,C2,C3的范圍，使最優(yōu)解不變；取C350，求最優(yōu)解；6試

13、卷A共4頁第13頁b1,b2,b3的范圍，使最優(yōu)基不變,取bi100，求最優(yōu)解；TX7,P71,4,3,C7XX1X2X3X4x5x6c1064000X4111100100X51045010600x62260013001064000311X40104052101210工060X15210x6065011180550210106008求最優(yōu)解55316x2Xix656164即，原問題的最優(yōu)解為Xx3為非基變量，故當c3100200,08&時，即c3X,x2為基變量，由公式，當4C15,20031003100103,z220032200320時，最優(yōu)解不變；3c24,最優(yōu)解不變，即5一,原

14、最優(yōu)表為3x2016x11016x60045 102333x2010x1100x3001251271212161600220035275246117524612546G15,4&10時，最優(yōu)解不變現(xiàn)對c35020,最優(yōu)解改變，此時381336333xx1x2X3x4X5X6c10625000351c200036321人100036320110053232,b2523253123T1752752325即相應的最優(yōu)解為X25zW66320031003100得40n50,200b2400,100b3,60150,400b21000,b3200，最優(yōu)基不變.bi10050,最優(yōu)解改變，此時20

15、06001b此時最優(yōu)表為即最優(yōu)解為X3005323216160X2X1x6X2X1X420060030070031003100X110X26X34X40x5056164532321616070031003100八八8102八32000003333256121616561311505028032590030,150,0T,z900.P7B1P753232x 為 x2 x3c 10 64X4X5X6x70008x20x110x600451 八，20001363211000036320111007cBB1P7c7，2,0486820,故最優(yōu)解改變33310，相應的最優(yōu)表為1102220002333x

16、70x11x001951八，2000136321八八100-00363111/C10010363133201c八260000333六、下述線性規(guī)劃問題：maxz10Xi24x220x320x425x5Xix22x33x45x5192x14x23x32x4x557xj0,j1,2,5以yi,y2為對偶變量寫出其對偶問題。七、某公司下屬的2個分廠Ai、A生產(chǎn)質(zhì)量相同的工藝品，要運輸?shù)紹、8、B3,3個銷售點，分廠產(chǎn)量、銷售點銷量、單位物品的運費數(shù)據(jù)如下表：BB2B3）里A23112025A18161725銷量201020用伏格爾法給出近似最優(yōu)解。七、有甲、乙、丙、丁四個人，要分別指派他們完成ABCD不同的工作，每人做各項工作所消耗的時間如下表所示：ABCD甲791012乙13121517丙15161415丁11121516問：應該如何指派，才能使總的消耗時間為最少？八、某公司生產(chǎn)三種產(chǎn)品，各產(chǎn)品的重量和利潤關(guān)系如下:產(chǎn)品IRm重量