运筹学-运输问题

1、2021/3/231 运输问题 运输问题（运输问题（Transportation Problem, ,简记为简记为TP）是一类常见而且极其特殊的线性规划问题是一类常见而且极其特殊的线性规划问题. .它最早是从它最早是从物资调运工作中提出来的物资调运工作中提出来的, ,是物流优化管理的重要的是物流优化管理的重要的内容之一内容之一 。 从理论上讲从理论上讲, ,运输问题也可用单纯形法来求解运输问题也可用单纯形法来求解, ,但是由于运输问题数学模型具有特殊的结构但是由于运输问题数学模型具有特殊的结构, ,存在一存在一种比单纯形法更简便的计算方法种比单纯形法更简便的计算方法 表上作业法表上作业法, ,

2、用表上作业法来求解运输问题比用单纯形法可节约计用表上作业法来求解运输问题比用单纯形法可节约计算时间与计算费用算时间与计算费用. .但表上作业法的实质仍是单纯形法但表上作业法的实质仍是单纯形法 2021/3/2321 运输问题及其数学模型1 1 运输问题及其数学模型运输问题及其数学模型 设某种物资共有设某种物资共有 m 个产地个产地 A1,A2,Am,各各产地的产量分别是产地的产量分别是a1,a2 ,am;有有n 个销地个销地 B1,B2,Bn ,各销地的销量分别为各销地的销量分别为b1,b2,bn . 假定从产地假定从产地Ai（i =1,2,m）向销地向销地Bj（j =1,2,n）运输单位物资

