(精品)第03章 运输问题-运筹学.ppt

《(精品)第03章 运输问题-运筹学.ppt》由会员分享，可在线阅读，更多相关《(精品)第03章 运输问题-运筹学.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学方法及其应用运筹学方法及其应用讲授：毕德春讲授：毕德春辽东学院信息技术学院信息管理系辽东学院信息技术学院信息管理系 1/8/20231运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题第第3章运输问题章运输问题例例1：某某食食品品公公司司经经销销的的主主要要产产品品之之一一是是糖糖果果，它它下下面面设设有有三三个个加加工工厂厂，每每天天的的糖糖果果生生产产量量分分别别为为：A1-7t，A2-4t，A3-9t。该该公公司司把把这这些些糖糖果果分分别别运运往往四四个个地地区区的的门门市市销销售售，各各销销售售点点每每日日销销量量为为：B1-3t，B2-6t，B3-5t，B4-6

2、t.已已知知从从各各工工厂厂到到各各销销售售门门市市部部每每吨吨糖糖果果的的运运价价为为下下表表所所示示。问问该该食食品品公公司司应应如如何何调调运运，在在满满足足各各门门市市部部销销售售需需求求量量的的情情况况下下，使使总总运运费费支支出出为为最少最少?门市部门市部加工厂加工厂B1B2B3B4产量（万吨）产量（万吨）A1710867A2597124A336589销量（万吨）销量（万吨）36561运输问题的典型和数学模型运输问题的典型和数学模型1/8/20232运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题解解：这这是是一一个个产产销销平平衡衡的的运运输输问问题题，设设X X

3、ijij表表示示从从A Ai i调调运运产产品品到到B Bj j的的数数量量（吨吨），其其数学模型是：数学模型是：1/8/20233运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题1/8/20234运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题1/8/20235运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题1/8/20236运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题运输问题主要性质运输问题主要性质 （1 1）约束条件系数矩阵中）约束条件系数矩阵中元素等于元素等于0 0或或1 1；（2 2）约约束束条条件件系系数数矩矩阵阵

4、的的每每一一列列有有两两个个非非0 0元元素素，与与每每个个变变量量在在前前 m m 个个约约束束方程和后方程和后 n n 个约束方程中各出现一次相对应。个约束方程中各出现一次相对应。对于产销平衡的运输问题，还有以下两个特点：对于产销平衡的运输问题，还有以下两个特点：（3 3）所有的结构约束方程都是）所有的结构约束方程都是等式等式；（4 4）各产地的产量之和等于各销地的销量之和。）各产地的产量之和等于各销地的销量之和。1/8/20237运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题2 2 表上作业法表上作业法1/8/20238运筹学基础及应用运筹学基础及应用第第3 3章章 运

5、输问题运输问题该运输问题的数学模型为：该运输问题的数学模型为：1/8/20239运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题下面介绍三种常用的方法。下面介绍三种常用的方法。1.最小元素法最小元素法思想：优先满足运价（或运距）最小的供销业务。思想：优先满足运价（或运距）最小的供销业务。给出运输问题的初始可行解（初始调运方案）给出运输问题的初始可行解（初始调运方案）1/8/202310运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题1/8/202311运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题最小元素法最小元素法最小元素最小元素0.1产量产

6、量400和销量和销量300最小者最小者1/8/202312运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题最小元素最小元素0.21/8/202313运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题最小元素最小元素0.31/8/202314运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题最小元素最小元素0.41/8/202315运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题最小元素最小元素0.51/8/202316运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题0.30.10.20.41/8/202317运筹学基础

7、及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地销地产地产地产产量量 4124111610398511622销销 量量14121448练习练习3.1 用最小元素法给出下面运输问题的初始方案用最小元素法给出下面运输问题的初始方案1/8/202318运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地销地产地产地产产量量 412411162109108511622销销 量量 81414481/8/202319运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地销地产地产地产产量量 412112109108511622销销 量量 8141214481/

8、8/202320运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地销地产地产地产产量量 4121182109108116销销 量量 81214481/8/202321运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地销地产地产地产产量量 412118210910811销销 量量 812481/8/202322运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地销地产地产地产产量量 4128210910811销销 量量 812481/8/202323运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题此时得到一个初始调运方案（

