2008采礦05運(yùn)籌學(xué)試題(A)解答

1、1 用圖解法求解下列線性規(guī)劃問題，并指出問題具有惟一最優(yōu)解、無窮多最優(yōu)解、無界解還是無可行解。 解：圖解過程見下圖0 1 2 x1x221有： 該問題有無窮多最優(yōu)解。2 將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式，并列出初始單純形表。 （10分）解：原問題標(biāo)準(zhǔn)化為：其初始單純形表為：Cj-3-11-20000Xjx1x/2x/2x/3x4x5x6x7000x4x6x7128524331-1-3-114-2-31000-10010001cj-zj-3-11-200003 已知某線性規(guī)劃問題用單純形法迭代時(shí)得到中間某兩步的單純形表如表所示，試將表中空白處數(shù)字填上。 （10分）354000x1x2x3x4x5x

2、6500x2x5x68/314/329/32/3-4/35/31000541/3-2/3-2/3010001cj-zj-1/304-5/300543x2x3x150/4162/4189/4100110001015/41-6/41-2/418/415/41-12/41-10/414/4115/41cj-zj000-45/41-24/41-11/414 已知線性規(guī)劃問題：試應(yīng)用對偶理論證明上述線性規(guī)劃問題最優(yōu)解為無界。 （10分）解：原問題的對偶問題為：由約束條件 可知，其對偶問題無解；又因是原問題的可行解。由對偶定理可知原線性規(guī)劃問題最優(yōu)解為無界。5 東興煤炭公司下屬吉祥、平安、雙福三個(gè)煤礦，年

3、生產(chǎn)能力分別為120、160、100萬t。公司同3個(gè)城市簽訂了下年度的供貨合同：城市1-110萬t，城市2-150萬t，城市3-70萬t，但城市3表示愿購買剩余的全部煤炭。另有城市4雖未簽訂合同，但也表示只要公司有剩余煤炭，愿全部收購。已知從各礦至4個(gè)城市的煤炭單位運(yùn)價(jià)見表。將此問題歸結(jié)為運(yùn)輸問題，列出相應(yīng)的產(chǎn)銷平衡表與單位運(yùn)價(jià)表。 （10分）單位運(yùn)價(jià)表 單位：元/t城市煤礦1234吉祥平安雙福856724513235解：該問題的運(yùn)輸問題產(chǎn)銷平衡表與單位運(yùn)價(jià)表為城市煤礦1233/4/產(chǎn)量吉祥平安雙福虛設(shè)礦山856M724M513M5130235012016010050銷量11015070505

4、06 已知下列五名運(yùn)動(dòng)員各種姿勢的游泳成績(各為50m，單位：s)如表所示。試問如何從中選拔一個(gè)4×50m混合泳的接力隊(duì)，使預(yù)期的比賽成績?yōu)樽詈谩?（10分）趙錢張王周仰泳蛙泳蝶泳自由泳37.743.433.329.232.933.128.526.438.842.238.929.637.034.730.428.535.441.833.631.1解：原問題用匈牙利算法求解為： 變換后：再變換為： 再變換：再變換為： Z*=127.87 分別用破圈法和避圈法求下圖的最小部分樹。 （10分）2222222233335514解：用破圈法求最小部分樹為：W（Tmin）=18 注意有多重解222

5、2222233335514用避圈法求最小部分樹為：W（Tmin）=1822222222333355148 用標(biāo)號法求下圖中v1至各點(diǎn)的最短路。 （10分）v1v6v5v7v3v2198v42857410373解：標(biāo)號過程如圖所示：v1v6v5v7v3v2198v42857410373（0,v1）（14,v4）（13,v5）（11,v2）（10,v2）（9,v1）（8,v1）由圖可得：v1v2 L=9v1v3 L=8v1v2v4 L=11v1v2v5 L=10v1v2v4v6 L=14v1v2v5v7 L=139 現(xiàn)有8名青工，要分配給3個(gè)采礦隊(duì)，每隊(duì)限最多分5名，每個(gè)采礦隊(duì)增加不同青工后產(chǎn)量增

6、加如下表，如何分配才能使產(chǎn)量增加最大？試建立其動(dòng)態(tài)規(guī)劃求解模型。 （10分）增加青工數(shù)采礦隊(duì)012345第一采礦隊(duì)第二采礦隊(duì)第三采礦隊(duì)0001610122514173016213217223317.522.5解：根據(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。（3）uk：第k階段分配給第k作業(yè)班組的新工人數(shù)；有：U1=0,1,2,3,4,5，U2=0,1,2,x2( x25)；U2= x2-5,5( x2>5)，U3=x3。（4）狀態(tài)轉(zhuǎn)移方程：； （5）階段指標(biāo)：見表，如： ；（6）遞推方程：（7）邊界條件：。10 某書店希望訂購最新出版的圖書出售。根據(jù)以往經(jīng)驗(yàn)，新書的銷售量可能為50、100、150或200本。假定每本書的訂購價(jià)為4元，銷售價(jià)為6元，剩書處理價(jià)為每本2元。分別依據(jù)悲觀主義、樂觀主義、等可能性、最小機(jī)會損失決策準(zhǔn)則決定該書店應(yīng)訂購新書的數(shù)量。（10分）解：（1）根據(jù)題意該問題的益損值表為： Sji501001502