3、的运价是运输单位物资的运价是cij, ,问怎样调运才能问怎样调运才能使总运费最小使总运费最小? ?一、运输问题的数学模型一、运输问题的数学模型 加速物资流转加速物资流转 降低流通费用降低流通费用 0,0,0 (1,2,;1,2, )ijijabcim jn2021/3/233 运输问题 销地销地产地产地 B1 B2 Bn产量产量 A1c11c21 c1n a1 A2c21c22 c2n a2 Amcm1cm2 cmn am销量销量 b1 b2 bn 运输表运输表1 1、产销平衡问题、产销平衡问题即即11mnijijab 设设 xij 表示产地表示产地 Ai 运往销地运往销地 Bj (i=1,2

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

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

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

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

8、 个变量，个变量， 个约束个约束条件，规模很大。条件，规模很大。m nmn111111111111111111A1212111111111111111111mnaaaAbbb111212122212nnmmmnxxxxxxxxxGo back( )+1R Am n2021/3/238定理定理 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 知，知，det Bt 是个整数，是个整数， det B= ，因此，因此， 都是整数都是整数.1(1, 2,1)tti jxtmn其基变量为其基变量为2021/3/239 运输问题定义定义 1 1（其中（其中 互不相同，互不相同， 互不相同）互不相同）12, ,si ii12,sjjj形式的变量集合形式的变量集合,称为一个闭回路称为一个闭回路,其中诸变量称为其中诸变量称为这个闭回路的顶点这个闭回路的顶点. B1 B2 B3 B4 B5 A1 x11 x12 x13 x14 x15 A

10、2 x21 x22 x23 x24 x25 A3 x31 x32 x33 x34 x35 A4 x41 x42 x43 x44 x45如如:变量集合变量集合111222243431,xxxxxx变量集合变量集合1114444535322221,xxxxxxxx2、每一行（或列）若有闭回路的顶点每一行（或列）若有闭回路的顶点,则有两个则有两个顶点顶点;3、每两个顶点格子的连线都是水平的或垂直的每两个顶点格子的连线都是水平的或垂直的;4、闭回路中顶点的个数必为偶数闭回路中顶点的个数必为偶数. .闭回路的几何特征闭回路的几何特征:1、每一个顶点格子都是每一个顶点格子都是 90转角点转角点;凡是能排列

11、成凡是能排列成1 11 22 22 311 1, ,s ssi ji ji ji ji ji ji jxxxxxxx，凡是能排列成凡是能排列成1 11 22 22 311 1, ,s ssi ji ji ji ji ji ji jxxxxxxx，2021/3/23101 运输问题及其数学模型闭回路的代数性质闭回路的代数性质: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必线性相关必线性相关.证明证

12、明性质性质 2 分组分组构成闭回路构成闭回路,则该变量组对应的列向量组则该变量组对应的列向量组1 12 2,r ri ji ji jppp是线性相关的是线性相关的.推论推论 1 若变量组对应的列向量组线性无关若变量组对应的列向量组线性无关,则该变则该变量组一定不包含闭回路量组一定不包含闭回路.若变量组若变量组 中有一个部中有一个部1 12 2*,( )r ri ji ji jxxxGo on2021/3/2311性质性质 1 的证明的证明Proof :由直接计算可知由直接计算可知1 11 22 22 310s ssi ji ji ji ji ji jpppppp1111111111111111

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

14、变量组中不包含任何闭回路,则该变量组则该变量组必有孤立点必有孤立点.反证反证孤立点不会是孤立点不会是闭回路上的点闭回路上的点定理定理 5 变量组变量组 对应的列向量组线性无关的充要对应的列向量组线性无关的充要*( )条件是该变量组中不包含任何闭回路条件是该变量组中不包含任何闭回路. .证明证明2021/3/2313定理定理 5 的证明的证明Proof :用反证法用反证法设变量组设变量组（*）对应的列向量）对应的列向量组线性无关组线性无关,但该变量组包含一个以其中某些变量为顶但该变量组包含一个以其中某些变量为顶点的闭回路点的闭回路, 则由性质则由性质 2 知知,这些变量对应的列向量必这些变量对应

15、的列向量必线性相关线性相关, ,与假设矛盾与假设矛盾. .定理定理 5 变量组变量组 对应的列向量组线性无关的充要对应的列向量组线性无关的充要*( )条件是该变量组中不包含任何闭回路条件是该变量组中不包含任何闭回路. .设有一组数设有一组数 使得使得12,rkkk1 122120(1)rri ji jri jk pk pk p 由于变量组由于变量组（* *）中不包含任何闭回路中不包含任何闭回路,由性质由性质 3 可知其中必有孤立点可知其中必有孤立点,不妨设不妨设 为孤立点，为孤立点，1 1i jx又不妨设又不妨设 是（是（* *）在第）在第i1 1行上唯一的变量，这时由行上唯一的变量，这时由p

16、 pijij的特征，（的特征，（1 1）的左端第）的左端第i1个分量和为个分量和为k1，而右端为，而右端为0，1 1i jx在第在第 j1列上的唯列上的唯一变量如何一变量如何?2 21200r ri jri jkk pk p，从而（1）变成（2）但但 仍不包含闭回路，其中还有孤立点仍不包含闭回路，其中还有孤立点, ,2 23 3,r ri ji ji jxxx与前面类似分析可证与前面类似分析可证 k2= 0. 同理得同理得 k3 = k4 = kr = 0这就证明了向量组这就证明了向量组（* *）线性无关线性无关.2021/3/23141 运输问题及其数学模型推论推论 2 2 平衡运输问题中的

17、一组平衡运输问题中的一组 m + n - 1 个变量个变量能构成基变量的充要条件是它不包含任何闭回路能构成基变量的充要条件是它不包含任何闭回路.1 122,(1)ssi ji ji jxxxsmn 该推论给出了运输问题的基可行解中基变量的一该推论给出了运输问题的基可行解中基变量的一个基本特征个基本特征: :基变量组不含闭回路基变量组不含闭回路. . 这就是基可行解这就是基可行解在表上的一个表现在表上的一个表现, ,利用它来判断利用它来判断 m + n 1 个变量个变量是否构成基变量组是否构成基变量组,就看它是否包含闭回路就看它是否包含闭回路. . 这种方法简便易行这种方法简便易行,它比直接判断

18、这些变量对应它比直接判断这些变量对应的列向量是否线性无关要简便得多的列向量是否线性无关要简便得多. . 利用基变量的这个特征利用基变量的这个特征,将可以导出求平衡运输将可以导出求平衡运输问题的初始基可行解的一些简便方法问题的初始基可行解的一些简便方法. .2021/3/23152 运输问题的表上作业法2 2 运输问题的表上作业法运输问题的表上作业法 表上作业法（又称运输单纯形法）是根据单纯形表上作业法（又称运输单纯形法）是根据单纯形法的原理和运输问题的特点法的原理和运输问题的特点,设计的一种在表上运算设计的一种在表上运算的求解运输问题的简便而有效的方法的求解运输问题的简便而有效的方法.主要步骤

19、主要步骤:1、求一个初始调运方案（初始基可行解）求一个初始调运方案（初始基可行解）;2、判别当前方案是否为最优判别当前方案是否为最优,若是则迭代停止若是则迭代停止,否则否则 转下一步转下一步;3、改进当前方案改进当前方案,得到新的方案（新的基可行解）得到新的方案（新的基可行解）, 再返回再返回 2 。2021/3/2316 运输问题一、初始方案的确定一、初始方案的确定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 已知某商品有三个产地已知某商品有三个产

20、地A1、A2、A3和四个销地和四个销地B1、B2、B3、B4 , ,产量、销量及单位运价如表产量、销量及单位运价如表. .问应问应如何调运如何调运, ,在满足各销地需要的情况下在满足各销地需要的情况下, ,使总的运费使总的运费支出为最少支出为最少? ? 解解:51010205规则规则: :从运输表的西从运输表的西北角开始北角开始, ,优先安排优先安排编号小的产地和销地编号小的产地和销地的运输任务的运输任务. .填了几个数字填了几个数字? ?10505203 51 10254 10675z Note : 在填入一个数时在填入一个数时,如果行和列同时饱和如果行和列同时饱和, 规定只划去一行或一列规

21、定只划去一行或一列 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 155002021/3/23172 运输问题的表上作业法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

22、 : 在某行（或列）填入最后一个数时在某行（或列）填入最后一个数时,如果行和如果行和列同时饱和列同时饱和,规定只划去该行（或列）规定只划去该行（或列） BjAi B1 B2 B3 B4 ai A1 1 5 3 2 60 A2 4 1 2 3 20 A3 5 6 1 4 10 bj 50 20 10 100010102050填了几个数字填了几个数字? ?2021/3/2318 运输问题定理定理 6 用西北角法或最小元素法得到的初始解是用西北角法或最小元素法得到的初始解是平衡平衡运输问题的基可行解运输问题的基可行解, m+n-1 个个填入数字的格子对应的填入数字的格子对应的是基变量是基变量.Pro

23、of : ijx首先，得到的初始解首先，得到的初始解 为可行解是显然的为可行解是显然的. . 其次其次,由于行列数共有由于行列数共有 m+n ,而按填数字的方法而按填数字的方法, ,除填最后一个数时除填最后一个数时,划去一行一列外划去一行一列外,每填一个数划去每填一个数划去一行或一列一行或一列. 因此因此, , 共填共填 m+n-1 个数个数. . 最后最后,证明所填证明所填 m+n-1 个数对应的变量组不含闭回路个数对应的变量组不含闭回路.用反证法用反证法若含有闭回路若含有闭回路 不妨设此闭回路如右不妨设此闭回路如右（其他情形同理可证）（其他情形同理可证）1 1i jx4 4i jx3 3i

24、 jx2 2i jx 不妨设填不妨设填 后划去行后划去行, ,故故 必须较必须较 先填先填, ,且填后划去的是列且填后划去的是列, ,从而从而 必须较必须较 先填先填, ,且填后划且填后划去的是行去的是行, ,而这又说明而这又说明 必须较必须较 先填先填, ,且填后划且填后划去的是列去的是列, ,这又得到这又得到 必须较必须较 先填先填, ,且填后划去的且填后划去的是行是行, ,这样就得到了矛盾这样就得到了矛盾, ,所以所以, ,填数的填数的 m+nm+n-1 -1 个格个格子对应的变量组不含闭回路子对应的变量组不含闭回路, ,从而从而, ,证得了本定理证得了本定理. . 1 1i jx4 4

25、i jx2 2i jx3 3i jx1 1i jx2 2i jx4 4i jx3 3i jx1 1i jx2021/3/23192 运输问题的表上作业法关键关键1、填一个数字划去一行或一列填一个数字划去一行或一列 不产生闭回路；不产生闭回路； 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、

26、Vogel 法法 ( (元素差额法元素差额法) )规则规则:计算各行各列的最小元素与次小元素的差额计算各行各列的最小元素与次小元素的差额,优先安排差额最大的所优先安排差额最大的所在行或列的单位运价最在行或列的单位运价最小的产地与销地之间的小的产地与销地之间的运输任务运输任务8 23 42 334Vz 2021/3/2320 运输问题二、最优性检验二、最优性检验 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 设设 是平衡运输问题的是平衡运输问题的一组基变量

27、，一组基变量， 是非基变量，则在变量组是非基变量，则在变量组 中存在唯一的闭回路中存在唯一的闭回路.1 12 2,(1)s si ji 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奇顶点偶顶点2021/3/23212 运输问题的表上作业法2、位势法（对偶变量法）位势法（对偶变量法）求检验数的求检验数的方法方法11minmnijijijzc x1. .nijijstxa1,2,im1mijjixb1,2,j

28、n01,2,1,2,ijximjn11minmnijijijzc x1nijijxa2,3,im1mijjixb1,2,jn01,2,1,2,ijximjn111211nxxxa. .st0 x00a x约束方程的系数矩阵的秩为约束方程的系数矩阵的秩为m+n -1x0必为基变必为基变量量, x0= 0约束方程的系数矩阵的秩为约束方程的系数矩阵的秩为m+n对任意的对任意的 a0, 与原问题等价与原问题等价1212,mnyu uuv vv11maxmniijjijaub v10. .1,2,1,2,ijijijstuvcimuajnu v无符号限制由于由于01010ijipmj ijijijcyp

29、1212,ijmnijcu uuv vvpijijcuv001au010000pxj 的检验数的检验数 1jjBjjjcc Bpcyp1 12 2,(1)s si ji ji jxxxsmn设：为基变量，由于基变量设：为基变量，由于基变量的检验数等于零的检验数等于零111 1222 210sss siji jiji jiji juvcuvcuvcua有解有解, ,不唯一不唯一ui 称为行位势称为行位势, ,vj 称为行位势称为行位势2021/3/2322 运输问题ijijcuv BjAi B1 B2 B3 B4 ui A1 4010 25 5 2 5 3 A2 4 3 10 1 10 2 A3

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

31、 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1540102551010 BjAi B1 B2 B3 B4 A1 A2 A3检验数表检验数表-5-10 6 6 6选择进基变量选择进基变量min0,1,1stijijimjn 则取非基变量则取非基变量 xst 为进基变量为进基变量确定出基变量确定出基变量调整量调整量 minijklxx闭回路上偶顶点则基变量则基变量 xkl 出基（运量擦去）出基（运量擦去）调整方法：在该闭回路上，奇点运量加调整方法：在该闭回路上，奇点运量加 ，偶点减去，偶点减去 能转运多少能转运多少?153010 6 5 4 2010 1-5

32、6 520 6 6 4 5 6 因为因为 ，所以此运输方案为最优，所以此运输方案为最优方案方案0ijNote : 若在闭回路上有几个偶点处的运量等于若在闭回路上有几个偶点处的运量等于 , ,则则可任取其中一个作为出基变量（运量擦去）可任取其中一个作为出基变量（运量擦去）, ,其余几其余几个点的值调整后变为个点的值调整后变为0. (0. (但应填入但应填入, ,说明这些变量还说明这些变量还在基内在基内, ,这时就出现了退化这时就出现了退化) )问问: :从从A2到到B4的单位运价的单位运价c24在什么范围变化时在什么范围变化时, ,所得所得最优调运方案不变最优调运方案不变. . c12在什么范围

33、变化呢在什么范围变化呢?2021/3/2324四、四、 踏石法踏石法1)、找入变量、找入变量l从从 中找最小者中找最小者,对应对应 xij 就是入变量就是入变量2)、以、以 非基变量非基变量xij 为起点为起点,寻找由原基变量构成的寻找由原基变量构成的闭合回路闭合回路l该回路只在每个拐角各有一个基变量该回路只在每个拐角各有一个基变量,中间允许穿越某些基变中间允许穿越某些基变量量;因此因此,闭合回路中必有偶数个变量闭合回路中必有偶数个变量(包括包括 xij ),且回路中每行且回路中每行每列只有两个变量每列只有两个变量3)、求入基变量、求入基变量 xij 的最大值及新基变量的解的最大值及新基变量的

