《运筹学（第3版）》 课件 第3章 运输问题和指派问题

实用运筹学

－－运用Excel建模和求解（第3版）第3章运输问题和指派问题TheTransportationandAssignmentProblems本章内容要点运输问题的基本概念运输问题的数学模型运输问题的变形转运问题指派问题的基本概念指派问题的变形本章主要内容框架图3.1运输问题的基本概念运输问题源于在日常生活中人们把某些物品或人们自身从一些地方转移到另一些地方，要求所采用的运输路线或运输方案是最经济或成本最小的，这就成为一个运筹学问题。随着经济水平的不断提升，现代物流业蓬勃发展，如何充分利用时间、信息、仓储、配送和联运体系创造更多的价值，向运筹学提出了更高的挑战。这要求科学地组织货源、运输和配送，使运输问题变得日益复杂，但其基本思想仍然是实现现有资源的最优化配置。3.1运输问题的基本概念一般的运输问题就是解决如何把某种产品从若干个产地调运到若干个销地的问题，在每个产地的供应量和每个销地的需求量以及各地之间的运输单价已知的前提下，确定一个使得总运输成本最小的方案。平衡运输问题的条件如下：（1）明确出发地（产地）、目的地（销地）、供应量（产量）、需求量（销量）和单位运输成本。（2）需求假设：每一个出发地（产地）都有一个固定的供应量，所有的供应量都必须配送到目的地（销地）。与之类似，每一个目的地（销地）都有一个固定的需求量，所有的需求量都必须由出发地（产地）满足。即“总供应量＝总需求量”。（3）成本假设：从任何一个出发地（产地）到任何一个目的地（销地）的货物运输成本与所运送的货物数量呈线性关系，因此，货物运输成本就等于单位运输成本乘以所运送的货物数量（目标函数是线性的）。3.2运输问题的数学模型产销平衡运输问题的数学模型设从产地Ai运往销地Bj的物资数量为xij（i=1,2,⋯,m;j=1,2,⋯,n)

3.2.1产销平衡的运输问题例3-1

某公司有三个加工厂（A1、A2和A3）生产某种产品，每日的产量分别为7吨、4吨、9吨。该公司把这些产品分别运往四个销售点（B1、B2、B3和B4），四个销售点每日的销量分别为3吨、6吨、5吨、6吨。从三个加工厂（产地）到四个销售点（销地）的单位产品运价如表3-2所示。问该公司应如何调运产品，才能在满足四个销售点的销量的前提下，使总运费最小？销售点B1销售点B2销售点B3销售点B4加工厂A1311310加工厂A21928加工厂A3741053.2.1产销平衡的运输问题【解】首先，三个加工厂A1、A2、A3的总产量为7＋4＋9＝20（吨）；四个销售点B1、B2、B3、B4的总销量为3＋6＋5＋6＝20（吨）。也就是说，总产量等于总销量，故该运输问题是一个产销平衡的运输问题。（1）决策变量

设xij为从加工厂Ai（i＝1,2,3）运往销售点Bj（j=1,2,3,4）的运输量。（2）目标函数

本问题的目标是使公司的总运费最小。3.2.1产销平衡的运输问题（3）约束条件①三个加工厂的产品全部都要运送出去（产量约束）②四个销售点的产品全部都要得到满足（销量约束）③非负3.2.1产销平衡的运输问题运输问题是一种特殊的线性规划问题，一般采用“表上作业法”求解，但Excel的“规划求解”功能还是采用“单纯形法”来求解。例3-1的电子表格模型（1）设置条件格式的操作请参见本章附录。（2）将单元格的字体和背景颜色设置为相同颜色以实现“浑然一体”的效果，可以起到隐藏单元格内容的作用。当单元格被选中时，编辑栏中仍然会显示单元格的真实数据。（3）本章所有例题的最优解（运输方案或指派方案）有一个共同特点，即“0”值较多，所以都使用了Excel的“条件格式”功能。3.2.1产销平衡的运输问题例3-1的最优调运方案网络图A2A3A1B2B3B1B47365649231635产量

加工厂

运输量

销售点

