第3章运输问题2

1、运运 筹筹 学学( Operations Research )运输问题的一般形式：产销平衡运输问题的一般形式：产销平衡A1、 A2、 Am 表示某物资的表示某物资的m个产地；个产地； B1、B2、Bn 表示表示某物质的某物质的n个销地；个销地；ai 表示产地表示产地Ai的产量；的产量； bj 表示销地表示销地Bj 的销量；的销量； cij 表示把物资从产地表示把物资从产地Ai运往销地运往销地Bj的单位运价。设的单位运价。设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，得到下列一般运输量问题的模型：的运输量，得到下列一般运输量问题的模型： minjijijxcz11min11,1,

2、.,1,0,1,;1,nijijmijjiijxaims txbjnxim jn L LL LL LL L 表上作业法是一种求解运输问题的特殊方法，其表上作业法是一种求解运输问题的特殊方法，其实质是单纯实质是单纯形法。形法。计算步骤如下：计算步骤如下：(1) 找出初始调运方案。即在找出初始调运方案。即在(mn)产销平衡表上给出产销平衡表上给出m+n-1个数字格。个数字格。(最小元素法、西北角法或伏格尔法）最小元素法、西北角法或伏格尔法）(2) 求检验数。（闭回路法或位势法）求检验数。（闭回路法或位势法） 判别是否达到最优判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。解。如已是最

3、优解，则停止计算，否则转到下一步。(3) 对方案进行改善，找出新的调运方案。（表上闭回对方案进行改善，找出新的调运方案。（表上闭回路法调整）路法调整）确定确定m+n-1个基变量个基变量 (4) 重复（重复（2）、（）、（3），直到求得最优调运方案。），直到求得最优调运方案。空格空格最小最小元素法元素法练习练习 销地销地产地产地B1B2B3B4产量产量A1675314A2842727A35910619销量销量221312131213131912西北角法练习西北角法练习 销地销地产地产地B1B2B3B4产量产量A1675314A2842727A35910619销量销量221312138131314

4、66 销地销地产地产地B1B2B3B4产量产量行差额行差额A1412411160A221039101A385116221销量销量814121448列差额列差额251314所以，初始基可行解为：目标函数值Z244伏格尔法：伏格尔法： 销地销地产地产地B1B2B3B4产量产量行差额行差额A1412411160A221039101A385116222销量销量814121448列差额列差额21314所以，初始基可行解为：目标函数值Z2448伏格尔法：伏格尔法： 销地销地产地产地B1B2B3B4产量产量行差额行差额A1412411160A221039101A38511622销量销量814121448列差

5、额列差额21214所以，初始基可行解为：目标函数值Z24488伏格尔法：伏格尔法： 销地销地产地产地B1B2B3B4产量产量行差额行差额A1412411167A221039106A38511622销量销量814121448列差额列差额1214所以，初始基可行解为：目标函数值Z2448812伏格尔法：伏格尔法： 销地销地产地产地B1B2B3B4产量产量行差额行差额A1412411160A221039100A38511622销量销量814121448列差额列差额314所以，初始基可行解为：目标函数值Z244881224伏格尔法：伏格尔法：练习练习 销地销地产地产地B1B2B3B4产量产量A1675

6、314A2842727A35910619销量销量2213121312131213192、 最优解的判别（检验数的求法）最优解的判别（检验数的求法）求检验数的方法有两种：求检验数的方法有两种： 闭回路法闭回路法 对偶变量法（位势法）对偶变量法（位势法） （1）闭合回路法：闭合回路法： 最优性检验：最优性检验： ij0 （因为目标函数要求最小化）（因为目标函数要求最小化） 表格中有调运量的地方为基变量，空格处为非基变量。表格中有调运量的地方为基变量，空格处为非基变量。基变量的检验数基变量的检验数ij0，非基变量的检验数，非基变量的检验数ij0。 ij 0 表示运费增加。表示运费增加。 闭回路：从空

7、格出发顺时针闭回路：从空格出发顺时针( (或逆时针或逆时针) )画水平画水平( (或垂直或垂直) )直线，遇到填有运量的方格可转直线，遇到填有运量的方格可转9090，然后继续前进，直到，然后继续前进，直到到达出发的空格所形成的闭合回路。到达出发的空格所形成的闭合回路。调运方案的任意空格存在唯一闭回路。调运方案的任意空格存在唯一闭回路。注：注：1.1.每一空格有且仅有一条闭回路；每一空格有且仅有一条闭回路； 2.2.如果某数字格有闭回路，则此解不是可行解。如果某数字格有闭回路，则此解不是可行解。mnmnzzxxxx0111112122121 L Lm nxxxzz11121101,0 L L若令

8、若令则则运费运费的单位增量的单位增量分析：分析：以最小元素法的初始解为例。假设产地以最小元素法的初始解为例。假设产地A1供应供应1个单位的个单位的物品给销地物品给销地B1。则解的变化和目标函数的变化如何。则解的变化和目标函数的变化如何。 销地销地产地产地 B1B2B3B4产量产量A141241116106A2210391082A38511622148销量销量814121448要保证产销平衡，则要保证产销平衡，则01144321,1zzz 111121231311xxxx 称为闭回路 1113232111xxxxx 销地销地产地产地 B1B2B3B4产量产量A141241116106A22103

9、91082A38511622148销量销量8141214481 销地销地产地产地 B1B2B3B4产量产量A141241116106A2210391082A38511622148销量销量81412144812561112122 销地销地产地产地 B1B2B3B4产量产量A141241116106A2210391082A38511622148销量销量81412144811561143102221 销地销地产地产地 B1B2B3B4产量产量A141241116106A2210391082A38511622148销量销量8141214481031823411610 211 销地销地产地产地 B1B2

10、B3B4产量产量A141241116106A2210391082A38511622148销量销量81412144813311411612 211210 销地销地产地产地 B1B2B3B4产量产量A141241116106A2210391082A38511622148销量销量814121448124934111 21-11210检验数中有检验数中有负数负数，说明原方案不是最优解。，说明原方案不是最优解。练习练习 销地销地产地产地B1B2B3B4产量产量A167531414A28427278136A35910619613销量销量221312135579-3-11 uivjm个个 n个个（2 2）对

11、偶变量法（位势法）对偶变量法（位势法）设其对偶变量为：设其对偶变量为：mnYu uuv vv1212(,.,.,) 运输问题约束条件的系数矩阵运输问题约束条件的系数矩阵111111111111111111 L LL LO OL LO OO OO OO Onnmmmnxxxxxxxxx111212122212L LL LL LL Lmn uivj无约束无约束 （i=1,2, ,m; j=1,2, ,n)标准型运输问题的对偶问题模型为：标准型运输问题的对偶问题模型为：1maxnijjjmiiivbuaw=+=ijjicvu则运输问题变量则运输问题变量xij的检验数为：的检验数为：ijijijiji

