運(yùn)輸問(wèn)題的數(shù)學(xué)模型詳細(xì)講解,有案例 多種方法ppt課件

1、本節(jié)主要內(nèi)容:一、圖上作業(yè)法一、圖上作業(yè)法 在經(jīng)濟(jì)建立中，經(jīng)常碰到物資調(diào)撥中的運(yùn)輸問(wèn)題。例如 煤、鋼材、糧食、木材等物資，在全國(guó)都有假設(shè)干消費(fèi)基地，分別將這些物資調(diào)到各消費(fèi)基地去，應(yīng)如何制定調(diào)運(yùn)方案，使總的運(yùn)輸費(fèi)用最少？問(wèn)題的提出: 運(yùn)輸問(wèn)題的普通提法是：設(shè)某種物資有m個(gè)產(chǎn)地和n個(gè)銷地。產(chǎn)地Ai的產(chǎn)量為 ；銷地Bj的銷量 。從第i個(gè)產(chǎn)地向第j個(gè)銷地運(yùn)輸每單位物資的運(yùn)價(jià)為Cij。 這就是由多個(gè)產(chǎn)地供應(yīng)多個(gè)銷地的單種類物資運(yùn)輸問(wèn)題。問(wèn)如何調(diào)運(yùn)這些物資才干使總運(yùn)費(fèi)到達(dá)最小。), 2 , 1( miai ), 2 , 1( njbj 1、運(yùn)輸問(wèn)題的普通提法單位運(yùn)價(jià)表 1 。即運(yùn)輸問(wèn)題的總產(chǎn)量等于其總銷

2、量，這樣的運(yùn)輸問(wèn)題稱為產(chǎn)銷平衡的運(yùn)輸問(wèn)題。 2 。即運(yùn)輸問(wèn)題的總產(chǎn)量不等于總銷量，這樣的運(yùn)輸問(wèn)題稱為產(chǎn)銷不平衡的運(yùn)輸問(wèn)題。 njjmiiba11 njjmiiba11分兩種情況來(lái)討論： 假設(shè)用xij表示從Ai到Bj的運(yùn)量，那么在產(chǎn)銷平衡的條件下，要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，數(shù)學(xué)模型為： 0, 2 , 1)13(, 2 , 1.min1111ijnjiijmijijminjijijxmiaxnjbxtsxcz2、運(yùn)輸問(wèn)題的數(shù)學(xué)模型其中，ai和bj滿足： 稱為產(chǎn)銷平衡條件。 njjmiiba11將約束方程式展開(kāi)可得11112122111211112222 nnmmnmmmxxaxxaxxaxxxb

3、xxx212 nnmnnbxxxb約束方程式中共mn個(gè)變量，m+n個(gè)約束。行行行行nmAxxxxxxxxxmnmmnn 111111111111111111212222111211 上述模型是一個(gè)線性規(guī)劃問(wèn)題。但是其構(gòu)造很特殊，上述模型是一個(gè)線性規(guī)劃問(wèn)題。但是其構(gòu)造很特殊，特點(diǎn)如下：特點(diǎn)如下：1.變量多mn個(gè)，但構(gòu)造簡(jiǎn)單。 技術(shù)系數(shù)矩陣 該系數(shù)矩陣中每列只需兩個(gè)元素為1，其他的都為零。ijab2.m+n個(gè)約束中有一個(gè)是多余的由于其間含有一個(gè)平衡關(guān)系式 所以R(A)=m+n-1，即解的mn個(gè)變量中基變量為m+n-1個(gè)。二、圖上作業(yè)法二、圖上作業(yè)法 在運(yùn)輸中，假設(shè)運(yùn)用同一種運(yùn)輸工具，那么運(yùn)費(fèi)的計(jì)算

4、往往僅與運(yùn)送物資的多少及里程有關(guān)。因此，在求最正確的運(yùn)輸方案時(shí)，用噸公里作為度量的規(guī)范比用運(yùn)費(fèi)作為度量規(guī)范更加方便、適用。 在求解最正確運(yùn)輸方案時(shí)，用噸公里作為度量單位，還可以在曾經(jīng)畫出的交通圖上進(jìn)展，操作起來(lái)較為簡(jiǎn)單、方便、直觀、快捷。 在鐵路、公路等交通部門經(jīng)常運(yùn)用這種方法決策最優(yōu)運(yùn)輸問(wèn)題，這種方法被稱為圖上作業(yè)法。一編制交通圖和流向圖 交通圖 反映發(fā)點(diǎn)產(chǎn)地與收地銷地及交通線路及其間隔組成的圖形。 發(fā)點(diǎn)用“表示，發(fā)出貨物的數(shù)量記在“之內(nèi)單位：噸 收地銷地用“表示，收取貨物的數(shù)量記在“之內(nèi)單位：噸 兩點(diǎn)之間的線路長(zhǎng)度記在交通線路的旁邊。1、交通圖1、交通圖2、流向圖 流向圖: 在交通圖上表示

5、物資流向的圖被稱為流向圖。在圖中每個(gè)發(fā)點(diǎn)噸數(shù)全部運(yùn)完，每個(gè)收點(diǎn)所需噸數(shù)均已滿足。2、流向圖發(fā)點(diǎn)發(fā)點(diǎn)A到收點(diǎn)到收點(diǎn)B的的運(yùn)輸量，用括號(hào)運(yùn)輸量，用括號(hào)括起。括起。2、流向圖 關(guān)于流向圖的一些規(guī)定 箭頭必需表示物資運(yùn)輸?shù)姆较?流量寫在箭頭的旁邊，加小括號(hào)。 流向不能直接跨越道路上的收點(diǎn)、發(fā)點(diǎn)、交叉點(diǎn) 任何一段弧上最多只能顯示一條流向！即同一段弧上的多條流向必需合并。 除端點(diǎn)外，任何點(diǎn)都可以流進(jìn)和流出 含有圈的流向圖的補(bǔ)充規(guī)定 順時(shí)針?lè)较虻牧飨虮匦璁嬙谌Φ膬?nèi)側(cè)，稱為內(nèi)圈流向 逆時(shí)針?lè)较虻牧飨虮匦璁嬙谌Φ耐鈧?cè)，稱為外圈流向內(nèi)圈流向、外圈流向舉例44426圖：圖：5-144426圖：圖：5-2二對(duì)流向圖的

