第四章运输问题

1、 第四章第四章 运输问题运输问题 Combinatorial Optimization Theory第四章第四章 运输问题运输问题 运输问题（运输问题（Transportation Problem，简记为，简记为TP）是一类常见而且极其特殊的线性规划问题是一类常见而且极其特殊的线性规划问题. .它最早是从它最早是从物资调运工作中提出来的，是物流优化管理的重要的物资调运工作中提出来的，是物流优化管理的重要的内容之一内容之一 。 从理论上讲，运输问题也可用单纯形法来求解，从理论上讲，运输问题也可用单纯形法来求解，但是由于运输问题数学模型具有特殊的结构，存在一但是由于运输问题数学模型具有特殊的结构，

2、存在一种比单纯形法更简便的计算方法种比单纯形法更简便的计算方法 表上作业法，表上作业法，用表上作业法来求解运输问题比用单纯形法可节约计用表上作业法来求解运输问题比用单纯形法可节约计算时间与计算费用算时间与计算费用. .但表上作业法的实质仍是单纯形法但表上作业法的实质仍是单纯形法 加速物资流转加速物资流转 降低流通费用降低流通费用 1 运输问题及其数学模型1 1 运输问题及其数学模型运输问题及其数学模型 设某种物资共有设某种物资共有 m 个产地个产地 A1，A2，Am，各各产地的产量分别是产地的产量分别是a1，a2 ，am；有有n 个销地个销地 B1，B2，Bn ，各销地的销量分别为各销地的销量

3、分别为b1，b2，bn . 假定从产地假定从产地Ai（i =1，2，m）向销地向销地Bj（j =1，2，n）运输单位物资的运价是运输单位物资的运价是cij，问怎样调运才能，问怎样调运才能使总运费最小？使总运费最小？一、一、运输问题的数学模型运输问题的数学模型0,0,0 (1,2,;1,2, )ijijabcim jn第四章第四章 运输问题运输问题 销地销地产地产地 B1 B2 Bn产量产量 A1c11c21 c1n a1 A2c21c22 c2n a2 Amcm1cm2 cmn am销量销量 b1 b2 bn 运输表运输表1 1、产销平衡问题、产销平衡问题即即11mnijijab 设设 xij

4、 表示产地表示产地 Ai 运往销地运往销地 Bj (i=1,2,m; j=1,2,n) 的运量的运量.11minmnijijijzc x1. .nijijstxa1,2,im1mijjixb1,2,jn01,2,;1,2,ijxim jn 销地销地产地产地 B1 B2 Bn产量产量 A1 x11c11 x12c12 x1n c1n a1 A2 x21c21 x22c22 x2nc2n a2 Am xm1cm1 xm2cm2 xmncmn am销量销量 b1 b2 bnNote : cij 在左下在左下角角 xij 在右上角在右上角 1 运输问题及其数学模型2 2、产销不平衡问题、产销不平衡问题

5、当当11mnijijab11minmnijijijzc x1. .nijijstxa1,2,im1mijjixb1,2,jn01,2,;1,2,ijxim jn当当11mnijijab11minmnijijijzc x1. .nijijstxa1,2,im1mijjixb1,2,jn01,2,;1,2,ijxim jn第四章第四章 运输问题运输问题二、运输问题数学模型的特点二、运输问题数学模型的特点讨论产销平衡问题讨论产销平衡问题定理定理 1 平衡运输平衡运输问题必有可行解，也必有最优解问题必有可行解，也必有最优解. . 证明证明定理定理 2 平衡运输问题的约束方程系数矩阵平衡运输问题的约束方

6、程系数矩阵 A 和增广矩和增广矩阵阵 的秩相等，且等于的秩相等，且等于 m+n-1 . 即即 A( )( )1R AR Amn定理定理2 说明：说明：基可行解包含基可行解包含m+n-1个基变量个基变量.定理定理 3 平衡运输问题的约束方程系数矩阵平衡运输问题的约束方程系数矩阵 A 的所有的所有各阶子式只取各阶子式只取 0，1 或或 -1 三个值三个值.定理定理 4 如果平衡运输问题中的所有产量如果平衡运输问题中的所有产量 ai 和销量和销量 bj都是整数，那么，它的任一基可行解都是整数解都是整数，那么，它的任一基可行解都是整数解. .证明证明noteGo on定理定理 1 1 的证明的证明Pr

