运筹学——.运输问题精选文档.ppt

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

1、运筹学.运输问题本讲稿第一页，共四十二页一、运输问题的数学模型一、运输问题的数学模型1 1、运运运运输输输输问问问问题题题题的的的的一一一一般般般般提提提提法法法法：某某种种物物资资有有若若干干产产地地和和销销地地，现现在在需需要要把把这这种种物物资资从从各各个个产产地地运运到到各各个个销销地地，产产产产量量量量总总总总数数数数等等等等于于于于销销销销量量量量总总总总数数数数。已已知知各各产产地地的的产产量量和和各各销销地地的的销销销销量量量量以以及及各各产产地地到到各各销销地地的的单单单单位位位位运运运运价价价价（或或或或运运运运距距距距），问问应应如如何何组织调运，才能使组织调运，才能使总

2、运费（或总运输量）最省总运费（或总运输量）最省总运费（或总运输量）最省总运费（或总运输量）最省？3.1运输问题的典例和数学模型运输问题的典例和数学模型本讲稿第二页，共四十二页例1：产量：A1-7t，A2-4t，A3-9t 销量：B1-3t，B2-6t，B3-5t，B4-6t BjAiB1B2B3B4产量A13113107A219284A3741059需量365620本讲稿第三页，共四十二页单位单位单位单位根据具体问题选择确定。根据具体问题选择确定。产销平衡、单位运价表（表产销平衡、单位运价表（表3-1）单位单位运价运价销销或或运运距距地地产地产地B1B2Bn产产量量A1A2 Amc11c12c

3、1nc21c22c2ncm1cm2cmna1a2 am销销量量b1b2bn本讲稿第四页，共四十二页 2、运输问题的数学模型、运输问题的数学模型 设设xij为为从从产产地地Ai运运往往销销地地Bj的的物物资资数数量量（i=1，m；j=1，n），由由于于从从Ai运运出出的的物物资资总总量量应应等等于于Ai的的产产量量ai，因因此此xij应满足：应满足：本讲稿第五页，共四十二页同理，运到同理，运到Bj的物资总量应该等于的物资总量应该等于Bj的销的销量量bj，所以，所以xij还应满足：还应满足：总运费为：总运费为：本讲稿第六页，共四十二页运输问题的数学模型运输问题的数学模型本讲稿第七页，共四十二页二、

4、运输问题的特点与性质二、运输问题的特点与性质1约束方程组的系数矩阵具有特殊的结构约束方程组的系数矩阵具有特殊的结构写出式（写出式（3-1）的系数矩阵）的系数矩阵A，形式如下：，形式如下：m行行n行行本讲稿第八页，共四十二页矩阵的元素均为矩阵的元素均为1或或0；每一列只有两个元素为每一列只有两个元素为1，其余元素均为，其余元素均为0；列向量列向量Pij=(0,，0，1，0，,0,1,0,0)T，其中两个元素其中两个元素1分别处于第分别处于第i行和第行和第m+j行。行。将该矩阵分块，特点是：将该矩阵分块，特点是：前前m行构成行构成m个个mn阶阶矩阵矩阵，而且，而且第第k个矩阵只有第个矩阵只有第k行

5、元素全为行元素全为1，其余，其余元素全为元素全为0（k=1，m）；后后n行构成行构成m个个n阶单阶单位阵位阵。本讲稿第九页，共四十二页例例1 的数学模型的数学模型本讲稿第十页，共四十二页三、运输问题的求解方法三、运输问题的求解方法1、单纯形法（为什么？）、单纯形法（为什么？）2、表上作业法、表上作业法 由于问题的特殊形式而采用的由于问题的特殊形式而采用的更简洁、更方便的方法更简洁、更方便的方法本讲稿第十一页，共四十二页3.2运输问题的表上作业法运输问题的表上作业法一一、表表上上作作业业法法的的基基本本思思想想是是:先先设设法法给给出出一一个个初初始始方方案案,然然后后根根据据确确定定的的判判别

