1、運輸問題數(shù)學(xué)模型運輸問題數(shù)學(xué)模型例：某公司經(jīng)銷甲產(chǎn)品，下設(shè)例：某公司經(jīng)銷甲產(chǎn)品，下設(shè)3個加工廠個加工廠4個銷售點，其加工廠產(chǎn)量，銷售地銷量個銷售點，其加工廠產(chǎn)量，銷售地銷量以及各工廠到各銷售點單位運價見表，如何調(diào)運，總運費最小以及各工廠到各銷售點單位運價見表，如何調(diào)運，總運費最小206563銷量951047A348291A27103113A1產(chǎn)量B4B3B2B1 銷地 產(chǎn)地 第1頁/共42頁設(shè)設(shè)Xij為為Ai到到Bj的銷量的銷量Minz=3X11+ 11X12+ 3X13 + 10X14+ + 7X31 +4X32 +10X33 + 5X34 X11+X12+X13+X14 =7 a1 X21

2、+X22+X23+X24 =4 a2 X31+X32+X33+X34 =9 a3該模型又可表示為該模型又可表示為3141minijijijxczijijax41i =1，2，3 jiijbx31j =1，2，3，4Xij0，i =1，2，3 j =1，2，3，4 X11+X21+X31 =3 b1X12+X22+X32=6 b2 X13+X23+X33 =5 b3 X14+X24+X34 =9 b4 Xij0，i =1，2，3； j =1，2，3，4第2頁/共42頁上述問題可以擴展為上述問題可以擴展為m個產(chǎn)地個產(chǎn)地n個銷地的運輸問題，個銷地的運輸問題，設(shè)設(shè)ai為為Ai產(chǎn)量，產(chǎn)量，bj為為Bj銷

3、地銷量，銷地銷量，Ai到到Bj 單位運價單位運價Cij ，則產(chǎn)銷平衡的運輸問題其數(shù)學(xué)模型為則產(chǎn)銷平衡的運輸問題其數(shù)學(xué)模型為minjijijxcz11mininjijax1i =1，2，,m jmiijbx1j =1，2，nXij0，i =1，2，,m j =1，2，n第3頁/共42頁模型特點：模型特點：模型有模型有mn個變量，個變量，m+n個方程個方程對產(chǎn)銷平衡問題對產(chǎn)銷平衡問題ai= bj運輸問題（產(chǎn)銷平衡）總存在可行解和最優(yōu)解運輸問題（產(chǎn)銷平衡）總存在可行解和最優(yōu)解 1、 cij0 Xij 0 cij Xij 0 運輸問題一定有界運輸問題一定有界2、一定有可行解、一定有可行解Xij =ai

4、bjaiimiinjjimiinjjinjijaabaabax11111jmiijbx 1 3、有界且有可行解，所以一定有最優(yōu)解、有界且有可行解，所以一定有最優(yōu)解 約束方程系數(shù)矩陣具有稀疏結(jié)構(gòu)（見下頁），秩約束方程系數(shù)矩陣具有稀疏結(jié)構(gòu)（見下頁），秩r（A）=m+n-1 第4頁/共42頁 P11 P12 P1n P2 1 P22 P2n Pm1 Pm2 Pmn 1 1 1 a1 1 1 1 a2 : 1 1 1 am 1 1 1 b1 1 1 1 b2 : 1 1 1 bmm行行n行行 0 0 0 : : : 1 1 0Pij= : = : + : 1 0 1 : : : 0 0 0 第第i i

5、個個分量分量第第m+jm+j個個分量分量系數(shù)矩陣系數(shù)矩陣p pij除了第除了第i i和第和第m+jm+j個分量為個分量為1 1外，其余分外，其余分量全為量全為0 0A A的前的前m m行之和減去后行之和減去后n n行行之和得到的是零向量，即之和得到的是零向量，即A A的行向量線性相關(guān)，其不等的行向量線性相關(guān)，其不等于零的子式的最大階數(shù)為于零的子式的最大階數(shù)為m+n-1m+n-1第5頁/共42頁 表上作業(yè)法表上作業(yè)法 步驟：步驟： 1.確定初始基本可行解：確定初始基本可行解： 有三種方法：有三種方法： 最小元素法最小元素法 西北角法西北角法 伏格爾法伏格爾法 2.求非基變量檢驗數(shù)，進行最優(yōu)解判別