7、oof :11mnijijabd设(1,2,;1,2, )ijijabxim jnd111(1,2,)nnnijiijjijjjabaxba imdd则取则取显然有显然有 ， 0ijx 又又111(1,2, )mmmijjijijiiiabbxabjndd所以所以 ，是问题的一个可行解，是问题的一个可行解. 0ijx 0 (1,2,;1,2, )ijcim jn 又因为又因为 ，对于任一可行，对于任一可行解有目标函数值解有目标函数值 ，对于求极小化问题，目标函数，对于求极小化问题，目标函数值有下界，则必有最优解值有下界，则必有最优解. 0z 1 运输问题及其数学模型Note : 平衡运输问题有

8、平衡运输问题有 个变量，个变量， 个约束个约束条件，规模很大。条件，规模很大。m nmn111111111111111111A111212122212nnmmmnxxxxxxxxxGo back( )1R Amn( )1R Amnmn1212111111111111111111mnaaaAbbb定理定理 4 的证明的证明Proof : 设设 x 是是 Ax = b 的任一基可行解，的任一基可行解，1 12211,mnmni ji jijxxxB 为对应的基矩阵，则为对应的基矩阵，则det(1, 2,1)detttti jBxtmnB 其中其中 Bt 是用是用 b 中对应的中对应的 m+n-1元

9、素替换元素替换 B 的第的第t 列列元素得到的矩阵元素得到的矩阵.1212Tmnbaaabbb 显然显然，由定理，由定理 3 及及 ai 、 bj都是整数知，都是整数知，det Bt 是个是个整数，整数， det B= ，因此，因此，都是整数都是整数.1(1, 2,1)tti jxtmn其基变量为其基变量为第四章第四章 运输问题运输问题定义定义 1 1凡是能排列成凡是能排列成1 11 22 22 31,s ssi ji ji ji ji ji jxxxxxx（其中（其中 互不相同，互不相同， 互不相同）互不相同）12, ,si ii12,sjjj形式的变量集合，称为一个闭回路，其中诸变量称为形

10、式的变量集合，称为一个闭回路，其中诸变量称为这个闭回路的顶点这个闭回路的顶点. B1 B2 B3 B4 B5 A1 x11 x12 x13 x14 x15 A2 x21 x22 x23 x24 x25 A3 x31 x32 x33 x34 x35 A4 x41 x42 x43 x44 x45如：如： 变量集合变量集合111222243431,xxxxxx变量集合变量集合1114444535322221,xxxxxxxx2、每一行（或列）若有闭回路的顶点，则有两个每一行（或列）若有闭回路的顶点，则有两个顶点；顶点；3、每两个顶点格子的连线都是水平的或垂直的；每两个顶点格子的连线都是水平的或垂直的

11、；4、闭回路中顶点的个数必为偶数闭回路中顶点的个数必为偶数. .闭回路的几何特征：闭回路的几何特征：1、每一个顶点格子都是每一个顶点格子都是 90转角点；转角点；1 运输问题及其数学模型闭回路的代数性质：闭回路的代数性质：1 11 22 22 31,s ssi ji ji ji ji ji jxxxxxx性质性质 1 构成闭回路的变量组对应的列向量组构成闭回路的变量组对应的列向量组1 11 22 22 31,s ssi ji ji ji ji ji jpppppp必线性相关必线性相关.证明证明性质性质 2 分组分组构成闭回路，则该变量组对应的列向量组构成闭回路，则该变量组对应的列向量组1 12

