运筹学运输问题补例3.doc

运筹学运输问题补例一、运输问题是特殊的象形规划问题，其特殊性表现1、产销平衡运输问题总是存在可行解。就是一个。2、由于，目标函数有下界，故产销平衡运输问题必有最有解。3、求解过程要求每步得到的解是基可行解，意味着：解必须满足模型中所有约束条件；基变量对应的约束方程组的系数列向量线性无关；解中非零变量的个数不能大于个；为使迭代顺利进行，基变量的个数在迭代过程中保持为个。二、表上作业法：简单有效，其实质是单纯形法1、找出初始基本可行解（初始运输方案），常用最小元素法、西北角法、伏格尔法。2、求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。3、确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。4、重复步骤2、3，直到得到最优解为止。三、例11、最小元素法2、西北角法3、伏格尔法：每次都考虑最小运价与次最小运价的差额，差额越大的行或列，就最应该采用最小运价调运。当L1列销量满足时，就划掉第一列，继续用该方法做下去。3、解的最优性检验-闭回路法4、解的最优性检验-位势法由基变量的系数的个方程与取定某一个的值，其它的值就惟一确定了。对于非基变量，其检验数。5、解的改进如果某一个调运方案的所有空格的检验数都不小于0，则该调运方案是最优方案。调整的方法：从检验数是负值（有多个取绝对值最大的一个）的空格出发。四、例2两个水厂将自来水供应三个小区，每天个水厂的供应量与各小区的需求量以及各水厂调运到各小区的供水单价见下表。应如何安排供水方案，使总水费最小？供应量/ t1064170756200需求量/ t16090120370解 第一，分别用三种方法求出初始方案1、最小元素法的基本思想是“就近供应”。每次总选择剩余运价中最小的点作为数字格。2、西北角法：与最小元素法不同的是，不考虑运价的大小，而是直接人为地每次读从左上决的位置确定数字格及其值。与最优方案差距大，但有规律，实现简单，易编程。3、伏格尔法：考虑最小运价与次最小运价的差额，差额越大的行或列，就应该采用最小运价调运。每次总选择剩余运价中在差额最大处选择最小运价来作为数字格确定运量。第二，最优解的判别：计算空格（非基变量）的检验数，一般的问题都市求最小，所以当时，方案为最优方案。以下以最小元素法得出的初始方案为基础求检验数。1、闭回路法这里，有检验数-2小于零，不是最优方案，有待调整改正。2、位势法由基变量的系数的个方程与取定某一个的值，其它的值就惟一确定了。对于非基变量，其检验数。由，令，得，从而，第三，非最优方案的闭回路调整在所有负值的检验数中，选其中最小的负检验数所在的空格为调整格（入基变量），运用闭回路调整法进行调整。调整的方法：从调整格（作为第一个顶点）出发，奇数顶点的增加调整量，偶数顶点减少，的值为闭回路中偶数顶点上个数字格中数值最小的。调运后的方案的所有空格的检验数都不小于0，从而该调运方案是最优方案。最优方案的总运费为z=300+480+1120+200=2100五、例3 已知三个产地，四个销地的产销量级单位运价如表所示，求使总运费最小的调运方案。解 该方案为最优解，总运费6000。但不是惟一的最优解。见下表六、例4 已知三个产地，四个销地的产销量级单位运价如表所示，求使总运费最小的调运方案。解 这个产销不平衡问题，需要增加一个虚拟销地，得如下表七、例5 已知运输问题的产销平衡表、单位运价表及最优调运方案集中于下表，试回答下列问题：（1）从的运价在什么范围内变动时，这个最优调运方案不变？（2）的运价变为何值时，有无穷多最优调运方案？请至少给出两个调运方案来。解 （1）以单位运价表计算的基变量的检验数为0且非基变量检验数非负时，调运方案不变。假定未知，用位势法求各个空格的检验数如下表：欲使所有非基变量的检验数非负，则有，解得。所以从的运价在3与10之间变动时，这个最优调运方案不变。（2）当存在非基变量的检验数为0时，有无穷多最优解。设的运价未知，用位势法求各个空格的检验数如下表：由设得。所以当的运价变为17时，有无穷多最优调运方案。把作为调入格，以此格为出发点，作一闭回路，如下表调入量分别在区间中取5，10，即可得出两个最优调运方案来。八、例6 某百货公司其外地三个城市采购四种规格的服装，由于这些城市的服装质量、运价和销售情况不同，预计售后利润（元/套），有关资料见下表。请帮助该公司确定一个预期盈利最大的采购方案。解 用最大单位利润10减去表上利润数字，转化为求最小的运输问题，如下表：此方案即为最优方案， 按此方案采购可得最大盈利72000元。九、转运问题已知三个工厂生产同一规格的产品，用相同价格供应三个销售网点销售。有两个转运站，并且产品的运输允许在各产地、各销地及各转运站之间相互转运。已知各产地、销地、中转站相互之间的每吨货物的单位运价和产销量如下表。产地转运站销地产量30产地862-4108108513959206542287转运站2148463-328232销地49242-5105863-48973254销量153510解 转运问题比一般运输问题复杂，要将其化成一个等价的扩大运输问题，应做如下处理：（1）将所有的产地、转运站和销地都作为产地，也作为销地；（2）对扩大的运输问题建立运价表。对于没有运输路线的取任意大的正数；对于给自己运输的，运价计为0；（3）所有转运站的产量等于销量，但事先又无法知道该数量的确切值，因此可以将调运总量（即总产量或总销量）作为该数值的上界；（4）在扩大的运输问题中，原来的产地和销地由于也具有了转运的作用，所以在原来的产量与销量的数值再加上调运总量；同时原来各产地的销量、原各销地的产量均取为调运总量。得如下扩大的运输问题的产销平衡运输表：产地转运站销地产量90产地0862M41087080513959806504228760转运站2140846360M328023260销地492420M560105863M04608973254060销量6060606060759570用表上作业法可得最优方案表：产地转运站销地产量90产地601515705515805602060转运站451060402060销地606060606060销量6060606060759570由于是松弛变量，所以实际运量=产量（或销量）-，实际最优运输路线如下图，最小总运费为300。十、生产计划问题例1、饮料厂生产一种水果饮料，由于产品与季节关系密切，其生产能力与成本在每个季节独有区别；同时，已知饮料厂全年每季度的订货数量，见下表。如果生产出的饮料本季度不交货，没存储一个季度，每罐饮料的存储费为0.1元。要求在完成订货供应的前提下，制定饮料厂全年生产总费用最低的生产方案。一季度二季度三季度四季度生产能力/万罐50645620生产成本（元/罐）8.89.19.09.4订货数量/万罐20284535解 由于每个季度生产出来的饮料不一定当季交货，设为第季度生产第季度交货的数量。根据满足订货要求与生产能力约束，有及实际成本是生产成本本加上存储费，不存在的诸如二季度生产一季度交货情况，即当时，取。得总费用表一季度二季度三季度四季度一季度8.88.99.09.1二季度M9.19.29.3三季度MM9.09.1四季度MMM9.4于是，目标函数为该问题实际上属于产销不平衡运输问题，虚拟一个销地，形成如下产销平衡运输问题一季度二季度三季度四季度虚拟交货生产能力/万罐一季度8.88.99.09.1050二季度M9.19.29.3064三季度MM9.09.1056四季度MMM9.4020订货数量/万罐2028453562190用表上作业法可得最优方案表：一季度二季度三季度四季度虚拟交货生产能力/万罐一季度2028250二季度224264三季度213556四季度2020订货数量/万罐2028453562190在生产能力中扣除虚拟订货后才是实际生产量。故一季度生产50万罐，二季度生产22万罐，三季度生产56万罐，四季度生产0罐，生产存储最低总费用为1153.1万元例2、某造船厂根据合同要从当年起连续三年末各提供三条规格型号相同的大型客货轮。已知该厂这三年生产大型客货轮的能力和每艘客货轮的成本如下表所示。已知加班生产时，每艘客货轮的成本比正常生产时高出70万元。又知造出来的客货轮如当年不交货，每艘每积压一年造成积压损失为40万元。在签订合同时，该厂已储存了两艘客货轮，而该厂希望在第三年末完成合同后还能储存一艘备用。问该厂应如何安排生产，在满足上述要求的前提下，总的生产费用与积压损失为最小？年度正常生产时间内可完成的客货轮数加班生产时间内可完成的客货轮数正常生产时每艘客货轮的成本（万元）123500242600313550解 设为第年度生产用于第年度交货的艘数。根据满足订货要求与生产能力约束，为第年可供货的船，列出产销平衡及单位造价表如下。1234产量4080120025005405800257061065003M60064004M67071002MM55001MM62003需求3347用伏格尔法求出初始解如下表1234产量20222111344221133需求3347该厂应安排第一年生产2艘，第二年生产2艘，第三年生产4艘，在满足要求的前提下，总的生产费用与积压损失为80+500+540+1200+550+1860=4730万元最小。例3、甲乙丙三个城市每年需要煤炭分别为：320、250、350万吨，由A、B两处煤矿负责供应。已知煤炭年供应量分别为：A400万吨，B450万吨。由煤矿至各城市的单位运价（万元/万吨）见下表。由于需大于供，经研究平衡决定，甲城市供应量可减少030万吨，乙城市需要量应全部满足，丙城市供应量不少于270万吨。试求将供应量分配完，又使总运费最低的调运方案。甲乙丙A151822B212516解 由于供需不平衡，虚拟一个矿C，其供应量为缺口70万吨，另外要把可调控部分分开来。按照此方案调运，满足要求且运费最少，为14650万元。十一、判别下列两表中给出的调运方案能否作为用表上作业法求解时的初始解？为什么？表1产地 销地1234产量1015152151025355销量5151510表2