运筹学第三章3.1运输问题模型与性质.ppt

《运筹学第三章3.1运输问题模型与性质.ppt》由会员分享，可在线阅读，更多相关《运筹学第三章3.1运输问题模型与性质.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 特殊的线性规划特殊的线性规划运输问题运输问题&模型及其特点模型及其特点&求解思路及相关理论求解思路及相关理论&求解方法求解方法表上作业法表上作业法&运输问题的推广运输问题的推广产销不平衡的运输问题产销不平衡的运输问题转运问题转运问题3.1 运输问题模型与性质运输问题模型与性质一、运输问题的数学模型一、运输问题的数学模型 1、运运输输问问题题的的一一般般提提法法：某某种种物物资资有有若若干干产产地地和和销销地地，现现在在需需要要把把这这种种物物资资从从各各个个产产地地运运到到各各个个销销地地，产产量量总总数数等等于于销销量量总总数数。已已知知各各产产地地的的产产量量和和各各销销地地

2、的的销销量量以以及及各各产产地地到到各各销销地地的的单单位位运运价价（或或运运距距），问问应应如如何何组组织织调调运运，才才能能使使总总运运费费（或或总总运运输输量量）最省最省？单位单位根据具体问题选择确定根据具体问题选择确定。表表3-1有关信息有关信息单位单位运价运价销销或或运运距距地地产地产地B1B2Bn产产量量A1A2 Amc11c12c1nc21c22c2ncm1cm2cmna1a2 am销销量量b1b2bn2、运输问题的数学模型、运输问题的数学模型 设设xij为为从从产产地地Ai运运往往销销地地Bj的的物物资资数数量量（i=1，m；j=1，n），由由于于从从Ai运运出出的的物物资资总

3、总量量应应等等于于Ai的的产产量量ai，因因此此xij应满足：应满足：同理，运到同理，运到Bj的物资总量应该等于的物资总量应该等于Bj的销量的销量bj，所以，所以xij还应满足：还应满足：总运费为：总运费为：运输问题的数学模型运输问题的数学模型（3-1）二、运输问题的特点与性质二、运输问题的特点与性质1约束方程组的系数矩阵具有特殊的结构约束方程组的系数矩阵具有特殊的结构写出式（写出式（3-1）的系数矩阵）的系数矩阵A，形式如下：，形式如下：m行行n行行矩阵的元素均为矩阵的元素均为1或或0；每一列只有两个元素为每一列只有两个元素为1，其余元素均为，其余元素均为0；列向量列向量Pij=(0,，0，

4、1，0，,0,1,0,0)T，其中两个元素，其中两个元素1分别处于第分别处于第i行和第行和第m+j行。行。将该矩阵分块，特点是：前将该矩阵分块，特点是：前m行构成行构成m个个mn阶矩阵，而且第阶矩阵，而且第k个矩阵只有第个矩阵只有第k行元素全行元素全为为1，其余元素全为，其余元素全为0（k=1，m）；后）；后n行行构成构成m个个n阶单位阵。阶单位阵。2.运输问题的基变量总数是运输问题的基变量总数是m+n-1写出增广矩阵写出增广矩阵写出增广矩阵写出增广矩阵证明系数矩阵证明系数矩阵A及其增广矩阵的秩都是及其增广矩阵的秩都是m+n-1S前前m行相加之和减去后行相加之和减去后n行相加之和结果是行相加之

5、和结果是零向量，说明零向量，说明m+n个行向量线性相关，因此个行向量线性相关，因此的秩小于的秩小于m+n；？因此因此的秩恰好等于的秩恰好等于m+n-1，又，又D本身就含于本身就含于A中，故中，故A的秩也等于的秩也等于m+n-1S由由的第二至的第二至m+n行和前行和前n列及列及对应的列交叉处元素构成对应的列交叉处元素构成m+n-1阶方阵阶方阵D非奇非奇异；异；？可可以以证证明明：m+n个个约约束束方方程程中中的的任任意意m+n-1个个都都是线性无关的是线性无关的。定义定义3.1凡是能排成凡是能排成(3-4)或或(3-5)形形式式的的变变量量集集合合称称为为一一个个闭闭回回路路,并并称称式式中中变