12、 2,r ri ji ji jppp是线性相关的是线性相关的.推论推论 1 若变量组对应的列向量组线性无关，则该变若变量组对应的列向量组线性无关，则该变量组一定不包含闭回路量组一定不包含闭回路.若变量组若变量组 中有一个部中有一个部1 12 2*,( )r ri ji ji jxxxGo on性质性质 1 的证明的证明Proof :由直接计算可知由直接计算可知1 11 22 22 310s ssi ji ji ji ji ji jpppppp111111111111111111A111212122212nnmmmnxxxxxxxxx故该向量组线性相关故该向量组线性相关.第四章第四章 运输问题运

13、输问题在变量组在变量组 中，若有某中，若有某1 12 2*,( )r ri ji ji jxxx一个变量一个变量 xij 是它所在的行（第是它所在的行（第 i 行）或列（第行）或列（第 j 列）列）中出现于中出现于（*）中的唯一变量，则称该变量中的唯一变量，则称该变量 xij 是该变量是该变量组的一个孤立点组的一个孤立点.定义定义 21114444535322221,xxxxxxxx闭回路的特征闭回路的特征性质性质 3 没有孤立点没有孤立点 若一变量组中不包含任何闭回路，则该变量组若一变量组中不包含任何闭回路，则该变量组必有孤立点必有孤立点.反证反证孤立点不会是孤立点不会是闭回路上的点闭回路上

14、的点定理定理 5 变量组变量组 对应的列向量组线性无关的充要对应的列向量组线性无关的充要*( )条件是该变量组中不包含任何闭回路条件是该变量组中不包含任何闭回路. .证明证明定理定理 5 的证明的证明Proof :用反证法用反证法设变量组设变量组（*）对应的列向量）对应的列向量组线性无关，但该变量组包含一个以其中某些变量为顶组线性无关，但该变量组包含一个以其中某些变量为顶点的闭回路，点的闭回路，则由性质则由性质 2 知，这些变量对应的列向量必知，这些变量对应的列向量必线性相关，与假设矛盾线性相关，与假设矛盾. .定理定理 5 变量组变量组 对应的列向量组线性无关的充要对应的列向量组线性无关的充

15、要*( )条件是该变量组中不包含任何闭回路条件是该变量组中不包含任何闭回路. .设有一组数设有一组数 使得使得12,rkkk1 122120(1)rri ji jri jk pk pk p 由于变量组由于变量组（* *）中不包含任何闭回路，由性质中不包含任何闭回路，由性质 3 可知其中必有孤立点，可知其中必有孤立点， 不妨设不妨设 为孤立点，为孤立点，1 1i jx又不妨设又不妨设 是（是（* *）在第）在第i1 1行上唯一的变量，这时由行上唯一的变量，这时由p pijij的特征，（的特征，（1 1）的左端第）的左端第i1个分量和为个分量和为k1，而右端为，而右端为0，1 1i jx在第在第

16、j1列上的唯列上的唯一变量如何？一变量如何？2 21200r ri jri jkk pk p，从而（1）变成（2）但但 仍不包含闭回路，其中还有孤立点仍不包含闭回路，其中还有孤立点, ,2 23 3,r ri ji ji jxxx与前面类似分析可证与前面类似分析可证 k2= 0. 同理得同理得 k3 = k4 = kr = 0这就证明了向量组这就证明了向量组（* *）线性无关线性无关.1 运输问题及其数学模型推论推论 2 平衡运输问题中的一组平衡运输问题中的一组 m + n - 1 个变量个变量能构成基变量的充要条件是它不包含任何闭回路能构成基变量的充要条件是它不包含任何闭回路.1 122,(

17、1)ssi ji ji jxxxsmn 该推论给出了运输问题的基可行解中基变量的一该推论给出了运输问题的基可行解中基变量的一个基本特征：基变量组不含闭回路个基本特征：基变量组不含闭回路. . 这就是基可行解这就是基可行解在表上的一个表现，利用它来判断在表上的一个表现，利用它来判断 m + n 1 个变量个变量是否构成基变量组，就看它是否包含闭回路是否构成基变量组，就看它是否包含闭回路. . 这种方法简便易行，它比直接判断这些变量对应这种方法简便易行，它比直接判断这些变量对应的列向量是否线性无关要简便得多的列向量是否线性无关要简便得多. . 利用基变量的这个特征，将可以导出求平衡运输利用基变量的

