运筹学-第4章运输问题VIP免费

TransportationProblem安徽财经大学统计与应用数学学院pagepage22December25,2024December25,2024§4.1运输问题的数学模型§4.2求解运输问题的表上作业法§4.3表上作业法的特殊情况§4.4运输问题的应用安徽财经大学统计与应用数学学院pagepage33December25,2024December25,2024某种物资有m个产地A1,A2,…,Am，联合供应n个销地B1,B2,…,Bn，各产地产量、各销地销量（单位：吨）、各产地到各销地的单位运价（单位：元/吨）如表1-1，应如何组织调运，才能使得总运费最省？表4-1一般运输问题的平衡表与运价表平衡表运价表销地产地B1B2…Bn产量（吨）B1B2…BnA1a1c11c12…c1nA2a2c21c22…c2n………………Amamcm1cm2…cmn销量(吨)b1b2…bn§4.1运输问题的数学模型安徽财经大学统计与应用数学学院pagepage44December25,2024December25,2024用矩阵形式表示为：设xij表示产地Ai供应销地Bj的数量(i=1,2,…,m;j=1,2,…,n)。njjmiiba11当产销平衡()时，数学模型为(标准形)：0.minXbAXtsCXZnjmixnjbxmiaxtsxcZijmijijnjiijminjijij,,2,1;,,2,10,,2,1,,2,1.min1111§4.1运输问题的数学模型安徽财经大学统计与应用数学学院pagepage55December25,2024December25,2024其中：mnnmA)(100100100010010010001001001111000000000111000000000111TmnmmnnxxxxxxxxxX),,,,,,,,,,,,(212222111211Tnmbbbaaab),,,,,,,(2121),,,,,,,,,,,,(212222111211mnmmnncccccccccC§4.1运输问题的数学模型安徽财经大学统计与应用数学学院pagepage66December25,2024December25,2024总有可行解总有可行解XXijij=a=aii*b*bjj/Q/Q矩阵的元素均为矩阵的元素均为11或或00；；每一列只有两个元素为每一列只有两个元素为11，其余元素均为，其余元素均为00；；列向量列向量PPijij=(0,…=(0,…，，00，，11，，，，……,0,1,0,…0)T,0,1,0,…0)T，，其中两个元素其中两个元素11分别处于第分别处于第ii行和第行和第m+jm+j行，行，eeii+e+em+jm+j。。将该矩阵分块，特点是：将该矩阵分块，特点是：前前mm行构成行构成mm个个m×nm×n阶矩阵阶矩阵，而且，而且第第kk个矩阵只有第个矩阵只有第kk行元素全为行元素全为11，其，其余元素全为余元素全为00（（k=1k=1，，……，，mm））；；后后nn行构成行构成mm个个nn阶单位阵阶单位阵。。§4.1运输问题的数学模型安徽财经大学统计与应用数学学院pagepage77December25,2024December25,2024111111111111111111可以看出新组合成的子矩阵为对角矩阵，秩为m+n-1，即原矩阵的秩为m+n-1§4.1运输问题的数学模型安徽财经大学统计与应用数学学院pagepage88December25,2024December25,2024容易证明，秩A=m+n-1。事实上，由于A的前m行之和等于后n行之和，因此，秩A≤m+n-1;又，取A的前m+n-1行，变量对应的列所构成的A的子式为由此易知，这个m+n-1阶子式的值为1或-1，所以，A的秩恰为m+n-1。可见运输问题的基可行解中，基变量的个数应为m+n-1个。mnnnnxxxxx,,,,,,32111安徽财经大学统计与应用数学学院pagepage99December25,2024December25,2024因此，运输问题的任何一个基含有个线性无关的列向量，即任何一个基可行解含有个基变量，这时对应的基可行解就是一个可行的调运方案。关于运输问题的求解，当然可以用单纯形方法，但由于它结构的特殊性，用特殊的方法求解比较方便。下面介绍求解运输问题的表上作业法。1nm1nm§4.1运输问题的数学模型安徽财经大学统计与应用数学学院pagepage1010December25,2024December25,2024表上作业法是一类比较特殊的单纯形法。它必须首先确定一个初始方案，也就是找出一个基可行解，然后根据判别准则来检查这个初始方案是不是最优的，如果不是最优的，那么对初始方案...