chap3-运输问题及指派问题

本章知识结构,第,3,章 运输和指派问题,本章教学目标与要求,n,掌握产销平衡运输问题的数学模型及其特点,；,n,掌,握运输问题的表上作业法，包括初始调运方案的确定、检验数的计算、运输方案的调整方法,；,n,掌握产销不平衡运输问题转化为产销平衡问题的处理办法；掌握运输问题在实践中的典型应用,；,n,掌握标准指派问题的求解方法，会将各种非标准指派问题转化为标准指派问题,。,导入案例,运储物流的运输问题,运输成本占物流总成本的35-50左右，占商品价格的4-10，运输对物流总成本的节约具有举足轻重的作用。运储物流在物流运输管理中要着重考虑：运输方式的选择，运输路线的选择，编制运输计划等问题。,运输方式合适与否决定了运输时间的长短，决定了成本的高低，各种运输工具都有其使用的优势领域，对运输工具进行优化选择，按运输工具特点进行装卸运输作业，最大限度地发挥所用运输工具的作用；选择运输路线要与交通运输工具结合起来，尽量安排直达运输，以减少运输装卸、转运环节，缩短运输时间；编制运输计划还要从全局出发，深入调查研究，综合平衡，积极组织计划运输、合理运输、直达运输、均衡运输，按照成本最低的原则来制定合理的计划,。,3.1 运输问题概述,运输问题的典型提法是将某种物质从若干个产地调运到若干个销地，已知每个产地的产量和每个销地的销量，如何在许多可行调运方案中选择一个总运费最少的调运方案。,根据总产量与总销量是否相等的数量关系，运输问题通常可划分为,产销平衡,（相等）和,产销不平衡,（不相等）两大类别,。产销平衡的运输问题主要在这一节介绍，产销不平衡的运输问题将在后面节中讨论。,3.1.1 运输问题的引入,在生产、交换活动中，不可避免地要进行物资调运工作。某时期内将生产基地的煤、钢铁、粮食、矿砂、木材等各类物资，分别运送到需要这些物资的地区。,3.1 运输问题概述,【,例3.1,】,某物流公司从两个产地,A,1,(内蒙) 、,A,2,(山西)将煤炭运往三个销地,B,1,(北京) 、,B,2,(山东) 、,B,3,(上海) ，各产地的产量、各销地的销量、各产地运往各销地的每单位煤炭运费数据见下表，问：应如何调运煤炭可使总运输费用最小？,解,： 此为产销平衡的运输问题（总产量 = 总销量）。,设,x,ij,为从产地,A,i,(,i,=1,2)运往销地,B,j,(,j,=1,2,3)的运输量,x,11,x,12,x,13,x,21,x,22,x,23,则该问题的数学模型为,3.1 运输问题概述,该问题显然是一个线性规划模型，其系数矩阵,A,见下表,3.1 运输问题概述,可以看出运输问题的系数矩阵有如下特征：,（1）共有3+2行，分别表示各产地和销地；3,2列，分别表示各决策变量的系数列；,（2）每列只有两个1，其余为0，分别表示只有一个产地和一个销地被使用，由,x,ij,的行列下标所决定，这是运输问题表上作业法的由来。,3.1 运输问题概述,3.1.2 运输问题的数学模型,一般地，产销平衡的运输问题可以表述为：设有,m,个地点（称为产地或发地）,A,1,A,2,A,m,的某种物资调至,n,个地点,B,1,B,2,B,n,（称为销地或收地），各个产地需要调出的物资量分别为,a,1,a,2,a,m,单位，各个销地需要调进的物资量分别为,b,1,b,2,b,n,单位，且各个发点的供应量之和等于各个收点的需求量之和。已知每个发点,A,i,到每个收点,B,j,的物资单位调运价格为,c,ij,。现问如何安排调运，才能使总运费最小。,3.1 运输问题概述,设,x,ij,表示从产地,A,i,运往销地,B,j,的运量，,x,11,x,12,x,1,n,x,21,x,22,x,2,n,x,m,1,x,m,2,x,mn,于是产销平衡运输问题的数学模型为：,V,:,s.t.,3.1 运输问题概述,C,=,X,T,=,A,=,p,11,p,12,p,1,n,p,21,p,22,p,2,n,p,m,1,p,m,2,p,mn,A,=,=b,平衡运输问题模型写成矩阵形式为:,3.1 运输问题概述,在实际问题建立运输问题模型时，还会出现如下一些变化：,1）有时问题表面看不是运输问题，但其仍要求费用最低或要求目标函数（利润或营业额）最大化，仍可看成运输问题；,2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束。,3.1.3 运输问题的数学模型的特征,运输问题是一类线性规划问题，其目标函数一般为求总运费的极小值。根据线性规划的有关理论，如果它的最优解存在，一定可以在基可行解中找到，因而需先考察运输问题约束方程组系数矩阵的秩,r,(,A,) .,定理3.1,平衡运输问题模型的系数矩阵的秩,r,(,A,)=,m,+,n,-1 。,运输问题是特殊的线性规划,，单纯形法仍适合于运输问题。为此还要了解运输问题基可行解的性质，为说明其基本可行解的特征，引入,闭回路,的概念。,3.1 运输问题概述,定义3.1,在平衡运输问题的决策变量表中，凡是能够排列成下列形式的,x,ab,x,ad,x,cd,x,ce, ,x,st,x,sb,或,x,ab,x,cb,x,cd,x,ed, ,x,st,x,at,其中，,a,d,s,各不相同；,b,c,t,各不相同，称这些变量的集合为,一闭回路,，并将上式中的决策变量称为该闭回路的顶点。,例如,x,13,x,16,x,36,x,34,x,24,x,23,；,x,23,x,53,x,55,x,45,x,41,x,21,等都是闭回路，这些决策变量就是闭回路的顶点。,3.1 运输问题概述,根据闭回路可以看出其的一些明显特点，,闭回路是一个具有如下条件顶点格子的集合,：,1）每一个顶点格子都是转角点；,2）每一行（或列）若有闭回路的顶点，则必有两个顶点；,3）每两个顶点格子的连线都是水平的或垂直的；,4）闭回路中顶点的个数必为偶数。,定理3.2,对于产销平衡运输问题的闭回路来说，具有下面结论： 1）该问题,m,+,n,-1个变量构成基变量的充要条件是这些变量不包含任何闭回路； 2）给定一组基变量，那么从决策变量表中可找出唯一一个从任意非基变量出发，经过基变量为顶点，又回到该非基变量的闭回路。,事实上，,闭回路是一个简化的局部调运方案，反映了全局调运方案是否最优,。定理3.2给出了运输问题基本解的重要性质，为寻求运输问题的基本可行解提供了依据。与一般的线性规划问题有所不同，产销平衡的运输问题总是存在可行解，且目标函数值有界，故运输问题必有最优解。,3.2 运输问题的表上作业法,运输问题作为一类特殊的线性规划问题，在求解时仍可采用单纯形法的计算步骤，但因为运输决策变量有两个下标，可以在单位运价表和产销平衡表中进行基变量与非基变量的换基迭代，再加上运输问题模型系数矩阵的特征，早期的研究者们提出了专门针对运输问题的单纯形法,表上作业法,。,表上作业法的,主要步骤,：,第一步,求一个初始基可行解，即确定初始调运方案。,第二步,计算检验数并判断是否得到最优解。若是则迭代停止；否则转下一步；,第三步,换基迭代(即调整运量)。选一个变量出基，对原运输方案进行调整得到新的调运方案，改进当前方案，返回第二步，直至求出最优解为止。,开始,给出初始运输方案,结束,检验 运输方案是否 最优,改进运输方案,yes,no,(1),西北角法,(2),最小元素法,(3),差值(,Vogel),法,（1）闭回路法（2）位势法,3.2 运输问题的表上作业法,3.2.1 初始基可行解的确定,确定初始可行解常用的方法有,西北角法,、,最小元素法,和,差值,（,Vogel近似,）,法,。,西北角法,从产销平衡表的西北角（左上角）第一格开始，按集中供应的原则，依次安排调运量，即分析对应产地和销地的供需数量关系，尽最大可能满足需求，若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去；接着从未被划线的运价中再找出西北角的方格，重复上述操作，如此进行下去，直至得到一个基本可行解。,【,例3.2,】,设某种产品有三个生产厂商,A,1,、,A,2,、,A,3,，联合供应四个销地,B,1,、,B,2,、,B,3,、,B,4,，其供应量、需要量和单位产品的运输成本见下表，试求一调运方案。,3.2 运输问题的表上作业法,西北角法确定出的初始调运方案为：,由,A,1,B,1,运3;,A,1,B,2,运4;,A,2,B,2,运2;,A,2,B,3,运2;,A,3,B,3,运3;,A,3,B,4,运6，方案的运输总费用为,最小元素法,3.2 运输问题的表上作业法,最小元素法是按照“,最低运输成本优先集中供应,”的原则，即运价最小的需求优先满足，即从单位运价中最小的运价开始确定供需关系，然后依次找单位运价的次小值，一直到给出初始基本可行解为止。最小元素法的基本思想是就近供应，每一次都要求找出单位运价表中最小的元素，在运量表内对应的方格填入允许取得的最大数，若某行（列）的供应量（需求量）已满足，则把运价表中该运价所在行（列）划去；再找出未划去的单位运价中的最小数值，一直进行下去，直至得到一个基可行解。,【,例3.3,】,求下表所给运输问题的初始调运方案。,由,A,1,B,3,运7;,A,2,B,1,运3;,A,2,B,4,运6;,A,3,B,2,运5;,A,3,B,4,运2，方案的运输总费用为,3.2 运输问题的表上作业法,最小元素法确定出的初始调运方案为：,3.2 运输问题的表上作业法,【,例3.4,】,用最小元素法求例3.2运输问题的初始调运方案。,由,A,1,B,3,运4;,A,1,B,4,运3;,A,2,B,1,运3;,A,2,B,3,运1;,A,3,B,2,运6;,A,3,B,4,运3，方案的运输总费用为,最小元素法确定出的初始调运方案为：,3.2 运输问题的表上作业法,差值法（Vogel法）,差值法又称为伏格尔法。最小元素法只考虑了局部的运输费用最小，有时为了节省某一处运费，可能会导致其他处运费很大，缺乏对整个供需关系的考虑。差额法考虑产地和销地最小和次小运价的差额，如果差额很大，就选最小运价先调运，不然就会增加总的费用。最小元素法只考虑了局部的运输费用最小，有时为了节省某一处运费，可能会导致其他处运费很大，缺乏对整个供需关系的考虑。差额法考虑产地和销地最小和次小运价的差额，如果差额很大，就选最小运价先调运，不然就会增加总的费用。,差值法的,步骤,如下：,1）算出单位运价表各行各列中次小元素和最小元素的差额；,2）在差额最大的行或列中的最小元素处填上尽可能大的调运数（若几个差额同为最大，则可任取其一）；,3）这时必有一列或一行调运完毕，在剩下的运价表中再求最大差额，进行第二次调运，直至最后调运完毕，就得到一个初始调运方案。,3.2 运输问题的表上作业法,【,例3.5,】,用差值法求例3.2的初始调运方案。,2,5,1,3,0,1,1,5,3,2,7,6,7,2,2,10,8,10,3.2 运输问题的表上作业法,【,例3.5,】,用差值法求例3.2的初始调运方案。,由,A,1,B,3,运5;,A,1,B,4,运2;,A,2,B,1,运3;,A,2,B,4,运1;,A,3,B,2,运6;,A,3,B,4,运3，方案的运输总费用为,差值法确定出的初始调运方案为：,3.2 运输问题的表上作业法,3.2.2 检验数的计算,表上作业法计算检验数的方法有两种：一种是,闭回路法,，另一种是,位势法,。,闭回路法,根据单纯形法原理，要判断某个可行解是否为最优解，需要计算非基变量的检验数。用闭回路法求检验数时，对于给定的调运方案（基可行解），从非基变量,x,ij,出发作一条闭回路，并从,x,ij,开始将该闭回路上的顶点顺序编号（顺时针或逆时针均可），起点,x,ij,为零，依此类推。称编号为奇数的点为奇点，编号为偶数的点为偶点，则对应,x,ij,的检验数,ij,等于该闭回路上偶点处单位运价的总和与奇点处单位运价的总和之差，即,ij,=,偶点处单位运价的总和奇点处单位运价的总和,【,例3.6,】,求例3.4给出的可行解所对应的非基变量检验数。,3.2 运输问题的表上作业法,0,1,2,3,3.2 运输问题的表上作业法,0,1,2,3,3.2 运输问题的表上作业法,0,1,2,3,4,5,3.2 运输问题的表上作业法,0,1,2,3,3.2 运输问题的表上作业法,1,2,3,4,5,0,3.2 运输问题的表上作业法,1,2,3,0,3.2 运输问题的表上作业法,注,：如果全部检验数均为正数或零，则调运方案一定为最优方案；如果检验数中仍存在负数，则调运方案不是最优方案。,位势法,3.2 运输问题的表上作业法,位势法的,步骤,为：,1）在产销平衡表中，即调运方案中增加,u,i,行和,v,j,列，但在相应的基变量格（即数字格中）不是填写调运量，而是填写相应的运价，写在格的左上角；,2）令,u,1,=0或,v,n,=0，根据式,c,ij,-(,u,i,+,v,j,)=0(其中,x,ij,为基变量),依一定次序计算和，将结果填写在表中；,3）将非基变量的运价填入相应格的左上角，根据式,ij,=,c,ij,-(,u,i,+,v,j,)(其中,x,ij,为非基变量),计算相应的检验数，将结果填入相应格，写在该格的右下角。,【,例3.7,】,应用位势法求例3.4给出的初始可行解所对应的非基变量的检验数。,3.2 运输问题的表上作业法,3.2 运输问题的表上作业法,3.2 运输问题的表上作业法,3.2 运输问题的表上作业法,3.2 运输问题的表上作业法,3.2 运输问题的表上作业法,3.2 运输问题的表上作业法,3.2 运输问题的表上作业法,注,：闭回路法的主要缺点是当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。当运输问题的产地与销地很多时，空格的数目很多，用闭回路法计算检验数，要找很多的闭回路，计算量很大，而用位势法就简便得多。,3.2 运输问题的表上作业法,3.2.3 闭回路的调整,当初始基本可行解非基变量的检验数出现负数时，便需换基迭代。具体,步骤,如下：,1）若有两个和两个以上的负检验数时，一般选择其中最小的负检验数，以它对应的空格为调入格，以此格为出发点，作一闭回路，并从该空格出发，沿闭回路，将各顶点依次编号，空格编号为0。,2）取奇点所在格中最小的运量(记为,)，然后在闭回路中偶点增加,、奇点减少,，得出新的调整方案。,说明,：重新计算空格的检验数。如果所有的检验数都为正数或零，那么求出的就是最优解，不然，重复上述过程。,【,练习,】,应用闭回路调整例3.4给出的初始可行解，并计算所对应的新的可行解非基变量的检验数。,3.2 运输问题的表上作业法,0,1,2,3,3.2 运输问题的表上作业法,3.2 运输问题的表上作业法,3.3 其他形式的运输问题,产销平衡运输问题相当于线性规划的标准型，实际问题中经常还会遇到一些其他的运输问题，解决的主要方法是将这些问题都转化为产销平衡的运输问题。,3.3.1 产销不平衡的运输问题,产销不平衡的运输问题分两类：一是供大于求的运输问题；一是供不应求的运输问题。,供大于求的运输问题,供大于求的运输问题，即在,a,i,b,j,的情况下，求,c,ij,x,ij,（总费用最少），就得供大于求的运输问题模型,3.3 其他形式的运输问题,3.3 其他形式的运输问题,事实上，上面模型就是,m,个产地和,n,+1个销地的产销平衡运输问题，相当于增加了一个“虚拟”销地,B,n,+1,，由于这个销地并不存在，每个产地的剩余物资只能留在原产地，因此,A,i,产地运到,B,n,+1,的单位运价为,c,in,+1,=0，而这个销地的销量是,b,n,+1,。因而供大于求运输问题的求解思路是添加一个虚拟销地，转化为平衡运输问题来处理。,3.3 其他形式的运输问题,供不应求的运输问题,供不应求的运输问题，即在,a,i,b,j,的情况下，求,c,ij,x,ij,（总费用最少），就得供大于求的运输问题模型,3.3 其他形式的运输问题,事实上，上面模型就是,m,+1个产地和,n,个销地的产销平衡运输问题，相当于增加了一个“虚拟”产地,A,m,+1,，其相应的产量是,a,m,+1,。由于这个产地并不存在，因此,A,m,+1,产地运到,B,j,的单位运价为,c,m,+1,j,=0。因而供不应求运输问题的求解思路是添加一个虚拟产地，转化为平衡运输问题来处理。,【,例3.8,】,某公司在不同地区有,A,1,、,A,2,和,A,3,三个工厂，产品将运往,B,1,、,B,2,、,B,3,和,B,4,四个地区，其单位运价表见下表，试建立产销平衡的运输问题的数学模型。,3.3 其他形式的运输问题,销地,B,1,B,2,B,3,B,4,供应量,产地,A,1,6,10,16,8,60,A,2,14,8,16,12,100,A,3,20,6,10,4,120,需求量,30,20,80,90,220280,解,： 这是一个供大于求的物资调运问题，故增加一个虚拟的销地,B,5,，需求量为,b,5,=280-220=60，令,c,i,5,=0(,i,=1,2,3)，该供需平衡运输问题的数学模型为：,3.3 其他形式的运输问题,实际上，上述模型相应的产销平衡运输表如下表所示，,该问题的最优调运方案为：,3.3 其他形式的运输问题,3.3.2 禁运与封锁的运输问题,在实际的物资运输管理中常遇到以下情况，,某种物资不能从产地,A,i,运往销地,B,j,，或者销地,B,j,不接收从产地,A,i,调入的物资，称前者为,A,i,对,B,j,的禁运,，后者为,B,j,对,A,i,的封锁,。,造成禁运或封锁的因素很多，例如,A,i,与,B,j,之间没有运输线，或者由于自然灾害造成了原有交通运输线的中断，这样就形成了,A,i,对,B,j,的禁运；如果物资需通过铁路，航运运输，由于运输能力有限，有关部门暂时禁止这批物资通过他们所管辖的路段，也人为地造成了,A,i,对,B,j,的禁运；由于某经济原因，如质量问题或合同约束，销地,B,j,拒绝接收产地,A,i,的物资，从而形成,B,j,对,A,i,的封锁。,禁运和封锁给物资运输管理工作带来的后果是在制定物资调运方案时，必须使物资从,A,i,到,B,j,的调运量为零。也就是说，在数学模型中要增加约束条件,x,ij,=0,，去掉这个约束条件使模型转化为运输问题的方法是：,将,A,i,到,B,j,的运价,c,ij,修改为一个充分大的正数,M,，从而使得任意一个含有,x,ij,0,的调运方案均不可能成为最优方案，这样在得到了相应的运输问题的最优调运方案时，约束条件,x,ij,=0,自动地得到了满足，与线性规划的大,M,法相对应。,【,例3.9,】,供需双方在协商后签订了一个供货合同，合同规定供给方向六个地区（记为,B,1,B,2,B,6,）提供某种物资并负责物资的运输，同时规定,B,2,和,B,4,的物资只能由产地,A,1,或,A,2,调入，各地的供给量、需求量和单位运价由下表给出，试求满足合同要求的最优调运方案。,3.3 其他形式的运输问题,销地,B,1,B,2,B,3,B,4,B,5,B,6,供应量,产地,A,1,3,5,7,9,2,3,150,A,2,1,3,2,6,4,5,180,A,3,2,2,6,3,4,6,120,需求量,70,80,40,140,60,60,450,解,合同要求,B,2,和,B,4,的物资只能由,A,1,或,A,2,供给，形成了,B,2,和,B,4,对,A,3,的封锁。将,c,32,和,c,34,改为,M,，见下表，,3.3 其他形式的运输问题,应用表上作业法求解该运输问题，得到最优调运方案如下：,3.3 其他形式的运输问题,3.3.3 运力限制的运输问题,在制定物资调运方案时，管理人员应该考虑物资所经路段的运输能力。设,A,i,到,B,j,的路段的运输能力为,d,ij,，如果,A,i,的供应量和,B,j,的需求量都大于,d,ij,，则从,A,i,到,B,j,的物资调运量至多为,d,ij,。也就是说，在物资调运时,A,i,到,B,j,的路段存在着运输能力的限制，此时相应的数学模型中应增加运输能力约束，即有,x,ij,d,ij,。为将这种类型的问题转化为运输问题模型，可将,B,j,想象为两个销地,B,j,和,B,j,，规定,B,j,的需求量为,d,ij,，从而使得,A,i,到,B,j,（实际上为,A,i,到,B,j,）路段不再有运输能力的限制，同时规定,B,j,的需求量为,b,j,-,d,ij,，且,B,j,对,A,i,封锁，这样就不会有多于,d,ij,的物资经过,A,i,到,B,j,的路段。,【,例3.10,】,某运输公司可承担某种物资的运输任务，有关数据由下表给出，其中,c,ij,表示单位物资从,A,i,到,B,j,的运价。有关部门在,A,1,到,B,3,，,A,2,到,B,1,，,A,2,到,B,4,三个路段给出该公司的物资通过限量分别为15，15和10。应如何指定物资调运方案，才能使运输的总成本最小。,3.3 其他形式的运输问题,销地,B,1,B,2,B,3,B,4,供应量,产地,A,1,9,5,3,10,25,A,2,6,3,7,2,55,A,3,3,8,4,2,20,需求量,45,15,20,20,100,解,： 由于,A,2,的供应量和,B,1,的需求量都大于该路段的限制量，上述问题在,A,2,到,B,1,路段具有运输能力限制。为建立该问题的运输问题模型，将,B,1,视为二个销地,B,1,和,B,1,，需求量分别为15和30，且,B,1,对,A,2,封锁。同样处理另外二个有运输能力限制的路段，,A,1,到,B,3,和,A,2,到,B,4,，具体的处理结果见下表：,3.3 其他形式的运输问题,应用表上作业法求解，得调运方案如下：,3.3 其他形式的运输问题,将,B,j,和,B,j,合并为,B,j,(,j,=1,3,4),，,就得到可操作的调运方案，见下表,3.3 其他形式的运输问题,3.3.4 转运运输问题,在运输管理中，经常要处理物资中转的运输问题，例如物资从产地运到销地必须使用不同的运输工具，这样就需要首先将物资从产地运到某地（称为中转站），更换运输工具后再运往销地。又如，由于运输能力的限制或价格因素（转运运价小于直接运价），需要将不同产地的物资首先集中到某个中转站，再由中转站发往销地。,需要中转站的运输称为,转运运输,。,这里讨论一次转运问题，一般提法是：设有,r,个中转站,T,1,T,r,，物资的运输过程是先从产地,A,i,运到某个中转站,T,k,，再运往销地,B,j,。已知,A,i,到,T,k,的运价为,c,ik,，,T,k,到,B,j,的运价为,c,kj,，,A,i,的供给量为,a,i,，通过,T,k,的最大运输能力为,d,k,，,B,j,的需求量为,b,j,。不妨设,a,i,=,b,j,a,i,d,k,也就是说，供需是平衡的且所有的物资经转运后都能送达销地。现在要求一转运方案，使得运输的总费用最小。,3.3 其他形式的运输问题,设决策变量：,x,ik,：从,A,i,到,T,k,的调运量(,i,=1,2,m,;,k,=1,2,r,)，,x,ik,：从,T,k,到,B,j,的调运量(,k,=1,2,r,;,j,=1,2,n,), 则相应的数学模型为：,供给约束,运输能力约束,中转站平衡,需求约束,3.3 其他形式的运输问题,根据转运问题模型的结构可以看出，转运问题也可转化为运输问题模型求解，其方法是将每个中转站,T,k,既看成产地也看成销地，从而形成一个有,m,+,r,个产地，有,r,+,n,个销地的运输问题。由于物资不能由,A,i,直接到达,B,j,，故,B,j,对,A,i,封锁。同样，不同的中转站之间也互相封锁。,T,k,的供给量和需求量均为,d,k,，从而总供给量为 ,a,i,+,d,k,，总需求量为,b,j,+,d,k,，以实现供需平衡。,【,例3.11,】,将某种物资从,A,1,、,A,2,和,A,3,运往,B,1,、,B,2,、,B,3,、,B,4,和,B,5,五个销地，物资必须经过,T,1,、,T,2,、,T,3,和,T,4,中的任意一个中转站转运，有关数据由下表给出。试求解该转运问题。,3.3 其他形式的运输问题,该转运问题可转化为具体7个产地和9个销地的运输问题，有关数据见下表：,3.3 其他形式的运输问题,销地,T,1,T,2,T,3,T,4,B,1,B,2,B,3,B,4,B,5,供应量,产地,A,1,4,5,7,6,M,M,M,M,M,70,A,2,7,12,10,11,M,M,M,M,M,80,A,3,6,11,8,9,M,M,M,M,M,90,T,1,0,M,M,M,4,4,3,7,3,60,T,2,M,0,M,M,8,3,4,9,11,90,T,3,M,M,0,M,4,3,4,7,7,120,T,4,M,M,M,0,6,2,2,8,8,70,需求量,60,90,120,70,30,20,80,50,60,580,应用表上作业法可得最优调运方案，见,下表：,3.3 其他形式的运输问题,实际运输过程中物资可能需要多次中转，这种类型的转运问题比较复杂，但将它转化为运输问题模型时，与一次转运问题的处理思路一样，依照禁运与封锁原则，即当物资不能从一个产地或中转站直接到达另一个中转站或销地时，就应当对这两地实行禁运与封锁。,在现实生活中，有各种性质的指派问题。例如，有若干项工作需要分配给若干人（或部门）来完成；有若干项合同需要选择若干个投标者来承包；有若干班级需要安排在若干教室上课等等。诸如此类的问题，它们的基本要求是在满足特定的指派要求条件下，使指派方案的总体效果最佳。,【,例3.12,】,某厂拟派4个维修小组去维修4台机车，他们相应的完成工作所需时间,c,ij,(,i,j,=1,2,3,4)由右表给出。如何给每个小组安排工作才能使完成任务的总时间最少。,3.4,指派问题,指派问题,也称分配或配置问题，是资源合理配置或最优匹配问题。指派问题通常划分为,标准,和,非标准,的指派问题。,3.4.1 指派问题的引入,机车,1,2,3,4,小组,1,2,15,13,4,2,10,4,14,15,3,9,14,16,13,4,7,8,11,9,解,： 该指派问题是安排维修小组去维修机车，其决策变量为,3.4,指派问题,机车,1,2,3,4,小组,1,x,11,x,12,x,13,x,14,2,x,21,x,22,x,23,x,24,3,x,31,x,32,x,33,x,34,4,x,41,x,42,x,43,x,44,该问题的数学模型为：,任务约束,人员约束,3.4,指派问题,【,例3.13,】,某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司,A,i,(,i,=1,2,3,4,5)对新商店,B,j,(,j,=1,2,3,4,5)的建造费用的报价（万元）为,c,ij,，见下表。商业公司应当对5家建筑公司怎样分派建筑任务，才能使总的建筑费用最少？,商店,B,1,B,2,B,3,B,4,B,5,建公,A,1,4,8,7,15,12,A,2,7,9,17,14,10,A,3,6,9,12,8,7,A,4,6,7,14,6,10,A,5,6,9,12,10,6,解,： 该指派问题是安排建筑公司承建商店，其决策变量为,3.4,指派问题,该问题的数学模型为：,商店,B,1,B,2,B,3,B,4,B,5,建公,A,1,x,11,x,12,x,13,x,14,x,15,A,2,x,21,x,22,x,23,x,24,x,25,A,3,x,31,x,32,x,33,x,34,x,35,A,4,x,41,x,42,x,43,x,44,x,45,A,5,x,51,x,52,x,53,x,54,x,55,显然指派问题与运输问题相类似，该问题的指派平衡表如下：,3.4,指派问题,3.4,指派问题,3.4.2 标准指派问题的数学模型,一般地，指派问题的一般提法是：有,n,项任务，需分配给,n,个人员（或设备）去完成，已知每个人员完成某项工作的效率（或成本等）为,c,ij,，如何给每个人员指派一项工作，使得完成任务的总效率最高（或总成本最少），见下表。,任务,1,j,n,人,1,c,11,c,1,j,c,1,n,i,c,i,1,c,ij,c,in,n,c,n,1,c,nj,c,nn,解,：,3.4,指派问题,称矩阵,C,为,效率矩阵,（在其他问题中，可根据实际意义称为费用矩阵等）,，,其元素,c,ij,体现了第,i,个人完成第,j,项工作时的效率，即,决策变量,x,ij,排成的,n,n,矩阵,X,称为,决策变量矩阵,其中,3.4,指派问题,分析,：指派问题解的特征是它有,n,个1，其它都是0，且这,n,个1位于决策变量矩阵的不同行、不同列，每一种情况为指派问题的一个可行解，共,n,!个解。指派问题是：把这,n,个1放到的,n,2,个位置的什么地方可使耗费的总资源最少？（解最优）,【,例3.14,】,对于效率矩阵,决策变量矩阵,都是指派问题的最优解。,3.4,指派问题,3.4.3 指派问题的求解,指派问题既是一类特殊的整数规划问题，又是特殊的运输问题，因此可以用多种相应的解法来求解，然而这些解法都没有充分利用指派问题的特殊性质，有效地减少计算量，直到1955年库恩（W. W. Kuhn）提出的,匈牙利法,才有效地解决了指派问题。,匈牙利法的理论基础,定义3.2,独立零元素组,在效率矩阵中，有一组在不同行不同列的零元素，称为独立零元素组，其每个元素称为独立零元素。,【,例3.15,】,已知效率矩阵,求其独立零元素组。,3.4,指派问题,解,： 可行解c,12,=0， c,24,=0， c,31,=0， c,43,=0是一个独立零元素组，,c,12,=0， c,24,=0， c,31,=0， c,43,=0,分别称为独立零元素；,c,12,=0， c,23,=0， c,31,=0， c,44,=0也是一个独立零元素组，而c,14,=0， c,23,=0， c,31,=0， c,44,=0就不是独立零元素组.,根据上述对效率矩阵中零元素的分析，将效率矩阵中出现的独立零元素组中零元素所处的位置，在决策变量矩阵中令相应的,x,ij,=1，其余的,x,ij,=0，就可找到指派问题的一个最优解,如例3.14。,问题,：在有的问题中效率矩阵中独立零元素的个数不够,n,个，这样就无法求出最优指派方案，需作进一步的分析，首先给出下述定理。,3.4,指派问题,定理3.3,设指派问题的效率矩阵为,C,=,c,ij,n,n,，若将该矩阵的某一行（或某一列）的各个元素都减去同一常数,k,（,k,可正可负），得到新的效率矩阵,C,=,c,ij,n,n,，则以,C,为效率矩阵的新的指派问题与原指派问题的最优解相同。,推论,若将指派问题的效率矩阵每一行或每一列分别减去各行或各列的最小元素，则得到新指派问题与原指派问题有相同的最优解。,定理3.4,效率矩阵中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。,3.4,指派问题,匈牙利法求解步骤,第一步,：变换效率矩阵，将各行各列都减去当前各行、各列中最小元素。,第二步,：标记新矩阵的独立零元素。,1）,行检验,对变换后的效率矩阵进行逐行检验，若某行只有一个未标记的零元素时，用“*”将该零元素做标记，然后将被标记的零元素所在的列的其它未标记的零元素用“”将该零元素标记。,2）,列检验,与行检验过程类似，对进行了行检验的矩阵逐列进行检验，对每列只有一个未被标记的零元素，用“*”将该零元素做一标记，然后将该元素所在行的其他未被标记的零元素打“”将该零元素标记。重复上述列检验，直到每一列都没有未被标记的零元素或有两个未被标记的零元素为止。,这时可能出现以下三种情况： 每一行均有标记“*”出现，“*”的个数,m,恰好等于,n,； 存在未标记的零元素，但他们所在的行和列中，未标记过的零元素均至少有两个； 不存在未被标记过的零元素，“*”的个数,m,n,。,3.4,指派问题,3）,试指派,若情况出现，则可进行试指派：令“*”记号的决策变量取值为1，其他决策变量取值均为零，得到一个最优指派方案，停止计算。,若情况出现，则对每行、每列的其它未被标记的零元素任选一个，加上标记“*”，即给该零元素标记“*”，然后给同行、同列的其它未被标记的零元素加标记“”，然后再进行行、列检验，可能出现情况或，出现情况就会得到最优指派，停止计算。,若情况出现，则要转入下一步。,第三步,：作最少直线覆盖当前所有零元素。,3.4,指派问题,1）对新矩阵中所有不含“*”元素的行打 ；,2）对打的行中，所有零元素所在的列打；,3）对所有打列中标记“*”元素所在行打；,4）重复上述2），3）步，直到不能进一步打为止；,5）对未打的每一行划一直线，对已打的每一列划一纵线，即得到覆盖当前0元素的最少直线数。,第四步,：对矩阵未被直线覆盖过的元素中找最小元素，将打行的各元素减去这个最小元素，将打列的各元素加上这个最小元素（以避免打行中出现负元素），这样就增加了零元素的个数，返回第二步。,【,例3.16,】,求解例3.12和例3.13,3.4,指派问题,解,：,故可得到指派问题的最优解,X,，这样安排能使总的维修时间最少，维修时间为,z,=44911=28（小时）。,故可得到指派问题的最优解,X,，这样安排能使总的建造费用最少，建造费用为,z,=79666=34（万元）。,3.4,指派问题,3.4,指派问题,3.4.4 非标准指派问题,在实际应用中，常会遇到非标准形式，如求最大值，人数与工作数不相等以及不可接受的配置（某人不可完成某项任务）等特殊指派问题。解决的思路是先化成标准形式，然后再用匈牙利法求解，即对效率矩阵通过适当变换使得满足匈牙利算法的条件再求解。,最大化的指派问题,最大化指派问题的一般形式为,解决办法,：设最大化的指派问题的系数矩阵为,C,=,c,ij,n,n,，,M,=max,c,11,c,12,c,nn,，令,B,=,b,ij,n,n,= ,M,-,c,ij,n,n,，则以,B,为效率矩阵的最小化指派问题和以,C,为效率矩阵的原最大化指派问题有相同的最优解。,3.4,指派问题,【,例3.17,】,某工厂有4名工人A,1, A,2, A,3, A,4,分别操作4台车床B,1, B,2, B,3,B,4,每小时单产量如右表，求产值最大的分配方案,。,车间,B,1,B,2,B,3,B,4,工人,A,1,10,9,8,7,A,2,3,4,5,6,A,3,2,1,1,2,A,4,4,3,5,6,解,： 令,M,=max10,9,6=10,人数和事数不等的指派问题,3.4,指派问题,B,中有4个独立零元素，所以,为最优解，最大产值为z=10615=22。,若人数小于事数，添一些虚拟的“人”，此时这些虚拟的“人”做各件事的费用系数取为0，理解为这些费用实际上不会发生；若人数大于事数，添一些虚拟的“事”，此时这些虚拟的“事”被各个人做的费用系数同样也取为0。,【,例3.18,】,现有4个人，5件工作，每人做每件工作所耗时间如下表：,3.4,指派问题,工作,B,1,B,2,B,3,B,4,B,5,工人,A,1,10,11,4,2,8,A,2,7,11,10,14,12,A,3,5,6,9,12,14,A,4,13,15,11,10,7,问指派哪个人去完成哪项工作，可使总耗时最小？,解,：添加虚拟人A,5,，构造耗时矩阵,C,，,应用匈牙利法求解，得到最优解,X,，,最少耗时为,z,=2767=22。,一个人可做几件事的指派问题,3.4,指派问题,若某人可作几件事，则可将该人化作相同的几个“人”来接受指派。这几个“人”做同一件事的费用系数当然一样。,【,例3.19,】,对例3.13中的指派问题，为了保证工程质量，经研究决定，舍弃建筑公司,A,4,和,A,5,，让技术力量较强的建筑公司,A,1,A,2,A,3,来承建5家商店，其投标费用见右表。根据实际情况，允许每家建筑公司承建一家或两家商店，求使总费用最少的指派方案。,商店,B,1,B,2,B,3,B,4,B,5,建公,A,1,4,8,7,15,12,A,2,7,9,17,14,10,A,3,6,9,12,8,7,解,：由于每家建筑公司最多可承建两家新商店，因此，把每家建筑公司化作,A,i,和,A,i,(,i,=1,2,3)相同的两家建筑公司因而费用矩阵变为：,3.4,指派问题,上面的系数矩阵有6行5列，为了使“人”和“事”的数目相同，引入一件虚拟“事”，使之成为标准的指派问题，其效率矩阵为,C,应用匈牙利法求解，得最优解,X,，,总费用为,z,=74978=35（万元）。,某事不能由某人去做的指派问题,3.4,指派问题,某事不能由某人去做，可将此人做此事的费用取作足够大的,M,。,【,例3.20,】,分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每人完成各项任务的时间见下表。由于任务重，人数少，考虑：任务E必须完成，其它4项任务可选3项完成，但甲不能做A项工作，试确定最优分配方案，使完成任务的总时间最少。,工作,A,B,C,D,E,工人,甲,10,11,4,2,8,乙,7,11,10,14,12,丙,5,6,9,12,14,丁,13,15,11,10,7,解,：这是一人数与工作不等的指派问题，由于任务数大于人数，所以需要有一个虚拟的“人”，设为戊。因为甲不能做A，所以令甲完成工作A的时间为,M,；又因为工作E必须完成，故设戊完成E的时间为,M,，即戊不能做工作E，其余的假想时间为0，建立的效率矩阵为,C,最少的耗时数z=29203224=105。,3.4,指派问题,应用匈牙利法求解，得最优解,X,，,扩展性学习材料-,协同运输管理,协同运输管理（Collaborative Transportation Management，CTM）是一种在原有“供给商销售商”的合作关系上，扩展至“供给商发货人,第三方物流,收货商”的,战略联盟,，通过,信息,共享和供给链协作，制定计划、猜测、运输、,库存,等,商品,服务全过程的共同决策。,协同运输是近几年发展起来的现代物流模式，它使相对独立的运输企业协同运作，以达到减少车辆空载、降低运输成本和提高企业效率等目的。在传统运输模式下，各个运输实体独立完成自身运输任务，这将不可避免地产生大量的车辆空载行驶，从而导致运输成本增加。而多个运输企业实施协同运输，不同公司之间可以互相代为完成运输任务，则可以大量减少总体的运输空载。协同运输问题在小运量、车辆可混载的情况下属于多车场装卸运输问题(Multi-depot Pickup and Delivery Problem)；在车辆限定满载情况下，为多车场弧覆盖问题(Multi-depot Arc Routing Problem)。,2000年，全球最大,零售商,沃尔玛（WALMART）向供给商宝洁（PG）、货运巨头亨特提出了一个新型的合作方案，要在三者间实现更透明的信息交换，共同进行决策，这就是协同运输管理的开始。他们达成合作关系以后，沃尔玛大大减少了货物处理过程的步骤，而亨特减小了16的装卸货等待时间，空载率下降3，宝洁也实现了库存的下降。,计划经济学家康托洛维奇,利奥尼德康托洛维奇(L.V.Kantorovich， 19121986) ，苏联数学家，出生于俄国圣彼得堡的一个医生家庭。1930年毕业于列宁格勒大学，1934年成为该校最年轻的数学教授，1935年获该校数学博士学位，19481960年任列宁格勒科学院数学所研究室主任，1958年当选为苏联科学院通讯院士，并于1964年成为苏联科学院院士。19601971年任苏联科学院西伯利亚分院数学所副所长，19711976年任苏联国家科学技术委员会管理研究所室主任。1976年任苏联科学院系统分析所所长.他曾于1949年获斯大林数学奖，1965年获列宁经济学奖。康托洛维奇对经济学的贡献主要在于，他建立和发展了线性规划方法，并运用于经济分析，对现代经济应用数学的重要分支线性规划方法的建立和发展做出了开创性贡献。他把资源最优利用这一传统的经济学问题，由定性研究和一般的定量分析推进到现实计量阶段，对于在企业范围内如何科学地组织生产和在国民经济范围内怎样最优地利用资源等问题做出了独创性的研究。康托洛维奇的主要著作包括:生产组织和计划中的数学方法(1939年)，经济资源的最优利用(1959年)，经济最优决策(1972年，合著)，最优规划文集(1976年)等。因在创建和发展线性规划方法以及革新、推广和发展资源最优利用理论方面所做出的杰出贡献，与美籍荷兰经济学家库恰林库普曼斯(T.C.Koopmans， 19101985)一起分享1975年度诺贝尔经济学奖。,随后，康托罗维奇继续踏实地迈进，他发现一系列涉及如何科学地组织和计划生产的问题，都属于线性规划问题。比如，怎样最充分地利用机器设备，如何最大限度地减少废料，最有效地使用燃料，怎样最合理地组织货物运输，最适当地安排农作物布局等。,