18、这个特征，将可以导出求平衡运输问题的初始基可行解的一些简便方法问题的初始基可行解的一些简便方法. .2 运输问题的表上作业法2 2 运输问题的表上作业法运输问题的表上作业法 表上作业法（又称运输单纯形法）是根据单纯形表上作业法（又称运输单纯形法）是根据单纯形法的原理和运输问题的特点，设计的一种在表上运算法的原理和运输问题的特点，设计的一种在表上运算的求解运输问题的简便而有效的方法的求解运输问题的简便而有效的方法.主要步骤：主要步骤：1、求一个初始调运方案（初始基可行解）；求一个初始调运方案（初始基可行解）；2、判别当前方案是否为最优，若是则迭代停止，否则判别当前方案是否为最优，若是则迭代停止，

19、否则 转下一步；转下一步；3、改进当前方案，得到新的方案（新的基可行解），改进当前方案，得到新的方案（新的基可行解）， 再返回再返回 2 。第四章第四章 运输问题运输问题一、一、初始方案的确定初始方案的确定1、西北角法西北角法 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15Ex. 1 50 已知某商品有三个产地已知某商品有三个产地A1、A2、A3和四个销地和四个销地B1、B2、B3、B4 ，产量、销量及单位运价如表，产量、销量及单位运价如表. .问应问应如何调运，在满足各销地需要的情况下，

20、使总的运费如何调运，在满足各销地需要的情况下，使总的运费支出为最少？支出为最少？ 解：解：51010205规则规则: :从运输表的西从运输表的西北角开始北角开始, ,优先安排优先安排编号小的产地和销地编号小的产地和销地的运输任务的运输任务. .填了几个数字？填了几个数字？10505203 51 10254 10675z Note : 在填入一个数时，如果行和列同时饱和，在填入一个数时，如果行和列同时饱和， 规定只划去一行或一列规定只划去一行或一列 BjAi B1 B2 B3 B4 ai A110 5 2 3 50 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10

21、155002 运输问题的表上作业法2、最小元素法最小元素法 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15规则规则: :优先安排单位运价最小的产地与销地之间的运输优先安排单位运价最小的产地与销地之间的运输 任务任务. .4010255101010405253 51 102 105 10620z Note : 在某行（或列）填入最后一个数时，如果行和在某行（或列）填入最后一个数时，如果行和列同时饱和，规定只划去该行（或列）列同时饱和，规定只划去该行（或列） BjAi B1 B2 B3 B4

22、ai A1 1 5 3 2 60 A2 4 1 2 3 20 A3 5 6 1 4 10 bj 50 20 10 100010102050填了几个数字？填了几个数字？第四章第四章 运输问题运输问题定理定理 6 用西北角法或最小元素法得到的初始解是用西北角法或最小元素法得到的初始解是平衡平衡运输问题的基可行解，运输问题的基可行解， m+n-1 个个填入数字的格子对应的填入数字的格子对应的是基变量是基变量.Proof : ijx首先，得到的初始解首先，得到的初始解 为可行解是显然的为可行解是显然的. . 其次，由于行列数共有其次，由于行列数共有 m+n ，而按填数字的方法，而按填数字的方法, ,除

23、填最后一个数时，划去一行一列外，每填一个数划去除填最后一个数时，划去一行一列外，每填一个数划去一行或一列一行或一列. 因此因此, , 共填共填 m+n-1 个数个数. . 最后，证明所填最后，证明所填 m+n-1 个数对应的变量组不含闭回路个数对应的变量组不含闭回路.用反证法用反证法若含有闭回路若含有闭回路 不妨设此闭回路如右不妨设此闭回路如右（其他情形同理可证）（其他情形同理可证）1 1i jx4 4i jx3 3i jx2 2i jx 不妨设填不妨设填 后划去行，故后划去行，故 必须较必须较 先填，先填，且填后划去的是列，从而且填后划去的是列，从而 必须较必须较 先填，且填后划先填，且填后

