运筹学第4章运输问题

《运筹学第4章运输问题》由会员分享，可在线阅读，更多相关《运筹学第4章运输问题（69页珍藏版）》请在装配图网上搜索。

1、TransportationProblem安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 2 2 8/14/20238/14/20234.1运输问题的数学模型运输问题的数学模型4.2求解运输问题的表上作业法求解运输问题的表上作业法4.3表上作业法的特殊情况表上作业法的特殊情况4.4运输问题的应用运输问题的应用安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 3 3 8/14/20238/14/2023某种物资有某种物资有m个产地个产地A1,A2,Am，联合供应，联合供应n个销地个销地B1,B2,Bn，各产地产量、各销地销量（单位：吨

2、）、各产地，各产地产量、各销地销量（单位：吨）、各产地到各销地的单位运价（单位：元到各销地的单位运价（单位：元/吨）如表吨）如表1-1，应如何组织调，应如何组织调运，才能使得总运费最省？运，才能使得总运费最省？表表4-14-1一般运输问题的平衡表与运价表一般运输问题的平衡表与运价表 平衡表平衡表运价表运价表销地销地产地产地 B B1 1B B2 2B Bn n产量（吨）产量（吨）B B1 1B B2 2B Bn nA A1 1a a1 1c c1111c c1212c c1 1n nA A2 2a a2 2c c2121c c2222c c2 2n nA Am ma am mc cm m1 1

3、c cm m2 2c cmnmn销量销量(吨吨)b b1 1b b2 2b bn n4.1运输问题的数学模型运输问题的数学模型安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 4 4 8/14/20238/14/2023用矩阵形式用矩阵形式表示为：表示为：设设xij表示产地表示产地Ai供应销地供应销地Bj的数量的数量(i=1,2,m;j=1,2,n)。当产销平衡当产销平衡()时，数学模型为时，数学模型为(标准形标准形)：4.1运输问题的数学模型运输问题的数学模型安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 5 5 8/14/202

4、38/14/2023其中：其中：4.1运输问题的数学模型运输问题的数学模型安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 6 6 8/14/20238/14/2023v总有可行解总有可行解总有可行解总有可行解X Xij ij=a=ai i*b*bj j/Q/Qv矩阵的元素均为矩阵的元素均为矩阵的元素均为矩阵的元素均为1 1或或或或0 0；每一列只有两个元素为每一列只有两个元素为每一列只有两个元素为每一列只有两个元素为1 1，其余元素均为，其余元素均为，其余元素均为，其余元素均为0 0；列向量列向量列向量列向量P Pij ij=(0,=(0,，0 0，1 1，,0

5、,1,0,0)T,0,1,0,0)T，其中两，其中两，其中两，其中两个元素个元素个元素个元素1 1分别处于第分别处于第分别处于第分别处于第i i行和第行和第行和第行和第m+jm+j行，行，行，行，e ei i+e+em+jm+j。将该矩阵分块，特点是：将该矩阵分块，特点是：将该矩阵分块，特点是：将该矩阵分块，特点是：前前前前mm行构成行构成行构成行构成mm个个个个mnmn阶矩阶矩阶矩阶矩阵阵阵阵，而且，而且，而且，而且第第第第k k个矩阵只有第个矩阵只有第个矩阵只有第个矩阵只有第k k行元素全为行元素全为行元素全为行元素全为1 1，其余元素，其余元素，其余元素，其余元素全为全为全为全为0 0（

6、k=1k=1，mm）；后后后后n n行构成行构成行构成行构成mm个个个个n n阶单位阵阶单位阵阶单位阵阶单位阵。4.1运输问题的数学模型运输问题的数学模型安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 7 7 8/14/20238/14/2023可以看出新组合成的子矩阵为对角矩阵，秩为m+n-1，即原矩阵的秩为m+n-14.1运输问题的数学模型运输问题的数学模型安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 8 8 8/14/20238/14/2023 容易容易证明，秩明，秩A=m+n-1。事。事实上，由于上，由于A的前的前m行之

7、和等于后行之和等于后n行之和，因此，秩行之和，因此，秩Am+n-1;又，取又，取A的前的前m+n-1行，行，变量量 对应的的列所构成的列所构成的A的子式的子式为 由此易知，由此易知，这个个m+n-1阶子式的子式的值为1或或-1，所，所以，以，A的秩恰的秩恰为m+n-1。可。可见运运输问题的基可行解的基可行解中，基中，基变量的个数量的个数应为m+n-1个。个。安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 9 9 8/14/20238/14/2023因此，运输问题的任何一个基含有因此，运输问题的任何一个基含有个线性无个线性无关的列向量，即任何一个基可行解含有关的列

