运筹学 第2版 课件 第4章-运输问题

6/26/2025第4章运输问题1

例4.1

某饮料在国内有三个生产厂，分布在城市A1、A2、A3，其一级承销商有四个，分布在城市B1、B2、B3、B4。已知各厂的产量、各承销商的销量，以及从Ai到Bj的每吨饮料运费如下表4.1所示（其中Ai与Bj交叉格中的数字即为从Ai到Bj的单位运价）。为发挥集团优势，公司统一筹划运输问题以寻求总运费最小的调运方案。4.1运输问题的建模（1）问题的提出6/26/202524.1运输问题的建模6/26/20253解：这里规划调运方案就是要决策从产地到销地的运输量，因此是问题的决策变量。问题的优化目标是所有运输线路总运费最小，即各线路的运输量受到来自产地和销地的两类约束。其中，产地运出总量不大于产量是客观限制；销地运入总量不大于销量是经济性要求。在本例中，由于总产量（供应量）S=16+10+22=48，总销量（需求量）D=8+14+12+14=48，是供需平衡的，因此应将所有产地的产品运出才能满足需求，并且此时所有销地的需求恰好被满足。4.1运输问题的建模6/26/20254所以，产地和销地的两类约束可分别写为：

02运输问题的一般模型（2）运输问题的一般模型4.1运输问题的建模6/26/20255本章讨论的经典运输问题就是假设有某种货物，需要从多个产地（SupplyPoint）调运到多个销地（DemandPoint），如何确定每条线路上的运输量以使得总运费最小。该问题具体描述如下：若已知某种货物有m个产地A1，A2，…，Am，每个产地的货物供给量分别为a1，a2，…，am；并且有n个销地B1，B2，…，Bn，每个销地的货物需求量分别为b1，b2，…，bn。将货物从Ai运到Bj时，运输费用的单位价格（运价）为cij，i=1，…，m；j=1，…，n。请制定一个调运方案，使得在充分满足各个销地需求的条件下总运费最少。02运输问题的一般模型4.1运输问题的建模6/26/20256运输问题的相关信息可以概括地表示为一张运价和供需的关系表，参见表4.2。在该表中，最右边的一列为各产地的产量，最下面的一行为各销地的销量。表格的中间部分为从各产地到各销地的单位运价。表4.2运价和供需关系表的一般形式图4.1运输问题的示意图02运输问题的一般模型4.2运输问题的一般模型4.1运输问题的建模6/26/20257运输问题还可用网络示意图来表示，如图4.1。该网络图有两个显著的特点：第一、所有的节点分为两种不同类型（产地节点和销地节点）；第二、有向边都是从产地节点发出并指向销地节点的。从例4.1的分析中可知，运输问题的约束包括三类：产地约束、销地约束和非负约束。产地约束反映了产地节点的运出量与产量（供给量）之间的关系，而销地约束反映了销地节点的运入量与销量（需求量）之间的关系。所有产地的总供给量所有销地的总销售量设为从产地Ai运到销地Bj的运量。根据供需关系可以将运输问题分为三种类型：1）供需平衡的物资调运问题，S=D总供给等于总需求。当供需平衡时，每个产地的物资可全部运出，每个销地的需求都可以得到满足，因此供需平衡的物资调运问题的数学模型为：02运输问题的一般模型4.1运输问题的建模6/26/20258

02运输问题的一般模型4.1运输问题的建模6/26/202592）供大于求的物资调运问题，S>D总供给大于总需求时，有些产地的物资不能全部运出，数学模型改为：4.1运输问题的建模6/26/2025103）供不应求的物资调运问题，S<D总供给小于总需求时时，数学模型为：4.1运输问题的建模6/26/202511将不平衡的供需关系配平注：缺啥补啥，来配平。4.1运输问题的建模6/26/202512例3.2

某公司在不同地区有三个工厂，产品将运往四个地区销售。已知各线路的单位运输成本和供需关系见下表，请写出物资调运问题的数学模型，并转化为供需平衡的表格形式。解：（略）4.1运输问题的建模6/26/202513表4.3运价与供需关系表解：从总产量与总销量的关系可知，这是一个供大于求的运输问题。设从产地