34、解l从从 xij出发出发,沿任一个方向对回路拐角上的基变量依此标沿任一个方向对回路拐角上的基变量依此标“ ”和和“+”,表示表示“ ”和和“+” xij ,从而迭代后仍满足分配的平衡从而迭代后仍满足分配的平衡l标有标有“ ”的变量中最小者就是的变量中最小者就是出基变量出基变量,对应对应xij*的值就是所的值就是所求入基变量求入基变量 xij 的最大值。的最大值。l标有标有“ ”的变量减去的变量减去 xij*,标有标有“+”的变量加上的变量加上 xij* 4)、用位势法求新基变量的检验数、用位势法求新基变量的检验数l若所有若所有 ,则达到最优则达到最优,算法停止算法停止; 否则否则返回返回 1）

35、。）。()0ijijijcuv()0ijijijcuv2021/3/2325 补充补充 例题例题 踏石法踏石法, ,以最低费用法所得初始解开始（注意以最低费用法所得初始解开始（注意: :对对基变量基变量x xij ij有有: :c cij ij=u=ui i+v+vj j, ,任取一个任取一个u ui i或或v vj j=0=0, ,计算出计算出u ui i、v vj j) )所有所有 cij (ui+vj) =0,达到最优。达到最优。答答:最优解如上分配表最优解如上分配表,OBJ=98OBJ=121OBJ=1012021/3/2326五、五、 运输问题迭代中的一些具体问题运输问题迭代中的一些

