第3章-运输规划VIP

3.1运输问题概述,第3章运输规划,一般来说，运输问题是指：某种物资由m个发送点（发点）运往n个接收点（收点），已知各个发点的最大供给量（发量）、各个收点的需求量（收量），以及各发点向各收点的单位运价，如下表所示，在各收点收量达到满足的条件下，求总运费最低的运输方案的问题。,3.1.1运输问题及相关概念,若用xij表示从Ai到Bj的运输量，则运输方案如下表所示。根据总运费最小的目标及相关约束，可得其模型表示如下：,（各发点的发量约束）,（各收点的收量约束）,3.1.2运输问题的类型,根据实践应用中的具体情况，运输问题一般可以分为以下几种类型。（1）产销平衡的运输问题该类问题中总发量和总收量数值相等，且模型中发量约束和收量约束全部取等式。也简称为平衡运输问题，是运输问题的基本形式。（2）产销不平衡运输问题该类问题中总发量不等于总收量，具体又可以分为一般不平衡运输问题和复杂不平衡运输问题两种类型。一般不平衡运输问题是指：总发量不等于总收量，且模型的收量约束中不存在“型”的约束，具体包括产大于销和产小于销两种情况。复杂不平衡运输问题主要是指：总发量不等于总收量，且模型的收量约束中存在“型”的约束。实践中，复杂不平衡运输问题还有收点兼做发点，以及发点兼做收点等其它一些复杂情况，这些均不包括在本课程的讲述范围内。,3.1.3运输问题的特殊性,通过以上的描述不难看出，运输问题总体来说仍属于线性规划问题，此处单列出来讨论，是因为较之其它的线性规划问题，运输问题在模型结构上存在着显著的不同之处。平衡运输问题在实践中并不是常见的类型，但是由于其模型结构，在所有运输问题中相对简单、规范，便于研究与讨论；且其它类型的运输问题都可以通过某种方式转化为平衡运输问题。平衡运输问题便于讨论与构建求解方法，且通过问题类型的转换，所构建的解方法也可以在其它所有类型的运输问题上推广应用。因此，平衡运输问题被视为运输问题的基本形式。下面以平衡运输问题及其模型为基础，来具体讨论运输问题模型上的特殊性以及影响。例3-1问题背景：某公司的产品从两个产地A1、A2销往三个销地B1、B2和B3，已知各个产地的月额定生产能力、各个销地的月需求量（严格取表中数值），以及各产地向各销地运送产品的单位运费，如下表所示。,问题目标：应如何安排产品的运输计划，才能在每个销地每个月的产品需求达到满足的前提下，使总运输成本最低。通过分析建模，得该问题的运筹学模型如下：模型中总发量和总收量相等，所以在各个收量约束取严格等式时，各发,量约束也必然取严格等式，所以发量约束直接改写为等式约束。写出其系数矩阵如下：（1）系数矩阵的特殊性可以看出，系数矩阵的列数（变量个数）随着发点和收点个数呈积数态势增加，实践中一个稍具规模的运输问题，其系数矩阵便非常庞大。单纯形法计算中的大多数工作，是通过系数矩阵的迭代运算来完成的，如此庞大的系数矩阵，必然会带来单纯形表格绘制的困难，同时严重影响着单纯形法的整体计算效率。整个矩阵只有0和1两种元素，且每列均为两个1，在各个资源约束条件均为等式的前提下，用单纯形法去进行求解时，必须要添加大量的人工变,量，进一步增加了单纯形法的求解难度，求解效率也进一步被降低。模型中的资源约束条件总数为m+n个，但是在总发量等于总收量的前提下，其中有一个约束条件其实是多余的，因此系数矩阵的行向量之间其实是线性相关的，即：系数矩阵虽然是m+n行，但系数矩阵基的维数也即系数矩阵的秩却是m+n-1，这使得单纯形法求解时的难度与效率问题再次被加重。（2）最优解存在形式上的特殊性运输问题的特殊性还表现在最优解的存在形式上，运输问题的最优解存在形式只有唯一解和多重解两种，即至少存在一个最优解。目标函数是由单位运价和运输量组成的最小化目标，非负的极小化目标必然存在下界值0，所以不可能出现无界解的情况。若令平衡点的运输量为ai=bj=Q，则按下式所得的一组变量值，必为平衡运输问题的一个可行解。即：平衡运输问题一定存在至少一个可行解，不可能是无可行解。,3.1.4运输规划的提出,运输问题虽然总体来说，仍然属于线性规划问题的范畴，但鉴于上述所讨论的运输问题的特殊性，若将其视为普通的线性规划问题，在其模型的求解方面，便存在着求解难度大，求解效率低下的问题。随着社会与经济的发展，特别是伴随着物流业的兴起，运输问题越来越成为实践中一个经常性和重要性的问题；在线性规划的其它应用中，偶尔也会遇到和运输问题模型结构相同的一些特殊问题。因此，对于这些特殊的线性规划问题的求解，另寻其它更加有效的求解方法便成为一种必然需求。运筹学的实践中，将在模型结构上具有前述特殊性的所有线性规划问题，统称为运输问题，并将这些问题从线性规划中剥离出来，形成一支新的运筹学应用分支，即运输规划。其目的是，针对这类线性规划模型结构上的特殊性，研究并构建适用于这类模型的，专门的、更加有效的求解方法。,3.2平衡运输问题的表上作业法,（1）表上作业法的本质表上作业法是结合运输问题模型结构的特殊性，对单纯形法的一种改良算法。其基本原理以及基本流程和单纯形法相同，不同的只是其中的一些具体做法，主要表现在以下几个方面。初始基本可行解的获取，不再依靠初始基，从而避免的人工变量；最优性判断中，检验数的含义不变，但计算方法作了改进，避开了矩阵运算，使求解效率得到提高；基变换中的迭代运算，不再利用矩阵的初等变换运算，而是通过闭回路进行调整，同样回避了矩阵庞大的问题，使求解效率提高。（2）基本可行解的表格表示表上作业法中，基本可行解的表格表示不同于单纯形法，其表格如下：,3.2.1表上作业法概述,表格中间部分称为方案区，方案区的每一个格子对应一个变量，在格子的右上角标注单位运价，便于计算使用。值得注意的是，当表示基本可行解时，基变量所在格子里填入该变量的取值，无论是否为0；而非基变量所在的格子不填数值，即空格表示非基变量。由于有数字格表示基变量，从前述运输问题特殊性的论述可知，对于m个发点和n个收点的运输问题，表中有数字格的个数应为m+n-1。,（3）闭回路画法及概念闭回路的画法从方案表的某个空格开始，沿水平或竖直方向前进，在不走出方案区的前提下，路经有数字各格时，可以90度转向，也可以不转继续前进，在路经空格时，一定不能转向，最终回到出发点空格，所形成的闭合回路，就称为出发点空格的闭回路。如果方案表表示的是一个正确的基本可行解，则表中每一个空格都有且仅有一条闭回路，且从任何有数字格出发，都不可能找到闭回路。,闭回路的拐点及其编号闭回路上发生了方向转变的点，称为闭回路的拐点。拐点的编号方法是：以出发点（即空格所在点）为0号点，沿着闭回路依次顺序的给每个拐点进行编号。其中编号为偶数的拐点称为偶拐点；编号为奇数的点称为奇拐点。,3.2.2表上作业法的算法,（1）初始方案的编制确定初始基本可行解在表上作业法中，初始基本可行解的确定不再依赖初始基，常用的方法包括最小元素法、左上角法（西北角法）、伏格尔法等等。最小元素法基本思想：优先满足单位运费最低的需求。操作方法：包括以下四个相关的步骤a、在方案区未被直线覆盖的部分，选择单位运费最低的格子。b、在选中的格子里填入行值与列值中的较小者。其中：行值=选中格对应的发量-选中格所在行上已有物资量的总和列值=选中格对应的收量-选中格所在列上已有物资量的总和c、填入的数值若为行值，则划去所在行，为列值则划去所在列；如果行值与列值相等，则需要同时划去行和列，但必须在所划去的，行或列的任意一个空格内补填一个“0”。（此时所得到的基本可行解为退化解）d、重复ac直至方案区全部被直线覆盖，此时所得方案即初始方案。,例3-2用最小元素法编制下面平衡运输问题的初始方案。左上角法（西北角法）基本思想：优先满足最左上角（西北角）的格子的需求。操作方法：与最小元素法基本相同，只需将第a步改为：在未被直线覆盖的部分，选择最左上角（西北角）的格子，其它各步不变。因为最小元素法关注的只是局部最优，所以虽然每一步都是选单位运费最小的格子，但是所得方案并非最优，也就是说，是否选择单位运费最小的格子，和最优性无关，选择左上角的格子，识别效率更高。,20,20,0,15,30,15,伏格尔法无论最小元素法还是左上角法，都难免会遇到如下小的情况。定义：各行、各列中最小单位运费与次小单位运费的差额称为罚值。基本思想：优先满足罚值最大的行或列上，单位运费最小的格子。操作方法：与最小元素法基本相同，只需将第a步改为：在未被直线覆盖的部分，选择罚值最大的行或列上，单位运费最小的格子，其它不变。例3-3用伏格尔法编制下面平衡运输问题的初始方案。,20,20,0,45,0,15,（2）最优性判断检验数的含义表上作业法中，各变量（也即各个格子）的检验数的含义并没有变，仍然是指：在目标函数只含非基变量时，各变量的系数。从数值上来说基变量（有数字格）：检验数恒为零非基变量（空格）：检验数的数值代表了，该非基变量（空格）作单位数值的变化，所能引起的目标函数值的变化。数值的闭回路法计算在表上作业法中，空格数值的变化，其实是沿着其闭回路，从0号拐点开始，在闭回路的偶、奇拐点间作一加一减的波浪状的传递，最后重新使方案达到平衡，而最终完成的。（此处可以结合板书举例）由此，结合检验数的含义，不难得到空格的检验数的计算公式为：ij=空格(i,j)闭回路上偶拐点单位运费总和-奇拐点单位运费总和这种算法的缺点是：当空格数较多时，由于每个空格都要先画闭回路才能计算，所以计算工作量较大；但是它与的含义结合紧密。,上表中，若空格(1,2)的数值由0变为1，为了保持该行运输量平衡，则需要将闭回路号拐点的运输量减少1，同时需要将拐点运输量增加1，来保持第四列运输量平衡，同理号拐点的运输量需要减少1，才能保持第二行的物资平衡，到此，空格(1,2)数量增加1的变化才算最终完成。从而，空格(1,2)数值的这一单位数值的变化，所引起的目标函数的变化（即它的值）为：12=5-7+6-2=(5+6)-(7+2)=2其含义为：非基变量x12数值每增加1，则目标函数值增加2。,数值的位势法计算（对偶变量法）假设u1,u2,um是与m个发量约束相对应的对偶变量，v1,v2,vn是与n个收量约束相对应的对偶变量，则由对偶问题的经济性质（影子价格）可知：ij=cij-(u1,u2,um,v1,v2,vn)Pj又由前述运输问题系数矩阵的特点可知，变量xij的系数列向量里，只有第i和第j个元素是1，其他都是0，从而可得：ij=cij-(ui+vj)从而，只要能计算出ui和vj的数值，便可以计算所有的检验数了。已知有数字格的值为0，带入计算式ij=cij-(ui+vj)中，便可得到m+n-1个关于ui和vj的方程，但是ui加vj总共是m+n个未知量，若再给ui加vj中任意一个变量赋任意一个初始值，这样便可以构成一个变量和方程数都是m+n的线性方程组，解方程组便可得到所有的ui加vj值。由于ui加vj中，任意一个变量的初始值无论怎么赋，最终所求得的数值都一样，所以该方法又被称为位势法，与势能特性相仿。位势法（对偶变量法）的表格算法的基本步骤如下：,a、绘制如下的位势表，将当前方案表中有数字格的单位运费，填入位势表的相应格子里，并加括弧。b、令u1=0，利用有数字格值为0以及计算式ij=cij-(ui+vj)，直接在计算所有ui和vj的值，即ui和vj的和等于它俩交会处的，括弧中的数值。c、再次计算式ij=cij-(ui+vj)，以及上面已经算出的ui和vj的值，计算所有空格的检验数，并将结果填入表中相应的格子里。最优性判断方法若所有空格的值均为非负，则当前目标值达到最小值，当前方案为最优方案，否则为非最优。此时，若存在某个空格的值为0，则为多重最优解。,（3）方案调整基变换确定调整对象确定入基变量由值的含义可知，当某个空格的值为负，则沿革它的闭回路作运输量调整，目标函数值必然减小，所以选择调整对象（入基变量）的原则为：选负值中的最小者所对应的空格，作为调整对象（入基变量）。确定最大调整量确定出基变量因为空格运输量发生变化，必然会导致其闭回路上所有奇拐点的运输量减少，所以，允许的最大调整量，即奇拐点上的最小运输量，否则，下一个方案中最小运输量所在的格子必出现负数（不可行）。调整后，奇拐点上运输量最小的格子变为0值，即它就是出基变量，又非基变量用空格表示，所以调整后，0不用填入表中。闭回路法完成方案调整确定最大调整量后，在闭回路的所有偶拐点处加上最大调正量；在所有奇拐点处减去最大调整量，便完成了方案的调整。新方案再返回到（2），进行最有性判断。值得注意的是，调整后0的填写方法。,由上一步位势表可知21=-10，即当前方案非最优。选空格(2,1)作为调整对象，画出其闭回路并进行拐点编号如图所示。奇拐点上两个量相等，都是最小值15，所以调整量取15。按照“偶加奇减”的原则调整得如下方案。,调整后，两个奇拐点的运输量都变为了0，但是出基变量只有一个，所以两处中，必须有一处要填上0，表示它是一个等于0的非基变量。对调整后的新方案，画位势表，计算空格检验数如下。可见，此时表中所有空格的检验数均为非负数，即当前方案已经为最优方案，按此方案进行运输时，最小总运输费用为：Minz=457+158+202+204=555从最优方案的位势表可见，不存在空格的检验数为0，所以此时的最优运输方案，是该运输问题唯一的总费用最小化运输方案。,3.3非平衡运输问题的解法,（1）供大于销的问题指总发量大于总收量，收量约束中不存在“型”约束的运输问题。其求解方法包括如下几个步骤：添加一个虚拟收点，令其收量等于总发量与原总收量的差额；各实发点与虚收点间的单位运费按如下方法确定：A、剩余时不产生任何损失，则该发点到虚收点的单位运费为：零；B、剩余时产生一定的损失，该发点到虚收点单位运费：单位损失费；C、剩余时会产生巨大的损失，或者指令性要求该发点发量必须全部发出，则该发点到虚收点的单位运费为：M；表上作业法求解，最优方案中，虚收点对各实发点的物资接收量，表示对应发点，在总运输费用最小化时的物资剩余量。,3.3.1一般非平衡运输问题的解法,例3-4将下面的非平衡运输问题，转换为平衡运输问题。已知三个发点的情况：A1如果有剩余的话，单位剩余物资会造成损失7；A2的剩余物资没有任何损失；指令性的要求A3必须全部发出。则，问题转化为平衡运输问题后如下表所示：,（2）供小于销的问题指总发量小于总收量，收量约束中不存在“型”约束的运输问题。其求解方法包括如下几个步骤：添加一个虚拟发点，令其发量等于原总发量与总收量的差额；虚发点与各实收点间的单位运费按如下方法确定：a、缺货时无损失，可以无条接受件最大限度的缺货，则虚发点到这样的收点的单位运费为：零；b、缺货时有一定的损失，在供方给予相应的补偿后，可以接受最大限度的缺货，则虚发点到这样的收点的单位运费为：单位补偿费；c、缺货时损失巨大，完全不能接受缺货，或者指令性要求其需求必须满足，则虚发点到这样的收点的单位运费为：M；表上作业法求解，最优方案中，虚发点向各实收点发送的物资量，表示对应收点，在总运输费用最小时的缺货量。允许的缺货量有限时，约束表现为“型”，在复杂问题中讨论。,例3-5将下面的非平衡运输问题，转换为平衡运输问题。已知三个收点的情况：B1如果缺货，每缺1个会造成12的损失，发货方答应全额补偿；B2缺货时不会造成任何不利影响；B3缺货损失太大，不允许缺货。则，问题转化为平衡运输问题后如下表所示：,3.3.2复杂非平衡运输问题的解法,此处的复杂非平衡运输问题仅指收量约束中有“型”约束的问题。例3-6将下面的非平衡运输问题，转换为平衡运输问题。（1）确定无上限需求点的可能最大获取量在该类运输问题中，往往有些收点只表明了最低需求量，而并无明确的收量上限。此时，为了便于转换为平衡运输问题，需要确定其可能的最大获取量，用来等效的表示其需求的上限值。某收点的最大可获取量=总发量-其它各点需求量下限值之和,本例中B4的需求上限可以认为是：(45+55+30)-(15+10+0)=105（2）确定最大总需求当用最大可获取量代表无上限需求点的需求上限后，表中每个收点的需求便都具备了上限值，此时，将所有上限值加起来，即为最大总需求。本例中，最大总需求=15+20+20+105=160（3）添加虚拟发点最大总需求便是用来转换为平衡运输问题的平衡点运输量，次量一般大于总发量，所以转换时需要添加虚拟发点，并令其发量为：虚发点的发量=最大总需求-总发量本例中，虚发点A4的发量：a4=160-130=30（4）虚发点到各实收点的单位运费虚发点到各实收点的单位运费，分为以下三种情况：当某个收点的收量为严格的确定数值时，虚发点到该类收点的单位运费为：M，表示不接收来自虚发点的物资量，从而保障需求实现。（如B1）,当某个收点的收量下限值为零时，虚发点到这类收点的单位运费分为两种情况：当缺货不存在损失赔偿时为0；当缺货存在损失赔偿时为单位赔偿费。虚发点发往该点的物资量，即为缺货量。（如B3）当某个收点的收量下限值不为零时，为了便于问题的处理，将该收点按需求量分解为两个组成部分（在表格里表示为两个收点）：需求下限部分：用原编号表示，该部分的收量为需求量上限值，虚发点到该部分的单位运费为：M；上下限差额部分：用原编号加撇号表示，该部分的收量为需求量上下限的差额，虚发点到该部分的单位运费为：0。如本例中，将B2分解为B2和B2，B2的收量为10，与虚发点间的单位运费为M，B2的收量为10，与虚发点间的单位运费为0。（5）利用表上作业法求解经过上述四个步骤的处理，问题已经转变为平衡运输问题，利用表上作业即可实现问题的求解。最优方案中，虚发点给各个实收点的所发送的物资量，表示各个收点相对与需求上限的不足量（缺货量）。,其中第（4）步可以总结如下表所示：例3-6最终转换为平衡运输问题的方案表如下：,3.4运输问题应用举例,例3-7问题背景：某柴油机生产厂按合同规定，须于当年的每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如下表所示。又每个季度生产的柴油机并不一定在当季交货，如果当季不交货，每台柴油机每积压一个季度，需储存、维护等费用0.15万元。问题目标：要求在完成合同的情况下，作出使该厂全年生产费用(包括储存、维护费用等)最小的最优生产与经营决策。,解：由于每个季度生产出来的柴油机不一定当季交货，所以令xij为第i个季度生产的，用于第j个季度交货的柴油机数。根据