第7章运筹学运输问题

1、管管 理理 运运 筹筹 学学1第七章第七章 运运 输输 问问 题题 1 1运运 输输 模模 型型 2 2运输问题的计算机求解运输问题的计算机求解 3 3运输问题的应用运输问题的应用 4 4* *运输问题的表上作业法运输问题的表上作业法管管 理理 运运 筹筹 学学2管管 理理 运运 筹筹 学学3管管 理理 运运 筹筹 学学4管管 理理 运运 筹筹 学学5管管 理理 运运 筹筹 学学6管管 理理 运运 筹筹 学学7管管 理理 运运 筹筹 学学8管管 理理 运运 筹筹 学学9管管 理理 运运 筹筹 学学10管管 理理 运运 筹筹 学学11第四季度可以加班生产，生产能力为第四季度可以加班生产，生产能力

2、为1010台，加班费用台，加班费用1 1万元每台万元每台原有库存原有库存1515台，年末需要留有台，年末需要留有1010台库存？台库存？管管 理理 运运 筹筹 学学12生产与存储问题生产与存储问题管管 理理 运运 筹筹 学学13 某造船厂根据合同需连续三年提供五艘大型货轮给客户，该厂三年内的生产情况如表所示。年度正常生产 加班生产 正常生产每艘成本（万元）133600242700323650 加班生产比正常生产高出10%，每艘货轮积压一年的损失为60万元，签合同时，该厂已积压两艘货轮，该厂希望在三年后有一艘备用，问应该如何安排生产，总的费用最小？管管 理理 运运 筹筹 学学14生产问题生产问题

3、 某机床厂定下一年合同分某机床厂定下一年合同分别于各季度末交货。已知别于各季度末交货。已知各季度生产成本不同，允各季度生产成本不同，允许存货，存储费许存货，存储费0.12万元万元/台季，三、四季度可以加台季，三、四季度可以加班生产，加班生产能力班生产，加班生产能力8台台/季，加班费用季，加班费用3万元万元/台台 问如何安排生产使得总费问如何安排生产使得总费用最低？用最低？季度正常生产能力单位成本（万元）交货台数12343032202810.5510.81111.125301545管管 理理 运运 筹筹 学学15分析：分析： 可用线性规划，但用运输问题更简单可用线性规划，但用运输问题更简单 要决

4、策的问题是各季度生产量和交货量设要决策的问题是各季度生产量和交货量设xij表示第表示第i季度生产第季度生产第j季度交货的台数季度交货的台数 因加班时间生产成本不同，故要区别开来，因加班时间生产成本不同，故要区别开来，三四季度可加班，视同增加两个季度三四季度可加班，视同增加两个季度 需求量合计需求量合计115台，生产能力合计台，生产能力合计126台，供台，供需不平衡，因此，增加一个虚拟的需求点。需不平衡，因此，增加一个虚拟的需求点。管管 理理 运运 筹筹 学学16建模：建模： 成本成本 交货交货生产生产 1 2 3 4 5（虚拟）（虚拟）产量产量1季度正常生产季度正常生产2季度正常生产季度正常生

5、产3季度正常生产季度正常生产3季度加班生产季度加班生产4季度正常生产季度正常生产4季度加班生产季度加班生产10.55 10.67 10.79 10.91 0 M 10.8 10.92 11.04 0 M M 11 11.12 0 M M 12 14.12 0 M M M 11.1 0 M M M 14.1 0 30 32 20 8 28 8 需求量需求量 25 30 15 45 11 126126管管 理理 运运 筹筹 学学17结果：结果： 生产生产 交货交货生产生产 闲置闲置 1 2 3 4 能力能力产量产量1季度正常生产季度正常生产2季度正常生产季度正常生产3季度正常生产季度正常生产3季度

6、加班生产季度加班生产4季度正常生产季度正常生产4季度加班生产季度加班生产 25 5 25 7 8 12 8 28 5 3 30 32 20 8 28 8 需求量需求量 25 30 15 45 11 126126管管 理理 运运 筹筹 学学18管管 理理 运运 筹筹 学学19三、转运问题三、转运问题例8、腾飞公司有1、2两个分厂生产产品，1、2分厂每月分别生产400台和600台。有3、4两个分销商负责四个城市的供应。运输网络和运输费用如图，单位是百元。问应该如何调运仪器，可使总运输费用最低？管管 理理 运运 筹筹 学学20三、转运问题三、转运问题解：解：设 xij 为从 i 到 j 的运输量，可

