运输问题表上作业法

1、7.4 表上作业法一、一、表上作业法迭代步骤表上作业法迭代步骤 1按某种规则找出一个初始基可行解；按某种规则找出一个初始基可行解；2对现行解作最优性判断，即求各非基变量对现行解作最优性判断，即求各非基变量的检验数，判别是否达到最优解，如已是最优的检验数，判别是否达到最优解，如已是最优解，则停止计算，如不是最优解，则进行下一解，则停止计算，如不是最优解，则进行下一步骤；步骤；3在表上对初始方案进行改进，找出新的基在表上对初始方案进行改进，找出新的基可行解，再按第二步进行判别，直至找出最优可行解，再按第二步进行判别，直至找出最优解。解。 确定初始确定初始方案方案( ( 初初 始始 基本可行解基本可

2、行解) ) 改进调整改进调整（换基迭代）（换基迭代）否否 判定是否判定是否 最最 优？优？是是结结 束束最优方案最优方案图图 1运输问题求解思路图运输问题求解思路图二、初始基本可行解的确定二、初始基本可行解的确定 例题有关信息表例题有关信息表 450 200 150 100 日销量（需求量） 250 75 65 80 乙 200 100 70 90 甲 日产量日产量（供应量）（供应量） C B A运距运距 城市城市煤矿煤矿; 3 , 2 , 1; 2 , 1, 0200150100250200. .7565801007090min23132212211123222113121123222113

3、1211jixxxxxxxxxxxxxt sxxxxxxZij需求约束日产量约束总运输量 （1）最小元素法：从运价最小的格开始，在格）最小元素法：从运价最小的格开始，在格内的标上允许取得的最大数。然后按运价从小内的标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。进行下去，直至得到一个基本可行解。调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200

4、 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450 用最小元素法确定初始调运方案用最小元素法确定初始调运方案 15010010010010010010038750100*100150*65100*100100*90总运价为：（2 2）西北角法）西北角法不是优先考虑具有最小单位运价的供销业不是优先考虑具有最小单位运价的供销业务，而是优先满足运输表中西北角（左务，而是优先满足运输表中西北角（左上角）上空格的供销要求上角）上空格的供销要求调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13

5、 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450 用西北角法确定初始调运方案用西北角法确定初始调运方案 100100100 50 50200200 39250100*20065*50100*70100*90总运价为：三、最优性检验最优性检验根据最小元素法或西北角法求得运输问题的初始基可行解之后，按照表上作业法的第二步，下面需对这个解进行最优性判别，看它是否为本运输问题的最优解.、闭回路法、闭回路法思路：要判定运输问题的初始基可行解是否为思路：要判定运输问题的初始基可行解是否为最优解，可仿照一般单纯形法，检验这个解的最优解，可仿照一般单

6、纯形法，检验这个解的各非基变量（对应于运输表中的空格）的检验各非基变量（对应于运输表中的空格）的检验数。数。检验数检验数：运输问题中非基变量（对应于空格）运输问题中非基变量（对应于空格）的检验数定义为给某空格增加单位运量导致总的检验数定义为给某空格增加单位运量导致总费用的增加量。费用的增加量。如果有某空格（如果有某空格（i、Bj）的检验数为负，说明）的检验数为负，说明将将Xij变为基变量将使运输费用减少，故当前这变为基变量将使运输费用减少，故当前这个解不是最优解。若所有空格的检验数全为非个解不是最优解。若所有空格的检验数全为非负，则不管怎样变换，均不能使运输费用降低，负，则不管怎样变换，均不能

7、使运输费用降低，即目标函数值已无法改进，这个解就是最优解。即目标函数值已无法改进，这个解就是最优解。闭回路：在给出的调运方案的运输表上，闭回路：在给出的调运方案的运输表上，从一个空格（非基变量）出发，沿水平或从一个空格（非基变量）出发，沿水平或垂直方向前进，只有碰到代表基变量的数垂直方向前进，只有碰到代表基变量的数字格才能向左或向右转字格才能向左或向右转90继续前进，直继续前进，直至最终回到初始空格而形成的一条回路。至最终回到初始空格而形成的一条回路。从每一空格出发，一定可以找到一条且只从每一空格出发，一定可以找到一条且只存在唯一一条闭回路存在唯一一条闭回路 。以以xij空格为第一个奇数顶点，

8、沿闭回路的顺空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的每个（或逆）时针方向前进，对闭回路上的每个折点依次编号；折点依次编号；非基变量非基变量 xij 的检验数：的检验数：现在，在现在，在用最小元素法确定例用最小元素法确定例2初始调运方初始调运方案的基础上，案的基础上，计算非基变量计算非基变量X12的检验数的检验数 ：ij调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450100100100150122

9、12 2、对偶变量法（位势法）、对偶变量法（位势法）检验数公式： 分别表示前m个约束等式对应的对偶变量； 分别表示后n个约束等式对应的对偶变量。jiijijvuc), 2 , 1(miui), 2 , 1(njvj初始调运方案对偶变量对应表初始调运方案对偶变量对应表 调调 销地销地 运运 量量产地产地 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 u2iujv7565

10、100902332222213311111cvucvucvucvu 这个时这个时候方程的解可以称为位势。候方程的解可以称为位势。ij四、解的改进四、解的改进如检验出初始解不是最优解，即某非基如检验出初始解不是最优解，即某非基变量检验数为负，说明将这个非基变量变量检验数为负，说明将这个非基变量变为基变量时运费会下降。根据表上作变为基变量时运费会下降。根据表上作业法的第三步，需对初始方案进行改进。业法的第三步，需对初始方案进行改进。（一）解改进的步骤为：（一）解改进的步骤为：1（如存在多个非基变量的检验数为负（如存在多个非基变量的检验数为负时，以最小负检验数所在空格对应的变时，以最小负检验数所在空

11、格对应的变量）为换入变量，找出它在运输表中的量）为换入变量，找出它在运输表中的闭回路；闭回路；2以这个空格为第一个奇数顶点，沿闭以这个空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路的顺（或逆）时针方向前进，对闭回路上的每个折点依次编号；回路上的每个折点依次编号；解的改进步骤续：3在闭回路的所有偶数折点中，找出运输量在闭回路的所有偶数折点中，找出运输量最小的一个折点，以该格中的变量为换出变量；最小的一个折点，以该格中的变量为换出变量；4将闭回路上所有奇数折点的运输量都增加将闭回路上所有奇数折点的运输量都增加这一换出变量值，所有偶数折点处的运输量都这一换出变量值，所有偶数折点处的

12、运输量都减去这一数值，最终得出一个新的运输方案。减去这一数值，最终得出一个新的运输方案。对得出的新方案再进行最优性检验，如不是最对得出的新方案再进行最优性检验，如不是最优解，就重复以上步骤继续进行调整，一直到优解，就重复以上步骤继续进行调整，一直到得出最优解为止。得出最优解为止。调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450100100100150+-020050100 调调 销地销地 运运 量量产地产地 B1 B2 B

13、3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 45034250100100200 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课堂练习： 销产B1B2B3B4产量A241241116A22103910A38511622销量814121448五、几点说明（1）、若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代中。通常取 中最小者对应的变量为换入变量；（2）、当迭代到运