6、檢驗(yàn) 在物資運(yùn)輸中，把某種物資從各發(fā)點(diǎn)調(diào)到各收點(diǎn)的調(diào)運(yùn)方案是很多的，但我們的目的是找出噸公里數(shù)是最小的調(diào)運(yùn)方案。這就要留意在調(diào)運(yùn)中不要發(fā)生對(duì)物流運(yùn)輸和迂回運(yùn)輸，因此，我們?cè)谥贫飨驁D時(shí)，就要防止它的出現(xiàn)。1不合理的景象1：對(duì)流 1對(duì)流：所謂對(duì)流就是在一段線路上有同一種物資出現(xiàn)相對(duì)運(yùn)輸景象往返運(yùn)輸同一段線路上，兩各方向都有流向，如圖4-4。 甲乙兩地是一種對(duì)流景象。假設(shè)把流向圖改成圖4-5，就可以防止對(duì)流景象，從而可以節(jié)約運(yùn)輸量2010=200(噸公里)。201010(10)(20)乙甲圖 5-3圖 5-4201010(10)(10)乙甲(20)2不合理的景象2：迂回 2迂回：當(dāng)收點(diǎn)與發(fā)點(diǎn)之間的

7、運(yùn)輸線路有兩條或兩條以上時(shí)即交通圖成圈，假設(shè)運(yùn)送的貨物不是走最短線路，那么稱這種運(yùn)輸為迂回運(yùn)輸。 注：當(dāng)交通圖成圈時(shí)，假設(shè)流向圖中內(nèi)圈流向的總長(zhǎng)簡(jiǎn)稱內(nèi)圈長(zhǎng)或外圈流向的總長(zhǎng)簡(jiǎn)稱外圈長(zhǎng)超越整個(gè)圈長(zhǎng)的一半就稱為迂回運(yùn)輸。例如某物資流向圖如圖4-6、4-7所示。迂回運(yùn)輸?shù)呐袆e44426圖：圖：5-544426圖：圖：5-6顯然：圖顯然：圖5-5為迂回運(yùn)輸為迂回運(yùn)輸3、正規(guī)最優(yōu)流向圖 正規(guī)最優(yōu)流向圖：一個(gè)最優(yōu)的調(diào)運(yùn)方案，它的流向圖必是無(wú)對(duì)流、無(wú)迂回的流向圖，稱這種流向圖為正規(guī)流向圖。 物資調(diào)運(yùn)的圖上作業(yè)法就是尋覓一個(gè)無(wú)對(duì)流、無(wú)迂回的正規(guī)流向圖。 步驟如下： 作出一個(gè)無(wú)對(duì)流的初始可行方案； 檢驗(yàn)有無(wú)迂回

