运输问题的数学模型和应用举例

1、运输问题的数学模型和应用举例运输问题的数学模型表上作业法产销不平衡的运输问题运输问题应用举例 运输问题（Transportation Problem，简记为TP）是一类常见而且极其特殊的线性规划问题.它最早是从物资调运工作中提出来的，是物流优化管理的重要的内容之一 。 从理论上讲，运输问题也可用单纯形法来求解，但是由于运输问题数学模型具有特殊的结构，存在一种比单纯形法更简便的计算方法 表上作业法，用表上作业法来求解运输问题比用单纯形法可节约计算时间与计算费用.但表上作业法的实质仍是单纯形法。 1.1 产销平衡运输问题的数学模型1 运输问题的数学模型及其特点 设某种物资共有 m 个产地 A1，A

2、2，Am，各产地的产量分别是a1，a2 ，am；有n 个销地 B1，B2，Bn ，各销地的销量分别为b1 ，b2，bn . 假定从产地Ai（i =1，2，m）向销地Bj（j =1，2，n）运输单位物资的运价是cij ，其中 .问怎样调运才能使总运费最小？ 设 xij 表示产地 Ai 运往销地 Bj (i=1,2,m; j=1,2,n) 的运量. 销地产地 B1 B2 Bn产量 A1 x11c11 x12c21 x1n c1n a1 A2 x21c21 x22c22 x2nc2n a2 Am xm1cm1 xm2cm2 xmncmn am销量 b1 b2 bn 运输表注意 : cij 在左下角

3、xij 在右上角 1.2 运输问题数学模型的特点平衡运输问题的约束方程系数矩阵 A矩阵A有m+n行，每行的特点：前m行有n个1，这n个1连在一起，其余元素为0；后n行每行有m个1，其余元素为0。矩阵A有mn列，每一列只有两个元素为1，其余元素均为0。列向量Pij =(0,，0，1，0，,0,1,0,0)T，其中两个元素1分别处于第i行和第m+j行,即将矩阵A分块，特点是：前m行构成m个mn阶矩阵,而且第k个矩阵只有第k行元素全为1，其余元素全为0（k=1，m）；后n行构成m个n阶单位阵。其中e1是元素全为1的n维行向量，In为n阶单位矩阵。定理 1 平衡运输问题必有可行解，也必有最优解. 又因

4、为 ，对于任一可行解有目标函数值 ，对于求极小化问题，目标函数值有下界，则必有最优解. 证明:则取又所以 ，是问题的一个可行解. 证明：定理2 说明：基可行解包含m+n-1个基变量.定理 2 平衡运输问题的约束方程系数矩阵 A 和增广矩阵 的秩相等，且等于 m+n-1 . 即 2. 由 的第二至m+n行和前n列及 对应的列交叉处元素构成m+n-1阶方阵D 非奇异。前m行相加之和减去后n行相加之和结果是零向量，说明m+n个行向量线性相关，因此 的秩小于m+n； 证明系数矩阵A及其增广矩阵的秩都是m+n-1 因此 的秩恰好等于m+n-1，又D本身就含于A中，故A的秩也等于m+n-1 可以证明：m+

5、n个约束方程中的任意m+n-1个都是线性无关的。定理 3 平衡运输问题的约束方程系数矩阵 A 的所有各阶子式只取 0，1 或 -1 三个值.定理 4 如果平衡运输问题中的所有产量 ai 和销量 bj都是整数，那么，它的任一基可行解都是整数解.Proof :设 x 是 Ax = b 的任一基可行解，B 为对应的基矩阵，则 其中 Bt 是用 b 中对应的 m+n-1元素替换 B 的第t 列元素得到的矩阵. 显然，由定理 3 知，det Bt 是个整数， det B= ，因此， 都是整数.其基变量为定理 4 如果平衡运输问题中的所有产量 ai 和销量 bj都是整数，那么，它的任一基可行解都是整数解.

6、定义 1 将变量 在调运表中所对应的空格记作 ，下文将称为格点 或格 ，而 的系数列向量 也称作格点 所对应的系数列向量，若 为基变量，则 称为基格，否则是非基格。 凡是能排列成（其中 互不相同， 互不相同）形式的变量集合，称为一个闭回路，其中诸变量称为这个闭回路的顶点.定义 2 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如：变量集合变量集合或格组或格组3、每一行（或列）若有闭回路的顶点，则有两个顶点；4、每两个顶点格子的连线

7、都是水平的或垂直的；1、闭回路中顶点的个数必为大于或等于4的偶数.闭回路的几何特征：2、每一个顶点格子都是 90转角点； 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思考： 下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？为什麽？（a） （b） （c） （d） （e）闭回路的代数性质：性质 1 构成闭回路的变量组对应的列向量组必线性相关.证明由直接计算可知故该向量组线性相关.性质 2 分组构成闭回路，则该变量组对应的列

