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

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

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

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

5、l的矩陣，且l>k）的基的最多個數(shù)為_，基的可行解的最多個數(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、右端

6、項非零； B、目標求最大； C、有等式或不等式約束； D、變量均非負。2一個線性規(guī)劃問題（P）與它的對偶問題（D）有關(guān)系（ ）。A、（P）無可行解則（D）一定無可行解；B、（P）、（D）均有可行解則都有最優(yōu)解； C、（P）的約束均為等式，則（D）的所有變量均無非負限制； D、若（D）是（P）的對偶問題，則（P）是（D）的對偶問題。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 二次世界大

7、戰(zhàn)期間，英國軍事部門將運籌學運用到軍事戰(zhàn)略部署 B 美國最早將運籌學運用到農(nóng)業(yè)和人口規(guī)劃問題上C 二次世界大戰(zhàn)期間，英國政府將運籌學運用到政府制定計劃 D 50年代，運籌學運用到研究人口，能源，糧食，第三世界經(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 所有的變量必須是非負的

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

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

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

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

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

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

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