卫生管理运筹学课件04运输问题

运输问题薛迪复旦大学公共卫生学院医院管理学教研室TransportationProblem管理计划组织生产1生产2生产3销售1销售4销售2销售3原材料1原材料2原材料3原材料4物流第一节运输问题的数学模型例1：某制药公司在全国设有3个生产基地，其中某品种药的日产量为：A1厂700箱，A2厂400箱，A3厂900箱。这些生产基地每天将这些药分别运往四个地区的经销部门，各经销部门每天的需求量为：B1部门300箱，B2部门600箱，B3部门500箱，B4部门600箱。已知从每个生产基地到各销售部门每箱药品的运价如表所示，问该制药公司应如何调运，使在满足各销售部门需要的情况下，总的运输费用最少？表1各生产基地到各销售部门每箱药品的运费（单位：元）生产基地销售部门B1B2B3B4A10.31.10.31.0A20.10.90.20.8A30.70.41.00.5

表2运输表运输问题数学模型的特点（1）约束条件系数矩阵中元素等于0或1；（2）约束条件系数矩阵的每一列有两个非0元素，于每个变量在前m个约束方程和后n个约束方程中各出现一次相对应。对于产销平衡的运输问题，还有以下两个特点：（3）所有的结构约束方程都是等式；（4）各产地的产量之和等于各销地的销量之和。例1问题的运输表设X=（xij）为运输问题的一个解，则要求每步得到的X都必须是基本可行解，这就要求：（1）X必须满足模型中的所有约束条件；（2）基变量对应的约束方程组的系数列向量线性无关；（3）解中非0变量xij的个数不能多于（m+n-1）个；（4）基变量的个数在迭代过程中应该保持为（m+n-1）个。例1问题的一个基本可行解对于产销平衡的运输问题，我们有以下3条结论：（1）基变量有m+n-1个；（2）一定有最优解；（3）如果ai和bj都是整数，则一定有整数最优解。第二节表上作业法一、初始基本可行解的求法——最小元素法二、解的最优性检验——闭回路法11=c11-c21+c23-c13=0.3-0.1+0.2-0.3=0.131=c31-c21+c23-c13+c14-c34=0.7-0.1+0.2-0.3+1.0-0.5=1.0找出每一个空格(非基变量)的闭回路(只有一个顶点为空格，其他顶点均为填有数字的格)。

12=c12-c32+c34-c14=1.1-0.4+0.5-1.0=0.2

22=c22-c32+c34-c14+c13-c23=0.9-0.4+0.5-1.0+0.3-0.2=0.1

24=c24-c14+c13-c23=0.8-1.0+0.3-0.2=-0.1

33=c33-c34+c14-c13=1.0-0.5+1.0-0.3=1.2

注意：在运输问题中通常目标函数是求最小值，所以这时要求所有的检验数为正值。对于每一个非基变量，在运输表中唯一对应一条这样的闭回路。不能出现全部顶点由填有数字的格构成的闭回路。三、解的改进找出检验数ij为最小负值的格子的闭回路→在满足所有约束条件的情况下，尽可能增大这个格子的xij值→调整此闭回路上其他顶点的值→检验新解的最优性→重复上步骤直至得到最优解为止

改进的解和检验数注意1.退化问题：如果基本变量中至少有一个为零，则该问题为退化问题。2.结果应用文字表达，即写出运输方案。第三节产销不平衡的运输问题及其求解方法一、不平衡运输问题的数学模型在实际工作中经常有的情况，有时总产量大于总销量，有时总产量小于总销量，这类问题称为不平衡的运输问题。当总产量大于总销量时，其数学模型为：当总产量小于总销量时，其数学模型为：二、不平衡运输问题的求解方法[例2]设有三所社区医院，医生数分别为14、10和16人，在为4个居民区居民进行体检时，所需的医生数分别为6、12、8和4人，从各医院到各居民区每名医生的平均劳动成本见表4-12，问如何分配医生可以使总的劳动成本最低？表3各医院到各居民区每名医生的平均劳动成本（单位：元）医院居民区B1B2B3B4A140602080A250304060A370906040销地产地B1B2B3B4产量11x12x13x14A25030406010x21x22x23x24A37090604016x31x32x33x34销量61284表4各医院到各居民区的医生分配表销地产地B1B2B3B4B5产量A140602080014x11x12x13x14x15A250304060010x21x22x23x24x25A370906040016x31x32x33x34x35销量612841040表5各医院到各居民区的医生分配表对于总产量大于总销量的运输问题，我们可以增加一个假设的销地Bn+1，且该地的销量为：OBJECTIVEFUNCTIONVALUE1)1040.000VARIABLEVALUEX114.000000X122.000000X138.000000X140.000000X210.000000X2210.000000X230.000000X240.000000X312.000000X320.000000X330.000000X344.000000X150.000000X250.000000X3510.000000数学模型变为：