8、向量组是线性相关的.推论 1 若变量组对应的列向量组线性无关，则该变量组一定不包含闭回路.若变量组 中有一个部性质2的证明可借助性质1和高等代数中“若向量组中部分向量线性相关，则整个向量组就线性相关”的定理得到。在变量组 中，若有某一个变量 xij 是它所在的行（第 i 行）或列（第 j 列）中出现于（*）中的唯一变量，则称该变量 xij 是该变量组的一个孤立点.定义 3闭回路的特征注：孤立点不会是闭回路上的点。 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

9、x42 x43 x44 x45性质 3 若一变量组中不包含任何闭回路，则该变量组必有孤立点.注：性质3的逆命题不一定成立。变量组 中虽有孤立点 ，但包含闭回路 。证明 :用反证法设变量组（*）对应的列向量组线性无关，但该变量组包含一个以其中某些变量为顶点的闭回路，则由性质 2 知，这些变量对应的列向量必线性相关，与假设矛盾.定理 5 变量组 对应的列向量组线性无关的充要条件是该变量组中不包含任何闭回路.设有一组数 使得 由于变量组（*）中不包含任何闭回路，由性质 3 可知其中必有孤立点，不妨设 为孤立点，但 仍不包含闭回路，其中还有孤立点,与前面类似分析可证 k2= 0. 同理得 k3 = k

10、4 = kr = 0这就证明了向量组（*）线性无关.又不妨设 是（*）在第i1行上唯一的变量，这时由pij的特征，（1）的左端第i1个分量和为k1，而右端为0，推论 2 平衡运输问题中的一组 m + n - 1 个变量能构成基变量的充要条件是它不包含任何闭回路. 该推论给出了运输问题的基可行解中基变量的一个基本特征：基变量组不含闭回路. 这就是基可行解在表上的一个表现，利用它来判断 m + n 1 个变量是否构成基变量组，就看它是否包含闭回路.这种方法简便易行，它比直接判断这些变量对应的列向量是否线性无关要简便得多. 利用基变量的这个特征，将可以导出求平衡运输问题的初始基可行解的一些简便方法.

11、 表上作业法（又称运输单纯形法）是根据单纯形法的原理和运输问题的特点，设计的一种在表上运算的求解运输问题的简便而有效的方法.2 表上作业法主要步骤：1、求一个初始调运方案（初始基可行解）；2、判别当前方案是否为最优，若是则迭代停止，否则 转下一步；3、改进当前方案，得到新的方案（新的基可行解）， 再返回 2 。 已知某商品有三个产地A1、A2、A3和四个销地B1、B2、B3、B4 ，产量、销量及单位运价如表.问应如何调运，在满足各销地需要的情况下，使总的运费支出为最少？ 一、初始方案的确定1、西北角法 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 2

12、0 A3 5 6 3 4 10 bj 50 25 10 15例 1 50解：51010205规则:从运输表的西北角开始,优先安排编号小的产地和销地的运输任务.填了几个数字？注意 : 在填入一个数时，如果行和列同时饱和， 规定只划去一行或一列 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 15500 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 15505101020550例1的初始调运方案（西

13、北角法）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规则:优先安排单位运价最小的产地与销地之间的运输 任务，即就近供应。40102551010注意 : 在某行（或列）填入一个数时，如果行和列同时饱和，规定只划去该行（或列） 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填了几个数字？定理 6 用西北角法或最小元素法得到的初始解是平衡运输问题的基可行

14、解， m+n-1 个填入数字的格子对应的是基变量.证明 :首先，得到的初始解 为可行解是显然的. 其次，由于行列数共有 m+n ，而按填数字的方法,除填最后一个数时，划去一行一列外，每填一个数划去一行或一列. 因此, 共填 m+n-1 个数. 最后，证明所填 m+n-1 个数对应的变量组不含闭回路.用反证法若含有闭回路 不妨设此闭回路如右（其他情形同理可证） 不妨设填 后划去行，故 必须较 先填，且填后划去的是列，从而 必须较 先填，且填后划去的是行，而这又说明 必须较 先填，且填后划去的是列，这又得到 必须较 先填，且填后划去的是行，这样就得到了矛盾，所以，填数的 m+n-1 个格子对应的变

15、量组不含闭回路，从而，证得了本定理. 关键1、填一个数字划去一行或一列 不产生闭回路； 2、填一个数字只划去一行或一列 填满m+n-1个数. BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 315按最小元素法3、伏格尔法 (元素差额法) 最小元素法的缺点：为了节省一处的费用，有时造成在其它处要花几倍的运费。所以我们考虑若一产地的产品不能按最小运费就近供应，就考虑次小运费，这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加越多。 因而，对差额最大处，就优先采用最小运费调运，这就是伏格尔法的基本思想 BjAi B1 B2 ai A1 8 2 5 A2 3 1