9、初始可行解）：此时得到一个初始调运方案（初始可行解）：其余变量全等于零。其余变量全等于零。总运费为（目标函数值）总运费为（目标函数值）此解满足所有约束条件，且基变量（非零变量）的个数为此解满足所有约束条件，且基变量（非零变量）的个数为6（等于（等于m+n-1=3+4-1=6).1/8/202324运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题西北角法西北角法西北角西北角1/8/202325运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题练习练习3.2 用西北角法给出下面运输问题的一个初始方案。用西北角法给出下面运输问题的一个初始方案。销地销地产地产地产产量量4

10、1241121039108511622销销 量量141214481/8/202326运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地销地产地产地产产量量 41241121039108511622销销 量量141214481/8/202327运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地销地产地产地产产量量 41241121039108511622销销 量量1214481/8/202328运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地销地产地产地产产量量 41241121039108511622销销 量量141214481/8

11、/202329运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地销地产地产地产产量量 412411210398511622销销 量量141214481/8/202330运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地销地产地产地产产量量 412411210398511622销销 量量141214481/8/202331运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地销地产地产地产产量量 412411210398511622销销 量量1414481/8/202332运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销

12、地销地产地产地产产量量 412411210398511622销销 量量141214481/8/202333运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地销地产地产地产产量量 4124112103985116销销 量量141214481/8/202334运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地销地产地产地产产量量 4124112103985116销销 量量141214481/8/202335运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地产地产量 4124112103985116销 量1412481/8/202336运筹

13、学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地产地产量 4124112103985116销 量141214481/8/202337运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题此时得到一个初始调运方案（初始可行解）：此时得到一个初始调运方案（初始可行解）：其余变量全等于零。其余变量全等于零。总运费为（目标函数值）总运费为（目标函数值）此解满足所有约束条件，且基变量（非零变量）的个数为此解满足所有约束条件，且基变量（非零变量）的个数为6（等于（等于m+n-1=3+4-1=6).1/8/202338运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问

14、题 沃格尔（沃格尔（Vogel)法法沃格尔法的基本思想：运输表中各行各列的最小运价与次小运价之差值沃格尔法的基本思想：运输表中各行各列的最小运价与次小运价之差值（罚数）应尽可能地小。（罚数）应尽可能地小。或者说：优先供应罚数最大行（或列）中最小运费的方格，以避免将运量或者说：优先供应罚数最大行（或列）中最小运费的方格，以避免将运量分配到该行（或该列）次小的方格中。分配到该行（或该列）次小的方格中。1/8/202339运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地销地产地产地产产量量 4128210910811销销 量量812481/8/202340运筹学基础及应用运筹学

15、基础及应用第第3 3章章 运输问题运输问题销 地产地产量行罚数1234124111602103910181161销 量8121448列罚数12513231/8/202341运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题销 地产地产量行罚数123 412411160021039101185112212销 量8141248列罚数12513221331/8/202342运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题销 地产地产量行罚数123 41241116000103911185112212销 量141248列罚数1251322133211/8/202343运筹

16、学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题销 地产地产量行罚数456 41211710396851122销 量1448列罚数412561/8/202344运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题销 地产地产量行罚数456 412117010360851122销 量1448列罚数4125261/8/202345运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题此时得到一个初始调运方案（初始可行解）：此时得到一个初始调运方案（初始可行解）：其余变量全等于零。其余变量全等于零。总运费为（目标函数值）总运费为（目标函数值）此解满足所有约束条件，且

17、基变量（非零变量）的个数为此解满足所有约束条件，且基变量（非零变量）的个数为6（等于（等于m+n-1=3+4-1=6).1/8/202346运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题二、解的最优性检验二、解的最优性检验前面得到了初始基可行解，一般来说此解并非最优。下面介绍前面得到了初始基可行解，一般来说此解并非最优。下面介绍最优性检验的两种方法。最优性检验的两种方法。闭回路法（闭回路法（cycle method)下面用最小元素法所确定的初始基本可行解来说明。下面用最小元素法所确定的初始基本可行解来说明。与单纯性原理相同，现目标是运费最少，故检验每一个非基变量的检与单纯性原

18、理相同，现目标是运费最少，故检验每一个非基变量的检验数是否验数是否1/8/202347运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地产地产量412104611168210239108145118622销 量8141214481/8/202348运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地产地产量 412104611168210239108145118622销 量8141214481/8/202349运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地产地产量 412104611168210239108145118622销 量8

