运筹学 第3章 运输问题—08讲

《运筹学 第3章 运输问题—08讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、手机：13551284516院系：交通与汽车学院，交通运输系主讲:罗建运筹学邮箱：luo06_jian2000@126.com3.1典型例子和模型问题提出：一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。第3章运输问题一、运输问题的数学表达生产某种产品，m个产地：A1,…，Am,产量：a1,…，amn个销地：B1,…，Bn,销量：b1,…，bn已知：Ai至Bj的运输单价为cij问题：确定Ai运往Bj的数量xij，使总运费最低？第3章运

2、输问题二、运输问题的表示网络图运输表线性规划模型A2A3B2A1B3B4B1运输问题网络图a2=4a3=9b1=3b2=6b3=5b4=6a1=7供应量供应地运价需求量需求地311310192874105运输问题的表格表示运输问题线性规划模型产量约束销量约束三、运输问题的分类产销平衡问题：∑ai=∑bj产销不平衡问题：供大于求：∑ai>∑bj供不应求：∑ai<∑bj四、运输问题的求解——表上作业法确定初始可行调运方案最小元素法判别当前可行方案是否最优闭回路法对现有方案进行调整闭回路法用最小元素法确定初始可行调运方案最小元素法的基本思想：就近尽量满足供应313463

3、010403030300用闭回路法进行最优性检验1、找空格的闭回路：以某空格为起点，用水平线或垂直线向前划，只能在碰到某一数字格时才能转弯，按照这一规则继续前进，直到回到起始的空格为止。3134632、根据闭回路计算空格的检验数：检验数=奇数顶点的单位运价之和–偶数顶点的单位运价之和313463121-11012检验数的经济含义：当由产地Ai往销地Bj增运一个单位货物时所引起的总运输成本的变化数结论：若所有检验数都大于等于0，则当前方案最优313463-11211012对现有方案进行调整在负的检验数中选择绝对值最大的空格，在方案表中从该空格出发，沿着其闭回路依次标

4、上“+q”、“-q”，+q-q+q-q其中q表示最大调整量，它的取值为标“-q”的数字中最小的数值。于是q=min{3,1}=1调整后的方案为3135620221912五、应用举例例、甲乙丙三座城市所需煤炭由A,B两个煤矿供应，有关数据如表所示，单位运费为万元/万吨，产销关系为如下图所示。由于需求大于供应，经研究，甲城市供应量可减少0－30万吨，乙城市必须全部满足，丙城市供应量不少于270万吨，求将供应量全部分完又使总运费最低的调运方案?甲乙丙产量A151822400B212516450销量320250350甲乙丙产量A151822400B212516450最高最

5、低320290250250350270甲甲’乙丙丙’产量A1515182222400B2121251616450CM0MM0702903025027080甲甲’乙丙丙’产量A1515015182502222400B211402125162701640450CM030MM04070销量2903025027080甲城市：A煤矿运150，B煤矿运140，共290乙城市：A煤矿运250，共250丙城市：B煤矿运310，共310551MMM1212