运输问题新PPT课件

1、运输问题数学模型运输问题数学模型例：某公司经销甲产品，下设例：某公司经销甲产品，下设3个加工厂个加工厂4个销售点，其加工厂产量，销售地销量个销售点，其加工厂产量，销售地销量以及各工厂到各销售点单位运价见表，如何调运，总运费最小以及各工厂到各销售点单位运价见表，如何调运，总运费最小206563销量951047A348291A27103113A1产量B4B3B2B1 销地 产地 第1页/共42页设设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个产地个产地n个销地的运输问题，个销地的运输问题，设设ai为为Ai产量，产量，bj为为Bj销

3、地销量，销地销量，Ai到到Bj 单位运价单位运价Cij ，则产销平衡的运输问题其数学模型为则产销平衡的运输问题其数学模型为minjijijxcz11mininjijax1i =1，2，,m jmiijbx1j =1，2，nXij0，i =1，2，,m j =1，2，n第3页/共42页模型特点：模型特点：模型有模型有mn个变量，个变量，m+n个方程个方程对产销平衡问题对产销平衡问题ai= bj运输问题（产销平衡）总存在可行解和最优解运输问题（产销平衡）总存在可行解和最优解 1、 cij0 Xij 0 cij Xij 0 运输问题一定有界运输问题一定有界2、一定有可行解、一定有可行解Xij =ai

4、bjaiimiinjjimiinjjinjijaabaabax11111jmiijbx 1 3、有界且有可行解，所以一定有最优解、有界且有可行解，所以一定有最优解 约束方程系数矩阵具有稀疏结构（见下页），秩约束方程系数矩阵具有稀疏结构（见下页），秩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个个分量分量系数矩阵系数矩阵p pij除了第除了第i i和第和第m+jm+j个分量为个分量为1 1外，其余分外，其余分量全为量全为0 0A A的前的前m m行之和减去后行之和减去后n n行行之和得到的是零向量，即之和得到的是零向量，即A A的行向量线性相关，其不等的行向量线性相关，其不等于零的子式的最大阶数为于零的子式的最大阶数为m+n-1m+n-1第5页/共42页 表上作业法表上作业法 步骤：步骤： 1.确定初始基本可行解：确定初始基本可行解： 有三种方法：有三种方法： 最小元素法最小元素法 西北角法西北角法 伏格尔法伏格尔法 2.求非基变量检验数，进行最优解判别

6、，求非基变量检验数，进行最优解判别，若最优，停止，否则进行下一步若最优，停止，否则进行下一步 3.确定进基、离基变量，找新的基本可行确定进基、离基变量，找新的基本可行解，返回解，返回2，重复，重复2、3，直到得到最优解。，直到得到最优解。第6页/共42页最小元素法最小元素法 基本思想：基本思想： 步骤：步骤：Ckt=min Cij 2. 根据根据Ckt对应的产地产量对应的产地产量ak 、销地销量、销地销量bt确定调运量确定调运量 调运量调运量Xkt=min ak，bt ， 将将Xkt 填在产销平衡表第（填在产销平衡表第（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.从未被划去元素中再找最小元素，重复从未被划去元素中再找最小元素，重复1、2，当填入最后，当填入最后一个元素时，同时划去一行一列。一个元素时，同时划去一行一列。第7页/共42页6563销量销量951047A348291A27103113A1产量产量B4B3B2B1 销地销地产地产地B1B2B3B4销量销量A17A24A39产量产量365631463 3 注意：注意： 最小运价有多个最小运价有多个

8、时，可任选一个时，可任选一个 保证数字格数量保证数字格数量为（为（m+n-1）个）个产销平衡表中填入数字产销平衡表中填入数字的格为数字格，其余格的格为数字格，其余格为空格。为空格。第8页/共42页伏格尔法伏格尔法 思路：思路： 步骤：步骤：C Cij ij的差，分别填在最右一列和最下面一行的差，分别填在最右一列和最下面一行 2. 2.选差最大的行（或列），根据该行（列）最小元素选差最大的行（或列），根据该行（列）最小元素C Cij ij确定调运量确定调运量第9页/共42页 B1 B2 B3 B4A1A2A3销量销量产量产量 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页 最优解判别：最优解判别： 两种方法两种方法: 闭回路法闭回路法 位势法位势法 1.闭回路法：闭回路法： 闭回路：互不相同的闭回路：互不相同的2k个变量个变量X11 X21 X22 X kk X1 k （其下标交错相等其下标交错相等,在表中表现为相临的两个变量，同行或同列在表中表现为相临的两个变量，同行或同列）组成一个）组成一个闭回路。闭回路。X11X12X22X21第11页/共42页 闭回路求法：闭回路求法： 在给出调运方案