6、，求非基變量檢驗數(shù)，進行最優(yōu)解判別，若最優(yōu)，停止，否則進行下一步若最優(yōu)，停止，否則進行下一步 3.確定進基、離基變量，找新的基本可行確定進基、離基變量，找新的基本可行解，返回解，返回2，重復(fù)，重復(fù)2、3，直到得到最優(yōu)解。，直到得到最優(yōu)解。第6頁/共42頁最小元素法最小元素法 基本思想：基本思想： 步驟：步驟：Ckt=min Cij 2. 根據(jù)根據(jù)Ckt對應(yīng)的產(chǎn)地產(chǎn)量對應(yīng)的產(chǎn)地產(chǎn)量ak 、銷地銷量、銷地銷量bt確定調(diào)運量確定調(diào)運量 調(diào)運量調(diào)運量Xkt=min ak，bt ， 將將Xkt 填在產(chǎn)銷平衡表第（填在產(chǎn)銷平衡表第（k，t）格）格 若若ak bt ， Xkt=bt ，劃去第劃去第t列，置列

7、，置ak= ak- bt 若若akbt ， Xkt= ak ，劃去第劃去第k行，置行，置bt= bt - ak 若若ak= bt 劃去第劃去第k行或第行或第t列，置列，置bt =0 或或 ak =0 3.從未被劃去元素中再找最小元素，重復(fù)從未被劃去元素中再找最小元素，重復(fù)1、2，當(dāng)填入最后，當(dāng)填入最后一個元素時，同時劃去一行一列。一個元素時，同時劃去一行一列。第7頁/共42頁6563銷量銷量951047A348291A27103113A1產(chǎn)量產(chǎn)量B4B3B2B1 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4銷量銷量A17A24A39產(chǎn)量產(chǎn)量365631463 3 注意：注意： 最小運價有多個最小運價有多個

8、時，可任選一個時，可任選一個 保證數(shù)字格數(shù)量保證數(shù)字格數(shù)量為（為（m+n-1）個）個產(chǎn)銷平衡表中填入數(shù)字產(chǎn)銷平衡表中填入數(shù)字的格為數(shù)字格，其余格的格為數(shù)字格，其余格為空格。為空格。第8頁/共42頁伏格爾法伏格爾法 思路：思路： 步驟：步驟：C Cij ij的差，分別填在最右一列和最下面一行的差，分別填在最右一列和最下面一行 2. 2.選差最大的行（或列），根據(jù)該行（列）最小元素選差最大的行（或列），根據(jù)該行（列）最小元素C Cij ij確定調(diào)運量確定調(diào)運量第9頁/共42頁 B1 B2 B3 B4A1A2A3銷量銷量產(chǎn)量產(chǎn)量 3 11 3 10 1 9 2 8 7 4 10 5 3 6 5 67

9、4 9 列列 差差 額額011 2 5 1 3 6 0 1 2 3 2 1 3 0 1 2 1 2 3 1 2 5 2 1 2 行行 差差 額額 7 6第10頁/共42頁 最優(yōu)解判別：最優(yōu)解判別： 兩種方法兩種方法: 閉回路法閉回路法 位勢法位勢法 1.閉回路法：閉回路法： 閉回路：互不相同的閉回路：互不相同的2k個變量個變量X11 X21 X22 X kk X1 k （其下標(biāo)交錯相等其下標(biāo)交錯相等,在表中表現(xiàn)為相臨的兩個變量，同行或同列在表中表現(xiàn)為相臨的兩個變量，同行或同列）組成一個）組成一個閉回路。閉回路。X11X12X22X21第11頁/共42頁 閉回路求法：閉回路求法： 在給出調(diào)運方案

