产销不平衡运输问题及算法毕业论

1、2012届毕业生毕业论文题 目: 产销不平衡的运输问题及算法 院系名称： 理学院 专业班级： 信计F0801 学生姓名： 刘景 学 号： 200848490110 指导教师： 林浩 教师职称： 副教授 2012年5月25日摘 要产销不平衡的运输问题及算法摘要：传统的产销平衡运输模型，为人们解决运输问题准备了原始的基本思路。而实际生产生活运输中，产量和销量是不确定的，企业在考虑自身成本时，都会有一个生产量的最低限制。本文就是围绕产销不平衡运输问题的数学建模及其处理和求解展开探讨的，并用例子进行证明和探讨，建立数学模型，转化成产销平衡问题，用表上作业法求解，满足实际需求并获得最大利润。在这篇论文中

2、，我掌握了运输问题的基本概念及其数学模型，以及求解方法。表上作业法是求解运输问题的一种既简单又非常重要的求解方法，并且掌握了表上作业法的基本方法。通过这篇文章我理解运输问题其实也是一种特殊的线性规划问题，求解线性规划问题的基本方法是单纯形法，而运输问题的求解方法和求解线性规划的单形法没有本质区别。关键词： 线性规划 ；产销不平衡 ；运输问题 ；表上作业法 ；Abstract: the traditional production and marketing transport model for people to balance the transportation problem for

3、the basic thought of the original. And the actual production and life in transportation production and sales volume is not affirmatory, the enterprise is in itself when considering the cost will be the lowest limit production. This paper is the production and transportation problem around the balanc

4、e of mathematical modeling and the processing and the solving discusses, examples proved and discussed, the mathematical model, production and marketing into a balance, table-manipulation method is used, meet the practical needs and obtain the biggest profit. In this paper, I have mastered the basic

5、 concept of the transportation problem and its mathematical model, and the solving method, the method of solving the homework table of transportation problem is a simple and very important solution method, and mastery of the basic method of processing. Through this article I understand transportatio

6、n problem is actually a special kind of linear programming, and solve the linear programming problem is the basic method of the simplex method, and the method of calculating the transportation problem and solve the linear programming method of single form is essentially no difference.essay presents

7、the solution and the solving to a category of mathematic model about transportation problems. Example patterns are provided.Keywords: the linear programming ；the transportation problem of production not as marketing ；the transportation problem ；the simplex method目录引言5正文6一、产销平衡运输问题61，平衡运输问题到数学问题6（1）平

8、衡运输问题简介6（2）平衡运输问题数学模型62，表上作业法求解平衡运输问题7(1),确定初始基可行解9(2)最优解的判别11(3)闭回路调整法13二、产销不平衡运输问题141，生产大于销售15（1），产大于销转化为产销相等15（2），产大于销问题解决应用举例162，供不应求17（2），供不应求转化为供需相等17（2），供不应求问题解决应用举例18结论20致谢21参考文献22引言在传统的农业社会，不存在对运输和货物流动的需求。进入现代社会，随着制造业、服务业的发展以及人们生活水平的提高，有了资源、制造产地和市场这三者的区位关系。因此，交通运输在整个经济发展中有着非常巨大的影响。根据运输距离、运输

9、工具、运输环节、运输时间、运输费用等要素合理化货物运输，最后达到减少动力投入、增加运输能力、减少运输费用的综合目的，这就是要解决的交通运输问题。本课题专门研究有多个生产地和有多个销售地的企业产销不平衡的运输问题及算法，因为，在实际生产生活中的运输过程，产量和销量的不确定导致产销不平衡现象越来越明显，往往存在的情况是产大于销或者供不应求。本课题先讨论产销平衡时的运输问题,再讨论产销不平衡时怎样控制运输成本来提高企业的竞争力和经济效益。产销平衡时的运输问题。表上作业法是单纯形在求解产销平衡运输问题的一种既简单又非常重要的求解方法。因为，运输问题是线性规划问题，可以用线性规划中的单纯形法来解决，但是

