下面是范文網(wǎng)小編整理的運籌學與系統(tǒng)工程上機實驗指導書實驗五(管理運籌學上機實驗)，供大家參閱。

　　運籌學與系統(tǒng)工程上機實驗指導書 機電學院工業(yè)工程專業(yè) 2013-2014（1）學期 上機實驗五：應用 Lingo 求解動態(tài)規(guī)劃和排隊論問題 一、 實驗目的 在熟練編寫和運行 Lingo 程序的基礎上，應用 Lingo 進行求解動態(tài)規(guī)劃和排隊論等深層次優(yōu)化問題的練習。

　　二、 實驗要求 1、根據(jù)本指導書學習 Lingo 對典型動態(tài)規(guī)劃問題進行建模和求解。

　　2、根據(jù)本指導書學習排隊論相關函數(shù)的具體使用方法，對典型的隨機服務系統(tǒng)問題進行建模和求解。

　　3、獨立完成相關應用題目的分析、建模和應用 Lingo 軟件的求解過程。

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

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

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

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

　　1 LW? ? ?? ?? （1）

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

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

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

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

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

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

　　圖 2 城市網(wǎng)絡 （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 ) 指標函數(shù)：F k (S k ) （3）求解過程：

　　（4）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)計劃問題 （1） 問題描述：

　　設某種材料可用于兩種方式生產(chǎn)，用后除產(chǎn)生效益外，還有一部分回收，表1 所示為生產(chǎn)方式、效益及回收之間的關系，若有材料 100 個單位，計劃進行 3個階段的生產(chǎn)，如何投入材料，使總效益達到最大? 表 1 生產(chǎ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 指標函數(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);!目標函數(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、等待制排隊問題 （1） 問題描述 某修理店只有一個修理工，來修理店的顧客到達過程為泊松流，平均 4 人/小時，修理時間服從負指數(shù)分布，平均需要 6 分鐘，試求：1）修理店空閑的概率；2）店內(nèi)恰好有 3 個顧客的概率；3）店內(nèi)至少有 1 個顧客的概率；4）店內(nèi)的平均顧客數(shù)；5）每位顧客在店內(nèi)的平均停留時間；6）等待服務的平均顧客數(shù)；7）每位顧客的平均等待服務時間；8）顧客在店內(nèi)等待時間超過 10 分鐘的概率。

　　解：本題可看成一個 M/M/1/∞排隊問題，其中 λ=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）等待服務的平均顧客數(shù) Lq=L-ρ=4/15= 人 7）每位顧客的平均等待服務時間為 Wq=W-1/μ=10-6=4 分鐘 8 ） 顧 客 在 店 內(nèi) 等 待 時 間 超 過 10 分 鐘 （ 1/6 小 時 ） 的 概 率 ：P{T>1/6}=e-(10-4/6) = （2） Lingo 程序 ! 服務臺數(shù); S =1; ! 顧客到達率（/小時）; lambda = 4; !顧客服務率; mu = 10; !系統(tǒng)到達負荷; load = lambda/mu; ! 顧客等待的概率; Pwait = @PEB(load, S); ! 顧客平均等待時間; W_q = Pwait/mu/(S-load); !等待服務的平均顧客數(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é)果及分析 可見，程序運行結(jié)果與計算結(jié)果一致。

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

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

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

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

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

　　實驗課程名稱實驗指導書

　　機器人實驗指導書

　　生產(chǎn)與運作管理》實驗指導書

　　實驗五,抽樣定理與PAM通信系統(tǒng)實驗

　　土木工程實驗教學中心學生實驗指導書

運籌學與系統(tǒng)工程上機實驗指導書實驗五(管理運籌學上機實驗)相關文章：