運(yùn)籌學(xué)試卷試題和答案

1、 試 題 2009 年 2010 年第 1 學(xué)期課程名稱： 運(yùn)籌學(xué)基礎(chǔ) 專業(yè)年級(jí)： 信息（電專）0803、0804 考生學(xué)號(hào)： 考生姓名： 試卷類型： A卷 B卷 考試方式: 開(kāi)卷 閉卷 一、 填空（每題4分，共20分）1. 線性規(guī)劃問(wèn)題MaxZ=CX；AX=b，X0（A為kxl的矩陣，且l>k）的基的最多個(gè)數(shù)為_(kāi)，基的可行解的最多個(gè)數(shù)為_(kāi).2.指派問(wèn)題的最優(yōu)解的性質(zhì)_.3.線性規(guī)劃問(wèn)題的所有可行解構(gòu)成的集合是_,它們有有限個(gè)_,線性規(guī)劃問(wèn)題的每個(gè)基可行解對(duì)應(yīng)可行域的_,若線性規(guī)劃問(wèn)題有最優(yōu)解，必在_得到。4影子價(jià)格的經(jīng)濟(jì)含義_.在完全市場(chǎng)經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場(chǎng)價(jià)格低于影子價(jià)格時(shí)

2、，企業(yè)應(yīng)_該資源，而當(dāng)某種資源的市場(chǎng)價(jià)格高于影子價(jià)格時(shí)，則企業(yè)應(yīng)_該資源，可見(jiàn)影子價(jià)格對(duì)市場(chǎng)有_作用。5. 運(yùn)輸問(wèn)題的產(chǎn)銷平衡表中有m個(gè)產(chǎn)地n個(gè)銷地，其決策變量的個(gè)數(shù)有_個(gè)，其數(shù)值格有_個(gè)二、 計(jì)算（共60分）1 對(duì)下列線性規(guī)劃問(wèn)題 Max z=2x1+x2+3x3 x1+ x2+2x3 5 s.t. 2x1+3x2+4x312x1, x2, x30（1） 寫(xiě)出其對(duì)偶問(wèn)題；（5分）（2） 已知（3，2，0）T是上述問(wèn)題的最優(yōu)解，根據(jù)互補(bǔ)松弛理論求出對(duì)偶問(wèn)題的最優(yōu)解；（10分）2. （15分）運(yùn)用單純形法求解下面線性規(guī)劃問(wèn)題。 3 （15分）已知運(yùn)輸問(wèn)題的產(chǎn)銷平衡表與單位運(yùn)價(jià)表如下表所示 銷地產(chǎn)

3、地B1B2B3B4產(chǎn)量A11067124A21610599A35410104銷量5246試用運(yùn)用伏格爾法求出初始運(yùn)輸方案。4 （15分）用匈牙利法求解下列分配問(wèn)題，已知效益矩陣為 798561274879667810三、 建模（第1題10分，第2題10分，共20分）1 某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下：設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開(kāi)始時(shí)上班，并連續(xù)工作八小時(shí)，問(wèn)該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員 （15分）2. 某工廠要做100套鋼架，每套用長(zhǎng)為2.9 m,2.1 m,1.5 m的圓鋼各一根。已知原料每根長(zhǎng)7.4 m，問(wèn)：

4、應(yīng)如何下料，可使所用原料最省（15分） 試卷答案 2009 年 2010 年第 1 學(xué)期課程名稱： 運(yùn)籌學(xué)基礎(chǔ) 專業(yè)年級(jí)： 信息（電專）0803、0804 考生學(xué)號(hào)： 考生姓名： 試卷類型： A卷 B卷 考試方式: 開(kāi)卷 閉卷 四、 填空（每空2分，共20分）1:Clk , Clk 2設(shè)指派問(wèn)題的效率矩陣為C= ，若將該矩陣的某一行（或某一列）的各個(gè)元素都減去統(tǒng)一常數(shù)，得到新的效率矩陣，則以為效率矩陣的新的指派問(wèn)題與原指派問(wèn)題的最優(yōu)解相同。3 凸集，頂點(diǎn)，頂點(diǎn)，頂點(diǎn)4其它條件不變的情況下，單位第i種資源變化所引起目標(biāo)函數(shù)值的變化量。買(mǎi)進(jìn)，賣出。5 ，五、 計(jì)算（每題15分，共60分）1. 解（

5、1）（5分）寫(xiě)出其對(duì)偶問(wèn)題； Minw=5y1+12y2 s.t. y1+2y22 y1+3y21 2y1+4y23 y10， y2 無(wú)約束 （2） （10分）已知（3，2，0）T是上述問(wèn)題的最優(yōu)解，根據(jù)互補(bǔ)松弛理論求出對(duì)偶問(wèn)題的最優(yōu)解； 由于原問(wèn)題x1和x2為正，根據(jù)互補(bǔ)松弛理論，有對(duì)偶問(wèn)題取最優(yōu)解時(shí)（1）、（2）取嚴(yán)格等式，即為 y1+2y22 y1+3y21解得y2-1 y14故對(duì)偶問(wèn)題最優(yōu)解為Y*（4，1），w*=82. 解（1）（3分）加入松弛變量，上述模型可轉(zhuǎn)化為（10分） cj3130CBXBbx1x2x3x40x315351050x42462014z031000x33041-0

6、.51.23x1411/301/6-z12000-0.5（2分）最優(yōu)解，最優(yōu)值3. （1） （7分）用最小元素法求得初始可行基如下 銷地產(chǎn)地B1B2B3B4產(chǎn)量A110 36 ×7 ×12 14 0 A216 ×10 ×5 49 59 -3A35 24 210 ×10 ×4 -5銷量5 102 94 86 12（2） （8分）位勢(shì)方程組為u1+v1=10 u1+v4=12u2+v3=5 u2+v4=9u3+v1=5 u3+v2=4令u10，解得v1=10 v2=9 v3=8 v4=12 u2 =-3 u3 =-5 各非基變量檢驗(yàn)數(shù)為1

7、26（09）-3137（08）-12116（103）92210（93）43310（85）73410（125）3存在非基變量檢驗(yàn)數(shù)為負(fù)，沒(méi)有達(dá)到最優(yōu)解4 用匈牙利法求解下列分配問(wèn)題，已知效益矩陣為 798561274879667810第一步（5分），把Cij轉(zhuǎn)化為Cij, 2410281030210104第二步（5分），求初始分配方案及尋找覆蓋所有零元素的最少直線，2410281030210104第三步（5分），調(diào)整，求最優(yōu)解。1300170030220105所以，最優(yōu)解為六、 建模（第1題10分，第2題10分，共30分）1. 解：設(shè) xi 表示第i班次時(shí)開(kāi)始上班的司機(jī)和乘務(wù)人員數(shù), （2分）這樣我們建立如下的數(shù)學(xué)模型。 目標(biāo)函數(shù)： Min x1 + x2 + x3 + x4 + x5 + x6 （3分） 約束條件：s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0（5分）2. 解： 共可設(shè)計(jì)下列5 種下料方案，見(jiàn)下表（5分）設(shè) x1,x2,x3,x4,x5 分別為上面 5 種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學(xué)模型。（5分） 目