[運(yùn)籌學(xué)](中科大)答案解析

1、cjb2+-530-M-MCBXBx1x2x3x4x5x62+x1511/2-5/2-1/21/20-Mx6201/27/21/2-1/214/7-z0-6- /2 + M/28+5 /2+ 7M/21+ /2+M/2-/2-M/2-10cjb2+-530-M-MCBXBx1x2x3x4x5x62+x145/716/70-1/71/75/73x34/701/711/7-1/72/7-z0-50/7-6 /70-1/7+ /7- M+1/7- /7-M-16/7-5 /7時(shí)，最優(yōu)解不變。7時(shí)， 750 617 ，即77750 617 ，即777cjb2+-530-M-MCBXBx1x2x3x4x

2、5x62+x145/716/70-1/71/75/715/23x34/701/711/7-1/72/74-z0-50/7-6 /70-1/7+ /7-M +1/7- /7-M-16/7-5 /7cjb2+-530-M-MCBXBx1x2x3x4x5x62+x1310-6-11-1-5x240171-12-z0040+67+-M-7-M+12+14(3)的最優(yōu)解為(3,4,0)T，目標(biāo)函數(shù)值為z 3模型（1）的最優(yōu)解為（3,29/7,0）T ，目標(biāo)函數(shù)值為z 314 5/ 7（ 4 ）變化第一個約束條件時(shí)：cjb2-530-M-MCBXbx1x2x3x4x5x6-Mx510+s21-5-1105

3、+s/2-Mx671110017-z2+3 M-5+2 M3-4 MM005 s/2 7，即 s 4時(shí)cjb2-530-M-MCBXBx1x2x3x4x5x62x15+s/211/2-5/2-1/21/20-Mx62-s/201/27/21/2-1/214/7-s/7-z0-6+ M/28+7 M/21+M/2-M/2-10cjb2-530-M-MCBXbx1x2x3x4x5x62x145/7+s/16/70-1/71/75/773x34/7-s/701/711/7-1/72/7-z0-50/70-1/7-M+1/7- M-16/745 s 4 s102 s此時(shí)最優(yōu)解為(45 s ,0, 4

4、s)T ，目標(biāo)函數(shù)最大值為z 102 s777變化第二個約束條件時(shí)：cjb2-530-M-MCBXBx1x2x3x4x5x6-Mx51021-5-1105-Mx67+t1110017+t-z2+3 M-5+2 M3-4 MM005 7 t ，即 t 2cjb2-530-M-MCBXbx1x2x3x4x5x62x1511/2-5/2-1/21/20-Mx62+t01/27/21/2-1/214/7+2t/7-z0-6+ M/28+7 M/21+M/2-M/2-10cjb2-530-M-MCBXbx1x2x3x4x5x62x145/7+5t/716/70-1/71/75/73x34/7+2t/70

5、1/711/7-1/72/7-z0-50/70-1/7-M+1/7- M-16/745 5t 4 2t T102 16t此時(shí)最優(yōu)解為(,0,) ，目標(biāo)函數(shù)最大值為z777很明顯當(dāng)擴(kuò)大第二項(xiàng)約束時(shí)最有利。3 、已知線性規(guī)劃問題：（ 2000,2004 ）Min z 2x1 x2 2x3x1 x2 x34s.t.x1 x2 kx3 6x1 0,x2 0, x3無約束*其最優(yōu)解為：x15;x2 0;x31（ 1 ） 寫出該問題的對偶問題，并求出對偶問題的最優(yōu)解；（ 2 ） 求出 k 的值解： （ 1 ）Max w 4y1 6y2y1 y22y1 y21s.t.y1 ky22y1無約束，y2 0由 z

