運(yùn)籌學(xué)后半段 第五章 動(dòng)態(tài)規(guī)劃

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

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

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

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

例如：最短路徑問(wèn)題

求A到B的最短路徑：

大體思路：遞歸

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

• 基本概念

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

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

遞推關(guān)系：

路徑加和累計(jì)

連乘累計(jì)

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

5.2 動(dòng)態(tài)規(guī)劃模型舉例 5.2.1 資源分配問(wèn)題（重點(diǎn)）

解

逆向開(kāi)始書(shū)寫(xiě)：

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

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

結(jié)論

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

簡(jiǎn)單圖：既沒(méi)有自環(huán)也沒(méi)有平行邊的圖

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

**‘完全圖’😗*任意兩個(gè)點(diǎn)都有邊

?n個(gè)頂點(diǎn)有 Cn 2個(gè)邊

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

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

度為0的點(diǎn)：孤立點(diǎn)

度為1的點(diǎn)：懸掛點(diǎn)

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

圈（loop）：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的鏈

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

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

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

走過(guò)圖中所有邊且每條邊僅走一次的閉行走稱(chēng)為歐拉回路

**‘簡(jiǎn)單路徑’😗*除了路徑起點(diǎn)和終點(diǎn)相同，其余頂點(diǎn)都不同

**‘連通圖’😗*對(duì)任意兩個(gè)頂點(diǎn)都有路徑

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

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

2）最小生成樹(shù) 圖的生成樹(shù)：（重點(diǎn)）

? 生成樹(shù)是圖的所有頂點(diǎn)連接在一起，但不形成回路

? ‘深度優(yōu)先生成樹(shù)’:通過(guò)深度優(yōu)先搜索進(jìn)行遍歷的生成樹(shù)

? ‘廣度優(yōu)先生成樹(shù)’:通過(guò)廣度優(yōu)先搜索進(jìn)行遍歷的生成樹(shù)

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

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

? Prim算法(選頂點(diǎn))

(從a結(jié)點(diǎn)開(kāi)始遍歷，如果同時(shí)出現(xiàn)多個(gè)可以選擇的結(jié)點(diǎn)時(shí)，優(yōu)先把序號(hào)較小的結(jié)點(diǎn)加入生成樹(shù))

? Kruskal(選擇邊)

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

最短路徑（重點(diǎn)）

不同于最小生成樹(shù)，不用包含全部的頂點(diǎn)

Dijkstra算法(解決到達(dá)一個(gè)點(diǎn)的最短路徑)

步驟：

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

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

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

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

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

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

步驟：

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

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

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

• 概念：

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

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

• 滿(mǎn)足上述條件的稱(chēng)為可行流，存在大可行流
• 當(dāng)支路上fij = cij ，稱(chēng)為飽和弧

截集與截集容量

s:開(kāi)始點(diǎn)，t：結(jié)束點(diǎn)

定義：

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

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

確定網(wǎng)絡(luò)大流的標(biāo)號(hào)法

• 飽和?。篺ij = cij 的弧

• 非飽和?。篺ij< cij 的弧

• 零流?。篺ij = 0的弧

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

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

• 正向弧：

• 第一類(lèi)是弧的方向與鏈μ的方向一致，稱(chēng)為前向?。ㄕ蚧。?，前向弧的全體集合記為μ+；

• 反向弧：第二類(lèi)是弧的方向與鏈μ的方向相反，稱(chēng)為后向弧（反向?。笙蚧〉娜w集合記為μ-

• 增廣鏈：

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

當(dāng)μ滿(mǎn)足下述條件：

即μ上的前向?。ㄕ蚧。榉秋柡突?，后向弧（反向?。榉橇懔骰　?/p>

• 大標(biāo)號(hào)法步驟（重要）

第一步

第二步

例：

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

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

定義介紹：

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

相關(guān)特性

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

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

7.1.2 輸入過(guò)程與服務(wù)時(shí)間

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

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

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

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

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

7.2 隨機(jī)服務(wù)過(guò)程

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

例：

間隔到達(dá)時(shí)間：τ

等待時(shí)長(zhǎng)：w

服務(wù)時(shí)長(zhǎng)：h

• 當(dāng)服務(wù)臺(tái)連續(xù)不斷服務(wù)時(shí)，有如下關(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 表示了累計(jì)的未完成的服務(wù)時(shí)長(zhǎng)，一般地有

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

1）Wq 、Wd 分別是顧客的平均排隊(duì)等待時(shí)間和平均逗留時(shí)間
2）Lq 、Ld分別是系統(tǒng)平均排隊(duì)的顧客數(shù)和系統(tǒng)的平均顧客數(shù)
3） Ln 是同時(shí)接受服務(wù)的平均顧客數(shù)（即平均服務(wù)臺(tái)占用數(shù)）
4） h 是顧客的平均服務(wù)時(shí)長(zhǎng)，λ是顧客的平均到達(dá)率（即單位時(shí)間內(nèi)到達(dá)的顧客數(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ù)時(shí)間與間隔時(shí)間 7.3.1 概述

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

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

主要是講述

7.3.2 常用的概率分布

• 定長(zhǎng)分布

• 負(fù)指數(shù)分布（重點(diǎn)）

• 愛(ài)爾蘭分部

7.3.3 負(fù)指數(shù)分布的特點(diǎn)

• 負(fù)指數(shù)分布之所以常用，是因?yàn)樗泻芎玫奶匦?，使?shù)學(xué)分析變得方便： 期望等于均方差

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