16、 4 bj 6 3 差额 6 2 差额 5 1315 BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 342注：伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。优先安排差额最大的所在行或列的单位运价最小的产地与销地之间的运输任务规则：计算各行各列的最小元素与次小元素的差额， 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 155052040例1的初始调运方案（伏格尔法）101510二、最优性检验定理 7 设 是平衡运输问题的一组基变量， 是非基变量，则格

17、组 中必存在唯一的闭回路.证明 : （1）存在性：设与变量组 所对应的系数列向量组为 ，则它们一定线性相关，据定理5 ，变量组 所对应的格子组必包含闭回路，而且这个闭回路必包含非基变量 所对应的非基格 。否则，就说基格组（或一部分）构成了闭回路，这与基的定义和定理5相矛盾。（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

18、10 15401025510101、闭回路法+1-1+1-1 BjAi B1 B2 B3 B4 A1 A2 A3检验数表-5-10 6 6 6检验数检验数 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+1-1+1-1闭回路的经济解释:在已给出的初始解的表中，可以从任意一个空格出发，如 ，若让 的产品调运1个单位给 ，为了保持产销平衡，就要依次调整：在 处减少一个单位，在 处增加一个单位，在 减少一个单位，即构成了以空格 为起点，其它为数字格的闭回路。可见这样调整得运

19、费的改变量为：2、位势法（对偶变量法）约束方程的系数矩阵的秩为m+n -1由于xj 的检验数 ui 称为行位势，vj 称为列位势解上面第一个方程，将ui、vj代入第二个方程求出 。 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-2-120273见 例 1 最小元素法得到的初始基可行解10053-12-5 若 ，则此时的运输方案为最优的 定理 8 检验数 与初始给定 的取值无关。 （下面的证明摘自教材最优化方法书后参

20、考文献1）证明： 引理1 引理2 由此定理可知，我们用位势法求检验数时给定初始的Vn=0是合理的，从而计算出的ij 是唯一的。三、基可行解的改进 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 B1 B2 B3 B4 A1 A2 A3检验数表-5-10 6 6 6选择进基变量则取非基变量 xst 为进基变量确定出基变量调整量则基变量 xkl 出基（运量擦去）调整方法：在该闭回路上，奇点运量加 ，偶点减去 153010 6 5 4 2010 1-5 6 520

