补偿随机规划的若干算法及其应用研究.docx

分 类 号 ：O221.5 密 级：公 开U D C : 单位代码：10424学 位 论 文补偿随机规划的若干算法及其应用研究张 丽 林申请学位级别：硕士学位 专业名称：运筹学与控制论指导教师姓名：贺 国 平 职 称： 教 授周 长 银 职 称： 副 教 授山 东 科 技 大 学二零零八年五月论文题目：补偿随机规划的若干算法及其应用研究作者姓名： 张 丽 林 入学时间： 2005 年 9 月专业名称： 运筹学与控制论 研究方向： 优化方法及其应用指导教师： 贺 国 平 职 称： 教 授周 长 银 职 称： 副 教 授论文提交日期：2008 年 5 月论文答辩日期：2008 年 6 月授予学位日期：STUDY OF SOME ALGORITHMS FOR STOCHASTICPROGRAMS WITH RECOURSE AND ITSAPPLICATIONSA Dissertation submitted in fulfillment of the requirements of the degree ofMASTER OF SCIENCEfromShandong University of Science and TechnologybyZhang LilinSupervisor: Professor He GuopingAssociate Professor Zhou ChangyinCollege of Information Science and EngineeringMay 2008声 明本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所公认的文献外，全部是本人在导师指导下的研究成果。

该论文资料尚没有呈交于其它任何学术机关作鉴定硕士生签名：日 期：AFFIRMATIONI declare that this dissertation, submitted in fulfillment of the requirementsfor the award of Master of Science in Shandong University of Science andTechnology, is wholly my own work unless referenced of acknowledge. Thedocument has not been submitted for qualification at any other academicinstitute.Signature:Date:山东科技大学硕士学位论文 摘要摘 要本文系统地介绍了随机规划的产生和发展，总结和分析了近年来随机规划领域的研究成果在前人研究的基础上，对随机规划问题特别是补偿随机规划问题，进行了系统研究，用基于热启动策略的内点法求解问题首先介绍了随机规划的产生和发展、随机规划问题的分类和求解算法，着重介绍了两阶段和多阶段随机规划模型。

其次，简要介绍了求解凸优化问题的有效算法—内点算法及其在各种优化问题中的应用，特别是详细介绍了原始-对偶路径跟踪内点算法；概括了“热启动策略”的思想，并给出了求解线性规划和凸二次规划问题的热启动内点算法，所给出的算法是收敛的，并具有多项式时间复杂度对于补偿随机规划问题，多数学者用分解算法去求解，而本文则致力于用内点法和热启动策略来求解问题首先给出了求解带有离散型随机变量的多阶段随机线性规划问题的热启动内点算法，然后将这种算法推广应用到求解多阶段二次随机规划问题理论上证明了当问题的扰动满足一定条件时，所设计的算法是有效的算法先求解一个与简化的方案树相对应的小规模问题，用得到的解构造原问题（大规模问题）的初始迭代点，再用大步长路径跟踪内点算法求解原问题因为补偿随机规划模型引入了随机变量，使得建立的模型更加符合生产生活中的实际情况，所以其应用日益广泛本文建立了求解大规模运输—库存决策问题的二阶段随机线性规划模型，并给出了实例分析所建立的模型具有很好的实用价值，特别是对于解决物流管理系统中带有很大不确定性的运输—库存问题效果明显关键词：补偿随机规划问题，路径跟踪内点算法，热启动策略，方案树，运输—库存问题山东科技大学硕士学位论文 摘要AbstractThis paper introduces the development of stochastic programming systematically whilesummarizing and analyzing the fruits on this field in the past. Based on the study of someresearchers, we study stochastic programming systematically, especially on how to solvestochastic programming with recourse with warm-start interior point methods.First of all, we summarily introduce the generation 、 development and current researchsituations as well as the classification about stochastic programming. And we introduce themodels of stochastic programming with recourse systematically. Next, we introduce theinterior point method briefly for solving convex optimization problem, especially introducingthe path-following primal-dual algorithm in detail. And we summarize the “warm startstrategies”. We give the warm start interior point methods for solving linear programming andquadratic programming. The algorithm is convergent and it has polynomial-time complexity.Many researchers solve stochastic programming with recourse with speciali- zeddecomposition. While，we concentrate on “warm start strategies” and interior point methods.We give a warm start interior point methods for solving multi-stage stochastic linearprogramming which is extended to solve multi-stage quadratic stochastic programming.Theoretically we have proved that when the discrepancy among scenarios in the event tree issmall adequately algorithm 3 is practical completely. The basic idea of our algorithm is asfollows: First, we solve the small-scale problem corresponding to the reduced tree. Then wecan obtain a starting point for the complete problem from the small-scale problem. Finally wesolve the complete problem with long step path-following interior point algorithm.We introduce random variable in the model of stochastic programming with recourse sothat our model is in complete accord with reality. Therefore, its application is widespread dayby day. We establish a model of two stage stochastic programming for transportation-inventoryproblem 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 managementsystem with much more uncertainty.Keywords: stochastic programming with recourse, path-following interior point algorithm,warm start strategies, scenario tree, transportation-inventory problem…1…7…4山东科技大学硕士学位论文 目录目 录1 绪 论………………………………………………………………………121.引言………………………………………………………………………………… 11.2 随机规划问题的主要模型……………………………………………………………11.3 求解方法和研究现状…………………………………………………………………41.4 本文的主要工作………………………………………………………………………5内点法及热启动内点法……………………………………………………72.1 引言 ……………………………………………………………………………………72.2 原始 ―对偶路径跟踪法………………………………………………………………72.3 热启动策略…………………………………………………………………………102.4 求解凸二次规划的热启动内点算法…………………………………………………113 求解多阶段随机规划问题的热启动内点法…………………………………143.1 引言 …………………………………………………………………………………143.2 求解多阶段随机线性规划问题的热启动算法……………………………………143.3 求解多阶段二次随机规划的热启动算法…………………………………………224 二阶段随机规划模型在大规模运输―库存问题中的应用………… …334.1 引言 …………………………………………………………………………………334.2 大规模运输网络配流―库存决策问题……………………………………………334.3 运输 ―库存问题的二阶段随机规划模型…………………………………………344.4 实例分析……………………………………………………………………………375 总结与展望 …………………………。