上海電機(jī)學(xué)院運籌學(xué)期末考試試題及答案

1、選擇題（共20分，每題2分）1、線性規(guī)劃模型三個基本要素中不包括（D ）A.決策變量B.目標(biāo)函數(shù)C.約束條件D.基2、使用人工變量法求解極大化線性規(guī)劃問題時，當(dāng)所有的檢驗數(shù)/M 0在基變量中仍含有非零的人工變量，表明核線性規(guī)劃問題（ D ）A.有唯一的最優(yōu)解B.有無窮多最優(yōu)解 C.為無界解D .無可行解3、若線性規(guī)劃的原問題不存在最優(yōu)解，則對偶問題（ B ）A.可能存在最優(yōu)解B.不存在最優(yōu)解C. 一定是無可行解D. 一定是無界解4、若線性規(guī)劃問題的某個資源常數(shù)發(fā)生變化，則在最終單純形表中這一變化 （B ）A.對檢驗數(shù)存在影響B(tài).對b列數(shù)存在影響C.對該資源常數(shù)所在行的數(shù)存在影響D.對所有數(shù)都無

2、影響5、在產(chǎn)銷平衡運輸問題中，設(shè)產(chǎn)地為 m個，銷地為n個，那么基變量個數(shù) （C ）A.不能大于（m+n-1） B.不能小于（m+n-1）C.等于（m+n-1） D.不確止6、一般講，對于某一問題的線性規(guī)劃與該問題的整數(shù)規(guī)劃可行域的關(guān)系存在(A )A.前者大于后者B.后者大于前者C.二者相等D.二者無關(guān)7、如果要使目標(biāo)規(guī)劃實際實現(xiàn)值不超過目標(biāo)值。則相應(yīng)的偏離變量應(yīng)滿足(B )A.d* 0 B./=0C.d -0 D.08、對于目標(biāo)規(guī)劃問題的求解，在滿足一個目標(biāo)時(B )A.必須同時考慮優(yōu)先級較低的目標(biāo) B.不得違背已經(jīng)得到滿足的優(yōu)先級更高 的目標(biāo)C.不必顧慮優(yōu)先級較高的目標(biāo)D.無須考慮上述情況9

3、、關(guān)于圖論中的圖，以下敘述不正確的是( C )A.圖中點表示研究對象，邊或有向邊表示研究對象之間的特定關(guān)系B.圖論中的圖，畫邊時長短曲直無所謂C.圖中的邊表小研究對象，點表小研究對象之間的特定關(guān)系D.圖論中的圖，可以改變點與點的相互位置，只要不改變點與點的連接關(guān)系10、關(guān)于最短路，以下敘述正確的有（A ）A. 從起點出發(fā)到終點的最短路不一定是唯一的，但其最短路線的長度是確定的B.從起點出發(fā)到終點的最短路是唯一的C.從起點出發(fā)的有向邊中的最小權(quán)邊，一定包含在起點到終點的最短路上D.從起點出發(fā)的有向邊中的最大權(quán)邊，一定不包含在起點到終點的最短路上二、填空題（共10 分，每空 1 分）1、線性規(guī)劃問

4、題如果有無窮多最優(yōu)解，則單純形計算表的終表中必然有某一個非基變量的檢驗數(shù)為 0。2、線性規(guī)劃的解有唯一最優(yōu)解、無窮多最優(yōu)解、無界解 和無可行解四種。3、線性規(guī)劃原問題中的變量個數(shù)與其對偶問題中的約束條件 個數(shù)相等，因此，當(dāng)原問題增加一個變量時，對偶問題就增加一個約束條件 ，從而對偶可行域?qū)⒖赡茏冃?（ 小還是大 ） 。4、“如果線性規(guī)劃原問題存在可行解，則其對偶問題一定存在可行解”，這句話對還是錯？ 錯。5、如果某一整數(shù)規(guī)劃：max工二七斗刀工951JT十S1414f 1-2工+三冬王，出之0,11為整數(shù)所對應(yīng)的線性規(guī)劃（松弛問題）的最優(yōu)解為10,我們現(xiàn)在要對 進(jìn)行分枝，應(yīng)該分為為x 0J =