4.1运输问题的建模6/26/202514运往销地

的产品运输量为

，那么该运输问题的线性规划模型为：

解：4.1运输问题的建模6/26/2025

表4.4运价与供需平衡表以上讨论说明运输问题是一类具有特殊结构的线性规划。供需平衡的物资调运问题是运输问题的基本问题，因为可以将供过于求/供不应求的运输问题通过增加虚拟的销地/产地转化为供求平衡的运输问题。运输问题的特征体现在它的技术系数矩阵A中各元素仅可取值为1或0，且对应于决策变量的系数列向量，只有第i个和第m+j个分量取值为1，其余分量的取值均为0，即这里，表示仅在第k个分量取值为1的m+n维单位列向量。4.1运输问题的建模6/26/202516m行n行系数矩阵的特殊结构决定了平衡运输问题具有以下三个性质。4.1运输问题的建模6/26/2025174.1运输问题的建模6/26/202518

（2）运输问题一定存在有限最优解。对于平衡运输问题4.2，若令

，其中

，则可验证该组取值就是一个可行解。这说明运输问题的目标函数值有下界，不会趋于

。因此，运输问题必有有限最优解。

4.1运输问题的建模6/26/202519

幺模矩阵的一个重要性质就是对于约束方程组

，其所有的基本可行解都是整数。

这一性质使得运输问题的求解可以不必考虑决策变量xij是否有整数约束，即可以采用标准的线性规划方法求解。

1、运输问题中任意m+n个决策变量的系数列向量都是线性相关的。可以进一步证明，运输问题的基变量的个数为m+n-1。如果我们能得到决策变量的m+n-1个线性无关的系数列向量，就得到一个相应的基可行解。2、运输问题必存在最优解。（课后思考，为什么？）3、如果运输问题中的所有供给量和需求量都为整数，则该问题的任意基可行解均为整数解。这时不必考虑整数约束运输问题的主要特征：4.1运输问题的建模6/26/202520定义4.1

凡是能排列成（其中互不相同，互不相同）形式的变量集合，称为一个闭回路，其中诸变量称为这个闭回路的顶点。图4.3闭回路辨析图（3）运输问题的基本定理4.1运输问题的建模6/26/202521闭回路的几何特征：1、每一个顶点格子都是90°转角点；2、每一行（或列）若有闭回路的顶点，则有两个顶点；3、每两个顶点格子的连线都是水平的或垂直的；4、闭回路中顶点的个数必为偶数。闭回路的代数性质：性质4.1

构成闭回路的变量组对应的列向量组必线性相关。4.1运输问题的建模6/26/202522性质4.2

若变量组中有一个部分组构成闭回路，则该变量组对应的列向量组是线性相关的。推论：若变量组对应的列向量组线性无关，则该变量组一定不包含闭回路。该推论可以用反证法和性质3.2得到。定义4.2在变量组中，若有某一个变量xij

是它所在的行（第i

行）或列（第j

列）组的一个孤立点。4.1运输问题的建模6/26/202523性质4.3若一变量组中不包含任何闭回路，则该变量组必有定理4.1变量组孤立点。对应的列向量组线性无关的充要条件是该变量组中不包含任何闭回路。4.1运输问题的建模6/26/202524既然运输问题是线性规划问题，当然可以直接用单纯形法求解。但运输问题变量较多（如有20个产地50个销地的运输问题就有20×50＝1000个变量，直接求解效率不高。是一种根据运输问题的特殊结构进行优化的单纯形法，可以显著而表上作业法就提高解题效率。其求解步骤也分为确定初始基可行解、最优性判别和改善基可行解这三个主要步骤。4.2运输问题的表上作业法6/26/202525

01确定初始基可行解（1）

确定初始基本可行解6/26/2025261）西北角法西北角法（NorthwestCornerMethod）优先满足表中未划去部分的左上角（西北角）空格的供销需求。其目的只是找初始基可行解，不考虑优化。为了在供求平衡表的基础上，同时标注求解过程中所需的其他信息，将Ai和Bj的交叉格（Ai，Bj）中的运价cij放在该格的右上角，在该格子的左下角标注从Ai到Bj的线路的其他信息。01确定初始基可行解（1）