24、划去的是行，而这又说明去的是行，而这又说明 必须较必须较 先填，且填后划先填，且填后划去的是列，这又得到去的是列，这又得到 必须较必须较 先填，且填后划去的先填，且填后划去的是行，这样就得到了矛盾，所以，填数的是行，这样就得到了矛盾，所以，填数的 m+nm+n-1 -1 个格个格子对应的变量组不含闭回路，从而，证得了本定理子对应的变量组不含闭回路，从而，证得了本定理. . 1 1i jx4 4i jx2 2i jx3 3i jx1 1i jx2 2i jx4 4i jx3 3i jx1 1i jx2 运输问题的表上作业法关键关键1、填一个数字划去一行或一列填一个数字划去一行或一列 不产生闭回路

25、；不产生闭回路； 2、填一个数字填一个数字只只划去一行或一列划去一行或一列 填满填满m+n-1-1个数个数. . BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 差额差额 6 2 差额差额 5 1315 BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 8 53 1 1 346z 按最小元素法按最小元素法3423、Vogel 法法 ( (元素差额法元素差额法) )规则：计算各行各列的最小元素与次小元素的差额，规则：计算各行各列的最小元素与次小元素的差额，优先安排差额最大的所优先安排差额最大的所在行或列的单位运价最在行或列的单位运价最小的

26、产地与销地之间的小的产地与销地之间的运输任务运输任务8 23 42 334Vz 这是最优解这是最优解.110 405 52 103 153 205 10600VExz 第四章第四章 运输问题运输问题二、二、最优性检验最优性检验 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1540102551010定理定理 7 设设 是平衡运输问题的是平衡运输问题的一组基变量，一组基变量， 是非基变量，则在变量组是非基变量，则在变量组 中存在唯一的闭回路中存在唯一的闭回路.1 12 2,(1)s si ji

27、ji jxxxsmn1 12 20,s si ji ji jx xxx0 x1、闭回路法闭回路法+1-1+1-121423 105 检验数检验数 BjAi B1 B2 B3 B4 A1 A2 A3检验数表检验数表-5-10 6 6 6ijijijcc奇顶点偶顶点2 运输问题的表上作业法2、位势法（对偶变量法）位势法（对偶变量法）求检验数的求检验数的方法方法11minmnijijijzc x1. .nijijstxa1,2,im1mijjixb1,2,jn01,2,1,2,ijximjn11minmnijijijzc x1nijijxa2,3,im1mijjixb1,2,jn01,2,1,2,i

28、jximjn111211nxxxa. .st0 x00a x约束方程的系数矩阵的秩为约束方程的系数矩阵的秩为m+n -1x0必为基变必为基变量量, x0= 0约束方程的系数矩阵的秩为约束方程的系数矩阵的秩为m+n对任意的对任意的 a0， 与原问题等价与原问题等价1212,mnyu uuv vv11maxmniijjijaub v10. .1,2,1,2,ijijijstuvcimuajnu v无符号限制由于由于01010ijipmj ijijijcyp1212,ijmnijcu uuv vvpijijcuv001au010000pxj 的检验数的检验数 1jjBjjjcc Bpcyp1 12

29、2,(1)s si ji ji jxxxsmn设：为基变量，由于基变量设：为基变量，由于基变量的检验数等于零的检验数等于零111 1222 210sss siji jiji jiji juvcuvcuvcua一定有解，不唯一一定有解，不唯一（a0 0可任取）可任取）ui 称为行位势称为行位势，vj 称为列位势称为列位势第四章第四章 运输问题运输问题ijijcuv BjAi B1 B2 B3 B4 ui A1 4010 25 5 2 5 3 A2 4 3 10 1 10 2 A3 10 5 6 3 4 vj BjAi B1 B2 B3 B4 A1 A2 A3检验数表检验数表-5-10 6 6 6