6、变量量为为该该闭闭回回路路的的顶顶点点；其其中中互互不不相同相同,互不相同。互不相同。3.m+n-1个变量构成基变量的充要条件是个变量构成基变量的充要条件是它们不构成闭回路。它们不构成闭回路。X11X13X21X24X33B1B2B3B4A1X12X14A2X22X23A3X31X32X34例例3-1设设m=3，n=4，决策变量，决策变量xij表示从产地表示从产地Ai到销地到销地Bj的调运量，列表如下，给出闭回路的调运量，列表如下，给出闭回路在表中的表示法在表中的表示法用折线连接起来的顶点变量。用折线连接起来的顶点变量。三、运输问题的求解方法三、运输问题的求解方法1、单纯形法（为什么？）、单纯

7、形法（为什么？）2、表上作业法、表上作业法 由于问题的特殊形式而采用的由于问题的特殊形式而采用的更简洁、更方便的方法更简洁、更方便的方法3.2运输问题的表上作业法运输问题的表上作业法一一、表表上上作作业业法法的的基基本本思思想想是是:先先设设法法给给出出一一个个初初始始方方案案,然然后后根根据据确确定定的的判判别别准准则则对对初初始始方方案案进进行行检检查查、调调整整、改改进进，直直至至求求出出最优方案，如图最优方案，如图3-1所示。所示。表表上上作作业业法法和和单单纯纯形形法法的的求求解解思思想想完完全全一一致致，但是具体作法更加简捷。但是具体作法更加简捷。确定初始确定初始方案方案(初初 始

8、始 基本可行解基本可行解)改进调整改进调整（换基迭代）（换基迭代）否否判定是否判定是否最最优？优？是是结结束束最优方案最优方案图图3-1运输问题求解思路图运输问题求解思路图二、二、初始方案的确定初始方案的确定1、作业表（产销平衡表）、作业表（产销平衡表）初始方案就是初始基本可行解。初始方案就是初始基本可行解。将运输问题的有关信息表和决策变量将运输问题的有关信息表和决策变量调运调运量结合在一起构成量结合在一起构成“作业表作业表”（产销平衡表）。（产销平衡表）。表表3-3是两个产地、三个销地的运输问题作业表。是两个产地、三个销地的运输问题作业表。调调销地销地运运量量产地产地B1B2B3产产 量量A

9、1c11X11c12X12c13X13a1A2c21X21c22X22c23X23a2销销量量b1b2b3表表3-3运输问题作业表（产销平衡表）运输问题作业表（产销平衡表）其中其中xij是决策变量，表示待确定的从第是决策变量，表示待确定的从第i个产个产地到第地到第j个销地的调运量，个销地的调运量，cij为从第为从第i个产地到个产地到第第j个销地的单位运价或运距。个销地的单位运价或运距。2、确定初始方案的步骤：、确定初始方案的步骤：（1）选择一个）选择一个xij，令，令xij=minai，bj=将具体数值填入将具体数值填入xij在表中的位置；在表中的位置；（2）调调整整产产销销剩剩余余数数量量：

10、从从ai和和bj中中分分别别减减去去xij的的值值，若若ai-xij=0，则则划划去去产产地地Ai所所在在的的行行，即即该该产产地地产产量量已已全全部部运运出出无无剩剩余余，而而销销地地Bj尚尚有有需需求求缺缺口口bj-ai；若若bj-xij=0，则则划划去去销销地地Bj所所在在的的列列，说说明明该该销销地地需需求求已已得得到到满满足足，而而产产地地Ai尚尚有有存余量存余量ai-bj；（3）当当作作业业表表中中所所有有的的行行或或列列均均被被划划去去，说说明明所所有有的的产产量量均均已已运运到到各各个个销销地地，需需求求全全部部满满足足，xij的的取取值值构构成成初初始始方方案案。否否则则，在

