運(yùn)籌學(xué) 試卷及答案 卷1

課程名稱:課程名稱:運(yùn)籌學(xué)題號(hào)一二三四五六七八九十總分評(píng)卷得分評(píng)卷簽名復(fù)核得分復(fù)核簽名一、單項(xiàng)選擇（每題2分，共20分）1、對(duì)一個(gè)極大化的線性規(guī)劃問題用單純形法求解，若存在某檢驗(yàn)數(shù)，且它所在列的系數(shù)向量，則該線性規(guī)劃問題（）。A．有唯一最優(yōu)解B．有無窮多最優(yōu)解C．為無界解D．無可行解2、若原問題中xj為自由變量，那么對(duì)偶問題中的第j個(gè)約束一定為。A．等式約束B．“≤”型約束C．“≥”約束D．無法確定3、有m個(gè)產(chǎn)地，n個(gè)銷地的產(chǎn)銷平衡的運(yùn)輸問題中，用表上作業(yè)法求解得到時(shí)，表中空格數(shù)是。A．m×nB．m+n－1C．m+nD．m×n－(m+n－1)4、要用最少費(fèi)用建設(shè)一條公路網(wǎng)，將五個(gè)城市連接起來，使它們可以相互到達(dá)，已知建設(shè)費(fèi)用與公路長(zhǎng)度成正比，那么該問題可以看成是。A．最小樹問題求解 B．樹的生成問題求解C．最短路問題求解 D．最大流問題求解5、在用對(duì)偶單純形法解最大化線性規(guī)劃問題時(shí)，每次迭代要求單純形表中（）。A．b列元素不小于零B．檢驗(yàn)數(shù)都大于零C．檢驗(yàn)數(shù)都不小于零D．檢驗(yàn)數(shù)都不大于零6、任何圖中，頂點(diǎn)次數(shù)的總和等于邊數(shù)的（）倍。A．2B．3C．1D．4學(xué)院：專業(yè)：學(xué)號(hào)：姓名：裝訂線7、整數(shù)規(guī)劃問題（）。A．可以用舍入取整法求得最優(yōu)解B．最優(yōu)目標(biāo)函數(shù)值一定優(yōu)于松弛問題最優(yōu)目標(biāo)函數(shù)值C．可以化為0-1型整數(shù)規(guī)劃問題D．一定有有限個(gè)可行解8、如果要使目標(biāo)規(guī)劃實(shí)際實(shí)現(xiàn)值不低于目標(biāo)值，但允許超過目標(biāo)值，則目標(biāo)函數(shù)應(yīng)該采用以下哪個(gè)基本表達(dá)式：（）。A．min{f（d-）}B．min{f（d+）}C．min{f（d++d-）}D．min{f(d--d+)}9、用沃格爾法求解運(yùn)輸問題時(shí)，如果罰數(shù)的值很大時(shí)，應(yīng)盡量按（）運(yùn)價(jià)安排運(yùn)輸。A．最小單位B．最大單位C．最大差D．最小差10、關(guān)于凸集，不正確的描述是（）。A.凸集里面的任意兩個(gè)點(diǎn)的連線上的點(diǎn)仍然在該凸集內(nèi)B.線性規(guī)劃問題的可行域一定是一個(gè)凸集C.若線性規(guī)劃問題的可行域是凸集，則該凸集上的任一個(gè)頂點(diǎn)都可能是最優(yōu)解D.若線性規(guī)劃問題存在最優(yōu)解，則最優(yōu)解一定是可行域的凸集上的某一個(gè)頂點(diǎn)二、判斷題（每題2分，共20分）1、線性規(guī)劃問題的任意一可行解都可以用全部基可行解的線形組合表示。（）2、整數(shù)規(guī)劃問題的可行解集合是它的松弛問題可行解集合的一個(gè)子集，任意兩個(gè)可行解的凸組合不一定滿足整數(shù)約束條件，因而不一定仍為可行解。（）3、目標(biāo)約束是一種軟約束，目標(biāo)約束中決策值和目標(biāo)值之間的差異用偏差變量表示,它并不是目標(biāo)規(guī)劃所特有的概念。（）4、設(shè)T是圖G的最小樹，任取G中的一條不屬于T中的邊e添加到T中，則可以得到一個(gè)圈，并且e是這個(gè)圈中的權(quán)最大的邊。（）5、用位勢(shì)法求檢驗(yàn)數(shù)時(shí)，位勢(shì)不同則求出的檢驗(yàn)數(shù)不一定不同。（）6、當(dāng)原問題為無界解時(shí)，其對(duì)偶問題無可行解，反之，當(dāng)對(duì)偶問題無可行解時(shí)，其原問題具有無界解。（）7、指派問題數(shù)學(xué)模型的形式同運(yùn)輸問題十分相似，也可用表上作業(yè)法求解。（）8、無向連通圖G是歐拉圖，當(dāng)且僅當(dāng)G中只有一個(gè)奇點(diǎn)。（）9、序列5，4，3，2，1可以是某個(gè)簡(jiǎn)單圖的點(diǎn)的次的序列。（）10、用單純形法計(jì)算中，如不按最小比值原則選取換出變量，則在下一個(gè)解中至少有一個(gè)基變量的值為負(fù)。（）三、解答題（注意：1、2、3題為必做題，4、5題為選做題，工商管理1-4班選做第5題，工商管理5、6班選做第4題）1、（20分）已知下列線性規(guī)劃問題（1）用單純形法求解線性規(guī)劃問題。（14分）（2）寫出上述問題的對(duì)偶問題。（6分）2、（16分）給定下列運(yùn)輸問題：（表中數(shù)據(jù)為產(chǎn)地Ai到銷地Bj的單位運(yùn)費(fèi)），求最優(yōu)運(yùn)輸方案。產(chǎn)銷B1B2B3B4產(chǎn)量A1123410A2876520A391011930銷量82212183、（10分）試求下圖的最小生成樹,并計(jì)算該樹的長(zhǎng)度。4、（14分）已知贏得矩陣A如下，請(qǐng)用圖解法求解矩陣對(duì)策。5、（14分）某公司打算在3個(gè)不同地區(qū)設(shè)置4個(gè)銷售點(diǎn)，根據(jù)市場(chǎng)預(yù)測(cè)部門估計(jì)，每月可得利潤(rùn)如下表所示，試問應(yīng)如何在各地區(qū)設(shè)置銷售站，可使每月總利潤(rùn)最大？地區(qū)銷售點(diǎn)01234A016253032B012172022C010141617《運(yùn)籌學(xué)》參考答案及評(píng)分細(xì)則一、單項(xiàng)選擇題（2分/題，共20分）1、C2、A3、D4、A5、D6、A7、D8、A9、A10、B二、判斷題（2分/題，共20分）1、√2、√3、╳4、√5、╳6、╳7、√8、╳9、╳10、√三、解答題1．（1）解：將原問題化為標(biāo)準(zhǔn)形式如下：(2分)Cj→20200θCBXBbx1x2x3x4x50x4102471010/20x511[4]830111/4δj20200（3分）0x49/200[11/2]1-1/29/112x111/4123/401/411/3δj0-41/20-1/2（4分）2x39/110012/11-1/112x147/22120-3/227/22δj0-40-1/11-5/11（3分）此時(shí)，原問題得到最優(yōu)解為X*=(47/22，0，9/11，0，0)T，maxZ＝65/11（2分）（2）.原問題的對(duì)偶問題為：2．解：方法一：（1）用最小元素法求得初始解，并計(jì)算檢驗(yàn)數(shù)如下：B1B2B3B4產(chǎn)量uiA182（0）（2）100A2（4）（2）218203A3（0）2010（-1）308銷量8221218vj1232（初始方案5分，位勢(shì)2分，檢驗(yàn)數(shù)2分）（2）因?yàn)棣?4<0，所以此方案不是最優(yōu)方案，調(diào)整的新方案并計(jì)算新檢驗(yàn)數(shù)：B1B2B3B4產(chǎn)量uiA182（1）（3）100A2（3）（1）128204A3（0）20（1）10308銷量8221218vj1221（新方案3分，位勢(shì)1分，檢驗(yàn)數(shù)1分）因?yàn)樗笑襥j≥0，所以此解為最優(yōu)解，又因?yàn)橛蟹腔兞繖z驗(yàn)數(shù)δ31＝0，所以，該問題有多個(gè)最優(yōu)解。其中一個(gè)最優(yōu)解為：A1-B1：8，A1-B2：2，A2-B3：12，A2-B4：8，A3-B2：20，A3-B4：10；最小運(yùn)費(fèi)z=8×1+2×2+12×6+8×5+20×10+10×9＝414。（2分）方法二：用沃格爾法（方法略），初始解即為最優(yōu)解。（評(píng)分標(biāo)準(zhǔn)：沃格爾法求得初始方案10分，檢驗(yàn)數(shù)4分，結(jié)果2分）V1V2V5V3V6312121V7V43．解：利用破圈法依次去掉邊V2V5，VV1V2V5V3V6312121V7V4（8分）最小樹長(zhǎng)為：3+1+1+2+2+1＝10（2分）753232753232-2xΙΙΙΙΙΙA?4?1?2?3（4分）圖中A點(diǎn)縱坐標(biāo)即為對(duì)策值，令其為V，聯(lián)立過A的三條由?1，?2，?3，確定的直線方程：解得：=1/2，＝5/2所以，局中人Ι的最優(yōu)混合策略為X*＝（1/2，1/2）T（6分）因?yàn)榫种腥甩│┑淖顑?yōu)混合策略只能由?1，?2，?3組成，設(shè)Y*＝（y1*，y2*，y3*，y4*）T因?yàn)镋（x*，1）＝1/2*2+1/2*5）＝7/2>5/2＝V所以y1*＝0又因?yàn)閤1*＝1/2>0，x2*＝1/2>0，根據(jù)定理可得：又因?yàn)閥1*＝0所以解得：y1*＝y(tǒng)4*＝0，y2*＝y(tǒng)3*＝1/2。局中人ΙΙ的最優(yōu)策略為y*＝（0，1/2，1/2，0）T。（4分）5．解：此問題可分為三個(gè)階段，分別在地區(qū)A、B、C設(shè)銷售點(diǎn)，k=1,2,3；決策變量uk：表示在地區(qū)k可設(shè)置的銷售點(diǎn)數(shù)；狀態(tài)變量sk：表示k階段出可在第k到第c個(gè)地區(qū)設(shè)置銷售點(diǎn)的個(gè)數(shù)；狀態(tài)轉(zhuǎn)移方程：sk+1=sk-uk（表示：2分）因?yàn)榇藛栴}為離散確定性多階段決策，所以可用圖表示，見下圖。（圖形：6分）此問題求總利潤(rùn)最大，相當(dāng)于求狀態(tài)s1到狀態(tài)s4的最長(zhǎng)路，采用逆序法標(biāo)號(hào)。（標(biāo)號(hào)：4分）則最長(zhǎng)路徑為：4—2