下面是范文網(wǎng)小編整理的運(yùn)籌學(xué)與系統(tǒng)工程上機(jī)實(shí)驗(yàn)指導(dǎo)書實(shí)驗(yàn)五(管理運(yùn)籌學(xué)上機(jī)實(shí)驗(yàn))，供大家參閱。

　　運(yùn)籌學(xué)與系統(tǒng)工程上機(jī)實(shí)驗(yàn)指導(dǎo)書 機(jī)電學(xué)院工業(yè)工程專業(yè) 2013-2014（1）學(xué)期 上機(jī)實(shí)驗(yàn)五：應(yīng)用 Lingo 求解動態(tài)規(guī)劃和排隊(duì)論問題 一、 實(shí)驗(yàn)?zāi)康?在熟練編寫和運(yùn)行 Lingo 程序的基礎(chǔ)上，應(yīng)用 Lingo 進(jìn)行求解動態(tài)規(guī)劃和排隊(duì)論等深層次優(yōu)化問題的練習(xí)。

　　二、 實(shí)驗(yàn)要求 1、根據(jù)本指導(dǎo)書學(xué)習(xí) Lingo 對典型動態(tài)規(guī)劃問題進(jìn)行建模和求解。

　　2、根據(jù)本指導(dǎo)書學(xué)習(xí)排隊(duì)論相關(guān)函數(shù)的具體使用方法，對典型的隨機(jī)服務(wù)系統(tǒng)問題進(jìn)行建模和求解。

　　3、獨(dú)立完成相關(guān)應(yīng)用題目的分析、建模和應(yīng)用 Lingo 軟件的求解過程。

　　三、 相關(guān)知識 1、動態(tài)規(guī)劃問題模型及典型應(yīng)用 動態(tài)規(guī)劃（Dynamic Programming）是將一個大型、復(fù)雜的問題轉(zhuǎn)換為若干階段的子問題，從而將動態(tài)的多階段問題簡化為靜態(tài)的單階段決策問題，一般需要采用遞歸算法進(jìn)行求解。動態(tài)規(guī)劃問題的一般模型為：

　　動態(tài)規(guī)劃的典型應(yīng)用包括：最短路徑問題、動態(tài)生產(chǎn)計(jì)劃問題、資源配置問題、背包問題、旅行商問題、隨機(jī)性采購問題、設(shè)備更新問題等。按照決策變量取值的不同，也可以分為連接型動態(tài)規(guī)劃和離散型動態(tài)規(guī)劃問題。無論是連續(xù)問題還是離散問題，動態(tài)規(guī)劃解決問題的前提條件是：可將問題劃分為 k 個階段（k=1,2,…,n），并能構(gòu)建多階段模型（最優(yōu)指標(biāo)函數(shù) Vk,n，狀態(tài) Sk、決策 uk、狀態(tài)轉(zhuǎn)移方程 Tk）。

　　2、隨機(jī)服務(wù)系統(tǒng)相關(guān) Lingo 函數(shù) 隨機(jī)服務(wù)系統(tǒng)由輸入過程（反映顧客總體的特征）、排隊(duì)規(guī)則（反映隊(duì)伍特征）及服務(wù)機(jī)構(gòu)（反映服務(wù)臺的特征）所組成，對隨機(jī)服務(wù)系統(tǒng)的描述如圖 1所示，可用符號 M/M/1 表示泊松輸入、負(fù)指數(shù)服務(wù)、一個服務(wù)臺組成的隨機(jī)服務(wù)系統(tǒng)。

　　圖 1 隨機(jī)服務(wù)系統(tǒng)的描述 描述排隊(duì)系統(tǒng)的主要數(shù)量指標(biāo)有：隊(duì)長 L=正在服務(wù)的顧客數(shù) Ls+等待隊(duì)長Lq，顧客的平均停留時間 W=顧客的平均等待時間 Wq+平均服務(wù)時間 Ws。單位時間內(nèi)顧客到達(dá)率 λ、單位時間的服務(wù)率 μ。它們之間關(guān)系的主要公式為：

　　1 LW? ? ?? ?? （1）

