运筹学表上作业法.pptx

《运筹学表上作业法.pptx》由会员分享，可在线阅读，更多相关《运筹学表上作业法.pptx（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运输问题求解之表上作业法运输问题求解之表上作业法1.运输问题模型及其求解思路运输问题模型及其求解思路2.确定初始基本可行解确定初始基本可行解3.最优性检验最优性检验4.方案调整方案调整第1页/共43页1.运输问题模型及其求解思路运输问题模型及其求解思路运输问题：研究把某种商品从若干个产地运至若干个销售地而使总运费最小的一类问题。目标：1总运费最小第2页/共43页 1.运输问题模型及其求解思路运输问题模型及其求解思路 销地产地B1B2Bn产量A1A2:Amc11c21:cm1c12c22:cm2:c1nc2n:cmna1a2:am销量b1b2bnv已知有m个产地Ai（i=1,2，m）可供应某种物

2、资，其供应量（产量）分别为ai，有n个销地Bj（j=1,2，n）其销量（需求量）分别为bj，从A到B的单位物资运价为cij。第3页/共43页若设若设 代表从第代表从第Ai个产地到第个产地到第Bj个销售地的调运量，个销售地的调运量，在在产销平衡产销平衡的条件下（的条件下（），要确定总运输费），要确定总运输费用最小的调运方案，可表示为如下的数学模型用最小的调运方案，可表示为如下的数学模型s.t.(i=1，2，m；j=1，2，n)矩阵形式：s.t.1.运输问题模型及其求解思路运输问题模型及其求解思路第4页/共43页1 1 1 1 1 11 1 11 1 11 1 11 1 1 A=m 行n 行 1.

3、运输问题模型及其求解思路运输问题模型及其求解思路系数矩阵第5页/共43页2 1.运输问题模型及其求解思路运输问题模型及其求解思路对于产销平衡的运输问题，对于产销平衡的运输问题，若产地为若产地为m个，销地为个，销地为n个，个，则则 变量个数为变量个数为mn个，个，约束条件个数为约束条件个数为m+n，其中包含：总产量总销售其中包含：总产量总销售故线性无关的约束条件个数为故线性无关的约束条件个数为m+n-1，基本解中的基变量个数为基本解中的基变量个数为m+n-1。第6页/共43页运输问题求解思路运输问题求解思路表上作业法表上作业法由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则

4、无由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法表上作业法。1.运输问题模型及其求解思路运输问题模型及其求解思路第7页/共43页表上作业法是单纯形法在求解产销平衡的运输问题时的表上作业法是单纯形法在求解产销平衡的运输问题时的一种简化方法，其实质仍是单纯形法，所不同的只是完一种简化方法，其实质仍是单纯形法，所不同的只是完成各步采用的具体形式。成各步采用的具体形式。具体操作步骤如下：具体操作步骤如下：（1）确

5、定一个初始基本可行解：即在）确定一个初始基本可行解：即在mn阶产销平衡阶产销平衡表上给出表上给出m+n-1个数字格（个数字格（基变量基变量）；）；（2）求各非基变量（空格）的检验数，即在表上）求各非基变量（空格）的检验数，即在表上计算空格的计算空格的检验数检验数。判别式否达到最优解。如果是最优。判别式否达到最优解。如果是最优解，则停止计算，否则进入下一步。解，则停止计算，否则进入下一步。（3）确定换入变量和换出变量，找出新的基可行解。）确定换入变量和换出变量，找出新的基可行解。（4）重复）重复(2)、(3)直至得到最优解为止直至得到最优解为止。1.运输问题模型及其求解思路运输问题模型及其求解思

6、路第8页/共43页2.确定初始基本可行解确定初始基本可行解1）最小元素法）最小元素法 基本思想：基本思想：就近供应就近供应，按运价最小的优先调运原则确，按运价最小的优先调运原则确定初始方案，即从单位运价表中选择运价定初始方案，即从单位运价表中选择运价最小的开始确定调运关系，然后次小。若最小的开始确定调运关系，然后次小。若某行（列）的产量（销量）已满足，则把某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，该行（列）的其他格划去。如此进行下去，一直到给出初始基可行解为止一直到给出初始基可行解为止。第9页/共43页例如，某公司经营某种产品，该公司下设例如，某公司经营某种产品

