教案9_运输问题应用.ppt

,求解方法：转化为产销平衡问题，加松弛变量，使之成为,第三节产销不平衡的运输问题及其解法,然后，虚拟一个销地Bn+1，设它的销量为,将松弛变量xin+1看成是从产地Ai运往销地Bn+1的数量，而运费Cin+1=0，I=1,2,m，（储存起来）。,对销量大于产量的情况,其解法与产大于销量的解法类似（假想一个产地）。,例：求下列运输问题的最优运输方案。,产销及运价表,变成产销平衡的运输问题,利用伏格尔法、位势表可得最优方案如下：,练习：设有A1，A2，A3，三个产地生产某种物质，其产量分别为7，5，7，B1，B2，B3，B4四个销地需要该物资，销量分别为2，3，4，6，又已知各产销地之间的运价如表2，确定总运费最少的调运方案。,表2单位运价表,例2设有三个化肥厂供应四个地区化肥。其具体数据如下表，单位为万吨、万元/万吨，试求总运费最省的化肥调运方案。,解：这是一个产销不平衡问题。总产量160最低需求110。B4地最多可分配到60万吨化肥。整个四个地区的最高需求总量为210万吨，此时，需求量大于总产量。为了平衡在产销平衡表中增加一个假想的化肥厂A4，其产量为50万吨。由于各地区的需求量包含两部分，如地区B1，30万吨是最低需求，故必须实际得到满足，不能由假想的化肥厂提供，令其运价为M（任意大的正数），另一部分20万吨可满足或不满足都行，因此可由假想的化肥厂A4供给，可令其运价为0（相当于目标函数来说不影响，运不运都行）。等价于,然后，按产销平衡问题的表上作业法去作。这个问题的最优方案为下表。,注1：B3地区的最小需求为0，故不用分别按两个地区考虑。2：运价表中运费为0，就意味着运与否都可以，对目标函数没有影响。运费为M的，就意味着不允许运。,第四节：运输问题举例,例1某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如下表。又如果生产出来的柴油机当季度不交货，每台积压一个季度的储存费用为0.15万元。要求在完成合同的情况下，做出使该厂全年生产费用最小的决策。,D000030,例2某航运公司承担六个港口城市ABCDEF的四条航线，已知各航线的起终点及每天的航班数如表1，各城市间的航程天数如表2，每次装卸各需要1天，问航运公司至少配备多少条船，才能满足需要？,表1,表2,1.周转船只,2.调度船只,例3假定：每个工厂生产的糖果不一定直接发运到销售点，可以几个产地集中在一起运；运给各销地的糖果可以先运给其中几个销地，再转运给其他销地；除产、销点之外，中间还可有几个转运站，在产地间、销地间或在产地与销地间转运。问：产销地之间的直接运输和非直接运输的各种可能的方案中，如何使总的费用最少。,产地、销地、中间转运站及相互之间每吨糖果的运价。,解：从表中看出这是扩大的运输问题，特点：由于问题中所有产地、中间转运站、销地都可以看作产地，又可看作销地。建立单位运价表。方法不可能的运输方案的运价用任意大的正数M代替。所有中间转运站的产量等于销量。可以规定T1,T2,T3,T4的产量和销量均为20吨，每个约束条件中增加一个松弛变量xii,xii相当于一个虚构的转运站,(20-xii）就是每个转运站的实际转运量，运价cii=0。扩大的运输问题中原来的产地与销地因为也有转运站的作用，所以同样在原来产量与销量的数字上加20吨。A1到B2每吨糖果的直接费用为11元，如从A1经A3运往B2，每吨运价是3+4=7元，从A1经T2运往B2只需1+5=6元而从A1到B2运费最少的路径是从A1经A2，B1到B2，每吨糖果的运费只需1+1+1=3元。可见产地到销地之间