11、在作作业业表表剩剩余余的的格子中选择下一个决策变量，返回步骤（格子中选择下一个决策变量，返回步骤（2）。）。按按照照上上述述步步骤骤产产生生的的一一组组变变量量必必定定不不构构成成闭闭回回路路，其其取取值值非非负负，且且总总数数是是m+n-1个个，因此构成运输问题的基本可行解。因此构成运输问题的基本可行解。对对xij的的选选择择采采用用不不同同的的规规则则就就形形成成各各种种不不同同的的方方法法，常常用用的的方方法法有有最最小小元元素素法法和和伏伏格格尔法。尔法。下面通过具体实例分别介绍。下面通过具体实例分别介绍。3、举例举例例例3-2 甲甲、乙乙两两个个煤煤矿矿供供应应A、B、C三三个个城城

12、市市用用煤煤，各各煤煤矿矿产产量量及及各各城城市市需需煤煤量量、各各煤煤矿矿到到各各城城市市的的运运输输距距离离见见表表3-4，求求使使总总运运输输量量最最少少的的调运方案。调运方案。表表3-4 例例3-2有关信息表有关信息表450200150100日销量（需求量）250756580乙2001007090甲日产量日产量（供应量）（供应量）C B A运距运距 城市城市煤矿煤矿例例3-2 的数学模型的数学模型使用使用最小元素法最小元素法求出初始方案求出初始方案（1）最小元素法最小元素法基本思想是基本思想是“就近供应就近供应”：即从单位运价表或运距表中的最小元素开即从单位运价表或运距表中的最小元素开

13、始确定供销关系，然后次小，一直到给出初始始确定供销关系，然后次小，一直到给出初始基可行解为止。基可行解为止。调调销地销地运运量量产地产地B1B2B3产产 量量A190X1170X12100X13200A280X2165X2275X23250销销量量100150200450用最小元素法确定例用最小元素法确定例3-2初始调运方案初始调运方案150100100100100100100得到初始调运方案为：得到初始调运方案为：x11=100，x13=100，x22=150，x23=100最小元素法的缺点是：为了节省一处的费用，最小元素法的缺点是：为了节省一处的费用，有时造成在其他处要多花几倍的运费有时造

14、成在其他处要多花几倍的运费(运距运距)。（2）伏格尔法）伏格尔法它的基本思想是：它的基本思想是：考虑次小运费考虑次小运费(运距运距)，这就有一个差额。，这就有一个差额。因而对差额最大处，就应当采用最小运费因而对差额最大处，就应当采用最小运费(运距运距)调运。调运。找最大差额的最小运费找最大差额的最小运费用伏格尔法确定例用伏格尔法确定例3-2初始调运方案初始调运方案调销地运产地量ABC日产量(吨)行差额甲90X1170X12100X1320020乙80X2165X2275X2325010日销量(吨)100150200450列差额10525200501515050505050最小最小次小次小差额差

15、额得到初始调运方案为：得到初始调运方案为：x11=50，x12=150，x21=50，x23=200三、最优性检验三、最优性检验检查当前调运方案是不是最优方案的过程检查当前调运方案是不是最优方案的过程就是最优性检验。检查的方法：就是最优性检验。检查的方法：计算非基变量的检验数计算非基变量的检验数 未填上数值的格未填上数值的格未填上数值的格未填上数值的格(空格空格空格空格)空格的检验数空格的检验数空格的检验数空格的检验数 若全部大于等于零，则该方案就是最优调若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。运方案，否则就应进行调整。1、闭回路法、闭回路法以以确确定定初初始始调调运运方