8、向量，即任何一个基可行解含有个基个基变量，这时对应的基可行解就是一个可行的调运方案。变量，这时对应的基可行解就是一个可行的调运方案。关于运输问题的求解，当然可以用关于运输问题的求解，当然可以用单纯形方法单纯形方法，但由，但由于它结构的特殊性，用特殊的方法求解比较方便。下于它结构的特殊性，用特殊的方法求解比较方便。下面介绍求解运输问题的面介绍求解运输问题的表上作业法表上作业法。4.1运输问题的数学模型运输问题的数学模型安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 1010 8/14/20238/14/2023表上作业法是一类比较特殊的单纯形法。它必须首先确定一个

9、初始方案初始方案，也就是找出一个基可行解，然后根据判别准则来检查这个初始方案是不是最优的，如果不是最优的，那么对初始方案加以改进，直到找出最优方案。4.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 1111 8/14/20238/14/2023确定初始确定初始方案方案(初初 始始 基本可行解基本可行解)改进调整改进调整（换基迭代）（换基迭代）否否判定是否判定是否最最优？优？是是结结束束最优方案最优方案运输问题求解思路图运输问题求解思路图4.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用

10、数学学院安徽财经大学统计与应用数学学院page page 1212 8/14/20238/14/2023例 甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输距离见表，求使总运输量最少的调运方案。安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 1313 8/14/20238/14/2023 450 200 150 100 日日销量量（需求量）（需求量）250 75 65 80 乙乙 200 100 70 90 甲甲 日产量（供应量）C B A运距 城市煤矿安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page

11、page 1414 8/14/20238/14/2023安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 1515 8/14/20238/14/2023分别使用最小元素法和西北角法求出分别使用最小元素法和西北角法求出初始初始方案。方案。&最小元素法的基本思想是“就近供应”；&西北角法则不考虑运距（或运价），每次都选剩余表格剩余表格的左上角（即西北角）元素作为基变量，其它过程与最小元素法相同；安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 1616 8/14/20238/14/2023调 销地 运 量产地 B1 B2 B3 产 量 A

12、1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450用最小元素法确定初始调运方案用最小元素法确定初始调运方案 150100100100100100100安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 1717 8/14/20238/14/2023得到初始调运方案为：得到初始调运方案为：x11=100，x13=100，x22=150，x23=100安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 1818 8/14/20238/14/20

13、23调 销地 运 量产地 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450用西北角法确定初始调运方案用西北角法确定初始调运方案 1001001005050200200安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 1919 8/14/20238/14/2023得到初始调运方案为：得到初始调运方案为：x11=100，x12=100，x22=50，x23=200安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page

14、 2020 8/14/20238/14/2023基本思路是：从全局考虑。其方法是从运价表上分别找出每行与每列每行与每列最小的两个元素之差，再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量上供应完毕或得到满足时，划去运价表中的行或列，再重复再重复上述步上述步骤骤。直到找出初始初始调运方案。安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 2121 8/14/20238/14/2023销地销地产地产地 B1 B2 B3 B4产产 量量A1A2A3749销销 量量 3 6 5 6Table4 单位运价表 销地销地产地产地B1 B2 B3

15、 B4 两最小元素之差两最小元素之差 A1A2A33 11 3 101 9 2 87 4 10 50 0 0 7 01 1 1 6 0 1 2两最小两最小元素元素之差之差2 5 1 32 1 32 1 2 1 2 2365213安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 2222 8/14/20238/14/2023例例某种物资有某种物资有3个产地、个产地、4个销地，各产地的产量、销地的销量个销地，各产地的产量、销地的销量以及各产销地之间的运价如表以及各产销地之间的运价如表2-1，求最优的调运方案。，求最优的调运方案。表表运输问题的平衡表与运价表运输问题的平

