运输问题表上作业法课件.ppt

关于运输问题表上作业法现在学习的是第1页，共35页 确定初始确定初始方案方案(初初 始始 基本可行解基本可行解)改进调整改进调整（换基迭代）（换基迭代）否否 判定是否判定是否 最最 优？优？是是结结 束束最优方案最优方案图图 1运输问题求解思路图运输问题求解思路图现在学习的是第2页，共35页二、初始基本可行解的确定二、初始基本可行解的确定 例例2：甲甲、乙乙两两个个煤煤矿矿供供应应A、B、C三三个个城城市市用用煤煤，各各煤煤矿矿产产量量及及各各城城市市需需煤煤量量、各各煤煤矿矿到到各各城城市市的的运运输输单单价价见见表表所所示，求使总运输费用最少的调运方案。示，求使总运输费用最少的调运方案。现在学习的是第3页，共35页例题有关信息表例题有关信息表 450 200 150 100 日销量（需求量）250 75 65 80 乙 200 100 70 90 甲 日产量日产量（供应量）（供应量）C B A运距运距 城市城市煤矿煤矿现在学习的是第4页，共35页例题例题 数学模型数学模型现在学习的是第5页，共35页（1）最小元素法：从运价最小的格开始，在格内的标）最小元素法：从运价最小的格开始，在格内的标上允许取得的最大数。然后按运价从小到大顺序填上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。一个基本可行解。现在学习的是第6页，共35页调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450 用最小元素法确定初始调运方案用最小元素法确定初始调运方案 150100100100100100100现在学习的是第7页，共35页 得到初始调运方案为：得到初始调运方案为：x11=100，x13=100，x22=150，x23=100 现在学习的是第8页，共35页（2 2）西北角法）西北角法不是优先考虑具有最小单位运价的供销业不是优先考虑具有最小单位运价的供销业务，而是优先满足运输表中西北角（左务，而是优先满足运输表中西北角（左上角）上空格的供销要求上角）上空格的供销要求现在学习的是第9页，共35页调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450 用西北角法确定初始调运方案用西北角法确定初始调运方案 100100100 50 50200200现在学习的是第10页，共35页 得到初始调运方案为：得到初始调运方案为：x11=100，x12=100，x22=50，x23=200 现在学习的是第11页，共35页三、最优性检验最优性检验根据最小元素法或西北角法求得运输问题的初始基可行解之后，按照表上作业法的第二步，下面需对这个解进行最优性判别，看它是否为本运输问题的最优解.现在学习的是第12页，共35页、闭回路法、闭回路法思思路路：要要判判定定运运输输问问题题的的初初始始基基可可行行解解是是否否为为最最优优解解，可可仿仿照照一一般般单单纯纯形形法法，检检验验这这个个解解的的各各非非基变量（对应于运输表中的空格）的检验数。基变量（对应于运输表中的空格）的检验数。检检验验数数：运运输输问问题题中中非非基基变变量量（对对应应于于空空格格）的的检检验验数定义为给某空格增加单位运量导致总费用的增加量。数定义为给某空格增加单位运量导致总费用的增加量。如如果果有有某某空空格格（i、Bj）的的检检验验数数为为负负，说说明明将将Xij变变为为基基变变量量将将使使运运输输费费用用减减少少，故故当当前前这这个个解解不不是是最最优优解解。若若所所有有空空格格的的检检验验数数全全为为非非负负，则则不不管管怎怎样样变变换换，均均不不能能使使运运输输费费用用降降低低，即即目目标标函函数数值值已已无法改进，这个解就是最优解。无法改进，这个解就是最优解。现在学习的是第13页，共35页闭回路：在给出的调运方案的运输表上，闭回路：在给出的调运方案的运输表上，从一个空格（非基变量）出发，沿水平或从一个空格（非基变量）出发，沿水平或垂直方向前进，只有碰到代表基变量的数垂直方向前进，只有碰到代表基变量的数字格才能向左或向右转字格才能向左或向右转90继续前进，直继续前进，直至最终回到初始空格而形成的一条回路。至最终回到初始空格而形成的一条回路。从每一空格出发，一定可以找到一条且只从每一空格出发，一定可以找到一条且只存在唯一一条闭回路存在唯一一条闭回路。现在学习的是第14页，共35页以以xij空空格格为为第第一一个个奇奇数数顶顶点点，沿沿闭闭回回路路的的顺顺（或或逆逆）时时针针方方向向前前进进，对对闭闭回回路路上上的的每每个个折折点依次编号；点依次编号；非基变量非基变量 xij 的检验数：的检验数：现在，在现在，在用最小元素法确定例用最小元素法确定例2初始调运方案的初始调运方案的基础上，基础上，计算非基变量计算非基变量X12的检验数的检验数：=（闭回路上奇数次顶点运距或运价之和）（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和）（闭回路上偶数次顶点运距或运价之和）现在学习的是第15页，共35页调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450100100100150初始调运方案中以初始调运方案中以初始调运方案中以初始调运方案中以X12(X(X21)为起点的闭回路为起点的闭回路现在学习的是第16页，共35页非基变量非基变量X12的检验数：的检验数：非基变量非基变量X21的检验数：的检验数：=（c12+c23）-（c13+c22）=70+75-（100+65）=-20，=（c21+c13）-（c11+c23）=80+100-（90+75）=15。经经济济含含义义：在在保保持持产产销销平平衡衡的的条条件件下下，该该非非基基变变量量增增加加一一个个单单位位运运量量而而成成为为基基变变量量时时目目标标函函数值的变化量数值的变化量。现在学习的是第17页，共35页2 2、对偶变量法（位势法）、对偶变量法（位势法）检验数公式：分别表示前m个约束等式对应的对偶变量；分别表示后n个约束等式对应的对偶变量。现在学习的是第18页，共35页初始调运方案对偶变量对应表初始调运方案对偶变量对应表 调调 销地销地 运运 量量产地产地 B1 B2 B3产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450对偶变量对偶变量vj v1 v2 v3100100100150对偶对偶变量变量 ui u1 u2现在学习的是第19页，共35页 以初始调运方案为例，设置以初始调运方案为例，设置对偶对偶变量变量 和和 ，然后构造下面的方程组：然后构造下面的方程组：现在学习的是第20页，共35页 在在式式中中，令令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与前面用闭回路法求得的结果相同。与前面用闭回路法求得的结果相同。现在学习的是第21页，共35页方程组的特点：方程组的特点：方方程程个个数数是是m+n-1=2+3-1=4个个，对对偶偶变变量量共共有有m+n=2+3=5。初初始始方方案案的的每每一一个个基基变变量量xij对对应应一一个个方方程程-所所在在行行和和列列对对应应的的对对偶偶变变量量之之和和等等于于该该基基变变量量对对应的运距（或运价）应的运距（或运价）：ui+vj=cij；方程组恰有一个自由变量，方程组恰有一个自由变量，可以证明可以证明方程组中任方程组中任意一个变量均可取作自由变量。意一个变量均可取作自由变量。这个时候方程的解这个时候方程的解可以称为位势。可以称为位势。现在学习的是第22页，共35页 在在式式中中，令令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与前面用闭回路法求得的结果相同。与前面用闭回路法求得的结果相同。现在学习的是第23页，共35页位势法计算非基变量位势法计算非基变量xij检验数的公式检验数的公式 ij=cij-（ui+vj）=（闭回路上奇数次顶点运距或运价之和）（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和）（闭回路上偶数次顶点运距或运价之和）闭回路法计算非基变量闭回路法计算非基变量xij检验数的公式：检验数的公式：复习比较检验数计算的两种方法复习比较检验数计算的两种方法思考：试解释位势变量的含义（提示：写出运输问题的思考：试解释位势变量的含义（提示：写出运输问题的对偶问题）对偶问题）现在学习的是第24页，共35页四、解的改进四、解的改进如如检检验验出出初初始始解解不不是是最最优优解解，即即某某非非基基变变量量检检验验数数为为负负，说说明明将将这这个个非非基基变变量量变变为为基基变变量量时时运运费费会会下下降降。根根据据表表上上作作业法的第三步，需对初始方案进行改进。业法的第三步，需对初始方案进行改进。现在学习的是第25页，共35页（一）解改进的步骤为：（一）解改进的步骤为：1（如如存存在在多多个个非非基基变变量量的的检检验验数数为为负负时时，以以最最小小负负检检验验数数所所在在空空格格对对应应的的变变量量）为为换换入入变变量量，找找出出它它在在运运输输表表中中的的闭回路；闭回路；2以以这这个个空空格格为为第第一一个个奇奇数数顶顶点点，沿沿闭闭回回路路的的顺顺（或或逆逆）时时针针方方向向前前进进，对对闭闭回路上的每个折点依次编号；回路上的每个折点依次编号；现在学习的是第26页，共35页解的改进步骤续：3在在闭闭回回路路的的所所有有偶偶数数折折点点中中，找找出出运运输输量量最最小小的一个折点，以该格中的变量为换出变量；的一个折点，以该格中的变量为换出变量；4将将闭闭回回路路上上所所有有奇奇数数折折点点的的运运输输量量都都增增加加这这一一换换出出变变量量值值，所所有有偶偶数数折折点点处处的的运运输输量量都都减减去去这一数值，最终得出一个新的运输方案。这一数值，最终得出一个新的运输方案。对对得得出出的的新新方方案案再再进进行行最最优优性性检检验验，如如不不是是最最优优解解，就就重重复复以以上上步步骤骤继继续续进进行行调调整整，一一直直到到得得出出最最优优解解为止。为止。现在学习的是第27页，共35页调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450100100100150+-因因 1212=-20，画出以，画出以x x12为起始变量的闭回路为起始变量的闭回路 020050100现在学习的是第28页，共35页 计算调整量：计算调整量：=Min（100，150）=100。按照下面的方法调整调运量：按照下面的方法调整调运量：闭闭回回路路上上，奇奇数数次次顶顶点点的的调调运运量量加加上上，偶偶数数次次顶顶点点的的调调运运量量减减去去；闭闭回回路路之之外外的的变变量量调调运运量量不不变。变。得到新的得到新的调调运方案运方案：现在学习的是第29页，共35页调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 45034250100100200 50重复上面的步骤，直至求出最优调运方案：重复上面的步骤，直至求出最优调运方案：现在学习的是第30页，共35页调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450150 50200 50现在学习的是第31页，共35页 结结 果果 最优调运方案是：最优调运方案是：x11=50，x12=150，x21=50，x23=200 相应的最小总运输费用为：相应的最小总运输费用为：Zmin=9050+70150+8050+75200 =34000现在学习的是第32页，共35页课堂练习：销产B1B2B3B4产量A241241116A22103910A38511622销量814121448现在学习的是第33页，共35页五、几点说明（1）、若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代中。通常取 中最小者对应的变量为换入变量；（2）、当迭代到运输问题的最优解时，如果有某非基变量的检验数等于0，则说明该运输问题有多重最优解；现在学习的是第34页，共35页感感谢谢大大家家观观看看现在学习的是第35页，共35页