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

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

2、行解四種。10.在求運(yùn)費(fèi)最少的調(diào)度運(yùn)輸問(wèn)題中，如果某一非基變量的檢驗(yàn)數(shù)為4，則說(shuō)明 如果在該空格中增加一個(gè)運(yùn)量運(yùn)費(fèi)將增加4 。11.“如果線性規(guī)劃的原問(wèn)題存在可行解，則其對(duì)偶問(wèn)題一定存在可行解”，這句話對(duì)還是錯(cuò)？ 錯(cuò) 12.如果某一整數(shù)規(guī)劃：MaxZ=X1+X2X1+9/14X251/14-2X1+X21/3X1,X20且均為整數(shù)所對(duì)應(yīng)的線性規(guī)劃（松弛問(wèn)題）的最優(yōu)解為X1=3/2，X2=10/3，MaxZ=6/29，我們現(xiàn)在要對(duì)X1進(jìn)行分枝，應(yīng)該分為 X11 和 X12 。13.在用逆向解法求動(dòng)態(tài)規(guī)劃時(shí)，fk(sk)的含義是： 從第k個(gè)階段到第n個(gè)階段的最優(yōu)解 。14. 假設(shè)某線性規(guī)劃的可行解

3、的集合為D，而其所對(duì)應(yīng)的整數(shù)規(guī)劃的可行解集合為B，那么D和B的關(guān)系為 D 包含 B 15. 已知下表是制訂生產(chǎn)計(jì)劃問(wèn)題的一張LP最優(yōu)單純形表（極大化問(wèn)題，約束條件均為“”型不等式）其中X3,X4,X5為松馳變量。XBbX1X2X3X4X5X4300-213X14/310-1/302/3X210100-1Cj-Zj00-50-23問(wèn)：（1）寫出B-1=(2)對(duì)偶問(wèn)題的最優(yōu)解： Y（5，0，23，0，0）T 16. 線性規(guī)劃問(wèn)題如果有無(wú)窮多最優(yōu)解，則單純形計(jì)算表的終表中必然有_某一個(gè)非基變量的檢驗(yàn)數(shù)為0_；17. 極大化的線性規(guī)劃問(wèn)題為無(wú)界解時(shí)，則對(duì)偶問(wèn)題_ 無(wú)解_；18. 若整數(shù)規(guī)劃的松馳問(wèn)題的

4、最優(yōu)解不符合整數(shù)要求，假設(shè)Xi=bi不符合整數(shù)要求，INT（bi）是不超過(guò)bi的最大整數(shù)，則構(gòu)造兩個(gè)約束條件：XiINT（bi）1 和 XiINT（bi） ，分別將其并入上述松馳問(wèn)題中，形成兩個(gè)分支，即兩個(gè)后繼問(wèn)題。19. 知下表是制訂生產(chǎn)計(jì)劃問(wèn)題的一張LP最優(yōu)單純形表（極大化問(wèn)題，約束條件均為“”型不等式）其中X4,X5,X6為松馳變量。XBbX1X2X3X4X5X6X12110201X32/3001104X510-20116Cj-Zj000-40-9問(wèn)：(1)對(duì)偶問(wèn)題的最優(yōu)解： Y(4,0,9,0,0,0)T （2）寫出B-1= 20. 線性規(guī)劃問(wèn)題MaxZ=CX；AX=b，X0（A為kx