6、别准准则则对对初初始始方方案案进进行行检检查查、调调整整、改改进进，直直至至求求出出最最优优方方案案，如如图图3-1所示。所示。表表上上作作业业法法和和单单纯纯形形法法的的求求解解思思想想完完全全一一致致，但是具体作法更加简捷。但是具体作法更加简捷。本讲稿第十二页，共四十二页确定初始确定初始方案方案(初初 始始 基本可行解基本可行解)改进调整改进调整（换基迭代）（换基迭代）否否判定是否判定是否最最优？优？是是结结束束最优方案最优方案图图3-1运输问题求解思路图运输问题求解思路图本讲稿第十三页，共四十二页二、二、初始方案的确定初始方案的确定1、作业表（产销平衡表）、作业表（产销平衡表）初始方案就

7、是初始基本可行解。初始方案就是初始基本可行解。将运输问题的有关信息表和决策变量将运输问题的有关信息表和决策变量调运量结调运量结合在一起构成合在一起构成“作业表作业表”（产销平衡表产销平衡表）。）。表表3-2是两个产地、三个销地的运输问题作业表。是两个产地、三个销地的运输问题作业表。本讲稿第十四页，共四十二页调调销地销地运运量量产地产地 B1 B2 B3 产产 量量 A1 c11 X11 c12 X12 c13 X13 a1 A2 c21 X21 c22 X22 c23 X23 a2 销销量量 b1 b2 b3表表3-2运输问题作业表（产销平衡表）运输问题作业表（产销平衡表）本讲稿第十五页，共四

8、十二页其中其中xij是决策变量，表示待确定的从第是决策变量，表示待确定的从第i个产地到个产地到第第j个销地的调运量，个销地的调运量，cij为从第为从第i个产地到第个产地到第j个销个销地的单位运价或运距。地的单位运价或运距。2、确定初始方案的步骤：、确定初始方案的步骤：（1）选择一个）选择一个xij，令，令xij=minai，bj=将具体数值填入将具体数值填入xij在表中的位置；在表中的位置；本讲稿第十六页，共四十二页（2）调调整整产产销销剩剩余余数数量量：从从ai和和bj中中分分别别减减去去xij的的值值，若若ai-xij=0，则则划划去去产产地地Ai所所在在的的行行，即即该该产产地地产产量量

9、已已全全部部运运出出无无剩剩余余，而而销销地地Bj尚尚有有需需求求缺缺口口bj-ai；若若bj-xij=0，则则划划去去销销地地Bj所所在在的的列列，说说明明该该销销地地需需求已得到满足，而产地求已得到满足，而产地Ai尚有存余量尚有存余量ai-bj；（3）当当作作业业表表中中所所有有的的行行或或列列均均被被划划去去，说说明明所所有有的的产产量量均均已已运运到到各各个个销销地地，需需求求全全部部满满足足，xij的的取取值值构构成成初初始始方方案案。否否则则，在在作作业业表表剩剩余余的的格格子子中中选选择择下一个决策变量，返回步骤（下一个决策变量，返回步骤（2）。）。本讲稿第十七页，共四十二页按按

10、照照上上述述步步骤骤产产生生的的一一组组变变量量必必定定不不构构成成闭闭回回路路，其其取取值值非非负负，且且总总数数是是m+n-1个个，因因此此构构成成运输问题的基本可行解运输问题的基本可行解。对对xij的的选选择择采采用用不不同同的的规规则则就就形形成成各各种种不不同同的的方方法法，比比如如每每次次总总是是在在作作业业表表剩剩余余的的格格子子中中选选择择运运价价（或或运运距距）最最小小者者对对应应的的xij，则则构构成成最最小小元元素素法法，若若每每次次都都选选择择左左上上角角格格子子对对应应的的xij就就形成形成西北角法西北角法（也称（也称左上角法左上角法）。）。本讲稿第十八页，共四十二页

11、3、举例举例 例例1：产量：产量：A1-7t，A2-4t，A3-9t 销销量量：B1-3t，B2-6t，B3-5t，B4-6t；求使总运输量最少的调运方案。求使总运输量最少的调运方案。本讲稿第十九页，共四十二页 BjAiB1B2B3B4产量A13113107A219284A3741059需量365620本讲稿第二十页，共四十二页1、最小元素法、最小元素法:求出初始方案。求出初始方案。&最小元素法的基本思想是最小元素法的基本思想是“就近供应就近供应”本讲稿第二十一页，共四十二页 BjAiB1B2B3B4产量A13113107A219284A3741059需量365620用最小元素法确定例用最小元

