离散优化问题最优值函数的连续性质  

The continuity properties of optimal value function of discrete optimization problems

作　　者：张玉忠[1] 杨晓光[2] 

机构地区：[1]曲阜师范大学运筹学研究所、管理学院,山东日照276826 [2]中国科学院数学与系统科学研究院系统科学研究所,北京100080

出　　处：《运筹学学报》2016年第3期79-84,共6页Operations Research Transactions

基　　金：国家自然科学基金(No.61340045);山东省自然科学基金重点项目(No.ZR2015GZ009);教育部高等学校博士学科点专项基金(No.20123705110003);山东省研究生教育创新人才计划项目(No.SDYC13036);山东省属本科高校教学改革研究项目(No.2015M098)

摘　　要：对优化问题的最优值研究是有意义的,尽管有时并不知道怎样寻求最优值.研究了几个重要的组合最优化问题的目标值随着输入值变化的连续化性质,重点研究几个经典的、有代表性的离散优化问题:极小化最大完工时间的排序问题、背包问题、旅行商问题等,以连续的数学分析思维模式审视离散问题.最后,研究了一些近似算法对应的目标函数的性质.It is undoubtedly significant to study the change rules of the optimal values of optimization problems, when the set of feasible solutions changes follow some parameters, even if there is no way to get the optimal value generally. For continuous optimization, where the independent variables are numbers or vectors, the characteristics of the optimal value functions following the changing of the variables has been studied extensively, but for discrete optimization problems there is few literature. In this paper some important classical combinatorial optimization problems are considered. We mainly focus on the characteristics of the optimal value functions, here the independent variables are some plans or tours, may not be numbers nor vectors. Parallel scheduling problem, Knapsack problem, Traveling salesman problem are considered in the paper, focusing on the characteristics of the optimal value functions of these problems if the inputs of parameters are change. Finally, we also consider the characteristics of objective function arised by some famous algorithms such as LPT to minimize the makespan of parallel machine schedule.

关 键 词：排序问题 旅行商问题 背包问题 最优值函数 次梯度 

分 类 号：O221.1[理学—运筹学与控制论]