1、第三章 運輸問題上頁上頁下頁下頁返回返回運輸問題運輸問題數(shù)學(xué)模型的特點 運輸問題一定存在有界的最優(yōu)解 運輸問題約束條件的系數(shù)矩陣 約束條件系數(shù)矩陣每列只有兩個1,其余為0 約束條件中線性獨立方程個數(shù)最多為m+n-1,運輸問題的解中的基變量數(shù)一般為m+n-1個； 對產(chǎn)銷平衡運輸問題 約束條件均為等式，且產(chǎn)量之和=銷量之和；上頁上頁下頁下頁返回返回運輸問題表上作業(yè)法 表上作業(yè)法是單純形法在求解運輸問題的一種簡便方法。 表上作業(yè)法的步驟：計算表中空格檢驗數(shù)表上給出m+n-1個數(shù)字格檢驗數(shù)是否全大于或等于零表上作業(yè)法最小元素法、Vogel法閉回路法、位勢法上頁上頁下頁下頁返回返回運輸問題表上作業(yè)法換基

2、：表上調(diào)整（閉回路調(diào)整）重復(fù)上述過程,運輸問題必有最優(yōu)解停止最優(yōu)解？是否表上作業(yè)法上頁上頁下頁下頁返回返回上頁上頁下頁下頁返回返回運輸問題一、產(chǎn)銷不平衡的運輸問題（）若總產(chǎn)量大于總銷量，即njjmiiba11minjjinbab111令假想銷地的銷量為：上頁上頁下頁下頁返回返回運輸問題（）若總產(chǎn)量小于總銷量，即njjmiiba11miinjjmaba111令假想產(chǎn)地的產(chǎn)量為：一、產(chǎn)銷不平衡的運輸問題上頁上頁下頁下頁返回返回運輸問題二、有轉(zhuǎn)運的運輸問題 由于問題中所有產(chǎn)地、中間轉(zhuǎn)運站、銷地都可以看做產(chǎn)地,又可看做銷地.因此,把整個問題當(dāng)作擴大的運輸問題. 建立單位運價表，將原表中不可能的運輸方案

3、的運價用任意大的正數(shù)M代替. 所有中間轉(zhuǎn)運站的產(chǎn)量小于等于銷量. 擴大的運輸問題中原來的產(chǎn)地與銷地因為也起轉(zhuǎn)運站作用，所以，在原來產(chǎn)量和銷量的數(shù)字上加上總轉(zhuǎn)運量.上頁上頁下頁下頁返回返回習(xí)題三3.1已知運輸問題的產(chǎn)銷地的供需量與單位運價表如表3-35至表3-36所示，試用表上作業(yè)法求各題最優(yōu)解，同時用Vogel法求出各題的近似最優(yōu)解。101515551816142252097121511202103214321AAABBBB銷量產(chǎn)量銷地銷地產(chǎn)地產(chǎn)地表3-35上頁上頁下頁下頁返回返回運輸問題表上作業(yè)法用Vogel法得到的近似最優(yōu)解1015155552515100151053214321AAABB

4、BB銷量產(chǎn)量銷地銷地產(chǎn)地產(chǎn)地33511109157102525 z目標(biāo)函數(shù)值目標(biāo)函數(shù)值上頁上頁下頁下頁返回返回運輸問題表上作業(yè)法檢驗數(shù)表8171704000016033214321AAABBBB銷地銷地產(chǎn)地產(chǎn)地所有檢驗數(shù)都大于等于零，所以用Vogel法得到的解即為最優(yōu)解。上頁上頁下頁下頁返回返回習(xí)題三15201010263435257496721483214321AAABBBB銷量產(chǎn)量銷地銷地產(chǎn)地產(chǎn)地表3-36上頁上頁下頁下頁返回返回習(xí)題三因產(chǎn)大于銷,設(shè)一虛擬銷地B5,建立產(chǎn)銷平衡表.產(chǎn)地銷地上頁上頁下頁下頁返回返回習(xí)題三產(chǎn)地銷地用Vogel法得到的近似最優(yōu)解上頁上頁下頁下頁返回返回運輸問題表

5、上作業(yè)法193z檢驗數(shù)表產(chǎn)地銷地所有檢驗數(shù)都大于等于零，故用所有檢驗數(shù)都大于等于零，故用Vogel法得到法得到的解即為最優(yōu)解，對應(yīng)的目標(biāo)函數(shù)值的解即為最優(yōu)解，對應(yīng)的目標(biāo)函數(shù)值上頁上頁下頁下頁返回返回習(xí)題三3.5已知運輸問題的產(chǎn)銷平衡表、最優(yōu)調(diào)運方案及單位運價表分別如下表3-38和3-39所示：產(chǎn)地銷地表3-38 產(chǎn)銷平衡表及最優(yōu)方案上頁上頁下頁下頁返回返回習(xí)題三試分別分析:(a)從A2至B2的單位運價在什么范圍變化時,上述最優(yōu)調(diào)運方案不變;(b)從A2至B4的單位運價變?yōu)楹沃禃r,將有無限多最優(yōu)調(diào)運方案.除表3-38中給出方案,至少再寫出其他兩個最優(yōu)調(diào)運方案;(c)若從A3-B1的通道因故暫時封

6、閉,試提出一個較為簡便的方法重新找出最優(yōu)運輸方案;(d)以x12,x14,x21,x22,x23,x31為基變量列出本問題若用單純形法求解時的單純形表,并判別給出方案是否為最優(yōu).產(chǎn)地銷地表3-39 單位運價表上頁上頁下頁下頁返回返回習(xí)題三10301802401001003222222222222cccccc檢驗數(shù)表算得檢驗數(shù)表的值看成未知，重新計將單位運價表中解：22)(ca產(chǎn)地銷地上頁上頁下頁下頁返回返回習(xí)題三17017111724242424ccc最優(yōu)方案.)(242424可通過閉回路法求的值，驗數(shù)，只影響的變化不會影響其他檢解： cb產(chǎn)地銷地上頁上頁下頁下頁返回返回習(xí)題三其他最優(yōu)方案：方案一產(chǎn)地銷地方案二產(chǎn)地銷地上頁上頁下頁下頁返回返回習(xí)題三新最優(yōu)方案再繼續(xù)表上作業(yè)法問題的初始可行方案可將原最優(yōu)方案作為該無窮大為則它們之間的單位運價的通道因故暫時封閉，解：,),(M)(13BAc產(chǎn)地銷地產(chǎn)地銷地新單位運價