运筹学运输问题表上作业法.ppt

* * * 生产与储存问题 某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用0.15万元。要求在完成合同的情况下，作出使该厂全年生产费用(包括储存、维护费用) 最小的方案。 解：由于每个季度生产出来的柴油机不一定当季交货，所以设xij为第i季度生产的用于第j季度交货的柴油机数。根据合同要求，必须满足 又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有： 第i季度生产的用于j季度交货的每台柴油机的实际成本cij应该是该季度单位成本加上储存、维护等费用。cij的具体数值见下表： 设用ai表示该厂第i季度的生产能力，bj表示第i季度的合同供应量，则问题可写成： 目标函数： 约束条件： 显然，这是一个产大于销的运输问题模型。注意到这个问题中当i＞j时，xij=0，所以应令对应的cij=M，再加上一个假想的需求D，就可以把这个问题变成产销平衡的运输模型，并写出产销平衡表和单位运价表(合在一起，见下表)。 经用表上作业法求解，可得多个最优方案，下表是最优方案之一。 即第Ⅰ季度生产25台，10台当季交货，15台Ⅱ季度交货；Ⅱ季度生产5台，用于Ⅲ季度交货；Ⅲ季度生产30台，其中20台于当季交货，10台于Ⅳ季度交货。Ⅳ季度生产10台，于当季交货。按此方案生产，该厂总的生产费用(包括储存、维护费用)为773万元。 转运问题 ①每个产地的产品不一定直接发运到销售点，可以将其中几个产地集中一起运； ②运往各销地的产品可以先运给其中几个销地，再转运给其他销地； ③除产、销地之外，中间还可以有几个转运站，在产地之间、销地之间或产地与销地间进行转运。 * 产地：原产地、中间转运站、转运物资的销地 销地：原销地、中间转运站、转运物资的产地 如果是产销不平衡问题，先通过增加虚拟的产地或销地转化为产销平衡问题。 设各转运站转运物资的数量均为总产量∑ ai（或总销量∑ bj ） 专职转运站的产量和销量均为∑ ai 原产地Ai的产量均为（ai+∑ ai） 原销地Bj的销量均为（ bj+∑ ai） 将各条线路实际的运输单价列成单位运价表，其中不可能的运输其单位运价用M表示。 扩展运输表的构建步骤 举例：A、B两个化肥厂每年各生产磷肥900万吨和600万吨，这些化肥要运到三个港口，已知三个港口C、D、E每年能承担的船运量分别为700、400、300万吨，两个工厂及三个港口之间单位运价如下表所示，为按需要把磷肥运到各港口，怎样安排运输才能使运费最少？ A B C D E A 0 2 9 10 7 B 2 0 7 10 10 C 9 7 0 3 4 D 10 10 3 0 2 E 7 10 4 2 0 * C D E 产量 A 900 B 600 销量 700 400 300 C D E F 产量 A 900 B 600 销量 700 400 300 100 ∑产（或∑销）=1500 A B C D E 产量(转运量) A 1500 B 1500 C 1500 D 1500 E 1500 销量(转运量) 1500 1500 1500 1500 1500 ∑转运=7500 表1 表2 表3 产销平衡运输表的构建 A B C D E A 0 2 9 10 7 B 2 0 7 10 10 C 9 7 0 3 4 D 10 10 3 0 2 E 7 10 4 2 0 ∑=1500+7500=9000 F 发量 收量 900+1500=2400 600+1500=2100 1500 1500 1500 1500 1500 700+1500=2200 400+1500=1900 300+1500=1800 100 0 0 0 0 0 将表2和表3合并为一张表（加上单位运价） 例：已知各产地、销地、中间转运站及相互之间每吨产品的运价如表所示，问在考虑到产销地之间直接运输和非直接运输的各种可能方案的情况下，如何将三个厂每天生产的产品运往销售地，使总的运费最少。 (1) 由于问题中所有产地、中间转运站、销地都可以看作产地，又可看作销地。因此把整个问题当作有11个产地和11个销地的扩大的运输问题。 (2) 对扩大的运输问题建立单位运价表。方法将表中不可能的运输方案的运价用任意大的正数M代替。 (3) 所有中间转运站的产量等于销量。由于运费最少时不可能出现一批物资来回倒运的现象，所以每个转运站的转运数不超过20吨。可以规定T1，T2，T3，T4的产量和销量均为20吨。由于实际的转运量 可以在每个约束条件中增加一个松弛变量xii，xii相当于一个虚构的转运站，意义就是自己运给自己。 (20-xi