36、具体问题 1 ) 闭合回路的画法闭合回路的画法l从从入基入基变量变量xij出发出发, ,遇到某个基变量则选一个方向拐角遇到某个基变量则选一个方向拐角, ,若不能再若不能再遇到其它基变量遇到其它基变量, ,则返回上一拐角则返回上一拐角, ,换一个方向走换一个方向走, ,采用深探法采用深探法l闭合回路不一定是矩形闭合回路不一定是矩形 2 ) 产销不平衡产销不平衡l供过于求供过于求,即即 ai bj ,增加一个虚收点增加一个虚收点Dn+1,bn+1= ai - bj , 令令 wi,n+1=0, i=1,2,ml供小于求供小于求,即即 ai bj ,增加一个虚发点增加一个虚发点Wm+1,am+1=

37、bj - ai , 令令 wm+1,j=0, j=1,2,n 3 ) 关于退化问题关于退化问题(1)、初始解退化初始解退化。即初始基变量的个数少于。即初始基变量的个数少于m+n 1。必须补足基变。必须补足基变量的个数量的个数,否则不能正常解出否则不能正常解出m+n个个ui和和 vjl所补基变量的值为所补基变量的值为 0 ,补充的原则补充的原则:(1)尽量先选运费小的实变量尽量先选运费小的实变量;(2)补充后不能有某个基变量独占一行一列补充后不能有某个基变量独占一行一列2021/3/2327六、六、 关于退化问题关于退化问题(2)、迭代过程中出现退化迭代过程中出现退化l闭合回路中标有闭合回路中标