5、l的矩陣，且l>k）的基的最多個(gè)數(shù)為_，基的可行解的最多個(gè)數(shù)為_.21.指派問(wèn)題的最優(yōu)解的性質(zhì)_.22.線性規(guī)劃問(wèn)題的所有可行解構(gòu)成的集合是_,它們有有限個(gè)_,線性規(guī)劃問(wèn)題的每個(gè)基可行解對(duì)應(yīng)可行域的_,若線性規(guī)劃問(wèn)題有最優(yōu)解，必在_得到。23.影子價(jià)格的經(jīng)濟(jì)含義_.在完全市場(chǎng)經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場(chǎng)價(jià)格低于影子價(jià)格時(shí)，企業(yè)應(yīng)_該資源，而當(dāng)某種資源的市場(chǎng)價(jià)格高于影子價(jià)格時(shí)，則企業(yè)應(yīng)_該資源，可見(jiàn)影子價(jià)格對(duì)市場(chǎng)有_作用。24. 運(yùn)輸問(wèn)題的產(chǎn)銷平衡表中有m個(gè)產(chǎn)地n個(gè)銷地，其決策變量的個(gè)數(shù)有_個(gè)，其數(shù)值格有_個(gè)二、不定項(xiàng)選擇題(每小題2分，共6分)1線性規(guī)劃的標(biāo)準(zhǔn)型有特點(diǎn)（ ）。 A、右端

6、項(xiàng)非零； B、目標(biāo)求最大； C、有等式或不等式約束； D、變量均非負(fù)。2一個(gè)線性規(guī)劃問(wèn)題（P）與它的對(duì)偶問(wèn)題（D）有關(guān)系（ ）。A、（P）無(wú)可行解則（D）一定無(wú)可行解；B、（P）、（D）均有可行解則都有最優(yōu)解； C、（P）的約束均為等式，則（D）的所有變量均無(wú)非負(fù)限制； D、若（D）是（P）的對(duì)偶問(wèn)題，則（P）是（D）的對(duì)偶問(wèn)題。3關(guān)于動(dòng)態(tài)規(guī)劃問(wèn)題的下列命題中（ ）是錯(cuò)誤的。 A、動(dòng)態(tài)規(guī)劃階段的順序與求解過(guò)程無(wú)關(guān)；B、狀態(tài)是由決策確定的； C、用逆序法求解動(dòng)態(tài)規(guī)劃問(wèn)題的重要基礎(chǔ)之一是最優(yōu)性原理； D、列表法是求解某些離散變量動(dòng)態(tài)規(guī)劃問(wèn)題的有效方法。4.最早運(yùn)用運(yùn)籌學(xué)理論的是（ ）A 二次世界大

7、戰(zhàn)期間，英國(guó)軍事部門將運(yùn)籌學(xué)運(yùn)用到軍事戰(zhàn)略部署 B 美國(guó)最早將運(yùn)籌學(xué)運(yùn)用到農(nóng)業(yè)和人口規(guī)劃問(wèn)題上C 二次世界大戰(zhàn)期間，英國(guó)政府將運(yùn)籌學(xué)運(yùn)用到政府制定計(jì)劃 D 50年代，運(yùn)籌學(xué)運(yùn)用到研究人口，能源，糧食，第三世界經(jīng)濟(jì)發(fā)展等問(wèn)題上5.下列哪些不是運(yùn)籌學(xué)的研究范圍（ ）A 質(zhì)量控制 B 動(dòng)態(tài)規(guī)劃 C 排隊(duì)論 D 系統(tǒng)設(shè)計(jì)6.對(duì)于線性規(guī)劃問(wèn)題，下列說(shuō)法正確的是（ ）A線性規(guī)劃問(wèn)題可能沒(méi)有可行解 B 在圖解法上，線性規(guī)劃問(wèn)題的可行解區(qū)域都是“凸”區(qū)域C 線性規(guī)劃問(wèn)題如有最優(yōu)解，則最優(yōu)解可在可行解區(qū)域頂點(diǎn)上到達(dá)D 上述說(shuō)法都正確7.下面哪些不是線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式所具備的（ ）A 所有的變量必須是非負(fù)的

