《带有约束性的运输问题及其推广数学系毕业论文.doc》由会员分享，可在线阅读，更多相关《带有约束性的运输问题及其推广数学系毕业论文.doc（17页珍藏版）》请在三一办公上搜索。
1、 毕 业 论 文 学生姓名xx学 号 xxxxx学 院数学科学学院专 业数学与应用数学题 目带有约束性的运输问题及其推广指导教师xxx xxxxxxx年x月毕业论文独创性声明本人郑重声明：本论文是我个人在导师指导下进行的研究工作及取得的研究成果。本论文除引文外所有实验、数据和有关材料均是真实的。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。其他同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。作者签名： 日 期： 摘要：运输问题是一种线性问题，它一直被广泛运用于实际生活中，与我们的生活息息相关.约束问题所讨论的是同种物资的供需调拨问
2、题.本文首先提出了一般运输问题，以及它的解决方法.然后在一本运输问题的基础上，提出了带上界约束的运输问题，并通过对表上作业法的改进，提出了求解问题的一般方法.关键词：上界，运输问题，表上作业法Abstract: Transportation problem is a linear problem, it has been widely used in real life, is closely related to our life. Constraint problems discussed the issues of the same goods of supply and demand
3、allocate. At first, this paper presents a general transportation problem and its solutions. Then on the basis of a transportation problem, transportation problem with upper bound constraint is proposed, and through the improvement of method in table, puts forward the general method of solving proble
4、m.Key Words：upper bound,transportation problem,tabular method 目录1 前言42 运输问题的数学模型42.1 模型的推广42.1.1 约束情形152.1.2 约束情形252.1.3 约束情形363 一类带上界的运输问题73.1 带上界的运输问题的数学模型93.2 问题的优化方法9总结13参考文献141.前言运输问题是一种特殊的线性规划问题.广泛的运用于生产实践中，但是我们知道，很多一部分的运输问题并没有考虑到生产地和销售地的运输能力问题，这就导致了最佳的运输方案缺乏了一定的实际考究，可能有很多片面的局限性，这样就限制了运输问题在实际中
5、的应用.所以，我们在此对这一问题进行探讨. 2.运输问题的数学模型在经济活动及军事后勤中,物资的调拨运输随处可见,如何根据现有的供需状况及运输网络制定调运方案,使总运输费用最小,其模型描述如下.假定有m个供点,其供量为, ,有个需点,其需量为,.到的单位货物运价为,;.设供点对需点的供量为,则最小运输费用的数学模型为模型(TP)是一系数矩阵稀疏的线性规划模型,当时,即供需平衡时,为避免使用单纯形算法,文献1给出了运输问题的表上作业算法.但在实际问题中,遇到的往往是供需不平衡问题.当 (供大于需)或 (需大于供)时,由文献2可知,可将其转化为供需平衡问题来处理.2.1模型的推广在经济活动中,我们
6、所遇到的运输问题往往还会受到许多其它约束条件,如某些供点供给某些需点的量会因主、客观条件或政策因素而受到限制.这样,受到约束的运输问题就无法直接用表上作业法求解.为避免使用繁琐的单纯形法求解而推广运用表上作业法,我们可对供需平衡表中的供需点、供需量及运价作一些技术处理.本文主要是针对一对供需点带有约束的运输问题进行技术处理,对多对供需点带有约束的运输问题可作类似处理.2.11约束情形 1某供点至少供给某需点量，不妨设供电至少给需点量（或从处至多得到量）,对此情形，运输模型为.可将供点虚拟划分成两个供点,将需点虚拟分成两个需点,并赋予相应运价后构造供需运输平衡表,见表1.运价需点供量供点 需量其
7、中,价格中的表示对应的供点不供给对应的需点(下同).对处理后的供需运输平衡表,可使用表上作业法求其最优解.方案中需点从供点,处所得供量之和为从处所得量.同样,供点供给需点的需量之和为供给需点的量.2.12约束情形2 某供点至少供给某需点量，不妨设供电至少供给需点量（或从处至少得到量）.对此情形，运输模型为同样将供点虚拟划分成两个供点,将需点B1虚拟分成两个需点,并赋予相应运价后构造供需运输平衡表见表2. 运价需点供量供点 需量对此供需运输平衡表,使用表上作业法同样可求其最优供需方案.2.13约束情形3某供点必须且只需供给某需点量（即需点必须且只需从点得到量），此时运输模型为此情形,为了使用表上
8、作业法求其最优解,这里给出两种处理方法.方法将供点虚拟划分成两个供点,将需点虚拟分成两个需点,并赋予相应运价后构造供需运输平衡表,见表3.运价需点供量供点 需量方法让供点先供给需点量后,供量变为,需点从供点得到量后,需量变为,重新构造供需运输平衡表,见表4.运价需点供量2供点 需量由供需运输平衡表3或表4,用表上作业法可求此情下的最优供需方案. 3.一类带上界约束的运输问题 我们一般未考虑从某产地到销地的运输能力问题，因而会出现最优调运方案时从产地到销地单位时间内的最优调运量超过实际的通行能力的情况,因而限制了运输问题在实际中的应用.故我们要对此问题提出探讨.我们提出如下带上界约束的运输问题:
9、 在计划期内,已知有个生产产地( ),可供应某种物资,其供应量分别为( ),有个销地( ),其需求量分别为(),假定产销平衡的问题，从到运输单位物资的运价为.且由于实际运输能力的限制,计划期内从到的最大允许运输量为,试确定满足以上条件的最优调运方案. 以上这些数据可以汇总于产销平衡表、单位运价表及上界表中.见表1,2,3.由此可见,带上界约束的运输问题与一般运输问题相比多一张上界表,如令所有的，则转换为一般运输问题.因而一般运输问题是带上界约束运输问题的特例. 表1.产销平衡表 产地 销地 产量销量 表2.单位运价表产地销地 表3.上界表待添加的隐藏文字内容2产地销地3.1带上界约束问题的数学
10、模型设(); )表示从到的调运量,则可建立带上界约束运输问题. 显然此为一线性规划问题,因而可以用单纯形法求解,然而由于问题的特殊性,我们可以找到比单纯形法简单的多的求解方法.对一般运输问题均存在可行解,但由于带上界约束的运输问题多了上界约束条件,故不一定必然存在可行解.关于此问题的可行解,显然存在如下结论:定理1 带上界约束运输问题存在可行解的充分必要条件是:）3.2问题的优化方法由于带上界约束运输问题的数学模型比一般运输问题的数学模型仅多了(4)式,因而可以通过对表上作业法的改进来求解此类问题,求解思路为:(1)首先不考虑问题的上界约束用表上作业法求解替代的一般运输问题;(2)如第一步求解
11、的结果无法满足上界约束,则替代问题的最优解显然即是原问题的最优解.否则设法调整替代问题的最优解,使之逐渐满足,最后找到原问题最优解.下面以一实例加以说明.设一运输问题的有关数据如表4,5,6.表4.产销平衡表产地产量销量表5.单位运价表产地销地表6.上界表第一步,不考虑问题的上界约束表6,用表上作业法对表4、表5求解,可得表7、表8结果. 表7.替代问题最优调运方案销地产地 表8.检验数表产地销地 在表7中,由于,故非原问题最优调这运方案.第二步,由于表7非原问题最优调运方案,因而我们设法对其调整.调整的思路应该是：法减少满足的变量,而且调整时要尽可能少地增加运费.本例中,目前应该调整的变量为
12、,与,但,与的减少,必然引起替代问题最优解中非基变量的增加,从而引起总运费的增加.为分析调整的思路与运费的变化,我们将用闭回路法求表8检验数的过程写出如下: 首先找出含有,或的闭回路,在这些闭回路上调整可减少、或,然而并非找出的所有这些回路均可调整,要使该闭回路可调整,必须使该回路上所含正对应的变量满足,负对应的变量满足.否则即为不可调整的闭回路.在满足这些条件下,闭回路的可调整量为:调整后的单位运价变动量为.本例中,按以上原则判断后可知,对应的闭回路不可调,、对应的闭回路可调,运费的增加以最小,因而对此回路进行调整,按闭回路法调整后的结果如表9所示:产地 营销 41 6 0 6 1 表9 调
13、整后调运方案选取的，对应与.因此对而言，在表中它已不能再增加，也不能再减少.故对以后各步，不再可调，故用括号将其扩起，对余下的空格，将未加括号的数字键作为基变量，用闭回路法求得检验数，同理可找出对应的闭回路为最优调整路线,调整后结果如表10所示.同样按原则确定的，对应.故不再可调整,将其括起.仿照上述步骤,最后可满足上界约束的最优调运方案如表11所示.表10.调整后调运方案产地销地 表11.最优调运方案及上界表销地产地最优调选方案上届表可以证明,表11即为原问题的最优调运方案.由上例可得带上界约束运输问题的求解步骤如下:1. 不考虑原问题上界约束,用表上作业法求解替代问题的最优调运方案； 2.
14、 如所有，则已得原问题最优调运方案，否则转第三步；3.列出所有非基变量检验数对应的闭回路,将包含对应的的闭回路找出来,并确定该闭回路的可调整量，则该闭回路可调整；4.在所有可调整闭回路中找出对应检验数最小的闭回路进行调整,并将确定时对应的变量确定为不可调整变量,将其用用括号括起,在以后计算非基变量检验数时,不考虑括号内的数字.返回第2步,直至结束.以上分析了带上界约束产销平衡问题的求解,对产销不平衡问题,只要增设一个假想的产地(或销地),并假定从该产地到所有销地(或从所有产地到该销地)的单位运价和上界约束分别为和,即可转换为产销平衡问题. 结论运输问题由来已久，我们一定要根据产地和销地的具体实
15、际问题进行分析，才能合理优化的解决运输问题，同样的，在现实生活中，处理其它的问题也是一样，我们要细心分析具体的情况，从不同的角度出发，才能找到最合理的解决方法. 参 考 文 献 胡运权.运筹学基础及应用.哈尔滨:哈尔滨工业大学出版社,1993:30-45. 运筹学教材编写组.运筹学.北京:清华大学出版社,1990:20-36. 胡运权,等.运筹学M.北京:清华大学出版社,1982:46-68. 李向东.运筹学管理科学基础M.北京:北京理工大学出版社,1990:33-60. 张鸣龙.在最优解上挖潜运输问题的研究J.系统工程理论与实践,1987:20-43. 刘晓华.一般情形的运输问题J.系统工程,1989:37-62.致谢 本论文及研究实在我导师xxx先生的亲切关怀和悉心知道下完成的.他严肃的科学态度，严谨的治学精神，精益求精的工作作风，深深的感染和激励着我.xxx先生不仅在学业上给予我精心的指导，同时还在思想，生活上给我无微不至的关怀，在此向xxx先生致以诚挚的谢意和崇高的敬意.我才能克服一个一个的困难和疑惑，直至本文的顺利完成. 在论文即将完成的时刻，我的心情无法平静，从一开始进入课题到论文的顺利完成，有多少可敬的师长和同学给了我无言的帮助，在这里请接受我诚挚的谢意！最后还要感谢培养我长大的含辛茹苦的父母，谢谢你们！ 最后，再次对关心和帮助过我的老师和同学表示衷心地感谢！