7、，该公司下设A、B、C三三个生产厂，有甲、乙、丙、丁四个销售点。公司每天个生产厂，有甲、乙、丙、丁四个销售点。公司每天把三个工厂生产的产品分别运往四个销售点，各工厂把三个工厂生产的产品分别运往四个销售点，各工厂到各销售点的路程不同，单位产品的运费不同。各工到各销售点的路程不同，单位产品的运费不同。各工厂每日的产量、各销售点每日的销量，以及从各工厂厂每日的产量、各销售点每日的销量，以及从各工厂到各销售点单位产品的运价如下表。问该公司如何调到各销售点单位产品的运价如下表。问该公司如何调运产品，在满足各销售点需要的前提下，使运产品，在满足各销售点需要的前提下，使总运费最总运费最小小。甲甲乙乙丙丙丁丁

8、产量产量A3113107B19284C741059销量销量36562.确定初始基本可行解确定初始基本可行解第10页/共43页s.t2.确定初始基本可行解确定初始基本可行解v若设 代表从第i个产地到第j个销售地的运输量（i=1,2,3；j=1,2,3,4)第11页/共43页B1B2B3B4产量产量A13113107A219284A3741059销量销量36563431632.确定初始基本可行解确定初始基本可行解Z=43+310+31+12+64+35=86第12页/共43页为保证基变量的个数有为保证基变量的个数有m+n-1个，个，1、每次填完数，只能划去一行或一列，只有最后一个、每次填完数，只能

9、划去一行或一列，只有最后一个格子例外。格子例外。2、用最小元素法时，可能会出现基变量个数还差两个、用最小元素法时，可能会出现基变量个数还差两个以上但只剩下一行或一列的情况，此时不能将剩下行或以上但只剩下一行或一列的情况，此时不能将剩下行或列按空格划掉，应在剩下的空格中标上列按空格划掉，应在剩下的空格中标上0。（退化的基。（退化的基本可行解）本可行解）2.确定初始基本可行解确定初始基本可行解注意：注意：第13页/共43页B1B2B3B4产量产量A13113108A219283A3741059销量销量36563530632.确定初始基本可行解确定初始基本可行解第14页/共43页）伏格尔法）伏格尔法

10、伏格尔法的基本思想：如果某一地的产品不能按最小运费就近供应，就考伏格尔法的基本思想：如果某一地的产品不能按最小运费就近供应，就考虑次小运费，两者间就有一个差额。差额越大，说明虑次小运费，两者间就有一个差额。差额越大，说明费用增量费用增量越大。因而越大。因而对差额最大处，优先采用最小运费调运。对差额最大处，优先采用最小运费调运。步骤：步骤：分别计算表中各行和各列中分别计算表中各行和各列中最小运费和次小运费的差最小运费和次小运费的差 额额，并填入表，并填入表中的最右列和最下行。中的最右列和最下行。从行和列的差额中选出最大者，选择其所在行或列中的最小元素，按类从行和列的差额中选出最大者，选择其所在行

11、或列中的最小元素，按类似于最小元素法优先供应，划去相应的行或列。似于最小元素法优先供应，划去相应的行或列。对表中未划去的元素，重复对表中未划去的元素，重复，直到所有的行和列都划完为止。，直到所有的行和列都划完为止。2.确定初始基本可行解确定初始基本可行解第15页/共43页B1B2B3B4两最小元素之差两最小元素之差A1311310A21928A374105两最小元素之差两最小元素之差2.确定初始基本可行解确定初始基本可行解0112513第16页/共43页B1B2B3B4两最小元素之差两最小元素之差A13113100A219281A3741052两最小元素之两最小元素之差差2132.确定初始基本

12、可行解确定初始基本可行解第17页/共43页B1B2B3B4两最小元素之差两最小元素之差A13113100A219281A374105两最小元素之两最小元素之差差2122.确定初始基本可行解确定初始基本可行解第18页/共43页B1B2B3B4两最小元素之差两最小元素之差A13113107A219286A374105两最小元素之两最小元素之差差122.确定初始基本可行解确定初始基本可行解第19页/共43页B1B2B3B4两最小元素之差两最小元素之差A1311310A21928A374105两最小元素之两最小元素之差差22.确定初始基本可行解确定初始基本可行解第20页/共43页B1B2B3B4两最小

