数学建模---第四章-运输问题PPT课件

.,1,第四章运输问题,组合优化理论,CombinatorialOptimizationTheory,.,2,第四章运输问题,运输问题（TransportationProblem，简记为TP）是一类常见而且极其特殊的线性规划问题.它最早是从物资调运工作中提出来的，是物流优化管理的重要的内容之一。,从理论上讲，运输问题也可用单纯形法来求解，但是由于运输问题数学模型具有特殊的结构，存在一种比单纯形法更简便的计算方法表上作业法，用表上作业法来求解运输问题比用单纯形法可节约计算时间与计算费用.但表上作业法的实质仍是单纯形法,加速物资流转降低流通费用,.,3,1运输问题及其数学模型,1运输问题及其数学模型,设某种物资共有m个产地A1，A2，Am，各产地的产量分别是a1，a2，am；有n个销地B1，B2，Bn，各销地的销量分别为b1，b2，bn.假定从产地Ai（i=1，2，m）向销地Bj（j=1，2，n）运输单位物资的运价是cij，问怎样调运才能使总运费最小？,一、运输问题的数学模型,.,4,第四章运输问题,运输表,1、产销平衡问题,即,设xij表示产地Ai运往销地Bj(i=1,2,m;j=1,2,n)的运量.,Note:cij在左下角xij在右上角,.,5,1运输问题及其数学模型,2、产销不平衡问题,当,当,.,6,第四章运输问题,二、运输问题数学模型的特点,讨论产销平衡问题,证明,定理2说明：基可行解包含m+n-1个基变量.,证明,note,Goon,.,7,定理1的证明,Proof:,则取,显然有，,又,所以，是问题的一个可行解.,又因为，对于任一可行解有目标函数值，对于求极小化问题，目标函数值有下界，则必有最优解.,.,8,1运输问题及其数学模型,Note:,平衡运输问题有个变量，个约束条件，规模很大。,Goback,.,9,定理4的证明,Proof:,设x是Ax=b的任一基可行解，,B为对应的基矩阵，则,其中Bt是用b中对应的m+n-1元素替换B的第t列元素得到的矩阵.,显然，由定理3及ai、bj都是整数知，detBt是个整数，detB=，因此，都是整数.,其基变量为,.,10,第四章运输问题,定义1,凡是能排列成,（其中互不相同，互不相同）,形式的变量集合，称为一个闭回路，其中诸变量称为这个闭回路的顶点.,如：,变量集合,变量集合,2、每一行（或列）若有闭回路的顶点，则有两个顶点；,3、每两个顶点格子的连线都是水平的或垂直的；,4、闭回路中顶点的个数必为偶数.,闭回路的几何特征：,1、每一个顶点格子都是90转角点；,.,11,1运输问题及其数学模型,闭回路的代数性质：,构成闭回路的变量组对应的列向量组,必线性相关.,证明,分组构成闭回路，则该变量组对应的列向量组,是线性相关的.,推论1若变量组对应的列向量组线性无关，则该变量组一定不包含闭回路.,Goon,.,12,性质1的证明,Proof:,由直接计算可知,故该向量组线性相关.,.,13,第四章运输问题,一个变量xij是它所在的行（第i行）或列（第j列）,中出现于（*）中的唯一变量，则称该变量xij是该变量,组的一个孤立点.,闭回路的特征,没有孤立点,若一变量组中不包含任何闭回路，则该变量组必有孤立点.,反证,孤立点不会是闭回路上的点,变量组对应的列向量组线性无关的充要,条件是该变量组中不包含任何闭回路.,证明,.,14,定理5的证明,Proof:,用反证法,设变量组（*）对应的列向量,组线性无关，但该变量组包含一个以其中某些变量为顶点的闭回路，,则由性质2知，这些变量对应的列向量必,线性相关，与假设矛盾.,定理5,变量组对应的列向量组线性无关的充要,条件是该变量组中不包含任何闭回路.,设有一组数使得,由于变量组（*）中不包含任何闭回路，由性质3可知其中必有孤立点，,不妨设为孤立点，,又不妨设是（*）在第i1行上唯一的变量，这时由pij的特征，（1）的左端第i1个分量和为k1，而右端为0，,在第j1列上的唯一变量如何？,但仍不包含闭回路，其中还有孤立点,与前面类似分析可证k2=0.同理得k3=k4=kr=0,这就证明了向量组（*）线性无关.,.,15,1运输问题及其数学模型,推论2平衡运输问题中的一组m+n-1个变量能构成基变量的充要条件是它不包含任何闭回路.,该推论给出了运输问题的基可行解中基变量的一个基本特征：基变量组不含闭回路.这就是基可行解在表上的一个表现，利用它来判断m+n1个变量是否构成基变量组，就看它是否包含闭回路.这种方法简便易行，它比直接判断这些变量对应的列向量是否线性无关要简便得多.,利用基变量的这个特征，将可以导出求平衡运输问题的初始基可行解的一些简便方法.,.,16,2运输问题的表上作业法,2运输问题的表上作业法,表上作业法（又称运输单纯形法）是根据单纯形法的原理和运输问题的特点，设计的一种在表上运算的求解运输问题的简便而有效的方法.,主要步骤：,1、求一个初始调运方案（初始基可行解）；,2、判别当前方案是否为最优，若是则迭代停止，否则转下一步；,3、改进当前方案，得到新的方案（新的基可行解），再返回2。,.,17,第四章运输问题,一、初始方案的确定,1、西北角法,Ex.1,50,已知某商品有三个产地A1、A2、A3和四个销地B1、B2、B3、B4，产量、销量及单位运价如表.问应如何调运，在满足各销地需要的情况下，使总的运费支出为最少？,解：,5,10,10,20,5,规则:从运输表的西北角开始,优先安排编号小的产地和销地的运输任务.,填了几个数字？,Note:在填入一个数时，如果行和列同时饱和，规定只划去一行或一列,50,0,.,18,2运输问题的表上作业法,2、最小元素法,规则:优先安排单位运价最小的产地与销地之间的运输任务.,40,10,25,5,10,10,Note:在某行（或列）填入最后一个数时，如果行和列同时饱和，规定只划去该行（或列）,0,0,10,10,20,50,填了几个数字？,.,19,第四章运输问题,定理6用西北角法或最小元素法得到的初始解是平衡运输问题的基可行解，m+n-1个填入数字的格子对应的是基变量.,Proof:,首先，得到的初始解为可行解是显然的.,其次，由于行列数共有m+n，而按填数字的方法,除填最后一个数时，划去一行一列外，每填一个数划去一行或一列.因此,共填m+n-1个数.,最后，证明所填m+n-1个数对应的变量组不含闭回路.,用反证法,若含有闭回路,不妨设此闭回路如右（其他情形同理可证）,不妨设填后划去行，故必须较先填，且填后划去的是列，从而必须较先填，且填后划去的是行，而这又说明必须较先填，且填后划去的是列，这又得到必须较先填，且填后划去的是行，这样就得到了矛盾，所以，填数的m+n-1个格子对应的变量组不含闭回路，从而，证得了本定理.,.,20,2运输问题的表上作业法,关键,3,1,5,按最小元素法,3,4,2,3、Vogel法(元素差额法),规则：计算各行各列的最小元素与次小元素的差额，,优先安排差额最大的所在行或列的单位运价最小的产地与销地之间的运输任务,这是最优解,.,21,第四章运输问题,二、最优性检验,40,10,25,5,10,10,1、闭回路法,+1,-1,+1,-1,检验数,检验数表,-5,-1,0,6,6,6,.,22,2运输问题的表上作业法,2、位势法（对偶变量法）,求检验数的方法,约束方程的系数矩阵的秩为m+n-1,x0必为基变量,x0=0,约束方程的系数矩阵的秩为m+n,对任意的a0，与原问题等价,由于,xj的检验数,设：为基变量，由于基变量的检验数等于零,一定有解，不唯一（a0可任取）,ui称为行位势，vj称为列位势,.,23,第四章运输问题,检验数表,-5,-1,0,6,6,6,-2,-1,2,0,2,7,3,见Ex.1最小元素法得到的初始基可行解,10,0,5,3,-1,2,-5,若，则此时的运输方案为最优的,.,24,2运输问题的表上作业法,三、基可行解的改进,40,10,25,5,10,10,检验数表,-5,-1,0,6,6,6,选择进基变量,则取非基变量xst为进基变量,确定出基变量,调整量,则基变量xkl出基（运量擦去）,调整方法：在该闭回路上，奇点运量加，偶点减去,能转运多少？,15,30,10,6,5,4,20,10,1,-5,6,5,20,6,6,4,5,6,因为，所以此运输方案为最优方案,Note:若在闭回路上有几个偶点处的运量等于，则可任取其中一个作为出基变量（运量擦去），其余几个点的值调整后变为0.(但应填入，说明这些变量还在基内，这时就出现了退化),620-50-50=520,问：从A2到B4的单位运价c24在什么范围变化时，所得最优调运方案不变.c12在什么范围变化呢？,.,25,第四章运输问题,补充：运输问题的图上作业法,图上作业法是在交通图上进行物资调运方案编制和调整的一种科学方法。在铁路特别是公路运输中使用很多且有很好的效果。,在交通图中，用表示产地（发点），并将产量记在圆圈内；用表示销地（收点），并将销量记在方框内。,20,60,40,40,2,4,6,3,目标：吨公里数(费用)最小的调运方案.,物资调运的流向用与交通线平行的箭线表示，规定画在前进方向的右边，调运量加括号记在箭线的右边。,(20),(20),(40),.,26,补充：运输问题的图上作业法,20,30,30,20,2,4,3,对流：物资在同一线路上往返运输.,(20),(20),(30),(30),(10),这是对流,20,30,30,20,2,4,3,(20),(20),(30),(30),10,60,30,(10),(20),1、无圈的交通图,20,20,50,20,10,对于无圈图，每条边都是割边，去掉它网络将不连通，所以，每条边上的运量是不得不,只要每条边上不产生对流，即为最优方案,.,27,第四章运输问题,20,60,40,40,2,4,6,3,(20),(20),(40),2、有一个圈的交通图,圈长：圈上每一条边的长度之和（记为l）,l=15,先用“丢边破圈”方法，得到无圈图，再产生一个没有对流的方案。,内圈长l内：流向在圈内的边的长度之和,l内=8,外圈长l外：流向在圈外的边的长度之和,l外=4,是最优解吗？,称为迂回,调整方案：对内圈各流量中最小调运量，进行反向调运,(40),(20),(20),结论：内外圈长都小于圈长的一半的无对流的调运方案为最优方案,.,28,补充：运输问题的图上作业法,3、有多个圈的交通图,10,60,30,20,20,50,20,30,20,有几个圈？,如有一个圈的情形，对每一个圈先用“丢边破圈”方法，得到无圈图，再产生一个没有对流的方案。再进行检查、调整。,只需检查13个圈吗？,会循环吗？,一般不够！因为对一个圈进行调整后，会对已检查的圈有影响.,不会！因为每次目标函数下降值大于一个固定值（如1）,.,29,第四章运输问题,四、产销不平衡运输问题,当,Note:通常建立运输模型指的是平衡运输模型,可以虚设一个产地Am+1,其产量为,并假设产地Am+1运往各销地的单位运价为cm+1,j=0(j=1,2,n).则原问题可转化为平衡运输问题：,产大于销，可通过虚设销地，类似建立平衡运输模型,.,30,2运输问题的表上作业法,Ex.2,已知运输问题由表给出，试建立运输模型.,解:,本题产量为25，销量为29，是销大于产问题,虚设一个产地A3，由于并没有生产，所以运价为零，得运输模型.,如果各销地不满足时，单位缺货费为4，3，7，则运输模型为,4,3,7,.,31,第四章运输问题,Ex.3,已知运输问题由表给出，如果产地Ai的产量必须运走，试建立运输模型.,解:,这是一个产大于销的运输问题.,2,3,4,虚设一销地B4,销量b4=15.,4,4,3,B3,B1,5,3,5,10,15,A4,M,10,0,M,M,0,三个销地的最低需求为30，最高需求不限.根据现有产量，B3至多能得到25.,建立运输模型.,2,说明什么？,.,32,第四章运输问题,3运输问题应用举例,Ex.4(生产调度问题),某制冰厂每年14季度必须供应冰块15、20、25、10（千吨）.已知该厂各季度冰块的生产能力及冰块的单位成本如表.如果生产出来的冰块不在当季度使用，每千吨冰块存储一个季度费用为4（千元）.又设该制冰厂每年第3季度末对贮冰库进行清库维修.问应如何安排冰块的生产，可使该厂全年生产、存储费用最少？,.,33,3运输问题应用举例,解：,5,B5,4,9,13,M,0,M,M,M,M,M,0,0,0,5,11,8,17,9,13,7,.,34,第四章运输问题,Ex.5(运量有界的运输问题),表1给出一个运输问题.现在规定产地Ai至销地Bj的运量不能超过dij,由表2给定.试建立运输问题.,解：,虚设Dij(i=1,2;j=1,2,3)6个点，Dij既作产地，又作销地，其产量、销量都为dij.,产地Ai的物资只可运送给Dij,而Dij的物资只可运送给Bj,或送给自身.,.,35,3运输问题应用举例,8,10,4,3,3,0,0,0,0,3,0,5,0,4,0,0,0,0,2,0,6,0,7,4,3,3,4,2,5,4,2,5,7,5,6,3,3,2,1,3,0,3,1,2,4,2,4,4,2,1,4,.,36,第四章运输问题,Ex.6(空车调度问题),某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务.已知各条航线的起点、终点城市及每天航班数见表1，假定各条航线使用相同型号的船只，又各城市间的航程天数见表2.,又知每条船只每次装卸货的时间各需一天，则该航运公司至少应配备多少条船，才能满足所有航线的运