运输问题表上作业法.ppt
关于运输问题表上作业法现在学习的是第1页，共35页 确定初始确定初始方案方案(初初 始始 基本可行解基本可行解)改进调整改进调整（换基迭代）（换基迭代）否否 判定是否判定是否 最最 优？优？是是结结 束束最优方案最优方案图图 1运输问题求解思路图运输问题求解思路图现在学习的是第2页，共35页二、初始基本可行解的确定二、初始基本可行解的确定 现在学习的是第3页，共35页例题有关信息表例题有关信息表 450 200 150 100 日销量（需求量）250 75 65 80 乙 200 100 70 90 甲 日产量日产量（供应量）（供应量）C B A运距运距 城市城市煤矿煤矿现在学习的是第4页，共35页;3,2,1;2,1,0200150100250200.7565801007090min231322122111232221131211232221131211jixxxxxxxxxxxxxt sxxxxxxZij需求约束日产量约束总运输量现在学习的是第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页38750100*100150*65100*100100*90总运价为：现在学习的是第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页 39250100*20065*50100*70100*90总运价为：现在学习的是第11页，共35页三、最优性检验最优性检验根据最小元素法或西北角法求得运输问题的初始基可行解之后，按照表上作业法的第二步，下面需对这个解进行最优性判别，看它是否为本运输问题的最优解.现在学习的是第12页，共35页、闭回路法、闭回路法思路：要判定运输问题的初始基可行解是否为最优解，思路：要判定运输问题的初始基可行解是否为最优解，可仿照一般单纯形法，检验这个解的各非基变量（对应可仿照一般单纯形法，检验这个解的各非基变量（对应于运输表中的空格）的检验数。于运输表中的空格）的检验数。检验数检验数：运输问题中非基变量（对应于空格）的检验运输问题中非基变量（对应于空格）的检验数定义为给某空格增加单位运量导致总费用的增加量。数定义为给某空格增加单位运量导致总费用的增加量。如果有某空格（如果有某空格（i、Bj）的检验数为负，说明将）的检验数为负，说明将Xij变为基变量将使运输费用减少，故当前这个解不是变为基变量将使运输费用减少，故当前这个解不是最优解。若所有空格的检验数全为非负，则不管怎样变最优解。若所有空格的检验数全为非负，则不管怎样变换，均不能使运输费用降低，即目标函数值已无法改进，换，均不能使运输费用降低，即目标函数值已无法改进，这个解就是最优解。这个解就是最优解。现在学习的是第13页，共35页闭回路：在给出的调运方案的运输表上，闭回路：在给出的调运方案的运输表上，从一个空格（非基变量）出发，沿水平或从一个空格（非基变量）出发，沿水平或垂直方向前进，只有碰到代表基变量的数垂直方向前进，只有碰到代表基变量的数字格才能向左或向右转字格才能向左或向右转90继续前进，直继续前进，直至最终回到初始空格而形成的一条回路。至最终回到初始空格而形成的一条回路。从每一空格出发，一定可以找到一条且只从每一空格出发，一定可以找到一条且只存在唯一一条闭回路存在唯一一条闭回路。现在学习的是第14页，共35页以以xij空格为第一个奇数顶点，沿闭回路的顺（或空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的每个折点依次逆）时针方向前进，对闭回路上的每个折点依次编号；编号；非基变量非基变量 xij 的检验数：的检验数：现在，在现在，在用最小元素法确定例用最小元素法确定例2初始调运方案的初始调运方案的基础上，基础上，计算非基变量计算非基变量X12的检验数的检验数：ij现在学习的是第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现在学习的是第16页，共35页1221现在学习的是第17页，共35页2 2、对偶变量法（位势法）、对偶变量法（位势法）检验数公式：分别表示前m个约束等式对应的对偶变量；分别表示后n个约束等式对应的对偶变量。jiijijvuc),2,1(miui),2,1(njvj现在学习的是第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页iujv7565100902332222213311111cvucvucvucvu现在学习的是第20页，共35页现在学习的是第21页，共35页 这个时候方程的这个时候方程的解可以称为位势。解可以称为位势。现在学习的是第22页，共35页现在学习的是第23页，共35页ij现在学习的是第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+-020050100现在学习的是第28页，共35页 现在学习的是第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页现在学习的是第32页，共35页课堂练习：销产B1B2B3B4产量A241241116A22103910A38511622销量814121448现在学习的是第33页，共35页五、几点说明（1）、若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代中。通常取 中最小者对应的变量为换入变量；（2）、当迭代到运输问题的最优解时，如果有某非基变量的检验数等于0，则说明该运输问题有多重最优解；0ij现在学习的是第34页，共35页感谢大家观看感谢大家观看现在学习的是第35页，共35页
