在小花的上一篇文章中，分享了如何用 Excel 規(guī)劃求解工具解決最優(yōu)運(yùn)費(fèi)問(wèn)題↓↓↓

同事為這個(gè)運(yùn)費(fèi)問(wèn)題加班兩小時(shí)，而我 10 分鐘搞定！

今天，我們繼續(xù)探討另一運(yùn)輸問(wèn)題——最短路徑問(wèn)題。

什么是最短路徑問(wèn)題？

最短路徑問(wèn)題（The Shortest Path Problem, SPP）是組合優(yōu)化領(lǐng)域的經(jīng)典問(wèn)題之一，它是指在一個(gè)有向賦權(quán)網(wǎng)絡(luò)中，給定一個(gè)起點(diǎn)和一個(gè)終點(diǎn)，求從起點(diǎn)到終點(diǎn)距離最短的一條路徑及其長(zhǎng)度。

舉個(gè)例子，某公司需要將一批貨物以最快的速度從起點(diǎn) S 運(yùn)往終點(diǎn) T，中間有多個(gè)中轉(zhuǎn)站點(diǎn)，每個(gè)站點(diǎn)間是否可通行及通行的距離不一。

我們將具體情況繪制成下圖這樣一個(gè)有向賦權(quán)網(wǎng)絡(luò)，圓圈代表運(yùn)輸節(jié)點(diǎn)，帶箭頭線段代表運(yùn)輸路徑方向（稱為「弧」，如 SA、AD），數(shù)字代表距離。如弧 SA，其數(shù)字為 4，這代表 S 點(diǎn)可以往 A 點(diǎn)運(yùn)輸，運(yùn)輸距離為 4。

將貨物從起點(diǎn) S 運(yùn)往終點(diǎn) T 的可行路徑有很多：

比如 S-A-E-T，其路徑距離為 4+5+7=16；

再如 S-C-F-T，其路徑距離為 5+55+=15。

顯然，路徑 S-C-F-T 更短，而在本案例要求得最短路徑，就是要找出起點(diǎn)為 S、終點(diǎn)為 T 且各弧數(shù)值之和最小的那條折線。

最短路徑問(wèn)題在傳統(tǒng)數(shù)學(xué)計(jì)算上是比較復(fù)雜的，如窮舉、如圖解……

好在，我們有 Excel 規(guī)劃求解這樣的神器。

如何使用規(guī)劃求解解決？

▋STEP01?將有向賦權(quán)網(wǎng)絡(luò)轉(zhuǎn)換成表格形式，以便計(jì)算

我們需要依次把每條弧的起止點(diǎn)及距離錄入到 Excel 中，如下圖：

▋STEP02?建立可變單元格與規(guī)劃目標(biāo)之間的計(jì)算模型

顯然，案例中的規(guī)劃目標(biāo)為每條路徑經(jīng)過(guò)的弧的距離之和。問(wèn)題是，該如何確定當(dāng)前路徑包含哪些弧呢？

我們?cè)?D 列中，使用 0 和 1 來(lái)做區(qū)分，0 代表不經(jīng)過(guò)該弧，1 代表經(jīng)過(guò)該弧。由于任何數(shù)乘以 0 都等于 0，任何數(shù)乘以 1 等于其本身，當(dāng)前路徑的距離之和即為 D 列與 C 列乘積之和，我們使用 SUMPRODUCT 函數(shù)來(lái)完成計(jì)算。

當(dāng)前路徑運(yùn)輸距離公式：
=SUMPRODUCT(D2:D18,C2:C18)

▋STEP03?明確限制條件

該案例的限制條件是起點(diǎn)必須為 S，終點(diǎn)必須為 T，這在 Excel 中該如何體現(xiàn)呢？

我們把某一節(jié)點(diǎn)作為出發(fā)點(diǎn)的次數(shù)與其作為到達(dá)點(diǎn)的次數(shù)的差額稱為凈流量，則各節(jié)點(diǎn)的凈流量限制條件包含以下三個(gè)：

