運籌學(xué)后半段 第五章 動態(tài)規(guī)劃

最優(yōu)化原理，可以歸結(jié)為一個遞推公式

創(chuàng)新互聯(lián)公司科技有限公司專業(yè)互聯(lián)網(wǎng)基礎(chǔ)服務(wù)商，為您提供達州托管服務(wù)器，高防服務(wù)器租用，成都IDC機房托管，成都主機托管等互聯(lián)網(wǎng)服務(wù)。

現(xiàn)實應(yīng)用：比如最優(yōu)路徑、資源分配、生產(chǎn)計劃和庫存等

5.1 動態(tài)規(guī)劃的最優(yōu)化原理及其算法 5.1.1 求解多階段決策過程的方法

例如：最短路徑問題

求A到B的最短路徑：

大體思路：遞歸

5.1.2 動態(tài)規(guī)劃的基本概念及遞推公式

• 基本概念

• 最優(yōu)化原理和動態(tài)規(guī)劃遞推關(guān)系

最優(yōu)化原理：最優(yōu)策略的子策略也是最優(yōu)的

遞推關(guān)系：

路徑加和累計

連乘累計

• 動態(tài)規(guī)劃的步驟

5.2 動態(tài)規(guī)劃模型舉例 5.2.1 資源分配問題（重點）

解

逆向開始書寫：

X*：最終實際應(yīng)該給多少

$$ f_3=Max(d_3+f_4) $$

結(jié)論

第六章 圖與網(wǎng)絡(luò)分析 定義： 1）圖與網(wǎng)絡(luò)

簡單圖：既沒有自環(huán)也沒有平行邊的圖

**‘有向圖’😗*每條邊都有方向

**‘完全圖’😗*任意兩個點都有邊

?n個頂點有 Cn 2個邊

**‘網(wǎng)’😗*邊或者弧帶權(quán)值的圖

**‘頂點的度（degree）’😗*與該頂點相關(guān)聯(lián)的邊的數(shù)目

度為0的點：孤立點

度為1的點：懸掛點

鏈（link）：連續(xù)的邊構(gòu)成的頂點序列

圈（loop）：第一個頂點和最后一個頂點相同的鏈

‘路徑’:連續(xù)的邊構(gòu)成的頂點序列，且不出現(xiàn)重復(fù)

**‘路徑長度’😗*路徑的權(quán)值之和

**‘回路(circuit)’😗*第一個頂點和最后一個頂點相同的路徑

走過圖中所有邊且每條邊僅走一次的閉行走稱為歐拉回路

**‘簡單路徑’😗*除了路徑起點和終點相同，其余頂點都不同

**‘連通圖’😗*對任意兩個頂點都有路徑

