运筹学——.运输问题优秀PPT.ppt

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

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

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

3、输问题的数学模型 设设xij为为从从产产地地Ai运运往往销销地地Bj的的物物资资数数量量（i=1，m；j=1，n），由由于于从从Ai运运出出的的物物资资总总量量应应等等于于Ai的的产产量量ai，因因此此xij应满足：应满足：第五页，本课件共有42页同理，运到同理，运到Bj的物资总量应该等于的物资总量应该等于Bj的的销量销量bj，所以，所以xij还应满足：还应满足：总运费为：总运费为：第六页，本课件共有42页运输问题的数学模型运输问题的数学模型第七页，本课件共有42页二、运输问题的特点与性质二、运输问题的特点与性质1约束方程组的系数矩阵具有特殊的结构约束方程组的系数矩阵具有特殊的结构写出式（写出

4、式（3-1）的系数矩阵）的系数矩阵A，形式如下：，形式如下：m行行n行行第八页，本课件共有42页矩阵的元素均为矩阵的元素均为1或或0；每一列只有两个元素为每一列只有两个元素为1，其余元素均为，其余元素均为0；列向量列向量Pij=(0,，0，1，0，,0,1,0,0)T，其中两个元素其中两个元素1分别处于第分别处于第i行和第行和第m+j行。行。将该矩阵分块，特点是：将该矩阵分块，特点是：前前m行构成行构成m个个mn阶矩阵阶矩阵，而且，而且第第k个矩阵只有第个矩阵只有第k行元素全为行元素全为1，其余元素全为其余元素全为0（k=1，m）；后后n行构成行构成m个个n阶单位阵阶单位阵。第九页，本课件共有

5、42页例例1 的数学模型的数学模型第十页，本课件共有42页三、运输问题的求解方法三、运输问题的求解方法1、单纯形法（为什么？）、单纯形法（为什么？）2、表上作业法、表上作业法 由于问题的特殊形式而采用的更由于问题的特殊形式而采用的更简洁、更方便的方法简洁、更方便的方法第十一页，本课件共有42页3.2运输问题的表上作业法运输问题的表上作业法一一、表表上上作作业业法法的的基基本本思思想想是是:先先设设法法给给出出一一个个初初始始方方案案,然然后后根根据据确确定定的的判判别别准准则则对对初初始始方方案案进进行行检检查查、调调整整、改改进进，直直至至求求出出最最优优方方案案，如图如图3-1所示。所示。

6、表表上上作作业业法法和和单单纯纯形形法法的的求求解解思思想想完完全全一一致致，但是具体作法更加简捷。但是具体作法更加简捷。第十二页，本课件共有42页确定初始确定初始方案方案(初初 始始 基本可行解基本可行解)改进调整改进调整（换基迭代）（换基迭代）否否判定是否判定是否最最优？优？是是结结束束最优方案最优方案图图3-1运输问题求解思路图运输问题求解思路图第十三页，本课件共有42页二、二、初始方案的确定初始方案的确定1、作业表（产销平衡表）、作业表（产销平衡表）初始方案就是初始基本可行解。初始方案就是初始基本可行解。将运输问题的有关信息表和决策变量将运输问题的有关信息表和决策变量调运量调运量结合在

7、一起构成结合在一起构成“作业表作业表”（产销平衡表产销平衡表）。）。表表3-2是两个产地、三个销地的运输问题作业表。是两个产地、三个销地的运输问题作业表。第十四页，本课件共有42页调调销地销地运运量量产地产地 B1 B2 B3 产产 量量 A1 c11 X11 c12 X12 c13 X13 a1 A2 c21 X21 c22 X22 c23 X23 a2 销销量量 b1 b2 b3表表3-2运输问题作业表（产销平衡表）运输问题作业表（产销平衡表）第十五页，本课件共有42页其中其中xij是决策变量，表示待确定的从第是决策变量，表示待确定的从第i个产地个产地到第到第j个销地的调运量，个销地的调运