　　1 1 ( )qW W W?? ? ? ? ? ?? ? ? ? ?? ?s （2） （1）等待制排隊(duì)模型 1）Lingo 函數(shù)@PEB(ρ, S)：返回到達(dá)負(fù)荷為 ρ，服務(wù)系統(tǒng)有 S 個服務(wù)臺，且允許排隊(duì)時系統(tǒng)繁忙的概率，也就是顧客等待的概率 Pwait； 2）等待制排隊(duì)模型相關(guān)參數(shù)計(jì)算 ①顧客等待的概率 Pwait Pwait=@PEB(ρ,S)， 其中系統(tǒng)到達(dá)負(fù)荷 ρ=λ/μ， ②顧客平均等待時間（Wq）：( )waitqPWS ? ??? ③顧客平均停留時間（W），隊(duì)長（L）和排隊(duì)長（Lq）：

　　（2）損失制排隊(duì)模型 1）Lingo 函數(shù)@PEL(ρ,S)返回到達(dá)負(fù)荷為 ρ，服務(wù)系統(tǒng)有 S 個服務(wù)器，且不允許排隊(duì)時的損失概率，也就是顧客得不到服務(wù)離開的概率 Plost； 2）損失制排隊(duì)模型相關(guān)參數(shù)計(jì)算 ①顧客離開的概率 Plost Plost=@PEL(ρ,S)， 其中系統(tǒng)到達(dá)負(fù)荷 ρ=λ/μ， ②單位時間內(nèi)平均進(jìn)入系統(tǒng)的顧客數(shù) λe，即系統(tǒng)的有效到達(dá)率：λe=λ(1-Plost) ③系統(tǒng)的相對通過能力：Q=1-Plost ④系統(tǒng)在單位時間內(nèi)占用服務(wù)臺的均值 L=λe/μ。

　　⑤系統(tǒng)服務(wù)臺的效率 η=L/S ⑥顧客在系統(tǒng)內(nèi)平均停留時間 W=1/μ。

　?。?）有限源排隊(duì)模型 1）Lingo 函數(shù)@PFS(ρ, S, K)返回當(dāng)?shù)竭_(dá)負(fù)荷為 ρ，顧客數(shù)為 K，服務(wù)臺數(shù)量為 S 時，有限源的泊松服務(wù)系統(tǒng)等待或返修顧客數(shù)的期望值。

　　2）有限源排隊(duì)模型基本參數(shù) ①平均隊(duì)長 L=@PFS(Kρ, S, K)，其中系統(tǒng)到達(dá)負(fù)荷 ρ=λ/μ。

　?、趩挝粫r間平均進(jìn)入系統(tǒng)的顧客數(shù) λe=λ(K-L) ③顧客處于正常情況的概率 P=K-L/K ④每個服務(wù)臺的工作強(qiáng)度 Pwork=λe/Sμ 四、 動態(tài)規(guī)劃模型與求解 1、最短路徑問題 （1）問題描述：假設(shè)有如下的城市網(wǎng)絡(luò)圖，每兩點(diǎn)之間的距離已知(已將距離值標(biāo)在線上)，求從第任意一個城市到第 10 個城市的最短距離。

　　圖 2 城市網(wǎng)絡(luò) （2）模型 階段變量：k=1，2，…，10 狀態(tài)變量：S k 表示第 k 階段到第 k+1 階段的距離 決策變量：u k (S k )=D(X,Y) 狀態(tài)轉(zhuǎn)移方程：S k+1 =T(S k ，u k ) 指標(biāo)函數(shù)：F k (S k ) （3）求解過程：

