English

运筹学学报

• 运筹学 • 上一篇    下一篇

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

张玉忠1,*  杨晓光2   

  1. 1. 曲阜师范大学运筹学研究所、管理学院, 山东日照276826; 2. 中国科学院数学与系统科学研究院系统科学研究所, 北京 100080
  • 收稿日期:2015-07-07 出版日期:2016-09-15 发布日期:2016-09-15
  • 通讯作者: 张玉忠 yuzhongrz@163.com
  • 基金资助:

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

The continuity properties of optimal value function  of discrete optimization problems

ZHANG Yuzhong1,*  YANG Xiaoguang2   

  1. 1. Institute of Operational Research, School of Managements, Qufu Normal University, Rizhao 276826, Shandong, China; 2. Academy of Mathematics and System Science Academy, Chinese Academy of Sciences, Beijing 100080, China
  • Received:2015-07-07 Online:2016-09-15 Published:2016-09-15

PDF

443

被引次数

1

摘要：

对优化问题的最优值研究是有意义的, 尽管有时并不知道怎样寻求最优值. 研究了几个重要的组合最优化问题的目标值随着输入值变化的连续化性质, 重点研究几个经典的、有代表性的离散优化问题：极小化最大完工时间的排序问题、背包问题、旅行商问题等, 以连续的数学分析思维模式审视离散问题. 最后, 研究了一些近似算法对应的目标函数的性质.

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

Abstract:

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.

Key words: schedule, traveling salesman problem, Knapsack problem, optimal value function, subdifferential