10、，有两个运输问题的特点使我们不得不设计出他的特殊解法表上作业法。表上作业法，实质上也还是单纯形法，有三个基本步骤。一、确定一个初始可行调运方案。产销平衡问题始终存在可行解，确定初始基本可行解的方法很多，一般用最小元素法、西北角法、vogel法；二、检验当前可行方案是否最优。表上作业法是用闭回路法和位势法来处理这个问题的；三、方案调整。若检验数上有空格的检验数为负，则可改进方案，降低成本。产销不平衡时的运输问题及算法。产销不平衡时怎样控制运输成本来提高企业的竞争力和经济效益。主要思想是把产销不平衡问题转化为产销平横问题进行研究。产量大于销量时，虚拟出一个假想销地，使产销平衡，各个产地到假想销地的

11、运价为零；供不应求时，假想出一个产地，使产销平衡，假想产地到各个销地的运价为零。然后用表上作业法是求解产销平衡运输问题。正文一、产销平衡运输问题1，平衡运输问题到数学问题（1） 平衡运输问题简介在经济建设生产生活中，大宗物资调运是经常碰到的事情。若某物资在全国有很多生产地，有若干销售地，那根据现有的交通网络，制订一个什么样的调运方案，可以把这些物资调运到各个销售地，使得调运费用最少。这里有个默认的前提是产销平衡，那什么是产销平衡呢？全国各个生产地所生产的物资数量加在一起等于全国各地需要销售的物资数量的总和，这是产销相等，如何根据产地到销地的运价进行运输使运费最小，这是调运问题，两者连在一起就是

12、平衡运输问题。（2） 平衡运输问题数学模型假想，设有m个生产地，用Ai 表示，i=1,2，m。m个生产地可以供应某一种物资，每个产地的供应量分别为ai，i=1,2，m。有n个销售地点，用Bj表示，j=1,2,n。n个销售地的需求量分别为bj，j=1,2，n。单位物资从Ai运到Bj的运价为Cij，把这些数据分别汇总于两个表中，表1表示产销平衡表，表2表示单位运价表。下表即为表 1 销地产地12n产量1a12a2mam销量b1b2bn表 2 销地产地12n1c11c12c1n2c21c22c2nmcm1cm2cmn现在用表示物资从运到的运量，当产销平衡时，要求得最小总运费的调运方案，那么，可以求解

13、一下数学模型： 这就是平衡运输问题的数学模型。2，表上作业法求解平衡运输问题平衡运输问题数学模型，有（）个变量，有个约束方程，有以下关系式存在：因此平衡运输模型最多有个独立的约束方程，也就是说，它的系数矩阵的秩不超过m+n-1。所以我们就可以用表上作业来求解运输问题,这个方法求解运输问题比较简便，。表上作业法是我们的一个习惯称谓，其实质是单纯形法，只是求解运输问题时对其简化了。只不过具体计算、术语不同罢了。归纳为一下几点：（1） 确定初始基可行解。在产销平衡表上给出数字格。（2）判断是否为最优解。求出各个非基变量的检验数， 并判别是否已达到最优解了。若已经是最优解了，就停止计算，不然就转到下一

14、步。（3）用闭回路法调整最优解。确定换入变量、换出变量，找新的基可行解。（4）重复（2）和（3）一直到求出最优解。例1，某化工厂。在全国各地有3个生产地A1、A2、A3，A1生产地每日生产量为7吨，A2生产地每日生产量为4吨，A3生产地每日生产量为9吨。该工厂在全国各地有4个销售地点B1、B2、B3、B4，B1销售地的销售量每日为3吨，B2销售地的销售量每日为6吨，B3销售地的销售量每日为5吨，B4销售地的销售量每日为6吨。现在知道从各个生产地到各个销售地的单位产品的运价，如图表3所示，在满足各个销售地的需要量的前提下，公司怎样调运可以使运费最少。表 3 销地产地B43113101928A37

