运筹学：教案9_运输问题应用

1、求解方法：转化为产销平衡问题，加松弛变量，使之成为miaxxiinnjij, 2 , 111第三节第三节 产销不平衡的运输问题及其解法产销不平衡的运输问题及其解法然后，虚拟一个销地Bn+1，设它的销量为njjmiinbab111将松弛变量xin+1看成是从产地Ai运往销地Bn+1的数量，而运费Cin+1=0，I=1,2,m，（储存起来）。2. 销大于产的情况, 即njjmiiba11其数学模型为 0, 2 , 1, 2 , 1.min1111ijmijijnjiijminjijijxnjbxmiaxtsxcZ对销量大于产量的情况, 其解法与产大于销量的解法类似（假想一个产地）。例：求下列运输问

2、题的最优运输方案。 收点发点B1B2B3B4发量A1362470A2522480A3175265收量40307060产销及运价表变成产销平衡的运输问题发 收B1B2B3B4B5发量A13624070A25224080A31752065收量4030706015 利用伏格尔法、位势表可得最优方案如下：平衡表 单位：吨收点发点B1B2B3B4B5发量A17070 A23003515 80A3402565收量4030706015销地产地B1 B2 B3 B4A1A2A3 2 11 3 4 10 3 5 9 7 8 1 2练习：设有A1，A2，A3，三个产地生产某种物质，其产量分别为7，5，7，B1，B

3、2，B3，B4四个销地需要该物资，销量分别为2，3，4，6，又已知各产销地之间的运价如表2，确定总运费最少的调运方案。表2 单位运价表 例2 设有三个化肥厂供应四个地区化肥。其具体数据如下表，单位为万吨、万元/万吨，试求总运费最省的化肥调运方案。 需求地区 化肥厂 B1 B2 B3 B4 产量 A1 16 13 22 17 50 A2 14 13 19 15 60 A3 19 20 23 - 50 最低需求 最高需求 30 50 70 70 0 30 10 不限 解：这是一个产销不平衡问题。总产量160最低需求110。B4地最多可分配到60万吨化肥。整个四个地区的最高需求总量为210万吨，此时

4、，需求量大于总产量。为了平衡在产销平衡表中增加一个假想的化肥厂A4，其产量为50万吨。由于各地区的需求量包含两部分，如地区B1，30万吨 是最低需求，故必须实际得到满足，不能由假想的化肥厂提供，令其运价为M（任意大的正数），另一部分20万吨可满足或不满足都行，因此可由假想的化肥厂A4供给，可令其运价为0（相当于目标函数来说不影响，运不运都行）。等价于然后，按产销平衡问题的表上作业法去作。这个问题的最优方案为下表。 需求地区 化肥厂 B1 B*1 B2 B3 B4 B*4 产量 A1 16 16 13 22 17 17 50 A2 14 14 13 19 15 15 60 A3 19 19 20

5、 23 M M 50 A4 M 0 M 0 M 0 50 销量 30 20 70 30 10 50 注1：B3地区的最小需求为0，故不用分别按两个地区考虑。 2：运价表中运费为0，就意味着运与否都可以，对目标函数没有影响。 运费为M的，就意味着不允许运。 需求地区化肥厂B1B*1B2B3B4B*4产量A15050A220103060A33020050A4302050销量302070301050第四节：运输问题举例第四节：运输问题举例例1 某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如下表。又如果生产出来的柴油机

6、当季度不交货，每台积压一个季度的储存费用为0.15万元。要求在完成合同的情况下，做出使该厂全年生产费用最小的决策。季度生产能力单位成本（万元）12342535301010.811.111.011.31 2 3 4产量123410.8 10.95 11.10 11.25 11.10 11.25 11.40 11.0 11.15 11.3025353010销量10 15 25 20D000030MMMMMM例2 某航运公司承担六个港口城市ABCDEF的四条航线，已知各航线的起终点及每天的航班数如表1，各城市间的航程天数如表2，每次装卸各需要1天，问航运公司至少配备多少条船，才能满足需要？航线起点终

7、点每天航班1234EBADDCFB3211表1从 到ABCDEFABCDEF0102301413 1507 851707852030表21.周转船只2.调度船只城市到达需求余缺数ABCDEF012301120130-1-122-31ABE剩余CDF214731385173221缺少113例3假定：每个工厂生产的糖果不一定直接发运到销售点，可以几个产地集中在一起运；运给各销地的糖果可以先运给其中几个销地，再转运给其他销地；除产、销点之外，中间还可有几个转运站，在产地间、销地间或在产地与销地间转运。问：产销地之间的直接运输和非直接运输的各种可能的方案中，如何使总的费用最少。产地、销地、中间转运站及

8、相互之间每吨糖果的运价。解：从表中看出这是扩大的运输问题，特点：由于问题中所有产地、中间转运站、销地都可以看作产地，又可看作销地。 建立单位运价表。方法不可能的运输方案的运价用任意大的正数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元。可见产地到销地之间的运输方案是很多的。作一般的运输问题来处理，可以这样做：求解过程：求解过程：确定问题的单位运价表；得到产销平衡表计算最优方案；当变量多时可进行计算机编程运算，结果略。 表 3-25 产地销地A1A2A3T1T2T3T4B1B2B3B4产量A1A2A301310M3M023115M4M2323317119432101085272429T1T2T3T4