38、有“ ”的基变量同时有多个达到最小的基变量同时有多个达到最小l变换后变换后,有多个原基变量变为有多个原基变量变为 0,选运费最大者为出选运费最大者为出基基变量变量,其余其余保留在新的基础解中保留在新的基础解中l退化较严重时退化较严重时,可能会出现多次迭代只有值为可能会出现多次迭代只有值为 0 的基变量在转的基变量在转移。此时移。此时,一要耐心一要耐心,二要正确选择出变量二要正确选择出变量踏石法迭代中需注意的问题踏石法迭代中需注意的问题:(1)、错误地将分配表中基变量的解代入到运费表中、错误地将分配表中基变量的解代入到运费表中(2)、不能正确画闭合回路、不能正确画闭合回路(3)、初始解退化初始解

39、退化,未能补足基变量的个数未能补足基变量的个数。因此在位势法中。因此在位势法中多次令某个多次令某个ui或或 vj为为 0;(4)、在位势法中只能令一个在位势法中只能令一个 ui 或或 vj 为为 0;若不能求出全部若不能求出全部 ui和和 vj ,说明基变量未选够数或未选对说明基变量未选够数或未选对2021/3/2328 运输问题七、七、 补充补充:运输问题的图上作业法运输问题的图上作业法 图上作业法是在交通图上进行物资调运方案编制和图上作业法是在交通图上进行物资调运方案编制和调整的一种科学方法。在铁路特别是公路运输中使用很调整的一种科学方法。在铁路特别是公路运输中使用很多且有很好的效果。多且

