【作者】 张丽林；

【导师】 贺国平； 周长银；

【作者基本信息】 山东科技大学 ， 运筹学与控制论， 2008， 硕士

【摘要】 本文系统地介绍了随机规划的产生和发展,总结和分析了近年来随机规划领域的研究成果。在前人研究的基础上,对随机规划问题特别是补偿随机规划问题,进行了系统研究,用基于热启动策略的内点法求解问题。首先介绍了随机规划的产生和发展、随机规划问题的分类和求解算法,着重介绍了两阶段和多阶段随机规划模型。其次,简要介绍了求解凸优化问题的有效算法—内点算法及其在各种优化问题中的应用,特别是详细介绍了原始-对偶路径跟踪内点算法;概括了“热启动策略”的思想,并给出了求解线性规划和凸二次规划问题的热启动内点算法,所给出的算法是收敛的,并具有多项式时间复杂度。对于补偿随机规划问题,多数学者用分解算法去求解,而本文则致力于用内点法和热启动策略来求解问题。首先给出了求解带有离散型随机变量的多阶段随机线性规划问题的热启动内点算法,然后将这种算法推广应用到求解多阶段二次随机规划问题。理论上证明了当问题的扰动满足一定条件时,所设计的算法是有效的。算法先求解一个与简化的方案树相对应的小规模问题,用得到的解构造原问题(大规模问题)的初始迭代点,再用大步长路径跟踪内点算法求解原问题。因为补偿随机规划模型引入了随机变量,使得建立的模型更加符合生产生活中的实际情况,所以其应用日益广泛。本文建立了求解大规模运输—库存决策问题的二阶段随机线性规划模型,并给出了实例分析。所建立的模型具有很好的实用价值,特别是对于解决物流管理系统中带有很大不确定性的运输—库存问题效果明显。更多还原

【Abstract】 This paper introduces the development of stochastic programming systematically while summarizing and analyzing the fruits on this field in the past. Based on the study of some researchers, we study stochastic programming systematically, especially on how to solve stochastic programming with recourse with warm-start interior point methods.First of all, we summarily introduce the generations development and current research situations as well as the classification about stochastic programming. And we introduce the models of stochastic programming with recourse systematically. Next, we introduce the interior point method briefly for solving convex optimization problem, especially introducing the path-following primal-dual algorithm in detail. And we summarize the "warm start strategies". We give the warm start interior point methods for solving linear programming and quadratic programming. The algorithm is convergent and it has polynomial-time complexity.Many researchers solve stochastic programming with recourse with specialized decomposition. While, we concentrate on "warm start strategies" and interior point methods. We give a warm start interior point methods for solving multi-stage stochastic linear programming which is extended to solve multi-stage quadratic stochastic programming. Theoretically we have proved that when the discrepancy among scenarios in the event tree is small adequately algorithm 3 is practical completely. The basic idea of our algorithm is as follows: First, we solve the small-scale problem corresponding to the reduced tree. Then we can obtain a starting point for the complete problem from the small-scale problem. Finally we solve the complete problem with long step path-following interior point algorithm.We introduce random variable in the model of stochastic programming with recourse so that our model is in complete accord with reality. Therefore, its application is widespread day by day. We establish a model of two stage stochastic programming for transportation-inventory problem and an example analysis was given. The model has much more value in our real life, especially for the transportation-inventory problem in physical distribution management system with much more uncertainty.更多还原