　?。?）Lingo 程序 model: SETS: CITIES /1..10/: F; ! 城市集合 CITIES，屬性F ; ROADS(CITIES, CITIES)/ ! 路線集合 ROADS，屬性D ; 1,2 1,3 1,4 2,5 2,6 2,7 3,5 3,6 3,7 4,5 4,6 5,8 5,9 6,8 6,9 7,8 7,9 8,10 9,10/: D; ! D(i, j) 從第i個城市到第j個城市的距離; ENDSETS DATA: !由于并非所有城市間都有道路直接連接，所以將道路具體列出; D = 1 5 2 13 12 11 6 10 4 12 14 3 9 6 5 8 10 5 2; ENDDATA ! 如果本身就在第10個城市，則最短距離就是0; F(@SIZE(CITIES)) = 0; ! 從任意城市（除了第10個城市）到第10個城市的距離; @FOR(CITIES(i)| i #LT# @SIZE(CITIES): F(i) = @MIN(ROADS(i, j): D(i, j) + F(j)) ); （5）Lingo 求解結(jié)果：

　　2、多階段生產(chǎn)計(jì)劃問題 （1） 問題描述：

　　設(shè)某種材料可用于兩種方式生產(chǎn)，用后除產(chǎn)生效益外，還有一部分回收，表1 所示為生產(chǎn)方式、效益及回收之間的關(guān)系，若有材料 100 個單位，計(jì)劃進(jìn)行 3個階段的生產(chǎn)，如何投入材料，使總效益達(dá)到最大? 表 1 生產(chǎn)方式、效益和回收之間的關(guān)系 生產(chǎn)方式 1 2 效益函數(shù) 回收函數(shù) （2） 模型

　　階段變量：k=1，2，3 狀態(tài)變量：S k 表示第 k 階段開始生產(chǎn)時原料的數(shù)量 決策變量：u k (S k )表示從第 k 階段原料的數(shù)量 Sk 中分配給 1 型產(chǎn)品的數(shù)量 狀態(tài)轉(zhuǎn)移方程：S k+1 = k +(S k -u k )= k - k , k=1,2,3 指標(biāo)函數(shù)：F k (S k ) （3） 求解過程 k=3 時：? ?? ?3 33 33 3 3 3 303 3 30( ) max (S )max Su Sf S u uu u? ?? ?? ? ?? ? ?，最優(yōu)決策為：k ku S ? ，即原料配給 1型產(chǎn)品 k=2 時：? ?? ?2 22 22 2 2 2 2 2 202 2 20( ) max ( ) ( Su Sf S u S u S uS u S? ?? ?? ? ? ? ?? ? ?，最優(yōu)決策為：k ku S ? 0，即原料配給 2 型產(chǎn)品 k=1 時：? ?? ?1 11 11 1 1 1 1 1 101 1 10( ) max ( ) ( Su Sf S u S u S uS u S? ?? ?? ? ? ? ?? ? ?，最優(yōu)決策為：

　　0ku ? ，即原料配給 2 型產(chǎn)品 總收益為：

　　 100 (100 ) (100 ) ? ? ? ? ? ? ? ? ? （4） Lingo 模型 （5） Lingo 程序 model: SETS: stage/1..3/:x,y;!三個階段，每個階段1型和2型產(chǎn)品分配數(shù)量分別為x(k)和y(k); ENDSETS max = @sum(stage:*x+*y);!目標(biāo)函數(shù)：總效益最大化; n = @size(stage); !階段總數(shù); x(1)+y(1) <= 100; !第一階段分配總數(shù)不超過原料數(shù); @for(stage(k) | k #lt# n: x(k+1)+y(k+1) <= *x(k)+*y(k));!以后各階段分配總數(shù)不超過上階段回收數(shù); （6） Lingo 求解結(jié)果 3、等待制排隊(duì)問題 （1） 問題描述 某修理店只有一個修理工，來修理店的顧客到達(dá)過程為泊松流，平均 4 人/小時，修理時間服從負(fù)指數(shù)分布，平均需要 6 分鐘，試求：1）修理店空閑的概率；2）店內(nèi)恰好有 3 個顧客的概率；3）店內(nèi)至少有 1 個顧客的概率；4）店內(nèi)的平均顧客數(shù)；5）每位顧客在店內(nèi)的平均停留時間；6）等待服務(wù)的平均顧客數(shù)；7）每位顧客的平均等待服務(wù)時間；8）顧客在店內(nèi)等待時間超過 10 分鐘的概率。

　　解：本題可看成一個 M/M/1/∞排隊(duì)問題，其中 λ=4，μ=10，ρ=λ/μ= 1) 修理店空閑的概率 p0=1-ρ=

　　2）店內(nèi)恰有 3 個顧客的概率 p3=ρ3 (1-ρ)= 3）店內(nèi)至少有 1 個顧客的概率：P{N≥1}=1-p0= 4）店內(nèi)平均顧客數(shù)：L=λ/μ-λ=2/3 人 5）每位顧客在店內(nèi)的平均停留時間為：W=L/λ=1/6 小時=10 分鐘 6）等待服務(wù)的平均顧客數(shù) Lq=L-ρ=4/15= 人 7）每位顧客的平均等待服務(wù)時間為 Wq=W-1/μ=10-6=4 分鐘 8 ） 顧 客 在 店 內(nèi) 等 待 時 間 超 過 10 分 鐘 （ 1/6 小 時 ） 的 概 率 ：P{T>1/6}=e-(10-4/6) = （2） Lingo 程序 ! 服務(wù)臺數(shù); S =1; ! 顧客到達(dá)率（/小時）; lambda = 4; !顧客服務(wù)率; mu = 10; !系統(tǒng)到達(dá)負(fù)荷; load = lambda/mu; ! 顧客等待的概率; Pwait = @PEB(load, S); ! 顧客平均等待時間; W_q = Pwait/mu/(S-load); !等待服務(wù)的平均顧客數(shù); L_q = lambda * W_q; !每位顧客在店內(nèi)的平均停留時間; W=W_q+1/mu; !店內(nèi)的平均顧客數(shù); L=lambda * W; ! 修理店空閑的概率; P0=1-load; !店內(nèi)恰有3個顧客的概率; P3 = load^3 * p0; ! 顧客在店內(nèi)等待時間超過10分鐘; Pt10 = @exp(-(mu-lambda)*1/6); （3）Lingo 求解結(jié)果及分析 可見，程序運(yùn)行結(jié)果與計(jì)算結(jié)果一致。

　　五、 實(shí)驗(yàn)內(nèi)容及要求 根據(jù)本指導(dǎo)書提供的例題練習(xí)對動態(tài)規(guī)劃的建模及求解方法，以及應(yīng)用相關(guān)Lingo 函數(shù)求解排隊(duì)論問題，完成以下思考練習(xí)題，并通過手工計(jì)算對程序的運(yùn)行結(jié)果進(jìn)行驗(yàn)證。將相關(guān)的問題分析、模型、程序、運(yùn)行結(jié)果及結(jié)果的分析（包括手工計(jì)算過程）附在上機(jī)實(shí)驗(yàn)報告中。

　　練習(xí) 1：用 Lingo 軟件求解下圖所示的從 A 到 E 的最短路線及其長度。

　　圖 3 練習(xí) 1 相關(guān)網(wǎng)絡(luò)圖 練習(xí) 2：用 Lingo 軟件求解多階段生產(chǎn)安排問題。某公司現(xiàn)有同種施工機(jī)械 100

　　臺，分別用于兩類輕重不同的施工任務(wù)，該公司面臨兩年施工工期的每年初各分配多少臺機(jī)械用于這兩類任務(wù)的決策，目的是使總收益最大。若每年將 x 臺機(jī)械用于重任務(wù)，當(dāng)年收為 g(x)=10x2 （萬元），并將有 30%的機(jī)械于當(dāng)年年末報廢；若將 y 臺機(jī)械用于輕的施工任務(wù)，當(dāng)年收入為 g(y)=5y2 （萬元），但有 10%的機(jī)械于年末報廢。兩年施工結(jié)束后，未報廢的機(jī)械可以每臺 7 萬元的售價賣出。試為該公司提供你的決策建議。

　　練習(xí) 3：某維修中心在周末只安排一名員工為服務(wù)提供服務(wù)，新來的顧客到達(dá)后，若已有顧客正在接受服務(wù)，則需要排隊(duì)等待，假設(shè)來維修的顧客到達(dá)過程為泊松流，平均每小時 6 人，維修時間服務(wù)負(fù)指數(shù)分布，平均需要 4 分鐘，試求該系統(tǒng)的主要數(shù)量指標(biāo)：系統(tǒng)平均隊(duì)長 Ls、系統(tǒng)平均等待隊(duì)長 Lq、顧客平均停留時間W、顧客平均等待時間 Wq、系統(tǒng)繁忙概率 Pwait。

　　實(shí)驗(yàn)課程名稱實(shí)驗(yàn)指導(dǎo)書

　　機(jī)器人實(shí)驗(yàn)指導(dǎo)書

　　生產(chǎn)與運(yùn)作管理》實(shí)驗(yàn)指導(dǎo)書

　　實(shí)驗(yàn)五,抽樣定理與PAM通信系統(tǒng)實(shí)驗(yàn)

　　土木工程實(shí)驗(yàn)教學(xué)中心學(xué)生實(shí)驗(yàn)指導(dǎo)書

運(yùn)籌學(xué)與系統(tǒng)工程上機(jī)實(shí)驗(yàn)指導(dǎo)書實(shí)驗(yàn)五(管理運(yùn)籌學(xué)上機(jī)實(shí)驗(yàn))相關(guān)文章：