表上作业法在物品运输上的应用【文献综述】.doc

1、毕业论文文献综述数学与应用数学表上作业法在物品运输上的应用一、材料来源情况资料主要来自网上查询、课本以及指导教师的指导。二、课题的背景、研究现状运输问题是当今社会经济生活中经常出现的优化问题。在经济建设中，经常遇到物资的调运问题，如何制定调运方案，将物资运往指定地点，而且实现运输费用最小，即为运输问题。运输问题是特殊的线性规划问题，它是线性网络最优化的一个例子。最早研究这种运输问题的是美国学者希奇柯克（HITCHCOCK），1941年他在研究生产组织和铁路运输方面的线性规划问题的时候提出运输问题的基本模型；后来柯普曼（KOOPMANS）在1947年独立地提出运输问题并详细地加以讨论；从上世纪4

2、0年代早期开始，康脱洛维奇（KANTOROVICH）围绕着运输问题作了大量的研究，所以运输问题又称为希奇柯克问题或康脱洛维奇问题。与一般线性规划问题不同的是它的约束方程组的系数矩阵具有特殊结构，这就需要采用不同甚至更为简便的方法来解决这种在实际工作中遇到的问题。运输问题代表了物资合理调运、车辆合理调度等问题，其他类型问题经过一系列变换后也可以归结为运输问题。由于运输问题的特殊数学结构，人们很早就想到到通过给出基变量，离基变量的最优性条件，可以更有效地利用单纯形法对运输问题进行求解。DANZIG提出的单纯形法作为求解运输问题最初单纯形方法（PRIMALSIMPLEXTRANSPORTATIONM

3、ETHOD，PSTM）1。随后CHARNES和COOPER（1954）发展逐级算法（STEPPINGSTONEMETHOD，SSM），这种算法提供了决定单纯形方法信息的可选择途径。表上作业法是解决运输问题常用的解法，因为它在求解工作均在运输表上进行而得名。它是一种迭代算法，他的迭代步骤主要为先按某种规则找出一个初始解；再对现行解作出最优性判别；若该解不是最优解，就在运输表上进行调整改进，得出一个新的解，再重复判别改进，直至得到运输问题的最优解。表上作业法是指用列表的方法求解线性规划问题中运输模型的计算方法。是线性规划一种求解方法。当某些线性规划问题采用图上作业法难以进行直观求解时，就可以将各元

4、素列成相关表，作为初始方案，然后采用检验数来验证这个方案，否则就要采用闭合回路法、位势法等方法进行调整，直至得到满意的结果。这种列表求解方法就是表上作业法。表上作业法是求解运输问题的一种简便的方法,实质仍是单纯形法1计算步骤如下1找出初始基可行解,即在产销平衡表上给出MN1个数字格确定初始基可行解常用的方法最小元素法和伏格尔法VOGEL2求各非基变量的检验数,即在表上计算空格的检验数,判别是否达到最优解如果已是最优解,则停止计算,否则转入下一步3在经济建设中，经常碰到大宗物资调运问题。如煤、钢铁、木材、粮食等物资，在全国若干个生产基地，根据已有的交通网，应如何制订调运方案，将这些物资运到各消费

5、地点而总运费最小。本题目就是在这种类似的背景下，运用表上作业法，得出最优解使得总运费最小节省资金。4运输问题通常用“表上作业法”求解先以“最小元素法”或“西北角法”给出一个初始方案,再以“闭回路法”或“位势法”进行调整改进,直至获得最优方案。但在实际优化调整时,无论采用何种方法,都必须逐一计算每个空栏处的检验数,才可分析比较并作出调整,其过程重复、计算繁冗,极大地影响了实际应用和推广本文不仅要研究表上作业法在物品运输上的运用，也要对表上作业法加以改进，使得计算更加方便准确三、自己的观点与主张，该课题的发展动向和趋势物品运输问题在当今经济建设中是十分常见的问题，如何选择一个合理的运输方案使得运输

6、费用最低是十分关键的，本文主要目的便是采用传统的表上作业法来解析这一类问题。一般运输问题就是为解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的情况下，确定使总运输费用最小的方案的数学问题。例某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问应如何调运可使总运输费用最小表上作业法是求解运输问题的一种简便的方法,实质仍是单纯形法。在使用表上作业法是为确定初始基可行解常常采用最小元素法和法格尔法。最小元素法的所谓元素，是指单位运输价格。最小元素法的基本思

7、路是运输价格最便宜的优先调运。即从运输问题数据表（或单位运输价格表）中寻找最小数值，并以这个数值所对应的变量IJX作为第一个基变量，在该变量格内的右下角填入允许取得的最大数。然后一直按此方法继续下去，若某行（列）的产量（销量）已满足，则该行（列）的其他变量IJX只能取0值或说“把该行（列）的其他格划去，直到取得一个基本可行解为止。在充分研究好表上作业法之后，将会把表上作业法与其他方法进行比较分析，以期改进表上作业法，而后用改进的表上作业法解决物品运输问题，分析其先进之处。个人认为现在表上作业法求解过程复杂、繁琐,求解维数也受到很大限制2随着计算机技术的发展，在求解运输问题上表上作业法将与LIN

8、GO软件相结合使得问题的求解更为方便。主要参考文献1王有鸿,费威运输问题国内外研究评述J,东北财经物流研究2010247137182钱颂迪运筹学M北京清华大学出版社,2005,063李彦臣,魏丽雅产销平衡运输最低成本的表上作业法J交通科技与经济,2000,01251574张家善,LINGO软件求解运输问题与表上作业法的比较J湛江师范学院学报2001（3）1371405盛秀艳窦志伟,农业运输问题的表上作业法与图上作业法的比较J安徽农业科学报,2010，10720272036,金峻炎表上作业法与网络计算法求解运输问题的比较分析J科技咨询导报20071320217李时椿运输问题表上作业法的改进研究J

9、南京航空航天大学学报200032（6）3243298王德敬,改进平衡运输问题表上作业法中的最优方案判别法则J江西农业大学学报199618（4）4834879蒋宏锋,运输问题一种新的表上作业法J科学技术与工程2006,6243941394810杜子平运输问题表上作业法的解析C第六届中国青年运筹与管理学者大会论文集20040711刘耀表上作业法的改进J兰州大学自然科学学报196101171912伍学滨，刘国良，彭友霖表上作业法在物资调运问题中的应用M商场现代化200113郭秀英论运输问题表上作业法J科技与管理20073333514田荣表上作业法的一种理论证明J北京职工医学院学报2001333351

10、5刘大为，张方华，运输问题表上作业法的改进J科技资讯2008，1224825016XINFENGYANG,YINZHENLI,RUICHUNHE,LINZHONGLIUMODELANDALGORITHMOFTRANSPORTATIONPROBLEMONNETWORKJJOURNALOFSYSTEMSSCIENCEANDINFORMATION2008，6（4）32533217CHENHAIFENGCHOJOONGRAELEEJEONGTAE，SOLVINGHITCHCOCKSTRANSPORTATIONPROBLEMBYAGENETICALGORITHMJ重庆大学学报英文版20043（2）5457