1、第四章 運(yùn)輸問題Transportation Problems 數(shù)學(xué)模型及其解法,2,第一節(jié) 運(yùn)輸問題的數(shù)學(xué)模型,一、問題的提出,例1,產(chǎn)銷平衡表,3,二、運(yùn)輸問題的一般數(shù)學(xué)模型,有m個(gè)產(chǎn)地生產(chǎn)某種物資，有n個(gè)地區(qū)需要該類物資；,設(shè)xij表示產(chǎn)地 Ai 運(yùn)往銷地B j 的物資量，cij表示對(duì)應(yīng)的單位運(yùn)費(fèi)，則我們有運(yùn)輸問題的數(shù)學(xué)模型如下：,令a1, a2, , am表示各產(chǎn)地產(chǎn)量， b1, b2, , bn表示各銷地的銷量；,一般滿足產(chǎn)銷平衡：ai=bj,4,三、約束系數(shù)矩陣的特征,1. 系數(shù)矩陣的形式,在例1中，運(yùn)輸問題的系數(shù)矩陣A為：,2. 系數(shù)矩陣的特征,特征1：矩陣的行與平衡表行、列一一

2、對(duì)應(yīng),5,一般情況下,運(yùn)輸問題的決策變量xij的系數(shù)列向量為:,特征2：矩陣的列向量只有兩個(gè)元素為1,6,特征3：r(A)=m + n1,7,8,四、閉回路,1. 概念,例2,1) 數(shù)字格,2) 空格,3) 閉回路,閉回路：以某空格為起點(diǎn)，用水平或垂直線向前劃，當(dāng)碰到某恰當(dāng)?shù)臄?shù)字格后，轉(zhuǎn)900繼續(xù)前進(jìn)，直到回到起始空格為止。,9,10,11,12,13,14,15,2. 閉回路上的變量所對(duì)應(yīng)的系數(shù)列向量組線性相關(guān)性,結(jié)論1： 運(yùn)輸問題一組變量構(gòu)成閉回路的充要條件是這組變量所對(duì)應(yīng)的系數(shù)列向量線性相關(guān),16,結(jié)論2： 運(yùn)輸問題的一個(gè)可行解是基可行解的充要條件是：,1）數(shù)字格的個(gè)數(shù)為m+n-1個(gè),2

3、） m+n-1個(gè)數(shù)字格不構(gòu)成閉回路。,17,第二節(jié) 表上作業(yè)法,運(yùn)輸問題模型是線性規(guī)劃模型，當(dāng)然可以用單純形法求解，但由于其系數(shù)矩陣具有特殊形式，可以使單純形法的操作更為簡便，這就是表上作業(yè)法（其實(shí)質(zhì)是單純形法）。,18,初始基可行解 的確定,結(jié)束,Y,調(diào)整,N,一、表上作業(yè)法的步驟,19,二、初始基可行解的確定,與一般LP問題不同，產(chǎn)銷平衡的運(yùn)輸問題一定存在可行解。,20,1.最小元素法,基本思想:,就“近”供應(yīng)，從運(yùn)輸表中最小運(yùn)價(jià)所在格開始確定供銷關(guān)系。,缺點(diǎn):,為節(jié)省一處費(fèi)用，會(huì)使別處費(fèi)用增加很多，因此，其初始基可行解往往離最優(yōu)解甚遠(yuǎn)，需要較多的迭代過程。,21,例3,22,2.伏格爾法