确定初始基本可行解6/26/202527例4.3试运用西北角法给出例4.1的初始可行方案。解：该运输方案的总成本z=512（1）

确定初始基本可行解6/26/202528

Step1.找出目前未划去的最小运价，设为cst①若产地余量>销地余量，则销地上运满，填xst=销地的余量，划去第t列；②若产地余量<销地余量，则产地全运出，填xst=产地的余量，划去第s行；③若产地余量=销地余量，填xst=产地/销地的余量；因为同时满足了产地和销地的要求，同时划去第s行和第t列。还要在同时划去的第s行、第t列的任一其他空格添加一个0。Step2.重复step1直至，所有运价都划去。

2）最小元素法基本步骤：（1）

确定初始基本可行解6/26/202529例4.4试运用最小元素法给出例4.1的初始可行方案。解：其计算结果如表4.6。表4.6最小元素法的供求平衡表（1）

确定初始基本可行解6/26/202530最小运价法的不足图4.4一个简单的运输模型最小元素法可得:x11=1，x12=1，x22=2，总成本25；可是令x21=1，x12=2，x22=1，总成本20。可见，当只考虑最小运价线路的充分利用，而导致运价较小的线路（如该例中A2与B1，A1与B2之间线路）不能合理利用。（1）

确定初始基本可行解6/26/2025313）伏格尔（Vogel）法伏格尔法优先满足未划去部分各产地（销地）运出（运入）次小运价与最小运价的差值最大者的最小运价线路的物资调运。这种方法能一定程度地减少只顾使用最小运价线路，而导致某产地或销地的最大次小运价线路上运输量的增加导致的成本增加。例如，对图4.4模型可以列出供求平衡表，如表4.7。（1）

确定初始基本可行解6/26/202532表4.7图4.4模型的伏格尔法供求平衡表（1）

确定初始基本可行解6/26/202533例4.5

试运用伏格尔法给出例4.1的初始可行方案。（1）

确定初始基本可行解6/26/2025解：34如同一般目标函数最小化的线性规划一样，最小运输成本问题的基可行解是否最优可以根据非基变量检验数是否全部非负来判断。基本有闭回路法和对偶变量法这两种方法。1）闭回路法对每一个空格（非基变量）找从其出发，其余点为数字格（基变量）的闭合回路。具体操作为：从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有碰到代表基变量的填入数字的格子才能向左或向右转90°（当然也可不改变方向）继续前进，这样继续下去，直至回到出发的那个空格。02最优性检验（2）

最优性检验6/26/202535由此形成的封闭的折线构成的闭回路。一个非基变量存在惟一的闭回路。令该非基变量变为1，相应调整闭合回路上各个格子的运量，求出的总运输费用的增量就是该非基变量的检验数。当一个原非基变量xij变为1，其余基变量不变，（2）

最优性检验6/26/202536例4.6试对例4.4用最小元素法求出的初始可行解进行最优性检验解：因为非基变量x24的检验数为负数，所以该方案不是最优方案。

表4.9闭回路法检验数检查表（2）

最优性检验6/26/2025372）对偶变量法（位势法）有m个产地和n个销地的产销平衡的调运问题的对偶问题如下：对于一个基B，令（2）

最优性检验6/26/202538由于基变量的检验数为零，对于m+n-1个基变量xij有：为求出m+n的变量，可任意令（相当于划去第行），解出其余这样就可以用对偶变量来求所有非基变量的检验数是否非负。若都满足，则最优，否则还不是最优，还要改善可行方案。（2）

最优性检验6/26/202539表4.10对偶变量法检验数表由于，所有非基变量的检验数非负，所以该方案是一个最优解。例4.7试检验例3.1中伏格尔法的解得到的运输方案的最优性。（2）

最优性检验6/26/202540在所有为负值的检验数中，选其中最小的负检验数，以它对应的非基变量为入基变量，然后以该非基变量所在格为出发点作一个闭回路。该原非基变量的运量的调整值等于闭回路顶点的序号中，所有偶数序号的顶点的调运量的最小值。同时，对闭回路中偶数/奇数序号顶点减/加该调整量，以保证产销平衡。