15、4105表 4 销地产地B4产量74A39销量3656表 3 为运价表，表 4 为产销平衡表。解：通过以下三个步骤解决问题(1),确定初始基可行解用最小元素法确定初始基可行解，最小元素法基本思想很简单，就近供应思想，在单位运价表中，从最小的运价开始确定供销关系，然后是次小的运价，一直到确定出初始基可行解为止。对于平衡运输问题，因为：1mai=1nbj=d，所以，平衡运输问题一定存在初始基可行解。一定有可行解：xij=0，i=1、2、m，j=1、2、n又因为：0=xij（b1=3）,所以A2除了满足B1外，还有1吨多余的产品，在表 4 中的（A2，B1）的交叉格处填上3，得到表 5 ，把表3中的

16、B1列划去得表 6 。表 5 销地产地B4产量734A39销量3656表 6 销地产地B411310928A34105第二步：在表 6 中找出最小运价2，找到对应的产地和销地，把A2多余的那1吨供应给B3,在（A2，B3）的交叉格处填上1，得到一个新平衡表，把表 6 的A2行划去，得到一个新运价表。第三步：在第二步中得到的新运价表中找到最小运价3，就这样，一步一步的做下去，知道新的单位运价表被划空为止，最后得到的产销平衡表表 7 就是一个调运方案，这个调运方案的总运费为86元。表 7 销地产地B4产量437314A3639销量3656(2)最优解的判别判别方法也很好方便，主要是计算空格的检验数

17、cijCBB-1Pij，i，j是自然数。运输问题呢要实现目标函数最小化，所以最优解是在所有的cijCBB-1Pij = 0时的那个，现在将用闭回路法判别最优解。在表 7 上，以某一个空格为起点，从每个空格出发找一条闭回路，从起点开始，用水平线或者垂直线向前划，当遇到数字格时可以转90，然后继续向前划水平线或者垂直线，一直到回到起始位置为止。如下三个图：（a）（b）（c）因为m+n-1个数字格与之相对应的系数向量为一个基，任一空格与之相对应的系数向量为这个基的线性组合，所以从某个空格出发一定存在一个闭回路。例如Pij（i，j是自然数）可以表示为：Pij=ei+em+j=ei+em+k-em+k+

18、el-el+em+s-em+s+eu-eu+em+j图 d =(ei+em+k)(el+em+k)+(el+em+s)(eu+em+s)+(eu+em+j)PujPusPlkPlsPijPik=eik-elk+els-eus+eujeik，elk，els，eus，eujB。这些向量就构成了闭回路了，图 d 。计算检验数的闭回路法经济解释是：在表表 7 中从任意空格如（A1，B1）出发，假设把A1的产品调1吨给B1，那要保持平衡，就需要做依次的调整：（A1,B3）处减1吨，（A2，B3）处增多1吨，（A2，B1）处减1吨，这样就形成了以（A1，B1）空格为起点，其他格为数字的闭回路了如图：图 8

19、 。所在格右边的数字为单位运价。图 8 销地产地B4产量(+1)3114(-1)331073(-1)191(+1)284A376410359销量3656像这样调整之后运费增加（+1）*3+（-1）*3+（-1）*1+(+1)*2 = 1 (元)这表明，如果这样调整运价，运费将会增加。在（A1，B1）格填入“1”这个数，”1”就是检验数照这样的方法，可以找到所有检验数，如表：表 9 。表 9 空格 闭 回 路 检验数 （11）(11)-（13）-（23）-（21）-（11）1(12) (12)-（14）-（34）-（32）-（12）2（22）(22)-（23）-（13）-（14）-（34）-（3