4、（Vogel）,基本思想:,同時(shí)考慮每一產(chǎn)地（銷地）與每一銷地（產(chǎn)地）之間的最小運(yùn)價(jià)和次小運(yùn)價(jià)，若兩者差額大，說明若不能按最小運(yùn)價(jià)供應(yīng)，就有可能按次小運(yùn)價(jià)供應(yīng)，從而運(yùn)費(fèi)很高。因此，應(yīng)先對(duì)最大差額所在的行或列，按最小元素確定供銷關(guān)系。,優(yōu)點(diǎn):,按此法所得基可行解較最小元素法所得可行解更接近最優(yōu)解。,23,例4,若同時(shí)有多個(gè)相同的最大差額，選取最小元素確定供應(yīng)關(guān)系,24,1)在運(yùn)輸表上寫出各行各列最小運(yùn)價(jià)和次小 運(yùn)價(jià)差額；,步驟:,2)選最大差額所在行或列的最小元素確定供銷關(guān)系；,3)對(duì)未確定的行列，重新計(jì)算差額，重復(fù)2)、3)， 直至得出初始解。,25,在以上兩種方法中，有幾點(diǎn)需要注意：,這兩種

5、方法得出的解均為初始可行解。,在以上方法中，每填寫一個(gè)數(shù)字劃去一行(列)，只有在填寫最后一個(gè)數(shù)字時(shí)，同時(shí)劃去該數(shù)字所在行和列。從而保證基變量個(gè)數(shù)為（m+n-1）個(gè)。,26,例5,xij 的分配公式,3. 左上角法（西北角法）,從 x11開始分配，從西北向東南方向逐個(gè)分配。,27,例5 左上角法解題演示,28,三、求檢驗(yàn)數(shù)并進(jìn)行最優(yōu)解的判定,1. 閉回路法,就是求調(diào)運(yùn)方案中空格的檢驗(yàn)數(shù)ij，當(dāng)所有ij 0，則得最優(yōu)解。,29,注: 數(shù)字格檢驗(yàn)數(shù)均為0,顯然該問題至此尚未達(dá)到最優(yōu)解。,例6：以最小元素法求得的調(diào)運(yùn)方案為例,1,2,1,-1,10,12,30,(+1),(-1),(+1),(-1),

6、31,(+1),(-1),(+1),(-1),32,(+1),(-1),(+1),(-1),(+1),(-1),33,(+1),(-1),(+1),(-1),34,(+1),(+1),(-1),(+1),(-1),(-1),35,(+1),(-1),(+1),(-1),36,2. 位勢(shì)法,例7 由最小元素法得出初始解,如下表,3）行勢(shì)、列勢(shì)可不唯一，但檢驗(yàn)數(shù)是一致的。,37,例7：以最小元素法求得的調(diào)運(yùn)方案為例,位勢(shì)法的計(jì)算過程,0,3,10,-1,-5,9,2,1,2,1,-1,10,12,令u1=0,根據(jù)數(shù)字格的單價(jià)按ui+vj=cij相繼確定其他的ui和vj,計(jì)算空格的檢驗(yàn)數(shù)。 ij=

7、cij-(ui+vj)，如11=3-(0+2)=1,因?yàn)?24=-10,因而該問題至此尚未達(dá)到最優(yōu)解.,38,四、 調(diào)整,從最小負(fù)檢驗(yàn)數(shù)所對(duì)應(yīng)的空格進(jìn)行調(diào)整,例8 對(duì)由最小元素法得出的初始解進(jìn)行調(diào)整,調(diào)整方法：,1）找出閉回路,2）確定調(diào)整量 使最小負(fù)檢驗(yàn)數(shù)所對(duì)應(yīng)的空格達(dá)到最大的調(diào)整量，即 =min(1,3)=1,再按調(diào)整后的解由位勢(shì)法計(jì)算空格的檢驗(yàn)數(shù),1,2,1,-1,10,12,(+),(-),(+),(-),39,五、典型運(yùn)輸問題解題步驟示例,1.由最小元素法求得初始基可行解,40,0,3,10,-1,-5,9,2,1,2,1,-1,10,12,令u1=0,按ui+vj=cij相繼確定其