? 起始點(diǎn) S 的凈流量必須等于 1，這表明某一次從 S 出發(fā)后未再返回，結(jié)合第 3 點(diǎn)所述，S 即為起點(diǎn)；

? 終止點(diǎn) T 的凈流量必須等于-1，這表明某一次到達(dá) T 點(diǎn)后，未再出發(fā)，結(jié)合第 3 點(diǎn)所述，S 即為終點(diǎn)；

? 其他途經(jīng)點(diǎn)（A、B、C、D、E、F）的凈流量必須等于 0，這表明每一次到達(dá)這些途經(jīng)點(diǎn)后，總是再次出發(fā)，最終不停留在這些途經(jīng)點(diǎn)上。

我們用 SUMIF 函數(shù)分別計(jì)算出每個(gè)節(jié)點(diǎn)作為出發(fā)點(diǎn)的次數(shù)和作為終止點(diǎn)的次數(shù)，二者相減，必須滿足 S 點(diǎn)為 1，T 點(diǎn)為-1，其余點(diǎn)為 0。

于是，我們構(gòu)建限制條件區(qū)域如下：

L2 單元格公式如下：
=SUMIF($A$2:$A$18,$K2,$D$2:$D$18)-SUMIF($B$2:$B$18,$K2,$D$2:$D$18)

▋STEP04?設(shè)置規(guī)劃求解器，進(jìn)行求解

? 點(diǎn)擊【數(shù)據(jù)】-【規(guī)劃求解】，<設(shè)置目標(biāo)>選擇 F16 單元格，規(guī)劃目標(biāo)設(shè)定為<最小值>，選擇<可改變單元格>為 D2:D18；

? 添加約束條件 L2:L9=N2:N9；

? 勾選<使無(wú)約束變量為非負(fù)數(shù)>，選擇求解方法為<單純線性規(guī)劃>，點(diǎn)擊【求解】，得到結(jié)果后，點(diǎn)擊【確定】即可。

到此，我們就完成了最優(yōu)路徑問(wèn)題的求解，即 S-A-E-D-T，總運(yùn)輸距離為 14。

寫在最后


以上就是小花分享的，使用規(guī)劃求解完成最短路徑問(wèn)題的方法，你學(xué)會(huì)了嗎？簡(jiǎn)單 4 步，即可輕松搞定哦！

? 將有向賦權(quán)網(wǎng)絡(luò)轉(zhuǎn)換成含起止點(diǎn)距離的表格形式；

? 建立表示是否經(jīng)過(guò)的 0/1 變量和路徑距離之間的計(jì)算模型；

? 明確起終點(diǎn)和途徑點(diǎn)的凈流量限制值，并設(shè)置凈流量計(jì)算公式；

? 設(shè)置規(guī)劃求解器，求解最短路徑。

規(guī)劃求解是一個(gè)功能強(qiáng)大的 Excel 加載項(xiàng)，只要我們將實(shí)際問(wèn)題以合適的方式置入 Excel 表格中，設(shè)置基于變量的目標(biāo)值及限制條件，我們就可以解決復(fù)雜的最優(yōu)解問(wèn)題。

后續(xù)有機(jī)會(huì)，小花還將持續(xù)分享其他經(jīng)典的最優(yōu)解問(wèn)題 Excel 求解方案，敬請(qǐng)期待吧！

如果你還想了解更多的 Excel 知識(shí)，更輕松高效地解決求解問(wèn)題，?我推薦你參加《3 天 Excel 集訓(xùn)營(yíng)》！

為期 3 天的課程專為職場(chǎng)人準(zhǔn)備，全部基于職場(chǎng)真實(shí)表格案例設(shè)計(jì)，還有很多超實(shí)用 Excel 技巧教學(xué)。

每天學(xué)習(xí)大概?30 分鐘，從日常的功能出發(fā)，全程演示，一課一練，夯實(shí)進(jìn)階每一步。

3 天 Excel 集訓(xùn)營(yíng)

原價(jià)?99?元

現(xiàn)在只需1元

現(xiàn)在報(bào)名還送

【35 個(gè)常用函數(shù)說(shuō)明】

??????

*廣告