运筹学-运输与指派问题.pptx

第4章 运输问题和指派问题 运输问题和指派问题是实际中碰到的比较常见的一类线性规划问题，它们在变量的取值、约束条件的系数矩阵等具有一定的特殊性，所以可以找到比单纯形法更为简便的求解方法。4.1 运输问题模型及表上作业法求解B1B2BnA1A2A3c11c21cm1c12c22cm2c1nc2ncmn单位运价表单位运价表(cij)B1B2 Bn产量产量A1A2Amx11X21xm1x12X22xm2x1nX2nxmna1a2am销量销量b1b2bn产销平衡表（决策变量产销平衡表（决策变量xij=0或或1)产销平衡的运输问题产销平衡的运输问题:运输问题的表上作业法n表上作业法是一种简便而有效的方法表上作业法是一种简便而有效的方法,实质是单纯实质是单纯形法形法.n例例4.1某公司下属有三个加工厂某公司下属有三个加工厂A1,A2,A3生产化肥生产化肥,负责供负责供应应B1,B2,B3,B4四个地区所需化肥，各厂化肥产量及各地区四个地区所需化肥，各厂化肥产量及各地区所需化肥、各化肥厂到各地区所的运输距离见下表：所需化肥、各化肥厂到各地区所的运输距离见下表：单位单位 销地销地运价运价 产地产地B1B2B3B4产量产量(吨吨)A13113107A219284A2741059销量销量(吨吨)3656单位运价表单位运价表(元元)产销平衡表产销平衡表 B1B2B3B4产量产量(吨吨)A1x11x12x13x147A2x11x12x13x144A2x11x12x13x149销量销量(吨吨)3656销地销地运量运量产地产地给出初始解给出初始解n给出初始解有西北给出初始解有西北角法、最小元素法角法、最小元素法和和Vogel法法,我们只我们只介绍比较简单的介绍比较简单的最最小元素法小元素法.n步骤步骤:在产销平衡的在产销平衡的前提下前提下,运价低的优运价低的优先安排调运先安排调运.B1B2B3B4产量产量A1(3)(11)(3)(10)7A2(1)(9)(2)(8)4A3(7)(4)(10)(5)9销量销量3656314633最小元素法初始方案最小元素法初始方案产产 销销B1B2B3B4产量产量A1A2A3317119432101085749销量销量365620 20单位运价表单位运价表解的最优性检验解的最优性检验n解的最优性检验主要有闭回路解的最优性检验主要有闭回路法和位势法法和位势法,我们只介绍我们只介绍位势法位势法.n位势法位势法:n(1)把产销平衡表中初始方案中把产销平衡表中初始方案中有数字格对应的运价写到检验有数字格对应的运价写到检验数表中数表中;n(2)对运输表上的每一行对运输表上的每一行(列列)赋赋予一个数值予一个数值ui(vj),称为位势称为位势.各格各格子的位势等于行位势与列位势子的位势等于行位势与列位势之和之和.n(3)求出检验数求出检验数:ij=cij-(ui+vj)B1B2B3B4(ui)A1(3)0(10)0A2(1)0(2)0A3(4)0(5)0(vj)2-13010-59B1B2B3B4A1311310A21928A374105单位运价表单位运价表位势法检验数计算表位势法检验数计算表(3)1(11)2(9)1(8)-1(7)10(10)12运输方案的改进运输方案的改进n当所有当所有ij0,即为即优即为即优.当当ijbj时时,用产销平衡的数学模型用产销平衡的数学模型,其约束其约束会产生矛盾会产生矛盾.此时模型应改为此时模型应改为:若用表上作业法求之若用表上作业法求之,可设一个假想销地可设一个假想销地,使其销使其销量为量为bn+1=ai-bj,ci,n+1=0.1234生产能力生产能力110.810.9511.1011.2525211.1011.2511.4035311.011.530411.310需量需量10152520例例4.2 按合同供货的生产计划问题（按合同供货的生产计划问题（P109）季度季度生产的能力（台）生产的能力（台）生产成本费（万元）生产成本费（万元）1 1252510.810.82 23511.111.13 33011.04 41011.311.3生产能力与生产成本生产能力与生产成本某厂按合同规定于当年每季度未分别提供10、15、25、20台同一规格柴油机。已知该厂的生产能力与生产成本如下表。若生产出的产品当季不交货，则需储存、维护等费用1500元。要求在完成合同的情况下，做出全年生产费用最小的决策。分析：由题设我们可得第i季度生产，第j季度交货的成本如下表，因此可看成是供大于求的运输问题。交货季度交货季度j生产季度生产季度i交货的成本交货的成本1234生产生产能力能力1x11x12x13x14252x21x22x23x24353x31x32x33x34304x41x42x43x4410需量需量10152520交货季度交货季度j生产季度生产季度i设xij表示第i季度生产，第j季度交货的柴油机数量，则产销表产销表用用Excel求解求解0 0 0am+1Am+1产销平衡产销平衡:B1B2Bn产量产量A1A2Amc11c21cm1 c12c22cm2c1nc2ncmna1a2am销量销量b1b2bn产量小于销量产量小于销量当当aibj时时,用产销平衡的数学模型用产销平衡的数学模型,其约束其约束会产生矛盾会产生矛盾.此时模型应改为此时模型应改为:若用表上作业法求之若用表上作业法求之,可设一个假想产地可设一个假想产地,使其销使其销量为量为am+1=bj-ai,cm+1,j=0.销地销地产地产地B1B2B3产量产量A113151278A211292245销量销量533665产量小于销量运输问题的产量小于销量运输问题的Excel求解（求解（P113例例4.3)1.ExcelORM线性规划线性规划运输运输问题问题目标目标min,销地数销地数4,产地数产地数3,生成电子表模型生成电子表模型用用Excel求解求解 产品产品工厂工厂B1B2B3B4生产生产能力能力A14127282475A24029-2375A33730272145需求需求20303040变形运输问题的变形运输问题的Excel求解（求解（P115例例4.4)1.ExcelORM线性规划线性规划运输运输问题问题目标目标min,销地数销地数4,产地数产地数3,销量有弹性，生成电子表模型销量有弹性，生成电子表模型用用Excel求解求解 销地销地产地产地B1B2B3B4产量产量A1554246538000A2371832485000A3295951357000最低需求最低需求最高需求最高需求70007000300090002000600008000需求有弹性的运输问题的需求有弹性的运输问题的Excel求解（求解（P117例例4.5)1.ExcelORM线性规划线性规划运输运输问题问题目标目标min,销地数销地数4,产地数产地数3,销量有弹性，生成电子表模型销量有弹性，生成电子表模型用用Excel求解求解运价运价1 2 n n+1 库存量库存量1p11p12p1np1n+1p21p22p2np2n+12 p11p12p1np1n+1m需量需量例例战备物资的调运战备物资的调运但有转运问题，pij与转运方式有关。有转运的运输问题有转运的运输问题设xk（=0或1）表示第k个中转站启用次数，xik表示从第i个仓库运到第k个中转站的物资数量，ykj表示从第k个中转站运到第j个单位的物资数量，则运输问题小结B1B2Bn产量A1A2A3x11x21xm1x12x22xm2x1nx2nxmna1a2am销量b1b2bn1.运输问题由一个产销平衡表和一个单位运价表构成运输问题由一个产销平衡表和一个单位运价表构成.B1B2 BnA1A2A3c11c21cm1c12c22cm2c1nc2ncmn2.运输问题数学模型运输问题数学模型产销平衡产销平衡产大于销产大于销产小于销产小于销3.表上作业法表上作业法:最小元素法给出初始方案、位势法求检验数、闭回路法调整方案最小元素法给出初始方案、位势法求检验数、闭回路法调整方案5.非地理问题转化为运输问题非地理问题转化为运输问题4.依据数学模型，用依据数学模型，用Excel求解。求解。指派问题（分派问题）（指派问题（分派问题）（Assignment problem）若需完成n项任务，分配给n个人承担。由于每人的专长、能力不同，各人完成任务的收益、成本也不同。于是产生应指派哪个人去完成哪项任务，才能使完成n项任务的总成本最低或总收益最高。这类问题统称为指派问题。指派问题。指派问题的假设指派问题的假设 1.被指派者的数量和任务的数量是相同的；2.每个人只完成一项任务；3.每项任务只能由一个人来完成；4.每个人和每项任务的组合都会有一个相关成本（收益）；5.目标总成本或总收益值是根据任务指派确定。某单位有n项任务需要n个人去完成，每个人仅能完成一项任务，每项任务仅要一人去完成，每个人完成不同的任务效率不同（见表4-1），问如何安排任务可使任务完成效率最高？设xij表示安排第i个人去完成第j项任务，则指派问题的模型指派问题的模型n一般指派问题的数学模型 它可看作一种特殊的运输问题。只是这里要求ai=bj=1,且xij=0,1.因此其有类似于运输问题的变形问题，处理技巧也类似。工作所需时间工作所需时间人员人员ABCD每小时工每小时工资（元）资（元）13541274014247453251123395636431343251254615指派问题的指派问题的Excel求解（求解（P126例例4.8)1.ExcelORM线性规划线性规划分配分配问题问题目标目标min,任务数任务数4,人员数人员数4,生成电子表模型生成电子表模型用用Excel求解求解例例 2011全国大学生数学建模竞赛全国大学生数学建模竞赛 B题题 交巡警服务平台的设置与调度交巡警服务平台的设置与调度根据该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图和相关的数据信息得各交巡警服务平台到各路口的最短距离表。请为各交巡警服务平台分配管辖范围，使各平台管辖范围内的路口数尽量均衡，同时使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。分析：这是一个为平台分配多任务的问题。设dij是平台i到路口j的最短距离,xij表示使用平台i负责路口j.则各平台管辖范围内的路口数尽量均衡 各平台出警时间尽量在3分钟之内赶到出事路口 每一个路口必须有而且仅由一个平台管辖因决策变量太多只能用Lingo求解