【正文】 答題畢2006級(jí)（A）1 用圖解法求解下列線性規(guī)劃問題。 （10分）解：決策樹見下圖：0中油田小油田無開采價(jià)值大油田不投標(biāo)或未中標(biāo)投標(biāo)并中標(biāo)計(jì)算效用期望值見下表。根據(jù)地震資料的分析，開采期內(nèi)可賺取20億元；，開采期內(nèi)可賺取10億元；，開采期內(nèi)可賺取3億元；，按招標(biāo)規(guī)定，開采前的勘探等費(fèi)用均由中標(biāo)者負(fù)擔(dān)，以后不論油田規(guī)模多大，開采期內(nèi)賺取的利潤中標(biāo)者分成30%。(4) 狀態(tài)轉(zhuǎn)移方程：sk+1=skxk(5) 階段指標(biāo)函數(shù)：vk(sk,xk)見表所示。(2) 狀態(tài)變量sk：k階段初待分派的資金；S1={2}、 S2={0,1,2}、 S3={0,1,2}。問應(yīng)如何分配追加投資，使其中至少有一個(gè)方案完成的概率為最大。據(jù)現(xiàn)有條件，=。（1）根據(jù)初始流，則尋找可擴(kuò)充路（增廣鏈）的標(biāo)號(hào)過程如下：vsv5v4v3v2v1vt3(3)3(2)5(5)6(4)3(3)2(0)4(4)2(2)5(4)2(0)6(6)8(6)（，∞）（+vs，2）（v5，1）（+v2，1）（v3，1）（+v1，1）（+v4，1）（2）調(diào)整流量，繼續(xù)標(biāo)號(hào)有：vsv5v4v3v2v1vt3(2)3(3)5(5)6(5)3(3)2(0)4(4)2(1)5(5)2(0)6(6)8(7)（+vs，1）（，∞）（3）由圖所示，標(biāo)號(hào)過程進(jìn)行不下去，即不存在vsvt的可擴(kuò)充路（增廣鏈），根據(jù)可擴(kuò)充路（增廣鏈）定理，圖示流即為最大流，maxQ=13。圖中各弧旁數(shù)字為容量cij，括弧中為流量fij。 （10分）解：用對(duì)偶單純形法求解有：Cj52400bCBXBx1x2x3x4x50x43121040x563*50110σj524000x41*01/311/32/32x2215/301/310/3σj102/302/320/35x1101/311/32/32x2011212σj001/311/322/3∴ 規(guī)劃問題最優(yōu)解為 X*=(2/3，2，0)T；Z*=22/35 已知運(yùn)輸問題的產(chǎn)銷平衡表與單位運(yùn)價(jià)表如表所示，試用Vogel法求出其近似最優(yōu)解。 （10分）解：原問題標(biāo)準(zhǔn)化為：其初始單純形表為：Cj35110000Xjx1x2x/3x//3x4x5x6x7000x5x6x761610121211135135100100010001cjzj351100003 寫出下列線性規(guī)劃問題的對(duì)偶問題。 （10分）解：圖解過程見下圖0 1 2 3 4 x1x2321由圖可見，該問題具有無界解。分別依據(jù)悲觀主義、樂觀主義、等可能性、最小機(jī)會(huì)損失決策準(zhǔn)則決定該書店應(yīng)訂購新書的數(shù)量。根據(jù)以往經(jīng)驗(yàn)，新書的銷售量可能為50、100、150或200本。（4）狀態(tài)轉(zhuǎn)移方程：； （5）階段指標(biāo)：見表，如： ；；（6）遞推方程：（7）邊界條件：。 （10分）增加青工數(shù)采礦隊(duì)012345第一采礦隊(duì)第二采礦隊(duì)第三采礦隊(duì)00016101225141730162132172233解：根據(jù)題意，原問題用動(dòng)態(tài)規(guī)劃求解模型為：（1）按作業(yè)班組分為3階段，K=（1，2，3，4），k=4為終了階段；（2）xk：第k階段初擁有待分配新工人數(shù)；有：X1={8}，X2={8,7,6,5,4,3}，X3={5,4,3,2,1,0}，X={0}。 （10分）2222222233335514解：用破圈法求最小部分樹為：W（Tmin）=18 注意有多重解2222222233335514用避圈法求最小部分樹為：W（Tmin）=1822222222333355148 用標(biāo)號(hào)法求下圖中v1至各點(diǎn)的最短路。試問如何從中選拔一個(gè)450m混合泳的接力隊(duì)，使預(yù)期的比賽成績?yōu)樽詈?。將此問題歸結(jié)為運(yùn)輸問題，列出相應(yīng)的產(chǎn)銷平衡表與單位運(yùn)價(jià)表。另有城市4雖未簽訂合同，但也表示只要公司有剩余煤炭，愿全部收購。5 東興煤炭公司下屬吉祥、平安、雙福三個(gè)煤礦，年生產(chǎn)能力分別為1160、100萬t。 （10分）解：原問題的對(duì)偶問題為：由約束條件 可知，其對(duì)偶問題無解；又因是原問題的可行解。 （10分）解：原問題標(biāo)準(zhǔn)化為：其初始單純形表為：Cj31120000Xjx1x/2x//2x/3x4x5x6x7000x4x6x71285243311311423100010010001cjzj311200003 已知某線性規(guī)劃問題用單純形法迭代時(shí)得到中間某兩步的單純形表如表所示，試將表中空白處數(shù)字填上。 （10分）解：圖解過程見下圖0 1 2 x1x221有： 該問題有無窮多最優(yōu)解。 （10分） 銷路品種收益(萬元)銷路好銷路中銷路差p(θ1)=p(θ2)=p(θ3)=A1141412A2221410A3181610A420128解：（1）最大可能準(zhǔn)則由表可以看出，銷路中的概率p=，因此產(chǎn)品的市場銷路中的可能性也就最大。 （10分）4,4,63,3,83,3,33,2,72,0,33,0,62,1,32,2,32,2,22,0,34,2,44,4,24,4,24,4,2vtv6v5v4v3v2vsv1解：由原流圖可作出其費(fèi)用有向圖為：47368373633234222vtv6v5v4v3v2vsv19 某企業(yè)擬利用剩余生產(chǎn)能力開發(fā)新產(chǎn)品。試建立其動(dòng)態(tài)規(guī)劃模型（不必求解）。 （10分）解：的海賽矩陣為：==，當(dāng)時(shí)，所以為凸函數(shù)。用表格迭代有　　　　Cj536600MbCBXBx1x2x3x4x5x6x70x51211100180x621[3]301016Mx7111100110σj5M3M6M6+M00010M0x51/35/30011/3038/36x32/31/31101/3016/3Mx71/3[2/3]0001/3114/3σj1M/312M/30002+M/3032+14M/30x51/200011/25/216x3[1/2]01101/21/233x21/210001/23/27σj1/200003/2390x500111145x110220163x2011[1]014σj001102420x501001085x1120001146x40111014σj01000146所以有：X*=(x1,x2,x3,x4,x5,x6,x7)T=(14,0,0,4,8,0,0)T；Z′*=46還原為原問題有：X*=(14,0,4)T；Z*=465 求解整數(shù)規(guī)劃問題： . 且為整數(shù)。 （10分）解：原問題的對(duì)偶規(guī)劃為：或 4 用大M法求解：為自由變量。于是就考慮按照這種市場銷路決策，通過比較可知，企業(yè)采取中批生產(chǎn)收益最大，所以d2是最優(yōu)決策方案?，F(xiàn)在要求通過決策分析，合理地確定生產(chǎn)批量，使企業(yè)獲得的收益最大。對(duì)v1來說，頂點(diǎn)vv4是不可達(dá)的?；∵厰?shù)字是該弧的長度。 （10分）解：原問題可改寫為：. 均是非負(fù)整數(shù)。 （10分）解：（1） 因 所以舍去區(qū)間（，10]7 試建立求解問題： . 均是非負(fù)整數(shù)。枚舉過程如下表：序號(hào)X=(x2,x4,x3,x1)T閥值約束1約束2約束3目標(biāo)函數(shù)0(0,0,0,0)T√1(0,0,0,1)T2(0,0,1,0)T√3(0,0,1,1)T4(0,1,0,0)T4√√√45(0,1,0,1)T6(0,1,1,0)T7(0,1,1,1)T8(1,0,0,0)T9(1,0,0,1)T10(1,0,1,0)T11(1,0,1,1)T12(1,1,0,0)T13(1,1,0,1)T14(1,1,1,0)T15(1,1,1,1)T所以：X*=(x2,x4,x3,x1)T=(0,1,0,0)T Z*=4還原有：X*=(x1,x2,x3,x4)T=(0,0,0,1)T Z*=46 用黃金分割法求解：的極小點(diǎn)。 （10分）解：原模型標(biāo)準(zhǔn)化為： 2 用圖解法求解 （10分）解：用圖解法有：（20/19,45/19）（2,0）3x1+5x2=15x2543210 1 2 3 4 5 x15x1+2x2=10該問題有無窮多最優(yōu)解,聯(lián)立 解得；聯(lián)立 解得；所以 ；3 用單純形法求解