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

運(yùn)籌學(xué)試卷B及參照答案（本題20分）一、考慮下面的線性規(guī)劃問題：Minz=6X1+4X2約束條件：2X1+X2≥13X1+4X2≥3X1,X2≥0用圖解法求解,并指出此線型規(guī)劃問題是具有惟一最優(yōu)解、無窮多最優(yōu)解、無界解或無可行解；寫出此線性規(guī)劃問題的原則形式；求出此線性規(guī)劃問題的兩個剩余變量的值；(4)寫出此問題的對偶問題。解：（1）陰影部分所示ABC即為此線性規(guī)劃問題的可行域。其中，A（0，1），B（1，3/4），C（1/5，3/5）。顯然，C（1/5，3/5）為該線性規(guī)劃問題的最優(yōu)解。因此，該線性規(guī)劃問題有唯一最優(yōu)解，最優(yōu)解為：。X2X2BX10BX10AL1AL1CCL2L2——8分。闡明：畫圖對的3分；求解對的3分；指出解的狀況并寫出最優(yōu)解2分。（2）原則形式為：——4分（3）兩個剩余變量的值為：——3分（4）直接寫出對偶問題如下：——5分（本題10分）二、前進(jìn)電器廠生產(chǎn)A、B、C三種產(chǎn)品，有關(guān)資料下表所示：產(chǎn)品材料消耗/（kg/件）臺時消耗/（臺時/件）產(chǎn)品利潤/（元/件）市場容量/件A2.028200B1.51.510250C5.01.212100資源限制3000kg1000臺時在資源限量及市場容量容許的條件下，怎樣安排生產(chǎn)使獲利最多？（只建立線性規(guī)劃數(shù)學(xué)模型，不求解）解：設(shè)生產(chǎn)A、B、C三種產(chǎn)品的數(shù)量分別為x1，x2和x3，則有：——1分 ——14分，目的函數(shù)和每個約束條件2分（本題10分）三、某電子設(shè)備廠對一種元件的年需求為件，訂貨提前期為零，每次訂貨費(fèi)為25元。該元件每件成本為50元，年存儲費(fèi)為成本的20%。如發(fā)生供應(yīng)短缺，可在下批貨抵達(dá)時補(bǔ)上，但缺貨損失費(fèi)為每件每年30元。規(guī)定：（1）經(jīng)濟(jì)訂貨批量及整年的總費(fèi)用；（2）如不容許發(fā)生供應(yīng)短缺，重新求經(jīng)濟(jì)訂貨批量，并同（1）的成果進(jìn)行比較。解：（1）求出容許缺貨的經(jīng)濟(jì)訂購批量為：——6分（2）不容許發(fā)生供應(yīng)短缺的經(jīng)濟(jì)訂購批量為：比較（1）和（2），容許發(fā)生缺貨一般比不容許發(fā)生缺貨有更大的選擇余地。——4分（本題15分）四、已知某運(yùn)送問題的產(chǎn)量、銷量及運(yùn)送單價如表。又知B地區(qū)需要的115單位必須滿足銷地運(yùn)送單價銷地產(chǎn)地ABCDE產(chǎn)量甲乙丙10203015403520154020305540302550100130銷量25115603070規(guī)定：（1）列出該運(yùn)送問題的產(chǎn)銷平衡及單位運(yùn)價表；（2）用最小元素法求出此運(yùn)送問題的初始解。解：（1）根據(jù)題意，需不小于供，需要增長一種假想的產(chǎn)地丁，列出產(chǎn)銷平衡及單位運(yùn)價表如下：銷地產(chǎn)地ABCDE產(chǎn)量甲101520204050乙2040153030100丙3035405525130丁0M00020銷量25115603070300300——8分（2）用最小元素法求得初始解（因計算過程中最小元素有多種，可任選其一計算，計算的初始解不唯一）如下：銷地產(chǎn)地ABCDE產(chǎn)量甲54550乙106030100丙6070130丁2020銷量25115603070300300——7分（本題15分）五、某制造廠加工了150個機(jī)器零件，經(jīng)驗(yàn)表明由于加工設(shè)備的原因，這一批零件不合格率p不是0.10就是0.30，且所加工的這批量中p等于0.10的概率是0.8，這些零件將被用來組裝部件，制造廠可以在組裝前按每個零件10元的費(fèi)用來檢查這批零件的每個零件，發(fā)現(xiàn)不合格立即更換，也可以不予檢查就直接組裝，但發(fā)現(xiàn)一種不合格品進(jìn)行返工的費(fèi)用是100元。（1）寫出這個問題的收益矩陣；（2）用期望值法求出該廠的最優(yōu)檢查方案；（3）用決策樹措施解此題。解：（1）列出收益矩陣為：自然狀態(tài)方案N1（0.8）N3（0.2）S1（檢查）15001500S2（不檢查）15004500——4分（2）E（S1）=1500*0.8+1500*0.2=1500E（S2）＝1500*0.8+4500*0.2=2100故為S1（檢查）最優(yōu)方案。——4分（3）1500I1500I1（不合格），P(I1)=0.815001500SS1I2I2（不合格），P(I2)=0.2檢驗(yàn)1500檢驗(yàn)1500決決策I1I1（不合格），P(I1)=0.81500210015002100不檢查不檢查SS2II2（不合格），P(I2)=0.245004500由圖闡明應(yīng)選擇不檢查?！?分（本題15分）六、某工廠生產(chǎn)三種產(chǎn)品，多種產(chǎn)品重量與利潤關(guān)系如下表所示?，F(xiàn)將此三種產(chǎn)品運(yùn)往市場發(fā)售，運(yùn)送能力總重量不超過10噸，問怎樣安排運(yùn)送使總利潤最大？（背包問題,用動態(tài)規(guī)劃的措施求解）產(chǎn)品重量與利潤的關(guān)系種類重量（噸/件）利潤（元/件）121002314034180單位：萬元解：將問題按產(chǎn)品種類分為三個階段設(shè)sk＝分派給第k種產(chǎn)品到第三種產(chǎn)品的總重量（k＝1，2，3）；Xk＝分派給第k種產(chǎn)品的數(shù)量S1＝10，s2＝s1－2x1S3＝s2－3x2S3＝4x3基本方程為：——3分（1）當(dāng)k＝3時，s3＝4x3X3S3*01200——0010——0020——0030——0040180—180150180—180160180—180170180—18018018036036029018036036021001803603602——3分（2）當(dāng)k＝2時，X2S2＋*012300+0=0———0010+0=0——0020+0=0———0030+0=0140+0=140——140140+180=180140+0=140——180050+180=180140+0=140——180060+180=180140+0=140280+0=280—280270+180=180140+180=320280+0=280—320180+360=360140+180=320280+0=280—360090+360=360140+180=320280+0=280420+0=4204202100+360=360140+180=320280+180=460420+0=4204601——3分（3）當(dāng)k＝1時，X1S1＋*012345100+460=460100+360=460200+280=480300+180=480400+0=400500+0=5005005——3分當(dāng)*=5時，，*=0，，*=0，即運(yùn)送第一種產(chǎn)品5件，最優(yōu)值為500元?！?分(本題15分)七?如下圖，從V0派車到V8中間可通過V1，V2，V3，V4，V5，V6，V7各站，若各站間道路旁的數(shù)字表達(dá)單位時間內(nèi)此路上所能通過的最多車輛數(shù)，問應(yīng)怎樣派車才能使單位時間抵達(dá)V8的車輛最多?解：此為一種網(wǎng)絡(luò)的最大流問題，用麥克遜標(biāo)號法求解。首先需要對網(wǎng)絡(luò)的標(biāo)號進(jìn)行改善。（1）選擇路為v0—v2—v5—v8010V010V5010V010V2101001010010V8v10V8v0（2）選擇途徑v0—v3—v7—v820V820V8v0v0202003025303020V7V320V7V330V8（3）選擇途徑v0—v3—v6—v7—v30V840150