8、B 所有的約束條件（變量的非負(fù)約束除外）必須是等式C 添加新變量時(shí)，可以不考慮變量的正負(fù)性 D 求目標(biāo)函數(shù)的最小值8.在求解運(yùn)輸問(wèn)題的過(guò)程中運(yùn)用到下列哪些方法（ ）A 西北角法 B 位勢(shì)法 C 閉回路法 D 以上都是三、判斷題1若某種資源的影子價(jià)格等于k，在其他條件不變的情況下，當(dāng)該種資源增加5個(gè)單位時(shí)，相應(yīng)的目標(biāo)函數(shù)值將增大5k個(gè)單位。 （ ）2如果運(yùn)輸問(wèn)題單位運(yùn)價(jià)表的某一行（或某一列）元素分別加上一個(gè)常數(shù)k，最優(yōu)調(diào)運(yùn)方案將不會(huì)發(fā)生變化。 （ ）3運(yùn)輸問(wèn)題是一種特殊的線性規(guī)劃模型，因而求解結(jié)果也可能出現(xiàn)下列四種情況之一：有唯一最優(yōu)解，有無(wú)窮多最優(yōu)解，無(wú)界解，無(wú)可行解。 （ ）4用割平面法求解

9、純整數(shù)規(guī)劃問(wèn)題時(shí)，要求包括松弛變量在內(nèi)的全部變量必須取整數(shù)值。 （ ）5如圖中某點(diǎn)有若干個(gè)相鄰點(diǎn)，與其距離最遠(yuǎn)的相鄰點(diǎn)為，則邊必不包含在最小支撐樹內(nèi)。 （ ）6.用兩階段法求解線性規(guī)劃時(shí)，如果第一階段的最終表中基變量出現(xiàn)人工變量，則該問(wèn)題一定無(wú)解?！?】7.運(yùn)輸問(wèn)題一定存在有限的最優(yōu)解； 【 】8.如果某種資源的影子價(jià)格等于零，說(shuō)明該種資源一定已經(jīng)用完。 【× 】9.單純形法只適合求解線性規(guī)劃，對(duì)偶單純形法只適合求解對(duì)偶規(guī)劃 【× 】10.分枝定界法求解最大化問(wèn)題中，如果某個(gè)分支的目標(biāo)值少于已經(jīng)得到整數(shù)解的目標(biāo)值，則這一分支將被減去而不再往下求解 。 【 】11.運(yùn)輸問(wèn)題表

10、上作業(yè)法的最優(yōu)判別標(biāo)準(zhǔn)是所有的檢驗(yàn)數(shù)應(yīng)該小于等于0。【× 】12.分枝定界法和割平面法一樣適用于線性規(guī)劃的求解 。 【× 】13.如果原規(guī)劃無(wú)可行解，則其對(duì)偶規(guī)劃也必將無(wú)可行解 【× 】 14.如果原問(wèn)題最優(yōu)解的某個(gè)分量非零，則其對(duì)偶規(guī)劃對(duì)應(yīng)的約束條件一定是等式【 】15.如果某種資源的影子價(jià)格為4，而該資源的市場(chǎng)價(jià)格為3。則應(yīng)買進(jìn)該資源投入生產(chǎn) 【 】16.最優(yōu)表中如果某個(gè)非基變量檢驗(yàn)數(shù)為零，說(shuō)明該問(wèn)題有多重解 【 】17.對(duì)偶單純形法應(yīng)用的前提是對(duì)偶問(wèn)題可行，原規(guī)劃不可行 【 】18.線性規(guī)劃問(wèn)題的解只有唯一最優(yōu)解、無(wú)解和無(wú)界解幾種情況 【× 】19

11、.連通且有n-1條邊的圖一定是樹 【 】20.線性規(guī)劃原問(wèn)題和對(duì)偶問(wèn)題都有可行解，則該線性規(guī)劃問(wèn)題一定有唯一最優(yōu)解 【 】21.運(yùn)輸問(wèn)題表上作業(yè)法的最優(yōu)判別標(biāo)準(zhǔn)是所有的檢驗(yàn)數(shù)應(yīng)該大于等于0?！?】22.用兩階段法求解線性規(guī)劃時(shí)，如果該線性規(guī)劃問(wèn)題存在最優(yōu)解，則第一階段最終表中的基變量中一定不會(huì)出現(xiàn)人工變量。 【 】23.求解整數(shù)規(guī)劃的分枝定界法中的“定界”的目的是加快解的搜索速度?！?】24. 用閉回路法計(jì)算的檢驗(yàn)數(shù)如果等于3，表明沿該閉回路調(diào)整一個(gè)單位運(yùn)量可以節(jié)約3個(gè)單位成本。 【 】四、表中給出的是某極大化問(wèn)題的單純型表，試根據(jù)下面的問(wèn)題，確定表中的值或取值范圍。（1） 計(jì)算a2的值。（2

