本期我們運(yùn)籌學(xué)之網(wǎng)絡(luò)計(jì)劃技術(shù)的講解，我們將對(duì)網(wǎng)絡(luò)計(jì)劃技術(shù)的基礎(chǔ)知識(shí)進(jìn)行一個(gè)簡(jiǎn)單的回顧，并介紹求解網(wǎng)絡(luò)計(jì)劃技術(shù)中的節(jié)點(diǎn)參數(shù)和關(guān)鍵路徑的MATLAB和Python相關(guān)代碼，以幫助大家利用工具快速求解相關(guān)問題，做到事半功倍。由于篇幅有限，小編接下來(lái)只展示部分代碼，小伙伴們可以關(guān)注“運(yùn)籌說(shuō)”公眾號(hào)→后臺(tái)回復(fù)“網(wǎng)絡(luò)計(jì)劃代碼”獲取完整代碼。話不多說(shuō)，我們一起來(lái)看看吧！

一、基礎(chǔ)知識(shí)

1、關(guān)鍵路線與工作時(shí)間的確定

★關(guān)鍵路線

通常把網(wǎng)絡(luò)圖中需時(shí)最長(zhǎng)的路叫作關(guān)鍵路線，關(guān)鍵路線上的工作稱為關(guān)鍵工作。網(wǎng)絡(luò)圖的關(guān)鍵路線可以通過(guò)時(shí)間參數(shù)的計(jì)算求得，總時(shí)差為零為關(guān)鍵工作。

工作(i,j)的所需工時(shí)可記為t(i,j)，有兩種確定方法。

★確定型工作時(shí)間

在具備工時(shí)定額和勞動(dòng)定額的任務(wù)中，工作的工時(shí)t(i,j)可以用這些定額資料確定。有些工作雖無(wú)定額可查，但有有關(guān)工作的統(tǒng)計(jì)資料，也可利用統(tǒng)計(jì)資料通過(guò)分析來(lái)確定工作的工時(shí)。

★概率型工作時(shí)間

（1）定義

對(duì)于開發(fā)性試制性的任務(wù)，往往不具備可用的定額資料，難以準(zhǔn)確估計(jì)工作所需工時(shí)，可以采用三點(diǎn)時(shí)間估計(jì)法來(lái)確定工作的工時(shí)。這種方法對(duì)每道工作先要作出三種情況的時(shí)間估計(jì)：即a——最快可能完成時(shí)間（最樂觀時(shí)間）；m——最可能完成時(shí)間；b——最慢可能完成時(shí)間（最悲觀時(shí)間）。

（2）計(jì)算公式

利用上述3個(gè)時(shí)間a、b、m，可估計(jì)每道工作的期望工時(shí)：

方差為：

2、事項(xiàng)時(shí)間參數(shù)

★ 事項(xiàng)的最早時(shí)間tE(j)

（1）定義

事項(xiàng)j的最早時(shí)間用tE(j)表示，它表明以它為始點(diǎn)的各工作最早可能開始的時(shí)間，也表示以它為終點(diǎn)的各工作的最早可能完成時(shí)間（相同），它等于從始點(diǎn)事項(xiàng)到該事項(xiàng)的最長(zhǎng)路線上所有工作的工時(shí)總和。

（2）計(jì)算公式

設(shè)總開工事項(xiàng)編號(hào)為(1)，事項(xiàng)最早時(shí)間的計(jì)算公式為：

其中，式中tE(i)表示與事項(xiàng)j相鄰的各緊前事項(xiàng)的最早時(shí)間。可令終點(diǎn)事項(xiàng)編號(hào)為n，則終點(diǎn)事項(xiàng)的最早時(shí)間顯然就是整個(gè)工程的總最早完工期，即：tE(n)為總最早完工期。

★ 事項(xiàng)的最遲時(shí)間tL(i)

（1）定義

事項(xiàng)i的最遲時(shí)間用tL(i)表示，它表明在不影響任務(wù)總工期條件下，以它為始點(diǎn)的工作的最遲必須開始時(shí)間，或以它為終點(diǎn)的各工作的最遲必須完成時(shí)間。一般情況下，我們都把任務(wù)的最早完工時(shí)間作為任務(wù)的總工期。

（2）計(jì)算公式

事項(xiàng)最遲時(shí)間的計(jì)算公式為：

其中，tL(j)表示與事項(xiàng)i相鄰的各緊后事項(xiàng)的最遲時(shí)間。事項(xiàng)最遲時(shí)間的計(jì)算公式也是遞推公式，但與事項(xiàng)最早時(shí)間的計(jì)算公式相反，是從終點(diǎn)事項(xiàng)開始，按編號(hào)由大至小的順序逐個(gè)由后向前計(jì)算。

3、工作的時(shí)間參數(shù)

★ 工作的最早可能開工時(shí)間tES(i,j)

一個(gè)工作(i,j)的最早可能開工時(shí)間用tES(i,j)表示。任何一件工作都必須在其所有緊前工作全部完工后才能開始。計(jì)算公式為：

★ 工作的最早可能完工時(shí)間tEF(i,j)

工作(i,j)的最早可能完工時(shí)間用tEF(i,j)表示。它表示工作按最早開工時(shí)間開始所能達(dá)到的完工時(shí)間。計(jì)算公式為：