16、衡表与运价表平衡表(单位：t)运价表运价表B1B2B3B4发量B1B2B3B4A146534A264475A337658收量243413安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 2323 8/14/20238/14/2023表表 运输问题的初始调运方案运输问题的初始调运方案平衡表运价表运价表B1B2B3B4发量B1B2B3B4A13146534A22464475A30337658收量243413表中表中,有数字的格子有数字的格子(包括包括0)对应的是基变量对应的是基变量,空格所对空格所对应的变量是非基变量。应的变量是非基变量。4.2求解运输问题的表上作业法

17、求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 2424 8/14/20238/14/2023显然，任何一个产销平衡的运输问题都可以用最小元显然，任何一个产销平衡的运输问题都可以用最小元素法求出一个初始调运方案，又因为运输问题目标函素法求出一个初始调运方案，又因为运输问题目标函数必然有下界（且非负），所以平衡运输问题一定有数必然有下界（且非负），所以平衡运输问题一定有最优解。人们可能认为用最小元素法得到的初始方案最优解。人们可能认为用最小元素法得到的初始方案一定是最优的，其实不然。该方案对应的运费等于一定是最优的，其实不然。该方案对应的运

18、费等于Z=33+14+24+44+06+38=61,但该运输问但该运输问题的最小费用为题的最小费用为55。4.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 2525 8/14/20238/14/2023对于每一个非基变量（空格）都对应一个检验数，对于每一个非基变量（空格）都对应一个检验数，则有以下最优性准则：则有以下最优性准则：定理定理1.4.1(最优性判别准则最优性判别准则)在运输问题的某个可行方在运输问题的某个可行方案中，如果对应于每一个非基变量案中，如果对应于每一个非基变量xij(即空格即空格)的的检验检

19、验数数l lij 0，则该基可行解为最优解，对应的调运方案为，则该基可行解为最优解，对应的调运方案为最优方案。最优方案。为了说明如何在表上作业法的过程中求出非基变量为了说明如何在表上作业法的过程中求出非基变量的检验数，下面介绍闭回路的概念。的检验数，下面介绍闭回路的概念。2.2求检验数、最优性判别求检验数、最优性判别4.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 2626 8/14/20238/14/2023检验数检验数闭回路：闭回路：在调运方案中，从一个空格出发，沿水平或在调运方案中，从一个空格出发，沿水平

20、或垂直方向前进，遇到一个适当的有数字的格子，则转垂直方向前进，遇到一个适当的有数字的格子，则转向向90前进，这样必会又遇到一个适当的有数字的格子，前进，这样必会又遇到一个适当的有数字的格子，同样再转向同样再转向90前进；经若干次后，必然会回到出发的前进；经若干次后，必然会回到出发的那个空格，这样就形成一条由水平与垂直线构成的封那个空格，这样就形成一条由水平与垂直线构成的封闭折线，我们称这样的封闭折线为该空格的闭回路。闭折线，我们称这样的封闭折线为该空格的闭回路。该空格（非基变量）对应的检验数就等于该闭回路上该空格（非基变量）对应的检验数就等于该闭回路上所有偶次拐点的运价之和减去所有奇次拐点的运

21、价之所有偶次拐点的运价之和减去所有奇次拐点的运价之和。和。在例在例1中：中：闭回路闭回路:闭回路闭回路:检验数检验数4.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 2727 8/14/20238/14/2023闭回路闭回路:检验数检验数闭回路闭回路:检验数检验数闭回路闭回路:检验数检验数闭回路闭回路:检验数检验数初学者可能感到这样求检验数比较麻烦初学者可能感到这样求检验数比较麻烦,但它反映了检验但它反映了检验数的本质。我们也可以用位势法来求检验数。数的本质。我们也可以用位势法来求检验数。4.2求解运输问题的表

22、上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 2828 8/14/20238/14/2023位势法：位势法：将运价表中将运价表中基变量基变量所对应的运价打所对应的运价打“*”号号或者将数字画圈或者将数字画圈“”，然后对运价表每一行、每，然后对运价表每一行、每一列同时加上或减去同一个数，当基变量对应的检一列同时加上或减去同一个数，当基变量对应的检验数（打验数（打“*”号的或画圈号的或画圈“”的）的）等于零等于零，其余，其余各数就是各个非基变量所对应的检验数。各数就是各个非基变量所对应的检验数。对例对例1，采用位势法求检验数过程如下

