資源描述：
《第七章運輸問題ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、運輸問題在工商管理中有著廣泛的應用，它是一類特殊的線性規(guī)劃問題，對于運輸問題，當然可以用前面所介紹的單純形法進行求解，但由于這類線性規(guī)劃問題在結構上有其特殊性，我們可以找到比標準單純形法更簡單有效的專門方法，從而節(jié)約計算時間和費用，因此，這里把運輸問題單列一章進行討論。本章介紹運輸問題的模型、表上作業(yè)法以及運輸問題的一些實際應用。運問題輸?shù)诹乱弧⑦\輸問題的提出及其數(shù)學模型一般的運輸問題就是要解決把某種產(chǎn)品從若干個產(chǎn)地調(diào)運到若干個銷地，在每個產(chǎn)地的供應量與每個銷地的需求量已知，并知道各地之間的運輸單價的前提下，如何確定一個使得總的運輸費用
2、最小的方案。例題1：某公司從兩個產(chǎn)地A1，A2將產(chǎn)品運往三個銷地B1，B2，B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地的單位產(chǎn)品運費如表3-1所示。問如何調(diào)運，使得總運輸費最??？解：從表中可以看到，A1，A2兩個產(chǎn)地的總產(chǎn)量為500件；B1，B2，B3三個銷地的總銷量為500件，因此這是一個產(chǎn)銷平衡的運輸問題。把A1，A2的產(chǎn)量全部分配給B1，B2，B3，正好滿足這三個銷地的需要。此數(shù)學模型當然可用線性規(guī)劃的常用方法求解（比如單純形法），但求解的程序相對復雜，即使利用計算機程序來求解，其輸入和解決問題的規(guī)模都受到限制。因此，管理運
3、籌學中有專門的求解運輸問題的程序，一般只要輸入產(chǎn)點數(shù)，各產(chǎn)地的產(chǎn)量，銷點數(shù)，各銷地的銷量，以及各產(chǎn)地到各銷地的運輸單價，立即可得到運輸問題的最優(yōu)解。把本例的相關數(shù)據(jù)輸入運輸問題的程序，得到最優(yōu)解為：先給出一般運輸問題的線性規(guī)劃模型。我們用A1，A2，…，表示某種物資的m個產(chǎn)地；B1，B2，…，Bn表示某種物資的n個銷地；表示產(chǎn)地的產(chǎn)量；表示銷地的銷量；表示把物資從產(chǎn)地i運到銷地j的單位運價；并設為從產(chǎn)地運到銷地的運輸量，則產(chǎn)銷平衡的運輸問題的線性規(guī)劃數(shù)學模型如下所示有時上述問題的一般模型會發(fā)生如下一些變化：求目標函數(shù)值的最大值而不是最小值
4、。有些運輸問題中，其目標是找出利潤最大或營業(yè)額最大的調(diào)運方案，這時要求目標函數(shù)的最大值。當某些運輸線路的運輸能力有一定限制時，這時要在線性規(guī)劃模型的約束條件上加上運輸能力限制的約束條件。當生產(chǎn)總量不等于銷量總量，即產(chǎn)銷不平衡時，這時需要通過一個假想倉庫或假想生產(chǎn)地來化成產(chǎn)銷平衡的問題，具體做法在后面闡述。二、運輸問題的求解---表上作業(yè)法直接采用單純形法求解運輸問題明顯是不利的。好在運輸問題具有特殊的結構，因此可以利用單純形法的原理提出一種直接在運輸表上計算以求解產(chǎn)銷平衡運輸問題的簡便方法--表上作業(yè)法。它大大簡化了計算過程的求解方法計算
5、過程如下：Step1給出初始調(diào)運方案（初始基可行解）。對于有m個產(chǎn)地n個銷地的產(chǎn)銷平衡的問題，從其線性規(guī)劃的模型上可知其有m+n個約束方程，但由于產(chǎn)銷平衡，前m個約束方程之和等于后n個約束方程之和，所以其數(shù)學模型最多只有m+n-1個獨立的約束方程。實際上其正好是m+n-1個獨立的約束方程，也就是說運輸問題的約束方程組系數(shù)矩陣的秩等于m+n-1，因此其基可行解中基變量的個數(shù)為m+n-1。表上作業(yè)法中找初始基可行解，就是在m×n產(chǎn)銷平衡表上找出m+n-1個數(shù)字格，其相應的調(diào)運量就是基變量，格子中所填寫的值即為基變量的值。Step2判斷初始調(diào)運
6、方案是否最優(yōu)求表中各空格（對應于非基變量）的檢驗數(shù)以判定當前解是否最優(yōu)，若已是最優(yōu)解則停止計算；否則轉到下一步。Step3.調(diào)整確定入基變量與出基變量。從一個基可行解轉換成另一個"更好"的基可行解，即進行方案調(diào)整。Step4重復2、3直至得到最優(yōu)解。三、例題某食品公司有三個生產(chǎn)面包的分廠A1，A2，A3，有四個銷售分公司B1，B2，B3，B4，其各分廠每日的產(chǎn)量、各分銷售公司每日的銷量以及各分廠到各分銷售公司的單位運價如表3-2所示。問該公司應如何調(diào)運產(chǎn)品在滿足各銷點的需求量的前提下，總運費最少？Step1求初始調(diào)運方案---最小元素法求
7、初始調(diào)運方案，也就是求初始基可行解有3種方法(西北角法、最小元素法、伏格爾法)，在此只介紹最小元素法。該方法的基本思想是采用“優(yōu)先安排單位運價最小的產(chǎn)地與銷地之間的運輸業(yè)務”，用這個規(guī)則來確定初始基可行解。我們直接在運輸表中的格子里填數(shù)表示基變量。為了把初始基可行解與運價分開，把運價放在每一欄的右上角，每一欄的中間填上初始基可行解（調(diào)運量）見表3-3。在表上找到單位運價最小的開始分配運輸量，并使取盡可能大的值，即取min（4，3）3，把所在空格里填上3，然后把A2的產(chǎn)量改寫為4-3=1，把B1的銷量改寫為3-3=0，并把B1列劃去。在剩下
8、的3×3矩陣里找到運價最小的變量，取min（1，5）=1，A2的產(chǎn)量改為1-1=0，B3的銷量改為5-1=4，并把A2行劃去。在剩下的矩陣里找到運價最小的變量，取min（7，4）=4，A1的產(chǎn)