（3）

改进的运输方案6/26/202541例4.8试用闭回路法调整例4.1中最小元素法得到的可行方案。可以进一步验证调整后的方案是最优方案。（3）

改进的运输方案6/26/202542表4.11闭回路法供需平衡表1）无穷多最优解当某个非基变量的检验数为0时，该问题有无穷多最优解。如表3.10中x11的检验数为0，表示该例有无穷多最优解。只要把检验数为0的非基变量x11作为入基变量，调整运输方案，就可得到另一个最优方案。从出发，找到闭合路（4）

特殊情况的处理6/26/202543为了产销平衡调整闭回路中其他变量的值，;其余变量不变。详见表3.13。表4.12另一最优解（4）

特殊情况的处理6/26/2025442）退化有两种情况会出现某个基变量为零的退化情况。在用划线法确定初始基可行解时，若某选择的基变量所在格对应的产地余量和销地余量恰好相等。这时该基变量=产地余量，对应产地和销地都已平衡。但为了保证划线法每确定一个基变量划一线的原则，应先划去对应产地所在行/销地所在列，再在销地所在列/产地所在行的其它格中任选一个填0作为退化的基变量，最后再划去其所在的列/行。（4）

特殊情况的处理6/26/202545当用闭回路法调整时，出现回路中偶数节点格中有多于1个等于最小值。这时入基变量取该最小值，导致有多个原基变量变为0。这时，只能选其中任一个为0的原基变量出基，而其余的作为退化的基变量必须在其所在格中填0，以保证基变量的个数不变。03改进运输方案（4）

特殊情况的处理6/26/202546例4.9北方的某汽车制造集团企业有三个组装厂，即A工厂、B工厂、C工厂，每年分别需要生活用煤和取暖用煤2000t，1000t，3000t，由山西省大同、阳泉两处煤矿负责供应。这两处煤矿的价格和质量都基本相同。两处煤矿能供应该化工企业的煤的数量，山西阳泉为4000t，山西大同为1500t，由煤矿至该化工企业的单位运价（百元／t）如表4.13所示。由于供不应求，经企业领导研究平衡决定A工厂供应量不少于1500t，B工厂需要量应全部满足，C工厂供应量可减少300t。试求：总运费为最低的调运方案。01需求可变的运输问题4.3几种特殊的运输问题（1）需求可变的运输问题6/26/202547表4.13煤矿运价表(单位:百元/吨)解：主要步骤（1）判断供需关系（2）分析各销地的刚性、柔性需求（3）列出供需平衡表4.3几种特殊的运输问题6/26/202548表4.14供需平衡与运价表拓展思考：（1）若C工厂为了能争取到更多的煤，声称有多少煤都愿意买下，则如何写出这种情况下的供需平衡及运价表。（2）若大同到C工厂的运输线路因泥石流被破坏，则需要如何调整供需平衡及运价表。4.3几种特殊的运输问题6/26/202549其中，cij

为从i点运到j点的单位运价，si为发点i的供应量，dj为收点j的需求量。

图4.5转运问题的网络图（2）转运问题4.3几种特殊的运输问题6/26/202550转运问题（TransshipmentProblem）将节点分为产地（发点）、销地（收点）和转运点。其中，任何节点都可以承担转运功能。转运点的运出量等于运入量。发点的运出量大于运入量。收点的运入量大于运出量。因此，转运问题关于运输节点的约束也相应分为发点约束、收点约束以及转运点约束。（2）转运问题4.3几种特殊的运输问题6/26/202551运输问题模型是在经济管理中有着广泛应用的重要模型。因为与一般的线性规划相比运输问题模型在变量个数相同的条件下，表上作业法较单纯形法简单有效，所以，常常尽可能地将一些线性规划问题化为运输问题的模型。一些管理问题直接可体现为供给和需求的形式，如按合4.4运输问题的应用举例6/26/2025同生产的生产计划问题等。52例4.12某集团公司为降低设备采购的成本，对生产设备实行集中采购。采购部门计划通过招标采购某种生产设备。共邀请了m家工厂来参加投标。假设各厂家提供的是同质产品。每个厂家都提供了一份标书，在标书中注明了该厂单位产品的价格和按此价格所能提供的数量，设为ai。该采购部门将这些产品运往不同的n个地区的子公司，第j个地区的设备需求量为bj，运输费用由该采购部门支付。根据这些标书，该部门应该向哪些厂家订货，订货量各为多少？（1）