23、，采用位势法求检验数过程如下最后的数阵中没有标记最后的数阵中没有标记*的数字就是的数字就是非基变量的检验数。非基变量的检验数。4.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 2929 8/14/20238/14/2023从一个可行方案调整到另一个可行方案从一个可行方案调整到另一个可行方案,也就是从一个也就是从一个基可行解换基迭代到另一个基可行解基可行解换基迭代到另一个基可行解,且使目标函数值且使目标函数值不断下降。运输问题表上作业法的换基迭代实际上是在不断下降。运输问题表上作业法的换基迭代实际上是在调运表上调

24、运表上负检验数对应的空格负检验数对应的空格所在的闭回路上进行的所在的闭回路上进行的.第一个检验数小于零第一个检验数小于零l l24=-1=-10的空格所对应的非基变的空格所对应的非基变量为进基变量，并使这个非基变量的值由零增加到调整量为进基变量，并使这个非基变量的值由零增加到调整量。量。2.3求出调整量、求出调整量、在闭回路上进行调整在闭回路上进行调整调整量调整量：该闭回路上所有奇次拐点调运量的：该闭回路上所有奇次拐点调运量的最小值。最小值。4.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 3030 8/14/

25、20238/14/2023调整方法：调整方法：闭回路上每个闭回路上每个奇次奇次拐点拐点的调运量的调运量都减去调都减去调整量整量(其中有一个且其中有一个且仅允许有一个仅允许有一个调运量为调运量为0变为变为空格空格成成为非基变量，其他变为为非基变量，其他变为0的仍然要填上的仍然要填上0)，各偶次拐点，各偶次拐点的调运量均加上调整量，其中有一个由非基变量的调运量均加上调整量，其中有一个由非基变量(空格空格)变为基变量。变为基变量。对例对例1，取，取表表2-3 2-3 运输问题调运方案调整表运输问题调运方案调整表B1B2B3B4发量B1B2B3B4A131431A224-3+36213A30+33-3

26、33收量2434134.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 3131 8/14/20238/14/2023使用位势法求检验数，过程如下：使用位势法求检验数，过程如下：有检验数有检验数l l33=-1=-10,继续调整继续调整,取取表表2-4 2-4 运输问题调运方案调整表运输问题调运方案调整表B1B2B3B4发量B1B2B3B4A13-3 1+3 44A221+3 3-36240A33-3+3 303收量2434134.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安

27、徽财经大学统计与应用数学学院page page 3232 8/14/20238/14/2023注意注意：这里经调整以后，有：这里经调整以后，有3个基变量个基变量x13,x24,x31同时同时变为零！但变为零！但只能有一个只能有一个x13成为非基变量成为非基变量(空格空格)，另外，另外两个两个x24,x31仍为基变量，其对应的调运量等于仍为基变量，其对应的调运量等于0。继续求检验数：继续求检验数：此时所有检验数全部非负，因此对应的调运方案是此时所有检验数全部非负，因此对应的调运方案是最优的。最优的。min Z=44+24+44+35=55。4.2求解运输问题的表上作业法求解运输问题的表上作业法安

28、徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 3333 8/14/20238/14/2023例例2求表求表2-5对应的运对应的运输问题的最输问题的最优解：优解：表表2-5运输问题的平衡表与运价表运输问题的平衡表与运价表B1B2B3B4发量B1B2B3B4A17311310A241928A3974105收量365620解：解：首先用最小元素法求初始调运方案首先用最小元素法求初始调运方案，见表，见表2-6。表表2-6运输问题的初始调运方案运输问题的初始调运方案B1B2B3B4发量B1B2B3B4A1437311310A23141928A363974105收量3656

29、20总费用总费用Z=43+310+31+12+64+35=864.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 3434 8/14/20238/14/2023采用位势法求检验数：采用位势法求检验数：有检验数有检验数为负为负,非最非最优方案优方案,需需要要进行方进行方案的调整案的调整,见表见表2-7。表表2-7运输问题的运输问题的调运方案调整表调运方案调整表B1B2B3B4发量B1B2B3B4A14+1 3-1752A231-1+1431A363963收量3 65620总费用总费用Z=53+210+31+18+6

30、4+35=854.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 3535 8/14/20238/14/2023采用位势法求检验数：采用位势法求检验数：所有检验数全部非负所有检验数全部非负,此方案是最优的调运方案。此方案是最优的调运方案。由于由于非基变量非基变量x11的检验数的检验数l l11=0,该运输问题可能该运输问题可能不止一个最优方案不止一个最优方案。进行调整见表。进行调整见表1-79，该表对应另，该表对应另一个最优方案。一个最优方案。最小费用最小费用Z=53+210+31+18+64+35=85。4.2