8、假設(shè)無(wú)，終了；否那么，調(diào)整，直到最優(yōu)。三、圖上作業(yè)法的求解過(guò)程 1、無(wú)圈的交通圖 2、有圈的交通圖 方法：供需歸鄰站 【例1】求最優(yōu)調(diào)運(yùn)方案324786451A1A2B1B3B2A5A3A4B4 口訣：抓各端，各端供需歸鄰站 即：先滿足端點(diǎn)的要求，逐漸向中間逼近，直至收點(diǎn)與發(fā)點(diǎn)得到全部滿足為止。324786451A1A2B1B3B2A5A3A4B4342347310圖圖 4-8練一練答案 【例2】求最優(yōu)調(diào)運(yùn)方案454786454A1A2B1B3B2B5A38B42273463圖圖 4-9 第一步：變有圈為無(wú)圈。 方法：“丟邊破圈。即丟掉一條邊，破去一個(gè)圈。 留意：丟邊時(shí)，往往是丟掉圈中長(zhǎng)度最大

9、的邊。如下圖第一步： “丟邊破圈454786454A1A2B1B3B2B5A38B42273463 第二步：在無(wú)圈的交通圖上作流向圖。 原那么：先外后內(nèi)，先端點(diǎn)后中間點(diǎn)，要求每個(gè)邊都有流向。當(dāng)某條邊無(wú)流向時(shí)，必需填上運(yùn)輸量為零的虛流向。454786454A1A2B1B3B2B5A38B4227346348 15328圖圖 4-10 第三步：補(bǔ)上丟掉的邊，檢查有無(wú)迂回。 圈B5B4B3A2的圈長(zhǎng)=4+4+5+8=21,內(nèi)圈長(zhǎng)= 4+4+5=1321/2，有迂回，所以流向圖不是最優(yōu)流向圖。需求調(diào)整。 第四步：對(duì)方案進(jìn)展調(diào)整。 方法：找出有迂回圈的流量最小的邊去掉的邊除外，改此邊為丟掉的邊邊B5B4

10、，并補(bǔ)上原來(lái)丟掉的邊邊B5A2，得到新的交通圖。在此交通圖上做新的流向圖。454786454A1A2B1B3B2B5A38B4227346348 15126圖圖 4-11 第五步：對(duì)新方案進(jìn)展檢驗(yàn)。 圈B5B4B3A2的圈長(zhǎng)=4+4+5+8=21,內(nèi)圈長(zhǎng)= 4+5=921/2，外圈長(zhǎng)= 825/2，有迂回，所以流向圖不是最優(yōu)流向圖。需求調(diào)整。 第六步：對(duì)方案進(jìn)展調(diào)整。 方法：找出有迂回圈的流量最小的邊去掉的邊除外，改此邊為丟掉的邊邊A1B3，并補(bǔ)上原來(lái)丟掉的邊邊B1A3，得到新的交通圖。在此交通圖上做新的流向圖。454786454A1A2B1B3B2B5A38B422734633714226圖

