《运筹学》胡运权清华版-3-03 运输问题的进一步讨论ppt课件

1、产销不平衡的运输问题产销不平衡的运输问题有转运的运输问题有转运的运输问题产量或销量有上下限的运输问题产量或销量有上下限的运输问题一、一、 产销不平衡的运输问题产销不平衡的运输问题1 产产销销模型模型s.t. 销地产地B1B2.BnBn1产量A1c11c12.c1n0a1A2c21c22.c2n0a2.Amcm1cm2.cmn0am销量b1b2.bnbn1处置方法虚拟销地虚拟销地2 产产销销 ，相差，相差4 销地产地B1B2B3B4B5产量产量A1 8A25A39销量销量4356431234112596751转化成产销平衡000有转运的运输问题有转运的运输问题例例5 某运输问题的产销平衡表以及单

2、位运价如下某运输问题的产销平衡表以及单位运价如下 销地产地B1B2B3B4产量产量A17 101397A29711149A312106186销量销量8365现决议在现决议在B2处设立中转站，由处设立中转站，由B2转往其他销地运转往其他销地运价如下：价如下： 销地转运地B1B2B3B4B290311比较：比较： A2 B3 A2 B2 B3更经济更经济转运问题转运问题规范运输问题规范运输问题 销地产地B1B2B3B4产量A17 101397A29711149A312106186B29031122销量82565220223例例6 工厂工厂S1、S2、S3要运送货物到要运送货物到D1、D2、D3、D

3、4去，一切供应量及去，一切供应量及单位运价如下单位运价如下 仓库工厂D1D2D3D4产量S17 11484S2610395S3592103销量2433假设一切的工厂、仓库都可以作为转运点，假设一切的工厂、仓库都可以作为转运点，工厂与工厂之间的单位运价是工厂与工厂之间的单位运价是 工厂工厂S1S2S3S10 23S2202.5S332.50仓库与仓库之间单位运价如下仓库与仓库之间单位运价如下 仓库仓库D1D2D3D4D10 522D25043.5D32401.5D42 3.51.50问：如何调运使得总运费最低？问：如何调运使得总运费最低？解：转化成平衡运输问题解：转化成平衡运输问题 S1 S2

4、S3 D1 D2 D3 D4S1S2S3D1D2D3D4 0 2 32 0 2.5 3 2.5 0 7 11 4 8 16 6 10 3 9 17 5 9 2 10 157 6 511 10 94 3 28 9 10 0 5 2 2 12 5 0 4 3.5 12 2 4 0 1.5 12 2 3.5 1.5 0 1212 12 12 14 16 15 15总结总结有转运的运输问题有转运的运输问题 m个产地：个产地：A1，A2，.Am n个销地：个销地：B1，B2，.Bn假设：假设：1 一切产地和销地都可以作为转运地一切产地和销地都可以作为转运地 2 产销平衡产销平衡知：知：ai第第i个产地的

5、产量净供应量个产地的产量净供应量) bj第第j个销地的销量净需求量个销地的销量净需求量) xij第第i个产地到第个产地到第j个销地的运量个销地的运量 cij第第i个产地到第个产地到第j个销地的运价个销地的运价 ci第第i个地点转运单位物资的费用个地点转运单位物资的费用问：如何调问：如何调运，使得总运，使得总运费最低运费最低?有转运平衡运输问题模型有转运平衡运输问题模型 1 由于一切产地、销地都可以既看作产地、又看作由于一切产地、销地都可以既看作产地、又看作销地，因此可以把整个问题看作是销地，因此可以把整个问题看作是m+n个产地、个产地、m+n个销地的扩展了的运输问题；个销地的扩展了的运输问题；

6、2 对扩展的运输问题建立单位运价表。方法是将不对扩展的运输问题建立单位运价表。方法是将不能够的运输方案的运价用恣意大的正数能够的运输方案的运价用恣意大的正数M替代；替代；3 普通可以如下定义新产量和新销量普通可以如下定义新产量和新销量 产地的发送量净发送量总产量或总销量产地的发送量净发送量总产量或总销量 销地的接纳量净需求量总产量或总销量销地的接纳量净需求量总产量或总销量产量或销量有上下限产量或销量有上下限的运输问题的运输问题例7 使用生产B1B2B3生产量生产量A16a111A2a27A3a34使用量使用量1046243156324问：如何运输，使总运费最低？问：如何运输，使总运费最低？例7

7、 使用生产B1B2B3生产量生产量A16a111A2a27A3a34使用量使用量1046243156324处置方法处置方法 首先假定取消最小消费量限首先假定取消最小消费量限制，而把最大消费量当作各个地制，而把最大消费量当作各个地域的消费量。域的消费量。 使用生产B1B2B3生产量生产量A111A27A3a34使用量使用量1046243156324？例7 使用生产B1B2B3生产量生产量A16a111A2a27A3a34使用量使用量1046243156324 总运用量总运用量104620 前两地最低消费量前两地最低消费量6713 A3最大消费量最大消费量20137 使用生产B1B2B3生产量生产

8、量A111A27A37使用量使用量1046243156324例7不平衡不平衡 使用生产B1B2B3B4生产量生产量A1 11A27A37使用量使用量10465243015603204最低最低产量产量64 使用生产B1B2B3B4生产量生产量A16A1 5A27A34A33使用量使用量10465243M156M3204243032M4最小需求最小需求最大需求最大需求最小需求最小需求 最小产量最小产量部分必需发部分必需发出，不能发出，不能发到虚拟地到虚拟地 使用生产B1B2B3B4生产量生产量A16A1 5A27A34A33使用量使用量10465243M15603204243032M4333274

9、03此平衡运输问题最优解此平衡运输问题最优解最小费用最小费用39 6 0 9 9 7 0 0 0 8 0练习 某大学有三个区：一区、二区、三区，某大学有三个区：一区、二区、三区，每年分别需求煤每年分别需求煤30003000吨，吨，10001000吨和吨和20002000吨，吨，由两个煤矿：煤矿由两个煤矿：煤矿1 1和煤矿和煤矿2 2担任供应，两个担任供应，两个煤矿供应量分别为煤矿供应量分别为15001500吨和吨和40004000吨。假设这吨。假设这两个煤矿的煤价和质量一样，由煤矿到大学两个煤矿的煤价和质量一样，由煤矿到大学的单位运价百元的单位运价百元/ /吨见下表：吨见下表：单价单价一区一区二区二区三区三区煤矿煤矿1 11.651.651.701.701.751.75煤矿煤矿2 21.601.601.651.651.701.70由于总需求量大于总供应量，经大学研讨决议一由于总需求量大于总供应量，经大学研