运筹学 第四章 运输问题

《运筹学 第四章 运输问题》由会员分享，可在线阅读，更多相关《运筹学 第四章 运输问题（116页珍藏版）》请在文档大全上搜索。

1、运输问题v运输问题及其数学模型v运输问题的表上作业法v运输问题的进一步讨论例1：某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点（销地）出售，各工厂的生产量、各销售点的销售量（假定单位均为t）以及各工厂到各销售点的单位运价（元/t）示于下表中要求研究产品如何调运才能使总运费最小 4.1 运输问题及其数学模型单位 销地 运价产地产量2910291342584257销量38464321 BBBB321AAAA2A3B2A1B3B4B1s2=5s3=7d1=3d2=8d3=4d4=6s1=9供应量供应地运价需求量需求地2910213428425运输问题网络图运输问题网络图 )4 . 3

2、 . 2 . 1, 3 . 2 . 1(06483759524824371092min342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZxijij 约约束束条条件件：目目标标函函数数：为为运运量量设设产量约束销量约束运输问题的一般提法是：设某种物资有 个产地m,1A,2A,mA各产地的产量是;,21maaa有 个销地,1B,2B,nBn各销地的销量是.,21nbbb假定从产地 ), 2, 1(miAi到销地), 2 , 1

3、(njBj运输单位物品的运价是 ，问ijc怎样调运这些物品才能使总运费最小？ 销地产地产量销 量1A2AmA1B2BnB11c12cnc111x12xnx121c22cnc221x22xnx21mc2mcmnc1mx2mxmnx1b2bnb1a2ama运价表 ) ( 0min11ijjijijiijminjijijxbabxaxxcZ当产销平衡时，其模型如下：0,0,0ijijabc假设：当产大于销时，其模型是： ) ( 0min11ijjijijiijminjijijxbabxaxxcZ当产小于销时，其模型是：min ()0ijijijiijjijijZc xxaxbabx 1 1、平衡运输

4、问题必有可行解，也、平衡运输问题必有可行解，也必有最优解；必有最优解；运输问题数学模型的特点运输问题数学模型的特点证明 记.11dbaminjji则令dbaxjiij), 2 , 1;, 2 , 1(njmi则 为运输问题的一个可行解。事实上：ijxnjijinjnjjiijabdadbax111), 2 , 1(mimijijmimijiijbadbdbax111), 2 , 1(nj又因. 0, 0jiba所以. 0ijx故 是一组可行解。ijx又因为总费用不会为负值（存在下界）。这说明，运输问题既有可行解，又必然有下界存在，因此一定有最优解存在。 2 2、运输问题约束条件的系数矩阵、运输

5、问题约束条件的系数矩阵运输问题数学模型的特点运输问题数学模型的特点对运输问题数学模型的结构约束加以整理，可知其系数矩阵具有下述形式：m行n行1运输问题是一个具有mn个变量和n+m个等型约束的线性规划问题。 （41）mnmmnnxxxxxxxxx,;,212222111211jmiijeep), 2 , 1;, 2 , 1(njmi() 1() 1() 1000110000101000ijimjmnmnmnpee2运输问题约束方程组的系数矩阵是一个只有0和1两个数值的稀疏矩阵,其中1的总数为 2mn 个。3、约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在

6、后n个约束方程中也出现一次4、约束条件系数矩阵的秩是m+n-1。即运输问题的基变量总数是m+n-1证明：因A的前m行对应元素的和与后n行对应元素的和相等，恰好都是：nmE) 1 , 1 , 1 (1所以A的行向量是线性相关的。从而 r(A)m+n.去掉A的第一行，并取如下m+n-1列，得到m+n-1阶子式1112121311|00010000001000000110100111010000001000nmDp pp ppp 所以 r(A)=m+n-1.对于产销平衡运输问题，除了上述特点外，还有以下特点： 1 所有结构约束条件都是等式约束 2 各产地产量之和等于各销地销量之和 3 3、运输问题的

7、解、运输问题的解运输问题数学模型的特点运输问题数学模型的特点运输问题是一种线性规划问题。前面讲述的单纯形法是求解线性规划问题十分有效的一般方法，因而可用单纯形法求解运输问题。但是当用单纯形法求解运输问题时，先得在每个约束条件中引入一个人工变量，这样一来，即使对于m=3、n=4这样简单的运输问题，变量数目也会达到19个之多。因此，我们利用运输问题数学模型的特点，引入了表上作业法来求解运输问题 4.2 用表上作业法求解运输问题表上作业法的基本思想：先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如下图所示。初始化最优性检验迭代（Iteration）最

8、优？yesSTOPno这和单纯形法的求解思想完全一致，但是具体的作法则更加简捷。例1 某部门有3个同类型的工厂（产地），生产的产品由4个销售点出售，各工厂的生产量、各销售点的销售量（假定单位为t）以及各工厂到销售点的单位运价（元/t）示于表4-2中，问如何调运才能使总运费最小？ 销地产地产量4124111621039108511622销 量8141214481A2A1B2B3B4B3A表 4-211x12x13x14x21x22x23x24x31x32x33x34x34333231242322213141141312116115893102114124minxxxxxxxxxxxxxcziji

9、jij4 , 3 , 2 , 1; 3 , 2, 1, 01412148221016342414332313322212312111343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxij该运输问题的数学模型为：可以证明：约束矩阵的秩 r (A) = m +n -1.基变量的个数为 m+n-1.表上作业法v计算步骤：1、给出初始方案2、检验是否最优3、调整调运方案 , Go to 2表上作业法v计算步骤：1、给出初始方案2、检验是否最优3、调整调运方案 , Go to 2下面介绍三种常用的方法。一、给出运输问题的初始可行解（初始调运方案）l最小

10、元素法l西北角法l沃格尔(Vogel)法1。最小元素法思想：优先满足运价（或运距）最小的供销业务。 销地产地产量 4124111610398511622销 量141214481A2A1B2B3B4B3A表 3-2228810 销地产地产量 412411162109108511622销 量 81414481A2A1B2B3B4B3A表 3-23210128 销地产地产量 412112109108511622销 量 8141214481A2A1B2B3B4B3A表 3-232104161068 销地产地产量 4121182109108116销 量 81214481A2A1B2B3B4B3A表 3-

11、2321041610651422148 销地产地产量 412118210910811销 量 812481A2A1B2B3B4B3A表 3-23210416106514221486146 销地产地产量 4128210910811销 量 812481A2A1B2B3B4B3A表 3-2321041610651422148614611此时得到一个初始调运方案（初始可行解）：,1013x, 614x, 821x, 223x,1432x, 834x其余变量全等于零。总运费为（目标函数值）3141ijijijxcz246685143228116410此解满足所有约束条件，且基变量（非零变量）的个数为6（等