40、有很好的效果。 在交通图中在交通图中, ,用用表示表示产地（发点）产地（发点）, ,并将产量记并将产量记在圆圈内在圆圈内; ;用用表示销地表示销地（收点）（收点）, ,并将销量记在方并将销量记在方框内。框内。206040402463目标目标: :吨公里数吨公里数( (费用费用) )最小的调运方案最小的调运方案 . . 物资调运的流向用与交通线平行的箭线表示物资调运的流向用与交通线平行的箭线表示,规定规定画在前进方向的右边画在前进方向的右边,调运量加括号记在箭线的右边。调运量加括号记在箭线的右边。(20)(20)(40)2021/3/2329补充:运输问题的图上作业法20303020243对流对

41、流:物资在同一线路上往返运输物资在同一线路上往返运输.(20)(20)(30)(30)(10)这是对流这是对流20303020243(20)(20)(30)(30)106030(10)(20)1、无圈无圈的交通的交通图图2020502010 对于无圈图对于无圈图,每条每条边都是割边边都是割边,去掉它网去掉它网络将不连通络将不连通,所以所以,每每条边上的运量是不得不条边上的运量是不得不只要每条边上不产生对流只要每条边上不产生对流,即为最优方案即为最优方案2021/3/2330 运输问题206040402463(20)(20)(40)2、有一个圈的交通图有一个圈的交通图圈长圈长:圈上每一条边的长度

42、之和（记为圈上每一条边的长度之和（记为 l）l =15 先用先用“丢边破圈丢边破圈”方法方法,得到无圈图得到无圈图,再产生一个再产生一个没有对流的方案。没有对流的方案。内圈长内圈长 l内内:流向在圈内的边的长度之和流向在圈内的边的长度之和l内内= 8外圈长外圈长 l外外:流向在圈外的边流向在圈外的边的长度之和的长度之和l外外= 4是最优解码是最优解码?8,2ll 内不是最优的.称为迂回称为迂回调整方案调整方案:对内圈各流量中最小调运量对内圈各流量中最小调运量,进行反向调运进行反向调运(40)(20)(20)结论结论: :内外圈长都小于圈长的一半的无对流的调运方案内外圈长都小于圈长的一半的无对流

43、的调运方案 为最优方案为最优方案67.22llll外内此时为最优调运方案2021/3/2331补充:运输问题的图上作业法3、有多个、有多个圈圈的交通的交通图图106030202050203020有几个圈? 如有一个圈的情形如有一个圈的情形,对每一个圈先用对每一个圈先用“丢边破圈丢边破圈”方方法法,得到无圈图得到无圈图,再产生一个没有对流的方案。再进行再产生一个没有对流的方案。再进行检查、调整。检查、调整。只需检查13个圈吗?会循环吗? 一般不够一般不够!因为对一个圈进行调整后因为对一个圈进行调整后,会对已检会对已检查的圈有影响查的圈有影响. 不会不会!因为每次目标因为每次目标函数下降值大于一个

44、固定函数下降值大于一个固定值（如值（如 1）2021/3/2332 运输问题4、产销不平衡运输问题、产销不平衡运输问题当当11mnijijab111minmnijijijzc x1. .nijijstxa1,2,1im m11mijjixb1,2,jn01,2,1;1,2,ijxim mjnNote : 通常建立运输模通常建立运输模型指的是平衡运输模型型指的是平衡运输模型可以虚设一个产地可以虚设一个产地 Am+1, 其产量为其产量为111nmmjijiaba 并假设产地并假设产地 Am+1 运往各销地的单运往各销地的单位运价为位运价为 cm+1, j = 0 ( j = 1 , 2 , , n

45、 ) . 则原问题可转则原问题可转化为平衡运输问题化为平衡运输问题: 产大于销产大于销,可通可通过虚设销地过虚设销地,类似类似建立平衡运输模型建立平衡运输模型2021/3/23332 运输问题的表上作业法Ex. 2已知运输问题由表给出已知运输问题由表给出,试建立运输模型试建立运输模型 . Bj Ai B1 B2 B3 ai A14 25 10 A2638 15 bj 8 7 14解解: Bj Ai B1 B2 B3 ai A14 25 10 A2638 15 A3000 4 bj 8 7 14本题产量为本题产量为25, ,销量为销量为29,是销大于产问题是销大于产问题 虚设一个产地虚设一个产地