證明

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

證明

7.4 輸入過(guò)程

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

• 定長(zhǎng)輸入過(guò)程：間隔時(shí)間服從定長(zhǎng)分布

• 泊松輸入過(guò)程：?jiǎn)挝粫r(shí)間內(nèi)到達(dá)的顧客數(shù)服從泊松分布

7.4.1 泊松輸入過(guò)程及其特點(diǎn)

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

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

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

• 

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

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

• 泊松過(guò)程的到達(dá)間隔時(shí)間為負(fù)指數(shù)分布

證

7.4.2 馬爾科夫鏈

馬爾科夫鏈 （Markov Chain ) 又簡(jiǎn)稱(chēng)馬氏鏈 ，是一種 離散事件 隨機(jī)過(guò)程。
用數(shù)學(xué)式表達(dá)為：

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

7.5 生滅過(guò)程

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

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

• 生滅過(guò)程的馬氏鏈

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

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

   

2. 其次解遞歸解

   

• 滿(mǎn)足生滅過(guò)程的條件

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

泊松輸入/負(fù)指數(shù)服務(wù)時(shí)長(zhǎng)/n個(gè)并聯(lián)服務(wù)臺(tái)

8.1 M/M/n損失制

增長(zhǎng)：有新來(lái)的顧客

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

8.1.1 M/M/n損失制，無(wú)限源

顧客到達(dá)率：λ（人/小時(shí)）

每個(gè)臺(tái)的服務(wù)率（人/小時(shí)）：

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

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

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

  

  服務(wù)臺(tái)利用率

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

  

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

• 愛(ài)爾蘭損失表

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

例 1：

解

例 2：

解

例 3：

解

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

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

N:顧客總數(shù)

n：服務(wù)臺(tái)個(gè)數(shù)

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

**q=γ/μ：**平均時(shí)長(zhǎng)

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

按時(shí)間計(jì)算的損失率：

按顧客到達(dá)的損失率：

不用記，考試要用會(huì)給

• 服務(wù)臺(tái)利用率

例1：

解

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

顧客到達(dá)率為λ

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

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

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

8.22 系統(tǒng)的各個(gè)指標(biāo)

當(dāng)n=1時(shí)

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

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

tips：

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

例1：

例2：

第九章 存儲(chǔ)理論 9.1 簡(jiǎn)單介紹

存儲(chǔ)理論主要分為：

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

• 術(shù)語(yǔ)

• 存儲(chǔ)策略

9.2 確定性存儲(chǔ)模型

市場(chǎng)的備運(yùn)期和需求是已知的

9.2.1 不允許缺貨模型

Cd：一次性訂購(gòu)費(fèi)

Cs：?jiǎn)挝粫r(shí)間存儲(chǔ)費(fèi)

t：訂貨周期

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

• 定量分析：

Q = D t ：每次訂購(gòu)量 Q=Dt：\text{每次訂購(gòu)量} Q=Dt：每次訂購(gòu)量

平均存儲(chǔ)量 = 1 / 2 Q 平均存儲(chǔ)量=1/2Q 平均存儲(chǔ)量=1/2Q

單位時(shí)間存儲(chǔ)費(fèi)：三角形面積/t*單位時(shí)間存儲(chǔ)費(fèi)

（必考）

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

C(Q0):最佳費(fèi)用

t0：最佳訂貨周期

幾點(diǎn)說(shuō)明：

例題：

解

計(jì)算年存儲(chǔ)費(fèi)使用的是：平均存儲(chǔ)量

9.2.2 允許缺貨模型

H：大存儲(chǔ)量

Cq:單位缺貨損失費(fèi)

缺貨時(shí)間：t2

例：

解

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

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

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

Cd:準(zhǔn)備費(fèi)

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

9.2.4 兩種存儲(chǔ)費(fèi)，不允許缺貨模型

自己倉(cāng)庫(kù)存儲(chǔ)量不夠，租用其他倉(cāng)庫(kù)

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

購(gòu)買(mǎi)越多，單價(jià)越低

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

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

計(jì)算步驟：

例：

解

要計(jì)算每個(gè)區(qū)間的右端點(diǎn)，算出最小值C（Q0）

考試范圍：

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

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

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

廣告

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