12、） 計(jì)算目標(biāo)函數(shù)值。（3） 已知初始，求d的值。（4） 該線性規(guī)劃問(wèn)題具有無(wú)界解，則a1, C1的取值范圍是多少？（5） 表中解為無(wú)窮多最優(yōu)解之一，則表中C1等于多少？（6） 寫出對(duì)偶規(guī)劃的解和第二種資源的影子價(jià)格。表1213000CBXBx1x2x3x4x5X62X141-5002a23X310-710100X4d 0a10104j0C100-4-2 五、考慮下列線性規(guī)劃：其最優(yōu)單純形表為：0620-11-25411101-Z-20-20-40-51、寫出此線性規(guī)劃的最優(yōu)解、最優(yōu)值；2、求線性規(guī)劃的對(duì)偶問(wèn)題的最優(yōu)解；3、試求在什么范圍內(nèi)，此線性規(guī)劃的最優(yōu)解不變；4、若變?yōu)?，最優(yōu)解及最優(yōu)值是

13、什么？ 例：設(shè)線性規(guī)劃 求：1.最優(yōu)解; 2.確定的范圍,使最優(yōu)解不變; 取,求最優(yōu)解; 3.確定的范圍,使最優(yōu)基不變, 取求最優(yōu)解; 4.引入求最優(yōu)解;解 1.由單純形方法得即,原問(wèn)題的最優(yōu)解為2.因?yàn)榉腔兞?故當(dāng)時(shí),即時(shí), 最優(yōu)解不變; 為基變量,由公式,當(dāng)最優(yōu)解不變, 即時(shí),最優(yōu)解不變.現(xiàn)對(duì)最優(yōu)解改變,此時(shí)原最優(yōu)表為即相應(yīng)的最優(yōu)解為3.此時(shí)得最優(yōu)基不變.即最優(yōu)基不變.當(dāng)最優(yōu)解改變,此時(shí)此時(shí)最優(yōu)表為即最優(yōu)解為4.此時(shí)故最優(yōu)解改變.相應(yīng)的最優(yōu)表為六、下述線性規(guī)劃問(wèn)題 ：以為對(duì)偶變量寫出其對(duì)偶問(wèn)題。 七、某公司下屬的2個(gè)分廠A1、A2生產(chǎn)質(zhì)量相同的工藝品，要運(yùn)輸?shù)紹1、B2、B3，3個(gè)銷售點(diǎn)

14、，分廠產(chǎn)量、銷售點(diǎn)銷量、單位物品的運(yùn)費(fèi)數(shù)據(jù)如下表：B1B2B3產(chǎn)量A123112025A218161725銷量201020用伏格爾法給出近似最優(yōu)解。七、有甲、乙、丙、丁四個(gè)人，要分別指派他們完成A、B、C、D不同的工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表所示：ABCD甲791012乙13121517丙15161415丁11121516問(wèn)：應(yīng)該如何指派，才能使總的消耗時(shí)間為最少？八、某公司生產(chǎn)三種產(chǎn)品，各產(chǎn)品的重量和利潤(rùn)關(guān)系如下：產(chǎn)品重量（t）456利潤(rùn)（元）81113現(xiàn)將三種產(chǎn)品運(yùn)往市場(chǎng)出售，運(yùn)輸能力為總重量不超過(guò)10t，如何安排運(yùn)輸使總利潤(rùn)最大。試建立此問(wèn)題的動(dòng)態(tài)規(guī)劃模型（只建模，不求解）。九、某旅游者要從A地出發(fā)到終點(diǎn)F，他事先得到的路線圖如下：F437351257962