運籌學試卷及參考答案

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