‘聯(lián)通分量(極大連通子圖）’:再加入一個頂點子圖不再連通

平面圖(planar graph)：在平面上可以畫出該圖而沒有任何邊相交

2）最小生成樹 圖的生成樹：（重點）

? 生成樹是圖的所有頂點連接在一起，但不形成回路

? ‘深度優(yōu)先生成樹’:通過深度優(yōu)先搜索進行遍歷的生成樹

? ‘廣度優(yōu)先生成樹’:通過廣度優(yōu)先搜索進行遍歷的生成樹

最小生成樹 (各邊權(quán)值和最小)

? ‘MST性質(zhì)(貪心算法)’:'U集合’是已經(jīng)經(jīng)過的頂點,在’U’和’U-V’選取權(quán)值最小的邊,這條邊一定在生成樹上

? Prim算法(選頂點)

(從a結(jié)點開始遍歷，如果同時出現(xiàn)多個可以選擇的結(jié)點時，優(yōu)先把序號較小的結(jié)點加入生成樹)

? Kruskal(選擇邊)

(如果同時出現(xiàn)多個可以選擇的邊時，以邊中序號較小的結(jié)點為第一優(yōu)先，序號較大的結(jié)點為第二優(yōu)先，按照升序順序選擇。假設(shè)邊(a,d),(a,e),(b,c)有相同權(quán)重,選擇優(yōu)先順序從大到小為(a,d),(a,e),(b,c))

最短路徑（重點）

不同于最小生成樹，不用包含全部的頂點

Dijkstra算法(解決到達一個點的最短路徑)

步驟：

? 1.‘初始化’:先找出原點v0到所有頂點的最短路徑(v0,vk)

? S={v0},T={其余頂點},D[i]存放距離值

? 2.‘選擇’:從這些路徑中學(xué)出一條長度最短的路徑(v0,u)

? 3.‘更新’:若存在(u,vk)且路徑(v0,u,vk)<(v0,vk) 用其代替

? 4.(v0,u,vk)作為新的頂點集合,重復(fù)操作

Floyd算法(解決所有頂點的最短路徑)

步驟：

? n階矩陣,對角線元素為0,矩陣存的為對應(yīng)權(quán)值

? 依次加入中間頂點,如果變短則修改,直到所有點增加完畢

3）網(wǎng)絡(luò)的大流和最小截集（重點）

• 概念：

• 網(wǎng)絡(luò)流一般在有向圖上討論

• 定義網(wǎng)絡(luò)上支路的容量為其大通過能力，記為cij ，支路上的實際流量記為fij

• 滿足上述條件的稱為可行流，存在大可行流
• 當支路上fij = cij ，稱為飽和弧

截集與截集容量

s:開始點，t：結(jié)束點

定義：

• 截集：把網(wǎng)絡(luò)分割為兩個成分的弧的最小集合，其中一個成分包含s 點，另一個包含t 點。
• 最小截集：所有點到外部都是滿載的點

福特-富克森定理：網(wǎng)絡(luò)的大流等于最小截集容量

確定網(wǎng)絡(luò)大流的標號法

• 飽和?。篺ij = cij 的弧

• 非飽和弧：fij< cij 的弧

• 零流?。篺ij = 0的弧

• 非零流?。篺ij >0 的弧

規(guī)定鏈μ：的方向是從始點s到終點t

• 正向?。?/p>

• 第一類是弧的方向與鏈μ的方向一致，稱為前向?。ㄕ蚧。?，前向弧的全體集合記為μ+；

• 反向?。旱诙愂腔〉姆较蚺c鏈μ的方向相反，稱為后向弧（反向?。?，后向弧的全體集合記為μ-

• 增廣鏈：

理解：從原點可以增加多少流量到該結(jié)點

當μ滿足下述條件：

即μ上的前向弧（正向?。榉秋柡突?，后向?。ǚ聪蚧。榉橇懔骰?。

• 大標號法步驟（重要）

第一步

第二步

例：

如Dijkstra一樣，每次合并后所有結(jié)點視為一個整體（找的增廣鏈先后順序無所謂）

第七章 隨機服務(wù)理論概述 7.1 隨機服務(wù)系統(tǒng)

定義介紹：

• 系統(tǒng)的輸入輸出是隨機變量，可以稱之為排隊論和擁塞理論

相關(guān)特性

7.1.1 服務(wù)機構(gòu)的組織方式與服務(wù)方式

• 單臺制和多臺制
• 并聯(lián)服務(wù)
• 串聯(lián)服務(wù)
• 串并聯(lián)服務(wù)、網(wǎng)絡(luò)服務(wù)

7.1.2 輸入過程與服務(wù)時間

• 顧客單個到達或成批到達
• 顧客到達時間間隔的分布和服務(wù)時間的分布
• 顧客源是有限的還是無限的

7.1.3 服務(wù)規(guī)則

• 損失制
• 等待制：先到先服務(wù) ( FIFO)，后到先服務(wù)，隨機服務(wù)，優(yōu)先權(quán)服務(wù)

上述兩個為重點學(xué)習(xí)內(nèi)容

• 混合制
• 逐個到達，成批服務(wù)；成批到達，逐個服務(wù)

7.2 隨機服務(wù)過程

• 單臺服務(wù)系統(tǒng)、等待制、先到先服務(wù)
• 顧客在系統(tǒng)中的總時長：逗留時間=等待時長+服務(wù)時長
• 等待時長與顧客到達率和服務(wù)時長有關(guān)

例：

間隔到達時間：τ

等待時長：w

服務(wù)時長：h

• 當服務(wù)臺連續(xù)不斷服務(wù)時，有如下關(guān)系：

w i + 1 + τ i + 1 = w i + h i w_{i+1}+\tau_{i+1}=w_i+h_i wi+1?+τi+1?=wi?+hi?

• wi+hi 表示了累計的未完成的服務(wù)時長，一般地有

tips：排隊系統(tǒng)的指標及其關(guān)系

1）Wq 、Wd 分別是顧客的平均排隊等待時間和平均逗留時間
2）Lq 、Ld分別是系統(tǒng)平均排隊的顧客數(shù)和系統(tǒng)的平均顧客數(shù)
3） Ln 是同時接受服務(wù)的平均顧客數(shù)（即平均服務(wù)臺占用數(shù)）
4） h 是顧客的平均服務(wù)時長，λ是顧客的平均到達率（即單位時間內(nèi)到達的顧客數(shù)）。
5）相關(guān)公式
L d = λ W d = λ ( W q + h ) = L q + L n Ld = \lambda W_d= \lambda(W_q + h ) = L_q + L_n Ld=λWd?=λ(Wq?+h)=Lq?+Ln?

L q = λ W q Lq = \lambda W_q Lq=λWq?

L n = λ h L_n = \lambda h Ln?=λh

7.3 服務(wù)時間與間隔時間 7.3.1 概述

• 顧客的服務(wù)時間由于多種原因具有不確定性，最好的描述方法就是概率分布；同樣顧客到達的間隔時間也具有一定的概率分布
• 服務(wù)時間和到達間隔時間服從什么分布？可以先通過統(tǒng)計得到經(jīng)驗分布，再做理論假設(shè)和檢驗。
• 經(jīng)驗分布一般采用直方圖來表示，如下圖

下述內(nèi)容是之前概率論學(xué)過的

主要是講述

7.3.2 常用的概率分布

• 定長分布

• 負指數(shù)分布（重點）

• 愛爾蘭分部

7.3.3 負指數(shù)分布的特點

• 負指數(shù)分布之所以常用，是因為它有很好的特性，使數(shù)學(xué)分析變得方便： 期望等于均方差

• 無記憶性 。指的是不管一次服務(wù)已經(jīng)過去了多長時間，該次服務(wù)所剩的服務(wù)時間仍服從原負指數(shù)分布

證明

• 普通型：多個獨立同分布負指數(shù)分布的服務(wù)在進行，不可能有兩個以上同時結(jié)束

證明

7.4 輸入過程

顧客到達的分布，可用相繼到達顧客的間隔時間描述，也可以用單位時間內(nèi)到達的顧客數(shù)描述

• 定長輸入過程：間隔時間服從定長分布

• 泊松輸入過程：單位時間內(nèi)到達的顧客數(shù)服從泊松分布

7.4.1 泊松輸入過程及其特點

泊松分布的均值和方差均為λ ， λ也稱為到達率， λt 是(0, t) 時間內(nèi)顧客到達的期望值

• 平穩(wěn)性 ：顧客到達數(shù)只與時間區(qū)間長度有關(guān)

• 無后效性 ：不相交的時間區(qū)間內(nèi)所到達的顧客數(shù)是獨立的

• 

• 有限性 ：在有限的時間區(qū)間內(nèi)，到達的顧客數(shù)是有限的。

• 可疊加性：即獨立的泊松分布變量的和仍為泊松分布（概率論）

• 泊松過程的到達間隔時間為負指數(shù)分布

證

7.4.2 馬爾科夫鏈

馬爾科夫鏈 （Markov Chain ) 又簡稱馬氏鏈 ，是一種 離散事件 隨機過程。
用數(shù)學(xué)式表達為：

