運輸問題課件例題1:某公司從兩個產地A1,A2將產品運往三個銷地B1,B2,B3,各產地得產量、各銷地得銷量與各產地運往各銷地得單位產品運費如表3-1所示。問如何調運,使得總運輸費最小？

解:從表中可以瞧到,A1,A2兩個產地得總產量為500件;B1,B2,B3三個銷地得總銷量為500件,因此這就是一個產銷平衡得運輸問題。把A1,A2得產量全部分配給B1,B2,B3,正好滿足這三個銷地得需要。

此數學模型當然可用線性規劃得常用方法求解(比如單純形法),但求解得程序相對復雜,即使利用計算機程序來求解,其輸入與解決問題得規模都受到限制。因此,管理運籌學中有專門得求解運輸問題得程序,一般只要輸入產點數,各產地得產量,銷點數,各銷地得銷量,以及各產地到各銷地得運輸單價,立即可得到運輸問題得最優解。把本例得相關數據輸入運輸問題得程序,得到最優解為:

先給出一般運輸問題得線性規劃模型。

我們用A1,A2,…,表示某種物資得m個產地;B1,B2,…,Bn表示某種物資得n個銷地;表示產地得產量;表示銷地得銷量;表示把物資從產地i運到銷地j得單位運價;并設為從產地運到銷地得運輸量,則產銷平衡得運輸問題得線性規劃數學模型如下所示

有時上述問題得一般模型會發生如下一些變化:

求目標函數值得最大值而不就是最小值。有些運輸問題中,其目標就是找出利潤最大或營業額最大得調運方案,這時要求目標函數得最大值。

當某些運輸線路得運輸能力有一定限制時,這時要在線性規劃模型得約束條件上加上運輸能力限制得約束條件。當生產總量不等于銷量總量,即產銷不平衡時,這時需要通過一個假想倉庫或假想生產地來化成產銷平衡得問題,具體做法在后面闡述。

大家有疑問的，可以詢問和交流可以互相討論下，但要小聲點二、運輸問題得求解

---表上作業法

直接采用單純形法求解運輸問題明顯就是不利得。好在運輸問題具有特殊得結構,因此可以利用單純形法得原理提出一種直接在運輸表上計算以求解產銷平衡運輸問題得簡便方法--表上作業法。它大大簡化了計算過程得求解方法

計算過程如下:

Step1給出初始調運方案(初始基可行解)。

對于有m個產地n個銷地得產銷平衡得問題,從其線性規劃得模型上可知其有m+n個約束方程,但由于產銷平衡,前m個約束方程之與等于后n個約束方程之與,所以其數學模型最多只有m+n-1個獨立得約束方程。實際上其正好就是m+n-1個獨立得約束方程,也就就是說運輸問題得約束方程組系數矩陣得秩等于m+n-1,因此其基可行解中基變量得個數為m+n-1。表上作業法中找初始基可行解,就就是在m×n產銷平衡表上找出m+n-1個數字格,其相應得調運量就就是基變量,格子中所填寫得值即為基變量得值。

Step2判斷初始調運方案就是否最優

求表中各空格(對應于非基變量)得檢驗數以判定當前解就是否最優,若已就是最優解則停止計算;否則轉到下一步。

Step3、調整

確定入基變量與出基變量。從一個基可行解轉換成另一個"更好"得基可行解,即進行方案調整。

Step4重復2、3直至得到最優解。

三、例題某食品公司有三個生產面包得分廠A1,A2,A3,有四個銷售分公司B1,B2,B3,B4,其各分廠每日得產量、各分銷售公司每日得銷量以及各分廠到各分銷售公司得單位運價如表3-2所示。問該公司應如何調運產品在滿足各銷點得需求量得前提下,總運費最少？

Step1求初始調運方案---最小元素法

求初始調運方案,也就就是求初始基可行解有3種方法(西北角法、最小元素法、伏格爾法),

在此只介紹最小元素法。該方法得基本思想就是采用

“優先安排單位運價最小得產地與銷地之間得運輸業務”,

用這個規則來確定初始基可行解。

我們直接在運輸表中得格子里填數表示基變量。為了把初始基可行解與運價分開,把運價放在每一欄得右上角,每一欄得中間填上初始基可行解(調運量)見表3-3。

在表上找到單位運價最小得開始分配運輸量,并使取盡可能大得值,即取min(4,3)3,把所在空格里填上3,然后把A2得產量改寫為4-3=1,把B1得銷量改寫為3-3=0,并把B1列劃去。在剩下得3×3矩陣里找到運價最小得變量,取min(1,5)=1,A2得產量改為1-1=0,B3得銷量改為5-1=4,并把A2行劃去。在剩下得矩陣里找到運價最小得變量,取min(7,4)=4,A1得產量改為3,B3得銷量改為0,并劃去B3列。

Step2最優解得判別--位勢法

同單純形法一樣,表上作業法也就是用檢驗數來檢驗方案得最優性。檢驗已得得運輸方案就是否就是最優得方法有兩種:一種就是閉回路法,

一種就是位勢法。

Step3方案得調整

表中帶圈得數字就是非基變量得檢驗數,可知所有檢驗數都大于等于零(基變量得檢驗數都等于零),此解就是最優解,這時最小總運輸費用為85元,具體得運輸方案如下:A1分廠運