[管理学]3运输问题.ppt

位势法计算检验数 ?ij = cij –(ui+vj ) ui代表产地Ai的位势量，vj代表销地Bj的位势量。 基变量的检验数为0，即?ij= cij –ui–vj =0， 并令u1 =0，计算各行各列的位势量。 基变量的检验数?ij= cij –ui – vj =0， 即cij =ui +vj ， 且令u1 =0，计算位势量ui和vj 计算非基变量的检验数?ij= cij –ui – vj 解：设xij为从i到j的运输量，可得到有下列特点的线性规划模型： 目标函数：Min z = 所有可能的运输费用（运输单价与运输量乘积之和） 约束条件： 对产地（发点） i ：输出量-输入量= 产量 对转运站（中转点）：输入量-输出量= 0 对销地（收点） j ：输入量-输出量= 销量 约束条件： s.t. x13+ x14 ≤ 600 (广州分厂供应量限制） x23+ x24+ x28 ≤ 400 (大连分厂供应量限制） -x13- x23 + x35 + x36+ x37 + x38 = 0 （上海销售公司，转运站） -x14- x24 + x45 + x46+ x47 + x48 = 0 （天津销售公司，转运站） x35+ x45 = 200 （南京的销量） x36+ x46 = 150 （济南的销量） x37+ x47 = 350 （南昌的销量） x38+ x48 + x28 = 300 （青岛的销量） xij ≥ 0 , i,j = 1,2,3,4,5,6,7,8 用软件求得结果： x13 = 550 x14 =50 ； x23 = 0 x24 = 100 x28 = 300 ； x35 = 200 x36 = 0 x37 = 350 x38 = 0 ； x45 = 0 x46 = 150 x47 = 0 x48 = 0 。 最小运输费用为：4600百元 作业 复习：运输问题 预习：整数规划 书面作业： P103-105：习题3.2，3.5， 3.7，3.11。 解:根据题意，作出产销平衡与运价表： 取 M 代表一个很大的正数，其作用是强迫相应的 x31、x33、x34取值为0。 例:设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表。试求总费用为最低的化肥调拨方案。 解：根据题意，作出产销平衡与运价表:最低要求必须满足，因此把相应的虚设产地运费取为 M ，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为 0 。对应 4”的销量 50 是考虑问题本身适当取的数据，根据产销平衡要求确定D的产量为 50。 例:某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。 解： 设xij为第i季度生产的第j季度交货的柴油机数目，那么应满足： 交货： 生产： x11 = 10 x11 + x12 + x13 + x14 ≤ 25x12 + x22 = 15 x22 + x23 + x24 ≤ 35x13 + x23 + x33 = 25 x33 + x34 ≤ 30x14 + x24 + x34 + x44 = 20 x44 ≤ 10 把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交货的柴油机数目看作第 j 个销售点的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题：目标函数：Min z= 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15