21、 6 6 4 5 6 因为 ，所以此运输方案为最优方案 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 1550252020例1的最优调运方案101510model:!3发点4收点产销平衡的运输问题;sets: cd/1.3/: capacity; xd/1.4/: demand; links(cd,xd): cost, variable;endsets!目标函数; min=sum(links: cost* variable);!需求约束; for(xd(j): sum(cd(i): varia

22、ble(i, j)=demand(j);!产量约束; for(cd(i): sum(xd(j): variable(i, j)=capacity(i);!这里是数据;data: capacity= 70 20 10 ; demand=50 25 10 15;cost= 10 5 2 3 4 3 1 2 5 6 3 4;enddataend求解例1的lingo源代码求解例1的lingo输出报告练习1 某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。产销

23、平衡表见表1。已知从各工厂到各销售点的单位产品的运价为表2所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。 表1 产销平衡表表2 单位运价表 BOOK P122 例例表3 最优调运方案表4 检验数表所以调运的总运费最小是85元。解：求初始基本可行解时，当minai,bj=ai=bj 时，此时要同时划去第i行及第j列，为了确保调运表上仍有m+n-1个基变量的取值，需要在所划去的第i行或第j列任一空格上加0,表示这个格中的基变量的取值是0，这样就出现了退化解。 若在闭回路上有几个偶点处的运量等于，则可任取其中一个作为出基变量（运量擦去），其余几个点的值调整后变为0，但应

24、填入，说明这些变量还在基内，这时就出现了退化。(1)有无穷多最优解.最终解中有非基变量检验数为零时，以此非基变量为换入变量，可求得另一基最优解。基最优解的任一凸组合都是最优解。 BOOK P136 例表上作业法计算中的两个问题(2)退化解.解中非零基变量个数小于m+n-1时，为退化解。一般在下面两种情况下出现： BOOK P138 例1.4.5+例设数学模型为 关于极大化运输问题的求解例2 下列矩阵C是Ai到Bj的吨公里利润, 产量、销量及其单位利润合并于下表，问运输部门如何安排运输方案使总利润最大？ cij BjAi B1 B2 B3 ai A12 58 9 A29107 10 A3654

25、12 bj 8 14 9方法I：将极大化问题转化为极小化问题。设极大化问题的运价表为C=（cij）mn，用一个较大的数M（Mmaxcij）去减每一个cij得到矩阵C/=（c/ij）mn ，其中c/ij=Mcij0， 将C/作为极小化问题的运价表，用表上作业法求出最优解，目标函数值为： cij BjAi B1 B2 B3 ai A12 58 9 A29107 10 A3654 12 bj 8 14 9 BjAi B1 B2 B3 ai A1 8 5 2 9 A21 03 10 A3 4 5 6 12 bj 8 14 9用最小元素法求初始运输方案910840 BjAi B1 B2 B3 A1 8

26、4 A2 2 2 A3检验数表 由于检验数全部非负,因此该初始运输方案也是最优运输方案, 则最大利润为： Z=89+1010+68+54=240方法II: 所有非基变量的检验数ij0时最优.求初始运输方案可采用最大元素法.如上例,用最大元素得到的初始运输方案:8 14 9求检验数:11=8,12=4,21=2,23=2,全部非正,得到最优解运输方案,结果与第一种方法相同.当当3 产销不平衡的运输问题当可以虚设一个产地 Am+1, 其产量为 并假设产地 Am+1 运往各销地的单位运价为 cm+1, j = 0 ( j = 1 , 2 , , n ) . 则原问题可转化为平衡运输问题： 产大于销，

27、可通过虚设销地，类似建立平衡运输模型例3已知运输问题由表给出，试建立运输模型 . 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，是销大于产问题 虚设一个产地 A3，由于并没有生产，所以运价为零，得运输模型. 如果各销地不满足时，单位缺货费为 4，3，7，则运输模型为437 已知运输问题由表给出，如果产地 Ai 的产量必须运走，试建立运输模型 . BjAi B1 B2 B3 ai A14 23 10 A2564

28、 15 A3345 20 最低需求量 10 10 10例4 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 A3345 20 bj 10 10 10 443B3B15351015A4M100MM0 三个销地的最低需求为

29、30，最高需求不限. 根据现有产量，B3 至多能得到 25. 建立运输模型 .练习2 设有三个化肥厂(A，B，C)供应四个地区(，)的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如表1所示。试求出总的运费最节省的化肥调拨方案。BOOK P145 例解：这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，第个地区每年最多能分配到60万吨，这样最高需求为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个假想的化肥厂D，其年产量为50万吨。由于各地区的需要量包含

30、两部分，如地区，其中30万吨是最低需求，故不能由假想化肥厂D供给，令相应运价为M(任意大正数)，而另一部分20万吨满足或不满足均可以，因此可以由假想化肥厂D供给，按前面讲的，令相应运价为0。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以写出这个问题的产销平衡和单位运价表(表2)。产销平衡表和单位运价表合并于下面的表2根据表上作业法计算，可以求得这个问题的最优方案如表3所示 某制冰厂每年1 4 季度必须供应冰块 15、20、25、10（千吨）.已知该厂各季度冰 块的生产能力及冰块的单位成本如表. 如果生产出来的冰块不在当季度使用，每千吨冰块存储一个季度费用为4（千元）.又设该制冰

31、厂每年第3季度末对贮冰库进行清库维修.问应如何安排冰块的生产，可使该厂全年生产、存储费用最少？4 运输问题应用举例例 5 (生产调度问题)季 度 生产能力（千吨） 单位成本（千元） 1 25 5 2 18 7 3 16 8 4 15 5季 度 生产能力（千吨） 单位成本（千元） 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 bj 15 20 25 10 解：5B54913M0MMMMM0005118179137 某航运公司承担六个港口城市 A、B、C、D、E、F 的四条固定航线的物资运输任务.

32、已知各条航线的起点、终点城市及每天航班数见表1，假定各条航线使用相同型号的船只，又各城市间的航程天数见表2.例6(空车调度问题) 又知每条船只每次装卸货的时间各需一天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求？航线起点城市终点城市每天航班数1ED32BC23AF14DB1表1 到从ABCDEFA0121477B1031388C23015557851703F7852030表2解：该公司所需配备船只分两部分.1、载货航程需要的周转船只数航线起点城市终点城市每天航班数1ED32BC23AF14DB1表1 到从ABCDEFA0121477B1031388C2

33、3015557851703F7852030表2 如航线1，在港口E 装货1 天，E 至 D 航程17天，在D 卸货1天，总计19天. 每天3 航班，故该航线周转船只需57条.航线装货天数航程天数卸货天数小计航班数需周转船只数11171193572131521031719194113115115累计共需周转船只数91条.2、各港口间调度所需船只数港口城市每天到达每天需求余缺数A01-1B12-1C202D312E03-3F101 港口每天到达与需要的船只不同，如表.为使配备船只数最少，应做到周转的空船数为最少. 建立运输模型，C、D、F 为空船的产地，A、B、E 为销地，单位运