本期繼續(xù)進(jìn)行運(yùn)籌學(xué)算法的講解，我們將對比求解運(yùn)輸問題初始調(diào)運(yùn)方案的西北角法、最小元素法、沃格爾法并介紹實現(xiàn)三種方法的MATLAB相關(guān)代碼，以幫助大家利用工具快速求解運(yùn)輸問題，做到事半功倍。話不多說，我們一起來看看吧！

表上作業(yè)法是求解運(yùn)輸問題的一種簡便而有效的方法，其求解工作在運(yùn)輸表上進(jìn)行。作為一種迭代的方法，其迭代步驟為：

①按某種規(guī)則找出一個初始解（初始調(diào)運(yùn)方案）；

②對現(xiàn)行解作最優(yōu)性判別；

③若該解不是最優(yōu)解，就在運(yùn)輸表上對它進(jìn)行調(diào)整改進(jìn)，得出一個新解；

④再判別，再改進(jìn)，直至得到最優(yōu)解為止。

此次推文重點為大家介紹表上作業(yè)法的第一步—求解運(yùn)輸問題初始調(diào)運(yùn)方案的三種方法，即西北角法、最小元素法、沃格爾法。

一、方法介紹

1、方法概述

★西北角法

遵循“優(yōu)先安排運(yùn)價表上編號最小的產(chǎn)地和銷地之間（即運(yùn)價表的西北角位置）的運(yùn)輸業(yè)務(wù)”的規(guī)則，從運(yùn)價表的西北角（左上角）格開始，在格內(nèi)標(biāo)上允許取得的最大數(shù)；然后按行（列）標(biāo)下一格的數(shù)；若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去；如此進(jìn)行下去，直至得到一個基本可行解。

★最小元素法

最小元素法的基本思想是就近供應(yīng)，為了減少運(yùn)費(fèi)，優(yōu)先考慮運(yùn)價表中單位運(yùn)價最?。ɑ蜻\(yùn)距最短）的供銷業(yè)務(wù)，最大限度地滿足其供銷量，從而確定該處的產(chǎn)銷關(guān)系，然后在余下的供銷地關(guān)系中，繼續(xù)按上述方法安排調(diào)運(yùn)，直至安排完所有供銷任務(wù)，得到一個完整的調(diào)運(yùn)方案（完整的解）為止。

★沃格爾（Vogel）法

沃格爾法又稱差值法，該方法考慮到，最初按某一最小單位運(yùn)價優(yōu)先安排物品調(diào)運(yùn)時，在后續(xù)調(diào)運(yùn)過程中卻可能不得不采用運(yùn)費(fèi)很高的其他供銷點，從而使整個運(yùn)輸費(fèi)用增加。沃格爾法的基本思想是在運(yùn)價表中分別計算出各行各列的最小單位運(yùn)價和次小單位運(yùn)價之差，并稱這兩個單位運(yùn)價之差為該銷售地或供應(yīng)地的罰數(shù)，然后按照最小單位運(yùn)價對罰數(shù)最大處安排運(yùn)輸。因為若罰數(shù)的值很大，說明不按最小運(yùn)價組織運(yùn)輸就會造成很大的運(yùn)費(fèi)損失。

2、 方法對比

從本質(zhì)上說，運(yùn)輸問題還是一種線性規(guī)劃問題，可以用迭代法進(jìn)行求解，西北角法、最小元素法、沃格爾（Vogel）法是求解運(yùn)輸問題初始基可行解的3種方法。西北角法并沒有對運(yùn)價進(jìn)行考量，只是從西北角處進(jìn)行迭代，因此其求解出的初始方案往往離最優(yōu)解還有一定差距，后續(xù)進(jìn)行解的改進(jìn)時可能需要的次數(shù)較多，現(xiàn)已不常使用。最小元素法考慮到了單位運(yùn)價的大小，但在某些問題中也有著因追求最小運(yùn)費(fèi)而使得其他供銷地運(yùn)費(fèi)陡然增加的弊端。沃格爾（Vogel）法求解初始調(diào)運(yùn)方案時，考慮到了最小單位運(yùn)價與次小單位運(yùn)價的差額給組織運(yùn)輸關(guān)系帶來的影響，因此其求解出的初始方案往往更接近最優(yōu)解，后續(xù)在進(jìn)行解的改進(jìn)時所需次數(shù)也相對較少，甚至在某些簡單的問題中，其初始調(diào)運(yùn)方案可能就已經(jīng)是最優(yōu)調(diào)運(yùn)方案。與前兩種方法相比，沃格爾（Vogel）法的應(yīng)用更加廣泛。