10、的产销平衡表上，从某一空格（在给出调运方案的产销平衡表上，从某一空格（k k，t t）格出发，）格出发，沿水平或竖直方向前进，遇到一个合适的数字格转弯沿水平或竖直方向前进，遇到一个合适的数字格转弯9090继续前继续前进，再遇到一个合适的数字格再转弯进，再遇到一个合适的数字格再转弯9090，继续前进，继续前进，最，最后又回到原来的出发点（后又回到原来的出发点（k k，t t）格，称这样走过的一条路线为从）格，称这样走过的一条路线为从（k k，t t）格出发的闭回路。）格出发的闭回路。注：以空格为起点，以某些数字格为转折点，最终返回起点，所构成的一个路线称为闭回路。闭回路是惟一的！每一个空格点都能

11、构成一条闭回路！65639A34A27A1B4B3B2B1 3 11 3 10 1 9 2 8 7 4 10 5314633第12页/共42页 检验数求法：检验数求法： 对从（对从（k k，t t）格出发的闭回路各顶点依次编号）格出发的闭回路各顶点依次编号, ,（k k，t t）格为第一）格为第一顶点，对所经过的其它各顶点顺序编号，依次为第二、第三顶点，顶点，对所经过的其它各顶点顺序编号，依次为第二、第三顶点，则闭回路上所有奇数点单位运价之和减偶数点单位运价之和所得的则闭回路上所有奇数点单位运价之和减偶数点单位运价之和所得的差，即为（差，即为（k k，t t）格的检验数）格的检验数 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页 位势法位势法设设Xij为为Ai到到Bj的的 运量，根据运量，根据例例1运输问题数学模型运输问题数学模型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设设U1 ， U2，U3 ， V1 ， V2 ，V3， V4 为对应为对应3+4个约束方程的对偶变量，则个约束方程的对偶变量，则其对偶问题为其对偶问题为Max = Ui ai + Vj bj Ui+VjCijUi，Vj无约束无约束i =1,2,3j =1,2,3,4第14页/共42页同理：对一般运输问题数学模型同理：对一般运输问题数学模型设设U1 ， U2， Um ， V1 ， V2 ， Vn 为对应运输问题为对应运输问题m+n个约束个约束方程的对偶变量方程的对偶变量对偶问题数学模型：对偶问题数学模型：M

14、ax = Ui ai + Vj bj Ui+VjCijUi，Vj无约束无约束Ui，Vj又分别称为对应于发又分别称为对应于发点（点（产地产地）i和收点（和收点（销地销地）j的位势的位势minjijijxcz11mininjijax1i =1,2,m Ui jmiijbx1j =1,2,n V Vj jXij0，i =1，2，,m j =1，2，n第15页/共42页 设基设基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的系数列向量的系数列向量Pij ij=ei+em+j =0 ： 1 ：1 ： 0检验数检验数 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 由单纯形法原理可知基变量检验数为零即由单纯形法原理可知基变量检验数为零即 C Cij ij-U-Ui i-V-Vj j=0=0 C Cij ij=U=Ui i+V+Vj j X Xij ijXXB B 即：我们可以把某一调运方案中所有基变量的运价即：我们可以把某一调运

16、方案中所有基变量的运价C Cij ij分解为对应分解为对应的行位势和列位势两部分的行位势和列位势两部分0110第16页/共42页续上页：续上页：由于基变量由于基变量C Cij ij=U=Ui i+V+Vj j 非基变量检验数非基变量检验数 ij ij=C=Cij ij-U-Ui i-V-Vj j 只要求出只要求出U Ui i、V Vj j ，则可求出，则可求出 ij ij例：例例：例1 1初始调运表见下表初始调运表见下表该例：该例：m=3m=3，n=4n=4，基变量，基变量有有6 6个，对应的个，对应的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将位势量填入调运方案表将位势量填入调运方案表中，计算非基变量的检验中，计算非基变量的检验数数 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 非基变量检验数非基变量检验数 ij=Cij-Ui-Vj 方法：方法： 1.在产销平衡表分别增加一行、一列在产销平衡表分别增加一行、一列 2.计算行位势和列位势计算行位势和列位势,分别填入最右一列、最后一行对应位分别填入最右一列、最后一行对应位置置VjA3A2A1UiB4B3B2B13 11 3 104331631 9 2 87 4 10 50310-12-59注：注：上表中右上角数字为单位上表中右上角数字为单位运价运价，左下角红色数字为左

19、下角红色数字为非基变量检验数非基变量检验数，中间兰中间兰色数字为调运量色数字为调运量上表中有负检验数，说明上表中有负检验数，说明不是最优解不是最优解121-11012 第18页/共42页位势法步骤：位势法步骤：已知基可行解已知基可行解 Xij 1、对基变量、对基变量Xij ，解方程，解方程Cij = Ui+Vj ，得到，得到 Ui，Vj 2、对非基变量、对非基变量Xij 计算计算 ij=Cij-Ui-Vj，若，若 ij全全0，停。，停。 否则，转否则，转3 3、方案调整。、方案调整。第19页/共42页调运方案的改进调运方案的改进闭回路调整法闭回路调整法1、确定进基格（进基变量）、确定进基格（进