19、141214481/8/202350运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地产地产量 412104611168210239108145118622销 量8141214481/8/202351运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地产地产量 412104611168210239108145118622销 量8141214481/8/202352运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地产地产量 412104611168210239108145118622销 量8141214481/8/202353运筹学基础及

20、应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地产地产量 412104611168210239108145118622销 量8141214481/8/202354运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 对偶变量法（位势法）对偶变量法（位势法）(dual variable method)用用LP的对偶理论可以证明，检验数的公式为：的对偶理论可以证明，检验数的公式为：其中其中 分别称为行位势、列位势。分别称为行位势、列位势。有基变量所对应的检验数为零，可从有基变量所对应的检验数为零，可从m+n-1个等式个等式解出所有的行位势、列位势。解出所有的行位势、列位势。可

21、以证明，不论令可以证明，不论令 为何值，为何值，始终不变。始终不变。即即 将不会随将不会随 的取值而改变。的取值而改变。为此，在求解方程组时，为计算简便，可指定一个位势等于一个较小的整数或零。为此，在求解方程组时，为计算简便，可指定一个位势等于一个较小的整数或零。1/8/202355运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地产地产量412104611168210239108145118622销 量814121448行位势列位势1/8/202356运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地产地产量 412104611168210239108

22、145118622销 量8141214481/8/202357运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题三、解的改进（用闭回路法调整）三、解的改进（用闭回路法调整）选择进基变量的原则：选择进基变量的原则：即选择非基变量中检验数最小的一个进基。即选择非基变量中检验数最小的一个进基。在进基格点所对应的闭回路上，定义顶点的序号：自进基格点起选定一个方在进基格点所对应的闭回路上，定义顶点的序号：自进基格点起选定一个方向（比如顺时针方向），依次为第一格、第二格、向（比如顺时针方向），依次为第一格、第二格、在奇数格点上减少调整量在奇数格点上减少调整量 ，在偶数格点上增加调整量，在偶数

23、格点上增加调整量 。其中调整量为其中调整量为为闭回路中偶数格点为闭回路中偶数格点1/8/202358运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地产地产量 41241116821039108145118622销 量8141214481/8/202359运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地产地产量 412124411168210329108145118622销 量8141214481/8/202360运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题若在最优解中，某个非基变量的检验数为零，则该问题有无穷多个最优解（相若在最优

24、解中，某个非基变量的检验数为零，则该问题有无穷多个最优解（相当于当当于当 无整数要求而言）无整数要求而言）此时得到一个最优解：此时得到一个最优解：其余变量全等于零。其余变量全等于零。总运费为（目标函数值）总运费为（目标函数值）1/8/202361运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地产地产量 412124411168210329108145118622销 量8141214481/8/202362运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地产地产量 412124111621039108145118622销 量8141214481/8/20

25、2363运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地产地产量 441212411164210369108145118622销 量8141214481/8/202364运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题此时得另一个最优解：此时得另一个最优解：其余变量全等于零。其余变量全等于零。总运费为（目标函数值）总运费为（目标函数值）1/8/202365运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题四、平衡运输问题解法小结四、平衡运输问题解法小结 1/8/202366运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题运输问

26、题的进一步讨论运输问题的进一步讨论对产销不平衡问题，可转化为平衡问题，然后按表上作业法求解。转换办法：对产销不平衡问题，可转化为平衡问题，然后按表上作业法求解。转换办法：若产大于销，增加一个假想的销地（可视为库存地）其销量设定为余量，相应若产大于销，增加一个假想的销地（可视为库存地）其销量设定为余量，相应的运价设为的运价设为0。若销大于产，增加一个虚拟的产地，其产量设定为不足量，相应的运价也设为若销大于产，增加一个虚拟的产地，其产量设定为不足量，相应的运价也设为0。1/8/202367运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题例例4 某市有某市有3个造纸厂个造纸厂A1，A2，A 3 和和B1，B2，B3，B4 4个集中用户个集中用户，各工厂的生产，各工厂的生产量、各用户的需用量以及各工厂到用户的单位运价（元量、各用户的需用量以及各工厂到用户的单位运价（元/t）示于表中，问如何调运）示于表中，问如何调运才能使总运费最小？才能使总运费最小？销地销地产地产地产产量量31234811259567159销销 量量43562218可增加一个假想的销地了可增加一个假想的销地了B51/8/202368运筹学基础及应用运筹学基础及应用第第3 3章章 运输问题运输问题 销地产地产量 31234081125905671509销 量435641/8/202369