5、 1,2,3 K. J解：把模型化成標(biāo)準(zhǔn)形式：maxZ = 3Hl +412 +七2Xj +3jc2 +鼻 =1F +2/ +2Xj +r5 =3七 N0jf2,32分單純形表Cj34100OCBXBbX1X2X3X4X50X41231101/30X53122013/2%3410004X21/32/311/31/301/20X57/3-1/304/3-2/31-%1/30-1/3-4/303X11/213/21/21/200X55/201/23/2-1/210-1/2-1/2-3/209分最優(yōu)解：X= (1/2, 0, 0, 0, 5/2);最優(yōu)值 Z=3/212分四、(本題14分)設(shè)用單純形

6、法求解某極大化線性規(guī)劃問題得到如下的單純形表cj203/2000CBXBhx1x2x3x4x5x6ax12d-1001-1bx33/20210-12cx40e001-100-100-1/2f(1)試求上述表中的各參數(shù)af的值；(2)上表是否給出了最優(yōu)解，若是則求出最優(yōu)解;(3)利用對偶關(guān)系求出對偶問題最優(yōu)解、最優(yōu)值。解：（1） a=2, b=3/2, c=0, d=1, e=0, f=-6分(錯一個扣一分)(2)由于所有檢驗數(shù)都非正，因此該表給出最優(yōu)解，最優(yōu)解為JC1 = 2,巧=O,JCj =0,工百=0*=25/4(3)利用對偶關(guān)系可得對偶問題最優(yōu)解為M=。，用=1/2g=1,4 =。M，

7、丸=013分825/414分五、(共12分)已知線性規(guī)劃問題的最終單純表如下cj3 1 5 0 0CBXBhx1 x2 x3 x4 x535x1x3531-1/3 0 1/3 -1/30 1 1 -1/5 2/50 -3 0 0 -1試分析(1)在什么范圍變化，最優(yōu)解不變？(2)增加一個新的約束條件2玉+39十毛434,原問題最優(yōu)解是否依然保持？解：（1）由最終單純形表可知，為保持原最優(yōu)解不變應(yīng)有：1R*o仁=.（4 + 2）。L 35 分解不等式組得：3,67 分（2）將原問題的最優(yōu)解X= （5, 0, 3, 0, 0）代入不等式石十馬十434中，不等式仍然成立，故最優(yōu)解不變。-12 分銷地

8、rMB1B2B3B4產(chǎn)量（噸）Al81069250A2127156200A3651012350銷量（噸）220180160240800六、（共12分）銷地R產(chǎn)妁BAi8S元之 兩小素3 3 3 36已知產(chǎn)銷量及運價表（見右表）求解此運輸問題（要求用沃格爾法求初始調(diào) 運方案，用位勢法求檢驗數(shù)）。解：（1）由沃格爾法求初始調(diào)運方案 產(chǎn)銷平衡表二錯地產(chǎn)地 8iB,產(chǎn)量Ai5016040250%2002OT小170180350鋪必220190ieo540單位運價表的品小元菜之差牛 感6強(qiáng) J1b |岑】92111（2）用位勢法求檢驗數(shù)檢驗數(shù)表情Zf由日工%8I 0g0%7 M21 7（12） 156-3654） 110,112，一一B769（3）因為全體檢驗數(shù)非負(fù)，所以初始調(diào)運方案即為最優(yōu)解。12分七、（共10分）用Dijkstra 算法求下圖中vi到%的最短路。（可在原圖上標(biāo)號）解：評分標(biāo)準(zhǔn)，表錯一個扣一分10分八、（共10分）用圖解法找出下面目標(biāo)規(guī)劃問題，并寫出簡要步驟mmZ =片+用(4)十月若而一芻十4一一/；=0 (1)物+2小+d-d；=12 (2) TOC o 1-5 h z 2X1 +3x2+-(/； =12(3)$ 4 4(4)礪 0 (I = 1.23) 1ta 、解:X2d2+(4)d3