10、的產(chǎn)銷平衡表上，從某一空格（在給出調(diào)運方案的產(chǎn)銷平衡表上，從某一空格（k k，t t）格出發(fā)，）格出發(fā)，沿水平或豎直方向前進，遇到一個合適的數(shù)字格轉(zhuǎn)彎沿水平或豎直方向前進，遇到一個合適的數(shù)字格轉(zhuǎn)彎9090繼續(xù)前繼續(xù)前進，再遇到一個合適的數(shù)字格再轉(zhuǎn)彎進，再遇到一個合適的數(shù)字格再轉(zhuǎn)彎9090，繼續(xù)前進，繼續(xù)前進，最，最后又回到原來的出發(fā)點（后又回到原來的出發(fā)點（k k，t t）格，稱這樣走過的一條路線為從）格，稱這樣走過的一條路線為從（k k，t t）格出發(fā)的閉回路。）格出發(fā)的閉回路。注：以空格為起點，以某些數(shù)字格為轉(zhuǎn)折點，最終返回起點，所構(gòu)成的一個路線稱為閉回路。閉回路是惟一的！每一個空格點都能

11、構(gòu)成一條閉回路！65639A34A27A1B4B3B2B1 3 11 3 10 1 9 2 8 7 4 10 5314633第12頁/共42頁 檢驗數(shù)求法：檢驗數(shù)求法： 對從（對從（k k，t t）格出發(fā)的閉回路各頂點依次編號）格出發(fā)的閉回路各頂點依次編號, ,（k k，t t）格為第一）格為第一頂點，對所經(jīng)過的其它各頂點順序編號，依次為第二、第三頂點，頂點，對所經(jīng)過的其它各頂點順序編號，依次為第二、第三頂點，則閉回路上所有奇數(shù)點單位運價之和減偶數(shù)點單位運價之和所得的則閉回路上所有奇數(shù)點單位運價之和減偶數(shù)點單位運價之和所得的差，即為（差，即為（k k，t t）格的檢驗數(shù)）格的檢驗數(shù) kt kt

12、65639A34A27A1B4B3B2B1 3 11 3 10 1 9 2 8 7 4 10 5314633+1-1+1-1 11=（C11+ C23） - （ C13 + C21 ）=（3+2）-（3+1）=1第13頁/共42頁 位勢法位勢法設(shè)設(shè)Xij為為Ai到到Bj的的 運量，根據(jù)運量，根據(jù)例例1運輸問題數(shù)學(xué)模型運輸問題數(shù)學(xué)模型3141minijijijxcz X11+X12+X13+X14 =7 U1 X21+X22+X23+X24 =4 U2 X31+X32+X33+X34 =9 U3 X11+X21+X31 =3 V1X12+X22+X32=6 V2 X13+X23+X33 =5 V

13、3 X14+X24+X34 =9 V4 Xij0，i =1，2，3； j =1，2，3，4設(shè)設(shè)U1 ， U2，U3 ， V1 ， V2 ，V3， V4 為對應(yīng)為對應(yīng)3+4個約束方程的對偶變量，則個約束方程的對偶變量，則其對偶問題為其對偶問題為Max = Ui ai + Vj bj Ui+VjCijUi，Vj無約束無約束i =1,2,3j =1,2,3,4第14頁/共42頁同理：對一般運輸問題數(shù)學(xué)模型同理：對一般運輸問題數(shù)學(xué)模型設(shè)設(shè)U1 ， U2， Um ， V1 ， V2 ， Vn 為對應(yīng)運輸問題為對應(yīng)運輸問題m+n個約束個約束方程的對偶變量方程的對偶變量對偶問題數(shù)學(xué)模型：對偶問題數(shù)學(xué)模型：M

14、ax = Ui ai + Vj bj Ui+VjCijUi，Vj無約束無約束Ui，Vj又分別稱為對應(yīng)于發(fā)又分別稱為對應(yīng)于發(fā)點（點（產(chǎn)地產(chǎn)地）i和收點（和收點（銷地銷地）j的位勢的位勢minjijijxcz11mininjijax1i =1,2,m Ui jmiijbx1j =1,2,n V Vj jXij0，i =1，2，,m j =1，2，n第15頁/共42頁 設(shè)基設(shè)基B B為運輸問題的一個可行基，則對偶變量為運輸問題的一個可行基，則對偶變量 Y=CY=CB BB B-1 -1 =(U=(U1 1,U,U2 2 ,Um,V,Um,V1 1,V,V2 2 , Vn) , Vn) 決策變量決策變

