第4章 运输问题和指派问题PPT课件

第4章运输问题和指派问题TheTransportationandAssignmentProblems,本章内容要点,运输问题的基本概念运输问题的各种变形运输问题的建模求解与应用指派问题的基本概念指派问题的各种变形指派问题的建模求解与应用,本章内容,4.1运输问题的基本概念4.2运输问题的数学模型和电子表格模型4.3表上作业法(补充)4.4运输问题的变形4.5运输问题的应用举例4.6指派问题的基本概念4.7匈牙利法(补充)4.8指派问题的变形4.9指派问题的应用举例,本章主要内容框架图,4.1运输问题的基本概念,运输问题最初起源于在日常生活中人们把某些物品或人们自身从一些地方转移到另一些地方，要求所采用的运输路线或运输方案是最经济或成本最低的，这就成为了一个运筹学问题。随着经济的不断发展，现代物流业的蓬勃发展，如何充分利用时间、信息、仓储、配送和联运体系创造更多的价值，向运筹学提出了更高的挑战。要求科学地组织货源、运输和配送，使得运输问题变得日益复杂，但是其基本思想仍然是实现现有资源的最优化配置。,4.1运输问题的基本概念,一般的运输问题就是解决如何把某种产品从若干个产地调运到若干个销地，在每个产地的供应量和每个销地的需求量以及各地之间的运输单价已知的前提下，确定一个使得总运输成本最小的方案。平衡运输问题的条件如下：（1）明确出发地（产地）、目的地（销地）、供应量（产量）、需求量（销量）和单位运输成本。（2）需求假设：每一个出发地（产地）都有一个固定的供应量，所有的供应量都必须配送到目的地（销地）。与之类似，每一个目的地（销地）都有一个固定的需求量，整个需求量都必须由出发（产地）地满足。即“总供应量总需求量”。（3）成本假设：从任何一个出发地（产地）到任何一个目的地（销地）的货物运输成本与所运送的货物数量成线性比例关系，因此，货物运输成本就等于单位运输成本乘以所运送的货物数量（目标函数是线性的）。,4.1运输问题的基本概念,典型背景单一物资运输调度问题设某种物品有:m个产地：产量：n个销地：销量：从产地到销地的单位运价是。求总运费最小的调度方案。,4.1运输问题的基本概念,产销平衡运输问题的数学模型：设从产地Ai运往销地bj的物资数量为xij（i=1,2,m;j=1,2,n),Note1:,平衡运输问题有mn个变量，m+n个约束条件，规模很大。,x11x12x1nx21x22x2nxm1xm2xmn,运输问题,决策变量表示由到的物品数量。,Note2:,4.1运输问题的基本概念,例4.1某公司有三个加工厂（A1、A2和A3）生产某种产品，每日的产量分别为：7吨、4吨、9吨；该公司把这些产品分别运往四个销售点（B1、B2、B3和B4），各销售点每日的销量分别为：3吨、6吨、5吨、6吨；从三个加工厂（产地）到四个销售点（销地）的单位产品运价如表4-2所示。问该公司应如何调运产品，才能在满足四个销售点的需求量的前提下，使总运费最少？表4-2三个加工厂到四个销售点的单位产品运价（千元/吨）,4.2运输问题的数学模型和电子表格模型,解：首先，三个加工厂A1、A2、A3的总产量为74920（吨）；四个销售点B1、B2、B3、B4的总销量为365620（吨）。也就是说，总产量等于总销量，故该运输问题是一个产销平衡的运输问题。（1）决策变量设xij为从加工厂Ai（i1,2,3）运往销售点Bj（j=1,2,3,4）的运输量（吨）。（2）目标函数本问题的目标是使公司的总运费最少,4.2运输问题的数学模型和电子表格模型,（3）约束条件三个加工厂的产品都要全部运送出去（产量约束）四个销售点的产品都要全部得到满足（销量约束）非负,4.2运输问题的数学模型和电子表格模型,运输问题是一种特殊的线性规划问题，一般采用“表上作业法”求解运输问题，但Excel的“规划求解”还是采用“单纯形法”来求解。例4.1的电子表格模型,（1）设置“条件格式”的操作请参见本章附录（P142）（2）将单元格的字体和背景颜色设置为相同颜色以实现“浑然一体”的效果，这样可以起到隐藏单元格内容的作用。当单元格被选中时，编辑栏中仍然会显示单元格的真实数据。（3）本章所有例题的最优解（运输方案或指派方案）有一个共同特点：“0”值较多，所以都使用了Excel的“条件格式”功能。,4.2运输问题的数学模型和电子表格模型,需要注意的是，运输问题有这样一个性质（整数解性质），即只要它的供应量和需求量都是整数，任何有可行解的运输问题就必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件。由于运输量经常以卡车、集装箱等为单位，如果卡车不能装满，就很不经济了。整数解性质避免了运输量（运输方案）为小数的麻烦。,4.2运输问题的数学模型和电子表格模型,（1）销大于产（供不应求）运输问题的数学模型（以满足小的产量为准）,4.2运输问题的数学模型和电子表格模型,（2）产大于销（供过于求）运输问题的数学模型（以满足小的销量为准）,4.2运输问题的数学模型和电子表格模型,例4.2自来水输送问题。某市有甲、乙、丙、丁四个居民区，自来水由A、B、C三个水库供应。四个居民区每天必须得到保证的基本生活用水量分别为30、70、10、10千吨，但由于水源紧张，三个水库每天最多只能分别供应50、60、50千吨自来水。由于地理位置的差别，自来水公司从各水库向各居民区供水所需付出的引水管理费不同（见P95的表44，其中水库C与丁区之间没有输水管道），其他管理费用都是450元千吨。根据公司规定，各居民区用户按照统一标准900元千吨收费。此外，四个居民区都向公司申请了额外用水量，分别为每天50、70、20、40千吨。问：（1）该公司应如何分配供水量，才能获利最多？（2）为了增加供水量，自来水公司正在考虑进行水库改造，使三个水库每天的最大供水量都提高一倍，问那时供水方案应如何改变？公司利润可增加到多少？,4.2运输问题的数学模型和电子表格模型,例4.2问题（1）的线性规划模型：目标：从获利最多转化为引水管理费最少,4.2运输问题的数学模型和电子表格模型,例4.2问题（1）的电子表格模型：,4.2运输问题的数学模型和电子表格模型,例4.2问题（1）的最优供水方案网络图：,4.2运输问题的数学模型和电子表格模型,例4.2问题（2）方法1的线性规划模型：目标：将获利最多转化为引水管理费最少,4.2运输问题的数学模型和电子表格模型,例4.2问题（2）方法1的电子表格模型：,4.2运输问题的数学模型和电子表格模型,例4.2问题（2）的最优供水方案网络图：,4.2运输问题的数学模型和电子表格模型,例4.2问题（2）方法2：目标为获利最多,4.4运输问题的变形,现实生活中符合产销平衡运输问题的每一个条件的情况很少。一个特征近似但其中的一个或者几个特征却并不符合产销平衡运输问题条件的运输问题却经常出现。下面是要讨论的一些特征：（1）总供应量大于总需求量。每一个供应量（产量）代表了从其出发地（产地）中运送出去的最大数量（而不是一个固定的数值，）。（2）总供应量小于总需求量。每一个需求量（销量）代表了在其目的地（销地）中所接收到的最大数量（而不是一个固定的数值，）。（3）一个目的地（销地）同时存在着最小需求量和最大需求量，于是所有在这两个数值之间的数量都是可以接收的（需求量可在一定范围内变化，、）。（4）在运输中不能使用特定的出发地（产地）-目的地（销地）组合（xij=0）。（5）目标是使与运输量有关的总利润最大而不是使总成本最小（MinMax）,4.4运输问题的变形,例4.4某公司决定使用三个有生产余力的工厂进行四种新产品的生产。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量（见表4-7的最右列）。而每种产品每天有一定的需求量（见表4-7的最后一行）。除了工厂2不能生产产品3以外，每个工厂都可以生产这些产品。然而，每种产品在不同工厂中的单位成本是有差异的（如表4-7所示）。现在需要决定的是：在哪个工厂生产哪种产品，可使总成本最小。表4-7三个工厂生产四种新产品的有关数据,4.4运输问题的变形,解：把“指定工厂生产产品问题”看作“运输问题”。本问题中，工厂2不能生产产品3，这样可以增加约束条件x230；并且，总供应量（75+75+45=195）总需求量（20+30+30+40=120）。其数学模型如下：设xij为工厂i生产产品j的数量,4.4运输问题的变形,例4.4的电子表格模型,产品4分在2个工厂（工厂2和工厂3）生产,4.4运输问题的变形,例4.4需求量存在最小需求量和最大需求量（需求量可在一定范围内变化）的问题。某公司在三个工厂中专门生产一种产品。在未来的四个月中，四个处于国内不同区域的潜在顾客（批发商）很可能有大量订购。顾客1是公司最好的顾客，所以他的订单要全部满足；顾客2和顾客3也是公司很重要的顾客，所以营销经理认为至少要满足他们订单的1/3；对于顾客4，营销经理认为并不需要特殊考虑。由于运输成本上的差异，销售一个产品得到的利润也不同，利润很大程度上取决于哪个工厂供应哪个顾客（见表4-8）。问应向每一个顾客供应多少产品，才能使公司的总利润最大？表4-8三个工厂供应四个顾客的相关数据,4.4运输问题的变形,解：该问题要求满足不同顾客的需求（订购量），解决办法：实际供应量最少供应量实际供应量要求订购量目标是总利润最大，而不是总成本最小。其数学模型如下：设xij为工厂i供应顾客j的产品数量,4.4运输问题的变形,例4.4的电子表格模型,4.5运输问题的应用举例,例4.5（了解即可）某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务。各条航线的起点、终点城市及每天航班数如表4-9所示。假定各条航线使用相同型号的船只，各城市间的航程天数见表4-10。又知每艘船只每次装卸货的时间各需1天。问该航运公司至少应配备多少艘船，才能满足所有航线的运货需求？解：该公司所需配备船只分为两部分。（1）载货航程需要的周转船只数：直接计算。（2）各港口间调度所需船只数：运输问题。,了解即可,4.5运输问题的应用举例,例4.5的电子表格模型,了解即可,4.5运输问题的应用举例,例4.6设有某种原料的三个产地A1、A2和A3，把这种原料经过加工制成成品，再运往销售地。假设用4吨原料可制成1吨成品。产地A1年产原料30万吨，同时需要成品7万吨；产地A2年产原料26万吨，同时需要成品13万吨；产地A3年产原料24万吨，不需要成品。又知A1与A2的距离为150公里，A1与A3的距离为100公里，A2与A3的距离为200公里。原料运费为3千元/万吨公里，成品运费为2.5千元/万吨公里。且已知在产地A1把4万吨原料制成1万吨成品的加工费为5.5千元，在产地A2为4千元，在产地A3为3千元，见表4-16。因条件限制，产地A2的生产规模不能超过年产成品5万吨，而产地A1和产地A3没有限制。问应在何地设厂，生产多少成品，才能使总费用（包括原料运费、成品运费、加工费等）最少？,4.5运输问题的应用举例,解：该问题包含两个运输问题，一个是原料的运输问题，另一个是成品的运输问题。还有将原料制成成品的问题，所以，总费用原料运费成品运费加工费。例4.6的线性规划模型,4.5运输问题的应用举例,例4.6的电子表格模型,4.6指派问题的基本概念,在生活中经常会遇到这样的问题：某单位需完成n项任务，恰好有n个人可以承担这些任务。由于每个人的专长不同，各人完成的任务不同，所需的时间（或效率）也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务所需的总时间最短（或总效率最高）。这类问题称为指派问题（assignmentproblem）或分派问题。平衡指派问题的假设：（1）人的数量和任务的数量相等；（2）每个人只能完成一项任务；（3）每项任务只能由一个人来完成；（4）每个人和每项任务的组合都会有一个相关的成本（单位成本）；（5）目标是要确定如何指派才能使总成本最小。,4.6指派问题的基本概念,设xij为是否指派第i个人去完成第j项任务，目标函数系数cij为第i个人完成第j项任务所需要的单位成本。平衡指派问题的线性规划模型如下：,4.6指派问题的基本概念,需要说明的是：指派问题实际上是一种特殊的运输问题。其中出发地是“人”，目的地是“任务”。只不过，每个出发地的供应量都为1（因为每个人都要完成一项任务），每个目的地的需求量也都为1（因为每项任务都要完成）。由于运输问题有“整数解性质”，因此，指派问题没有必要加上所有决策变量都是0-1变量的约束条件。指派问题是一种特殊的线性规划问题，有一种简便的求解方法：匈牙利方法（HungarianMethod），但Excel的“规划求解”还是采用“单纯形法”来求解。,4.6指派问题的基本概念,例4.7某公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他安排小张、小王、小李、小刘四个人，每个人负责完成一项任务：A、B、C和D。由于每个人完成每项任务的时间和工资不同。问公司应指派何人去完成何任务，才能使总成本最少？,4.6指派问题的基本概念,解：该问题是一个典型的平衡指派问题。单位成本为每个人完成每项任务的总工资；目标是要确定哪个人去完成哪项任务，才能使总成本最少；供应量为1表示每个人都只能完成一项任务；需求量为1表示每项任务也只能由一个人来完成；总人数（4人）和总任务数（4项）相等,4.6指派问题的基本概念,例4.7的线性规划模型如下：设xij为是否指派人员i去完成任务j,4.6指派问题的基本概念,例4.7的电子表格模型,4.6指派问题的基本概念,例4.7的最优指派方案网络图,4.8指派问题的变形,经常会遇到指派问题的变形，之所以称它们为变形，是因为它们都不满足平衡指派问题所有假设中的一个或者多个。一般考虑下面的一些特征：（1）某人不能完成某项任务（相应的xij0）;（2）每个人只能完成一项任务，但是任务数比人数多(人少事多);（3）每项任务只由一个人完成，但是人数比任务数多（人多事少）；（4）某人可以同时被指派多个任务（一人可做多事）；（5）某事需要由多人共同完成（一事需多人做）；（6）目标是与指派有关的总利润最大而不是总成本最小；（7）实际需要完成的任务数不超过总人数也不超过总任务数。,4.8指派问题的变形,例4.8题目见例4.4，即某公司需要安排三个工厂来生产四种新产品，相关的数据在表4-7中已经给出。在例4.4中，允许产品生产分解，但这将产生与产品生产分解相关的隐性成本（包括额外的设置、配送和管理成本等）。因此，管理人员决定在禁止产品生产分解发生的情况下对问题进行分析。新问题描述为：已知如表4-7所示的数据，问如何把每个工厂指派给至少一个新产品（每种产品只能在一个工厂生产），才能使总成本最少？,4.8指派问题的变形,解：该问题可视为指派工厂生产产品问题，工厂可以看作指派问题中的人，产品则可以看作需要完成的任务。由于有四种产品和三个工厂，所以就需要有一个工厂生产两种新产品，只有工厂1和工厂2有生产两种产品的能力，这是因为工厂1和工厂2的生产能力都是75，而工厂3的生产能力是45。这里涉及如何把运输问题转化为指派问题，关键之处在于数据转化。,4.8指派问题的变形,数据转化：（1）单位指派成本:原来的单位成本转化成整批成本（整批成本单位成本需求量），即单位指派成本为每个工厂生产每种产品的成本。（2）供应量和需求量的转化：三个工厂生产四种产品，但一种产品只能在一个工厂生产。根据生产能力，工厂3只能生产一种产品（供应量为1），而工厂1和工厂2可以生产两种产品（供应量为2），而四种产品的需求量都为1。还有“总供应量（2+2+1=5）总需求量（1+1+1+1=4）”,为“人多事少”的指派问题。,4.8指派问题的变形,例4.8的线性规划模型：设xij为指派工厂i（i=1,2,3）生产产品j（j=1,2,3,4),4.8指派问题的变形,例4.8的电子表格模型,4.8指派问题的应用举例,例4.9科学家选派问题。某制药公司准备开发新药，市场部在进行了大量的市场调查之后，共有五个项目被公司选定。项目1；开发一种更加有效的抗抑郁剂。项目2：开发一种治疗躁狂抑郁病的新药。项目3：为女性开发一种副作用更小的节育方法。项目4：开发一种预防HIV的疫苗。项目5：开发一种更有效的降压药。公司将聘请五位科学家来负责这些项目的研发，但每位科学家根据自己的学科领域对各个项目的兴趣程度不同。为了使这些科学家能够从事他们感兴趣的项目，而又使公司能够在开发新药中的成功性尽可能大，公司设立了一个投标系统，每位科学家都有1000点，用来向自己感兴趣的项目投标。投标点数越多，则表示他对该项目的兴趣程度越高。,4.9指派问题的应用举例,表4-20五位科学家的投标情况,4.9指派问题的应用举例,分析：决定要对一些可能发生的情况进行评估。（1）根据给出的投标情况，如果需要为每个项目指派一位科学家，并且使得所有科学家的满意度最高，那么应该如何指派？（人数与项目数相等）P123124（2）如果罗林博士接到了北大医学院的邀请去完成一个教学任务，而公司却非常想把他留下来，但是北大的声望会使他离开公司。如果这种情况真的发生，那么公司就只有放弃那个最缺乏热情的项目。公司应当放弃哪个项目？（人少项目多）P124-125,4.9指派问题的应用举例,（3）当然，站在公司的角度，公司并不愿意放弃任何一个项目，因为如果放弃一个项目，而只剩下四个项目，就会大大降低研发出新药的概率。公司经过系统考察，认为朱诺博士和王凯博士的能力较强，可以同时负责两个项目的研发。在只有四位科学家的情况下，让哪位科学家负责哪个项目的研发，才能使得公司开发新药成功的概率最大？（朱诺博士和王凯博士可以同时负责两个项目的研发）P125126（4）还是来分析五位科学家五个项目的情况，但由于各方面的原因，有三位科学家不能负责几个特定项目的研发。由于存在有些科