20、2）-（22）1（24）(24)-（23）-（13）-（14）-（24）-1（31）(31)-（34）-（14）-（13）-（23）-（21）-（31）10（33）(33)-（34）-（14）-（13）-（33）12检验数还存在负数-1，说明原方程不是最优解，还需改进，下面介绍闭回路法来进行改进。(3)闭回路调整法如果检验数为负的个数超过或等于2，那先选择最小的检验数所对应的空格为调入格，以它对应的非基变量为换入变量。这里由表 9 知，只有一个负的检验数，以对应的空格（2,4）格为调入格，以此点为出发点作一闭回路，见表 10 。表 10 销地B1B2B3B4产量产地 A14（+1）3（-1）

21、7 A231（-1）（+1） 4 A3 63 9销量3 656选择表 10 中的闭回路上具有（-1）的数字格中的最小者作为（2,4）格的最小调入量，即： = min（1,3） = 1。然后再按闭回路上的正负号，加上或者减去这个最小调入量 1 ，又得到一个调整方案，如图 11 表 11 销地产地B4产量527314 A3639销量3656再用闭回路法对表 11 中给出的解求各空格的检验数，得到的表表 12 ，表 12 中没有检验数都为负的空格，所以表 11 中的解为最优解，这时得到的总运费为最小运费是85元。表 12 销地产地B40221 A3912二、产销不平衡运输问题前面讲的都是平衡运输问题

22、，现在开始讲产销不平衡运输问题。平衡运输问题模型以：i=1mai = j=1nbj为前提的，要解决产销不平衡运输问题，就可以转化为产销平衡运输问题来解决。1，生产大于销售（1），产大于销转化为产销相等生产大于销售，即：i=1mai j=1nbj这时的运输问题的数学模型可以写成：min z = i=1mj=1ncijxij满足j=1nxijai,i=1,2,，mi=1mxij=bj,j=1,2,，nxij0由于生产大于销售，所以要虚拟出一个假想销售地来，这个销售地用来销售各个产地多余的产品，只不过各个生产地运往这个销售地的运价为 0 ，设产地Ai的生产量为xi，n+1，有：j=1nxij+xi，

23、n+1=j=1n+1xij=ai，i=1,2，mi=1mxij=bj j=1,2,，ni=1mxi,n+1=i=1mai-j=1nbj=bn+1cij=cij,当i=1,2，m，j=1,2，n时cij=0，当i=1,2，m，j=n+1时带入模型得：min z=i=1mj=1n+1cijxij=i=1mj=1ncijxij+i=1mci,n+1xij =i=1mj=1ncijxijj=1n+1xij=aii=1mxij=bjxij0i=1mai=j=nbj+bn+1=j=1n+1bj可以看出这是一个平衡运输问题。如生产大于销售，那就增加一个销售地Bn+1，这个销售地为假想的，只不过各个生产地到这

24、个销售地的单位运价为0，该销售点的需要量为：i=1mai-j=1nbj。（2），产大于销问题解决应用举例例2：有两个个仓库A1、A2，有三个地方B1、B2、B3需要提供货物,具体资料如表 13 所示，可发货数量、需要量、单位运价都在里面。解：这个问题是产大于销的运输问题，增加一个假想需要地B4，b4=14-9=5，运价都为0，见表：表 14 。表 13 发点收点B1B2B3发运量A11236A26548需要量432914表 14 B1B2B3B4发货量A112306A265408需求量4325（1） 确定初始基可行解。最小元素法。表 15 。见表 15 B1B2B3B4发运量A1156A233

25、28需求量4325（2） 判别最优解，用闭回路法判别知，不是最优解。（3） 用闭回路法调整最优解，得到最优解，最小运费为21元，调整方案见表 16 表 16 B1B2B3B4发运量A1426A212258需求量4352，供不应求（2），供不应求转化为供需相等如果供不应求，类似产大于销售，同样是增加一个假想的生产地Am+1，他运往各个销售地的单位运价为0，生产量为：i=1mai-j=1nbjj=1nbj=i=1mai+am+1=i=1m+1ai（2），供不应求问题解决应用举例例3：有造纸厂三个，向四个用户供应货物，表 17 为其相关资料，要求确定一个调运方案使得总运费最小。表 17 产地 销地B