20、基变量） Min=ij ij 0 = kt Xkt为进基格为进基格2、作出从进基格（、作出从进基格（k，t）格出发的闭回路，对各顶点顺序编号）格出发的闭回路，对各顶点顺序编号3、确定调整量和离基格、确定调整量和离基格 调整量调整量 Q=min偶数点调运偶数点调运量量4、闭回路调整：、闭回路调整： 闭回路上：闭回路上： 奇数顶点调运量奇数顶点调运量+Q 偶数顶点调运量偶数顶点调运量-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表中解为最优解表中解为最优解非基变量非基变量X X1111检验数检验数 1111 =0 =0，所以该运输，所以该运输问题有无穷多解问题有无穷多解 1111 =0=0，作出（，作出（1 1，1 1）格）格的闭回路，进行最优的闭回路，进行最优解调整，则得另一最解调整，则得另一最优方案。优方案。VjA3A2A1UiB4B3B2B13 11 3 101 9 2 87 4 10 55632130 33-210-592021912第21页/共42页运输问题的解的情况：运输问题的解的情况：1、无穷多最优解：、

22、无穷多最优解：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）在用表上作业法求初始调运方案时，第（）在用表上作业法求初始调运方案时，第（k，t）格的调运量）格的

23、调运量Xkt=min ak bt 当当ak = bt 时，有两种处理方法：时，有两种处理方法：划去第划去第k行或第行或第t列，继续找其它数字格列，继续找其它数字格同时划去第同时划去第k行和第行和第t列，在划去的行或列的某个空格处填上一列，在划去的行或列的某个空格处填上一个零作为数字格个零作为数字格2）在用闭回路法对调运方案改进时：在闭回路顶点出现两个以）在用闭回路法对调运方案改进时：在闭回路顶点出现两个以上最小运量，调整后，这些偶数顶点减去调整量后，运量为零，上最小运量，调整后，这些偶数顶点减去调整量后，运量为零，这时，只能把其中的一个数字格作为出基格，其余仍为运量为零这时，只能把其中的一个数

24、字格作为出基格，其余仍为运量为零的数字格的数字格 当出现退化解后再作调整时，有可能在闭回路的偶数顶点上当出现退化解后再作调整时，有可能在闭回路的偶数顶点上出现运量为零的数字格，这时调整量为零。出现运量为零的数字格，这时调整量为零。第25页/共42页 产销不平衡运输问题及其求解方法产销不平衡运输问题及其求解方法1、产销、产销 ： ai bj Xij ai i=1，2m Xij=bj j=1，2n松弛变量松弛变量Xi，n+1 （I=1，2 m）表示）表示Ai的库存量，增的库存量，增加销地加销地Bn+1,销量销量ai- bj，对应运价，对应运价Ci，n+1=0innjijaXX11i=1，2mj=1

25、，2n ，n+1jmiijbX 1minjijijXCMinz1minjijijminjijijXCXCMinz1111第26页/共42页6432销量销量7A35A27A1产量产量B4B3B2B12 11 3 410 3 5 97 8 1 2B500044233322uivj0240-230380825772第27页/共42页2.销产销产 ：bj ai增加虚产地增加虚产地Am+ ，产量产量am+1= bj- ai ，对应运价对应运价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:设有

26、设有3个化肥厂供应个化肥厂供应4个地区的农用化肥个地区的农用化肥,假定等量化肥在这些地区使用效果相同假定等量化肥在这些地区使用效果相同,各各化肥厂年产量化肥厂年产量,各地区年需求量、各化肥厂到各地区运送单位化肥的运价如下表各地区年需求量、各化肥厂到各地区运送单位化肥的运价如下表,试求出试求出总运费最小的化肥调拨方案总运费最小的化肥调拨方案 产量产量ABC16 13 22 17 5014 13 19 15 6019 20 23 15 50最低需求最低需求 30 70 0 10 最高需求最高需求 50 70 30 不不限限 第29页/共42页 产产量量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 用表上作业法求得最优方案为：用表上作业法求得最优方案为：第31页/共42页例例3：某调运问题，其产地产量、销地销量及单位产品获利情况某调运问题，其产地产量、销地销量及单位产品获利情况见下表，已知丙销地至少保证供应见下表，已知丙销地至少保证供应C产品产品1000，而因某种，而因某种原因，该地不经销原因，该地不经销A产品，求使得总销售收入最大的调

28、运产品，求使得总销售收入最大的调运方案及相应利润。方案及相应利润。甲甲乙乙丙丙产量产量A5 481000B16892000C1210112000销量销量 1500 1500 1500第32页/共42页50015001500销量销量1000C2000B1000A产量产量丙丙乙乙甲甲 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当当C24-17=0有无穷多最优解有无穷多最优解17第35页/共42页VjA3A2A1uiB4B3B2B110 1 20 1112