12、jijmnijijijczcYPcuuuvvvPcuv1212(, ., .,)() 用位势法对初始方案进行最优性检验的方法：用位势法对初始方案进行最优性检验的方法：1）在给定初始解的表上增加一行和一列，在列中填入）在给定初始解的表上增加一行和一列，在列中填入ui，在，在行中填入行中填入vj；2）令）令u10，再，再按按 cij(ui+vj) = 0（基变量（基变量的检验数等于零）的检验数等于零） 求求出其余的出其余的ui与与vj；3）由）由 ij = cij （ui+vj），），求出非基变量的检验数。求出非基变量的检验数。B1B2B3B4uiA1A2A3vj311310192741058注意

13、：基变量的检验数注意：基变量的检验数 ij = cij -（ui+vj）=0436313B1B2B3B4uiA1A2A3vj311310192741058令令u1=0u1+v3=3u1+ v4 =10u2+ v3=2u2+v1=1u3+v2=4u3+ v4=543631321039vj-5A3-1A20A1uiB4B3B2B1436313当存在非基变量的检验数当存在非基变量的检验数 ij 0，说明现行方案，说明现行方案为最优方案，否则目标成本还可以进一步减小。为最优方案，否则目标成本还可以进一步减小。注意：非基变量的检验数注意：非基变量的检验数 i j=ci j -（ui+vj） 11=c11

14、 -（u1+v1）=3-(0+2)=1 31=c31 -（u3+v1）=7-(2-5)=10 24=c24 -（u2+v4）=8-(10-1)=-1 22=c22 -（u2+v2）=9-(9-1)=1 12=c12 -（u1+v2）=11-(0+9)=2 33=c33 -（u3+v3）=10-(3-5)=123113101927410583、 解的改进解的改进 闭合回路调整法（原理同单纯形法一样）闭合回路调整法（原理同单纯形法一样） 当在表中空格处出现当在表中空格处出现负检验数负检验数时，表明未得最优解。时，表明未得最优解。若有两个或两个以上的负检验数时，一般选用其中最小的若有两个或两个以上的

