Ch5运输与指派问题.ppt

《Ch5运输与指派问题.ppt》由会员分享，可在线阅读，更多相关《Ch5运输与指派问题.ppt（103页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1,5.1 运输模型 Mathematical Model of Transportation Problems5.2 运输单纯形法 Transportation Simplex Method5.3 运输模型的应用 Aplication of Transportation Model5.4 指派问题 Assignment problem,2,人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。,5.1 运输问

2、题的数学模型,5.1.1 数学模型,3,【例5-1】现有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元/吨）如表5-1所示，问如何安排一个运输计划，使总的运输费用最少。,运价表（元/T）,表5-1,5.1.1 数 学 模 型,4,【解】设xij (i=1,2,3；j=1,2,3,4)（单位：万吨）为第i个产粮地运往第 j 个需求地的运量，得到下列运输问题的数学模型：,5.1.1 数 学 模 型,5,【例5-2】有三台机床加工三种零件，计划第 i 台的生产任务为ai (i

3、=1,2,3)个零件，第 j 种零件的需要量为bj (j=1,2,3)，第 i 台机床加工第 j 种零件需要的时间为cij ，如表52所示。问如何安排生产任务使总的加工时间最少？,表52,5.1.1 数 学 模 型,6,【解】 设 xi j (i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的数量，则此问题的数学模型为,5.1.1 数 学 模 型,7,运输问题的一般数学模型,设有m个产地A1，A2，,Am，其产量分别为a1, a2, ，am 有n个销地B1，B2，Bn，其需求量分别为b1, b2, ，bn 从第 i 个产地到 j 个销地的单位运价为cij,5.1.1 数 学 模 型

4、,8,5.1.1 数 学 模 型,供求平衡,9,供过于求,供不应求,5.1.1 数 学 模 型,10,1. 存在可行解，也一定存在最优解。 2. 当供应量和需求量都是整数时，则一定存在整数最优解。3. 有m+n个约束，mn个变量。4. 有m+n1个基变量（定理5.1）。,5.1.2 模 型 特 征,11,5.1.2 模 型 特 征,【定理5.1】设m有个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。【定理5.3】m+n1个变量组构成基变量的充要条件是它不包含任何闭回路。,表53,变量集合x11, x12, x42, x43, x23, x25, x35, x31组成一个闭回路。共有

5、8个顶点。 一条回路中的顶点数一定是偶数。,5.1.2 模 型 特 征,为一个闭回路 ，集合中的变量称为闭回路的顶点，相邻两个变量的连线为闭回路的边。,13,表54,表54中闭回路是,5.1.2 模 型 特 征,14,本节介绍了具有m个产地n个销地的平衡运输问题1. 具有m+n1个基变量2. 闭回路的概念3. 怎样判断m+n1个变量是否构成一组基变量,本节学习要点,5.1 运输问题的数学模型,15,平衡运输问题的数学模型为：,5.2 运输问题的表上作业法,16,表上作业法的步骤 第一步：求初始基本可行解（初始调运方案）。 常用的方法有最小元素法、元素差额法（Vogel近似法）、左上角法。,第三

6、步：调整运量（即换基迭代）。选一个变量出基，对原运量进行调整得到新的基本可行解，转入第二步。,5.2 运输问题的表上作业法,第二步：求检验数并判断是否得到最优解。常用求检验数的方法有闭回路法和位势法，当全部非基变量的检验数ij0 时得到最优解，若存在检验数lk0，说明还没有达到最优，转第三步。,17,5.2.1 求初始基本可行解,1. 最小元素法：最小元素法的思想是就近优先运送，即最小运价cij对应的变量xij优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后得到一个初始基可行解。,可以证明： 用最小元素法得到的一组xij构成基本可行解。,18,【例5-3】求表

7、56所示的运输问题的初始基本可行解。,表56,5.2.1 求初始基本可行解,表5759,【解】,30,10,10,60,20,10,5.2.1 求初始基本可行解,20,基可行解可用矩阵,表示。矩阵X 中空白处对应的变量是非基变量，运量等于零，这组解就是初始调运方案。 总运费为 Z=360+810+520+130+210+910=500,5.2.1 求初始基本可行解,21,【例5-4】求表5-10给出的运输问题的初始基本可行解。,表5-10,5.2.1 求初始基本可行解,22,表5-11,【解】,5,10,0,15,10,10,5.2.1 求初始基本可行解,23,初始基本可行解可用下列矩阵表示,

8、基变量恰好是3+41=6个，且不包含闭回路。,5.2.1 求初始基本可行解,X=,24,2元素差额法（Vogel近似法） 最小元素法只考虑了局部运输费用最小。有时为了节省某一处的运费，而在其它处可能运费很大。元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案,前一种按最小元素法求得，总运费是Z1=108+52+151=105后一种方案考虑到C11与C21之间的差额是82=6，先调运x21，再是x22，其次是x12这时总运费Z2=105+152+51=85Z1。,5.2.1 求初始基本可行解,

9、25,元素差额法求初始基本可行解的步骤是：,第一步：求出每行次小运价与最小运价之差，记为ui，i=1,2,m ；同时求出每列次小运价与最小运价之差，记为vj，j=1,2,n 。,第二步：找出所有行、列差额的最大值，即L=maxui，vi，差额L对应行或列的最小运价处优先调运；,第三步：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运方案。,用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。,5.2.1 求初始基本可行解,26,表5-6,【例5-5】用元素差额法求表56运输问题的初始基本可行解。,【解】 求

10、行差额 ui, i=1,2,3及列差额vj,j=1,2,3,4.计算公式为 ui= i行次小运价i行最小运价 vj= j列次小运价j例最小运价,5.2.1 求初始基本可行解,27,表512,【 】,10,5.2.1 求初始基本可行解,28,表5-13,10,【 】,5.2.1 求初始基本可行解,29,表5-14,【 】,20,5.2.1 求初始基本可行解,30,表5-15,【 】,60,30,10,5.2.1 求初始基本可行解,31,基本可行解为,总运费Z=360+810530+120+210+210=470比最小元素法的总运费（500）要小30,5.2.1 求初始基本可行解,可以证明： 用元

11、素差额法得到的一组xij构成基本可行解。,32,3. 左上角法 左上角法(亦称西北角法)是优先从运价表的左上角的变量赋值，当行或列分配完毕后，再在表中余下部分的左上角赋值，依次类推，直到右下角元素分配完毕当出现同时分配完一行和一列时，仍然应在打“”的位置上选一个变量作基变量，以保证最后的基变量数等于m+n1,5.2.1 求初始基本可行解,33,【例5-6】用左上角法求例5-3中表5-6的初始基本可行解,表5-16,10,60,0,10,20,5.2 运输单纯形法 Transportation Simplex Method,40,34,基本可行解为,用左上角法求得的基本可行解对应的目标函数值（总

12、运费）是Z91036080540110+220=520,35,求最小值的运输问题的最优判别准则： 当ij0 时运输方案最优,求检验数的方法有两种，闭回路法和位势法。,1闭回路法 在基本可行解矩阵中，以非基变量为起点，以基变量为其它顶点，找一条闭回路，由起点开始，分别在顶点上交替标上代数符号+、-、+、-、，以这些符号分别乘以相应的运价，其代数和就是这个非基变量的检验数。,5.2.2 求 检 验 数,36,【解】用最小元素法求得初始调运方案,【例5-7】用闭回路法求例5-3表5-9的检验数。,30,10,10,60,20,10,5.2.2 求 检 验 数,5.2.2 求 检 验 数,表中打“”的

13、位置是非基变量，其余是基变量，这里只求非基变量的检验数。,求11: 先找出x11的闭回路 ， 对应的运价为,+,-,-,+,这里340，说明这组基本可行解不是最优解。,39,只要求得的基变量是正确的, 且数目为m+n1，则每个非基变量的闭回路存在且唯一，因而检验数唯一。,5.2.2 求 检 验 数,40,2位势法,位势法求检验数是根据对偶理论推导出来的一种方法。,5.2.2 求 检 验 数,（1）列位势方程组： （基变量格）cij=ui+vj ui代表产地Ai的位势量（行位势），vj代表销地Bj 的位势量（列位势）。 令u1 =0，计算各行各列的位势量。（2）计算非基变量检验数（基变量的检验数

14、为0） （空格） ij = cij (ui+vj ),【例5-8】用位势法求例5-3表5-9给出的初始基本可行解的检验数。,5.2.2 求 检 验 数,30,10,10,60,20,10,表5-9,42,【解】第一步求位势量,5.2.2 求 检 验 数,第二步由公式 求出检验数。,30,10,10,60,20,10,表5-9,44,当某个检验数lk0时，基可行解不是最优解，总运费还可以下降，这时需调整运输量，改进原运输方案，使总运费减少，改进运输方案的步骤是：,第一步：确定进基变量,第二步：确定出基变量 在进基变量xik的闭回路中，标有负号的最小运量作为调整量，对应的基变量为出基变量，并打上“

15、”以示作为非基变量。,第三步：调整运量 在进基变量的闭回路中标有正号的变量加上调整量，标有负号的变量减去调整量，其余变量不变，得到一组新的基可行解。,5.2.3 调 整 运 量,45,【例5-9】求例5-3的最优解【解】1、初始调运方案为,5.2.3 调 整 运 量,30,10,10,60,20,10,46,2、检验：34=-30，这组基本可行解不是最优解。3、调整：,5.2.3 调 整 运 量,+,-,-,+,30,10,10,60,20,10,调整量=10,47,5.2.3 调 整 运 量,4、再检验：11=5,14=0,21=6,22=6,32=9,33=3,20,10,10,60,30

16、,10,48,【例5-10】求下列运输问题的最优解,表5-17,【解】 （1）用最小元素法求初始基本可行解,5.2.3 调 整 运 量,（2）检验：求非基变量的检验数,非基变量x11进基.,x33最小，x33是出基量，即：x11进基, x33出基。,x11的闭回路,（3）调整运量,-,-,-,51,5.2.3 调 整 运 量,Z2=1105=Z1-60=1165-60,（4）再检验：求所有非基变量的检验数13=3，22=0，24=7，31=1，33=4，34=134=10, 说明还没有得到最优解，x34进基。（5）再调整：,53,5.2.3 调 整 运 量,54,调整运量得到：,再求非基变量的

17、检验数：,13=3，14=1，22=0，24=8，31=1，33=4,5.2.3 调 整 运 量,55,所有检验数ij 0, 因而得到最优解,最小运费,5.2.3 调 整 运 量,注意： 还可选取22=0为主元素再调整，得另一最优方案。 一般地，若某个非基变量的检验数=0，表明该运输问题有多个最优解。,【例5-11】有四项工作指派给甲、乙两人完成，每人完成两项工作。两人完成各项工作的时间（小时）见表5-18，怎样安排工作使总时间最少。,表5-18,【解】 设xij(i=1,2；j=1,2,3,4)为第i人完成第j项工作的状态,57,表5-19,表5-20,最优的工作分配方案是： 甲完成工作C和

18、D，乙完成工作A和B 总时间Z47（小时）,5.2.3 调 整 运 量,58,设数学模型为,5.2.4 最大值问题,59,设极大化问题的运价表为C=（cij）mn，用一个较大的数M（Mmaxcij）去减每一个cij得到矩阵C=(cij)mn ，其中c/ij=Mcij0, 将C/作为极小化问题的运价矩阵，用表上作业法求出最优解，目标函数值为,5.2.4 最大值问题,第二种方法: 求初始运输方案可采用最大元素法，所有非基变量的检验数ij0 时最优。,第一种方法：将极大化问题转化为极小化问题。,【补充例】作物布局问题 某农场有土地900亩。这些土地因土壤的肥沃程度和水源条件不同，可以分成三类。现在农

19、场要在这三类土地上计划种植三种作物；各类土地亩数、计划播种面积，以及各种作物在各类土地上的亩产量（单位：公斤）如下表。如何因地制宜安排作物布局，才能使作物总产量最多？,61,【解法1】用最大元素法作初始方案,300,100,100,400,0,5.2.4 最大值问题,最优解判别准则 若检验数ij0，则方案为最优方案。,最大总产量 Z=580000(公斤),调整一次，得最优布局方案,63,5.2.4 最大值问题,【解法2】化为最小化问题 取M=maxcij=850, cij=850-cij,64,当总产量与总销量不相等时，称为不平衡运输问题。这类运输问题在实际中常常碰到，它的求解方法是将不平衡问

20、题化为平衡问题再按平衡问题求解。,5.2.5 不平衡运输问题,65,【例5-12】求下列表中极小化运输问题的最优解。,表5-25,5.2.5 不平衡运输问题,66,【解】这是一个供过于求的问题 设置一个销量为b5=180160=20的虚拟销地B5， ci5=0（i=1,2,3,4）。表的右边增添一列 表中A2不可达B1，用一个很大的正数M表示运价c21,5.2.5 不平衡运输问题,下表为计算结果。可看出：产地A4还有20个单位没有运出。,最小总运费 Z=565说明： 用元素差额法求初始方案便是最优方案。 用最小元素法求初始方案时，B5列可以优先安排，也可以最后安排。,68,【例5-13】在例5

21、-12中，假定B1的需要量是20到60之间，B2的需要量是50到70，试求极小化问题的最优解。,5.2.6 需求量不确定的运输问题,69,（4）将B1与B2各分成两部分 的需求量是20， 的需求量是40， 的需求量分别是50与20，因此 必须由A1，A4供应， 可由 A1、A5供应。,分析： （1）总产量为180，B1，B4的最低需求量是 20+50+35+45=150，这时属供过于求,（2）B1，B4的最高需求是 60+70+35+45=210，这时属供不应求,（3）虚设一个产地A5，产量是210180=30，A5的产量只能供应B1或B2。,5.2.6 需求量不确定的运输问题,（5）上述A5

22、不能供应某需求地的运价用大M表示，A5 到 的运价为零。,得到这样的平衡表后，计算得到最优方案表5-23。,表5-22,5.2.6 需求量不确定的运输问题,71,表中x131=0是基变量,说明这组解是退化基本可行解,空格处的变量是非基变量。B1，B2，B3，B4实际收到产品数量分别是50，50，35和45个单位。,表5-23,5.2.6 需求量不确定的运输问题,72,产地,销地,3,5,4,2,3,1,6,8,2,3,2,9,图5.2,A4,A5,2,2,7,15,中转地,3,4,1,3,5.2.7 中 转 问 题,73,设xij为Ai到Aj的运量，i，j=1，2，m+n+r则中转运输问题的数

23、学模型为,产大于销时将式(5-3a)改为“”约束，销大于产时将式(5-3c)改为“”约束,5.2.7 中 转 问 题,74,本节讲解了平衡运输问题的求解方法：表上作业法1. 求初始运输方案，用最小元素法、元素差额法（Vogel近似法）2. 求检验数，用闭回路法和位势法3. 调整运量，用闭回路法4. 极大值问题的求解方法、不平衡问题、需求量不确定问题,5.2 运输问题的表上作业法,本节学习要点,75,【例5-13】DF公司在接下来的三个月内每月都要按照销售合同生产出两种产品。表5-24中给出了在正常时间（Regular Time，缩写为RT）和加班时间（Over Time，缩写为OT）内能够生产

24、这两种产品的总数。,5.3 运输模型的应用,76,（1）对这个问题进行分析，描述成一个运输问题的产销平衡表，使之可用表上作业法求解。（2）建立总成本最小的数学模型并求出最优解。,表5-30,5.3 运输模型的应用,【解】（1）变量设置如表所示，表中括号内的数据为产品序号 ,可看成一个供过于求的运输问题,表5-31,表5-32 平衡运输表,例如x35表示第2月正常时间内生产的产品1用于第3月交货的数量，第1种单位产品的成本是17（千元），在第3月交货单位产品的储存成本是2（千元），因此单位产品总成本c35等于19（千元），,79,（2）数学模型为：,5.3 运输模型的应用,最优生产计划是： 第1

25、个月正常时间内生产第1种产品7件，当月交货5件，第2个月交货2件；生产第2种产品3件，当月交货，总产量10件，不加班。 第2个月正常时间内生产第1种产品1件，当月交货1件；生产第2种产品7件，当月交货5件，第3个月交货2件，总产量8件，不加班。 第3个月正常时间内生产第1种产品4件，当月交货；生产第2种产品2件，当月交货，总产量6件，不加班期末无库存。 总成本为 Z=389（千元）,81,将生产计划问题转化为运输问题求解,5.3 运输模型的应用,本节学习要点,82,5.4 指 派 问 题,【例5-15】人事部门欲安排四人到四个不同的岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）

26、如表5-28所示，如何安排他们的工作使总成绩最好。,5.1.1 指派问题的数学模型,83,5.4 指 派 问 题,【解】设,84,5.1.1 指派问题的数学模型,每人做一项工作,每项工作只能安排一个人做,85,指派问题的一般模型 假设m个人恰好做m项工作，第i个人做第j项工作的效率为cij0，效率矩阵为cij , 如何分配工作使效率最佳（min或max）的数学模型为,5.1.1 指派问题的数学模型,86,5.4.2 解指派问题的匈牙利法,【定理5.4】如果从分配问题效率矩阵cij的每一行元素中分别减去（或加上）一个常数ui（被称为该行的位势），从每一列分别减去（或加上）一个常数vj（称为该列的

27、位势），得到一个新的效率矩阵bij，其中bij=cijuivj,则bij的最优解等价于cij的最优解，这里cij、bij均非负,【定理5.5】若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素（称为独立元素）的最大个数。,87,如果覆盖“0”元素的最少直线数等于m，则存在m个独立的“0”元素，令这些零元素对应的xij等于1，其余变量等于0，这时目标函数值等于零，得到最优解。,5.4.2 解指派问题的匈牙利法,匈牙利法的条件： 1、问题是求最小值 2、人数与工作数相等，即m=n 3、效率非负，即cij0。,88,【例5-15】某汽车公司拟将四

28、种新产品配置到四个工厂生产，四个工厂的单位产品成本（元/件）如表5-29所示。求最优生产配置方案。,5.4.2 解指派问题的匈牙利法,89,5.4.2 解指派问题的匈牙利法,C=,【解】问题为求最小值。 第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有,90,第二步：找出矩阵每列的最小元素，再分别从每列中减去，有,5.4.2 解指派问题的匈牙利法,91,第三步：用最少的直线覆盖所有“0”。 这里直线数等于3（等于4时可得最优解, 停止运算）。,第四步： 从矩阵未被直线覆盖的数字中找出一个最小数k并且减去k，矩阵中k5。 直线相交处的元素加上k，被直线覆盖而没有相交的元素不变，

29、得到矩阵C,5.4.2 解指派问题的匈牙利法,C=,92,第五步：覆盖所有零最少需要4条直线，表明矩阵中存在4个不同行不同列的零元素。第六步：找出独立的零元素,或,5.4.2 解指派问题的匈牙利法,C=,93,得到两个最优解,第一种方案：第一个工厂加工产品1，第二工厂加工产品3，第三个工厂加工产品4，第四个工厂加工产品2； 第二种方案：第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2； 单件产品总成本 Z5815025055513,5.4.2 解指派问题的匈牙利法,94,5.4.2 解指派问题的匈牙利法,【补充】求解下面指派问题,95,5.4.2 解指派问题

30、的匈牙利法,最少总费用 z=34万元,96,最大化指派问题应转化为最小化问题求解。效益矩阵C=(cij)，其中最大元素为m。令矩阵 B=(bij)= (m-cij)，则以B为效益矩阵的最小化指派问题和以C为效益矩阵的原最大化指派问题有相同最优解。人数和事数不等的指派问题，可添加虚拟的人或事，其系数取0，化为平衡指派问题。一个人可做几件事的指派问题，可将一个人视为相同的几个人，化为平衡指派问题。某事一定不能由某人做的指派问题，可将某人做某事所用的时间设为充分大的正数M 。,5.4.3 其它变异问题,97,5.4.3 其它变异问题,【例5-17】 求例5-15的最优分配方案,【解】,最优分配方案是

31、： 甲分配到B岗位；乙分配到A岗位；丙分配到D岗位；丁分配到C岗位； 总成绩为357,【例5-18】某商业集团计划在市内四个点投资四个专业超市，考虑的商品有电器、服装、食品、家俱及计算机5个类别。通过评估，家具超市不能放在第3个点，计算机超市不能放在第4个点，不同类别的商品投资到各点的年利润（万元）预测值见表5-31。该商业集团如何作出投资决策使年利润最大。,100,【解】 这是求最大值、人数与任务数不相等、不可接受的配置的一个综合指派问题，分别对表5-36进行转换。（1）令c43=c54=0（2）转换成求最小值问题，令M420，得到效率表 （机会损失表）（3）虚拟一个地点5,5.4.3 其它变异问题,0,0,102,Z=1350,最优投资方案：地点1投资建设计算机超市，地点2投资建设服装超市，地点3投资建设食品超市，地点4投资建设电器超市，不建家具超市。年利润总额预测值为1350万元,5.4.3 其它变异问题,最优解,103,1指派模型的特征2匈牙利法求解指派问题的条件3匈牙利法的两个基本定理4指派问题也是一个特殊的运输问题. 5将指派（分配）问题的效率矩阵每行分别加上一个数后最优解不变.,5.4 指 派 问 题,本节学习要点,