1、會計學(xué)12第1頁/共159頁3的平均時間）。的平均時間）。 服務(wù)強(qiáng)度服務(wù)強(qiáng)度，即每個服務(wù)臺單，即每個服務(wù)臺單位時間內(nèi)的位時間內(nèi)的平均服務(wù)時間；平均服務(wù)時間；一般有一般有 s ；第2頁/共159頁4第3頁/共159頁5第4頁/共159頁6第5頁/共159頁7eeeee進(jìn)入時刻進(jìn)入時刻離開時刻離開時刻總時間總時間W隊長隊長L由時間段內(nèi)由時間段內(nèi)W個個 e組成的組成的L= eW第6頁/共159頁85) Little公式公式 以上公式對一般泊松輸入以上公式對一般泊松輸入指數(shù)排指數(shù)排隊模型成立。隊模型成立。第7頁/共159頁90nnnPL0()qns mn smLns PmP), 2 , 1 , 0(n

2、PnLqL第8頁/共159頁10第9頁/共159頁11第10頁/共159頁12第11頁/共159頁13W= L/ 5、顧客花在排隊上的平均等待時間：、顧客花在排隊上的平均等待時間：Wq=W-1/u6、平均排隊的顧客數(shù)：、平均排隊的顧客數(shù)：Lq= Wq第12頁/共159頁141 1、例子例子 P216P216 某醫(yī)院急診室同時只能診治某醫(yī)院急診室同時只能診治1 1個病人，個病人，診治時間服從指數(shù)分布，每個病人平均需診治時間服從指數(shù)分布，每個病人平均需要要1515分鐘。病人按泊松分布到達(dá)，平均每分鐘。病人按泊松分布到達(dá)，平均每小時到達(dá)小時到達(dá)3 3人。求該排隊系統(tǒng)的主要數(shù)量指人。求該排隊系統(tǒng)的主要

3、數(shù)量指標(biāo)。標(biāo)。第13頁/共159頁15由題意知：該題是由題意知：該題是M/M/1/ / /FCFS排隊系統(tǒng)排隊系統(tǒng)3 (人小時人小時)， 60154(人小時人小時)故服務(wù)強(qiáng)度為故服務(wù)強(qiáng)度為75. 043 00,25. 075. 011pppnn 其中，其中，p0是急診室空閑的概率，也是病人不必是急診室空閑的概率，也是病人不必等待立即就能就診的概率。等待立即就能就診的概率。第14頁/共159頁1631L133 LW75. 025. 011 WWq此模型的平均有效到達(dá)率，即是到達(dá)率此模型的平均有效到達(dá)率，即是到達(dá)率 病人在急診室內(nèi)外平均逗留時間：病人在急診室內(nèi)外平均逗留時間：病人平均等候時間：病人

4、平均等候時間：(小時小時)45(分鐘分鐘)急診室內(nèi)外的病人平均數(shù)：急診室內(nèi)外的病人平均數(shù)：（人）（人）（小時）（小時）30.752.25qqLW急診室外排隊等待的病人平均數(shù)：急診室外排隊等待的病人平均數(shù)：(人人)第15頁/共159頁17(4) 病人排隊等待時間病人排隊等待時間(Wq)。第16頁/共159頁18第17頁/共159頁19第18頁/共159頁20第19頁/共159頁21第20頁/共159頁22第七章第七章 動態(tài)規(guī)劃動態(tài)規(guī)劃第21頁/共159頁23第22頁/共159頁24第23頁/共159頁25第24頁/共159頁26第25頁/共159頁27第26頁/共159頁28第27頁/共159頁

5、29第28頁/共159頁30第29頁/共159頁31第30頁/共159頁32第31頁/共159頁33第32頁/共159頁34)(kkkkksusTs,1第33頁/共159頁35第34頁/共159頁36第35頁/共159頁37)s(p,s(Rkkkk第36頁/共159頁38)s(p,s(Rkkkkn,2 , 1k)s(p,s(Ropt)s(fkkkk)s(PpkkkKk第37頁/共159頁39)s(u,),s(u),s(unn1k1kkkn, 2 , 1k)s(u,),s(u),s(u)s(pnn1k1kkkkkn,2 , 1k,u,u,upn1kkk第38頁/共159頁40第39頁/共159頁

6、41111112()(),npssusuu第40頁/共159頁42n,2 ,1kUuSs)u,s(Ts. t . s)u,s,u,s,u,s(RRoptkkkkkkk1knn2211uun1第41頁/共159頁431 , 2 , 1n,nk)s(f)s(u,s(gmin)s(f0)s(f1k1kkkkk)s(Uukk1n1nkkk（邊界條件）（邊界條件）階段指標(biāo)階段指標(biāo)第42頁/共159頁44第43頁/共159頁45第44頁/共159頁46第45頁/共159頁47第46頁/共159頁48第47頁/共159頁49第48頁/共159頁50動態(tài)規(guī)劃基本方程動態(tài)規(guī)劃基本方程 fn+1(sn+1) =

7、0 (邊界條件邊界條件) fk(sk) = opt ugk ( sk , uk ) + fk+1(sk+1) k = n , n-1, , 1第49頁/共159頁51第50頁/共159頁52第51頁/共159頁531 1、例子例子 P176P176用用遞推方程遞推方程求解最短路徑問題求解最短路徑問題第52頁/共159頁54第53頁/共159頁5511()()min (,)()4,3,2,1kkkkkkkkkkuUsfsgs ufsk第54頁/共159頁564444444455()( )min ( ,)( )uUsf sg s uf s s4U4(s4)s5g4(s4,u4) g4(s4,u4)

8、+f5(s5)f4(s4) 最優(yōu)決策最優(yōu)決策u4*C1C1EE55+0=5*5C1EC2C2EE88+0=8*8C2E第55頁/共159頁57)(),(min)(44333)(33333sfusgsfsUu從從 f4(s4) 到到f3(s3) 的遞推過程用表格表示如下表：的遞推過程用表格表示如下表：s3U3(s3)s4g3(s3,u3) g3(s3,u3)+f4(s4) f3(s3)最優(yōu)決策u3*B1B1C1B1C2C1C2 6 5 6+5=11* 5+8=1311B1C1B2B2C1B2C2C1C2 98 9+5=14* 8+8=1614B2C1第56頁/共159頁58)(),(min)(3

9、3222)(22222sfusgsfsUu第57頁/共159頁59s2U2(s2)s3g2(s2,u2) g2(s2,u2)+f3(s3) f2(s2)最優(yōu)決策最優(yōu)決策u2*A1A1B1A1B2B1B2 6 56+11=17*5+14=1917A1B1A2A2B1A2B2B1B2 8 68+11=19*6+14=2019A2B1A3A3B1A3B2B1B2 7 47+11=18*4+14=18*18A3B1A3B2第58頁/共159頁60從從 f2(s2)到到 f1(s1)的遞推過程用表格的遞推過程用表格 表示如下：表示如下： )(),(min)(22111)(11111sfusgsfsUu

10、s1U1(s1)s2g1(s1,u1) g1(s1,u1)+f2(s2) f1(s1)最優(yōu)決策最優(yōu)決策u1*S S A1S A2SA3A1A2A34334+17=21*3+19=223+18=21*21S A1S A3第59頁/共159頁61第60頁/共159頁62第61頁/共159頁63第62頁/共159頁64第63頁/共159頁65第64頁/共159頁66第65頁/共159頁67第66頁/共159頁68第67頁/共159頁692 2、基本可行解的最優(yōu)性檢驗(yàn)、基本可行解的最優(yōu)性檢驗(yàn) 第68頁/共159頁70第69頁/共159頁71 利用位勢求利用位勢求非非基變量基變量xij的檢驗(yàn)數(shù)：的檢驗(yàn)數(shù)

11、： ij = cij - ui - vj i = 1, , m ; j = 1, , n第70頁/共159頁72第71頁/共159頁733 3、求新的基本可行解、求新的基本可行解第72頁/共159頁7474 在運(yùn)輸問題的表上作業(yè)法中，換基的過程在運(yùn)輸問題的表上作業(yè)法中，換基的過程是如下進(jìn)行：是如下進(jìn)行：第73頁/共159頁7575第74頁/共159頁7676第75頁/共159頁7777第76頁/共159頁781、例子例子 P99 第77頁/共159頁79最小元素法最小元素法 B1 B2 B3 B4 產(chǎn)量 ai A1 3 11 3 4 10 3 7 A2 1 3 9 2 1 8 4 A3 7 4

12、 6 10 5 3 9 銷量 bj 3 6 5 6 20 第78頁/共159頁80 vj -3 4 -2 5 ui B1 B2 B3 B4 產(chǎn)量產(chǎn)量 ai 5 A1 3 1 11 2 3 4 10 3 7 4 A2 1 3 9 1 2 *1 8 -1 4 0 A3 7 10 4 6 10 12 5 3 9 銷量銷量 bj 3 6 5 6 20 第79頁/共159頁81 所有所有 ij 0，得到，得到最優(yōu)解最優(yōu)解 x13 = 5,x14 = 2,x21 = 3,x24 = 1, x32 = 6, x34 = 3, 其余其余 xij = 0 ; 最優(yōu)值最優(yōu)值： f* = 35+102+13+81+

13、46+53 = 85第80頁/共159頁822、用表上作業(yè)法求解下列運(yùn)輸問題用表上作業(yè)法求解下列運(yùn)輸問題 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A1847290A25835100A37729120銷量銷量705011080第81頁/共159頁83第82頁/共159頁84第83頁/共159頁85第84頁/共159頁86第85頁/共159頁87第86頁/共159頁88第87頁/共159頁89 沒沒有有非非負(fù)負(fù)限限制制321432143143214321, 0,1053042260272252375maxxxxxxxxxxxxxxxxxxxZ第88頁/共159頁90 沒有非負(fù)限制沒有非負(fù)限制432

14、1443214314321, 0, 051030422602722523xxxxxxxxxxxxxxxx第89頁/共159頁91 0,725472123122510306025min5432154213213132154321yyyyyyyyyyyyyyyyyyyyyyf沒沒有有非非負(fù)負(fù)限限制制第90頁/共159頁92無符號限制42314321432143214321, 0,1067912857653432maxxxxxxxxxxxxxxxxxxxxxZ第91頁/共159頁93第92頁/共159頁9494第93頁/共159頁9595nmjaaappBppppAbBbaccbcfTmjjjjjj

15、nmiijijjmiii, 1,),(,21121111 第94頁/共159頁9696第95頁/共159頁9797第96頁/共159頁9898第97頁/共159頁9999cI -2 -3 -4 0 0 cB xB b x1 x2 x3 x4 x5 -3 x2 2/5 0 1 -1/5 -2/5 1/5 -2 x1 11/5 1 0 7/5 -1/5 -2/5 j 0 0 -9/5 -8/5 -1/5 cI -2 -3 -4+c3 0 0 cB xB b x1 x2 x3 x4 x5 -3 x2 2/5 0 1 -1/5 -2/5 1/5 -2 x1 11/5 1 0 7/5 -1/5 -2/5

16、 j 0 0 -9/5+c3 -8/5 -1/5 從表中看到從表中看到3= c3+c3-(c2a13+c1a23 ) 可得到可得到c3 9/5 時，原最優(yōu)解不變。時，原最優(yōu)解不變。第98頁/共159頁100100第99頁/共159頁101101b增加變量增加變量增加約束增加約束第100頁/共159頁102102c i 2 3 0 0 0 cB xB B x1 x2 x3 x4 x5 2 x1 4 1 0 0 1/4 0 0 x5 4 0 0 -2 1/2 1 3 x2 2 0 1 1/2 -1/8 0 j 0 0 -1.5 -1/8 0 ci 2 3+c c2 0 0 0 cB xB B x1

17、 x2 x3 x4 x5 2 x1 4 1 0 0 1/4 0 0 x5 4 0 0 -2 1/2 1 3+c c2 x2 2 0 1 1/2 -1/8 0 j 0 0 -1.5 -C C2/2 -1/8+C C2/8 0 由由j=cj-(c1a1j+c5a5j+(c2+c2)a2j) j=3,4可得到可得到 -3c21時，原最優(yōu)解不變。時，原最優(yōu)解不變。第101頁/共159頁103103第102頁/共159頁104104ci 2 3 0 0 0 cB x B b x1 x2 x3 x4 x5 2 x1 4 1 0 0 1/4 0 0 x5 4 0 0 -2 1/2 1 3 x2 2 0 1

18、1/2 -1/8 0 j 0 0 -1.5 -1/8 0 第103頁/共159頁105105各列分別對應(yīng)各列分別對應(yīng) b1、b2、b3 的單一變化的單一變化因此，設(shè)因此，設(shè) b1 增加增加 4，則，則 x1 , x5 , x2分別變?yōu)椋悍謩e變?yōu)椋?+04=4, 4+(-2)4=-40, 2+0.54=4用用對偶單純形法對偶單純形法進(jìn)一步求解，可得：進(jìn)一步求解，可得：第104頁/共159頁106106c i 2 3 0 0 0 cB xB B x1 x2 x3 x4 x5 2 x1 4 1 0 0 1/4 0 0 x5 -4 0 0 -2 1/2 1 3 x2 4 0 1 1/2 -1/8 0

19、j -20 0 0 -1.5 -1/8 0 2 x1 4 1 0 0 1/4 0 0 x3 2 0 0 1 -1/4 -1/2 3 x2 3 0 1 0 0 1/4 j -17 0 0 0 -1/2 -3/4 于是，于是，x* = ( 4, 3, 2, 0, 0 )T f* = 17第105頁/共159頁107107第106頁/共159頁108108第107頁/共159頁109109ci 2 3 0 0 0 5 cB xB b x1 x2 x3 x4 x5 x6 2 x1 4 1 0 0 1/4 0 1.5 0 x5 4 0 0 -2 1/2 1 2 3 x2 2 0 1 1/2 -1/8 0

20、 0.25 j 0 0 -1.5 -1/8 0 1.25 用單純形法進(jìn)一步求解，可得：用單純形法進(jìn)一步求解，可得：x* = ( 1,1.5,0,0,0,2 )T f* = 16.5666616,pccpBpTB第108頁/共159頁110110第109頁/共159頁111111ci 2 3 0 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 2 x1 4 1 0 0 1/4 0 0 0 x5 4 0 0 -2 1/2 1 0 3 x2 2 0 1 1/2 -1/8 0 0 0 x6 15 3 2 0 0 0 1 j 0 0 -1.5 -1/8 0 0 對表中新的一行利用矩陣初等

21、行變對表中新的一行利用矩陣初等行變換進(jìn)行處理，可得新的對偶單純形表：換進(jìn)行處理，可得新的對偶單純形表：第110頁/共159頁112112ci 2 3 0 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 2 x1 4 1 0 0 1/4 0 0 0 x5 4 0 0 -2 1/2 1 0 3 x2 2 0 1 1/2 -1/8 0 0 0 x6 -1 0 0 -1 -1/2 0 1 j 0 0 -1.5 -1/8 0 0 第111頁/共159頁113113靈敏度分析靈敏度分析 1第112頁/共159頁114114第113頁/共159頁115115212(2)0cb(1)(3) 影

22、響第114頁/共159頁116116第115頁/共159頁117第116頁/共159頁118118第117頁/共159頁119第二章第二章 單單 純純 形形 法法第118頁/共159頁120標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：目標(biāo)函數(shù)：Max z = c1x1 + c2x2 + + cnxn 約束條件：約束條件：a11x1 + a12x2 + + a1nxn = b1a21x1 + a22x2 + + a2nxn = b2 . . .am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0 0第119頁/共159頁121 線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個線性規(guī)劃的標(biāo)準(zhǔn)形式有如下

23、四個特點(diǎn)：特點(diǎn)：目標(biāo)最大化、約束為等目標(biāo)最大化、約束為等式、決策變量均非負(fù)、右端項(xiàng)式、決策變量均非負(fù)、右端項(xiàng)非負(fù)。非負(fù)。 對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，轉(zhuǎn)換成標(biāo)準(zhǔn)形式進(jìn)行求解。問題，轉(zhuǎn)換成標(biāo)準(zhǔn)形式進(jìn)行求解。 第120頁/共159頁1221.極小化目標(biāo)函數(shù)的問題：極小化目標(biāo)函數(shù)的問題： 設(shè)目標(biāo)函數(shù)為設(shè)目標(biāo)函數(shù)為 Min f = c1x1 + c2x2 + + cnxn 則可以令則可以令z-f ，該極小化問題與下，該極小化問題與下面的極大化問題有相同的最優(yōu)解，即面的極大化問題有相同的最優(yōu)解，即 Max z = -c1x1 - c2x2 - - cnxn 但必須注意，

24、盡管以上兩個問題的最但必須注意，盡管以上兩個問題的最優(yōu)解相同，但他們最優(yōu)解的目標(biāo)函數(shù)值優(yōu)解相同，但他們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個符號，即卻相差一個符號，即 Min f - Max z第121頁/共159頁1232、約束條件不是等式的問題：、約束條件不是等式的問題： 設(shè)約束條件為設(shè)約束條件為 ai1 x1+ai2 x2+ +ain xn bi 可以引進(jìn)一個新的變量可以引進(jìn)一個新的變量s ，使它等于，使它等于約束右邊與左邊之差約束右邊與左邊之差 s =bi(ai1 x1 + ai2 x2 + + ain xn ) 顯然，顯然，s 也具有非負(fù)約束，即也具有非負(fù)約束，即s0， 這時新的約束條件成為這

25、時新的約束條件成為 ai1 x1+ai2 x2+ +ain xn+s = bi第122頁/共159頁124 當(dāng)約束條件為當(dāng)約束條件為 ai1 x1+ai2 x2+ +ain xn bi 時，類似地令時，類似地令 s =(ai1 x1+ai2 x2+ +ain xn)- bi 顯然，顯然，s 也具有非負(fù)約束，即也具有非負(fù)約束，即s0，這，這時新的約束條件成為時新的約束條件成為 ai1 x1+ai2 x2+ +ain xn-s = bi 第123頁/共159頁125 為了使約束由不等式成為等式為了使約束由不等式成為等式而引進(jìn)的變量而引進(jìn)的變量 s 稱為稱為“松弛變量松弛變量”。如果原問題中有若干個

26、非等式約束，如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時，必須對則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時，必須對各個約束引進(jìn)不同的松弛變量。各個約束引進(jìn)不同的松弛變量。 第124頁/共159頁1263.3.變量無符號限制的問題：變量無符號限制的問題：在標(biāo)準(zhǔn)形式中，必須每一個變量均有在標(biāo)準(zhǔn)形式中，必須每一個變量均有非負(fù)約束。當(dāng)某一個變量非負(fù)約束。當(dāng)某一個變量xj沒有非負(fù)約沒有非負(fù)約束時，可以令束時，可以令 xj = xj- xj”其中其中 xj0，xj”0即用兩個非負(fù)變量之差來表示一個無即用兩個非負(fù)變量之差來表示一個無符號限制的變量，當(dāng)然符號限制的變量，當(dāng)然xj的符號取決于的符號取決于xj和和xj”的大

27、小。的大小。第125頁/共159頁1274.4.右端項(xiàng)有負(fù)值的問題右端項(xiàng)有負(fù)值的問題：在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個分量非負(fù)。當(dāng)某一個右端項(xiàng)系數(shù)為個分量非負(fù)。當(dāng)某一個右端項(xiàng)系數(shù)為負(fù)時，如負(fù)時，如 bi0，則把該，則把該等式約束兩端等式約束兩端同時乘以同時乘以-1，得到：，得到： -ai1 x1-ai2 x2- -ain xn = -bi第126頁/共159頁128線性規(guī)劃的圖解法線性規(guī)劃的圖解法第127頁/共159頁129129第128頁/共159頁130130第129頁/共159頁131131第130頁/共159頁132132第131頁/共159頁1331

28、33第132頁/共159頁134134第133頁/共159頁135135第134頁/共159頁136136第135頁/共159頁137137x2 0 x1 03x1+ 2x2 65 2x1+ x2 40 3x2 75第136頁/共159頁138138第137頁/共159頁139139第138頁/共159頁140140第第3 3步圖示步圖示 作出目標(biāo)函數(shù)等值線作出目標(biāo)函數(shù)等值線函數(shù)值增大第139頁/共159頁1411411第140頁/共159頁142142根據(jù)上面的過程根據(jù)上面的過程 我們得到這個線性規(guī)劃的我們得到這個線性規(guī)劃的 最優(yōu)解最優(yōu)解 x1=5、x2=25， 最優(yōu)值最優(yōu)值 z = 70000即最優(yōu)方案為生產(chǎn)甲產(chǎn)品即最優(yōu)方案為生產(chǎn)甲產(chǎn)品5 5件、乙產(chǎn)件、乙產(chǎn)品品2525件，可獲得最大利潤為件，可獲得最大利潤為7000070000元元。第141頁/共159頁143第142頁/共159頁144單純形法的表格計算單純形法的表格計算第143頁/共159頁145第144頁/共159頁146第145頁/共