运输问题及指派问题.pptx

本章知识结构本章知识结构第第 3 章章 运输和指派问题运输和指派问题本章教学目标与要求本章教学目标与要求 n n掌握产销平衡运输问题的数学模型及其特点掌握产销平衡运输问题的数学模型及其特点；n n掌掌握运输问题的表上作业法，包括初始调运方案的确握运输问题的表上作业法，包括初始调运方案的确定、检验数的计算、运输方案的调整方法定、检验数的计算、运输方案的调整方法；n n掌握产销不平衡运输问题转化为产销平衡问题的处理掌握产销不平衡运输问题转化为产销平衡问题的处理办法；掌握运输问题在实践中的典型应用办法；掌握运输问题在实践中的典型应用；n n 掌握标准指派问题的求解方法，会将各种非标准指派掌握标准指派问题的求解方法，会将各种非标准指派问题转化为标准指派问题问题转化为标准指派问题。导入案例导入案例 运储物流的运输问题运储物流的运输问题 运运输输成成本本占占物物流流总总成成本本的的35-50左左右右，占占商商品品价价格格的的4-10，运运输输对对物物流流总总成成本本的的节节约约具具有有举举足足轻轻重重的的作作用用。运运储储物物流流在在物物流流运运输输管管理理中中要要着着重重考考虑虑：运运输输方方式式的的选选择择，运运输输路线的选择，编制运输计划等问题。路线的选择，编制运输计划等问题。运运输输方方式式合合适适与与否否决决定定了了运运输输时时间间的的长长短短，决决定定了了成成本本的的高高低低，各各种种运运输输工工具具都都有有其其使使用用的的优优势势领领域域，对对运运输输工工具具进进行行优优化化选选择择，按按运运输输工工具具特特点点进进行行装装卸卸运运输输作作业业，最最大大限限度度地地发发挥挥所所用用运运输输工工具具的的作作用用；选选择择运运输输路路线线要要与与交交通通运运输输工工具具结结合合起起来来，尽尽量量安安排排直直达达运运输输，以以减减少少运运输输装装卸卸、转转运运环环节节，缩缩短短运运输输时时间间；编编制制运运输输计计划划还还要要从从全全局局出出发发，深深入入调调查查研研究究，综综合合平平衡衡，积积极极组组织织计计划划运运输输、合合理理运运输输、直直达达运运输输、均均衡衡运运输输，按照成本最低的原则来制定合理的计划按照成本最低的原则来制定合理的计划。3.1运输问题概述运输问题概述 运输问题的典型提法是将某种物质从若干个产地调运到若运输问题的典型提法是将某种物质从若干个产地调运到若干个销地，已知每个产地的产量和每个销地的销量，如何在许干个销地，已知每个产地的产量和每个销地的销量，如何在许多可行调运方案中选择一个总运费最少的调运方案。多可行调运方案中选择一个总运费最少的调运方案。根据总产根据总产量与总销量是否相等的数量关系，运输问题通常可划分为量与总销量是否相等的数量关系，运输问题通常可划分为产销产销平衡平衡（相等）和（相等）和产销不平衡产销不平衡（不相等）两大类别（不相等）两大类别。产销平衡的。产销平衡的运输问题主要在这一节介绍，产销不平衡的运输问题将在后面运输问题主要在这一节介绍，产销不平衡的运输问题将在后面节中讨论。节中讨论。3.1.1运输问题的引入运输问题的引入在生产、交换活动中，不可避免地要进行物资调运工作。在生产、交换活动中，不可避免地要进行物资调运工作。某时期内将生产基地的煤、钢铁、粮食、矿砂、木材等各类物某时期内将生产基地的煤、钢铁、粮食、矿砂、木材等各类物资，分别运送到需要这些物资的地区。资，分别运送到需要这些物资的地区。3.1运输问题概述运输问题概述【例例3.1】某物流公司从两个产地某物流公司从两个产地A1(内蒙内蒙)、A2(山西山西)将煤将煤炭运往三个销地炭运往三个销地B1(北京北京)、B2(山东山东)、B3(上海上海)，各产地的产，各产地的产量、各销地的销量、各产地运往各销地的每单位煤炭运费数据量、各销地的销量、各产地运往各销地的每单位煤炭运费数据见下表，问：应如何调运煤炭可使总运输费用最小？见下表，问：应如何调运煤炭可使总运输费用最小？销地销地产地产地B1B2B3产量产量A1646200A2655300销量销量150150200500解解：此为产销平衡的运输问题（总产量此为产销平衡的运输问题（总产量=总销量）。总销量）。设设xij为从产地为从产地Ai(i=1,2)运往销地运往销地Bj(j=1,2,3)的运输量的运输量,x11x12x13x21x22x23则该问则该问题的数学模型为题的数学模型为3.1运输问题概述运输问题概述该问题显然是该问题显然是一个线性规划一个线性规划模型，其系数模型，其系数矩阵矩阵A见下表见下表x11x12x13x21x22x23A=111产地产地约束约束11111销地销地约束约束11113.1运输问题概述运输问题概述x11x12x13x21x22x23A=111产地产地约束约束11111销地销地约束约束1111可以看出运输问题的系数矩阵有如下特征：可以看出运输问题的系数矩阵有如下特征：（1）共有）共有3+2行，分别表示各产地和销地；行，分别表示各产地和销地；32列，分别表列，分别表示各决策变量的系数列；示各决策变量的系数列；（2）每列只有两个）每列只有两个1，其余为，其余为0，分别表示只有一个产地和一，分别表示只有一个产地和一个销地被使用，由个销地被使用，由xij的行列下标所决定，这是运输问题表上作业的行列下标所决定，这是运输问题表上作业法的由来。法的由来。3.1运输问题概述运输问题概述3.1.2运输问题的数学模型运输问题的数学模型一般地，产销平衡的运输问题可以表述为：设有一般地，产销平衡的运输问题可以表述为：设有m个地点个地点（称为产地或发地）（称为产地或发地）A1,A2,Am的某种物资调至的某种物资调至n个地点个地点B1,B2,Bn（称为销地或收地），各个产地需要调出的物资量分（称为销地或收地），各个产地需要调出的物资量分别为别为a1,a2,am单位，各个销地需要调进的物资量分别为单位，各个销地需要调进的物资量分别为b1,b2,bn单位，且各个发点的供应量之和等于各个收点的需求单位，且各个发点的供应量之和等于各个收点的需求量之和。已知每个发点量之和。已知每个发点Ai到每个收点到每个收点Bj的物资单位调运价格为的物资单位调运价格为cij。现问如何安排调运，才能使总运费最小。现问如何安排调运，才能使总运费最小。3.1运输问题概述运输问题概述销地销地B1B2Bn供应量供应量产地产地A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnam需求量需求量b1b2bn 设设xij表示从表示从产地产地Ai运往销地运往销地Bj的运量，的运量，x11x12x1nx21x22x2nxm1xm2xmn 于是于是产销平衡运输问产销平衡运输问题的数学模型为：题的数学模型为：V:s.t.3.1运输问题概述运输问题概述c11x11c12x12c1nx1nc21x21c22x22c2nx2ncm1xm1cm2xm2cmnxmnb111a1111a2111am111b1111b2111bnC=XT=A=p11p12p1np21p22p2npm1pm2pmnA=b平衡运输问题模型写成矩阵形式为平衡运输问题模型写成矩阵形式为:3.1运输问题概述运输问题概述在实际问题建立运输问题模型时，还会出现如下一些变化：在实际问题建立运输问题模型时，还会出现如下一些变化：1）有时问题表面看不是运输问题，但其仍要求费用最低或）有时问题表面看不是运输问题，但其仍要求费用最低或要求目标函数（利润或营业额）最大化，仍可看成运输问题；要求目标函数（利润或营业额）最大化，仍可看成运输问题；2）当某些运输线路上的能力有限制时，模型中可直接加入）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束。（等式或不等式）约束。3.1.3运输问题的数学模型的特征运输问题的数学模型的特征运输问题是一类线性规划问题，其目标函数一般为求总运运输问题是一类线性规划问题，其目标函数一般为求总运费的极小值。根据线性规划的有关理论，如果它的最优解存在，费的极小值。根据线性规划的有关理论，如果它的最优解存在，一定可以在基可行解中找到，因而需先考察运输问题约束方程一定可以在基可行解中找到，因而需先考察运输问题约束方程组系数矩阵的秩组系数矩阵的秩r(A).定理定理3.1平衡运输问题模型的系数矩阵的秩平衡运输问题模型的系数矩阵的秩r(A)=m+n-1。运输问题是特殊的线性规划运输问题是特殊的线性规划，单纯形法仍适合于运输问题。，单纯形法仍适合于运输问题。为此还要了解运输问题基可行解的性质，为说明其基本可行解为此还要了解运输问题基可行解的性质，为说明其基本可行解的特征，引入的特征，引入闭回路闭回路的概念。的概念。3.1运输问题概述运输问题概述定义定义3.1在平衡运输问题的决策变量表中，凡是能够排列成在平衡运输问题的决策变量表中，凡是能够排列成下列形式的下列形式的xab,xad,xcd,xce,xst,xsb 或或xab,xcb,xcd,xed,xst,xat其中，其中，a,d,s各不相同；各不相同；b,c,t各不相同，称这些变量的集合为各不相同，称这些变量的集合为一闭一闭回路回路，并将上式中的决策变量称为该闭回路的顶点。，并将上式中的决策变量称为该闭回路的顶点。例如例如x13,x16,x36,x34,x24,x23；x23,x53,x55,x45,x41,x21等都等都是闭回路，这些决策变量就是闭回路的顶点。是闭回路，这些决策变量就是闭回路的顶点。B1B2B3B4B5B6A1x11x12x13x14x15x16A2x21x22x23x24x25x26A3x31x32x33x34x35x36A4x41x42x43x44x45x46A5x51x52x53x54x55x563.1运输问题概述运输问题概述根据闭回路可以看出其的一些明显特点，根据闭回路可以看出其的一些明显特点，闭回路是一个具闭回路是一个具有如下条件顶点格子的集合有如下条件顶点格子的集合：1）每一个顶点格子都是转角点；）每一个顶点格子都是转角点；2）每一行（或列）若有闭回路的顶点，则必有两个顶点；）每一行（或列）若有闭回路的顶点，则必有两个顶点；3）每两个顶点格子的连线都是水平的或垂直的；）每两个顶点格子的连线都是水平的或垂直的；4）闭回路中顶点的个数必为偶数。）闭回路中顶点的个数必为偶数。定理定理3.2对于产销平衡运输问题的闭回路来说，具有下面对于产销平衡运输问题的闭回路来说，具有下面结论：结论：1）该问题）该问题m+n-1个变量构成基变量的充要条件是这些变量个变量构成基变量的充要条件是这些变量不包含任何闭回路；不包含任何闭回路；2）给定一组基变量，那么从决策变量表中可找出唯一一）给定一组基变量，那么从决策变量表中可找出唯一一个从任意非基变量出发，经过基变量为顶点，又回到该非基变个从任意非基变量出发，经过基变量为顶点，又回到该非基变量的闭回路。量的闭回路。事实上，事实上，闭回路是一个简化的局部调运方案，闭回路是一个简化的局部调运方案，反映了全局调运方案是否最优反映了全局调运方案是否最优。定理。定理3.2给出了运输给出了运输问题基本解的重要性质，为寻求运输问题的基本可问题基本解的重要性质，为寻求运输问题的基本可行解提供了依据。与一般的线性规划问题有所不同，行解提供了依据。与一般的线性规划问题有所不同，产销平衡的运输问题总是存在可行解，且目标函数产销平衡的运输问题总是存在可行解，且目标函数值有界，故运输问题必有最优解。值有界，故运输问题必有最优解。3.2运输问题的表上作业法运输问题的表上作业法运输问题作为一类特殊的线性规划问题，在求解时仍可采用单纯运输问题作为一类特殊的线性规划问题，在求解时仍可采用单纯形法的计算步骤，但因为运输决策变量有两个下标，可以在单位运价形法的计算步骤，但因为运输决策变量有两个下标，可以在单位运价表和产销平衡表中进行基变量与非基变量的换基迭代，再加上运输问表和产销平衡表中进行基变量与非基变量的换基迭代，再加上运输问题模型系数矩阵的特征，早期的研究者们提出了专门针对运输问题的题模型系数矩阵的特征，早期的研究者们提出了专门针对运输问题的单纯形法单纯形法表上作业法表上作业法。表上作业法的表上作业法的主要步骤主要步骤：第一步第一步求一个初始基可求一个初始基可行解，即确定初始调运方案。行解，即确定初始调运方案。第二步第二步计算检验数并判计算检验数并判断是否得到最优解。若是则断是否得到最优解。若是则迭代停止；否则转下一步；迭代停止；否则转下一步；第三步第三步换基迭代换基迭代(即调整即调整运量运量)。选一个变量出基，对。选一个变量出基，对原运输方案进行调整得到新原运输方案进行调整得到新的调运方案，改进当前方案，的调运方案，改进当前方案，返回第二步，直至求出最优返回第二步，直至求出最优解为止。解为止。开始开始给出初始给出初始运输方案运输方案结束结束检验检验运输方案是否运输方案是否最优最优改进运改进运输方案输方案yesno(1)西北角法西北角法(2)最小元素法最小元素法(3)差值差值(Vogel)法法（1）闭回路法）闭回路法（2）位势法）位势法3.2运输问题的表上作业法运输问题的表上作业法3.2.1初始基可行解的确定初始基可行解的确定确定初始可行解常用的方法有确定初始可行解常用的方法有西北角法西北角法、最小元素法最小元素法和和差值差值（Vogel近似近似）法法。西北角法西北角法从产销平衡表的西北角（左上角）第一格开始，按集中供应从产销平衡表的西北角（左上角）第一格开始，按集中供应的原则，依次安排调运量，即分析对应产地和销地的供需数量关的原则，依次安排调运量，即分析对应产地和销地的供需数量关系，尽最大可能满足需求，若某行（列）的产量（销量）已满足，系，尽最大可能满足需求，若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去；接着从未被划线的运价中再找出则把该行（列）的其他格划去；接着从未被划线的运价中再找出西北角的方格，重复上述操作，如此进行下去，直至得到一个基西北角的方格，重复上述操作，如此进行下去，直至得到一个基本可行解。本可行解。【例例3.2】设某种产品有三个生产厂商设某种产品有三个生产厂商A1、A2、A3，联合供应，联合供应四个销地四个销地B1、B2、B3、B4，其供应量、需要量和单位产品的运，其供应量、需要量和单位产品的运输成本见下表，试求一调运方案。输成本见下表，试求一调运方案。销地销地产地产地B1B2B3B4供应量供应量A13113107A219284A3741059需求量需求量3656203.2运输问题的表上作业法运输问题的表上作业法西北角法确定出的初始调运方案为：西北角法确定出的初始调运方案为：由由A1B1运运3;A1B2运运4;A2B2运运2;A2B3运运2;A3B3运运3;A3B4运运6，方案的运输总费，方案的运输总费用为用为 最小元素法最小元素法3.2运输问题的表上作业法运输问题的表上作业法最小元素法是按照最小元素法是按照“最低运输成本优先集中供应最低运输成本优先集中供应”的原则，的原则，即运价最小的需求优先满足，即从单位运价中最小的运价开始确即运价最小的需求优先满足，即从单位运价中最小的运价开始确定供需关系，然后依次找单位运价的次小值，一直到给出初始基定供需关系，然后依次找单位运价的次小值，一直到给出初始基本可行解为止。最小元素法的基本思想是就近供应，每一次都要本可行解为止。最小元素法的基本思想是就近供应，每一次都要求找出单位运价表中最小的元素，在运量表内对应的方格填入允求找出单位运价表中最小的元素，在运量表内对应的方格填入允许取得的最大数，若某行（列）的供应量（需求量）已满足，则许取得的最大数，若某行（列）的供应量（需求量）已满足，则把运价表中该运价所在行（列）划去；再找出未划去的单位运价把运价表中该运价所在行（列）划去；再找出未划去的单位运价中的最小数值，一直进行下去，直至得到一个基可行解。中的最小数值，一直进行下去，直至得到一个基可行解。【例例3.3】求下表所给运输问题的初始调运方案。求下表所给运输问题的初始调运方案。由由A1B3运运7;A2B1运运3;A2B4运运6;A3B2运运5;A3B4运运2，方案的运输总费用为，方案的运输总费用为3.2运输问题的表上作业法运输问题的表上作业法最小元素法确定出的初始调运方案为：最小元素法确定出的初始调运方案为：销地销地产地产地B1B2B3B4供应量供应量A1121310117A2101214109A3141115127需求量需求量3578233.2运输问题的表上作业法运输问题的表上作业法【例例3.4】用最小元素法求例用最小元素法求例3.2运输问题的初始调运方案。运输问题的初始调运方案。销地销地产地产地B1B2B3B4供应量供应量A13113107A219284A3741059需求量需求量365620由由A1B3运运4;A1B4运运3;A2B1运运3;A2B3运运1;A3B2运运6;A3B4运运3，方案的运输总，方案的运输总费用为费用为最小元素法确定出的初始调运方案为：最小元素法确定出的初始调运方案为：3.2运输问题的表上作业法运输问题的表上作业法 差值法（差值法（Vogel法）法）差值法又称为伏格尔法。最小元素法只考虑了局部的运输费用最差值法又称为伏格尔法。最小元素法只考虑了局部的运输费用最小，有时为了节省某一处运费，可能会导致其他处运费很大，缺乏对整小，有时为了节省某一处运费，可能会导致其他处运费很大，缺乏对整个供需关系的考虑。差额法考虑产地和销地最小和次小运价的差额，如个供需关系的考虑。差额法考虑产地和销地最小和次小运价的差额，如果差额很大，就选最小运价先调运，不然就会增加总的费用。最小元素果差额很大，就选最小运价先调运，不然就会增加总的费用。最小元素法只考虑了局部的运输费用最小，有时为了节省某一处运费，可能会导法只考虑了局部的运输费用最小，有时为了节省某一处运费，可能会导致其他处运费很大，缺乏对整个供需关系的考虑。差额法考虑产地和销致其他处运费很大，缺乏对整个供需关系的考虑。差额法考虑产地和销地最小和次小运价的差额，如果差额很大，就选最小运价先调运，不然地最小和次小运价的差额，如果差额很大，就选最小运价先调运，不然就会增加总的费用。就会增加总的费用。差值法的差值法的步骤步骤如下：如下：1）算出单位运价表各行各列中次小元素和最小元素的差额；）算出单位运价表各行各列中次小元素和最小元素的差额；2）在差额最大的行或列中的最小元素处填上尽可能大的调）在差额最大的行或列中的最小元素处填上尽可能大的调运数（若几个差额同为最大，则可任取其一）；运数（若几个差额同为最大，则可任取其一）；3）这时必有一列或一行调运完毕，在剩下的运价表中再求）这时必有一列或一行调运完毕，在剩下的运价表中再求最大差额，进行第二次调运，直至最后调运完毕，就得到一个初最大差额，进行第二次调运，直至最后调运完毕，就得到一个初始调运方案。始调运方案。3.2运输问题的表上作业法运输问题的表上作业法【例例3.5】用差值法求例用差值法求例3.2的初始调运方案。的初始调运方案。销地销地产地产地B1B2B3B4供应量供应量A13113107A219284A3741059需求量需求量3656251301153276722108103.2运输问题的表上作业法运输问题的表上作业法【例例3.5】用差值法求例用差值法求例3.2的初始调运方案。的初始调运方案。销地销地产地产地B1B2B3B4供应量供应量A131131075 2A2192843 1A374105963需求量需求量3656由由A1B3运运5;A1B4运运2;A2B1运运3;A2B4运运1;A3B2运运6;A3B4运运3，方案的运输总费用，方案的运输总费用为为差值法确定出的初始调运方案为：差值法确定出的初始调运方案为：3.2运输问题的表上作业法运输问题的表上作业法3.2.2检验数的计算检验数的计算表上作业法计算检验数的方法有两种：一种是表上作业法计算检验数的方法有两种：一种是闭回路法闭回路法，另，另一种是一种是位势法位势法。闭回路法闭回路法根据单纯形法原理，要判断某个可行解是否为最优解，需要根据单纯形法原理，要判断某个可行解是否为最优解，需要计算非基变量的检验数。用闭回路法求检验数时，对于给定的调计算非基变量的检验数。用闭回路法求检验数时，对于给定的调运方案（基可行解），从非基变量运方案（基可行解），从非基变量xij出发作一条闭回路，并从出发作一条闭回路，并从xij开始将该闭回路上的顶点顺序编号（顺时针或逆时针均可），起开始将该闭回路上的顶点顺序编号（顺时针或逆时针均可），起点点xij为零，依此类推。称编号为奇数的点为奇点，编号为偶数的为零，依此类推。称编号为奇数的点为奇点，编号为偶数的点为偶点，则对应点为偶点，则对应xij的检验数的检验数ij等于该闭回路上偶点处单位运价等于该闭回路上偶点处单位运价的总和与奇点处单位运价的总和之差，即的总和与奇点处单位运价的总和之差，即ij=偶点处单位运价的总和奇点处单位运价的总和偶点处单位运价的总和奇点处单位运价的总和【例例3.6】求例求例3.4给出的可行解所对应的非基变量检验数。给出的可行解所对应的非基变量检验数。3.2运输问题的表上作业法运输问题的表上作业法销地销地产地产地B1B2B3B4供应量供应量A1311310743A21928431A374105963需求量需求量365601 1233.2运输问题的表上作业法运输问题的表上作业法销地销地产地产地B1B2B3B4供应量供应量A13113107143A21928431A374105963需求量需求量365601 1233.2运输问题的表上作业法运输问题的表上作业法销地销地产地产地B1B2B3B4供应量供应量A131131071243A21928431A374105963需求量需求量365601 123453.2运输问题的表上作业法运输问题的表上作业法销地销地产地产地B1B2B3B4供应量供应量A131131071243A219284311A374105963需求量需求量365601233.2运输问题的表上作业法运输问题的表上作业法销地销地产地产地B1B2B3B4供应量供应量A131131071243A219284311-1A374105963需求量需求量36561234503.2运输问题的表上作业法运输问题的表上作业法销地销地产地产地B1B2B3B4供应量供应量A131131071243A219284311-1A37410591063需求量需求量365612303.2运输问题的表上作业法运输问题的表上作业法销地销地产地产地B1B2B3B4供应量供应量A131131071243A219284311-1A3741059106 123需求量需求量3656注注：如果全部检验数均为正数或零，则调运方案一定为最优：如果全部检验数均为正数或零，则调运方案一定为最优方案；如果检验数中仍存在负数，则调运方案不是最优方案。方案；如果检验数中仍存在负数，则调运方案不是最优方案。位势法位势法3.2运输问题的表上作业法运输问题的表上作业法位势法的位势法的步骤步骤为：为：1）在产销平衡表中，即调运方案中增加）在产销平衡表中，即调运方案中增加ui行和行和vj列，但在相列，但在相应的基变量格（即数字格中）不是填写调运量，而是填写相应的应的基变量格（即数字格中）不是填写调运量，而是填写相应的运价，写在格的左上角；运价，写在格的左上角；2）令）令u1=0或或vn=0，根据式，根据式cij-(ui+vj)=0(其中其中xij为基变量为基变量)依一依一定次序计算和，将结果填写在表中；定次序计算和，将结果填写在表中；3）将非基变量的运价填入相应格的左上角，根据式）将非基变量的运价填入相应格的左上角，根据式ij=cij-(ui+vj)(其中其中xij为非基变量为非基变量)计算相应的检验数，将结果填入相应计算相应的检验数，将结果填入相应格，写在该格的右下角。格，写在该格的右下角。【例例3.7】应用位势法求例应用位势法求例3.4给出的初始可行解所对应的非给出的初始可行解所对应的非基变量的检验数。基变量的检验数。3.2运输问题的表上作业法运输问题的表上作业法销地销地产地产地B1B2B3B4uiA131131043A2192831A3741056 3vj3.2运输问题的表上作业法运输问题的表上作业法销地销地产地产地B1B2B3B4uiA1311310u1=043A21928u2=-131A374105u3=-56 3vjv1=2v2=9v3=3v4=103.2运输问题的表上作业法运输问题的表上作业法销地销地产地产地B1B2B3B4uiA1311310u1=0143A21928u2=-131A374105u3=-56 3vjv1=2v2=9v3=3v4=103.2运输问题的表上作业法运输问题的表上作业法销地销地产地产地B1B2B3B4uiA1311310u1=01243A21928u2=-131A374105u3=-56 3vjv1=2v2=9v3=3v4=103.2运输问题的表上作业法运输问题的表上作业法销地销地产地产地B1B2B3B4uiA1311310u1=01243A21928u2=-1311A374105u3=-56 3vjv1=2v2=9v3=3v4=103.2运输问题的表上作业法运输问题的表上作业法销地销地产地产地B1B2B3B4uiA1311310u1=01243A21928u2=-1311-1A374105u3=-56 3vjv1=2v2=9v3=3v4=103.2运输问题的表上作业法运输问题的表上作业法销地销地产地产地B1B2B3B4uiA1311310u1=01243A21928u2=-1311-1A374105u3=-5106 3vjv1=2v2=9v3=3v4=103.2运输问题的表上作业法运输问题的表上作业法销地销地产地产地B1B2B3B4uiA1311310u1=01243A21928u2=-1311-1A374105u3=-5106 123vjv1=2v2=9v3=3v4=10注注：闭回路法的主要缺点是当变量个数较多时，寻找闭回路：闭回路法的主要缺点是当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。当运输问题的产地与销地很多时，以及计算两方面都会产生困难。当运输问题的产地与销地很多时，空格的数目很多，用闭回路法计算检验数，要找很多的闭回路，空格的数目很多，用闭回路法计算检验数，要找很多的闭回路，计算量很大，而用位势法就简便得多。计算量很大，而用位势法就简便得多。3.2运输问题的表上作业法运输问题的表上作业法3.2.3闭回路的调整闭回路的调整当初始基本可行解非基变量的检验数出现负数时，便需换基当初始基本可行解非基变量的检验数出现负数时，便需换基迭代。具体迭代。具体步骤步骤如下：如下：1）若有两个和两个以上的负检验数时，一般选择其中最小）若有两个和两个以上的负检验数时，一般选择其中最小的负检验数，以它对应的空格为调入格，以此格为出发点，作一的负检验数，以它对应的空格为调入格，以此格为出发点，作一闭回路，并从该空格出发，沿闭回路，将各顶点依次编号，空格闭回路，并从该空格出发，沿闭回路，将各顶点依次编号，空格编号为编号为0。2）取奇点所在格中最小的运量）取奇点所在格中最小的运量(记为记为)，然后在闭回路中偶，然后在闭回路中偶点增加点增加、奇点减少、奇点减少，得出新的调整方案。，得出新的调整方案。说明说明：重新计算空格的检验数。如果所有的检验数都为正数：重新计算空格的检验数。如果所有的检验数都为正数或零，那么求出的就是最优解，不然，重复上述过程。或零，那么求出的就是最优解，不然，重复上述过程。【练习练习】应用闭回路调整例应用闭回路调整例3.4给出的初始可行解，并计算给出的初始可行解，并计算所对应的新的可行解非基变量的检验数。所对应的新的可行解非基变量的检验数。3.2运输问题的表上作业法运输问题的表上作业法销地销地产地产地B1B2B3B4供应量供应量A131131071243A219284311-1A3741059106 123需求量需求量365601 123 33.2运输问题的表上作业法运输问题的表上作业法销地销地产地产地B1B2B3B4供应量供应量A1311310752A21928431A37410596 3需求量需求量36563.2运输问题的表上作业法运输问题的表上作业法销地销地产地产地B1B2B3B4供应量供应量A131131070252A2192843211A374105996 123需求量需求量36563.3其他形式的运输问题其他形式的运输问题 产销平衡运输问题相当于线性规划的标准型，实际问题中经产销平衡运输问题相当于线性规划的标准型，实际问题中经常还会遇到一些其他的运输问题，解决的主要方法是将这些问题常还会遇到一些其他的运输问题，解决的主要方法是将这些问题都转化为产销平衡的运输问题。都转化为产销平衡的运输问题。3.3.1产销不平衡的运输问题产销不平衡的运输问题产销不平衡的运输问题分两类：一是供大于求的运输问题；产销不平衡的运输问题分两类：一是供大于求的运输问题；一是供不应求的运输问题。一是供不应求的运输问题。供大于求的运输问题供大于求的运输问题 供大于求的运输问题，即在供大于求的运输问题，即在aibj的情况下，求的情况下，求cijxij（总费用最少），就得供大于求的运输问题模型（总费用最少），就得供大于求的运输问题模型3.3其他形式的运输问题其他形式的运输问题3.3其他形式的运输问题其他形式的运输问题事实上，上面模型就是事实上，上面模型就是m个产地和个产地和n+1个销地的产销平衡运输个销地的产销平衡运输问题，相当于增加了一个问题，相当于增加了一个“虚拟虚拟”销地销地Bn+1，由于这个销地并不，由于这个销地并不存在，每个产地的剩余物资只能留在原产地，因此存在，每个产地的剩余物资只能留在原产地，因此Ai产地运到产地运到Bn+1的单位运价为的单位运价为cin+1=0，而这个销地的销量是，而这个销地的销量是bn+1。因而供大于。因而供大于求运输问题的求解思路是添加一个虚拟销地，转化为平衡运输问求运输问题的求解思路是添加一个虚拟销地，转化为平衡运输问题来处理。题来处理。3.3其他形式的运输问题其他形式的运输问题 供不应求的运输问题供不应求的运输问题 供不应求的运输问题，即在供不应求的运输问题，即在aibj的情况下，求的情况下，求cijxij（总费用最少），就得供大于求的运输问题模型（总费用最少），就得供大于求的运输问题模型3.3其他形式的运输问题其他形式的运输问题事实上，上面模型就是事实上，上面模型就是m+1个产地和个产地和n个销地的产销平衡运输个销地的产销平衡运输问题，相当于增加了一个问题，相当于增加了一个“虚拟虚拟”产地产地Am+1，其相应的产量是，其相应的产量是am+1。由于这个产地并不存在，因此。由于这个产地并不存在，因此Am+1产地运到产地运到Bj的单位运价的单位运价为为cm+1j=0。因而供不应求运输问题的求解思路是添加一个虚拟产。因而供不应求运输问题的求解思路是添加一个虚拟产地，转化为平衡运输问题来处理。地，转化为平衡运输问题来处理。【例例3.8】某公司在不同地区有某公司在不同地区有A1、A2和和A3三个工厂，产品将三个工厂，产品将运往运往B1、B2、B3和和B4四个地区，其单位运价表见下表，试建立产四个地区，其单位运价表见下表，试建立产销平衡的运输问题的数学模型。销平衡的运输问题的数学模型。3.3其他形式的运输问题其他形式的运输问题销地销地B1B2B3B4供应量供应量产地产地A161016860A21481612100A3206104120需求量需求量30208090220280解解：这是这是一个供大于求一个供大于求的物资调运问的物资调运问题，故增加一题，故增加一个虚拟的销地个虚拟的销地B5，需求量为，需求量为b5=280-220=60，令，令ci5=0(i=1,2,3)，该供需平，该供需平衡运输问题的数学模型为：衡运输问题的数学模型为：3.3其他形式的运输问题其他形式的运输问题实际上，上述模型相应的产销平衡运输表如下表所示，实际上，上述模型相应的产销平衡运输表如下表所示，该问该问题的最优调运方案为：题的最优调运方案为：销地销地B1B2B3B4B5供应量供应量产地产地A1610168060A214816120100A32061040120需求量需求量3020809060303020206060603.3其他形式的运输问题其他形式的运输问题3.3.2禁运与封锁的运输问题禁运与封锁的运输问题在实际的物资运输管理中常遇到以下情况，在实际的物资运输管理中常遇到以下情况，某种物资不能从某种物资不能从产地产地Ai运往销地运往销地Bj，或者销地，或者销地Bj不接收从产地不接收从产地Ai调入的物资，称调入的物资，称前者为前者为Ai对对Bj的禁运的禁运，后者为，后者为Bj对对Ai的封锁的封锁。造成禁运或封锁的因素造成禁运或封锁的因素很多，例如很多，例如Ai与与Bj之间没有运输线，或者由于自然灾害造成了原有交通运输线之间没有运输线，或者由于自然灾害造成了原有交通运输线的中断，这样就形成了的中断，这样就形成了Ai对对Bj的禁运；如果物资需通过铁路，航运运输，由于的禁运；如果物资需通过铁路，航运运输，由于运输能力有限，有关部门暂时禁止这批物资通过他们所管辖的路段，也人为地运输能力有限，有关部门暂时禁止这批物资通过他们所管辖的路段，也人为地造成了造成了Ai对对Bj的禁运；由于某经济原因，如质量问题或合同约束，销地的禁运；由于某经济原因，如质量问题或合同约束，销地Bj拒绝拒绝接收产地接收产地Ai的物资，从而形成的物资，从而形成Bj对对Ai的封锁。的封锁。禁运和封锁给物资运输管理工作带来的后果是在制定物资调禁运和封锁给物资运输管理工作带来的后果是在制定物资调运方案时，必须使物资从运方案时，必须使物资从Ai到到Bj的调运量为零。也就是说，在数的调运量为零。也就是说，在数学模型中要增加约束条件学模型中要增加约束条件xij=0，去掉这个约束条件使模型转化为，去掉这个约束条件使模型转化为运输问题的方法是：运输问题的方法是：将将Ai到到Bj的运价的运价cij修改为一个充分大的正数修改为一个充分大的正数M，从而使得任意一个含有，从而使得任意一个含有xij0的调运方案均不可能成为最优方案，的调运方案均不可能成为最优方案，这样在得到了相应的运输问题的最优调运方案时，约束条件这样在得到了相应的运输问题的最优调运方案时，约束条件xij=0自动地得到了满足，与线性规划的大自动地得到了满足，与线性规划的大M法相对应。法相对应。【例例3.9】供需双方在协商后签订了一个供货合同，合同规定供需双方在协商后签订了一个供货合同，合同规定供给方向六个地区（记为供给方向六个地区（记为B1,B2,B6）提供某种物资并负责物资）提供某种物资并负责物资的运输，同时规定的运输，同时规定B2和和B4的物资只能由产地的物资只能由产地A1或或A2调入，各地的调入，各地的供给量、需求量和单位运价由下表给出，试求满足合同要求的最供给量、需求量和单位运价由下表给出，试求满足合同要求的最优调运方案。优调运方案。3.3其他形式的运输问题其他形式的运输问题销地销地B1B2B3B4B5B6供应量供应量产地产地A1357923150A2132645180A3226346120需求量需求量7080401406060450解解合同要求合同要求B2和和B4的物资只能由的物资只能由A1或或A2供给，形成了供给，形成了B2和和B4对对A3的封锁。将的封锁。将c32和和c34改为改为M，见下表，见下表，3.3其他形式的运输问题其他形式的运输问题 应用表上作业法求解应用表上作业法求解该运输问题，得到最优调运方案如下：该运输问题，得到最优调运方案如下：销地销地B1B2B3B4B5B6供应量供应量产地产地A1357928150A2132645180A32M6M46120需求量需求量70804014060604501080604014