8、量，cij为从第为从第i个产地到第个产地到第j个销地的单位运价或运距。个销地的单位运价或运距。2、确定初始方案的步骤：、确定初始方案的步骤：（1）选择一个）选择一个xij，令，令xij=minai，bj=将具体数值填入将具体数值填入xij在表中的位置；在表中的位置；第十六页，本课件共有42页（2）调调整整产产销销剩剩余余数数量量：从从ai和和bj中中分分别别减减去去xij的的值值，若若ai-xij=0，则则划划去去产产地地Ai所所在在的的行行，即即该该产产地地产产量量已已全全部部运运出出无无剩剩余余，而而销销地地Bj尚尚有有需需求求缺缺口口bj-ai；若若bj-xij=0，则则划划去去销销地地

9、Bj所所在在的的列列，说说明明该该销销地地需需求求已已得得到到满满足足，而而产产地地Ai尚尚有有存存余余量量ai-bj；（3）当当作作业业表表中中所所有有的的行行或或列列均均被被划划去去，说说明明所所有有的的产产量量均均已已运运到到各各个个销销地地，需需求求全全部部满满足足，xij的的取取值值构构成成初初始始方方案案。否否则则，在在作作业业表表剩剩余余的的格格子中子中选择选择下一个决策变量，返回步骤（下一个决策变量，返回步骤（2）。）。第十七页，本课件共有42页按按照照上上述述步步骤骤产产生生的的一一组组变变量量必必定定不不构构成成闭闭回回路路，其其取取值值非非负负，且且总总数数是是m+n-1

10、个个，因因此构成此构成运输问题的基本可行解运输问题的基本可行解。对对xij的的选选择择采采用用不不同同的的规规则则就就形形成成各各种种不不同同的的方方法法，比比如如每每次次总总是是在在作作业业表表剩剩余余的的格格子子中中选选择择运运价价（或或运运距距）最最小小者者对对应应的的xij，则则构构成成最最小小元元素素法法，若若每每次次都都选选择择左左上上角角格格子子对对应应的的xij就就形成形成西北角法西北角法（也称（也称左上角法左上角法）。）。第十八页，本课件共有42页3、举例举例 例例1：产量：产量：A1-7t，A2-4t，A3-9t 销销量量：B1-3t，B2-6t，B3-5t，B4-6t；求

11、使总运输量最少的调运方案。求使总运输量最少的调运方案。第十九页，本课件共有42页 BjAiB1B2B3B4产量A13113107A219284A3741059需量365620第二十页，本课件共有42页1、最小元素法、最小元素法:求出初始方案。求出初始方案。&最小元素法的基本思想是最小元素法的基本思想是“就近供应就近供应”第二十一页，本课件共有42页 BjAiB1B2B3B4产量A13113107A219284A3741059需量365620用最小元素法确定例用最小元素法确定例1初始调运方案初始调运方案 3114436333第二十二页，本课件共有42页最小元素法实施步骤口诀最小元素法实施步骤口诀

12、运价表运价表上找最小，上找最小，平衡表平衡表上定产销；上定产销；满足销量划去满足销量划去“列列”，修改，修改“行产行产”要记牢；要记牢；（满足产量划去（满足产量划去“行行”，修改，修改“列销列销”要记牢）要记牢）划去列划去列(行行)对对运价运价，修改修改“行产行产(列销列销)”在在产销产销；余表再来找最小，方案很快就找到。余表再来找最小，方案很快就找到。第二十三页，本课件共有42页2、Vogel法法(元素差额法元素差额法):求出初始方案。求出初始方案。第一步：在表中分别计算出各行和各列的最小运费和次最小运费的差第一步：在表中分别计算出各行和各列的最小运费和次最小运费的差第一步：在表中分别计算出

13、各行和各列的最小运费和次最小运费的差第一步：在表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。额，并填入该表的最右列和最下行。额，并填入该表的最右列和最下行。额，并填入该表的最右列和最下行。第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。素。素。素。第二十四页，本课件共有42页用用Vogel法确定初始调运方案法确定初始调运方案 BjAiB1B2B3B4产产量量行行差差