8、他數(shù)字格的ui和vj,計(jì)算空格的檢驗(yàn)數(shù)。 ij= cij-(ui+vj)，如11=3-(0+2)=1,因?yàn)?24=-10,因而該問題至此尚未達(dá)到最優(yōu)解.,2.由位勢(shì)法求檢驗(yàn)數(shù),41,3.從最小負(fù)檢驗(yàn)數(shù)所對(duì)應(yīng)的空格進(jìn)行調(diào)整,調(diào)整方法：,1）找出閉回路,2）確定調(diào)整量 使最小負(fù)檢驗(yàn)數(shù)所對(duì)應(yīng)的空格達(dá)到最大的調(diào)整量，即 =min(1,3)=1,1,2,1,-1,10,12,(+),(-),(+),(-),42,0,3,10,-2,-5,9,3,0,2,2,1,9,12,令u1=0,按ui+vj=cij相繼確定其他數(shù)字格的ui和vj,計(jì)算空格的檢驗(yàn)數(shù)。 ij= cij-(ui+vj)，如11=3-(0+

9、3)=0,因?yàn)閕j 0,至此該問題已經(jīng)達(dá)到最優(yōu)解.,4. 再按調(diào)整后的解由位勢(shì)法計(jì)算空格的檢驗(yàn)數(shù),43,六、位勢(shì)法的理論依據(jù)（互補(bǔ)松弛定理）,44,七、表上作業(yè)法的說明,無窮多最優(yōu)解判別：存在非基變量的檢驗(yàn)數(shù)=0的空格,確定初始解時(shí)，若數(shù)字格不夠（m+n-1），需任選一些空格填為0，使其成為數(shù)字格；用閉回路調(diào)整時(shí)，若減去后成為0的格多于1個(gè)，需將多出的格（任選）填0。,若調(diào)入格調(diào)整量=0，也要按步驟求調(diào)整方案，盡管實(shí)際并未 調(diào)整，但解的性質(zhì)有了變化（原空格變成基變量），從而影響 檢驗(yàn)數(shù)結(jié)果。,45,一、 求解原理,第三節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題,46,證明：,47,結(jié)論：,48,二、產(chǎn)銷不平衡問

10、題的處理,49,例9 產(chǎn)銷不平衡問題（書P105 例2）,若IIIIII按最低需求供應(yīng)，IV可獲得最高需求60，若各地都按最高需求供應(yīng)，產(chǎn)量缺50，按最高需求，這是一個(gè)銷大于產(chǎn)問題。為便于分析，將各地需求分為最低需求和超出最低需求部分，實(shí)際按兩個(gè)地區(qū)看待。前者必須滿足，后者因供不應(yīng)求可以不滿足。假想一產(chǎn)地，其產(chǎn)量為50，在表中增加一行D，其運(yùn)價(jià)應(yīng)視最低需求還是超出部分而賦予M或0，即保證各地最低需求不能從假想地購買。,50,這樣可將該問題化為產(chǎn)銷平衡問題：,51,根據(jù)表上作業(yè)法計(jì)算，可得該問題的最優(yōu)方案，如下表：,52,對(duì)最小化運(yùn)輸問題：,1) 用伏格爾法確定初始方案，并檢驗(yàn)是否最優(yōu)；,2) 如果產(chǎn)地A1產(chǎn)量減少100，但要保證B2的需求，給出其相應(yīng)的產(chǎn)銷平衡表。,補(bǔ)充作業(yè)4-1,53,第四節(jié) 應(yīng)用舉例,例10 （書P107 例3）,54,設(shè)ai表示第i季度的生產(chǎn)能力，bj表示第j季度的合同供應(yīng)量，建立數(shù)學(xué)模型表示為：,55,這是一個(gè)產(chǎn)大于銷的運(yùn)輸問題，增加一個(gè)假想的需求D，將問題轉(zhuǎn)化為產(chǎn)銷平衡的運(yùn)輸問題。如下表：,56,用表上作業(yè)法求解可得多個(gè)最優(yōu)解，下表給出了其中一個(gè)最優(yōu)解 （單位： 臺(tái)）,按此方案生產(chǎn)，總費(fèi)用為773萬元。,57,例11 求下面運(yùn)輸問題的最優(yōu)解,