• X n+ 1 的狀態(tài)只與 X n 的狀態(tài)有關(guān)，與 X n 前的狀態(tài)無關(guān)，具有無記憶性或 無后效性 ，又稱 馬氏性
• 狀態(tài)轉(zhuǎn)移是一步一步發(fā)生的（從i狀態(tài)轉(zhuǎn)移到j(luò)狀態(tài)）。令 X n = i 表示系統(tǒng)在時刻 t 處于狀態(tài) i 這一事件，一步狀態(tài)轉(zhuǎn)移概率：

7.5 生滅過程

一種描述自然界生滅現(xiàn)象的數(shù)學(xué)方法，如細菌的繁殖和滅亡、人口的增減、生物種群的滅種現(xiàn)象等

• 采用馬氏鏈
  • 令 N t 代表系統(tǒng)在時刻 t 的狀態(tài)，下一瞬間 t = ? t 系統(tǒng)的狀態(tài)只能轉(zhuǎn)移
  • 到相鄰狀態(tài)，或維持不變，如圖所示：數(shù)量 +1 數(shù)量 1 ，數(shù)量不變
  • 三種轉(zhuǎn)移是不相容的，三者必居其一
  • 只有具有無記憶性和普通性的過程 分布 才適用馬氏鏈
  • 令 P j(t) P{ N(t) = j }代表系統(tǒng)在時刻 t 處于狀態(tài) j 的概率