15、量X Xij ij的系數(shù)列向量的系數(shù)列向量Pij ij=ei+em+j =0 ： 1 ：1 ： 0檢驗數(shù)檢驗數(shù) ij ij=C=Cij ij- -C CB BB B-1 -1 P Pij ij =C=Cij ij-(U-(U1 1,U,U2 2 ,Um,V,Um,V1 1,V,V2 2, Vn ), Vn )=Cij-Ui-Vj 由單純形法原理可知基變量檢驗數(shù)為零即由單純形法原理可知基變量檢驗數(shù)為零即 C Cij ij-U-Ui i-V-Vj j=0=0 C Cij ij=U=Ui i+V+Vj j X Xij ijXXB B 即：我們可以把某一調(diào)運方案中所有基變量的運價即：我們可以把某一調(diào)運

16、方案中所有基變量的運價C Cij ij分解為對應(yīng)分解為對應(yīng)的行位勢和列位勢兩部分的行位勢和列位勢兩部分0110第16頁/共42頁續(xù)上頁：續(xù)上頁：由于基變量由于基變量C Cij ij=U=Ui i+V+Vj j 非基變量檢驗數(shù)非基變量檢驗數(shù) ij ij=C=Cij ij-U-Ui i-V-Vj j 只要求出只要求出U Ui i、V Vj j ，則可求出，則可求出 ij ij例：例例：例1 1初始調(diào)運表見下表初始調(diào)運表見下表該例：該例：m=3m=3，n=4n=4，基變量，基變量有有6 6個，對應(yīng)的個，對應(yīng)的C Cij ij方程也有方程也有6 6個，而位勢量個，而位勢量( (對偶變量對偶變量) )有

17、有7 7個，個，6 6個方程解出個方程解出7 7個位勢個位勢有很多解，把有很多解，把U U1 1作為自由作為自由變量，變量，令令U U1 1=0=0C13= U1 +V3=3 V3 =3 C14= U1 +V4=10 V4 =10C23= U2 +V3=2 U2 =-1C21= U2 +V1=1 V1=2C34= U3+V4=5 U3 =-5C32= U3 +V2=4 V2 =9將位勢量填入調(diào)運方案表將位勢量填入調(diào)運方案表中，計算非基變量的檢驗中，計算非基變量的檢驗數(shù)數(shù) ij ij=C=Cij ij-U-Ui i-V-Vj jVjA3A2A1UiB4B3B2B13 11 3 101 9 2 8

18、7 4 10 5U1V3V4U2V1U3V2第17頁/共42頁 上述計算過程可在表中進行，其中上述計算過程可在表中進行，其中 基變量基變量Cij=Ui+Vj 非基變量檢驗數(shù)非基變量檢驗數(shù) ij=Cij-Ui-Vj 方法：方法： 1.在產(chǎn)銷平衡表分別增加一行、一列在產(chǎn)銷平衡表分別增加一行、一列 2.計算行位勢和列位勢計算行位勢和列位勢,分別填入最右一列、最后一行對應(yīng)位分別填入最右一列、最后一行對應(yīng)位置置VjA3A2A1UiB4B3B2B13 11 3 104331631 9 2 87 4 10 50310-12-59注：注：上表中右上角數(shù)字為單位上表中右上角數(shù)字為單位運價運價，左下角紅色數(shù)字為左

19、下角紅色數(shù)字為非基變量檢驗數(shù)非基變量檢驗數(shù)，中間蘭中間蘭色數(shù)字為調(diào)運量色數(shù)字為調(diào)運量上表中有負檢驗數(shù)，說明上表中有負檢驗數(shù)，說明不是最優(yōu)解不是最優(yōu)解121-11012 第18頁/共42頁位勢法步驟：位勢法步驟：已知基可行解已知基可行解 Xij 1、對基變量、對基變量Xij ，解方程，解方程Cij = Ui+Vj ，得到，得到 Ui，Vj 2、對非基變量、對非基變量Xij 計算計算 ij=Cij-Ui-Vj，若，若 ij全全0，停。，停。 否則，轉(zhuǎn)否則，轉(zhuǎn)3 3、方案調(diào)整。、方案調(diào)整。第19頁/共42頁調(diào)運方案的改進調(diào)運方案的改進閉回路調(diào)整法閉回路調(diào)整法1、確定進基格（進基變量）、確定進基格（進