13、元素之差两最小元素之差A1311310A21928A374105两最小元素之两最小元素之差差2.确定初始基本可行解确定初始基本可行解第21页/共43页B1B2B3B4产量产量A1527A2314A3639销量销量36562.确定初始基本可行解确定初始基本可行解Z=53+210+31+18+64+35=85第22页/共43页3.最优性检验最优性检验检验数的意义：非基变量增加一个单位，使目标函数值检验数的意义：非基变量增加一个单位，使目标函数值增加的数量。增加的数量。运输问题中目标函数值要求最小化，因此，当所有的检运输问题中目标函数值要求最小化，因此，当所有的检验数都验数都大于或等于零大于或等于零

14、时该调运方案就是最优方案；否则时该调运方案就是最优方案；否则不是。不是。下面介绍两种计算检验数的方法：下面介绍两种计算检验数的方法：第23页/共43页1 1、闭回路法、闭回路法闭回路：在已给出基本解的运输表上，从一个非基变量出发，沿水平或竖直方向前闭回路：在已给出基本解的运输表上，从一个非基变量出发，沿水平或竖直方向前进，只有碰到基变量，才能向右或向左转进，只有碰到基变量，才能向右或向左转9090o o(当然也可以不改变方向）继续前进。当然也可以不改变方向）继续前进。这样继续下去，总能回到出发的那个非基变量，由此路线形成的封闭曲线，叫闭回这样继续下去，总能回到出发的那个非基变量，由此路线形成的

15、封闭曲线，叫闭回路。路。3.最优性检验最优性检验第24页/共43页3.最优性检验最优性检验B1B2B3B4产量产量A13113 410 37A21 392 184A374 6105 39销量销量3656v若让若让x111，则总运费变化：，则总运费变化：31+231。11=1v若让若让x311，则总运费变化：，则总运费变化：75+103+2-110。31=10第25页/共43页3.最优性检验最优性检验63 24=-13B49 33=126 31=10A3563销量销量41 22=13A274 12=2A1产量产量B3B2B1 11=1v最优标准：所有检验数最优标准：所有检验数 ij 0第26页/

16、共43页2、位势法、位势法闭回路法的缺点：当变量个数较多时，寻找闭回路以及计闭回路法的缺点：当变量个数较多时，寻找闭回路以及计算两方面都容易出错。算两方面都容易出错。位势法检验步骤：位势法检验步骤：1）设产地）设产地Ai对应的位势量为对应的位势量为ui，销地，销地Bj对应的位势量为对应的位势量为vj；2）由）由 ij=Cij-（Ui+Vj）,利用对基变量而言有利用对基变量而言有 ij=0，计算计算位势位势Ui，Vj，即即Cij-（Ui+Vj）=0，令，令U1=0；3）再由）再由 ij=Cij-（Ui+Vj）计算非基变量的检验数计算非基变量的检验数 ij3.最优性检验最优性检验第27页/共43页

17、B1B2B3B4uiA13 11 3 410 3A21 39 2 18A37 4 6105 3vju1 u2u3v1v2v3v40103-1-5293.最优性检验最优性检验第28页/共43页B1B2B3B4uiA13 11 3 410 30A21 39 2 18-1A37 4 6105 3-5vj29310 ij=Cij-（Ui+Vj）11=C11-（U1+V1）=3-(0+2)=1 12=C12-（U1+V2）=11-(0+9)=2(1)(2)3.最优性检验最优性检验第29页/共43页B1B2B3B4产量产量A1437A2314A3639销量销量36563.最优性检验最优性检验 33=12

18、11=1 22=1 31=10 24=-1 12=2当存在非基变量的检验数当存在非基变量的检验数 ij 0，说明现行方案为最，说明现行方案为最优方案，否则目标成本还可以进一步减小。优方案，否则目标成本还可以进一步减小。第30页/共43页3.最优性检验最优性检验1、闭回路法计算式：、闭回路法计算式：ij=(闭回路上的奇数顶点运价之和闭回路上的奇数顶点运价之和)-(闭回路上的偶数顶点运价之和闭回路上的偶数顶点运价之和)2、位势法计算式：、位势法计算式：ij=cij-ui vj 当存在非基变量的检验数当存在非基变量的检验数 ij 0，说明现行方案为，说明现行方案为最优方案，否则目标成本还可以进一步减

19、小。最优方案，否则目标成本还可以进一步减小。第31页/共43页4.方案调整方案调整闭回路调整法步骤：闭回路调整法步骤：1、入基变量的确定：选负检验数中最小者、入基变量的确定：选负检验数中最小者 rk，那么，那么 xrk 作为进基变量；（使总运作为进基变量；（使总运费尽快减少）费尽快减少）2、出基变量的确定：在进基变量、出基变量的确定：在进基变量xrk 的闭回路上，选取偶数顶点上调运量最小的值，的闭回路上，选取偶数顶点上调运量最小的值，将其对应的运量作为出基变量。（刚好有一个基变量出基，其它基变量都为正）将其对应的运量作为出基变量。（刚好有一个基变量出基，其它基变量都为正）第32页/共43页4.

20、方案调整方案调整即求即求=Minxij 闭回路上的偶数顶点的闭回路上的偶数顶点的xij=xpq。那么确定那么确定xpq为出基变量，为出基变量，为调整量；为调整量；3、换基调整：对闭回路的奇数顶点运量调整为：、换基调整：对闭回路的奇数顶点运量调整为：xij+，对各偶数顶点运量调整为：，对各偶数顶点运量调整为：xij-，特别，特别 xpq-=0，xpq变为非基变量。变为非基变量。重复以上步骤，直到所有检验数均非负，即得到重复以上步骤，直到所有检验数均非负，即得到最优解。最优解。第33页/共43页4.方案调整方案调整B1B2B3B4产量产量A13 （1）11 （2）3 410 37A21 39 （1

21、）2 18 （-1）4A37 （10）4 610 （12）5 39销量销量3656最小检验数最小检验数原则，确定原则，确定进基变量进基变量最小偶点原则，最小偶点原则，确定出基变量和确定出基变量和调整量调整量+1-1+1-1第34页/共43页四、方案调整B1B2B3B4产量产量aiA13 11 3 5 10 2 7A21 39 2 8 14A37 4 610 5 39销量销量bj3656v得到新的基变量：得到新的基变量：x13=5,x14=2,x21=3,x24=1,x32=6,x34=3。重新计算检验数。重新计算检验数。（1）（2）（2）（1）（9）（12）第35页/共43页四、方案调整经过一

22、次基变换，所有经过一次基变换，所有 ij 0，已得到最优解：，已得到最优解：x13=5,x14=2,x21=3,x24=1,x32=6,x34=3，其它为，其它为0。最优值：最优值：f*=35+102+13+81+46+53=85第36页/共43页表上作业法计算中的相关问题表上作业法计算中的相关问题1.无穷多最优解当最优方案中存在某空格（非基变量）检验数为当最优方案中存在某空格（非基变量）检验数为0,时，则该运输问题一定时，则该运输问题一定有多重最优解。有多重最优解。2.退化解当运输问题的最优表中有数格（基变量）的运量为当运输问题的最优表中有数格（基变量）的运量为0，则出现退化。，则出现退化。

23、1）确定基本可行解中，出现同时需要划去一行和一列的情况，则需要在）确定基本可行解中，出现同时需要划去一行和一列的情况，则需要在填写数格的行或列上，写上一个填写数格的行或列上，写上一个0数格。数格。2）在闭回路中进行调整时，如同时有）在闭回路中进行调整时，如同时有t(t1)个最小数格时，则只有一个个最小数格时，则只有一个运量为运量为0的数格必须出基，其余的必须补上（的数格必须出基，其余的必须补上（t-1)个个0数格。数格。第37页/共43页产销不平衡运输问题产销不平衡运输问题当产大于销：当产大于销：s.t.(i=1，2，m；j=1，2，n)s.t.(i=1，2，m；j=1，2，n+1)第38页/

24、共43页产销不平衡运输问题产销不平衡运输问题 销地产地B1B2B3产量A1646300A2655300销量150150200 销地产地B1B2B3B4(虚销地）虚销地）产量 A16460300A26550300销量150150200100第39页/共43页产销不平衡运输问题产销不平衡运输问题当产小于销：当产小于销：s.t.(i=1，2，m；j=1，2，n)s.t.(i=1，2，m+1；j=1，2，n)第40页/共43页产销不平衡运输问题产销不平衡运输问题 销地产地B1B2B3产量A1646200A2655300销量250200200 销地产地B1B2B3产量 A1646200A2655300A3（虚产地）（虚产地）000150销量250200200第41页/共43页海量海量PPT模板免费下载模板免费下载第42页/共43页感谢您的观看！第43页/共43页