7、得到有下列特点的线性规划模型：目标函数：Min f = 所有可能的运输费用（运输单价与运输量乘积之和）约束条件： 对产地（发点） i ：输出量 - 输入量 = 产量 对转运站（中转点）：输入量 - 输出量 = 0 对销地（收点） j ：输入量 - 输出量 = 销量管管 理理 运运 筹筹 学学21三、转运问题三、转运问题目标函数： Min f = 2x13+ 3x14+ 3x23+ x24+ 4x28 + 2x35+ 6x36+ 3x37+ 6x38+ 4x45+ 4x46+ 6x47+ 5x48 约束条件： s.t. x13+ x14 600 (1分厂供应量限制） x23+ x24+ x28

8、400 (2分厂供应量限制） -x13- x23 + x35 + x36+ x37 + x38 = 0 （3转运站） -x14- x24 + x45 + x46+ x47 + x48 = 0 （4转运站） 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管管 理理 运运 筹筹 学学22三、转运问题三、转运问题用用“管理运筹学管理运筹学”软件求得结果：软件求得结果： x13 = 550 x14 =50 ； x23 = 0 x24 = 100 x28 = 3

9、00 ； x35 = 200 x36 = 0 x37 = 350 x38 = 0 ； x45 = 0 x46 = 150 x47 = 0 x48 = 0 。最小运输费用为：最小运输费用为：4600百元百元如何把转运问题转化为运输问题？如何把转运问题转化为运输问题？管管 理理 运运 筹筹 学学23举例说明表上作业法例1、某部门三个工厂生产同一产品的产量、 四个销售点的销量及单位运价如下表：41228543961111104814121482210163214321AAABBBB销量产量销地产地管管 理理 运运 筹筹 学学24 按单位运价的大小决定供应的先后，优先满足单位运价最小者的供销要求。 即

10、从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格。 管管 理理 运运 筹筹 学学25最小元素法举例41228543961111104814121482210163214321AAABBBB销量产量销地产地822010100614868000060管管 理理 运运 筹筹 学学26最小元素法举例41228543961111104814121482210163214321AAABBBB销量产量销地产地821014682466811632410514280z最小元素法缺点：有时为了优先考虑某一最小元素，却可能使其他供销点的运输费用大大增加，会出现顾此失彼。 考虑运价差管管 理理 运运

11、筹筹 学学27 罚数（即差额）=次小运价-最小运价罚数（或差额）的解释：;差额大，则不按最小运费调运，运费增加大。差额大，则不按最小运费调运，运费增加大。;差额小，则不按最小运费调运，运费增加不大。差额小，则不按最小运费调运，运费增加不大。对差额最大处，采用最小运费调运。伏格尔法思路：管管 理理 运运 筹筹 学学28 结合例结合例1说明这种方法。说明这种方法。4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地行罚数04-4=0第一次第一次管管 理理 运运 筹筹 学学29 结合例结合例1说明这种方法。说明这种方法。481412148

12、2210163214321AAABBBB4122854396111110销量产量销地销地产地产地行罚数013-2=1第一次第一次管管 理理 运运 筹筹 学学30 结合例结合例1说明这种方法。说明这种方法。4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地行罚数011第一次第一次管管 理理 运运 筹筹 学学31 结合例结合例1说明这种方法。说明这种方法。4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地行罚数011 列 罚 数4-2=22153第一次第一次管管 理理 运

13、运 筹筹 学学32 结合例结合例1说明这种方法。说明这种方法。4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地行罚数011 列 罚 数21531480优先安排销地 ，否则运价会更高2B下次不考虑该列第一次第一次管管 理理 运运 筹筹 学学33第二次第二次 结合例结合例1说明这种方法。说明这种方法。行罚数012 列 罚 数213优先安排销地 ，否则运价会更高4B84814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地148006下次不考虑该行管管 理理 运运 筹筹 学学3

14、4 结合例结合例1说明这种方法。说明这种方法。行罚数01 列 罚 数21284814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地148006下次不考虑该列802第三次第三次管管 理理 运运 筹筹 学学35 结合例结合例1说明这种方法。说明这种方法。行罚数76 列 罚 数1284814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地1480068024120下次不考虑该列第四次第四次管管 理理 运运 筹筹 学学36 结合例结合例1说明这种方法。说明这种方法。行罚数00 列 罚

15、数24284814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地1480068024120000第五次第五次管管 理理 运运 筹筹 学学37 例1用伏格尔法得到的初始基可行解4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地48148122244685149228114412 z目标函数值目标函数值用最小元素法求出的目标函数z=246管管 理理 运运 筹筹 学学38第二步：解的最优性检验 闭回路法 思路：计算空格（非基变量）的检验数 24242121121211110 x

16、xxxzz0112412110, 1zzxxx若令则如何求检验数？分析：运费的增量即 增加1个单位 的检验数=相应的运费增量11x11x管管 理理 运运 筹筹 学学3941228543961111104814121482210163214321AAABBBB销量产量销地产地821014682460z从初始表分析：要保证产销平衡，则1, 12344110zz111121231311xxxx 称为闭回路 21231311xxxx+1-1+1-1管管 理理 运运 筹筹 学学4041228543961111104814121482210163214321AAABBBB销量产量销地产地821014682

17、561112121561143102221管管 理理 运运 筹筹 学学41检验数表41228543961111104814121482210163214321AAABBBB销量产量销地产地82101468211-11012,0124表中的解不是最优解。管管 理理 运运 筹筹 学学42第三步：解的调整 从检验数为负值的格出发，做一条除该空格外其余顶点均为有数字格组成的闭回路。在这条闭回路上对空格的运量作最大可能的调整。41228543961111104814121482210163214321AAABBBB销量产量销地产地82101468-1（-2）（-2）（+2）（+2）管管 理理 运运 筹筹

18、 学学43 调整后的解为：41228543961111104814121482210163214321AAABBBB销量产量销地产地8212144822091122246244689211441251428, 0zij此时的解为最优解。最优解不唯一管管 理理 运运 筹筹 学学44运输问题练习1 求解运输问题 销地销地产地产地B B1 1 B B2 2 B B3 3 B4 4产量产量A A1 1A A2 2A A3 34 8 7 54 8 7 53 5 4 33 5 4 35 4 9 65 4 9 67 73 36 6销销 量量4 4 5 34 4 5 3管管 理理 运运 筹筹 学学45运输问题练习2有甲乙丙三个商品产地，商品的运出量分别为25t、18t、5t，ABCD四个销售地，运入量分别为16t、20t、5t、7t，运输费用与各地之间的运输距离成正比，运输距离和运输量如下表所示，求合理的调运方案及最小吨公里。管管 理理 运运 筹筹 学学462.位势法位势法 所谓位势法，我们对运输表上的每一行赋予一个数值ui，对每一列赋予一个数值v