31、求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 3636 8/14/20238/14/2023表表2-8运输问题的调运方案运输问题的调运方案调整表调整表B1B2B3B4发量B1B2B3B4A1+25 2-2725A23-21+2413A363963收量365620最小费用最小费用Z=23+53+11+38+64+35=854.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 3737 8/14/20238/14/2023对例对例2用用L

32、INDO软件进行求解，程序如下：软件进行求解，程序如下：min3x11+11x12+3x13+10 x14+x21+9x22+2x23+8x24+7x31+4x32+10 x33+5x34stx11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+X34=6end4.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 3838 8/14/20238/14/2023LPOPTIMU

33、MFOUNDATSTEP6OBJECTIVEFUNCTIONVALUE1)85.00000VARIABLEVALUEREDUCEDCOSTx112.0000000.000000 x120.0000002.000000 x135.0000000.000000 x140.0000000.000000 x211.0000000.000000 x220.0000002.000000 x230.0000001.000000 x243.0000000.000000 x310.0000009.000000 x326.0000000.000000 x330.00000012.000000 x343.00000

34、00.000000结果如下：结果如下：4.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 3939 8/14/20238/14/2023ROWSLACKORSURPLUSDUALPRICES2)0.000000-9.0000003)0.000000-7.0000004)0.000000-4.0000005)0.0000006.0000006)0.0000000.0000007)0.0000006.0000008)0.000000-1.000000NO.ITERATIONS=64.2求解运输问题的表上作业法求解运输

