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