【正文】 n!ρn=ρ=25(人 ) n=0 ∞ 代入 ∑Pn=1 n=0 與最優(yōu)化問題 完全消除排隊(duì)現(xiàn)象是不現(xiàn)實(shí)的 ， 那會(huì)造成服務(wù)人員和設(shè)施的嚴(yán)重浪費(fèi) ， 但是設(shè)施的不足和低水平的服務(wù) ， 又將引起太多的等待 ， 從而導(dǎo)致生產(chǎn)和社會(huì)性損失 。 從經(jīng)濟(jì)角度考慮 ， 排隊(duì)系統(tǒng)的費(fèi)用應(yīng)該包含以下兩個(gè)方面：一個(gè)是 服務(wù)費(fèi)用 ，它是服務(wù)水平的 遞增函數(shù) ；另一個(gè)是顧客等待的 機(jī)會(huì)損失 (費(fèi)用 )， 它是服務(wù)水平的遞減函數(shù) 。 兩者的總和呈一條 U形曲線 。 與最優(yōu)化問題 系統(tǒng)最優(yōu)化的目標(biāo)是尋求 U曲線的最小點(diǎn) 。 這種意義下 ， 排隊(duì)系統(tǒng)的最優(yōu)化問題通常分為兩類：一類稱之系統(tǒng)的靜態(tài)最優(yōu)設(shè)計(jì) ， 目的在于使設(shè)備達(dá)到最大效益 ， 或者說 ， 在保證一定服務(wù)質(zhì)量指標(biāo)的前題下 ， 要求機(jī)構(gòu)最為經(jīng)濟(jì)；另一類叫作系統(tǒng)動(dòng)態(tài)最優(yōu)運(yùn)營 ， 是指一個(gè)給定排隊(duì)系統(tǒng) ， 如何運(yùn)營可使某個(gè)目標(biāo)函數(shù)得到最優(yōu) 。 歸納起來 ， 排隊(duì)系統(tǒng)常見的優(yōu)化問題在于： 與最優(yōu)化問題 (1)確定最優(yōu)服務(wù)率 ?*； (2)確定最佳服務(wù)臺(tái)數(shù)量 s*； (3)選擇最為合適的服務(wù)規(guī)則； (4)確定上述幾個(gè)量的最優(yōu)組合 。 本節(jié)僅就 ?， s這兩個(gè)決策變量的分別單獨(dú)優(yōu)化 ， 介紹兩個(gè)較簡單的模型 ，以便讀者了解排隊(duì)系統(tǒng)優(yōu)化設(shè)計(jì)的基本思想 。 與最優(yōu)化問題 一 、 M／ M／ 1／ ∞ 系統(tǒng)的最優(yōu)平均服務(wù)率 ?* : 設(shè) C1—— 當(dāng) ? =1時(shí)服務(wù)系統(tǒng)單位時(shí)間的平均費(fèi)用 Cw—— 平均每個(gè)顧客在系統(tǒng)逗留單位時(shí)間的損失； y—— 整個(gè)系統(tǒng)單位時(shí)間的平均總費(fèi)用 。 其中 C1， Cw均為可知 。 則目標(biāo)函數(shù)為 (652) Lccy w?? ?1 與最優(yōu)化問題 將 L= ? ／ (? ?)， 代入上式 ， 得 易見 y是關(guān)于決策變量 ?的一元非線性函數(shù) 由一階條件 解得駐點(diǎn) (653) ??????? 11 wccy0)(121 ???? ???? wccddy1* / ccw ??? ?? 與最優(yōu)化問題 根號(hào)前取正號(hào)是為了保證 ? 1， 即?* ? 。 這樣 ， 系統(tǒng)才能達(dá)到穩(wěn)態(tài) 。 又由二階條件 (因 ?? ） 可知 (653)給出的 ?*為 (?,∞)上的全局唯一最小點(diǎn) 。 將 ?*代入 (652)中 ， 可得最小總平均費(fèi)用 0)(2322???????wcdyd?? wcccy 11* 2?? （ 654） 與最優(yōu)化問題 另外 ， 若設(shè) cw為平均每個(gè)顧客在隊(duì)列中等待單位時(shí)間的損失 ， 則需用 取代式 (652)中的 L， 這時(shí)類似可得一階條件： 這是一個(gè)關(guān)于 ?的四次方程 ， 一般采用數(shù)值法 (如牛頓法 )確定其根 ?*。 )(2??????qL022 322213141 ????? ???????? ww ccccc 與最優(yōu)化問題 二 、 M /M /s /∞ 系統(tǒng)的最優(yōu)服務(wù)臺(tái)數(shù) s* 設(shè)目標(biāo)函數(shù)為 (655) 其中： s —— 并聯(lián)服務(wù)臺(tái)的個(gè)數(shù) (待定 )； f (s) —— 整個(gè)系統(tǒng)單位時(shí)間的平均總費(fèi)用 ， 它是關(guān)于服務(wù)臺(tái)數(shù) s 的函數(shù)； c2—— 平均每個(gè)服務(wù)臺(tái)的單位時(shí)間費(fèi)用； )()( 2 sLcscsf w??cw—— 平均每個(gè)顧客在系統(tǒng)中逗留 (或等待 )單位時(shí)間的損失； L(s)—— 平均隊(duì)長 (或平均等待隊(duì)長 )， 它是關(guān)于服務(wù)臺(tái)數(shù) s 的函數(shù)； 要確定最優(yōu)服務(wù)臺(tái)數(shù) s*∈ {1， 2， … }，使 由于 s取值離散 ， 不能采用微分法或非線性規(guī)劃的方法 ， 因此我們采用差分法 。顯然有 （ 656） )()(m i n)( 2* sLcscsfsf w????????????)1()()1()(****sfsfsfsf 與最優(yōu)化問題 把式 （ 655） 代人式 (656) 中 ， 得 可得 令 (657) 依次計(jì)算 s =1， 2， … 時(shí)的 L(s)值及每一差值 L(s) L(s+1) ， 根據(jù) ? 落在哪兩個(gè)差值之間就可確定 s*。 ???????????????)1()1()()1()1()(**2**2**2**2sLcscsLcscsLcscsLcscwwww)s(L)s(Lcc)s(L)s(L **w** ?????? 11 2wcc 2??103 例 : 興建一座港口碼頭 ， 只有一個(gè)裝卸船只的泊位 。 要求設(shè)計(jì)裝卸能力 。 裝卸能力單位為 （ 只 /日 ） 船數(shù) 。已知：單位裝卸能力的平均生產(chǎn)費(fèi)用a=2千元 ， 船只逗留每日損失 b=元 。 船只到達(dá)服從泊松分布 ， 平均速率 λ=3只 /日 。 船只裝卸時(shí)間服從負(fù)指數(shù)分布 。 目標(biāo)是每日總支出最少 。 應(yīng) 用 舉 例 解： λ=3 , μ待定 模型 M/M/1/∞/∞ 隊(duì)長 Ls =λ/(μλ) 總費(fèi)用 C = aμ+bLs= aμ+bλ/(μλ) 求極值 （ 最小值 ） 求導(dǎo) d C / dμ = a + (bλ)/(μλ)2 = 0 應(yīng) 用 舉 例 得 : μλ= 177。 (bλ/a)1/2（ 根據(jù)題意舍負(fù) ） 所以 μ=λ+(bλ/a)1/2=3+()1/2=(只 /日 ) 105 例 : 建造一口碼頭 ， 要求設(shè)計(jì)裝卸船只的泊位數(shù) 。 已知 :預(yù)計(jì)到達(dá)λ=3只 /天 ， 泊松流；裝卸 μ=2只 /天 ，負(fù)指數(shù)分布 。 裝卸費(fèi)每泊位每天 a=2千元 ， 停留損失費(fèi) b= /日 。 目標(biāo)是總費(fèi)用最少 。 應(yīng) 用 舉 例 解 :模型 M/M/c/∞/∞ c 待定 總費(fèi)用： F = a c + b Ls(c) c 是離散變量 ， 無法用求導(dǎo)來解 。 106 應(yīng) 用 舉 例 考慮 : M/M/c/∞/∞ 要求 : ρ=λ/(cμ) 1 即 c(λ/μ)= 討論 c=2,3,4… c1 P0=[∑/n﹗ ρn+cc/c!ρc/(1 ρ)]1 n=0 Lq= ccρc+1/c!(1ρ)2 P0 L=Lq+λ/μ 應(yīng) 用 舉 例 結(jié)論： c =3 即設(shè)計(jì)三個(gè)裝卸泊位可使每天的總費(fèi)用最少為 。 M /M/ 2/ ? / ? M /M/ 3/ ? / ? M /M/ 4/ ? / ?P01/7= 86 4/19= 053 40/181=0. 22099Lq 27/14= 2857 9/83= 684 81/1810=0 .04475Ls 24/7= 857 33/19= 3684 1398/905= 5F 64/7= 286 327/38=8. 60526 9337/905= 13ρ =1/2 ρ =3/4 ρ =3/8 108 與最優(yōu)化問題 例 : 某市政府的上訪接待室每天平均接待來訪 48次 ， 來訪者為泊松流 ，上訪所造成的損失為平均每次 20元 。該室每設(shè)置一名接待員的服務(wù)成本為平均每天 8元 ， 接待時(shí)間為指數(shù)分布 ，平均每天可接待 25次 。 問應(yīng)設(shè)置幾名接待員能使平均總費(fèi)用為最小 ? 解 : 此為 M／ M／ s／ ∞系統(tǒng) ， 有 109 與最優(yōu)化問題 c2＝ 8元／人天 ， cw＝ 20元／天次 ， ?＝ 48次／天 ， ?＝ 25次／天 ， 則按式 (657)得 ＝ 另有 208??2548 ??????ssssss, ???????? ?????110 與最優(yōu)化問題 把 代入式 (615)， 得 又由式 (617)、 式 (618) 得 把 , P0代入上式整理可得 ??? ?1,1100 )()!1()(!)(????????????? ?sksksskP???? ??? 02)1(!PsLs??? ?1, 與最優(yōu)化問題 當(dāng) S=1時(shí) ， ? = ? =＞ 1， 不滿足系統(tǒng)達(dá)到穩(wěn)態(tài)的條件 ?＜ 1， 故這時(shí) L(1)=∞。 依次計(jì)算當(dāng) s＝ 2， 3， … 時(shí)的值及其差值L(s)L(s+1) ， 如表 63所示 。 由表 63可知： S*＝ 4(人 ) )(!)()()!1()()()(101????????????????skskskssssL112 據(jù)此 (s*=4)可得最小總平均費(fèi)用： (元／天 ) 故該室應(yīng)設(shè)置 4名接待員可使每天總平均費(fèi)用達(dá)到最小 ， 為 。 s＝ 2， 3， … 時(shí)的 L(s)值及其差值 L(s)L(s+1)如下面表 63 與最優(yōu)化問題 26730 6 322048..)s(f *?????作業(yè)： P323— 1, 3, 5 s 1 2 3 4 5 … L(s) ? … L(s)L(s+1) ? … … 表 6－ 3