★ 工作的最遲必須開工時(shí)間tLS(i,j)和工作的最遲必須完工時(shí)間tLF(i,j)

（1）定義

工作(i,j)的最遲必須開工時(shí)間用tLS(i,j)表示。它表示工作(i,j)在不影響整個(gè)任務(wù)如期完成的前提下，必須開始的最晚時(shí)間。工作(i,j)的最遲必須完工時(shí)間用tLF(i,j)表示。它表示工作(i,j)按最遲時(shí)間開工，所能達(dá)到的完工時(shí)間。

（2）計(jì)算公式

由于這組公式是按工作的最遲必須開工時(shí)間由終點(diǎn)向始點(diǎn)逐個(gè)遞推的公式，因此不能單獨(dú)分開。計(jì)算公式為：

凡是進(jìn)入總完工事項(xiàng)n的工作(i,n)，其最遲完工時(shí)間必須等于預(yù)定總工期或這個(gè)工作的最早可能完工時(shí)間。

4、時(shí)差

★ 工作的總時(shí)差R(i,j)

在不影響任務(wù)總工期的條件下，某工作(i,j)可以延遲其開工時(shí)間的最大幅度，叫做該工作的總時(shí)差。其計(jì)算公式為：

★ 工作的單時(shí)差r(i,j)

在不影響緊后工作的最早開工時(shí)間條件下，此工作可以延遲其開工時(shí)間的最大幅度。其計(jì)算公式為：

5、時(shí)間參數(shù)求解算法

★ 問題描述

已知工序明細(xì)表G=（w(i,j)，t(i,j)，Ww(i,j)(m,n)）和網(wǎng)絡(luò)圖，包含每項(xiàng)工作w(i,j)的工時(shí)t(i,j)和工作w(i,j)的緊前工作Ww(i,j)(m,n)。求G的各項(xiàng)工作時(shí)間參數(shù)，包括最早可能開工時(shí)間tES(i,j)，工作的最遲必須開工時(shí)間tLS(i,j)，總時(shí)差R(i,j)和工作總時(shí)間，并指出關(guān)鍵路線。

★ 算法流程

二、算法實(shí)現(xiàn)

1、例題1

（1）例題介紹

某公司的產(chǎn)前分析網(wǎng)絡(luò)工程圖的工序明細(xì)表和網(wǎng)絡(luò)圖如下圖所示，求出網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的最早開始時(shí)間、最遲開始時(shí)間、關(guān)鍵路線及所需最短時(shí)間。

（2）代碼實(shí)現(xiàn)

我們以上述例題為例，借助MATLAB介紹實(shí)現(xiàn)求解的相關(guān)代碼。

★ 代碼展示

★ 代碼調(diào)用

代碼運(yùn)行及最終結(jié)果展示如下，每個(gè)節(jié)點(diǎn)的最早開始時(shí)間分別為：0，5，10，14，10，31，35，51；每個(gè)節(jié)點(diǎn)的最遲開始時(shí)間分別為：0，6，10，16，10，31，36，51；根據(jù)總時(shí)差確定關(guān)鍵路線為①→③→⑤→⑥→⑧；所需最短的工作總時(shí)間為51；

2、例題2

（1）例題介紹

某項(xiàng)產(chǎn)品的制作需要多個(gè)步驟工序的實(shí)施，現(xiàn)產(chǎn)品的工序明細(xì)表和網(wǎng)絡(luò)圖如下所示，求出網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的最早開始時(shí)間、最遲開始時(shí)間、關(guān)鍵路線及所需最短時(shí)間。

（2）代碼實(shí)現(xiàn)

我們以上述例題為例，借助Python介紹實(shí)現(xiàn)求解問題的相關(guān)代碼。

★ 代碼展示

★ 代碼調(diào)用

代碼運(yùn)行及最終結(jié)果展示如下，每個(gè)節(jié)點(diǎn)的最早開始時(shí)間分別為：0，3，3，6，6，6，14，11，18；每個(gè)節(jié)點(diǎn)的最遲開始時(shí)間分別為：0，3，6，6，9，12，14，16，18；根據(jù)總時(shí)差確定關(guān)鍵路線為①→②→③→⑦→⑨→⑩；所需最短的工作總時(shí)間為20；

三、參考資料

【網(wǎng)絡(luò)計(jì)劃技術(shù)節(jié)點(diǎn)參數(shù)和關(guān)鍵路徑的MATLAB實(shí)現(xiàn)及優(yōu)化】

徐永琳,劉露.網(wǎng)絡(luò)計(jì)劃技術(shù)節(jié)點(diǎn)參數(shù)和關(guān)鍵路徑的MATLAB實(shí)現(xiàn)及優(yōu)化[J].工業(yè)儀表與自動(dòng)化裝置,2013(04):26-30.

【根據(jù)邏輯關(guān)系圖以及雙代號(hào)網(wǎng)絡(luò)圖編寫求時(shí)間參數(shù)】

https://blog.csdn.net/weixin_54627824/article/details/127503757

本期的內(nèi)容就介紹到這里，想要進(jìn)一步了解運(yùn)籌學(xué)，關(guān)注本公眾號(hào)，快快學(xué)起來(lái)吧！

作者 | 尹萌娟 王連聚

責(zé)編 | 劉文志

審核 | 徐小峰