11、圖 4-12 可驗(yàn)證：此方案中無(wú)迂回景象。即為最優(yōu)方案。發(fā)收B1B2B3B4B5發(fā)貨量A1347A24228A3145收貨量44462練一練答案 運(yùn)輸問(wèn)題依然是線性規(guī)劃問(wèn)題，可以用線性規(guī)劃法中的單純形法來(lái)處理。但是： 1.運(yùn)輸問(wèn)題所涉及的變量多，呵斥單純形表太大； 2.假設(shè)把技術(shù)系數(shù)矩陣A中的0迭代成非0，會(huì)使問(wèn)題更加復(fù)雜。 以上兩個(gè)緣由使得我們不得不利用運(yùn)輸問(wèn)題的特點(diǎn)設(shè)計(jì)出它的特殊解法表上作業(yè)法。表上作業(yè)法，本質(zhì)上還是單純形法。其步驟如下：1.確定一個(gè)初始可行調(diào)運(yùn)方案?？梢越?jīng)過(guò)最小元素法、西北角法、Vogel 法來(lái)完成；2.檢驗(yàn)當(dāng)前可行方案能否最優(yōu)，常用的方法有閉回路法和位勢(shì)法，用這兩種方法

12、計(jì)算出檢驗(yàn)數(shù)，從而判別方案能否最優(yōu)；3.方案調(diào)整，從當(dāng)前方案出發(fā)尋覓更好方案，常采用閉回路法。 例3 某公司從三個(gè)產(chǎn)地A1、A2、A3 將物品運(yùn)往四個(gè)銷地B1、B2、B3、B4，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表3-4所示 問(wèn)應(yīng)如何調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最小? 即初始根本可行解確實(shí)定，與普通線性規(guī)劃即初始根本可行解確實(shí)定，與普通線性規(guī)劃問(wèn)題不同，產(chǎn)銷平衡運(yùn)輸問(wèn)題總是存在可行解。問(wèn)題不同，產(chǎn)銷平衡運(yùn)輸問(wèn)題總是存在可行解。1、確定初始方案 確定初始根本可行解的方法很多，普通希望方法是既簡(jiǎn)便，又盡能夠接近最優(yōu)解。下面引見(jiàn)兩種方法：最小元素法，西北角法、 Vogel 法1最

13、小元素法 最小元素法的根本思想是優(yōu)先滿足單位運(yùn)價(jià)最小的供銷業(yè)務(wù)。 首先找出運(yùn)價(jià)最小的，并以最大限制滿足其供銷量為原那么確定供銷業(yè)務(wù)。同樣的方法反復(fù)進(jìn)展直到確定了一切的供銷業(yè)務(wù)，得到一個(gè)完好的調(diào)運(yùn)方案即初始根本可行解為止。 銷產(chǎn)A17311310A241928A3974105需求3656201321344653103方案表運(yùn)價(jià)表以此，得到一初始方案：X13=4 , X14=3， X21=3，X23=1， X32=6， X34=3有數(shù)格X11=X31=X12=X22=X33=X24=0空格B1B2B3B4A143A231A363注：有數(shù)格是基變量，共m+n-1=3+4-1=6個(gè)?？崭袷欠腔兞?，共

14、劃去m+n=7條線；假設(shè)填上一個(gè)變量之后能同時(shí)劃去兩條線一行與一列，就須在所劃去的該行或該列填一個(gè)0，此0格當(dāng)有數(shù)格對(duì)待。初始方案運(yùn)費(fèi) Z0=31+64+43+12+310+35=86(元)2西北角法 西北角法與最小元素法不同，它不是優(yōu)先思索具有最小單位運(yùn)價(jià)的供銷業(yè)務(wù)，而是優(yōu)先滿足運(yùn)輸表中西北角左上角上空格的供銷需求。 銷銷產(chǎn)產(chǎn)A17311310A241928A3974105需求需求365620342236方案表運(yùn)價(jià)表 例例4 某公司下屬有消費(fèi)一種化工產(chǎn)品的三個(gè)產(chǎn)地某公司下屬有消費(fèi)一種化工產(chǎn)品的三個(gè)產(chǎn)地A1、A2、A3 ，有四個(gè)銷售點(diǎn)，有四個(gè)銷售點(diǎn)B1、B2、B3、B4 銷售這種化工產(chǎn)品。銷售