投标裁决问题6/26/202553从第i个厂家订货并往到第j个地区时的单位产品成本，cij。设决策变量xij为从第i个厂家订货后运至第j个地区的订货量，（i=1，…，m；j=1，…，n）。

解：（1）

投标裁决问题6/26/202554例4.13某数码产品制造公司有3个分厂，生产A、B两种数码产品。生产方式分为正常生产和加班生产两种，加班生产成本大于正常生产成本。现要制定两个月的工作计划：第一月A、B产品的需求量分别为200和600件，第二月A、B产品的需求量分别为400和700件。各厂生产A和B产品所需时间、可用时间数据由表4.24的数据给出。设两种产品的单位产品制造时间都为1小时。如果在第一月生产第二月的产品，则需存放一个月，3个工厂的保管费分别为10，15和20元。试拟定生产计划，使总成本最低。

（2）生产排程问题6/26/202555表4.24基本数据表（成本单位：元/件，时间单位：小时）解：（2）生产排程问题6/26/202556表4.25生产排程问题的“运价表”例4.14某航空公司使用上海作为中转枢纽，以最少的航班数满足国内北方城市和南方城市之间的航空出行需求。从上午10点到11点有四架分别来自哈尔滨、长春、吉林、沈阳的波音747客机将在上海虹桥机场降落。这些飞机上的乘客将分别去往福州、广州、深圳、厦门。飞机的离场时间为11点30分到12点30分。表4.27列出了各个航班的乘客去往各目的地的情况表，即转机情况表。例如，来自哈尔滨的飞机，若飞往厦门则有38人不转机，剩下的去福州、广州和深圳等城市的都需要转机。此外，表中航班的出发地和目的地都是按时间的先后顺序排列的。例如，福州在广州之前表示去往福州的飞机将先于去往广州的飞机起飞。表格中标记为“-”的两个格子表示，由于来自沈阳的飞机到中转站（上海）的时间最迟，已经来不及在去福州和广州的城市的飞机起飞前完成到这两地的转机流程。请问应如何安排各航班离开虹口机场后的目的地，以使得在虹桥机场转机的乘客数最少？（3）

机场航班转机问题6/26/202557

（3）

机场航班转机问题6/26/2025解：58例4.15在某个建筑工程的施工中有一种设备容易损坏，因此X公司专门设立了一个设备供给处负责工程施工期间对这种设备的补给。供给处有三种途径来满足工程施工对该设备的需求。第一条途径是利用自己的一个修理车间对该设备进行公司内部的维修。内部维修该设备的修理时间为4周，每台所需费用为100元。第二条途径是外送维修，即将设备送到专门的设备维修公司进行修理。修理时间为1周，但每台费用为300元。第三条途径是购买新设备。每台新设备的价格为900元。供给处需租用仓库存放已修、待修或报废的设备，每台每周的存贮费为10元。报废的设备存储在仓库中等工程完工时统一处理。假设每周末X公司工程处将损坏设备送到供给处并领走相同数量的好设备。预计该工程可在n周完工（为简化取n=10）。请你为供给处设计一个合理的供给计划，要求在绝对保证工程需要的条件下，能使得供给处所花费的总费用最少。（4）供给计划问题6/26/202559案例1新美电器公司是新进在中国南方崛起的智能家用电器公司。从一家小型科技创业企业起家，凭借其研发的家用智能机器人技术，首先在深圳建立了第一个制造基地。随着业务的发展又在顺德建立了第二个制造基地。为了覆盖全国的市场，公司在北京、上海和广州建立分销中心，向9个目标客户区销售产品。这九个地区的编号分别为T1，...，T9