30、-2-120273见见 Ex. 1 最小元素法得到的初始基可行解最小元素法得到的初始基可行解2121241411cccc21241411cuvuvuv2121cuv4275 3333333( 2)( 1)6cuv 10053-12-5323232cuv6( 5)56 若若 ，则此时的运输方案为最优的，则此时的运输方案为最优的0ijijijijcuv2 运输问题的表上作业法三、三、基可行解的改进基可行解的改进 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1540102551010 BjAi B

31、1 B2 B3 B4 A1 A2 A3检验数表检验数表-5-10 6 6 6选择进基变量选择进基变量min0,1,1stijijimjn 则取非基变量则取非基变量 xst 为进基变量为进基变量确定出基变量确定出基变量调整量调整量 minijklxx闭回路上偶顶点则基变量则基变量 xkl 出基（运量擦去）出基（运量擦去）调整方法：在该闭回路上，奇点运量加调整方法：在该闭回路上，奇点运量加 ，偶点减去，偶点减去 能转运多少？能转运多少？153010 6 5 4 2010 1-5 6 520 6 6 4 5 6 因为因为 ，所以此运输方案为最优，所以此运输方案为最优方案方案0ijNote : 若在闭

32、回路上有几个偶点处的运量等于若在闭回路上有几个偶点处的运量等于 ，则，则可任取其中一个作为出基变量（运量擦去），其余几可任取其中一个作为出基变量（运量擦去），其余几个点的值调整后变为个点的值调整后变为0. (0. (但应填入，说明这些变量还但应填入，说明这些变量还在基内，这时就出现了退化在基内，这时就出现了退化) )620-50-50=520问：问：从从A2到到B4的单位运价的单位运价c24在什么范围变化时，所得在什么范围变化时，所得最优调运方案不变最优调运方案不变. . c12在什么范围变化呢？在什么范围变化呢？第四章第四章 运输问题运输问题补充：运输问题的图上作业法补充：运输问题的图上作业

33、法 图上作业法是在交通图上进行物资调运方案编制和图上作业法是在交通图上进行物资调运方案编制和调整的一种科学方法。在铁路特别是公路运输中使用很调整的一种科学方法。在铁路特别是公路运输中使用很多且有很好的效果。多且有很好的效果。 在交通图中，用在交通图中，用表示表示产地（发点），并将产量记产地（发点），并将产量记在圆圈内；用在圆圈内；用表示销地表示销地（收点），并将销量记在方（收点），并将销量记在方框内。框内。206040402463目标：吨公里数目标：吨公里数( (费用费用) )最小的调运方案最小的调运方案 . . 物资调运的流向用与交通线平行的箭线表示，规定物资调运的流向用与交通线平行的箭线表

34、示，规定画在前进方向的右边，调运量加括号记在箭线的右边。画在前进方向的右边，调运量加括号记在箭线的右边。(20)(20)(40)补充：运输问题的图上作业法20303020243对流：物资在同一线路上往返运输对流：物资在同一线路上往返运输.(20)(20)(30)(30)(10)这是对流这是对流20303020243(20)(20)(30)(30)106030(10)(20)1、无圈无圈的交通的交通图图2020502010 对于无圈图，每条对于无圈图，每条边都是割边，去掉它网边都是割边，去掉它网络将不连通，所以，每络将不连通，所以，每条边上的运量是不得不条边上的运量是不得不只要每条边上不产生对流

35、，即为最优方案只要每条边上不产生对流，即为最优方案第四章第四章 运输问题运输问题206040402463(20)(20)(40)2、有一个圈的交通图有一个圈的交通图圈长：圈上每一条边的长度之和（记为圈长：圈上每一条边的长度之和（记为 l）l =15 先用先用“丢边破圈丢边破圈”方法，得到无圈图，再产生一方法，得到无圈图，再产生一个个没有对流的方案。没有对流的方案。内圈长内圈长 l内内：流向在圈内的边的长度之和：流向在圈内的边的长度之和l内内= 8外圈长外圈长 l外外：流向在圈外的边：流向在圈外的边的长度之和的长度之和l外外= 4是最优解吗？是最优解吗？8,2ll 内不是最优的.称为迂回称为迂回