26、1B2B3B4产量A1312348A2112595A367159销量8467解：这是一个生产大于销售的运输问题，可转化为产销平衡运输问题来解决。见表 18 表 18 产地 销地B1B2B3B4产量A1312348A2112595A367159A400003销量846725(1) 确定初始基可行解。用的是最小元素法。结果见表 19 (2) 判断是否为最优解。表 19 中有1个0解，表 19 中，第一个初始解x44=3找的比较好，计算过后每一个空格的检验数都不为负，所以表 19 为最优解。假设把第一个初始解定在其他位置，如（x41、x42、x43）检验数存在负数，所以需要调整。(3) 闭回路法调整

27、最优解。假设第一个初始解定在x41，那用闭回路法调整，调整方案为：A1造纸厂给B1用户运输8个单位产品，A2造纸产给B2用户运输4个单位产品、给B4运输1个单位产品，A3造纸产给B3用户运输6个单位产品、给B4用户运输3个单位产品，总运费为62。见表 20 。表 19 产地 销地B1B2B3B4产量A13 (8)1234 (4)8A2112 (4)59 (1)5A3671 (6)5 (3)9A40000 (3)3销量846725表 20 产地 销地B1B2B3B4产量A13 （8）12348A2112 （4）59 （1）5A3671 （6）5 （3）9A400003销量846725结论本文通过

28、对产销不平衡运输问题的分析和探讨，给出了解决运输问题的思想和步骤，解决了如何调运使总的运输费用最小的问题，在今后运输生产及管理过程起到不可估量的作用，的别是对经常会遇到的将大宗物资从产地调运到销地的情况起到巨大作用自己。通过这篇论文，我们将清楚地知道，什么运输问题应该用什么样的手段来解决。若是平衡运输问题，先建立数学模型，就用表上作业法来解决，大体上分三个步骤，第一、确定初始基可行解，第二步、判断是否为最优解、第三步，调整最优解。若是产销不平衡运输问题，先把其转化为平衡运输问题，再进行解决。产大于销，就就虚拟出一个假想销售地，这样才能转化为平衡运输问题；供不应求，就虚拟出一个假想生产地，这样才

29、能转化为平衡运输问题。通过对这篇论文的设计，我除了掌握了运输问题的基本概念及其数学模型，以及求解方法外。我还更加深刻的学习和应用了线性规划问题，知道了表上作业法是求解运输问题的一种既简单又非常重要的求解方法，并且掌握了表上作业法的基本方法。通过这篇论文我理解运输问题其实也是一种特殊的线性规划问题，求解线性规划问题的基本方法是单纯形法，而运输问题的求解方法和求解线性规划的单形法没有本质区别。最深刻的是单纯形的理论和应用。最后给我的感触是，运筹学中的交通运输问题在现实中是一个非常重要的问题，对人类的生活有着非常重要的作用。通过做毕业设计，自己才真正感觉到自己学了这十几年的数学并非白学，反而感到数学

30、真的强大，没有数学真的什么也干不了。另外，我学到了做项目和做事情不可以少的一些基本常识，即，做事，要有个计划，要按计划有序的完成任务，没有计划就会乱，不知道今天该做什么或者明天该做什么，最后是什么也没做，任务完成不了，在毕业设计这个过程中能学到这一点我已经感到很荣幸了，这一点将对我以后的人生起到不可估量的作用。致谢在本论文的写作即将完成之际，笔者的心情无法平静，本文的完成既是笔者孜孜不倦努力的结果，更是导师林浩副教授亲切关怀和悉心指导的结果。在整个论文的选题、研究和撰写过程中，导师都给了我精心的指导、热忱的鼓励和支持，他多次询问论文的写作进程，多次为我批阅文章并提出修改意见，他的精心点拨为我开拓了研究视野，修正了写作思路，整个毕业设计过程，无不凝聚着林浩老师的心血和汗水，对论文的完善和质量的提高起到了关键性的作用。另外，在学习生活中，林浩老