【作者】 刘徽；

【导师】 严从荃；

【作者基本信息】 四川大学 ， 基础数学， 2005， 硕士

【摘要】 本文论讨了两类运输问题的算法,传统运输问题的算法和受时间约束运输问题的方案及算法。 对于传统的运输问题,应用线性规划内点算法的基本理论,结合运输问题模型的特殊性,提出了运输问题内点算法的基本理论和一般步骤。该算法从运输问题可行域的内部出发,沿着中心路径的方向,通过反复迭代寻找运输问题的近似最优解。 受时间约束运输问题给出了求解的一种新方案,并举例说明了其可行性。 全文共分五部分:第一部分引言,第二部分对线性规划和运输问题的历史做一个小结性的回忆。第三部分,对内点算法的一些理论做一些简单的介绍,当然其中大部分引用了前人的工作,其中Yinyu Ye和Andersen对我有很大的帮助,这部分内容主要是他们的一些卓有成效的工作。第四部分,运输问题的新算法,给出了运输问题内点算法的相关理论和步骤及受时间约束运输问题的解决方案。第五部分,结束语,对所做工作的一个自我评价。 本人所做的工作主要在第四部分,包括下面几个方面: (1) 总结性给出运输问题的特点; (2) 提出运输问题内点算法的构想和理论; (3) 给出运输问题内点算法的一般步骤; (4) 提出最优准则下受时间约束运输问题的配送方案; (5) 通过实际的例子说明了受时间约束运输问题的具体算法。更多还原

【Abstract】 In this paper, the author presents two k inds of methods for the Transportation Problems, which are Traditional Transportation Problem and Transportation Problem with time constraints.For traditional problem this paper is based on the basic theories of Interior -Point Method for the Linear Programming, and we have considered special structure of the Transportation Problem. The method is finding an interior point in the feasible region, followed by the central path, we can find a approximate optimal solution.New approach to solve Transportation Problems with time constraints is discussed in the practice.And an example is given to illustrate its feasibility.The paper has fiveparts. The first partis introduction The second part, simply introduces the history and development of L inear Programming and Transportation Problem. The third part, introduces the basic theory of Interior -Point Method. Thanks for Yinyu Ye[2] and Andersen[3] and theirexcellent work. The fourth part, gives the theory and steps of Interior -Point Method for Transportation Problem and approach to solve Transportation Problems with time constraints. The fifth part, function as ending paragraph for self-estimate.My work mainly includes five parts:(1) Giving the special structure of the transportation problem;(2) Presenting the basic theories and conception of Interior Point Method to solve Transportation Problem;(3) Giving the steps of Interior -Point Method to solve Transportation Problem.(4) Giving the approach to time constraint s problem on the precedence principle(5) Introducing the application of the methodfor time constraints problem更多还原