6、 w 及互補(bǔ)松弛性質(zhì)得y1 y224y1 6y212得到y(tǒng)1 0, y22，得到k=1.4、設(shè)有線性規(guī)劃問題（2002 ）Min z 2x1 2x2 4x3s.t.2x13x13x2 5x3 2x2 7x3 3x1 4x2 6x3 5x2 0,x30, x1無約束試求（ 1 ）該問題的對偶問題2）寫出該問題的標(biāo)準(zhǔn)型，并寫出單純性法求解的初始單純型表。解：Max w2y1 3y2 5y32y1 3y2 y3 23y1 y2 4y3 2s.t.5y1 7y2 6y3 4y10, y20, y3無約束Max w2y1 3y2 5(y4 y5) 0y6 0y7 My8 My92y1 3y2 y4 y5

7、 y8 23y1 y2 4(y4 y5) y6 y92s.t.5y1 7y2 6(y4 y5) y7 4y1, y2 , y4 , y5, y6, y7 05 、設(shè)有線性規(guī)劃問題：( 2002 )MaxZ2x14x2x3x4x13x2x482x1x26s.t. x2 x3 x4 6x1 x2 x39xj 0,(j 1,2,3,4)T已知該問題的最優(yōu)解為：X*2, 2, 4,0 T ， 試根據(jù)對偶理論直接求出其對偶問題的最優(yōu)解。解：對偶問題為Min W 8y1 6y2 6y3 9y4y1 2y2 y423y1 y2 y3 y44s.t. y3 y4 1y1 y31yi 0(i 1,2,3, 4)

8、*由互補(bǔ)松弛性得y40，y1y31 ， 8y16y26y316 ，y31解的y1 0, y2 5/3, y3 1,y4 0四、指派問題1 、一個公司要分派5 個推銷員去5 個地區(qū)推銷某種產(chǎn)品，5 個推銷員在各個地區(qū)推銷這種產(chǎn)品的預(yù)期利潤如下表所示，問應(yīng)如何分派這5 個推銷員才能使得公司總的利潤最大。（ 2003 ， 2005 ）ABCDE甲1510121012乙1112999丙1020151713丁18179913戊713101312解：引入變量xij ，并令1 當(dāng)?shù)?i 個推銷員去第j個地區(qū)推銷產(chǎn)品xij0 當(dāng)?shù)?i個推銷員不去第j個地區(qū)推銷產(chǎn)品則該問題的數(shù)學(xué)模型為：max zcij xij

9、xij1,j 1,2,.,5xij1,i 1,2,.,5xij1或 0該模型的目標(biāo)函數(shù)可變化為min zbij xijxij1,j 1,2,.,5xij1,i 1,2,.,5xij1或 0其中bij20 cij 。然后采用匈牙利法求解。101085111111(bij)101010101010101、分配甲乙丙丁四個人去完成五項(xiàng)任務(wù)，每人完成各項(xiàng)任務(wù)的時(shí)間如下表所示，由于任務(wù)數(shù)多于人數(shù)，故規(guī)定其中一人可兼完成兩項(xiàng)任務(wù)，其余三人每人完成一項(xiàng)，試確定總花費(fèi)時(shí)間最小的指派方案。（ 2001 ， 2004 ）ABCDE甲3539415247乙4948363043丙4437385042丁34524633

10、55五、非線性規(guī)劃問題1 、設(shè)有如下的非線性規(guī)劃問題：( 2000 ， 2004 ， 2009 )22Min f (X) (x1 2)r1 (x2 x1 )0r2(2 x1 x2 ) 0r1 , r20 (x2 1)22g1(X) x2 x10s.t.g2(X) 2 x1 x2 0( 1 ) 用圖解法求上述問題的最優(yōu)解( 2 ) 簡述庫恩-塔克條件，并用(1 )的結(jié)果說明其幾何意義2(x1 2)2(x2 1)2x111解：f(X)g1(X)g2(X)2(x1 2)2x11r1r202(x2 1)1 1212 2r1 x1 r2 4 02x2 2 r1 r2 02r1(x2 x1 ) 0r2(2

11、 x1 x2 ) 0r1,r20解得r1 r22/3,x1 x2 12 、 試用動態(tài)規(guī)劃方法求解下面的非線性規(guī)劃問題(2001 ， 2000 )10Min f (Z)xi21110xi 16s.t. i 1xi0,(i 1,2,.,10)解：具體計(jì)算過程參考p207 或 p208f1s12f2 2s22/3f33s22/4f10 10s120/10 10*16 1/510*2 4/5六、簡答及建模問題（新的題型方向）簡答題1. 簡述對偶問題的對稱性定理、弱對偶性定理、對偶定理。對稱性定理：對偶問題的對偶是原問題。弱對偶性定理：若X 是原問題的可行解，Y 是對偶問題的可行解，則存在CXYb。對偶