• 生滅過程的馬氏鏈

推導(dǎo)過程了解即可

1. 首先解穩(wěn)態(tài)方程組

   

2. 其次解遞歸解

   

• 滿足生滅過程的條件

第八章 M/M/n系統(tǒng)

泊松輸入/負指數(shù)服務(wù)時長/n個并聯(lián)服務(wù)臺

8.1 M/M/n損失制

增長：有新來的顧客

消亡：有顧客完成服務(wù)

8.1.1 M/M/n損失制，無限源

顧客到達率：λ（人/小時）

每個臺的服務(wù)率（人/小時）：

化簡：ρ=λ/μ稱為業(yè)務(wù)量，表示一個平均服務(wù)一個人到幾個人

• 系統(tǒng)的服務(wù)質(zhì)量

  系統(tǒng)的質(zhì)量用損失率來度量，兩種度量方法

  

  服務(wù)臺利用率

  （1-B）:完成服務(wù)率

  

• 求所需最少服務(wù)臺的方法

• 愛爾蘭損失表

• 服務(wù)臺利用率和服務(wù)臺數(shù)量的關(guān)系

例 1：

解

例 2：

解

例 3：

解

8.1.2 M/M/n損失制，有限源

顧客到達率是與系統(tǒng)中被服務(wù)的顧客數(shù)相關(guān)的

N:顧客總數(shù)

n：服務(wù)臺個數(shù)

j：現(xiàn)在服務(wù)的人數(shù)

**q=γ/μ：**平均時長

• 衡量服務(wù)質(zhì)量的指標：損失率

按時間計算的損失率：

按顧客到達的損失率：

不用記，考試要用會給

• 服務(wù)臺利用率

例1：

解

8.2 M/M/n等待制，無限源，無限容量 8.2.1 系統(tǒng)穩(wěn)態(tài)概率及等待概率

顧客到達率為λ

每臺的服務(wù)率為μ

業(yè)務(wù)量：ρ=λ/μ

• 計算顧客進入系統(tǒng)必須等待的概率D

8.22 系統(tǒng)的各個指標

當n=1時

8.23 系統(tǒng)等待時間的分布概率

顧客離去的概率符合泊松分布：

tips：

做題時關(guān)注n=1，如果有，可以簡化做題

例1：

例2：

第九章 存儲理論 9.1 簡單介紹

存儲理論主要分為：

我們只關(guān)注 經(jīng)典存儲理論

• 術(shù)語

• 存儲策略

9.2 確定性存儲模型

市場的備運期和需求是已知的

9.2.1 不允許缺貨模型

Cd：一次性訂購費

Cs：單位時間存儲費

t：訂貨周期

C(Q):單位時間內(nèi)的可變費用

• 定量分析：

Q = D t ：每次訂購量 Q=Dt：\text{每次訂購量} Q=Dt：每次訂購量

平均存儲量 = 1 / 2 Q 平均存儲量=1/2Q 平均存儲量=1/2Q

單位時間存儲費：三角形面積/t*單位時間存儲費

（必考）

Q0：最佳經(jīng)濟訂貨量

C(Q0):最佳費用

t0：最佳訂貨周期

幾點說明：

例題：

解

計算年存儲費使用的是：平均存儲量

9.2.2 允許缺貨模型

H：大存儲量

Cq:單位缺貨損失費

缺貨時間：t2

例：

解

9.2.3 連續(xù)進貨，不允許缺貨模型

t1:零件生產(chǎn)期

K：零件生產(chǎn)率，D：零件消耗率

Cd:準備費

直接代入不缺貨模型公式（3）：

9.2.4 兩種存儲費，不允許缺貨模型

自己倉庫存儲量不夠，租用其他倉庫

9.2.5 不允許缺貨，批量折扣模型

購買越多，單價越低

在區(qū)間內(nèi)的價格公式：

Q0是否為最小值要與右邊區(qū)間（左端點）進行比較

計算步驟：

例：

解

要計算每個區(qū)間的右端點，算出最小值C（Q0）

考試范圍：

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享標題：【北郵果園大三上】運籌學(xué)期中后-創(chuàng)新互聯(lián)
網(wǎng)頁路徑：http://jinyejixie.com/article8/ggdop.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、網(wǎng)站維護、網(wǎng)站改版、軟件開發(fā)、App開發(fā)、網(wǎng)站收錄

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)