46、 A3, ,由于并没有生产由于并没有生产, ,所以运价为所以运价为零零, ,得运输模型得运输模型. . 如果各销地不满足时如果各销地不满足时, ,单位缺货费为单位缺货费为 4,3,7, ,则则运输模型为运输模型为4372021/3/2334 运输问题 BjAi B1 B2 B3 ai A14 23 10 A2564 15 A3345 20 最低最低需求量需求量 10 10 10Ex. 3 已知运输问题由表给出已知运输问题由表给出,如果产地如果产地 Ai 的产量的产量必须运走必须运走, ,试建立运输模型试建立运输模型 . BjAi B1 B2 B3 B4 ai A14 23 10 A2564 1

47、5 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 A3345 20 bj 10 10 10 443B3B15351015A4M100MM0 三个销地的最低需求为三个销地的最低需求为 30,最高需求不限最高需求不限. . 根据根

48、据现有产量现有产量, ,B3 至多能得到至多能得到 25. 建立运输模型建立运输模型 .2说明什么说明什么? ?2021/3/2335 运输问题3 运输问题应用举例运输问题应用举例Ex. 4 (生产调度问题生产调度问题) 某制冰厂每年某制冰厂每年1 4 季度必须供季度必须供应并块应并块 15、20、25、10（千吨）（千吨）. .已知该厂各季度冰已知该厂各季度冰 块的生产能力及冰块的单位成本如表块的生产能力及冰块的单位成本如表. . 如果生产出来如果生产出来的冰块不在当季度使用的冰块不在当季度使用, ,每千吨冰块存储一个季度每千吨冰块存储一个季度费用为费用为4（千元）（千元）. .又设该制冰厂

49、每年第又设该制冰厂每年第3季度末对贮季度末对贮冰库进行清库维修冰库进行清库维修. .问应如何安排冰块的生产问应如何安排冰块的生产, ,可使可使该厂全年生产、该厂全年生产、存储费用最少存储费用最少? ?季季 度度 生产能力（千吨）生产能力（千吨） 单位成本（千元）单位成本（千元） 1 25 5 2 18 7 3 16 8 4 15 52021/3/23363 运输问题应用举例季季 度度 生产能力（千吨）生产能力（千吨） 单位成本（千元）单位成本（千元） 1 25 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

50、 bj 15 20 25 10 解解:5B54913M0MMMMM00051181791372021/3/2337 运输问题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 的运量不能超过的运量不能超过 dij , , 由表由表 2 2 给定给定. . 试建立运输问题试建立运输问题 . .解解: 虚设虚设 Dij

51、(i=1,2; j=1,2,3) 6 6个点个点, ,Dij 既作产地既作产地, ,又作销地又作销地, ,其产量、销量都为其产量、销量都为 dij . . 产地产地 Ai 的物资只可的物资只可运送给运送给 Dij , 而而 Dij 的物资只可运送给的物资只可运送给 Bj ,或送给自身或送给自身.2021/3/23383 运输问题应用举例 BjAi D11 D12 D13 D21 D22 D23 B1 B2 B3 ai A1 D11 D12 D13 A2 D21 D22 D23 bj 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 8 1043300003050400002060743342542575633213031242442142021/3/2339 运输问题Ex. 6 ( (空车调度问题空车调度问题) ) 某航运公司承担六个港口城市某航运公司承担六个港口城市 A、B、C、D、E、F 的四条固定航线的物资运输任的四条固定航线的物资运输任务务. . 已知各条航线的起点、终点城市及每天航班数见已知各条航线的