销量运输问题的整数解性质需要注意的是：运输问题有这样一个性质（整数解性质），即只要它的产量（供应量）和销量（需求量）都是整数，任何存在可行解的运输问题就必然存在所有决策变量都是整数的最优解。因此，没有必要加上所有决策变量都是整数的约束条件。由于运输量经常以卡车、集装箱等为单位，如果卡车不能装满，就很不经济了。整数解性质避免了运输量（运输方案）为小数的麻烦。3.2.2产销不平衡的运输问题实际问题中，产销往往是不平衡的。（1）销大于产（供不应求）运输问题的数学模型（以满足小的产量为准）3.2.2产销不平衡的运输问题（2）产大于销（供过于求）运输问题的数学模型（以满足小的销量为准）3.2.2产销不平衡的运输问题例3-2自来水输送问题。某市有甲、乙、丙、丁四个居民区，自来水由A、B、C三个水库供应。四个居民区每天的基本生活用水量分别为3万吨、7万吨、1万吨、1万吨，但由于水源紧张，三个水库每天最多只能分别供应5万吨、6万吨、5万吨自来水。由于地理位置的差别，自来水公司从各水库向各居民区供水所需支付的引水管理费不同（见表3‑4，其中水库C与丁区之间没有输水管道），其他管理费用都是4500元／万吨。根据公司规定，各居民区用户按照统一标准9000元／万吨收费。此外，四个居民区都向公司申请了额外用水量，分别为每天5万吨、7万吨、2万吨、4万吨。问：（1）该公司应如何分配供水量，才能获利最大？（2）为了增加供水量，自来水公司正在考虑进行水库改造，使三个水库每天的最大供水量都增加一倍，那时供水方案应如何改变？公司利润可增加到多少？3.2.2产销不平衡的运输问题【解】可以把“自来水输送问题”看作“运输问题”，也就是用“运输问题”的方法求解“自来水输送问题”。设xij为水库i向居民区j的日供水量（11个变量）

3.2.2产销不平衡的运输问题例3-2问题（1）的线性规划模型目标：从获利最大转化为引水管理费最小由于A、B、C三个水库的总供水量5＋6＋5＝16，超过四个居民区的基本生活用水量之和3＋7＋1＋1＝12（供过于求），但又少于四个居民区的基本生活用水量与额外用水量之和（3＋7＋1＋1）＋（5＋7＋2＋4）＝30（供不应求），所以本问题既是“供过于求”又是“供不应求”的不平衡运输问题。

3.2.2产销不平衡的运输问题例3-2问题（1）的电子表格模型电子表格模型中有12个变量（供水量，C9:F11区域），通过增加约束条件“$F$11＝0”，实现“水库C与居民区丁之间没有输水管道”。3.2.2产销不平衡的运输问题例3-2问题（1）的最优供水方案网络图BCA乙丙甲丁5814356551541水库供水量居民区最大供水量最大用水量3.2.2产销不平衡的运输问题例3-2问题（2）方法1的线性规划模型目标：将获利最大转化为引水管理费最小由于A、B、C三个水库每天的最大供水量都提高一倍，则公司总供水能力增加到16×2＝32万吨，大于总需求量30万吨，为“供过于求”的不平衡运输问题。

3.2.2产销不平衡的运输问题例3-2问题（2）方法1

的电子表格模型电子表格模型中有12个变量（供水量，C9:F11区域），通过增加约束条件“$F$11＝0”，实现“水库C与居民区丁之间没有输水管道”。3.2.2产销不平衡的运输问题例3-2问题（2）的最优供水方案网络图BCA乙丙甲丁10814351210105353水库供水量居民区最大供水量最大用水量43.2.2产销不平衡的运输问题例3-2问题（2）方法2：目标为获利最大电子表格模型中有12个变量（供水量，C9:F11区域），通过增加约束条件“$F$11＝0”，实现“水库C与居民区丁之间没有输水管道”。

3.3运输问题的变形现实生活中符合产销平衡运输问题的每个条件的情况很少。一个特征近似但其他一个或者几个特征不符合产销平衡运输问题条件的运输问题却经常出现。下面是要讨论的一些特征：特征1：总供应量大于总需求量。每个供应量（产量）代表了从其出发地（产地）运送出去的最大数量（而不是一个固定的数值，≤）特征2：总供应量小于总需求量。每个需求量（销量）代表了在其目的地（销地）接收到的最大数量（而不是一个固定的数值，≤）特征3：一个目的地（销地）同时存在最小需求量和最大需求量，于是所有在这两个数值之间的数量都是可以接收的（需求量可在一定范围内变化，≥、≤）特征4：在运输中不能利用特定的出发地（产地）--目的地（销地）组合（xij=0）特征5：目标是使与运输量有关的总利润最大而不是使总成本最小（Min－>