12、素法确定例1初始调运方案初始调运方案 3114436333本讲稿第二十二页，共四十二页最小元素法实施步骤口诀最小元素法实施步骤口诀运价表运价表上找最小，上找最小，平衡表平衡表上定产销；上定产销；满足销量划去满足销量划去“列列”，修改，修改“行产行产”要记牢；要记牢；（满足产量划去（满足产量划去“行行”，修改，修改“列销列销”要记牢）要记牢）划去列划去列(行行)对对运价运价，修改修改“行产行产(列销列销)”在在产销产销；余表再来找最小，方案很快就找到。余表再来找最小，方案很快就找到。本讲稿第二十三页，共四十二页2、Vogel法法(元素差额法元素差额法):求出初始方案。求出初始方案。第一步：在表中

13、分别计算出各行和各列的最小运费和次最小运费的差第一步：在表中分别计算出各行和各列的最小运费和次最小运费的差第一步：在表中分别计算出各行和各列的最小运费和次最小运费的差第一步：在表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。额，并填入该表的最右列和最下行。额，并填入该表的最右列和最下行。额，并填入该表的最右列和最下行。第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。素

14、。素。素。本讲稿第二十四页，共四十二页用用Vogel法确定初始调运方案法确定初始调运方案 BjAiB1B2B3B4产产量量行行差差额额A13113107A219284A3741059需量36562 0列差列差额额 Bj AiB1B2B3B4产量A1527A2314A3639需量365620本讲稿第二十五页，共四十二页三、最优性检验三、最优性检验检查当前调运方案是不是最优方案的过程就是检查当前调运方案是不是最优方案的过程就是最优性检验。最优性检验。检查的方法：检查的方法：计算非基变量计算非基变量（未填（未填上数值的格，即空格）上数值的格，即空格）的检验数的检验数（也称为（也称为空格空格的检验数的

15、检验数），若全部大于等于零，则该方案就是），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。最优调运方案，否则就应进行调整。本讲稿第二十六页，共四十二页1 1、闭回路法、闭回路法、闭回路法、闭回路法 以以以以确确确确定定定定了了了了初初初初始始始始调调调调运运运运方方方方案案案案的的的的作作作作业业业业表表表表为为为为基基基基础础础础，以以以以一一一一个个个个非非非非基基基基变变变变量量量量作为起始顶点，寻求闭回路。作为起始顶点，寻求闭回路。作为起始顶点，寻求闭回路。作为起始顶点，寻求闭回路。该该该该闭闭闭闭回回回回路路路路的的的的特特特特点点点点是是是是：除除了了起起始始顶顶点

16、点是是非非基基变变量量外外，其其他顶点均为基变量（对应着填上数值的格）。他顶点均为基变量（对应着填上数值的格）。可可可可以以以以证证证证明明明明，如如如如果果果果对对对对闭闭闭闭回回回回路路路路的的的的方方方方向向向向不不不不加加加加区区区区别别别别，对对对对于于于于每每每每一一一一个个个个非非非非基变量而言，以其为起点的闭回路基变量而言，以其为起点的闭回路基变量而言，以其为起点的闭回路基变量而言，以其为起点的闭回路存在且唯一存在且唯一存在且唯一存在且唯一。本讲稿第二十七页，共四十二页闭回路法计算非基变量闭回路法计算非基变量xij ij检验数的公式：检验数的公式：=（闭回路上奇数次顶点运距或运

17、价之和）（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和）（闭回路上偶数次顶点运距或运价之和）当检验数还存在负数时，说明原方案还不是最优解。当检验数还存在负数时，说明原方案还不是最优解。本讲稿第二十八页，共四十二页闭回路法最小元素法初始方案 B1 B2 B3 B4产量A13113107A219284A3741059需量365620 B1 B2 B3 B4产量A1437A2314A3（10）639需量365620本讲稿第二十九页，共四十二页检验数 B1B2B3B4产量A1（1）（2）437A23（1）1（1）4A3（10）6（12）39需量365620本讲稿第三十页，共四