15、负检验数时，一般选用其中最小的负检验数，以它对应的空格为调入格，即以它对应的非基负检验数，以它对应的空格为调入格，即以它对应的非基变量为换入变量。做一闭合回路。变量为换入变量。做一闭合回路。( 1 ) 确定换入基的变量：确定换入基的变量：当存在非基变量的检验数当存在非基变量的检验数 kl 0 且且 kl =min ij时，时，以以xkl为换入变量，找出它在运输表中的为换入变量，找出它在运输表中的闭合回路。闭合回路。接上例：接上例：24ijj , i)(min 0 x24为换入变量为换入变量解的改进的具体步骤：解的改进的具体步骤：21039vj-5A3-1A20A1uiB4B3B2B143631

16、3311310192741058( 2 ) 顶点编号：以空格顶点编号：以空格(Ak,Bl)(或进基变量或进基变量xik）为第一个）为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的顶点路上的顶点依次标号依次标号。+21039vj-5A3-1A20A1uiB4B3B2B1436313311310192741058( 2 ) 顶点编号：以空格顶点编号：以空格(Ak,Bl)(或进基变量或进基变量xik）为第一个）为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的顶点路上的顶

17、点依次标号依次标号。+换出变量换出变量X23 13 , 1minmin14,23 xx( 3 ) 确定换出基的变量：在该闭回路上，从确定换出基的变量：在该闭回路上，从所有标负号所有标负号格格点的调运量中选出最小值点的调运量中选出最小值 的顶点（格子），的顶点（格子），以该格子中的变量为换出变量。以该格子中的变量为换出变量。ijxmin ( 4 ) 确定新的运输方案：确定新的运输方案：以换出变量的运输量为调整量以换出变量的运输量为调整量 ，将该闭回路上将该闭回路上所有标正号所有标正号格的调运量加上调整量格的调运量加上调整量 ，所有标所有标负号负号格的调运量减去格的调运量减去 ，其余的不变，这样就

18、得到一个新的，其余的不变，这样就得到一个新的调运方案调运方案。该运输方案的总运费比原运输方案减少，改变量。该运输方案的总运费比原运输方案减少，改变量等于换出变量的检验数。等于换出变量的检验数。( 5 )然后，再对得到的新解进行最优性检验，加不是最优解，然后，再对得到的新解进行最优性检验，加不是最优解，就重复以上步骤继续进行调整，一直到得出最优解为止。就重复以上步骤继续进行调整，一直到得出最优解为止。21039vj-5A3-1A20A1uiB4B3B2B136313113101927410584331039vj-5A3-2A20A1uiB4B3B2B1536312311310192741058重

19、新求所有非基变量的检验数：重新求所有非基变量的检验数：31039vj-5A3-2A20A1uiB4B3B2B1536312当所有非基变量的检验数均非负时，则当前调运方案即为最当所有非基变量的检验数均非负时，则当前调运方案即为最优方案，如表此时最小总运费：优方案，如表此时最小总运费：Z =(13)(46)(35)(210)(18)(35)85元元31131019274105831039vj-5A3-2A20A1uiB4B3B2B1536312由于非基变量由于非基变量x11的检验的检验数数均零，故最优解不唯一。利用闭均零，故最优解不唯一。利用闭回路调整调运方案。回路调整调运方案。311310192

20、7410583656vj9A34A27A1aB4B3B2B1536312由于非基变量由于非基变量x11的检验的检验数数均零，故最优解不唯一。利用闭均零，故最优解不唯一。利用闭回路调整调运方案。回路调整调运方案。3113101927410583656b9A34A27A1aB4B3B2B151632调整后的调整后的调运方案依然是最优方案，运费为：调运方案依然是最优方案，运费为：Z =(23)(11)(64)(53)(38)(35)85元元3113101927410583表上作业法的计算步骤：表上作业法的计算步骤：分析实际问题列出产销平分析实际问题列出产销平衡表及单位运价表衡表及单位运价表确定初始调

21、运方案（最小确定初始调运方案（最小元素法或元素法或Vogel法）法）求检验数（位势法）求检验数（位势法）所有检验数所有检验数0找出绝对值最大的负检验数，用闭合找出绝对值最大的负检验数，用闭合回路调整，得到新的调运方案回路调整，得到新的调运方案得到最优方案，得到最优方案，算出总运价算出总运价否则否则（1）若运输问题的某一基可行解有多个非基变量的检验数）若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取目标函数值得到改善，但通常取ij0中最小者对应的变量为中最小者对应的变量为换入变量。换入变量。（2）无穷多）无穷多最优解最优解产销产销平衡的运输问题必定存最优解。平衡的运输问题必定存最优解。如果存在某一非如果存在某一非基变量基变量的的ij0，则该问题有无穷多最优解。，则该问题有无穷多最优解。如上例：如上例： 11的检验数是的检验数是 0，经过调整，可得到另一个最优，经过调整，可得到另一个最优解。解。 销