《運輸問題》PPT課件

《《運輸問題》PPT課件》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、運輸問題運輸問題及其數(shù)學(xué)模型運輸問題的表上作業(yè)法運輸問題的進(jìn)一步討論例1：某部門有3個生產(chǎn)同類產(chǎn)品的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由4個銷售點（銷地）出售，各工廠的生產(chǎn)量、各銷售點的銷售量（假定單位均為t）以及各工廠到各銷售點的單位運價（元/t）示于下表中要求研究產(chǎn)品如何調(diào)運才能使總運費最小4.1運輸問題及其數(shù)學(xué)模型單位銷地運價產(chǎn)地產(chǎn)量2910291342584257銷量3846A2A3B2A1B3B4B1s2=5s3=7d1=3d2=8d3=4d4=6s1=9供應(yīng)量供應(yīng)地運價需求量需求地2910213428425運輸問題網(wǎng)絡(luò)圖產(chǎn)量約束銷量約束運輸問題的一般提法是

2、：設(shè)某種物資有個產(chǎn)地各產(chǎn)地的產(chǎn)量是有個銷地各銷地的銷量是假定從產(chǎn)地到銷地運輸單位物品的運價是，問怎樣調(diào)運這些物品才能使總運費最??？銷地產(chǎn)地產(chǎn)量銷量運價表當(dāng)產(chǎn)銷平衡時，其模型如下：當(dāng)產(chǎn)大于銷時，其模型是：當(dāng)產(chǎn)小于銷時，其模型是：1、平衡運輸問題必有可行解，也必有最優(yōu)解；運輸問題數(shù)學(xué)模型的特點證明記則令則為運輸問題的一個可行解。事實上：又因所以故是一組可行解。又因為總費用不會為負(fù)值（存在下界）。這說明，運輸問題既有可行解，又必然有下界存在，因此一定有最優(yōu)解存在。2、運輸問題約束條件的系數(shù)矩陣運輸問題數(shù)學(xué)模型的特點對運輸問題數(shù)學(xué)模型的結(jié)構(gòu)約束加以整理，可知其系數(shù)矩

3、陣具有下述形式：m行n行1．運輸問題是一個具有m×n個變量和n+m個等型約束的線性規(guī)劃問題。（4－1）2．運輸問題約束方程組的系數(shù)矩陣是一個只有0和1兩個數(shù)值的稀疏矩陣,其中1的總數(shù)為2×m×n個。3、約束條件系數(shù)矩陣的每一列有兩個非零元素，這對應(yīng)于每一個變量在前m個約束方程中出現(xiàn)一次，在后n個約束方程中也出現(xiàn)一次4、約束條件系數(shù)矩陣的秩是m+n-1。即運輸問題的基變量總數(shù)是m+n-1證明：因A的前m行對應(yīng)元素的和與后n行對應(yīng)元素的和相等，恰好都是：所以A的行向量是線性相關(guān)的。從而r(A)≤m+n.去掉A的第一行，并取如下m+n-1列，得到m+n-1階子式所

4、以r(A)=m+n-1.對于產(chǎn)銷平衡運輸問題，除了上述特點外，還有以下特點：1所有結(jié)構(gòu)約束條件都是等式約束2各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和3、運輸問題的解運輸問題數(shù)學(xué)模型的特點運輸問題是一種線性規(guī)劃問題。前面講述的單純形法是求解線性規(guī)劃問題十分有效的一般方法，因而可用單純形法求解運輸問題。但是當(dāng)用單純形法求解運輸問題時，先得在每個約束條件中引入一個人工變量，這樣一來，即使對于m=3、n=4這樣簡單的運輸問題，變量數(shù)目也會達(dá)到19個之多。因此，我們利用運輸問題數(shù)學(xué)模型的特點，引入了表上作業(yè)法來求解運輸問題4.2用表上作業(yè)法求解運輸問題表上作業(yè)法的基本思想：先

5、設(shè)法給出一個初始方案,然后根據(jù)確定的判別準(zhǔn)則對初始方案進(jìn)行檢查、調(diào)整、改進(jìn)，直至求出最優(yōu)方案，如下圖所示。初始化最優(yōu)性檢驗迭代（Iteration）最優(yōu)？yesSTOPno這和單純形法的求解思想完全一致，但是具體的作法則更加簡捷。例1某部門有3個同類型的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由4個銷售點出售，各工廠的生產(chǎn)量、各銷售點的銷售量（假定單位為t）以及各工廠到銷售點的單位運價（元/t）示于表4-2中，問如何調(diào)運才能使總運費最??？銷地產(chǎn)地產(chǎn)量4124111621039108511622銷量814121448表4-2該運輸問題的數(shù)學(xué)模型為：可以證明：約束矩陣的秩r(A

6、)=m+n-1.基變量的個數(shù)為m+n-1.表上作業(yè)法計算步驟：1、給出初始方案2、檢驗是否最優(yōu)3、調(diào)整調(diào)運方案,Goto2表上作業(yè)法計算步驟：1、給出初始方案2、檢驗是否最優(yōu)3、調(diào)整調(diào)運方案,Goto2下面介紹三種常用的方法。一、給出運輸問題的初始可行解（初始調(diào)運方案）最小元素法西北角法沃格爾(Vogel)法1。最小元素法思想：優(yōu)先滿足運價（或運距）最小的供銷業(yè)務(wù)。銷地產(chǎn)地產(chǎn)量4124111610398511622銷量14121448表3-2①銷地產(chǎn)地產(chǎn)量412411162109108511622銷量8141448表3-2①②銷地產(chǎn)地產(chǎn)量4121121091

7、08511622銷量814121448表3-2①②③銷地產(chǎn)地產(chǎn)量4121182109108116銷量8121448表3-2①②③④銷地產(chǎn)地產(chǎn)量412118210910811銷量81248表3-2①③④⑤②銷地產(chǎn)地產(chǎn)量4128210910811銷量81248表3-2①③④⑤⑥⑥②此時得到一個初始調(diào)運方案（初始可行解）：其余變量全等于零?？傔\費為（目標(biāo)函數(shù)值）此解滿足所有約束條件，且基變量（非零變量）的個數(shù)為6（等于m+n-1=3+4-1=6).⒉西北角法西北角法是優(yōu)先滿足運輸表中西北角（左上角）上空格的供銷需求。銷地產(chǎn)地產(chǎn)量412411210391085116

8、22銷量14121448表3-2銷地產(chǎn)地產(chǎn)量4124