【正文】 同青工后產(chǎn)量增加如下表，如何分配才能使產(chǎn)量增加最大？試建立其動(dòng)態(tài)規(guī)劃求解模型。 （10分）增加青工數(shù)采礦隊(duì)012345第一采礦隊(duì)第二采礦隊(duì)第三采礦隊(duì)00016101225141730162132172233解：根據(jù)題意，原問(wèn)題用動(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}。（3）uk：第k階段分配給第k作業(yè)班組的新工人數(shù)；有：U1={0,1,2,3,4,5}，U2={0,1,2,…,x2}( x25)；U2={ x25,…,5}( x25)，U3={x3}。（4）狀態(tài)轉(zhuǎn)移方程：； （5）階段指標(biāo)：見表，如： ；；（6）遞推方程：（7）邊界條件：。10 某書店希望訂購(gòu)最新出版的圖書出售。根據(jù)以往經(jīng)驗(yàn)，新書的銷售量可能為50、100、150或200本。假定每本書的訂購(gòu)價(jià)為4元，銷售價(jià)為6元，剩書處理價(jià)為每本2元。分別依據(jù)悲觀主義、樂觀主義、等可能性、最小機(jī)會(huì)損失決策準(zhǔn)則決定該書店應(yīng)訂購(gòu)新書的數(shù)量。（10分）解：（1）根據(jù)題意該問(wèn)題的益損值表為： Sjαi501001502005010015020010001002001002001000100200300200100200300400（2）悲觀準(zhǔn)則： ∴樂觀準(zhǔn)則： ∴等可能準(zhǔn)則： ∴最小機(jī)會(huì)損失準(zhǔn)則：損失矩陣為： 則 ∴答題畢 2005級(jí)（B）1 用圖解法求解下列線性規(guī)劃問(wèn)題，并指出問(wèn)題具有惟一最優(yōu)解、無(wú)窮多最優(yōu)解、無(wú)界解還是無(wú)可行解。 （10分）解：圖解過(guò)程見下圖0 1 2 3 4 x1x2321由圖可見，該問(wèn)題具有無(wú)界解。2 將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式，并列出初始單純形表。 （10分）解：原問(wèn)題標(biāo)準(zhǔn)化為：其初始單純形表為：Cj35110000Xjx1x2x/3x//3x4x5x6x7000x5x6x761610121211135135100100010001cjzj351100003 寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題。 （10分）解：原問(wèn)題的對(duì)偶規(guī)劃為：4 用對(duì)偶單純形法求解下列線性規(guī)劃問(wèn)題。 （10分）解：用對(duì)偶單純形法求解有：Cj52400bCBXBx1x2x3x4x50x43121040x563*50110σj524000x41*01/311/32/32x2215/301/310/3σj102/302/320/35x1101/311/32/32x2011212σj001/311/322/3∴ 規(guī)劃問(wèn)題最優(yōu)解為 X*=(2/3，2，0)T；Z*=22/35 已知運(yùn)輸問(wèn)題的產(chǎn)銷平衡表與單位運(yùn)價(jià)表如表所示，試用Vogel法求出其近似最優(yōu)解。（10分）銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3A491081081091012121111131412121824612銷量614355解：該問(wèn)題用Vogel法求其近似最優(yōu)解為：銷地414224475產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3A49108108109101212111113141212182461210103231231211銷量6143551100100200006 求解整數(shù)規(guī)劃問(wèn)題： （10分）解：用圖解法有：0426486x18x22●●●∴X*=(5，0)T或X*=(4，1)T或X*=(3，2)T；Z*=57 用單純形求解下述目標(biāo)規(guī)劃問(wèn)題： （10分）解：用單純形法求解有000P2P30P4P1P1基x1x2d1d1+d2d2+d3d3+d4d4+0P3P4d1d2d3d440100301511[1]0110110001000010001000010001000010001P10000000101P20001000000P31100010000P4100000100P30d1d2x1d4107030150010[1]10110001000010001001110111000010001P10000000101P20001000000P30100011100P4000001000P30x2d2x1d41060305001010001101110[1]010001001011101100010001P10000000101P20001000000P30011011100P4000000P30P2x2d2x1d1+1555305001010000001000101000100011[1]011111011101P10000000101P20010001111P30000011111P40000001000P30P4x2d2x1d315602550010100001110111010001000001000110111011P10000000101P20001000000P30011010000P4001100011∴X*=(25，15)T8 用FordFulkerson的標(biāo)號(hào)算法求下圖中所示各容量網(wǎng)絡(luò)中從vs到vt的最大流。圖中各弧旁數(shù)字為容量cij，括弧中為流量fij。 （10分）vsv5v4v3v2v1vt3(3)3(2)5(5)6(4)3(3)2(0)4(4)2(2)5(4)2(0)6(6)8(6)解：用FordFulkerson方法求解。（1）根據(jù)初始流，則尋找可擴(kuò)充路（增廣鏈）的標(biāo)號(hào)過(guò)程如下：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)過(guò)程進(jìn)行不下去，即不存在vsvt的可擴(kuò)充路（增廣鏈），根據(jù)可擴(kuò)充路（增廣鏈）定理，圖示流即為最大流，maxQ=13。9 某項(xiàng)工程有三個(gè)設(shè)計(jì)方案。據(jù)現(xiàn)有條件，，=。為使這三個(gè)方案中至少完成一個(gè)的概率盡可能大，決定追加2萬(wàn)元投資，當(dāng)使用追加投資后，上述方案完不成的概率見下表。問(wèn)應(yīng)如何分配追加投資，使其中至少有一個(gè)方案完成的概率為最大。（只建模型） （10分）追加投資（萬(wàn)元）各方案完不成的概率123012解：(1) 階段：每個(gè)設(shè)計(jì)方案為一階段，K={1,2,3,4}，k=4為結(jié)束階段。(2) 狀態(tài)變量sk：k階段初待分派的資金；S1={2}、 S2={0,1,2}、 S3={0,1,2}。(3) 決策變量xk：k階段分派給k設(shè)計(jì)方案的資金；D1(s1)={0,1,2}、D2(s2)={0,1,2}、D3(s3)={s3} 。(4) 狀態(tài)轉(zhuǎn)移方程：sk+1=skxk(5) 階段指標(biāo)函數(shù)：vk(sk,xk)見表所示。(6) 遞推方程：(采用逆推法)(7) 邊界條件：10 有一塊海上油田進(jìn)行勘探和開采的招標(biāo)。根據(jù)地震資料的分析，開采期內(nèi)可賺取20億元；，開采期內(nèi)可賺取10億元；，開采期內(nèi)可賺取3億元；，按招標(biāo)規(guī)定，開采前的勘探等費(fèi)用均由中標(biāo)者負(fù)擔(dān)，以后不論油田規(guī)模多大，開采期內(nèi)賺取的利潤(rùn)中標(biāo)者分成30%。有A、B、C三家公司，其效用函數(shù)分別為：A公司 U(M)=(M+)B公司 U(M)=(M+)C公司 U(M)=(M+)試根據(jù)效用值，并用期望值法確定每家公司對(duì)投標(biāo)的態(tài)度。 （10分）解：決策樹見下圖：0中油田小油田無(wú)開采價(jià)值大油田不投標(biāo)或未中標(biāo)投標(biāo)并中標(biāo)計(jì)算效用期望值見下表。大油田中油田小油田無(wú)開采價(jià)值EMVA公司2B公司2C公司2結(jié)論為A公司和B公司愿參加投標(biāo)，C公司不參加投標(biāo)。答題畢2006級(jí)（A）1 用圖解法求解下列線性規(guī)劃問(wèn)題。 （10分）解：圖解過(guò)程見下圖0 5 10 15