1、2021/3/301第4章 运输问题和指派问题 运输问题和指派问题是实际中碰到的比较常见的一类线性规划问题，它们在变量的取值、约束条件的系数矩阵等具有一定的特殊性，所以可以找到比单纯形法更为简便的求解方法。22021/3/304.1 运输问题模型及表上作业法求解111,2,.,. .1,2,.,01,2,.,;1,2,.,nijijmijjiijxaims txbjnxim jnB1B2BnA1A2A3c11c21cm1c12c22cm2c1nc2ncmn单位运价表单位运价表(cij) B1B2 Bn产量产量A1A2Amx11X21xm1x12X22xm2x1nX2nxmna1a2am销量销量
2、b1b2bn产销平衡表（决策变量产销平衡表（决策变量xij=0或或1)11minmnijijijzc x产销平衡的运输问题产销平衡的运输问题:精品资料42021/3/30 你怎么称呼老师？ 如果老师最后没有总结一节课的重点的难点，你是否会认为老师的教学方法需要改进？ 你所经历的课堂，是讲座式还是讨论式？ 教师的教鞭 “不怕太阳晒，也不怕那风雨狂，只怕先生骂我笨，没有学问无颜见爹娘 ” “太阳当空照，花儿对我笑，小鸟说早早早”52021/3/30运输问题的表上作业法n表上作业法是一种简便而有效的方法表上作业法是一种简便而有效的方法,实质是单纯实质是单纯形法形法.n例例4.1某公司下属有三个加工厂
3、某公司下属有三个加工厂A1,A2,A3生产化肥生产化肥,负责供负责供应应B1,B2,B3,B4四个地区所需化肥，各厂化肥产量及各地区四个地区所需化肥，各厂化肥产量及各地区所需化肥、各化肥厂到各地区所的运输距离见下表：所需化肥、各化肥厂到各地区所的运输距离见下表：单位单位 销地销地运价运价 产地产地B1B2B3B4产量产量(吨吨)A13113107A219284A2741059销量销量(吨吨)3656单位运价表单位运价表(元元) 产销平衡表产销平衡表 B1B2B3B4产量产量(吨吨)A1x11x12x13x147A2x11x12x13x144A2x11x12x13x149销量销量(吨吨)3656
4、销地销地运量运量产地产地62021/3/30给出初始解给出初始解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单位
5、运价表单位运价表72021/3/30解的最优性检验解的最优性检验n解的最优性检验主要有闭回路解的最优性检验主要有闭回路法和位势法法和位势法,我们只介绍我们只介绍位势法位势法.n位势法位势法:n(1)把产销平衡表中初始方案中把产销平衡表中初始方案中有数字格对应的运价写到检验有数字格对应的运价写到检验数表中数表中;n(2)对运输表上的每一行对运输表上的每一行(列列)赋赋予一个数值予一个数值ui(vj),称为位势称为位势.各格各格子的位势等于行位势与列位势子的位势等于行位势与列位势之和之和.n(3)求出检验数求出检验数:ij=cij-(ui+vj)B1B2B3B4(ui)A1(3)0(10)0A2(
6、1)0(2)0A3(4)0(5)0(vj)2-13010-59B1B2B3B4A1311310A21928A374105单位运价表单位运价表位势法检验数计算表位势法检验数计算表(3)1(11)2(9)1(8)-1(7)10(10)1282021/3/30运输方案的改进运输方案的改进n当所有当所有ij0,即为即优即为即优.当当ijbj时时, 用产销平衡的数学模型用产销平衡的数学模型,其约束其约束会产生矛盾会产生矛盾.此时模型应改为此时模型应改为:111,2,.,. .1,2,.,01,2,.,;1,2,.,nijijmijjixaimstxbjnxijim jn11minmnijijijzc x
7、若用表上作业法求之若用表上作业法求之,可设一个假想销地可设一个假想销地, 使其销使其销量为量为bn+1=ai-bj,ci,n+1=0.1111,2,.,. .1,2,.,101,2,.,;1,2,.,1nijijmijjixaimstxbjnxijim jn11minmnijijijzc x122021/3/301234生产能力生产能力110.810.9511.1011.2525211.1011.2511.4035311.011.530411.310需量需量10152520例例4.2 按合同供货的生产计划问题（按合同供货的生产计划问题（P109）季度季度生产的能力（台）生产的能力（台）生产成本
8、费（万元）生产成本费（万元）1 1252510.810.82 23511.111.13 33011.04 41011.311.3生产能力与生产成本生产能力与生产成本某厂按合同规定于当年每季度未分别提供10、15、25、20台同一规格柴油机。已知该厂的生产能力与生产成本如下表。若生产出的产品当季不交货，则需储存、维护等费用1500元。要求在完成合同的情况下，做出全年生产费用最小的决策。分析：由题设我们可得第i季度生产，第j季度交货的成本如下表，因此可看成是供大于求的运输问题。交货季度交货季度j生产季度生产季度i交货的成本交货的成本132021/3/301234生产生产能力能力1x11x12x13
9、x14252x21x22x23x24353x31x32x33x34304x41x42x43x4410需量需量10152520交货季度交货季度j生产季度生产季度i设xij表示第i季度生产，第j季度交货的柴油机数量，则产销表产销表用用Excel求解求解142021/3/300 0 0am+1Am+1111,2,.,. .1,2,.,01,2,.,;1,2,.,nijijmijjixaimstxbjnxijim jn11minmnijijijzc x产销平衡产销平衡:B1B2Bn产量产量A1A2Amc11c21cm1 c12c22cm2c1nc2ncmna1a2am销量销量b1b2bn产量小于销量产
10、量小于销量当当aibj时时, 用产销平衡的数学模型用产销平衡的数学模型,其约束其约束会产生矛盾会产生矛盾.此时模型应改为此时模型应改为:111,2,.,. .1,2,.,01,2,.,;1,2,.,nijijmijjixaimstxbjnxijim jn11minmnijijijzc x若用表上作业法求之若用表上作业法求之,可设一个假想产地可设一个假想产地, 使其销使其销量为量为am+1=bj-ai,cm+1,j=0.1111,2,.,1. .1,2,.,01,2,.,1;1,2,.,nijijmijjixaimstxbjnxijimjn11minmnijijijzc x152021/3/30
11、 销地销地产地产地B1B2B3产量产量A113151278A211292245销量销量533665产量小于销量运输问题的产量小于销量运输问题的Excel求解（求解（P113例例4.3)1. ExcelORM线性规划线性规划运输运输问题问题目标目标min,销地数销地数4,产地数产地数3,生成电子表模型生成电子表模型用用Excel求解求解162021/3/30 产品产品工厂工厂B1B2B3B4生产生产能力能力A14127282475A24029-2375A33730272145需求需求20303040变形运输问题的变形运输问题的Excel求解（求解（P115例例4.4)1. ExcelORM线性规
12、划线性规划运输运输问题问题目标目标min,销地数销地数4,产地数产地数3,销量有弹性，生成电子表模型销量有弹性，生成电子表模型用用Excel求解求解172021/3/30 销地销地产地产地B1B2B3B4产量产量A1554246538000A2371832485000A3295951357000最低需求最低需求最高需求最高需求70007000300090002000600008000需求有弹性的运输问题的需求有弹性的运输问题的Excel求解（求解（P117例例4.5)1. ExcelORM线性规划线性规划运输运输问题问题目标目标min,销地数销地数4,产地数产地数3,销量有弹性，生成电子表模型
13、销量有弹性，生成电子表模型用用Excel求解求解182021/3/30运价运价1 2 n n+1 库存量库存量1p11p12p1np1n+1p21p22p2np2n+12 p11p12p1np1n+1m需量需量例例战备物资的调运战备物资的调运1a2ama2b1bnb1nb但有转运问题，pij与转运方式有关。有转运的运输问题有转运的运输问题192021/3/30设xk（ =0或1）表示第k个中转站启用次数，xik表示从第i个仓库运到第k个中转站的物资数量，ykj表示从第k个中转站运到第j个单位的物资数量，则miinjkjikpkjkjmikkikpkiikpknjkjkjmipkikikpkkk
14、pkayxnjbypkxcxmiaxtsyexdxfz1111111111)(, 2 , 1)(, 2 , 1)(, 2 , 1)(, 2 , 1. .转运平衡约束需求约束中转能力约束库存约束202021/3/30运输问题小结B1B2Bn产量A1A2A3x11x21xm1x12x22xm2x1nx2nxmna1a2am销量b1b2bn111,2,.,.1,2,.,01,2,., ;1,2,.,nijijmijjixaimstxbjnxijim jn11minmnijijijzc x111,2,.,.1,2,.,01,2,., ;1,2,.,nijijmijjixaimstxbjnxijim j
15、n11minmnijijijzc x111,2,.,.1,2,.,01,2,., ;1,2,.,nijijmijjixaimstxbjnxijim jn11minmnijijijzc x1.运输问题由一个产销平衡表和一个单位运价表构成运输问题由一个产销平衡表和一个单位运价表构成.B1B2 BnA1A2A3c11c21cm1c12c22cm2c1nc2ncmn()()( )()ijmnijmnimjnXxCcaabb决策变量矩阵单位运价矩阵产量行向量销量列向量2.运输问题数学模型运输问题数学模型产销平衡产销平衡产大于销产大于销产小于销产小于销3.表上作业法表上作业法:最小元素法给出初始方案、位势
16、法求检验数、闭回路法调整方案最小元素法给出初始方案、位势法求检验数、闭回路法调整方案5.非地理问题转化为运输问题非地理问题转化为运输问题4. 依据数学模型，用依据数学模型，用Excel求解。求解。212021/3/30指派问题（分派问题）（指派问题（分派问题）（Assignment problem） 若需完成n项任务，分配给n个人承担。由于每人的专长、能力不同，各人完成任务的收益、成本也不同。于是产生应指派哪个人去完成哪项任务，才能使完成n项任务的总成本最低或总收益最高。这类问题统称为指派问题。指派问题。指派问题的假设指派问题的假设 1. 被指派者的数量和任务的数量是相同的； 2. 每个人只完
17、成一项任务； 3. 每项任务只能由一个人来完成； 4.每个人和每项任务的组合都会有一个相关成本（收益）； 5.目标总成本或总收益值是根据任务指派确定。222021/3/30某单位有n项任务需要n个人去完成，每个人仅能完成一项任务，每项任务仅要一人去完成，每个人完成不同的任务效率不同（见表4-1），问如何安排任务可使任务完成效率最高？111max11,2,.,. .11,2,.,0,1; ,1,2,.,nnijijj i inijjnijiizc xxins txjnxi jn设xij表示安排第i个人去完成第j项任务，则232021/3/30指派问题的模型指派问题的模型n一般指派问题的数学模型 它可看作一种特殊的运输问题。只是这里要求ai=bj=1,且xij=0,1.因此其有类似于运输问题的变形问题，处理技巧也类似。242021/3/30 工作所需时间工作所需时间人员人员ABCD每小时工每小时工资（元）资（元）13541274014247453251123395636431343251254615指派问题的指派问题的Excel求解（求解（P126例例4.8)1. ExcelORM线性规划线性规划分配分配问题问题目标目标min,任务数任务数4,人员数人员数4,生成电子表模型生成电子表模型用用Excel求解求解
