运筹学胡运权清华版303运输问题的进一步讨论.ppt

产销不平衡的运输问题产销不平衡的运输问题有转运的运输问题有转运的运输问题产量或销量有上下限的运输问题产量或销量有上下限的运输问题一、一、产销不平衡的运输问题产销不平衡的运输问题1 产产销销模型模型s.t.销地产地B1B2.BnBn1产量A1c11c12.c1n0a1A2c21c22.c2n0a2.Amcm1cm2.cmn0am销量b1b2.bnbn1处理方法虚拟销地虚拟销地2 产产销销，相差，相差4 销地产地B1B2B3B4B5产量产量A1 8A25A39销量销量4356431234112596751转化成产销平衡000有转运的运输问题有转运的运输问题例例5 某运输问题的产销平衡表以及单位运价如下某运输问题的产销平衡表以及单位运价如下 销地产地B1B2B3B4产量产量A17 101397A29711149A312106186销量销量8365现决定在现决定在B2处设立中转站，由处设立中转站，由B2转往其他销地运价转往其他销地运价如下：如下：销地转运地B1B2B3B4B290311比较：比较：A2 B3 A2 B2 B3更经济更经济转运问题转运问题标准运输问题标准运输问题 销地产地B1B2B3B4产量A17 101397A29711149A312106186B29031122销量82565220223例例6 工厂工厂S1、S2、S3要运送货物到要运送货物到D1、D2、D3、D4去，所有供应量及去，所有供应量及单位运价如下单位运价如下 仓库工厂D1D2D3D4产量S17 11484S2610395S3592103销量2433若所有的工厂、仓库都可以作为转运点，若所有的工厂、仓库都可以作为转运点，工厂与工厂之间的单位运价是工厂与工厂之间的单位运价是 工厂工厂S1S2S3S10 23S2202.5S332.50仓库与仓库之间单位运价如下仓库与仓库之间单位运价如下 仓库仓库D1D2D3D4D10 522D25043.5D32401.5D42 3.51.50问：如何调运使得总运费最低？问：如何调运使得总运费最低？解：转化成平衡运输问题解：转化成平衡运输问题 S1 S2 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 1 所有产地和销地都可以作为转运地所有产地和销地都可以作为转运地 2 2 产销平衡产销平衡已知：已知：a ai i第第i i个产地的产量（净供应量个产地的产量（净供应量)b bj j第第j j个销地的销量（净需求量个销地的销量（净需求量)x xijij第第i i个产地到第个产地到第j j个销地的运量个销地的运量 c cijij第第i i个产地到第个产地到第j j个销地的运价个销地的运价 c ci i第第i i个地点转运单位物资的费用个地点转运单位物资的费用问：如何调问：如何调运，使得总运，使得总运费最低运费最低?有转运平衡运输问题模型有转运平衡运输问题模型 1 由于所有产地、销地都可以既看作产地、又看作由于所有产地、销地都可以既看作产地、又看作销地，因此可以把整个问题看作是销地，因此可以把整个问题看作是m+n个产地、个产地、m+n个销地的扩大了的运输问题；个销地的扩大了的运输问题；2 对扩大的运输问题建立单位运价表。方法是将不对扩大的运输问题建立单位运价表。方法是将不可能的运输方案的运价用任意大的正数可能的运输方案的运价用任意大的正数M代替；代替；3 一般可以如下定义新产量和新销量一般可以如下定义新产量和新销量 产地的发送量净发送量总产量（或总销量）产地的发送量净发送量总产量（或总销量）销地的接收量净需求量总产量（或总销量）销地的接收量净需求量总产量（或总销量）产量或销量有上下限产量或销量有上下限的运输问题的运输问题例7 使用生产B1B2B3生产量生产量A16a111A2a27A3a34使用量使用量1046243156324问：如何运输，使总运费最低？问：如何运输，使总运费最低？例7 使用生产B1B2B3生产量生产量A16a111A2a27A3a34使用量使用量1046243156324处理方法处理方法 首先假定取消最小生产量限首先假定取消最小生产量限制，而把制，而把最大生产量最大生产量当作各个地当作各个地区的生产量。区的生产量。使用生产B1B2B3生产量生产量A111A27A3a34使用量使用量1046243156324？例7 使用生产B1B2B3生产量生产量A16a111A2a27A3a34使用量使用量1046243156324 总使用量总使用量104620 前两地最低生产量前两地最低生产量6713 A3最大生产量最大生产量20137 使用生产B1B2B3生产量生产量A111A27A37使用量使用量1046243156324例7不平衡不平衡 使用生产B1B2B3B4生产量生产量A1 11A27A37使用量使用量10465243015603204最低最低产量产量64 使用生产B1B2B3B4生产量生产量A16A1 5A27A34A33使用量使用量10465243M156M3204243032M4最小需求最小需求最大需求最大需求最小需求最小需求 最小产量最小产量部分必须发部分必须发出，不能发出，不能发到虚拟地到虚拟地 使用生产B1B2B3B4生产量生产量A16A1 5A27A34A33使用量使用量10465243M15603204243032M433327403此平衡运输问题最优解此平衡运输问题最优解最小费用最小费用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由于总需求量大于总供应量，经大学研究决定一由于总需求量大于总供应量，经大学研究决定一区的需求量可减少区的需求量可减少0 0300300吨，二区必须满足，三吨，二区必须满足，三区需求量不能少于区需求量不能少于16001600吨。试建立总运费最小的吨。试建立总运费最小的调运方案。（作出产销平衡表与单位运价表即可，调运方案。（作出产销平衡表与单位运价表即可，不必求解）。不必求解）。