18、十二页2、位势法、位势法以例以例1初始调运方案为例，设置初始调运方案为例，设置位势变量位势变量和和，在初始调运方案表的基础上增在初始调运方案表的基础上增加一行和一列。加一行和一列。BjAiB1B2B3B4ujA1311310u1A21928u2A374105u3viv1v2v3v4本讲稿第三十一页，共四十二页检验数检验数各空格的检验数，令各空格的检验数，令代表空格（代表空格（Ai ,Bj）的检）的检验数。验数。当检验数还存在负检验数时，说明未得到最优解，当检验数还存在负检验数时，说明未得到最优解，还可以改进。还可以改进。如果表中出现有负的检验数时，对方案进行改进和如果表中出现有负的检验数时，对

19、方案进行改进和调整的访求同前面闭回路法调整一样。调整的访求同前面闭回路法调整一样。本讲稿第三十二页，共四十二页方案调整闭回路法 B1B2B3B4产量A1（1）（2）437A23（1）1（1）4A3（10）6（12）39需量365620本讲稿第三十三页，共四十二页调整结果 B1B2B3B4产量A1（0）（2）527A23（2）（1）14A3（9）6（12）39需量365620本讲稿第三十四页，共四十二页位势法计算非基变量位势法计算非基变量xij检验数的公式检验数的公式=（闭回路上偶数次顶点运距或运价之和）（闭回路上偶数次顶点运距或运价之和）-（闭回路上奇数次顶点运距或运价之和）（闭回路上奇数次顶

20、点运距或运价之和）闭回路法计算非基变量闭回路法计算非基变量xij检验数的公式：检验数的公式：复习比较检验数计算的两种方法复习比较检验数计算的两种方法本讲稿第三十五页，共四十二页四、方案调整四、方案调整当当至至少少有有一一个个非非基基变变量量的的检检验验数数是是负负值值时时，说说明明作业表上当前的调运方案不是最优的，应进行调整。作业表上当前的调运方案不是最优的，应进行调整。若若检检验验数数小小于于零零，则则首首先先在在作作业业表表上上以以xij为为起起始变量作出闭回路始变量作出闭回路，并，并求出调整量求出调整量：ij=min该闭回路中该闭回路中奇数次奇数次顶点调运量顶点调运量xij本讲稿第三十六

21、页，共四十二页3.3运输问题的推广运输问题的推广一、产销不平衡的运输问题一、产销不平衡的运输问题供大于求供大于求供不应求供不应求增加虚拟销地增加虚拟销地增加虚拟销地增加虚拟销地增加虚拟产地增加虚拟产地产销平衡的运输问题产销平衡的运输问题对应的运距（或运价）对应的运距（或运价）？转化转化本讲稿第三十七页，共四十二页二、转运问题二、转运问题特特点点是是所所调调运运的的物物资资不不是是由由产产地地直直接接运运送送到到销销地，而是经过若干中转站送达。地，而是经过若干中转站送达。求求解解思思路路：转转化化成成一一个个等等价价的的产产销销平平衡衡运运输输问问题，再用表上作业法求出最优调运方案。题，再用表上

22、作业法求出最优调运方案。如何转化如何转化？本讲稿第三十八页，共四十二页第第一一步步，将将产产地地、转转运运点点、销销地地重重新新编编排排，转运点既作为产地又作为销地；转运点既作为产地又作为销地；第第二二步步，各各地地之之间间的的运运距距（或或运运价价）在在原原问问题题运运距距（运运价价）表表基基础础上上进进行行扩扩展展：从从一一地地运运往往自自身身的的单单位位运运距距（运运价价）记记为为零零，不不存存在运输线路的则记为在运输线路的则记为M（一个足够大的正数）；（一个足够大的正数）；本讲稿第三十九页，共四十二页第第三三步步，由由于于经经过过转转运运点点的的物物资资量量既既是是该该点点作作为为销销地地的的需需求求量量，又又是是该该点点作作为为产产地地时时的的供供应应量量，但但事事先先又又无无法法获获取取该该数数量量的的确确切切值值，因因此此通通常常将将调调运总量作为该数值的上界运总量作为该数值的上界。对于产地和销地也作类似的处理。对于产地和销地也作类似的处理。本讲稿第四十页，共四十二页作业P101:3.1本讲稿第四十一页，共四十二页Thanks for Attention!Q and A本讲稿第四十二页，共四十二页