36、调整方案：调整方案：对内圈各流量中最小调运量，进行反向调运对内圈各流量中最小调运量，进行反向调运(40)(20)(20)结论：结论：内外圈长都小于圈长的一半的无对流的调运方案内外圈长都小于圈长的一半的无对流的调运方案 为最优方案为最优方案67.22llll外内此时为最优调运方案补充：运输问题的图上作业法3、有多个、有多个圈圈的交通的交通图图106030202050203020有几个圈？ 如有一个圈的情形，对每一个圈先用如有一个圈的情形，对每一个圈先用“丢边破圈丢边破圈”方方法，得到无圈图，再产生一个没有对流的方案。再进行法，得到无圈图，再产生一个没有对流的方案。再进行检查、调整。检查、调整。只

37、需检查13个圈吗？会循环吗？ 一般不够！因为对一个圈进行调整后，会对已检一般不够！因为对一个圈进行调整后，会对已检查的圈有影响查的圈有影响. 不会！因为每次目标不会！因为每次目标函数下降值大于一个固定函数下降值大于一个固定值（如值（如 1）第四章第四章 运输问题运输问题四、四、产销不平衡运输问题产销不平衡运输问题当当11mnijijab111minmnijijijzc x1. .nijijstxa1,2,1im m11mijjixb1,2,jn01,2,1;1,2,ijxim mjnNote : 通常建立运输模通常建立运输模型指的是平衡运输模型型指的是平衡运输模型可以虚设一个产地可以虚设一个产

38、地 Am+1, 其产量为其产量为111nmmjijiaba 并假设产地并假设产地 Am+1 运往各销地的单运往各销地的单位运价为位运价为 cm+1, j = 0 ( j = 1 , 2 , , n ) . 则原问题可转则原问题可转化为平衡运输问题：化为平衡运输问题： 产大于销，可通产大于销，可通过虚设销地，类似过虚设销地，类似建立平衡运输模型建立平衡运输模型2 运输问题的表上作业法Ex. 2已知运输问题由表给出，试建立运输模型已知运输问题由表给出，试建立运输模型 . Bj Ai B1 B2 B3 ai A14 25 10 A2638 15 bj 8 7 14解解: Bj Ai B1 B2 B3

39、 ai A14 25 10 A2638 15 A3000 4 bj 8 7 14本题产量为本题产量为25，销量为，销量为29，是销大于产问题，是销大于产问题 虚设一个产地虚设一个产地 A3，由于并没有生产，所以运价为，由于并没有生产，所以运价为零，得运输模型零，得运输模型. . 如果各销地不满足时，单位缺货费为如果各销地不满足时，单位缺货费为 4，3，7，则，则运输模型为运输模型为437第四章第四章 运输问题运输问题 BjAi B1 B2 B3 ai A14 23 10 A2564 15 A3345 20 最低最低需求量需求量 10 10 10Ex. 3 已知运输问题由表给出，如果产地已知运输

40、问题由表给出，如果产地 Ai 的产量的产量必须运走必须运走，试建立运输模型试建立运输模型 . BjAi B1 B2 B3 B4 ai A14 23 10 A2564 15 A3345 20 bj 10 10 10 15解解:这是一个产大于销的运输问题这是一个产大于销的运输问题. .234虚设一销地虚设一销地 B4 ,销量销量 b4 = 15 . BjAi B1 B2 B3 ai A14 23 10 A2564 15 A3345 20 最低最低需求量需求量 10 10 10 最高最高需求量需求量 20 10不限不限 BjAi B1 B2 B3 ai A14 23 10 A2564 15 A334