15、這種化工產(chǎn)品。各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每噸產(chǎn)品各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每噸產(chǎn)品的運(yùn)費(fèi)百元如下表所示。的運(yùn)費(fèi)百元如下表所示。 銷產(chǎn)A1753859A2402948A3806375需求35405565195 問(wèn)應(yīng)如何調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最小問(wèn)應(yīng)如何調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最小? 解：用西北角法求初始根本可行解解：用西北角法求初始根本可行解 銷產(chǎn)A1753859A2402948A3806375需求35405565195方案表運(yùn)價(jià)表35400401565(3)伏格爾法次小運(yùn)價(jià)與最小運(yùn)價(jià)之差大者先安排 銷銷產(chǎn)產(chǎn)A17311310A241928A3974105需求需求3

16、65620方案表運(yùn)價(jià)表 2 5 1 3 01160123 2 1 2 3765122、判別當(dāng)前方案能否為最優(yōu) 用單純形法解線性規(guī)劃問(wèn)題時(shí)，在迭代過(guò)程中每次求得一個(gè)根本可行解以后，都要檢驗(yàn)它是不是最優(yōu)解，假設(shè)不是最優(yōu)解，就要繼續(xù)進(jìn)展迭代，直到求得最優(yōu)解或者斷定無(wú)最優(yōu)解。 表上作業(yè)法是用以下兩種方法來(lái)處置這個(gè)問(wèn)題的：閉回路法和位勢(shì)法。1閉回路法 在單純形法中，為了檢驗(yàn)一個(gè)根本可行解是不是最優(yōu)解，需求求出一切非基變量的檢驗(yàn)數(shù)。在運(yùn)輸問(wèn)題中，每個(gè)空格對(duì)應(yīng)一個(gè)非基變量。因此，我們需求求出每個(gè)空格的檢驗(yàn)數(shù)。 由于目的要求極小，因此，當(dāng)一切的檢驗(yàn)數(shù)都大于或等于零時(shí)該調(diào)運(yùn)方案就是最優(yōu)方案。 B1B2B3B4A

17、143A231A363 對(duì)方案表中每一空格，確定一條由空格出發(fā)的閉回路。 閉回路是由程度或垂直線組成的閉合圖形。閉回路上的頂點(diǎn)除了這個(gè)空格外，其他均為有數(shù)格。B1B2B3B4A143A231A363 可以證明，對(duì)每一個(gè)空格都存在而且獨(dú)一存在這樣一條封鎖回路。B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363計(jì)算出空格的檢驗(yàn)數(shù)等于閉回路上由此空格起奇數(shù)頂點(diǎn)運(yùn)價(jià)與偶數(shù)頂點(diǎn)運(yùn)價(jià)負(fù)值的代數(shù)和。B1B2B3B4A143A231A363 11=3 - 3+2 - 1=1 11=3 - 3+2 -

18、1=1 22= 9-2+30+54 =1 22= 9-2+30+54 =1 31= 7-5+103+21=1031= 7-5+103+21=10 12=11 - 10+5 - 4=212=11 - 10+5 - 4=2 24= 810 +3 2 =-124= 810 +3 2 =-1 33=10 - 5+10 -3=1233=10 - 5+10 -3=12那么當(dāng)前方案是最優(yōu)的，假設(shè)尚有空格檢驗(yàn)數(shù)小于零，闡明當(dāng)前方案尚有待調(diào)整。 假設(shè)一切的空格檢驗(yàn)數(shù)都大于等于零，闡明任何一個(gè)空格處調(diào)運(yùn)1單位都會(huì)引起總本錢的上升，這闡明當(dāng)前方案不能再改良，即定為最優(yōu)方案。 ij 具有確切的經(jīng)濟(jì)意義，它表示由具有確

