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

The continuity properties of optimal value function of discrete optimization problems

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

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.