41、5 20 bj 10 10 10 443B3B15351015A4M100MM0 三个销地的最低需求为三个销地的最低需求为 30，最高需求不限最高需求不限. . 根据根据现有产量，现有产量，B3 至多能得到至多能得到 25. 建立运输模型建立运输模型 .2说明什么？说明什么？第四章第四章 运输问题运输问题3 运输问题应用举例运输问题应用举例Ex. 4 (生产调度问题生产调度问题) 某制冰厂每年某制冰厂每年1 4 季度必须供季度必须供应冰块应冰块 15、20、25、10（千吨）（千吨）. .已知该厂各季度冰已知该厂各季度冰 块的生产能力及冰块的单位成本如表块的生产能力及冰块的单位成本如表. .

42、如果生产出来如果生产出来的冰块不在当季度使用，每千吨冰块存储一个季度的冰块不在当季度使用，每千吨冰块存储一个季度费用为费用为4（千元）（千元）. .又设该制冰厂每年第又设该制冰厂每年第3季度末对贮季度末对贮冰库进行清库维修冰库进行清库维修. .问应如何安排冰块的生产，可使问应如何安排冰块的生产，可使该厂全年生产、该厂全年生产、存储费用最少？存储费用最少？季季 度度 生产能力（千吨）生产能力（千吨） 单位成本（千元）单位成本（千元） 1 25 5 2 18 7 3 16 8 4 15 53 运输问题应用举例季季 度度 生产能力（千吨）生产能力（千吨） 单位成本（千元）单位成本（千元） 1 25

43、5 2 18 7 3 16 8 4 15 5 Bj Ai B1 B2 B3 B4 ai A1 25 A2 18 A3 16 A4 15 bj 15 20 25 10 解：解：5B54913M0MMMMM0005118179137第四章第四章 运输问题运输问题Ex. 5 ( (运量有界的运输问题运量有界的运输问题) ) 6 5 7 bj 10762 A2 84 53 A1 ai B3 B2 B1 BjAi表表 1 1 5 2 4 A2 3 3 4 A1 B3 B2 B1 dij表表 2 2 表表1 给出一个运输问题给出一个运输问题. .现在规定产地现在规定产地 Ai 至销地至销地 Bj 的运量不

44、能超过的运量不能超过 dij , , 由表由表 2 2 给定给定. . 试建立运输问题试建立运输问题 . .解解： 虚设虚设 Dij (i=1,2; j=1,2,3) 6 6个点，个点，Dij 既作产地，既作产地，又作销地，其产量、销量都为又作销地，其产量、销量都为 dij . . 产地产地 Ai 的物资只可的物资只可运送给运送给 Dij , 而而 Dij 的物资只可运送给的物资只可运送给 Bj ,或送给自身或送给自身.3 运输问题应用举例 BjAi D11 D12 D13 D21 D22 D23 B1 B2 B3 ai A1 D11 D12 D13 A2 D21 D22 D23 bj 6 5

45、 7 bj 10762 A2 84 53 A1 ai B3 B2 B1 BjAi表表 1 1 5 2 4 A2 3 3 4 A1 B3 B2 B1 dij表表 2 2 8 104330000305040000206074334254257563321303124244214第四章第四章 运输问题运输问题Ex. 6 ( (空车调度问题空车调度问题) ) 某航运公司承担六个港口城市某航运公司承担六个港口城市 A、B、C、D、E、F 的四条固定航线的物资运输任的四条固定航线的物资运输任务务. . 已知各条航线的起点、终点城市及每天航班数见已知各条航线的起点、终点城市及每天航班数见表表1，假定各条航线使用相同型号的船只，又各城市间，假定各条航线使用相同型号的船只，又各城市间的航程天数见表的航程天数见表2. 又知每条船只每次装卸货的时间各又知每条船只每次装卸货的时间各需一天，则该航运公司至少应配备多少条船，才能满足需一天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求？所有航线的运货需求？航航线线起点起点城市城市终点终点城市城市每天航班每天航班数数1ED32BC23AF14DB1表表1 1 到到从从ABCDEFA0121477B1031388C23015557851703F7852030表