运筹学 运输与指派问题.ppt

1、第4章 运输问题和指派问题,运输问题和指派问题是实际中碰到的比较常见的一类线性规划问题，它们在变量的取值、约束条件的系数矩阵等具有一定的特殊性，所以可以找到比单纯形法更为简便的求解方法。,4.1 运输问题模型及表上作业法求解,单位运价表(cij),产销平衡表（决策变量xij=0或1),产销平衡的运输问题:,运输问题的表上作业法,表上作业法是一种简便而有效的方法,实质是单纯形法. 例4.1某公司下属有三个加工厂A1,A2,A3生产化肥,负责供应B1,B2,B3,B4四个地区所需化肥，各厂化肥产量及各地区所需化肥、各化肥厂到各地区所的运输距离见下表：,单位 销地,单位运价表(元),产销平衡表,销地

2、,运量 产地,给出初始解,给出初始解有西北角法、最小元素法和Vogel法,我们只介绍比较简单的最小元素法. 步骤:在产销平衡的前提下,运价低的优先安排调运.,3,1,4,6,3,3,最小元素法初始方案,单位运价表,解的最优性检验,解的最优性检验主要有闭回路法和位势法,我们只介绍位势法. 位势法: (1)把产销平衡表中初始方案中有数字格对应的运价写到检验数表中; (2)对运输表上的每一行(列)赋予一个数值ui(vj),称为位势.各格子的位势等于行位势与列位势之和. (3)求出检验数:ij=cij-(ui+vj),2,-1,3,0,10,-5,9,单位运价表,位势法检验数计算表,(3)1,(11)

3、2,(9)1,(8)-1,(7)10,(10)12,运输方案的改进,当所有ij0,即为即优.当ij0时,由闭回路法修改方案. 闭回路法: (1)找到最小的负检验数,其对应的变量为入基变量. (2)从入基变量对应的格子出发,遇到有数字的格子可以转90（也可不转）,直到回到出发点,形成闭回路. (3)根据供应量与需求量总量不变的原则,调整供需关系.,0+,3-,4+,1-,因供给非负,所以=1,得新供给方案,运输方案的改进,单位运价表,0,3,10,-2,3,-5,9,(3) 0,(11)2,(9)2,(2)1,(7)9,(10)12,2,1,3,至此,检验数全部大于0, 调整后的方案为已为最优方

4、案. 总运费=3*5+10*2+1*3+8*1+4*6+5+3 =85,4.2:产销平衡运输问题的Excel求解,1. ExcelORM线性规划运输问题目标min,销地数4,产地数3,生成电子表模型,2.输入单位运价、产量与销量,3.设置规划求解参数对话框,4.求解,0 0 0,bn+1,Bn+1,4.3 产销不平衡运输问题,产销平衡:,产量大于销量,当aibj时, 用产销平衡的数学模型,其约束会产生矛盾.此时模型应改为:,若用表上作业法求之,可设一个假想销地, 使其销量为bn+1=ai-bj,ci,n+1=0.,例4.2 按合同供货的生产计划问题（P109）,生产能力与生产成本,某厂按合同规

5、定于当年每季度未分别提供10、15、25、20台同一规格柴油机。已知该厂的生产能力与生产成本如下表。若生产出的产品当季不交货，则需储存、维护等费用1500元。要求在完成合同的情况下，做出全年生产费用最小的决策。,分析：由题设我们可得第i季度生产，第j季度交货的成本如下表，因此可看成是供大于求的运输问题。,交货季度j,生产季度i,交货的成本,交货季度j,生产季度i,设xij表示第i季度生产，第j季度交货的柴油机数量，则,产销表,用Excel求解,0 0 0,am+1,Am+1,产销平衡:,产量小于销量,当aibj时, 用产销平衡的数学模型,其约束会产生矛盾.此时模型应改为:,若用表上作业法求之,

6、可设一个假想产地, 使其销量为am+1=bj-ai,cm+1,j=0.,产量小于销量运输问题的Excel求解（P113例4.3),1. ExcelORM线性规划运输问题目标min,销地数4,产地数3,生成电子表模型,用Excel求解,变形运输问题的Excel求解（P115例4.4),1. ExcelORM线性规划运输问题目标min,销地数4,产地数3,销量有弹性，生成电子表模型,用Excel求解,需求有弹性的运输问题的Excel求解（P117例4.5),1. ExcelORM线性规划运输问题目标min,销地数4,产地数3,销量有弹性，生成电子表模型,用Excel求解,例战备物资的调运,但有转运

7、问题，pij与转运方式有关。,有转运的运输问题,设xk（ =0或1）表示第k个中转站启用次数，xik表示从第i个仓库运到第k个中转站的物资数量，ykj表示从第k个中转站运到第j个单位的物资数量，则,运输问题小结,1.运输问题由一个产销平衡表和一个单位运价表构成.,2.运输问题数学模型,产销平衡,产大于销,产小于销,3.表上作业法:最小元素法给出初始方案、位势法求检验数、闭回路法调整方案,5.非地理问题转化为运输问题,4. 依据数学模型，用Excel求解。,指派问题（分派问题）（Assignment problem） 若需完成n项任务，分配给n个人承担。由于每人的专长、能力不同，各人完成任务的收

8、益、成本也不同。于是产生应指派哪个人去完成哪项任务，才能使完成n项任务的总成本最低或总收益最高。这类问题统称为指派问题。 指派问题的假设 1. 被指派者的数量和任务的数量是相同的； 2. 每个人只完成一项任务； 3. 每项任务只能由一个人来完成； 4.每个人和每项任务的组合都会有一个相关成本（收益）； 5.目标总成本或总收益值是根据任务指派确定。,某单位有n项任务需要n个人去完成，每个人仅能完成一项任务，每项任务仅要一人去完成，每个人完成不同的任务效率不同（见表4-1），问如何安排任务可使任务完成效率最高？,设xij表示安排第i个人去完成第j项任务，则,指派问题的模型,一般指派问题的数学模型,

9、它可看作一种特殊的运输问题。只是这里要求ai=bj=1,且xij=0,1. 因此其有类似于运输问题的变形问题，处理技巧也类似。,指派问题的Excel求解（P126例4.8),1. ExcelORM线性规划分配问题目标min,任务数4,人员数4,生成电子表模型,用Excel求解,例 2011全国大学生数学建模竞赛 B题 交巡警服务平台的设置与调度,根据该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图和相关的数据信息得各交巡警服务平台到各路口的最短距离表。请为各交巡警服务平台分配管辖范围，使各平台管辖范围内的路口数尽量均衡，同时使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/