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

产销不平衡的运输问题有转运的运输问题产量或销量有上下限的运输问题,第三节 运输问题的 进一步讨论,一、产销不平衡的运输问题,1 产销,模型,s.t.,处理方法,虚拟销地,2 产销,模型,s.t.,处理方法,虚拟产地,例4,产销，相差4,转化成产销平衡,0,0,0,有转运的运输问题,例5 某运输问题的产销平衡表以及单位运价如下,现决定在B2处设立中转站，由B2转往其他销地运价如下：,比较：A2 B3 A2 B2 B3,更经济,转运问题标准运输问题,220,223,例6 工厂S1、S2、S3要运送货物到D1、D2、D3、D4去，所有供应量及单位运价如下,若所有的工厂、仓库都可以作为转运点，工厂与工厂之间的单位运价是,仓库与仓库之间单位运价如下,问：如何调运使得总运费最低？,解：转化成平衡运输问题,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 15,7 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 12,12 12 12 14 16 15 15,总结有转运的运输问题,m个产地：A1，A2，.Am n个销地：B1，B2，.Bn假设：1 所有产地和销地都可以作为转运地 2 产销平衡已知：ai第i个产地的产量（净供应量)bj第j个销地的销量（净需求量)xij第i个产地到第j个销地的运量 cij第i个产地到第j个销地的运价 ci第i个地点转运单位物资的费用,问：如何调运，使得总运费最低?,有转运平衡运输问题模型 1 由于所有产地、销地都可以既看作产地、又看作销地，因此可以把整个问题看作是m+n个产地、m+n个销地的扩大了的运输问题；2 对扩大的运输问题建立单位运价表。方法是将不可能的运输方案的运价用任意大的正数M代替；3 一般可以如下定义新产量和新销量 产地的发送量净发送量总产量（或总销量）销地的接收量净需求量总产量（或总销量）,产量或销量有上下限的运输问题,例7,问：如何运输，使总运费最低？,例7,处理方法 首先假定取消最小生产量限制，而把最大生产量当作各个地区的生产量。,？,例7,总使用量104620 前两地最低生产量6713 A3最大生产量20137,例7,不平衡,最低产量64,最小需求,最大需求最小需求,最小产量部分必须发出，不能发到虚拟地,3,3,3,2,7,4,0,3,此平衡运输问题最优解,最小费用39 6 0 9 9 7 0 0 0 8 0,练习,某大学有三个区：一区、二区、三区，每年分别需要煤3000吨，1000吨和2000吨，由两个煤矿：煤矿1和煤矿2负责供应，两个煤矿供应量分别为1500吨和4000吨。假设这两个煤矿的煤价和质量相同，由煤矿到大学的单位运价（百元/吨）见下表：,由于总需求量大于总供应量，经大学研究决定一区的需求量可减少0300吨，二区必须满足，三区需求量不能少于1600吨。试建立总运费最小的调运方案。（作出产销平衡表与单位运价表即可，不必求解）。,结束,第三节 运输问题的 进一步讨论,