二、算法實現(xiàn)

1、 例題介紹

某部門有3個生產(chǎn)同類的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由4個銷售點（銷地）出售，各工廠的生產(chǎn)量、各銷售點的銷售量（假定單位均為t）以及各工廠到各銷售點的單位運(yùn)價（元/t）示于下表中。要求研究產(chǎn)品如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最小。

2、 平臺實現(xiàn)?

此次我們以上述例題為例，借助MATLAB平臺分別介紹西北角法、最小元素法以及沃格爾法三種方法的詳細(xì)代碼、代碼調(diào)用方法以及最終的運(yùn)行結(jié)果。由于篇幅有限，小編接下來只展示每種方法的部分代碼，小伙伴們可以關(guān)注“運(yùn)籌學(xué)”公眾號→后臺回復(fù)“MATLAB之運(yùn)輸問題”獲取三種方法的完整代碼。

（1）西北角法

★?代碼展示

★?代碼調(diào)用及運(yùn)行結(jié)果

點擊運(yùn)行“N_W”文件，在命令行窗口依次“輸入運(yùn)價矩陣→回車→輸入產(chǎn)量矩陣→回車→輸入銷量矩陣→回車”，便可得到初始調(diào)運(yùn)方案結(jié)果，結(jié)果中等于-1的為非基元素，不等于-1的為基元素?？梢钥闯觯珹1運(yùn)往B1的產(chǎn)品數(shù)量為8t，A1運(yùn)往B2的產(chǎn)品數(shù)量為8t，A2運(yùn)往B2的產(chǎn)品數(shù)量為6t，A2運(yùn)往B3的產(chǎn)品數(shù)量為4t，A3運(yùn)往B3的產(chǎn)品數(shù)量為8t，A3運(yùn)往B4的產(chǎn)品數(shù)量為14t。

（2）最小元素法

★?代碼展示

★?代碼調(diào)用及運(yùn)行結(jié)果

點擊運(yùn)行“min_element”文件，在命令行窗口依次“輸入運(yùn)價矩陣→回車→輸入產(chǎn)量矩陣→回車→輸入銷量矩陣→回車”，便可得到初始調(diào)運(yùn)方案結(jié)果，結(jié)果中等于-1的為非基元素，不等于-1的為基元素?？梢钥闯?，A1運(yùn)往B3的產(chǎn)品數(shù)量為10t，A1運(yùn)往B4的產(chǎn)品數(shù)量為6t，A2運(yùn)往B1的產(chǎn)品數(shù)量為8t，A2運(yùn)往B3的產(chǎn)品數(shù)量為2t，A3運(yùn)往B2的產(chǎn)品數(shù)量為14t，A3運(yùn)往B4的產(chǎn)品數(shù)量為8t。

（3）沃格爾（Vogel）法

★?代碼展示

★?代碼調(diào)用及運(yùn)行結(jié)果

點擊運(yùn)行“Vogel”文件，在命令行窗口依次“輸入運(yùn)價矩陣→回車→輸入產(chǎn)量矩陣→回車→輸入銷量矩陣→回車”，便可得到初始調(diào)運(yùn)方案結(jié)果，結(jié)果中等于-1的為非基元素，不等于-1的為基元素?？梢钥闯?，A1運(yùn)往B3的產(chǎn)品數(shù)量為12t，A1運(yùn)往B4的產(chǎn)品數(shù)量為4t，A2運(yùn)往B1的產(chǎn)品數(shù)量為8t，A2運(yùn)往B4的產(chǎn)品數(shù)量為2t，A3運(yùn)往B2的產(chǎn)品數(shù)量為14t，A3運(yùn)往B4的產(chǎn)品數(shù)量為8t。

☆ 參考資料：

https://download.csdn.net/download/weixin_42576279/10908971?spm=1001.2014.3001.5503

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

后臺回復(fù)“MATLAB之運(yùn)輸問題”獲取三種方法的完整代碼

作者 | 曹貴玲 尹萌娟

責(zé)編 | 何洋洋

審核 | 徐小峰

· 知乎｜運(yùn)籌說 ·

· Bilibili｜運(yùn)籌說 ·

· CSDN｜運(yùn)籌說 ·