20、基變量） Min=ij ij 0 = kt Xkt為進基格為進基格2、作出從進基格（、作出從進基格（k，t）格出發(fā)的閉回路，對各頂點順序編號）格出發(fā)的閉回路，對各頂點順序編號3、確定調(diào)整量和離基格、確定調(diào)整量和離基格 調(diào)整量調(diào)整量 Q=min偶數(shù)點調(diào)運偶數(shù)點調(diào)運量量4、閉回路調(diào)整：、閉回路調(diào)整： 閉回路上：閉回路上： 奇數(shù)頂點調(diào)運量奇數(shù)頂點調(diào)運量+Q 偶數(shù)頂點調(diào)運量偶數(shù)頂點調(diào)運量-Q 其余格運量不變其余格運量不變VjA3A2A1UiB4B3B2B13 11 3 104331631 9 2 87 4 10 50310-12-59121-11012第20頁/共42頁VjA3A2A1UiB4B3B2

21、B13 11 3 101 9 2 87 4 10 55231 630310-59-230221912表中解為最優(yōu)解表中解為最優(yōu)解非基變量非基變量X X1111檢驗數(shù)檢驗數(shù) 1111 =0 =0，所以該運輸，所以該運輸問題有無窮多解問題有無窮多解 1111 =0=0，作出（，作出（1 1，1 1）格）格的閉回路，進行最優(yōu)的閉回路，進行最優(yōu)解調(diào)整，則得另一最解調(diào)整，則得另一最優(yōu)方案。優(yōu)方案。VjA3A2A1UiB4B3B2B13 11 3 101 9 2 87 4 10 55632130 33-210-592021912第21頁/共42頁運輸問題的解的情況：運輸問題的解的情況：1、無窮多最優(yōu)解：、

22、無窮多最優(yōu)解：A3A2A1B4B3B2B1 3 11 3 101 9 2 87 4 10 5UiVj5632130 33-210-592021912第22頁/共42頁2、退化解：有基變量取值為零的情況。、退化解：有基變量取值為零的情況。B1B2B3B4aiA17A24A39bi36563 11 4 57 7 3 81 2 10 636 41 60第23頁/共42頁B1B2B3B4aiA17A24A39bi3656 3 11 4 5 7 7 3 8 1 2 10 6360416第24頁/共42頁1）在用表上作業(yè)法求初始調(diào)運方案時，第（）在用表上作業(yè)法求初始調(diào)運方案時，第（k，t）格的調(diào)運量）格的

23、調(diào)運量Xkt=min ak bt 當(dāng)當(dāng)ak = bt 時，有兩種處理方法：時，有兩種處理方法：劃去第劃去第k行或第行或第t列，繼續(xù)找其它數(shù)字格列，繼續(xù)找其它數(shù)字格同時劃去第同時劃去第k行和第行和第t列，在劃去的行或列的某個空格處填上一列，在劃去的行或列的某個空格處填上一個零作為數(shù)字格個零作為數(shù)字格2）在用閉回路法對調(diào)運方案改進時：在閉回路頂點出現(xiàn)兩個以）在用閉回路法對調(diào)運方案改進時：在閉回路頂點出現(xiàn)兩個以上最小運量，調(diào)整后，這些偶數(shù)頂點減去調(diào)整量后，運量為零，上最小運量，調(diào)整后，這些偶數(shù)頂點減去調(diào)整量后，運量為零，這時，只能把其中的一個數(shù)字格作為出基格，其余仍為運量為零這時，只能把其中的一個數(shù)

24、字格作為出基格，其余仍為運量為零的數(shù)字格的數(shù)字格 當(dāng)出現(xiàn)退化解后再作調(diào)整時，有可能在閉回路的偶數(shù)頂點上當(dāng)出現(xiàn)退化解后再作調(diào)整時，有可能在閉回路的偶數(shù)頂點上出現(xiàn)運量為零的數(shù)字格，這時調(diào)整量為零。出現(xiàn)運量為零的數(shù)字格，這時調(diào)整量為零。第25頁/共42頁 產(chǎn)銷不平衡運輸問題及其求解方法產(chǎn)銷不平衡運輸問題及其求解方法1、產(chǎn)銷、產(chǎn)銷 ： ai bj Xij ai i=1，2m Xij=bj j=1，2n松弛變量松弛變量Xi，n+1 （I=1，2 m）表示）表示Ai的庫存量，增的庫存量，增加銷地加銷地Bn+1,銷量銷量ai- bj，對應(yīng)運價，對應(yīng)運價Ci，n+1=0innjijaXX11i=1，2mj=1