16、方案案的的作作业业表表为为基基础础，以以一个非基变量作为起始顶点，寻求闭回路。一个非基变量作为起始顶点，寻求闭回路。闭回路的特点：闭回路的特点：除除了了起起始始顶顶点点是是非非基基变变量量外外，其其他他顶顶点点均为基变量（对应着填上数值的格）。均为基变量（对应着填上数值的格）。可可以以证证明明，如如果果对对闭闭回回路路的的方方向向不不加加区区别别，对对于于每每一一个个非非基基变变量量而而言言，以以其其为为起起点点的的闭闭回回路路存在且唯一。存在且唯一。约约定定:起起始始顶顶点点为为非非基基变变量量，记记为为偶偶数数次次顶顶点点，其其它它顶顶点点从从1开开始始顺顺次次排排列列，那那么么，该非基变

17、量该非基变量xij的检验数：的检验数：现在，用最小元素法确定例现在，用最小元素法确定例3-2初始调运方案初始调运方案的基础上，计算非基变量的基础上，计算非基变量X12的检验数的检验数：=(闭回路上偶数次顶点运距或运价之和闭回路上偶数次顶点运距或运价之和)(闭回路上奇数次顶点运距或运价之和闭回路上奇数次顶点运距或运价之和)(3-6)调调销地销地运运量量产地产地B1B2B3产产 量量A190X1170X12100X13200A280X2165X2275X23250销销量量100150200450100100100150例例例例3-23-2初始调运方案中以初始调运方案中以初始调运方案中以初始调运方案

