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

1、手机：手机：13551284516院系：交通与汽车学院，交通运输系院系：交通与汽车学院，交通运输系主讲主讲:罗罗 建建 邮箱：邮箱：luo06_luo06_3.1 3.1 典型例子和模型典型例子和模型问题提出：问题提出：一般的运输问题就是要解决把某种产品从一般的运输问题就是要解决把某种产品从若干个若干个产地调运到若干个销地产地调运到若干个销地，在每个产地，在每个产地的的供应量供应量与每个销地的与每个销地的需求量需求量已知，并知道已知，并知道各地之间的各地之间的运输单价运输单价的前提下，如何确定一的前提下，如何确定一个使得总的运输费用最小的方案。个使得总的运输费用最小的方案。一、运输问题的数学表

2、达一、运输问题的数学表达 生产某种产品，生产某种产品，m m个产地：个产地：A A1 1,，A Am m,产量：产量：a a1 1,，a am m n n个销地：个销地：B B1 1,，B Bn n,销量：销量：b b1 1,，b bn n已知：已知：A Ai i至至B Bj j的运输单价为的运输单价为c cijij问题：确定问题：确定A Ai i运往运往B Bj j的数量的数量x xijij，使总运费最低？使总运费最低？二、运输问题的表示二、运输问题的表示网络图网络图运输表运输表线性规划模型线性规划模型A2A3B2A1B3B4B1运输问题网络图运输问题网络图a2=4a3=9b1=3b2=6b

3、3=5b4=6a1=7供应量供应量供应地供应地运价运价需求量需求量需求地需求地311310192874105运输问题的表格表示运输问题的表格表示 B1 B2 B3 B4 3 11 3 10 A1 x11 x12 x13 x14 7 1 9 2 8 A2 x21 x22 x23 x24 4 7 4 10 5 A3 x31 x32 x33 x34 9 3 6 5 6 运输问题线性规划模型运输问题线性规划模型产量约束产量约束销量约束销量约束0,6=+5=+6=+3=+9=+4=+7=+5+10+4+7+8+2+9+10+3+11+3=min343332312423222114131211342414

4、332313322212312111343332312423222114131211343332312423222114131211xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz三、运输问题的分类三、运输问题的分类产销平衡问题：产销平衡问题：a ai i=b=bj j产销不平衡问题：产销不平衡问题：供大于求：供大于求：ai bj供不应求：供不应求：ai bj四、运输问题的求解四、运输问题的求解表上作业法表上作业法确定初始可行调运方案确定初始可行调运方案最小元素法最小元素法判别当前可行方案是否最优判别当前可行方案是否最优闭回路法闭回路法对现有方

5、案进行调整对现有方案进行调整 闭回路法闭回路法用最小元素法确定初始可行调运方案用最小元素法确定初始可行调运方案 最小元素法的基本思想：就近尽量满足供应最小元素法的基本思想：就近尽量满足供应 B1 B2 B3 B4 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 3 6 5 6 31 346 301 040303 0300用闭回路法进行最优性检验用闭回路法进行最优性检验 1 1、找空格的闭回路、找空格的闭回路：以某空格为起点，用水平线或以某空格为起点，用水平线或垂直线向前划，只能在碰到某一数字格时才能转弯，按照这垂直线向前划，只能在碰到某一数字格时才能转弯，按

6、照这一规则继续前进，直到回到起始的空格为止。一规则继续前进，直到回到起始的空格为止。B1 B2 B3 B4 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 3 6 5 6 31 34 6 32 2、根据闭回路计算空格的检验数：、根据闭回路计算空格的检验数：检验数检验数 =奇数顶点的单位运价之和奇数顶点的单位运价之和 偶数顶点的单位运价之和偶数顶点的单位运价之和 B1 B2 B3 B4 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 3 6 5 6 31 346 3121-11012检验数检验数的经济的经济含义：含义：当由产

7、当由产地地Ai往往销地销地Bj增运一增运一个单位个单位货物时货物时所引起所引起的总运的总运输成本输成本的变化的变化数数结论：若所有检验数都大于等于结论：若所有检验数都大于等于0 0，则当前方案最优，则当前方案最优 B1 B2 B3 B4 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 3 6 5 6 31 346 3-11211012对现有方案进行调整对现有方案进行调整 在负的检验数中选择绝对值最大的空格，在方案表中从该空在负的检验数中选择绝对值最大的空格，在方案表中从该空格出发，沿着其闭回路依次标上格出发，沿着其闭回路依次标上“+q”+q”、“-q”-q”

8、，+q-q+q-q 其中其中q q表示最大调整量，它的取值为标表示最大调整量，它的取值为标“-q”-q”的数字中最小的数值。的数字中最小的数值。于是于是q=min3,1=1q=min3,1=1调整后的方案为调整后的方案为 B1 B2 B3 B4 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 3 6 5 6 31 3 56 20221912 五、应用举例五、应用举例 例例、甲乙丙三座城市所需煤炭由、甲乙丙三座城市所需煤炭由A,B两个煤矿供两个煤矿供应，有关数据如表所示，单位运费为万元应，有关数据如表所示，单位运费为万元/万吨，万吨，产销关系为如下图所示。由于

9、需求大于供应，经研产销关系为如下图所示。由于需求大于供应，经研究，甲城市供应量可减少究，甲城市供应量可减少030万吨，乙城市必须万吨，乙城市必须全部满足，丙城市供应量不少于全部满足，丙城市供应量不少于270万吨，求将供万吨，求将供应量全部分完又使总运费最低的调运方案应量全部分完又使总运费最低的调运方案?甲甲乙乙丙丙产量产量A151822400B212516450销量销量320250350甲甲乙乙丙丙产量产量A151822400B212516450最高最高最低最低320290250250350270甲甲甲甲乙乙丙丙丙丙 产量产量A1515182222400B2121251616450CM0MM0702903025027080甲甲甲甲乙乙丙丙丙丙产量产量A1515015182502222400B211402125162701640450CM030MM04070销量销量2903025027080甲城市：甲城市：A煤矿运煤矿运150，B煤矿运煤矿运140，共，共290乙城市：乙城市：A煤矿运煤矿运250，共，共250丙城市：丙城市：B煤矿运煤矿运310，共，共3105 55 51 1M MM MM M12121212