12、定理：若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解；且目標(biāo)函數(shù)數(shù)值相等。2. 為什么排隊(duì)論中假定顧客到達(dá)服從泊松發(fā)布，而服務(wù)時(shí)間服從負(fù)指數(shù)分布？顧客到達(dá)服從泊松分布：（ 1） 在不相重疊的時(shí)間區(qū)間內(nèi)顧客到達(dá)數(shù)是相互獨(dú)立的（顧客到達(dá)是隨機(jī)的）（ 2） 對充分小的t，在時(shí)間區(qū)間t,t t）內(nèi)有一個顧客到達(dá)的概率與t 無關(guān)，而約與區(qū)間長t 成正比；（ 3） 對于充分小的t， 在時(shí)間區(qū)間t,t t）內(nèi)有兩個或兩個以上顧客到達(dá)的概率極小，以至于可以忽略。這三個條件是符合實(shí)際情況的，由此推出的概率分布為泊松分布。服務(wù)時(shí)間服從負(fù)指數(shù)分布：對一顧客的服務(wù)時(shí)間定義為在忙期相繼離開系統(tǒng)的兩顧客的間隔時(shí)間。相繼到達(dá)相繼

13、離開的間隔時(shí)間與輸入過程為泊松流是一致的，可以推出為獨(dú)立且同負(fù)指數(shù)分布。3. 概括中國郵遞員問題的解決思路：問題是：在一個有奇點(diǎn)的圖中，要求增加一些重復(fù)邊，使新圖不含奇點(diǎn)，并且重 復(fù)邊的總權(quán)為最小。思路：找奇點(diǎn)，增加重復(fù)邊，確定第一個可行方案；調(diào)整方案，去掉偶數(shù)條重復(fù) 邊，使重復(fù)邊總權(quán)下降到最小。二 分析解答題1. 設(shè)備更新問題（動態(tài)規(guī)劃）某車間生產(chǎn)過程中必須使用某臺設(shè)備，每年年初，車間領(lǐng)導(dǎo)決定是購置新設(shè)備還是通過維修繼續(xù)使用舊設(shè)備。若購置新設(shè)備，需支付購置費(fèi)，購買單價(jià)如下表第二行所示，舊設(shè)備報(bào)廢無殘值；設(shè)備在使用的生命周期內(nèi)每年需支付一定的維修費(fèi)用， 且年度維修費(fèi)用隨著設(shè)備使用年限的增長而增

14、長，如下表第四行所示。請制定 2011-2015 年的設(shè)備更新計(jì)劃，使得總費(fèi)用最小。（忽略貨幣的時(shí)間價(jià)值）答案： 1, 0, 1, 0, 0(1,12)(0,18)(1,25)(0,40)(0,56)(0,28)(1,56)(1,32)(0,31)(1,39)(1,43)(0,38)(1,47)(0,41)(1,46)(0, 45)(1,54)(0, 49)(1,59)(0,48)(1,54)(0,53)(1,63)(0,53)(1,57)(0,52)(1,62)(0,55)(1,61)(0,60)(1,70)2. 報(bào)童通過訂購報(bào)紙進(jìn)行零售以獲利。已知，報(bào)童訂購報(bào)紙的單位成本為c，銷售單價(jià)p

