运筹学中的运输问题课件

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运输问题和指派问题,The Transportation,and Assignment Problems,运输问题和指派问题and Assignment Proble,本章内容要点,运输问题,的基本概念及其各,种变形的建模与应用,指派问题,的基本概念及其各,种变形的建模与应用,本章内容要点运输问题的基本概念及其各指派问题的基本概念及其各,本章节内容,1,运输问题基本概念,2,运输问题数学模型和电子表格模型,3,各种变形的运输问题建模,4,运输问题应用举例,5,指派问题,6,各种变形的指派问题建模,本章节内容1 运输问题基本概念, ,产大于销（总产量大于总销量）,运输问题 数学模型和电子表格模型,各种变形的建模,应用举例,指派问题 数学模型和电子表格模型,本章主要内容框架图, ,产销平衡（总产量等于总销量）, , ,销大于产（总产量小于总销量）,运输问题和指派问题, ,平衡指派问题（总人数等于总任务数）, ,各种变形的建模, 产大于销（总产量大于总销量）运输,1,运输问题,运输问题最初起源于人们在日常生活中把某,些物品或人们自身从一些地方转移到另一些,地方，要求所采用的,运输路线,或,运输方案是,最经济或成本最低,的，这就成为了一个运筹,学问题。,随着经济的不断发展，现代,物流业,蓬勃发展，,如何充分利用时间、信息、仓储、配送和联,运体系创造更多的价值，向运筹学提出了更,高的挑战。,要求科学地组织货源、运输和配送使得运输,问题变得日益复杂，但是其基本思想仍然是,实现现有资源的最优化配置,。,1 运输问题运输问题最初起源于人们在日常生活中把某,1,运输问题基本概念,一般的运输问题就是解决如何把某种产品从若干个,产地,调运到若干个,销地,，在每个产地的,供应量,和每个销地的,需求量,已知，并知道各地之间的,运输单价,的前提下，如,何确定一个使得总的运输费用最小的方案。,平衡运输问题,的条件：,1.,明确出发地（产地）、目的地（销地）、供应量（产量）、需求,量（销量）和单位成本。,2.,需求假设：每一个出发地都有一个,固定的供应量,，所有的供应量,都必须配送到目的地。与之类似，每一个目的地都有一个固定的,需求量，整个需求量都必须由出发地满足。即,“,总供应总需,求,”,。,3.,成本假设：从任何一个出发地到任何一个目的地的货物配送成本,与所配送的数量成线性比例关系，因此成本就等于配送的单位成,本乘以所配送的数量（目标函数是线性的）。,1 运输问题基本概念一般的运输问题就是解决如何把某种产品从,1,运输问题基本概念,例,1,某公司有三个加工厂,A1,、,A2,、,A3,生产某产品，每日,的产量分别为：,7,吨、,4,吨、,9,吨；该公司把这些产品分别,运往四个销售点,B1,、,B2,、,B3,、,B4,，各销售点每日销量分,别为：,3,吨、,6,吨、,5,吨、,6,吨；从各工厂到各销售点的单,位产品运价如表,1,所示。问该公司应如何调运这些产品，,在满足各销售点的需要量的前提下，,使总运费最少,？,表,1,各工厂到各销售点的单位产品运价（元,/,吨）,B1,B2,B3,B4,产量（吨）,7,4,9,A1,A2,A3,销量（吨）,3,1,7,3,11,9,4,6,3,2,10,5,10,8,5,6,1 运输问题基本概念例1 某公司有三个加工厂A1、A2、A,对于例,1,，其数学模型如下：,首先，三个产地,A1,、,A2,、,A3,的总产量为,7,4,9,20,；四个,销地,B1,、,B2,、,B3,、,B4,的总销量为,3,6,5,6,20,。由于总产,量等于总销量，故该问题是一个产销平衡的运输问题。,(1),决策变量,设,x,ij,为从产地,Ai,运往销地,Bj,的运输量,(i,1,2,3;j=1,2,3,4),（,2,）目标函数,本问题的目标是使得总运输费最小,Min z,=,3,x,11,+,11,x,12,+,3,x,13,+,10,x,14,+,x,21,+,9,x,22,+,2,x,23,+,8,x,24,+,7,x,31,+,4,x,32,+,10,x,33,+,5,x,34,对于例1，其数学模型如下：首先，三个产地A1、A2、A3的,（,3,）约束条件,满足产地产量,（,3,个产地的产,品都要全部配,送出去）,满足销地销量,（,4,个销地的产,品都要全部得,到满足）,非负,（3）约束条件,2,运输问题数学模型和电子表格模型,运输问题是一种特殊的线性规划问题，一般采用“,表上作业,法,”,求解运输问题，但,Excel,的,“,规划求解,”,工具还是采用,“,单纯形法,”,来求解。,例,1,的电子表格模型,2 运输问题数学模型和电子表格模型运输问题是一种特殊的线性,2,运输问题数学模型和电子表格模型,（,1,）,产销平衡,运输问题的数学模型,具有,m,个产地,A,i,（,i,1,2,m,）和,n,个销地,B,j,（,j,1,2,n,）的运输问题的数学模型为,2 运输问题数学模型和电子表格模型（1）产销平衡运输问题的数,2,运输问题数学模型和电子表格模型,需要注意的是：运输问题有这样一个性,质（,整数解性质,），只要它的,供应量,和,需求量,都是,整数,，任何有可行解的运输,问题必然有所有决策变量都是,整数的最,优解,。因此，没有必要加上所有变量都,是整数的约束条件。,由于运输量经常以卡车、集装箱等为单,位，如果卡车不能装满的话，就很不经,济了。整数解性质就避免了运输量（运,输方案）为小数的麻烦。,2 运输问题数学模型和电子表格模型需要注意的是：运输问题有,运筹学中的运输问题课件,（,以满足小的产量为准,）,i j,=,（,3,）,销大于产（供不应求）,运输问题,（以满足小的产量为准） i,2,运输问题数学模型和电子表格模型,例,2,某厂按合同规定须于当年每个季度末分别提供,10,，,15,，,25,，,20,台同一规格的柴油机。已知该厂各,季度的生产能力及生产每台柴油机的成本如表所示。,如果生产出来的柴油机当季不交货的，每台每积压,一个季度需储存、维护等费用,1500,元。要求在完成,合同的情况下，做出使该厂,全年生产（包括储存、,维护）费用最小,的决策,。,各季度的生产能力及生产每台柴,油机的成本,季度,生 产 能 力 （ 台 ） 单位成本（万元）,1,2,3,4,25,35,30,10,10.8,11.1,11.0,11.3,2 运输问题数学模型和电子表格模型季度生 产 能 力 （,2,运输问题数学模型和电子表格模型,解：,这是一个,生产与储存（库存）问题,，可以转化为,运输问题,来做。,由于每个季度生产出来的柴油机不一定当季交货，,所以设,x,ij,为第,i,季度生产的第,j,季度交货的柴油机数,。,则第,i,季度生产的第,j,季度交货的每台柴油,机的实际成,本,c,ij,为：,c,ij,=,第,i,季度每台的生产成本,+0.15(,j-i,),（储存、维护等费用）,把第,i,季度生产的柴油机数看作第,i,个生产厂商的产,量；把第,j,季度交货的柴油机数看作第,j,个销售点的销,量；生产成本加储存、维护等费用看作运,费。将生产,与储存问题转化为运输问题，相关数据见表。,2 运输问题数学模型和电子表格模型解：这是一个生产与储存（库,2,运输问题数学模型和电子表格模型,柴油机生产的相关数据,由表可知，总产量（生产能力）为,25+35+30+10=100,，总销量（需求量）为,10+15+25+20=70,，因此是,产大于销,的运输问题。,1,2,3,4,生产能力,10.8,10.95,11.10,1,2,3,11.10,11.25,11.00,11.25,11.40,11.15,25,35,30,4,11.30,10,需求量,10,15,25,20,2 运输问题数学模型和电子表格模型由表可知，总产量（生产,该生产与,储存问题,（转化为,产大于销,的运输问,题）的数,学模型为,2,运输问题数学模型和电子表格模型,Min z,=,10.80,x,11,+,10.95,x,12,+,11.10,x,13,+,11.25,x,14,+,11.10,x,22,+,11.25,x,23,+,11.40,x,24,+,11.00,x,33,+,11.15,x,34,+,11.30,x,44,该生产与2 运输问题数学模型和电子表格模型+ 11.30 x,2,运输问题数学模型和电子表格模型,例,2,的电子表格模型,2 运输问题数学模型和电子表格模型例2的电子表格模型,2,运输问题数学模型和电子表格模型,例,3,某公司从两个产地,A1,、,A2,将物品运往三,个销地,B1,、,B2,、,B3,，各产地的产量、各销地,的销量和各产地运往各销地每件物品的运费,如表所示。问应如何调运，可使得总运输费,最小？,例,3,运输费用表,B1,B2,B3,产量,A1,A2,销量,13,11,53,15,29,36,12,22,65,78,45,（销大于产）,2 运输问题数学模型和电子表格模型B1B2B3产量A113,2,运输问题数学模型和电子表格模型,解：,由表知，总产量为,78+45=123,，总销量为,53+36+65=154,，,销大于产,(,供不应求,),。数学模型如下：,设,x,ij,为产地,Ai,运往销地,Bj,的物品数量,2 运输问题数学模型和电子表格模型解：由表知，总产量为78+,2,运输问题数学模型和电子表格模型,例,3,的电子表格模型,2 运输问题数学模型和电子表格模型例3的电子表格模型,3,各种变形的运输问题建模,现实生活中符合产销平衡运输问题每一个条件的情况很少。一,个特征近似但其中的一个或者几个特征却并不符合产销平衡运,输问题条件的运输问题却经常出现。,下面是要讨论的一些特征：,（,1,）,总供应大于总需求,。每一个供应量（产量）代表了从其出,发地中配送出去的最大数量（而不是一个固定的数值,）。,（,2,）,总供应小于总需求,。每一个需求量（销量）代表了在其目,的地中所接收到的最大数量（而不是一个固定的数值,）。,（,3,）一个目的地,同时存在着最小需求和最大需求,，于是所有在,这两个数值之间的数量,都是可以接收的（,）。,（,4,）在配送中,不能使用,特定的出发地,目的地组合（,x,ij,=0,）。,（,5,）目标是使与配送数量有关的,总利润最大,而不是使总成本最,小。（,Min,Max,）,3 各种变形的运输问题建模现实生活中符合产销平衡运输问题每一,3,各种变形的运输问题建模,例,4,某公司决定使用三个有生产余力的工厂进行四种新产品的生产。每,单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意,种产品的数量来衡量（见表的最右列）。而每种产品每天有一定的需求,量（见表的最后一行）。每家工厂都可以制造这些产品，除了工厂,2,不,能生产产品,3,以外。然而，每种产品在不同工厂中的单位成本是有差异,的（如表所示）。,现在需要决定的是在哪个工厂生产哪种产品，可使总成本最小。,表 产品生产的有关数据,单位成本（元）,生产能力,产品,1,产品,2,产品,3,产品,4,75,75,45,工厂,1,工厂,2,工厂,3,需求量,41,40,37,20,27,29,30,30,28,27,30,24,23,21,40,3 各种变形的运输问题建模产品1产品2产品3产品475工厂,解：,指定工厂生产产品,可以看作运输问题来求,解。本题中，工厂,2,不能,生产产品,3,，这样可以,增,加约束条件,；并且，总,供应,x,23,0,（,75+75+45=195,）,总需,求（,20+30+30+40=120,）。,其数学模型如下：,设,x,ij,为工厂,i,生产产品,j,的数量,3,各种变形的运输问题建模,解：指定工厂生产产品3 各种变形的运输问题建模,3,各种变形的运输问题建模,例,4,的电子表格模型,产品,4,分在,2,个工厂生产,3 各种变形的运输问题建模例4的电子表格模型产品4分在2个工,3,各种变形的运输问题建模,例,5,某公司在,3,个工厂中专门生产一种产品。在未来的,4,个月中，有四个,处于国内不同区域的潜在顾客（批发商）很可能大量订购。顾客,1,是公司,最好的顾客，所以他的全部订购量都应该满足；顾客,2,和顾客,3,也是公司,很重要的顾客，所以营销经理认为作为最低限度至少要满足他们订单的,1/3,；对于顾客,4,，销售经理认为并不需要进行特殊考虑。由于运输成本,上的差异，销售一个产品得到的净利润也不同，很大程度上取决于哪个,工厂供应哪个顾客（见表）。问,应向每一个顾客供应多少货物,，以使公,司总利润最大？,表,4-8,工厂供应顾客的相关数据,产量,单位利润（元）,顾客,1,顾客,2,顾客,3,顾客,4,8000,5000,7000,工厂,1,工厂,2,工厂,3,最小采购量,最大采购量,55,37,29,7000,7000,42,18,59,3000,9000,46,32,51,2000,6000,53,48,35,0,8000,3 各种变形的运输问题建模产量单位利润（元）顾客3顾客48,3,各种变形的运输问题建模,解：,该问题要求满足不,同顾客的需求（采购,量），解决办法：,实际供给量,最小采购量,实际供给量,最大采购量,目标是利润最大，而,不是成本最小。,其数学模型如下：,设,x,ij,为,工厂,i,供应给,顾,客,j,的产品,数量,3 各种变形的运输问题建模解：该问题要求满足不,3,各种变形的运输问题建模,例,5,的电子表格模型,3 各种变形的运输问题建模例5的电子表格模型,4,运输问题应用举例,例,6,某厂生产设备是以销定产的。已知,1,6,月份各月的生产能力、合,同销量和单台设备平均生产费用，如表所示。,已知上年末库存,103,台。如果当月生产出来的设备当月不交货，则,需要运到分厂库房，每台增加运输成本,0.1,万元，每台设备每月的平均,仓储费、维护费为,0.2,万元。,7,8,月份为销售淡季，全厂停产,1,个月，,因此在,6,月份完成销售合同后还要留出库存,80,台。加班生产设备每台增,加成本,1,万元。问应如何安排,1,6,月份的生产，使总的生产（包括运输、,仓储、维护）费用最少？,月份,1,月,2,月,3,月,4,月,5,月,6,月,正常生产能力,（台）,60,50,90,100,100,80,加班生产能力,（台）,10,10,20,40,40,40,合同销量（台）,104,75,115,160,103,70,单台费用,（万元）,15,14,13.5,13,13,13.5,4 运输问题应用举例月份正常生产能力加班生产能力合同销量（台,4,运输问题应用举例,例,7,华中金刚石锯片厂有两条生产线，分别生产直,径,900-1800mm,大锯片基体,20000,片，直径,350-800mm,中小锯片基体,40000,片。公司在全国有,25,个销售网,点，主要销售区域集中在福建、广东、广西、四川、,山东,5,个石材主产区。为完成总厂的要求，公司决,定一方面拿出,10%,的产量稳定与前期各个客户的联,系以保证将来的市场区域份额，另一方面，面临如,何将剩余的,90%,的产量合理分配给,五个石材主产区,和其他省区,，,以获取最大的利润。各个销售区的最,低需求、销售固定费用、每片平均运费、每片从总,厂库房的购进价与当地的销售价差贡献等自然情况,见表。问应如何分配给各个销售区，才能使得总利,润为最大？,4 运输问题应用举例例7 华中金刚石锯片厂有两条生产线，分别,4,运输问题应用举例,4 运输问题应用举例,5,指派问题,在现实生活中，经常会遇到指派人员做某项工,作（任务）的情况。,指派问题,的许多应用是用,来帮助管理人员解决如何为一项即将开展的工,作指派人员的问题。其他的一些应用如为工作,指派机器、设备或工厂等。,指派问题也称,分配问题，,主要研究人和工作,（任务）间如何匹配，以使所有工作完成的效,率实现最优化。形式上，指派问题给定了一系,列所要完成的工作以及一系列完成工作的人员，,所需要解决的问题就是要确定出指派哪个人去,完成哪项工作。,5 指派问题在现实生活中，经常会遇到指派人员做某项工指派,5,指派问题,指派问题的假设：,（,1,）人的数量和工作的数量,相等,；,（,2,）每个人,只能完成一项,工作；,（,3,）每项工作,只能由一个人,来完成,；,（,4,）每个人和每项工作的组合都会有一,个相关的成本（,单位成本,）；,（,5,）目标是要确定如何指派才能使,总成,本最小,。,5 指派问题指派问题的假设：,设决策变量,x,ij,为,第,i,个人,做,第,j,项工作,，,而已知,5,指派问题,目标函数系数,cij,为第,i,个人完成第,j,项工作所需,要的单位成本。,平衡指派问题的数学模型为,设决策变量xij为第i个人做第j项工作，而已知5 指派问题,5,指派问题,需要说明的是：,指派问题,实际上是一种,特殊的,运输问题,。,其中出发地是人，目的地是工作。只,不过,，,每一个出发地的,供应量都为,1,（因为每个,人都要完成一项工作），每一个目的地的,需求量,都为,1,（因为每项,工作都要完成）。由于运输问,题有,“,整数解性质,”,，因此，,没有必要,加上所有,决策变量都是,0-1,变量,的约束。,指派问题是一种特殊的线性规划问题，有一种,快捷的求解方法：,匈牙利方法,（,Hungarian,Method,），但,Excel,的,“,规划求解,”,工具还是采,用,“,单纯形法,”来求解。,5 指派问题需要说明的是：指派问题实际上是一种特殊的指派,5,指派问题,例,8,某公司的营销经理将要主持召开一年一度的由,营销区域经理以及销售人员参加的销售协商会议。,为了更好地安排这次会议，他安排小张、小王、小,李、小刘等四个人，每个人负责完成下面的一项工,作：,A,、,B,、,C,和,D,。,由于每个人完成每项任务的时间和工资不同（如,表所示）。问如何指派，可使总成本最小。,人员,每小时工资,（元）,每一项工作所需要的时间（小时）,工作,A,工作,B,工作,C,工作,D,小张,小王,小李,小刘,35,47,39,32,41,45,56,51,27,32,36,25,40,51,43,46,14,12,13,15,5 指派问题人员每小时工资每一项工作所需要的时间（小时）小张,5,指派问题,解,：,该问题是一个,典型的指派问题,。,单位成本,为每个人做每项工作的总,工资,目标,是要确定哪个人做哪一项工作，,使总成本最小,供应量为,1,代,表每个人都只能完成一,项工作,需求量为,1,代,表每项工作也只能有一,个人来完成,总人数（,4,人）和总任务数（,4,项）,相等,5 指派问题解：该问题是一个典型的指派问题。单位成本为每个,5,指派问题,数学模型：,设,x,ij,为指派人员,i,去做工作,j,（,i,，,j,1,2,3,4),5 指派问题,5,指派问题,电子表格模型,5 指派问题电子表格模型,6,各种变形的指派问题建模,经常会遇到指派问题的,变形,，之所以称它们为变形，,是因为它们都不满足平衡指派问题所有假设之中的一,个或者多个。一般考虑下面的一些特征：,（,1,）有些人,并不能,进行某项工作（相应的,x,ij,0,）,;,（,2,）虽然每个人完成一项任务，但是任务比人多,(,人少事多,);,（,3,）虽然每一项任务只由一个人完成，但是人比任务多（,人,多事,少,）；,（,4,）某人可以同时被指派给多个任务（,一人可做几件事,）；,（,5,）某事可以由多人共同完成（,一事可由多人完成,） ；,（,6,）目标是与指派有关的,总利润最大,而不是使总成本最小；,（,7,）实际需要完成任务数不超过总人数也不超过总任务数。,6 各种变形的指派问题建模经常会遇到指派问题的变形，之所以称,6,各种变形的指派问题建模,例,9,题目见例,4,，即某公司需要安排三个工,厂来生产四种新产品，相关的数据在例,4,表,4,中已经给出。在例,4,中，允许产品生产分解，,但这将产生与产品生产分解相关的隐性成本,（包括额外的设置、配送和管理成本等）。,因此，管理人员决定在,禁止产品生产分解,发,生的情况下对问题进行分析。,新问题描述为：已知如表所示的数据，,问如何把每一个工厂指派给至少一个新产品,（每一种产品只能在一个工厂生产），使总,成本达到最小？,6 各种变形的指派问题建模例9 题目见例4，即某公司需要安排,6,各种变形的指派问题建模,解：,该问题可视为,指派工厂生产产品问,题,，,工厂可以看作指派问题中的人，产,品则可以看作需要完成的工作（任务）。,由于有四种产品和三个工厂，所以就有,两个工厂各只能生产一种新产品，第三,个工厂生产两种新产品。只有工厂,1,和工,厂,2,有生产两种产品的能力。,这里涉及如何把,运输问题,转换为,指派,问题,，关键所在是,数据转换,。,6 各种变形的指派问题建模解：该问题可视为指派工厂生产产品问,6,各种变形的指派问题建模,数据转换：,（,1,）,单位指派成本,:,原来的单位成本转换成,整,批,成本（单位,成本,需求量），即单位指派,成本为,每个工厂生产每种产品的成本,。,（,2,）,供应量和需求量的转换问题,：三个工厂生,产四种产品，但一种产品只能在一个工厂生产，,根据生产能力，工厂,3,只能生产一种产品（供,应量为,1,），而工厂,1,和工厂,2,可以生产,2,种产品,（供应量为,2,），而产品的需求量为,1,。还有,“,总供应（,2+2+1=5,）,总需求,（,1+1+1+1=4,）,”,为人多事少的指派问题,。,6 各种变形的指派问题建模数据转换：（1）单位指派成本: 原,6,各种变形的指派问题建模,数学模型：,设,x,ij,为指派工厂,i,生产产品,j,（,i=1,2,3;j=1,2,3,4),6 各种变形的指派问题建模,6,各种变形的指派问题建模,电子表格模型,6 各种变形的指派问题建模电子表格模型,What You Should Know about t,he,Transportation and Assignment,Problems,How to formulate various types of,Transportation problems.,How to find solutions.,How to transform variables and functions,into the standard form.,What You Should Know about the,