19、切的經(jīng)濟(jì)意義，它表示由Ai往往Bj增運(yùn)增運(yùn)1單單位時(shí)，引起的總運(yùn)輸本錢的變化數(shù)。位時(shí)，引起的總運(yùn)輸本錢的變化數(shù)。B1B2B3B4A143A231A363 閉回路法的主要缺陷是：當(dāng)變量個(gè)數(shù)較多閉回路法的主要缺陷是：當(dāng)變量個(gè)數(shù)較多時(shí)，尋覓閉回路以及計(jì)算都會(huì)產(chǎn)生困難。時(shí)，尋覓閉回路以及計(jì)算都會(huì)產(chǎn)生困難。2位勢(shì)法對(duì)偶變量法 對(duì)于一個(gè)調(diào)運(yùn)方案的每列賦予一個(gè)值，稱為列位勢(shì)，記 ，對(duì)于每行賦予一個(gè)值，稱為行位勢(shì)，記為 nvvv,21muuu,21ijjicvu 那么檢驗(yàn)數(shù)為： ij = cij - ui - vj i = 1, , m ; j = 1, , n它們的值由以下方程組決議：其中， cij 是一切

20、基變量數(shù)字格xij 的運(yùn)價(jià)系數(shù) 。 銷銷產(chǎn)產(chǎn)A17311310A241928A3974105需求需求3656201321344653103方案表運(yùn)價(jià)表u1 + v3 = c13 = 3 u2 + v1 = c21 = 1u3 + v2 = c32 = 4u1u2u3v1v3v2v4u1 + v4 = c14 = 10u2 + v3 = c23 = 2 u3 + v4 = c34 = 5 令u1 = 5 那么有 v4 = 5 v3 = -2u2 = 4 u3=0v2=4v1= -311 = c11 u1 - v1 = 3 5 (-3) = 1 12 = c12 u1 v2 = 11 5 4 =

21、222 = c22 u2 v2 = 9 4 4 = 1 24 = c24 u2 v4 = 8 4 5 = -1 31 = c31 u3 - v1 = 7 0 (-3) = 10 33 = c33 u3 v3 = 10 0 (-2) = 12 再求非基變量空格檢驗(yàn)數(shù)： u1 + v3 = c13 = 3 u2 + v1 = c21 = 1u3 + v2 = c32 = 4u1 + v4 = c14 = 10u2 + v3 = c23 = 2 u3 + v4 = c34 = 5 1在有數(shù)格上填上相應(yīng)的運(yùn)價(jià) 銷銷產(chǎn)產(chǎn)A143A231A363方案表運(yùn)價(jià)表 銷銷產(chǎn)產(chǎn)A1310A212A345u1u2u3

22、v1v3v2v4位勢(shì)法在表上進(jìn)展： (2) 設(shè)u1=0，然后根據(jù)cij=ui+vj 有數(shù)格，依次求得ui和vj的值，并填在相應(yīng)的位置 銷銷產(chǎn)產(chǎn)A1310A212A345u1u2u3v1v3v2v4239100-1-5計(jì)算(ui+vj )表，把(ui+vj )位勢(shì)和值填在表中相應(yīng)位置上，并將有數(shù)格位置上的值ui+vj 加上括號(hào)以示區(qū)別。 2989-3-2(ui+vj )表 銷銷產(chǎn)產(chǎn)A1311310A21928A374105運(yùn)價(jià)表 銷銷產(chǎn)產(chǎn)A129(3)(10)A2(1)8(2)9A3-3(4)-2(5)u1u2u3v1v3v2v4239100-1-5檢驗(yàn)數(shù)表 銷銷產(chǎn)產(chǎn)A1A2A33計(jì)算檢驗(yàn)數(shù)表ij = cij ( ui + vj)(ui+vj )表121-110123、調(diào)整方案 假設(shè)在檢驗(yàn)數(shù)上有某空格的檢驗(yàn)數(shù)為負(fù)，那么可改良方案，降低本錢。調(diào)整的方法是從具有負(fù)檢驗(yàn)數(shù)的空格出發(fā)(有多個(gè)負(fù)檢驗(yàn)數(shù)時(shí)，選擇絕對(duì)值大的一個(gè))，沿它的閉回路進(jìn)展調(diào)整，即在堅(jiān)持方案可行的條件下，盡量添加空格