18、中以X X1212(X(X2121)为起点的闭回路为起点的闭回路为起点的闭回路为起点的闭回路非基变量非基变量X12的检验数：的检验数：非基变量非基变量X21的检验数：的检验数：=（c12+c23）-（c13+c22）=70+75-(100+65)=-20，=（c21+c13）-（c11+c23）=80+100-（90+75）=15。经经济济含含义义在在保保持持产产销销平平衡衡的的条条件件下下，该该非非基基变变量量增增加加一一个个单单位位运运量量而而成成为为基变量时目标函数值的变化量。基变量时目标函数值的变化量。2、位势法、位势法以例以例3-2初始调运方案为例，设置位势变初始调运方案为例，设置位

19、势变量量和和，在初始调运方案表的基础上增加，在初始调运方案表的基础上增加一行和一列（见下页表格）。一行和一列（见下页表格）。然后构造下面的方程组：然后构造下面的方程组：（3-7）例例3-2初始调运方案位势变量对应表初始调运方案位势变量对应表调调销地销地运运量量产地产地B1B2B3产产 量量A190X1170X12100X13200A280X2165X2275X23250销销量量100150200450位势变量位势变量vjv1v2v3100100100150位势位势变量变量uiu1u2方程组的特点：方程组的特点：方方程程个个数数是是m+n-1=2+3-1=4个个，位位势势变变量量共共有有m+n=

20、2+3=5个个，通通常常称称ui为为第第i行行的的位位势势，称称vj为第为第j列的位势；列的位势；u初始方案的每一个基变量初始方案的每一个基变量xij对应一个方程对应一个方程-所所在在行行和和列列对对应应的的位位势势变变量量之之和和等等于于该该基基变量对应的运距（或运价）：变量对应的运距（或运价）：ui+vj=cij；方程组恰有一个自由变量，可以证明方程组方程组恰有一个自由变量，可以证明方程组中任意一个变量均可取作自由变量。中任意一个变量均可取作自由变量。给给定定自自由由变变量量一一个个值值,解解方方程程组组式式(3-7)，即即可可求求得得位位势势变变量量的的一一组组值值，根根据据式式(3-6

21、)结结合合方程组方程组(3-7)，则计算非基变量，则计算非基变量xij检验数的公式检验数的公式ij=cij-（ui+vj）（3-8）在式在式(3-7)中中,令令u1=0,则可解得则可解得v1=90,v3=100,u2=-25,v2=90，12=c12-（u1+v2）=70-（0+90）=-2021=c21-（u2+v1）=80-（-25+90）=15与前面用闭回路法求得的结果相同。与前面用闭回路法求得的结果相同。四、方案调整四、方案调整当当至至少少有有一一个个非非基基变变量量的的检检验验数数是是负负值值时时，说说明明作作业业表表上上当当前前的的调调运运方方案案不不是是最最优优的的，应应进行调整

22、。进行调整。若若检检验验数数ij小小于于零零，则则首首先先在在作作业业表表上上以以xij为起始变量作出闭回路为起始变量作出闭回路,并求出调整量并求出调整量:ij=min该闭回路中奇数次顶点调运量该闭回路中奇数次顶点调运量xij调调销地销地运运量量产地产地B1B2B3产产 量量A190X1170X12100X13200A280X2165X2275X23250销销量量100150200450100100100150+-上例中上例中上例中上例中 1212=-20=-20，画出以，画出以，画出以，画出以x x1212为起始变量的闭回路为起始变量的闭回路为起始变量的闭回路为起始变量的闭回路 计算调整量：

23、计算调整量：=Min（100，150）=100。按照下面的方法调整调运量：按照下面的方法调整调运量：闭回路上闭回路上：闭回路之外的变量调运量不变。：闭回路之外的变量调运量不变。奇数次顶点的调运量减去奇数次顶点的调运量减去，偶数次顶点的调运量加上偶数次顶点的调运量加上；得到新的得到新的调调运方案运方案：调调销地销地运运量量产地产地B1B2B3产产 量量A190X1170X12100X13200A280X2165X2275X23250销销量量10015020045010010020050重复上面的步骤，直至求出最优调运方案重复上面的步骤，直至求出最优调运方案.调调销地销地运运量量产地产地B1B2B

24、3产产 量量A190X1170X12100X13200A280X2165X2275X23250销销量量1001502004501505020050结结 果果最优调运方案是：最优调运方案是：x11=50，x12=150，x21=50，x23=200相应的最小总运输量为：相应的最小总运输量为：Zmin=9050+70150+8050+75200=34000（吨公里）（吨公里）3.3运输问题的推广运输问题的推广一、产销不平衡的运输问题一、产销不平衡的运输问题供大于求供大于求供不应求供不应求增加虚拟销地增加虚拟销地增加虚拟销地增加虚拟销地增加虚拟产地增加虚拟产地增加虚拟产地增加虚拟产地产销平衡的运输问

25、题产销平衡的运输问题对应的运距（或运价）对应的运距（或运价）？转化转化二、转运问题二、转运问题特特点点:调调运运的的物物资资不不是是由由产产地地直直接接运运送送到到销地，而是经过若干中转站送达。销地，而是经过若干中转站送达。求求解解思思路路：转转化化成成一一个个等等价价的的产产销销平平衡衡运运输输问问题题，再再用用表表上上作作业业法法求求出出最最优调运方案。优调运方案。如何转化如何转化？第第一一步步，将将产产地地、转转运运点点、销销地地重重新新编编排排，转运点既作为产地又作为销地；转运点既作为产地又作为销地；第第二二步步，各各地地之之间间的的运运距距（或或运运价价）在在原原问问题题运运距距（运运价价）表表基基础础上上进进行行扩扩展展：从从一一地地运运往往自自身身的的单单位位运运距距（运运价价）记记为为零零，不不存存在在运运输输线线路路的的则则记记为为M（一一个个足足够够大大的正数）；的正数）；第第三三步步，由由于于经经过过转转运运点点的的物物资资量量既既是是该该点点作作为为销销地地的的需需求求量量，又又是是该该点点作作为为产产地地时时的的供供应应量量，但但事事先先又又无无法法获获取取该该数数量量的的确确切切值值，因因此此通通常常将将调调运总量作为该数值的上界。运总量作为该数值的上界。对于产地和销地也作类似的处理。对于产地和销地也作类似的处理。