15、，若報(bào)紙未賣出，則低價(jià)處理的單價(jià)為q 。已知 p c q 。根據(jù)過去的售賣經(jīng)驗(yàn)得知，報(bào)童每日賣出r 份報(bào)紙的概念為P(r)。請問，為使得收益最大化，報(bào)童每天的最佳訂購量Q 為多少？答案： 記報(bào)童每天購進(jìn)n 份報(bào)紙時(shí)的平均收入為G(n)， 如果這天的需求量r n，則他售出r 份，退回n-r 份；如果這天的需求量r>n ，則 n 份將全部售出考慮到需求量為r 的概率是f(r)，所以nG(n) a b r b c n r f r a b nf r 1 r0rn1問題歸結(jié)為在f(r)， a， b， c已知時(shí)，求n 使 G(n)最大通常需求量r 的取值和購進(jìn)量n 都相當(dāng)大，將 r 視為連續(xù)變量更便

16、于分析和計(jì)算，這時(shí)概率f (r)轉(zhuǎn)化為概率密度函數(shù)p(r)， (1)式變成Gnp r drb np rdr 2計(jì)算dG dnnpdrabnpb p r drdrdrdG令dn0 .得到0n pr dr ap r dr b c n使報(bào)童日平均收入達(dá)到最大的購進(jìn)量n 應(yīng)滿足 (3)式 因?yàn)?0 p(r)dr 1， 所以 (3)式又可表為nabp r dr40ac根據(jù)需求量的概率密度p(r)的圖形很容易從(3)式確定購進(jìn)量n在圖 2 中用P1 ，P2 分別表示曲線p(r)下的兩塊面積，則(3)式可記作P1a b5P2b cnn 份報(bào)紙時(shí)，P10 p(r)dr是需求量r 不超過 n 的概率，即賣不完的

17、概率：P2n p(r)dr 是需求量r 超過 n 的概率，所以( 3) 式表明，購進(jìn)的份數(shù) 應(yīng)該使賣不完和賣完的概率之比，恰好等a-b 與退回一份賠b-c 之比.顯然，當(dāng)報(bào)童與報(bào)社簽訂的合同使報(bào)童每份賺錢和賠錢之比越大時(shí)，報(bào)童購進(jìn)的份數(shù)就應(yīng)該越多3. 某投資公司邀請你出資一萬元參加如下游戲，游戲規(guī)則如下：首先，提供給你 100 萬元的原始資本，該游戲分為50 輪。在每一輪中，盈利與虧損的可能性都為50% 。若盈利，凈盈利額為投資額的1.6 倍；若虧損，凈虧損額為投資額的全部。為保證游戲可持續(xù)進(jìn)行，每輪游戲以當(dāng)時(shí)總資產(chǎn)的一半作為投資額，請問：（ 1 ）你的期望收益大約是多少？（2）你是否愿意參加

18、此游戲？答案：設(shè) xt 為第t 輪的初始資金，則xt 1 0.5xt 0.5xt*1.6*0.50.9xt那么，游戲結(jié)束50 輪時(shí)期望收益為50x51 （0.9） 50 *1000.0052*100=0.521不愿意 機(jī)組問題建模（0-1 整數(shù)規(guī)劃） 某發(fā)電站負(fù)責(zé)對本地區(qū)供電，該地區(qū)的總體用電需求每天呈有規(guī)律變化，具體表 現(xiàn)為： 0-t1 時(shí)段：需求量為D1 ； t1-t2 時(shí)段：需求量為D2； t2-24 點(diǎn)時(shí)段：需求量為D3。 該電站有發(fā)電機(jī)組N 組， 第 j 個機(jī)組的發(fā)電能力固定且為S（j j=1 ， 2， ， N） 。 已知S1 S2 K SNmaxD1,D2,D3 。供電系統(tǒng)運(yùn)行要求發(fā)電能力與用電需求 相匹配， 不宜超額發(fā)電，每單位超額發(fā)電將浪費(fèi)成本（包括發(fā)電成本、消解成本）為 w。 因此， 電站將靈活調(diào)整各個發(fā)電機(jī)組的開關(guān)狀態(tài)，以實(shí)現(xiàn)發(fā)電能力與需求的匹配。此外，工程師告知，對于任一機(jī)組，一旦開動，在p 小時(shí)內(nèi)不得關(guān)閉；而一旦關(guān)閉，在q 小時(shí)內(nèi)不得重新啟動。請問，如何決