奥运调度问题模型转换及优化研究

？本文研究了奥运会调度问题的模型转换和优化.(1)时间区间约束是奥运会调度问题的关键约束,本文建立了一种时间区间模型语言以描述这个调度问题.(2)奥运会调度问题是一个约束满足问题,考虑其本质复杂性,本文通过柔化决赛时间约束将约束满足问题转化为约束优化问题.(3)约束优化模型中,项由场地约束关联起来,如果去掉场地约束,各项则是相互独立的.因而本文通过松弛场地约束将约束优化问题分解为若干子问题.全局优化解通过调整拉格朗日乘子获得.(4)为了调整拉格朗日乘子,本文研究了变直径次梯度投影算法,此算法不依赖于任何先验知识收敛,本文给出了收敛效率.仿真结果说明了算法的收敛性,显示出变直径次梯度投影算法与简化算法在性能上的差别,并且表明原约束满足问题的相变现象可以通过变直径次梯度投影算法获得正的对偶值的概率和首次获得正的对偶值的时间来识别.