《運(yùn)輸問(wèn)題》PPT課件

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

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

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

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

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

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

6、)=m+n-1.基變量的個(gè)數(shù)為m+n-1.表上作業(yè)法計(jì)算步驟：1、給出初始方案2、檢驗(yàn)是否最優(yōu)3、調(diào)整調(diào)運(yùn)方案,Goto2表上作業(yè)法計(jì)算步驟：1、給出初始方案2、檢驗(yàn)是否最優(yōu)3、調(diào)整調(diào)運(yùn)方案,Goto2下面介紹三種常用的方法。一、給出運(yùn)輸問(wèn)題的初始可行解（初始調(diào)運(yùn)方案）最小元素法西北角法沃格爾(Vogel)法1。最小元素法思想：優(yōu)先滿足運(yùn)價(jià)（或運(yùn)距）最小的供銷業(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①③④⑤⑥⑥②此時(shí)得到一個(gè)初始調(diào)運(yùn)方案（初始可行解）：其余變量全等于零?？傔\(yùn)費(fèi)為（目標(biāo)函數(shù)值）此解滿足所有約束條件，且基變量（非零變量）的個(gè)數(shù)為6（等于m+n-1=3+4-1=6).⒉西北角法西北角法是優(yōu)先滿足運(yùn)輸表中西北角（左上角）上空格的供銷需求。銷地產(chǎn)地產(chǎn)量412411210391085116

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