Max）3.3运输问题的变形例3-3

某公司决定使用三个有生产余力的工厂进行四种产品的生产。生产每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量（见表3-7的最右列）。而每种产品每天有一定的需求量（见表3-7的最后一行）。除了工厂2不能生产产品3以外，每个工厂都可以生产这些产品。然而，每种产品在不同工厂中的单位成本（元）是有差异的（如表3-7所示）。现在需要决定的是在哪个工厂生产哪种产品，可使总成本最小。单位成本生产能力产品1产品2产品3产品4工厂24029一2375工厂33730272145需求量203030403.3运输问题的变形【解】把“指定工厂生产产品问题”看作“运输问题”。本问题中，工厂2不能生产产品3，这样可以增加约束条件x23＝0

；并且总供应量（75+75+45=195）>总需求量（20+30+30+40=120），是供大于求的运输问题。其数学模型：设xij为工厂i生产产品j

的数量3.3运输问题的变形例3-3的电子表格模型产品4分在2个工厂（工厂2和工厂3）生产3.3运输问题的变形例3-4

需求量存在最小需求量和最大需求量（需求量可在一定范围内变化）的问题。某公司在三个工厂中专门生产一种产品。在未来的四个月中，四个处于国内不同区域的潜在顾客（批发商）很可能有大量订购该产品。顾客1是公司最重要的顾客，所以他的订单要全部满足；顾客2和顾客3也是公司很重要的顾客，所以营销经理认为至少要满足他们订单的1/3；对于顾客4，营销经理认为并不需要特殊考虑。由于运输成本的差异，单位利润也不同，利润很大程度上取决于哪个工厂供应哪个顾客（见表3-8）。问应向每个顾客供应多少产品，才能使公司的总利润最大？单位利润（元）产量（件）顾客1顾客2顾客3顾客4工厂1554246538000工厂2371832485000工厂3295951357000最少供应量（件）7000300020000要求订购量（件）70009000600080003.3运输问题的变形【解】该问题要求满足不同顾客的需求（订购量），解决办法：实际供应量

最少供应量实际供应量

要求订购量

目标是总利润最大，而不是总成本最小。其数学模型：设xij为工厂i供应顾客j的产品数量3.3运输问题的变形例3-4的电子表格模型3.4转运问题在实际工作中，有一类问题是需要先将物品由产地运到某个中间转运地，这个转运地可以是产地、销地或中间转运仓库，然后再运到销售目的地，这类问题称为转运问题，可以通过建模转化为运输问题模型。例3-5

例3-1是一个普通的产销平衡运输问题，如果假定：（1）每个加工厂（产地）的产品不一定直接运到销售点（销地），可以将其中几个加工厂的产品集中一起运；（2）运往各销售点的产品可以先运给其中几个销售点，再转运给其他销售点；（3）除产地、销地之外，中间还可以有几个转运站，在产地之间、销地之间或产地与销地之间转运。3.4转运问题例3-5转运问题（续）已知各产地、销地、中间转运站及相互之间的单位产品运价如表3-9所示，问在考虑产销地之间非直接运输的情况下，如何将三个加工厂生产的产品运往销售点，才能使总运费最小？单位运价加工厂（产地）中间转运站销售点（销地）A1A2A3T1T2T3T4B1B2B3B4加工厂（产地）A1

132143311310A21

一35一21928A33一

1一2374105中间转运站T1231

1322846T215一1

114527T34一231

21824T4323212

1一26销售点（销地）B13172411

142B21194858一1

21B33210422242

3B410856746213

