Transportation-problemPPT课件

.,1,第4讲运输问题,运输问题的数学模型表上作业法产销不平衡的运输问题运输问题应用举例,.,2,运输问题（TransportationProblem，简记为TP）是一类常见而且极其特殊的线性规划问题.它最早是从物资调运工作中提出来的，是物流优化管理的重要的内容之一。,从理论上讲，运输问题也可用单纯形法来求解，但是由于运输问题数学模型具有特殊的结构，存在一种比单纯形法更简便的计算方法表上作业法，用表上作业法来求解运输问题比用单纯形法可节约计算时间与计算费用.但表上作业法的实质仍是单纯形法。,.,3,1.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,设xij表示产地Ai运往销地Bj(i=1,2,m;j=1,2,n)的运量.,运输表,注意:cij在左下角xij在右上角,.,5,1.2运输问题数学模型的特点,平衡运输问题的约束方程系数矩阵A,.,6,矩阵A有m+n行，每行的特点：前m行有n个1，这n个1连在一起，其余元素为0；后n行每行有m个1，其余元素为0。矩阵A有mn列，每一列只有两个元素为1，其余元素均为0。列向量Pij=(0,，0，1，0，,0,1,0,0)T，其中两个元素1分别处于第i行和第m+j行,即,.,7,将矩阵A分块，特点是：前m行构成m个mn阶矩阵,而且第k个矩阵只有第k行元素全为1，其余元素全为0（k=1，m）；后n行构成m个n阶单位阵。,其中e1是元素全为1的n维行向量，In为n阶单位矩阵。,.,8,又因为，对于任一可行解有目标函数值，对于求极小化问题，目标函数值有下界，则必有最优解.,证明:,则取,又,所以，是问题的一个可行解.,.,9,证明：,定理2说明：基可行解包含m+n-1个基变量.,.,10,2.由的第二至m+n行和前n列及对应的列交叉处元素构成m+n-1阶方阵D非奇异。,前m行相加之和减去后n行相加之和结果是零向量，说明m+n个行向量线性相关，因此的秩小于m+n；,证明系数矩阵A及其增广矩阵的秩都是m+n-1,因此的秩恰好等于m+n-1，又D本身就含于A中，故A的秩也等于m+n-1,.,11,.,12,可以证明：m+n个约束方程中的任意m+n-1个都是线性无关的。,.,13,.,14,Proof:,设x是Ax=b的任一基可行解，,B为对应的基矩阵，则,其中Bt是用b中对应的m+n-1元素替换B的第t列元素得到的矩阵.,显然，由定理3知，detBt是个整数，detB=，因此，都是整数.,其基变量为,.,15,.,16,如：,变量集合,变量集合,或格组,或格组,.,17,3、每一行（或列）若有闭回路的顶点，则有两个顶点；,4、每两个顶点格子的连线都是水平的或垂直的；,1、闭回路中顶点的个数必为大于或等于4的偶数.,闭回路的几何特征：,2、每一个顶点格子都是90转角点；,.,18,思考：下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？为什麽？,.,19,闭回路的代数性质：,构成闭回路的变量组对应的列向量组,必线性相关.,证明,由直接计算可知,故该向量组线性相关.,.,20,.,21,分组构成闭回路，则该变量组对应的列向量组,是线性相关的.,推论1若变量组对应的列向量组线性无关，则该变量组一定不包含闭回路.,性质2的证明可借助性质1和高等代数中“若向量组中部分向量线性相关，则整个向量组就线性相关”的定理得到。,.,22,一个变量xij是它所在的行（第i行）或列（第j列）,中出现于（*）中的唯一变量，则称该变量xij是该变量,组的一个孤立点.,闭回路的特征,注：孤立点不会是闭回路上的点。,.,23,若一变量组中不包含任何闭回路，则该变量组必有孤立点.,注：性质3的逆命题不一定成立。,变量组中虽有孤立点，但包含闭回路。,.,24,证明:,用反证法,设变量组（*）对应的列向量,组线性无关，但该变量组包含一个以其中某些变量为顶点的闭回路，,则由性质2知，这些变量对应的列向量必,线性相关，与假设矛盾.,变量组对应的列向量组线性无关的充要,条件是该变量组中不包含任何闭回路.,设有一组数使得,.,25,又不妨设是（*）在第i1行上唯一的变量，这时由pij的特征，（1）的左端第i1个分量和为k1，而右端为0，,.,26,推论2平衡运输问题中的一组m+n-1个变量能构成基变量的充要条件是它不包含任何闭回路.,该推论给出了运输问题的基可行解中基变量的一个基本特征：基变量组不含闭回路.这就是基可行解在表上的一个表现，利用它来判断m+n1个变量是否构成基变量组，就看它是否包含闭回路.这种方法简便易行，它比直接判断这些变量对应的列向量是否线性无关要简便得多.,利用基变量的这个特征，将可以导出求平衡运输问题的初始基可行解的一些简便方法.,.,27,表上作业法（又称运输单纯形法）是根据单纯形法的原理和运输问题的特点，设计的一种在表上运算的求解运输问题的简便而有效的方法.,主要步骤：,1、求一个初始调运方案（初始基可行解）；,2、判别当前方案是否为最优，若是则迭代停止，否则转下一步；,3、改进当前方案，得到新的方案（新的基可行解），再返回2。,2表上作业法,.,28,已知某商品有三个产地A1、A2、A3和四个销地B1、B2、B3、B4，产量、销量及单位运价如表.问应如何调运，在满足各销地需要的情况下，使总的运费支出为最少？,一、初始方案的确定,1、西北角法,例1,50,解：,5,10,10,20,5,规则:从运输表的西北角开始,优先安排编号小的产地和销地的运输任务.,填了几个数字？,注意:在填入一个数时，如果行和列同时饱和，规定只划去一行或一列,50,0,.,29,50,5,10,10,20,5,50,例1的初始调运方案（西北角法）,.,30,2、最小元素法,规则:优先安排单位运价最小的产地与销地之间的运输任务，即就近供应。,40,10,25,5,10,10,注意:在某行（或列）填入一个数时，如果行和列同时饱和，规定只划去该行（或列）,0,0,10,10,20,50,填了几个数字？,.,31,定理6用西北角法或最小元素法得到的初始解是平衡运输问题的基可行解，m+n-1个填入数字的格子对应的是基变量.,证明:,首先，得到的初始解为可行解是显然的.,其次，由于行列数共有m+n，而按填数字的方法,除填最后一个数时，划去一行一列外，每填一个数划去一行或一列.因此,共填m+n-1个数.,最后，证明所填m+n-1个数对应的变量组不含闭回路.,用反证法,若含有闭回路,不妨设此闭回路如右（其他情形同理可证）,.,32,不妨设填后划去行，故必须较先填，且填后划去的是列，从而必须较先填，且填后划去的是行，而这又说明必须较先填，且填后划去的是列，这又得到必须较先填，且填后划去的是行，这样就得到了矛盾，所以，填数的m+n-1个格子对应的变量组不含闭回路，从而，证得了本定理.,.,33,关键,3,1,5,按最小元素法,.,34,3、伏格尔法(元素差额法),最小元素法的缺点：为了节省一处的费用，有时造成在其它处要花几倍的运费。所以我们考虑若一产地的产品不能按最小运费就近供应，就考虑次小运费，这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加越多。因而，对差额最大处，就优先采用最小运费调运，这就是伏格尔法的基本思想,.,35,3,1,5,3,4,2,注：伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。,优先安排差额最大的所在行或列的单位运价最小的产地与销地之间的运输任务,规则：计算各行各列的最小元素与次小元素的差额，,.,36,50,5,20,40,例1的初始调运方案（伏格尔法）,10,15,10,.,37,二、最优性检验,定理7设是平衡运输问题的一组基变量，是非基变量，则格组中必存在唯一的闭回路.,.,38,（2）唯一性：若格组中存在两个不同的闭回路，由（1）分析可知，这两个闭回路中必都有非基格，即可由基向量组写出两种不同的线性组合。,.,.,-知,设,据基变量组所对应的系数列向量组线性无关知,.,39,40,10,25,5,10,10,1、闭回路法,+1,-1,+1,-1,检验数表,-5,-1,0,6,6,6,检验数,检验数,.,40,40,10,25,5,10,10,+1,-1,+1,-1,闭回路的经济解释:在已给出的初始解的表中，可以从任意一个空格出发，如，若让的产品调运1个单位给，为了保持产销平衡，就要依次调整：在处减少一个单位，在处增加一个单位，在减少一个单位，即构成了以空格为起点，其它为数字格的闭回路。可见这样调整得运费的改变量为：,.,41,2、位势法（对偶变量法）,约束方程的系数矩阵的秩为m+n-1,.,42,由于,xj的检验数,ui称为行位势，vj称为列位势,解上面第一个方程，将ui、vj代入第二个方程求出。,.,43,检验数表,-5,-1,0,6,6,6,-2,-1,2,0,2,7,3,见例1最小元素法得到的初始基可行解,10,0,5,3,-1,2,-5,若，则此时的运输方案为最优的,.,44,定理8检验数与初始给定的取值无关。（下面的证明摘自教材最优化方法书后参考文献1）,证明：,.,45,引理1,.,46,.,47,.,48,.,49,引理2,.,50,由此定理可知，我们用位势法求检验数时给定初始的Vn=0是合理的，从而计算出的ij是唯一的。,.,51,三、基可行解的改进,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,因为，所以此运输方案为最优方案,.,52,50,25,20,20,例1的最优调运方案,10,15,10,.,53,model:!3发点4收点产销平衡的运输问题;sets:cd/1.3/:capacity;xd/1.4/:demand;links(cd,xd):cost,variable;endsets!目标函数;min=sum(links:cost*variable);!需求约束;for(xd(j):sum(cd(i):variable(i,j)=demand(j);!产量约束;for(cd(i):sum(xd(j):variable(i,j)=capacity(i);!这里是数据;data:capacity=702010;demand=50251015;cost=1052343125634;enddataend,求解例1的lingo源代码,.,54,求解例1的lingo输出报告,.,55,.,56,练习1某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。产销平衡表见表1。已知从各工厂到各销售点的单位产品的运价为表2所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。,表1产销平衡表,表2单位运价表,BOOKP122例1.4.2-例1.4.4,.,57,表3最优调运方案,表4检验数表,所以调运的总运费最小是85元。,解：,.,58,练习1的lingo输出报告,.,59,.,60,求初始基本可行解时，当minai,bj=ai=bj时，此时要同时划去第i行及第j列，为了确保调运表上仍有m+n-1个基变量的取值，需要在所划去的第i行或第j列任一空格上加0,表示这个格中的基变量的取值是0，这样就出现了退化解。若在闭回路上有几个偶点处的运量等于，则可任取其中一个作为出基变量（运量擦去），其余几个点的值调整后变为0，但应填入，说明这些变量还在基内，这时就出现了退化。,(1)有无穷多最优解.最终解中有非基变量检验数为零时，以此非基变量为换入变量，可求得另一基最优解。基最优解的任一凸组合都是最优解。BOOKP136例1.4.4,表上作业法计算中的两个问题,(2)退化解.解中非零基变量个数小于m+n-1时，为退化解。一般在下面两种情况下出现：BOOKP138例1.4.5+例1.4.6,.,61,设数学模型为,关于极大化运输问题的求解,.,62,例2下列矩阵C是Ai到Bj的吨公里利润,产量、销量及其单位利润合并于下表，问运输部门如何安排运输方案使总利润最大？,.,63,方法I：将极大化问题转化为极小化问题。设极大化问题的运价表为C=（cij）mn，用一个较大的数M（Mmaxcij）去减每一个cij得到矩阵C/=（c/ij）mn，其中c/ij=Mcij0，将C/作为极小化问题的运价表，用表上作业法求出最优解，目标函数值为：,.,64,用最小元素法求初始运输方案,检验数表,由于检验数全部非负,因此该初始运输方案也是最优运输方案,则最大利润为：Z=89+1010+68+54=240,.,65,方法II:所有非基变量的检验数ij0时最优.求初始运输方案可采用最大元素法.,如上例,用最大元素得到的初始运输方案:,8149,求检验数:11=8,12=4,21=2,23=2,全部非正,得到最优解运输方案,结果与第一种方法相同.,.,66,当,当,3产销不平衡的运输问题,.,67,当,可以虚设一个产地Am+1,其产量为,并假设产地Am+1运往各销地的单位运价为cm+1,j=0(j=1,2,n).则原问题可转化为平衡运输问题：,产大于销，可通过虚设销地，类似建立平衡运输模型,.,68,例3,已知运输问题由表给出，试建立运输模型.,解:,本题产量为25，销量为29，是销大于产问题,虚设一个产地A3，由于并没有生产，所以运价为零，得运输模型.,如果各销地不满足时，单位缺货费为4，3，7，则运输模型为,4,3,7,.,69,已知运输问题由表给出，如果产地Ai的产量必须运走，试建立运输模型.,例4,解:,这是一个产大于销的运输问题.,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.,建立运输模型.,.,70,练习2设有三个化肥厂(A，B，C)供应四个地区(，)的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如表1所示。试求出总的运费最节省的化肥调拨方案。,BOOKP145例1.4.8,.,71,解：这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，第个地区每年最多能分配到60万吨，这样最高需求为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个假想的化肥厂D，其年产量为50万吨。由于各地区的需要量包含两部分，如地区，其中30万吨是最低需求，故不能由假想化肥厂D供给，令相应运价为M(任意大正数)，而另一部分20万吨满足或不满足均可以，因此可以由假想化肥厂D供给，按前面讲的，令相应运价为0。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以写出这个问题的产销平衡和单位运价表(表2)。,.,72,产销平衡表和单位运价表合并于下面的表2,.,73,根据表上作业法计算，可以求得这个问题的最优方案如表3所示,.,74,某制冰厂每年14季度必须供应冰块15、20、25、10（千吨）.已知该厂各季度冰块的生产能力及冰块的单位成本如表.如果生产出来的冰块不在当季度使用，每千吨冰块存储一个季度费用为4（千元）.又设该制冰厂每年第3季度末对贮冰库进行清库维修.问应如何安排冰块的生产，可使该厂全年生产、存储费用最少？,例5(生产调度问题),4运输问题应用举例,.,75,解：,5,B5,4,9,13,M,0,M,M,M,M,M,0,0,0,5,11,8,17,9,13,7,.,76,某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务.已知各条航线的起点、终点城市及每天航班数见表1，假定各条航线使用相同型号的船只，又各城市间的航程天数见表2.,例6(空车调度问题),又知每条船只每次装卸货的时间各需一天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求？,表1,表2,.,77,解：,该公司所需配备船只分两部分.,1、载货航程需要的周转船只数,表1,表2,如航线1，在港口E装货1天，E至D航程17天，在D卸货1天，总计19天.每天3航班，故该航线周转船只需57条.,累计共需周转船只数91条.,.,78,2、各港口间调度所需船只数,港口每天到达与需要的船只不同，如表.,为使配备船只数最少，应做到周转的空船数为最少.,建立运输模型，C、D、F为空船的产地，A、B、E为销地，单位运价为相应各港口之间的船只航程天数.,1,1,1,1,1,用表上作业法求出空船的最优调度方案.,最少需周转的空船数为40条.,所以，在不考虑维修、储备等情况下，该公司至少应配备131条船.,.,79,例7(转运问题)某公司有A1、A2、A3三个分厂生产某种物质，分别供应B1、B2、B3、B4四个地区的销售公司销售。假设质量相同，有关数据如下表：,表1产销平衡表,表2单位运价表,.,80,如果假定：每个工厂生产的产品不一定直接发运到销售点，可以将其中几个产地集中一起运；运往各销地的产品可以先运给其中几个销地，再转运给其他销地；除产、销地之外，中间还可以有几个转运站，在产地之间、销地之间或产地与销地间转运。已知各产地、销地、中间转运站及相互之间每吨产品的运价如表3所示，问在考虑到产销地之间直接运输和非直接运输的各种可能方案的情况下，如何将三个厂每天生产的产品运