25、，2n ，n+1jmiijbX 1minjijijXCMinz1minjijijminjijijXCXCMinz1111第26頁/共42頁6432銷量銷量7A35A27A1產(chǎn)量產(chǎn)量B4B3B2B12 11 3 410 3 5 97 8 1 2B500044233322uivj0240-230380825772第27頁/共42頁2.銷產(chǎn)銷產(chǎn) ：bj ai增加虛產(chǎn)地增加虛產(chǎn)地Am+ ，產(chǎn)量產(chǎn)量am+1= bj- ai ，對應(yīng)運價對應(yīng)運價Cm+1，j=0Minz= CijXiji=1 j=1m+1n Xij=ai 1,2+1j=1nij=bj j=1,2 ni=1m+1第28頁/共42頁例例2:設(shè)有

26、設(shè)有3個化肥廠供應(yīng)個化肥廠供應(yīng)4個地區(qū)的農(nóng)用化肥個地區(qū)的農(nóng)用化肥,假定等量化肥在這些地區(qū)使用效果相同假定等量化肥在這些地區(qū)使用效果相同,各各化肥廠年產(chǎn)量化肥廠年產(chǎn)量,各地區(qū)年需求量、各化肥廠到各地區(qū)運送單位化肥的運價如下表各地區(qū)年需求量、各化肥廠到各地區(qū)運送單位化肥的運價如下表,試求出試求出總運費最小的化肥調(diào)撥方案總運費最小的化肥調(diào)撥方案 產(chǎn)量產(chǎn)量ABC16 13 22 17 5014 13 19 15 6019 20 23 15 50最低需求最低需求 30 70 0 10 最高需求最高需求 50 70 30 不不限限 第29頁/共42頁 產(chǎn)產(chǎn)量量ABC16 13 22 17 5014 13

27、19 15 60 19 20 23 - 501614191715 - DM0M0 M050307030102050第30頁/共42頁 ABCD 50 50 20 10 30 60 30 20 0 50 30 20 50 30 20 70 30 10 50 用表上作業(yè)法求得最優(yōu)方案為：用表上作業(yè)法求得最優(yōu)方案為：第31頁/共42頁例例3：某調(diào)運問題，其產(chǎn)地產(chǎn)量、銷地銷量及單位產(chǎn)品獲利情況某調(diào)運問題，其產(chǎn)地產(chǎn)量、銷地銷量及單位產(chǎn)品獲利情況見下表，已知丙銷地至少保證供應(yīng)見下表，已知丙銷地至少保證供應(yīng)C產(chǎn)品產(chǎn)品1000，而因某種，而因某種原因，該地不經(jīng)銷原因，該地不經(jīng)銷A產(chǎn)品，求使得總銷售收入最大的調(diào)

28、運產(chǎn)品，求使得總銷售收入最大的調(diào)運方案及相應(yīng)利潤。方案及相應(yīng)利潤。甲甲乙乙丙丙產(chǎn)量產(chǎn)量A5 481000B16892000C1210112000銷量銷量 1500 1500 1500第32頁/共42頁50015001500銷量銷量1000C2000B1000A產(chǎn)量產(chǎn)量丙丙乙乙甲甲 5 4 0 16 8 912 10 11丁丁0005001500500500500500500uiVj00465 412-7-5 0-4-6-6第33頁/共42頁VjA3A2A1uiB4B3B2B110 1 20 1112 C22 9 202 14 16 185105015100111C22-110- C2213- C22C22-11題-3+ C2210+ C2210- C2224- C221718- C22-3+ C22010+ C22010- C22024- C22018- C22010 C223第34頁/共42頁VjA3A2A1uiB4B3B2B110 1 20 1112 7 9 C242 14 16 18 5105015100111636-4417C24-171711當(dāng)當(dāng)C24-17=0有無窮多最優(yōu)解有無窮多最優(yōu)解17第35頁/共42頁VjA3A2A1uiB4B3B2B110 1 20 1112