3.4转运问题【解】现在把该转运问题转化成一般运输问题，要做如下处理：（1）由于问题中的所有加工厂、中间转运站、销售点都可以看作产地，也可以看作销地，因此把整个问题当作有11个产地和11个销地的扩大的运输问题。（2）对扩大的运输问题建立单位运价表。方法是将不可能的运输方案的运价用任意大的正数（相对极大值）M代替，其余运价cij不变。（3）所有中间转运站的产量等于销量，即流入量等于流出量。（4）扩大的运输问题中原来的产地（加工厂）与销地（销售点），因为也有中间转运站的作用，所以同样在原来的产量与销量上加t＝20吨。即三个加工厂的每日产量分别改为27吨、24吨和29吨，销量均为20吨；四个销售点的每日销量分别改为23吨、26吨、25吨和26吨，产量均为20吨。同时引进xii为辅助变量（虚拟运量）。3.4转运问题【解】表3-10为扩大的运输问题产销平衡表与单位运价表。单位运价A1A2A3T1T2T3T4B1B2B3B4产量A1013214331131027A210M35M2192824A33M01M237410529T12310132284620T215M1011452720T34M23102182420T432321201M2620B13172411014220B21194858M102120B332104222420320B410856746213020销量20202020202020232625262403.4转运问题例3-5的电子表格模型例3-5（转运问题）有多组最优解。（1）最优调运方案1：无需中间转运站，如表3-11和图3-12所示；（2）最优调运方案2：需中间转运站T1，如表3-12和图3-13所示；（3）最优调运方案3：需中间转运站T3，如表3-13和图3-14所示。3.5指派问题的基本概念在生活中经常会遇到这样的问题：某单位需完成n项任务，恰好有n个人可以承担这些任务。由于每个人的专长不同，各人完成的任务不同，所需的时间（或效率）也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务所需的总时间最短（或总效率最高）。这类问题称为指派问题或分派问题。平衡指派问题的假设如下：（1）人的数量和任务的数量相等；（2）每个人只能完成一项任务；（3）每项任务只能由一个人完成；（4）每个人和每项任务的组合都会有一个相关的成本（单位成本）；（5）目标是要确定如何指派才能使总成本最小。3.5指派问题的基本概念设xij为是否指派第i个人去完成第j项任务，目标函数系数cij为第i个人完成第j项任务所需要的单位成本。平衡指派问题的线性规划模型如下：3.5指派问题的基本概念需要说明的是：指派问题实际上是一种特殊的运输问题。其中出发地是“人”，目的地是“任务”。只不过，每个出发地的供应量都为1（因为每个人都要完成一项任务），每个目的地的需求量也都为1（因为每项任务都要完成）。由于运输问题有整数解性质，因此，指派问题没有必要加上所有决策变量都是0-1变量的约束条件。指派问题是一种特殊的线性规划问题，有一种简便的求解方法：匈牙利方法（HungarianMethod），但Excel的“规划求解”功能还是采用单纯形法来求解。3.5指派问题的基本概念例3-6

某公司的营销经理将要主持召开一年一度的由营销区域经理以及营销人员参加的销售协商会议。为了更好地召开这次会议，他安排小张、小王、小李、小刘四个人，每个人负责完成一项任务：A、B、C和D。由于每个人完成每项任务的时间和工资不同。问公司应指派哪个人去完成哪项任务，才能使总成本最小？完成每项任务的时间（小时）每小时工资（元）任务A任务B任务C任务D小张3541274014小王4745325112小李3956364313小刘32512546153.5指派问题的基本概念【解】

该问题是一个典型的平衡指派问题。单位成本为每个人完成每项任务的总工资；目标是要确定哪个人去完成哪项任务，才能使总成本最小；供应量为1表示每个人都只能完成一项任务；需求量为1表示每项任务也只能由一个人完成；总人数（4人）和总任务数（4项）相等。3.5指派问题的基本概念例3-6的线性规划模型设xij为是否指派人员i去完成任务j

3.5指派问题的基本概念例3-6的电子表格模型3.5指派问题的基本概念例3-6的最优指派方案网络图小李小刘小张BCAD人指派任务小王3.6指派问题的变形经常会遇到指派问题的变形，之所以称它们为变形，是因为它们都不满足平衡指派问题所有假设中的一个或者多个。一般考虑下面的一些特征：特征1：某人不能完成某项任务（相应的xij＝0）；特征2：每个人只能完成一项任务，但是任务数比人数多(人少事多)；特征3：每项任务只由一个人完成，但是人数比任务数多（人多事少）；特征4：某人可以同时被指派多项任务（一人可做多事）；特征5：某事需要由多人共同完成（一事需多人做）；特征6：目标是与指派有关的总利润最大而不是总成本最小；特征7：实际能够完成的任务数小于总人数，也小于总任务数。3.6指派问题的变形例3-7指派工厂生产产品问题。题目见例3-3，即某公司需要安排三个工厂来生产四种产品，相关的数据见表3-7。在例3-3中，允许产品生产分解，但这将产生与产品生产分解相关的隐性成本（包括额外的设置、配送和管理成本等）。因此，管理人员决定在禁止产品生产分解发生