由于各产地调运到这个假设的销地的物品数量xi,n+1实际上是各产地存储的物品的数量，所以各产地到该销地的单位运输费用ci,n+1=0。销地产地B1B2…BnBn+1(存储)产量A1c11c12c1n0a1x11x12x1nx1,n+1A2c21c22C2n0a2x21x22x2nx2,n+1Amcm1cm2cmn0amxm1xm2xmnxm,n+1销量b1b2…bn表6总产量大于总销量的运输问题的运输表

类似地，对于总销量大于总产量的运输问题，我们可以假设有一个产地Am+1，它的产量等于：这个产地发往各个销地的物品数量xm+1,j实际上是各个销地所欠缺的物品数量。当然这个假设产地到各销地的单位运价cm+1,j都是等于0，数学模型变为：销地产地B1B2…Bn产量A1c11c12c1na1x11x12x1nA2c21c22c2na2x21x22x2nAmcm1cm2cmnamxm1xm2xmnAm＋1(欠缺)000xm+1,1xm+1,2xm+1,n销量b1b2…bn表7总销量大于总产量的运输问题的运输表第四节应用实例[例3]某药厂和药品销售公司签订了供货合同，已知该药厂各季度的生产能力、每件产品的生产成本和每季度末应该提供的产品件数（见下表），若药厂当季度末完成供给量，每件产品需支付保管费用100元，试问在遵守合同的情况下，该药厂该如何安排生产才能使年消耗成本最低？季度药厂生产能力(件)供货量(件)每件产品的成本(元)一30020012000二40025011000三35030011500四25025012500表8某药厂的生产能力及供货量表9生产成本Cij表生产季度供货季度一二三四一12000121001220012300二M110001110011200三MM1150011600四MMM12500

第i季度生产第j季度交货的每件产品的生产成本cij实际上是生产成本加上保管费用之和

第i季度生产第j季度交货的每件产品的生产成本cij实际上是生产成本加上保管费用之和解：用xij表示第i季度生产第j季度交货的药品件数则数学模型为：

交货季生产季一二三四t生产量一1200012100122001230003000x11x12x13x14x15二M110001110011200040000x22x23x24x25三MM11500116000350000x33x34x35四MMM1250002500000x44x45供货量20002500300025003000表10药厂供货问题的运输表OBJECTIVEFUNCTIONVALUE1)0.3355000E+08VARIABLEVALUEVARIABLEVALUEX110.000000X120.000000X130.000000X140.000000MX210.000000X220.000000X23500.000000X242500.000000MX310.000000MX320.000000X330.000000X340.000000MX410.000000MX420.000000MX430.000000X440.000000X153000.000000X211000.000000X250.000000X311000.000000X322500.000000X350.000000X410.000000X420.000000X432500.000000X450.000000[例4]某种产品有A1、A2、A3和A4三个产地，销售地为B1、B2、B3和B4，各产地到销售地间的单位运价如表4-19。四个销售地的需求量分别为40、60、90和70件。现要求产地A1必须供给70件产品；A2至少供给70件产品，但不能多于100件；A3至少供给60件产品；A4供给的产品不能多于90件。问应该如何在产销平衡的情况下调运产品，使总运费最少？表11某产品的单位运价表销地产地B1B2B3B4供给量A13352a1＝70A2443170a2100A33543a360A45262a490需求量40609070解：当A2、A4的供给量为最小值时，总供给量为140，而总需求量是260，故在产销平衡的条件下A3最大的供给量是120。如果产地A2、A3和A4的供给量都取最大值，总的供给量是380，大于总需求量，这时应该增加一个假设的销售地B5，其需求量是120。销地产地B1B2B3B4B5供给量A13352M70A24431M70A’24431030A33543M60A’33543060A45262090需求量40609070120表12例4的改进运输表OBJECTIVEFUNCTIONVALUE1)640.0000VARIABLEVALUEVARIABLEVALUEX110.000000X120.000000X130.000000X140.000000MX150.000000X210.000000X220.000000