运输问题(新)ppt课件

第三章运输问题,1,运输问题数学模型例：某公司经销甲产品，下设3个加工厂4个销售点，其加工厂产量，销售地销量以及各工厂到各销售点单位运价见表，如何调运，总运费最小,2,设Xij为Ai到Bj的销量Minz=3X11+11X12+3X13+10X14+7X31+4X32+10X33+5X34X11+X12+X13+X14=7a1X21+X22+X23+X24=4a2X31+X32+X33+X34=9a3,该模型又可表示为,i=1，2，3,j=1，2，3，4,Xij0，,i=1，2，3j=1，2，3，4,X11+X21+X31=3b1X12+X22+X32=6b2X13+X23+X33=5b3X14+X24+X34=9b4Xij0，i=1，2，3；j=1，2，3，4,3,上述问题可以扩展为m个产地n个销地的运输问题，设ai为Ai产量，bj为Bj销地销量，Ai到Bj单位运价Cij，则产销平衡的运输问题其数学模型为,i=1，2，,m,j=1，2，n,Xij0，,i=1，2，,mj=1，2，n,4,模型特点：模型有mn个变量，m+n个方程对产销平衡问题ai=bj运输问题（产销平衡）总存在可行解和最优解1、cij0Xij0cijXij0运输问题一定有界,2、一定有可行解Xij=,3、有界且有可行解，所以一定有最优解约束方程系数矩阵具有稀疏结构（见下页），秩r（A）=m+n-1,5,P11P12P1nP21P22P2nPm1Pm2Pmn111a1111a2:111am111b1111b2:111bm,m行,n行,第i个分量,第m+j个分量,系数矩阵pij除了第i和第m+j个分量为1外，其余分量全为0A的前m行之和减去后n行之和得到的是零向量，即A的行向量线性相关，其不等于零的子式的最大阶数为m+n-1,6,表上作业法步骤：1.确定初始基本可行解：有三种方法：最小元素法西北角法伏格尔法2.求非基变量检验数，进行最优解判别，若最优，停止，否则进行下一步3.确定进基、离基变量，找新的基本可行解，返回2，重复2、3，直到得到最优解。,7,最小元素法,基本思想：步骤：1.从单位运价表中找最小元素Ckt=minCij2.根据Ckt对应的产地产量ak、销地销量bt确定调运量调运量Xkt=minak，bt，将Xkt填在产销平衡表第（k，t）格若akbt，Xkt=bt，划去第t列，置ak=ak-bt若akbt，Xkt=ak，划去第k行，置bt=bt-ak若ak=bt划去第k行或第t列，置bt=0或ak=03.从未被划去元素中再找最小元素，重复1、2，当填入最后一个元素时，同时划去一行一列。,8,3,1,4,6,3,3,注意：最小运价有多个时，可任选一个保证数字格数量为（m+n-1）个,产销平衡表中填入数字的格为数字格，其余格为空格。,9,伏格尔法,思路：步骤：1.计算各行各列最小元素与次最小元素Cij的差，分别填在最右一列和最下面一行2.选差最大的行（或列），根据该行（列）最小元素Cij确定调运量,10,列差额,0,1,1,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,11,最优解判别：两种方法:闭回路法位势法1.闭回路法：闭回路：互不相同的2k个变量X11X21X22XkkX1k（其下标交错相等,在表中表现为相临的两个变量，同行或同列）组成一个闭回路。,12,闭回路求法：在给出调运方案的产销平衡表上，从某一空格（k，t）格出发，沿水平或竖直方向前进，遇到一个合适的数字格转弯90继续前进，再遇到一个合适的数字格再转弯90，继续前进，最后又回到原来的出发点（k，t）格，称这样走过的一条路线为从（k，t）格出发的闭回路。,注：以空格为起点，以某些数字格为转折点，最终返回起点，所构成的一个路线称为闭回路。闭回路是惟一的！每一个空格点都能构成一条闭回路！,13,检验数求法：对从（k，t）格出发的闭回路各顶点依次编号,（k，t）格为第一顶点，对所经过的其它各顶点顺序编号，依次为第二、第三顶点，则闭回路上所有奇数点单位运价之和减偶数点单位运价之和所得的差，即为（k，t）格的检验数kt,+1,-1,+1,-1,11=（C11+C23）-（C13+C21）=（3+2）-（3+1）=1,14,位势法设Xij为Ai到Bj的运量，根据例1运输问题数学模型,设U1，U2，U3，V1，V2，V3，V4为对应3+4个约束方程的对偶变量，则其对偶问题为Max=Uiai+VjbjUi+VjCij,Ui，Vj无约束,i=1,2,3j=1,2,3,4,15,同理：对一般运输问题数学模型,设U1，U2，Um，V1，V2，Vn为对应运输问题m+n个约束方程的对偶变量对偶问题数学模型：Max=Uiai+VjbjUi+VjCijUi，Vj无约束Ui，Vj又分别称为对应于发点（产地）i和收点（销地）j的位势,i=1,2,mUi,j=1,2,nVj,Xij0，,i=1，2，,mj=1，2，n,16,设基B为运输问题的一个可行基，则对偶变量Y=CBB-1=(U1,U2,Um,V1,V2,Vn)决策变量Xij的系数列向量,检验数ij=Cij-CBB-1Pij=Cij-(U1,U2,Um,V1,V2,Vn),=Cij-Ui-Vj,由单纯形法原理可知基变量检验数为零即Cij-Ui-Vj=0Cij=Ui+VjXijXB即：我们可以把某一调运方案中所有基变量的运价Cij分解为对应的行位势和列位势两部分,17,续上页：由于基变量Cij=Ui+Vj非基变量检验数ij=Cij-Ui-Vj只要求出Ui、Vj，则可求出ij例：例1初始调运表见下表,该例：m=3，n=4，基变量有6个，对应的Cij方程也有6个，而位势量(对偶变量)有7个，6个方程解出7个位势有很多解，把U1作为自由变量，令U1=0C13=U1+V3=3V3=3C14=U1+V4=10V4=10C23=U2+V3=2U2=-1C21=U2+V1=1V1=2C34=U3+V4=5U3=-5C32=U3+V2=4V2=9将位势量填入调运方案表中，计算非基变量的检验数ij=Cij-Ui-Vj,18,上述计算过程可在表中进行，其中基变量Cij=Ui+Vj非基变量检验数ij=Cij-Ui-Vj方法：1.在产销平衡表分别增加一行、一列2.计算行位势和列位势,分别填入最右一列、最后一行对应位置,0,3,10,-1,2,-5,9,注：上表中右上角数字为单位运价，左下角红色数字为非基变量检验数，中间兰色数字为调运量上表中有负检验数，说明不是最优解,1,2,1,-1,10,12,19,位势法步骤：已知基可行解Xij1、对基变量Xij，解方程Cij=Ui+Vj，得到Ui，Vj2、对非基变量Xij计算ij=Cij-Ui-Vj，若ij全0，停。否则，转33、方案调整。,20,调运方案的改进闭回路调整法1、确定进基格（进基变量）Min=ijij0=ktXkt为进基格2、作出从进基格（k，t）格出发的闭回路，对各顶点顺序编号,3、确定调整量和离基格调整量Q=min偶数点调运量,4、闭回路调整：闭回路上：奇数顶点调运量+Q偶数顶点调运量-Q其余格运量不变,21,5,2,3,1,6,3,0,3,10,-5,9,-2,3,0,2,2,1,9,12,表中解为最优解非基变量X11检验数11=0，所以该运输问题有无穷多解11=0，作出（1，1）格的闭回路，进行最优解调整，则得另一最优方案。,22,运输问题的解的情况：1、无穷多最优解：,23,2、退化解：有基变量取值为零的情况。,31145,7738,12106,3,6,4,1,6,0,24,31145,7738,12106,3,6,0,4,1,6,25,1）在用表上作业法求初始调运方案时，第（k，t）格的调运量Xkt=minakbt当ak=bt时，有两种处理方法：划去第k行或第t列，继续找其它数字格同时划去第k行和第t列，在划去的行或列的某个空格处填上一个零作为数字格2）在用闭回路法对调运方案改进时：在闭回路顶点出现两个以上最小运量，调整后，这些偶数顶点减去调整量后，运量为零，这时，只能把其中的一个数字格作为出基格，其余仍为运量为零的数字格当出现退化解后再作调整时，有可能在闭回路的偶数顶点上出现运量为零的数字格，这时调整量为零。,26,产销不平衡运输问题及其求解方法1、产销：aibj,Xijaii=1，2mXij=bjj=1，2n,松弛变量Xi，n+1（I=1，2m）表示Ai的库存量，增加销地Bn+1,销量ai-bj，对应运价Ci，n+1=0,i=1，2m,j=1，2n，n+1,27,B5,0,0,0,4,4,2,3,3,3,2,2,ui,vj,0,2,4,0,-2,3,0,3,8,0,8,2,5,7,7,2,28,2.销产：bjai增加虚产地Am+，产量am+1=bj-ai，对应运价Cm+1，j=0,Minz=CijXij,i=1,j=1,m+1,n,Xij=ai1,2+1,j=1,n,ij=bjj=1,2n,i=1,m+1,29,例2:设有3个化肥厂供应4个地区的农用化肥,假定等量化肥在这些地区使用效果相同,各化肥厂年产量,各地区年需求量、各化肥厂到各地区运送单位化肥的运价如下表,试求出总运费最小的化肥调拨方案,30,16,14,19,17,15,-,D,M,0,M,0,M,0,50,30,70,30,10,20,50,31,用表上作业法求得最优方案为：,32,例3：某调运问题，其产地产量、销地销量及单位产品获利情况见下表，已知丙销地至少保证供应C产品1000，而因某种原因，该地不经销A产品，求使得总销售收入最大的调运方案及相应利润。,33,1500,500,500,500,500,500,ui,Vj,0,0,4,6,5,4,12,-7,-5,0,-4,-6,-6,34,0,11,1,C22-1,10-C22,13-C22,C22-11,P1003.4题,-3+C22,10+C22,10-C22,24-C22,17,18-C22,-3+C220,10+C220,10-C220,24-C22018-C220,35,0,11,1,6,3,6,-4,4,17,C24-17,17,11,当C24-17=0有无穷多最优解,17,36,闭回路调整得另一最优方案,37,教材3、4题要求除了表中最优方案外至少写出其它两个最优方案,105,05155,150,5,01510,5,38,三、四、五章习题课,1。甲乙丙三个城市分别需要煤炭320、250、350（万吨），由