35、问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 4040 8/14/20238/14/2023model:!3发点发点4收点运输问题收点运输问题;sets:warehouses/wh1.wh3/:capacity;vendors/v1.v4/:demand;links(warehouses,vendors):cost,volume;endsets!目标函数目标函数;min=sum(links:cost*volume);!需求约束需求约束;for(vendors(J):sum(warehouses(I):volume(I,J)=demand(J);

36、!产量约束产量约束;用用LINGO求解的基本程序如下求解的基本程序如下4.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 4141 8/14/20238/14/2023for(warehouses(I):sum(vendors(J):volume(I,J)=capacity(I);!这里是数据这里是数据;data:capacity=7,4,9;demand=3,6,5,6;cost=3,11,3,10,1,9,2,8,7,4,10,5;enddataend4.2求解运输问题的表上作业法求解运输问题的表上作业法安徽

37、财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 4242 8/14/20238/14/2023Objectivevalue:85.00000VariableValueReducedCostVOLUME(WH1,V1)2.0000000.000000VOLUME(WH1,V2)0.0000002.000000VOLUME(WH1,V3)5.0000000.000000VOLUME(WH1,V4)0.0000000.000000VOLUME(WH2,V1)1.0000000.000000VOLUME(WH2,V2)0.0000002.000000VOLUME(WH2,V

38、3)0.0000001.000000VOLUME(WH2,V4)3.0000000.000000VOLUME(WH3,V1)0.0000009.000000VOLUME(WH3,V2)6.0000000.000000VOLUME(WH3,V3)0.00000012.00000VOLUME(WH3,V4)3.0000000.000000运行结果运行结果(部分部分)如下如下4.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 4343 8/14/20238/14/2023使用表上作业法，有以下特殊情况需要注意使用表上作

39、业法，有以下特殊情况需要注意在用最小元素法作初始调运方案时，在用最小元素法作初始调运方案时，当出现供需相当出现供需相等时，这时可以等时，这时可以(也只能也只能)满足一家！另一家供满足一家！另一家供(需需)量量相应地改为相应地改为0 0；在下一次供应时，；在下一次供应时，0 0也要进行供应或需也要进行供应或需求求(如例如例1 1用最小元素法作初始调运方案用最小元素法作初始调运方案)。在方案的调整过程中，在方案的调整过程中，若奇次拐点的调运量有不止若奇次拐点的调运量有不止一个等于调整量，调整以后，有几个同时变为一个等于调整量，调整以后，有几个同时变为0 0，这，这时只允许一个变为空格成为非基变量，

40、其余的仍为基时只允许一个变为空格成为非基变量，其余的仍为基变量，对应的调运量等于变量，对应的调运量等于0 0，不能是空格。，不能是空格。（如例（如例1 1，方案的调整）方案的调整）在方案的调整过程中在方案的调整过程中，如果调整量等于如果调整量等于0，这时也，这时也要作形式上的调整，只是要作形式上的调整，只是0与空格的位置互换与空格的位置互换罢了。罢了。4.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 4444 8/14/20238/14/2023产销不平衡问题产销不平衡问题例例3 3 某建材公司有某建材公司有3

41、 3个分厂，均生产水泥预制板，其产销情个分厂，均生产水泥预制板，其产销情况及运价如表况及运价如表3-13-1所示，求运费最省的调运方案。所示，求运费最省的调运方案。若供大于求，即若供大于求，即，则可以增加一个虚，则可以增加一个虚的的销地销地(仓库仓库),其需要量为其需要量为并且各个产并且各个产地到仓库的运价等于地到仓库的运价等于0。表表3-1产销不平衡时运输问题的平衡表与运价表产销不平衡时运输问题的平衡表与运价表B1B2B3B4发量B1B2B3B4A1220311310A23001928A340074105收量2202402601104.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财

42、经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 4545 8/14/20238/14/2023解解由于总发量由于总发量920920吨，收量为吨，收量为830830吨，产销不平衡，发量比收量吨，产销不平衡，发量比收量多多9090吨。如果把这吨。如果把这9090吨看成是库存的需求量，因此可在运价吨看成是库存的需求量，因此可在运价表中虚加一列，运价表也相应地增加一列，但各发点到库存表中虚加一列，运价表也相应地增加一列，但各发点到库存的的运价全为零运价全为零，于是得到产销平衡的运输问题，于是得到产销平衡的运输问题(表表3-2)3-2)。表表3-2化为产销平衡运输问题的平衡表与

43、运价表化为产销平衡运输问题的平衡表与运价表B1B2B3B4库存 发量B1B2B3B4库存A12203113100A230019280A3400741050收量22024026011090920其最优解其最优解(最小运输费最小运输费)为：为：4.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 4646 8/14/20238/14/2023若用若用LINDO或或LINGO进行求解，就不必化成产销平衡的情况，进行求解，就不必化成产销平衡的情况，可直接求解。可直接求解。model:sets:warehouses/wh1.

44、wh3/:capacity;vendors/v1.v4/:demand;links(warehouses,vendors):cost,volume;endsetsmin=sum(links:cost*volume);for(vendors(J):sum(warehouses(I):volume(I,J)=demand(J);for(warehouses(I):sum(vendors(J):volume(I,J)=capacity(I);data:capacity=220,300,400;demand=220,240,260,110;cost=3,11,3,10,1,9,2,8,7,4,10,5

45、;enddataend4.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 4747 8/14/20238/14/2023Globaloptimalsolutionfoundatiteration:5Objectivevalue:2430.000VariableValueReducedCostVOLUME(WH1,V1)0.0000001.000000VOLUME(WH1,V2)0.0000007.000000VOLUME(WH1,V3)180.00000.000000VOLUME(WH1,V4)0.0000005

46、.000000VOLUME(WH2,V1)220.00000.000000VOLUME(WH2,V2)0.0000006.000000VOLUME(WH2,V3)80.000000.000000VOLUME(WH2,V4)0.0000004.000000VOLUME(WH3,V1)0.0000005.000000VOLUME(WH3,V2)240.00000.000000VOLUME(WH3,V3)0.0000007.000000VOLUME(WH3,V4)110.00000.000000部分输出结果如下部分输出结果如下(与输入信息重复的和无用信息不再列出与输入信息重复的和无用信息不再列出)：

47、4.2求解运输问题的表上作业法求解运输问题的表上作业法安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 4848 8/14/20238/14/2023若是求最大化运输问题时，只需要作若是求最大化运输问题时，只需要作相应地改动相应地改动：用用最大元素法最大元素法作初始调运方案；作初始调运方案；在最优性判别时，当所有检验数在最优性判别时，当所有检验数均非正均非正时为最优；时为最优；对对检验数大于零的空格检验数大于零的空格所对应的闭回路进行调整。所对应的闭回路进行调整。其他与最小化运输问题一样。其他与最小化运输问题一样。若供不应求，即若供不应求，即，则可以增加一个虚的，

48、则可以增加一个虚的产地产地,其产量为其产量为并且该产地到各个销地的并且该产地到各个销地的运价等于运价等于0。这样就可以把产销不平衡问题化为产销平衡问题进行这样就可以把产销不平衡问题化为产销平衡问题进行处理处理.不过不过,在用计算机软件求解时在用计算机软件求解时,一般不需要化为产一般不需要化为产销平衡问题销平衡问题,因为在软件的设计时因为在软件的设计时,都能够自动处理都能够自动处理.4.3表上作业法的特殊情况表上作业法的特殊情况安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 4949 8/14/20238/14/2023例例4农作物布局问题农作物布局问题(表表3-

49、3)，求产量，求产量最大最大的布局方案。的布局方案。表3-3 农作物布局问题的平衡表与产量表土地土地 农作物农作物B1B2B3B4土地面积土地面积 B1B2B3B4A110005726A24004103A318001344播种面积600 800 500 130032004.3表上作业法的特殊情况表上作业法的特殊情况安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 5050 8/14/20238/14/2023解解：用最大元素法作初始调运方案（表：用最大元素法作初始调运方案（表3-4）：）：表3-4 农作物布局问题的初始方案土地土地 农作物农作物B1B2B3B4土地

50、面积土地面积 B1B2B3B4A180020010005726A24004004103A3200500 110018001344播种面积600 800 500 13003200有检验数有检验数,不是最优解不是最优解,进行进行调整调整(表表3-5)。4.3表上作业法的特殊情况表上作业法的特殊情况安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 5151 8/14/20238/14/2023表3-5 农作物布局问题的方案调整土地土地 农作物农作物B1B2B3B4土地土地面积面积B1B2B3B4A1+200800200-2001000200800A2400400400A

51、3200-200 5001100+200180005001300播种面积60080050013003200所有检验数全部非正，最优。最大产量：所有检验数全部非正，最优。最大产量：maxZ=2005+8007+4004+5004+13004=15400使用位使用位势法求势法求检验数检验数4.3表上作业法的特殊情况表上作业法的特殊情况安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 5252 8/14/20238/14/2023经典运输问题经典运输问题“悖论悖论”.例例5对于例对于例2讨论的运输问题讨论的运输问题,最优调运方案如下表所示最优调运方案如下表所示表表3-6

52、运输问题的平衡表与运价表运输问题的平衡表与运价表B1B2B3B4发量B1B2B3B4A1257311310A21341928A363974105收量365620表表3-6是最优方案。是最优方案。minZ=23+53+11+38+64+35=854.3表上作业法的特殊情况表上作业法的特殊情况安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 5353 8/14/20238/14/2023对应的运输问题的数学模型为：对应的运输问题的数学模型为：4.3表上作业法的特殊情况表上作业法的特殊情况安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 5

53、454 8/14/20238/14/2023若将模型改为：若将模型改为：4.3表上作业法的特殊情况表上作业法的特殊情况安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 5555 8/14/20238/14/2023表表3-7增加收发量的平衡表与运价表增加收发量的平衡表与运价表则可得到以下两种情况下，则可得到以下两种情况下，运输量多运输量多，而，而总运费反而总运费反而少的运输方案少的运输方案。这就是经典运输问题。这就是经典运输问题“悖论悖论”，或者，或者说是说是“多反而少多反而少”现象（表现象（表3-7，表，表3-8）。）。B1B2B3B4发量B1B2B3B4A12

54、57311310A24041928A3661274105收量665623表表3-7所示方案是最优方案。所示方案是最优方案。MinZ=23+53+41+08+64+65=794.3表上作业法的特殊情况表上作业法的特殊情况安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 5656 8/14/20238/14/2023表表3-8增加收发量的平衡表与运价表增加收发量的平衡表与运价表表表3-8是最优方案。是最优方案。MinZ=73+41+64+65=79B1B2B3B4发量B1B2B3B4A177311310A240041928A3661274105收量4676234.3表

55、上作业法的特殊情况表上作业法的特殊情况安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 5757 8/14/20238/14/2023例例6某工厂专造飞机发动机，根据合同，某工厂专造飞机发动机，根据合同，14月份交货量以及工月份交货量以及工厂的最大生产能力如表厂的最大生产能力如表4-1，由于技术上的原因，生产发动机的，由于技术上的原因，生产发动机的成本波动，其变化情况见表成本波动，其变化情况见表4-1。表表4-1飞机发动机交货量与生产能力飞机发动机交货量与生产能力月份1月2月3月4月交货台数10152520工厂的最大生产能力25353010每台发动机成本（万元）1

56、.081.111.101.13由于生产成本的变化，可能在某个月成本低时由于生产成本的变化，可能在某个月成本低时多生产多生产些些留到以留到以后用后用，但每台发动机，但每台发动机存贮一个月存贮一个月要要0.015(万元万元)(包括成本的利息包括成本的利息等等)。现要制定一个进度表，。现要制定一个进度表，每月安排生产每月安排生产多少台可使总成本多少台可使总成本最小？最小？4.4运输问题的应用运输问题的应用安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 5858 8/14/20238/14/2023但是但是,2月生产的不能在月生产的不能在1月份供应月份供应,3月份生产的

57、不能在月份生产的不能在1、2月份供应月份供应,4月份生产的不能在月份生产的不能在1、2、3月份供应月份供应,解：解：由于有存贮费由于有存贮费,因此因此1月份生产每台的成本月份生产每台的成本1.08万元万元,如果如果2月份才卖出月份才卖出,那么成本为那么成本为1.08+0.015=1.095万元万元;若留到若留到3、4月份才卖出，相应的成本分别为月份才卖出，相应的成本分别为1.11万元万元和和1.125万元。其余的成本计算与此类似。万元。其余的成本计算与此类似。为了阻止这种行为发生，我们将对应的为了阻止这种行为发生，我们将对应的成本成本定为一个定为一个充分大的正数充分大的正数M。由于生产能力的产

58、量大于需求量，由于生产能力的产量大于需求量，构造一个虚的需要构造一个虚的需要地地，其需要量为，其需要量为25+35+30+10-10-15-25-20=30。则可。则可列表如表列表如表4-2.4.4运输问题的应用运输问题的应用安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 5959 8/14/20238/14/2023表表4-2飞机发动机飞机发动机交货量与生产能力交货量与生产能力的平衡表的平衡表1月2月3月4月未未生生产产产量1月2月3月4月未未生生产产1月1015251.081.0951.111.12502月053035M1.111.1251.14003月25

59、530MM1.101.11504月1010MMM1.1300需要量1015252030100取取M=1000用计算机软件可求得最优解如表用计算机软件可求得最优解如表1-89，Z=77.3万元。万元。4.4运输问题的应用运输问题的应用安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 6060 8/14/20238/14/2023min1.08x11+1.095x12+1.11x13+1.125x14+1000 x21+1.11x22+1.125x23+1.14x24+1000 x31+1000 x32+1.1x33+1.115x34+1000 x41+1000 x4

60、2+1000 x43+1.13x44stx11+x12+x13+x1425x21+x22+x23+x2435x31+x32+x33+x3430 x41+x42+x43+x44=30 x11+x21+x31=50 x12+x22+x32=70 x13+x23+x33=10end4.4运输问题的应用运输问题的应用安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 6666 8/14/20238/14/2023LPOPTIMUMFOUNDATSTEP10OBJECTIVEFUNCTIONVALUE1)2460.000VARIABLEVALUEREDUCEDCOSTx110

61、.0000004.000000 x1250.0000000.000000 x130.0000007.000000 x140.0000002.000000 x210.0000002.000000 x2220.0000000.000000 x230.0000004.000000 x2440.0000000.000000 x3150.0000000.000000 x320.0000000.000000 x330.0000001.000000 x340.000000978.0000004.4运输问题的应用运输问题的应用安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 67

62、67 8/14/20238/14/2023ROWSLACKORSURPLUSDUALPRICES2)0.000000-15.0000003)0.000000-15.0000004)0.000000-22.0000005)20.0000000.0000006)0.0000003.0000007)0.0000002.0000008)30.0000000.0000009)30.0000000.000000NO.ITERATIONS=104.4运输问题的应用运输问题的应用安徽财经大学统计与应用数学学院安徽财经大学统计与应用数学学院page page 6868 8/14/20238/14/2023表表4-5三个化肥厂供应四个地区的化肥的计划表三个化肥厂供应四个地区的化肥的计划表产量A505016132217B20406014131915C5050192023最低需求3070010最高需求507030不限当然，如果用当然，如果用LINGO直接编程求解也是很方便的。直接编程求解也是很方便的。于是可得到总运费最省的化肥调拨方案如于是可得到总运费最省的化肥调拨方案如4-5所示所示:4.4运输问题的应用运输问题的应用