14、额额A13113107A219284A3741059需量36562 0列差列差额额 Bj AiB1B2B3B4产量A1527A2314A3639需量365620第二十五页，本课件共有42页三、最优性检验三、最优性检验检查当前调运方案是不是最优方案的过程检查当前调运方案是不是最优方案的过程就是最优性检验。就是最优性检验。检查的方法：检查的方法：计算非基变量计算非基变量（未填上数值的格，即空格）（未填上数值的格，即空格）的检验数的检验数（也（也称为称为空格的检验数空格的检验数），若全部大于等于零，则该），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。方案就是最优调运方案，否则就应进

15、行调整。第二十六页，本课件共有42页1 1、闭回路法、闭回路法、闭回路法、闭回路法以以确确定定了了初初始始调调运运方方案案的的作作业业表表为为基基础础，以以一一个个非非基变量作为起始顶点，寻求闭回路。基变量作为起始顶点，寻求闭回路。该该闭闭回回路路的的特特点点是是：除除了了起起始始顶顶点点是是非非基基变变量量外外，其其他顶点均为基变量（对应着填上数值的格）。他顶点均为基变量（对应着填上数值的格）。可可以以证证明明，如如果果对对闭闭回回路路的的方方向向不不加加区区别别，对对于于每每一一个个非基变量而言，以其为起点的闭回路非基变量而言，以其为起点的闭回路存在且唯一存在且唯一。第二十七页，本课件共有

16、42页闭回路法计算非基变量闭回路法计算非基变量xij ij检验数的公式：检验数的公式：=（闭回路上奇数次顶点运距或运价之和）（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和）（闭回路上偶数次顶点运距或运价之和）当检验数还存在负数时，说明原方案还不是最优解。当检验数还存在负数时，说明原方案还不是最优解。第二十八页，本课件共有42页闭回路法最小元素法初始方案 B1 B2 B3 B4产量A13113107A219284A3741059需量365620 B1 B2 B3 B4产量A1437A2314A3（10）639需量365620第二十九页，本课件共有42页检验数 B1B2B

17、3B4产量A1（1）（2）437A23（1）1（1）4A3（10）6（12）39需量365620第三十页，本课件共有42页2、位势法、位势法以例以例1初始调运方案为例，设置初始调运方案为例，设置位势变量位势变量和和，在初始调运方案表的基础上增在初始调运方案表的基础上增加一行和一列。加一行和一列。BjAiB1B2B3B4ujA1311310u1A21928u2A374105u3viv1v2v3v4第三十一页，本课件共有42页检验数检验数各空格的检验数，令各空格的检验数，令代表空格（代表空格（Ai ,Bj）的检验数。的检验数。当检验数还存在负检验数时，说明未得到最优当检验数还存在负检验数时，说明未

18、得到最优解，还可以改进。解，还可以改进。如果表中出现有负的检验数时，对方案进行改进如果表中出现有负的检验数时，对方案进行改进和调整的访求同前面闭回路法调整一样。和调整的访求同前面闭回路法调整一样。第三十二页，本课件共有42页方案调整闭回路法 B1B2B3B4产量A1（1）（2）437A23（1）1（1）4A3（10）6（12）39需量365620第三十三页，本课件共有42页调整结果 B1B2B3B4产量A1（0）（2）527A23（2）（1）14A3（9）6（12）39需量365620第三十四页，本课件共有42页位势法计算非基变量位势法计算非基变量xij检验数的公式检验数的公式=（闭回路上偶数

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

20、并，并求出调整量求出调整量：ij=min该闭回路中该闭回路中奇数次奇数次顶点调运量顶点调运量xij第三十六页，本课件共有42页3.3运输问题的推广运输问题的推广一、产销不平衡的运输问题一、产销不平衡的运输问题供大于求供大于求供不应求供不应求增加虚拟销地增加虚拟销地增加虚拟产地增加虚拟产地增加虚拟产地增加虚拟产地产销平衡的运输问题产销平衡的运输问题对应的运距（或运价）对应的运距（或运价）？转化转化第三十七页，本课件共有42页二、转运问题二、转运问题特特点点是是所所调调运运的的物物资资不不是是由由产产地地直直接接运运送送到销地，而是经过若干中转站送达。到销地，而是经过若干中转站送达。求求解解思思路

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