Range sets for weak efficiency in multiobjective linear programming and a parametric polytopes intersection problem

The aim of this paper is to obtain the range set for a given multiobjective linear programming problem and a weakly efficient solution. The range set is the set of all values of a parameter such that a given weakly efficient solution remains efficient when the objective coefficients vary in a given direction. The problem was originally formulated by Benson in 1985 and left to be solved. We formulate an algorithm for determining the range set, based on some hard optimization problems. Due to toughness of these optimization problems, we propose also lower and upper bound approximation techniques. In the second part, we focus on topological properties of the range set. In particular, we prove that a range set is formed by a finite union of intervals and we propose upper bounds on the number of intervals. Our approach to tackle the range set problem is via the intersection problem of parametric polytopes. Thus, our results have much wider area of applicability since the intersection (and separability) problem of convex polyhedra is important in many fields of optimization.本文旨在针对给定的多目标线性规划（multiobjective linear programming）问题与弱有效解（weakly efficient solution），求取其对应的值域集（range set）。该值域集指的是：当目标系数沿指定方向变动时，给定的弱有效解仍能保持有效状态的所有参数取值所构成的集合。该问题最早由Benson于1985年提出，迄今尚未得到解决。本文基于若干难求解优化问题，构建了用于求解该值域集的算法。鉴于此类优化问题的求解难度，我们同时提出了下界与上界近似求解技术。在第二部分中，我们聚焦于值域集的拓扑性质。具体而言，我们证明了值域集可表示为有限个区间的并集，并给出了区间数量的上界。本文求解值域集问题的思路依托于参数多面体（parametric polytopes）的交集问题。由于凸多面体（convex polyhedra）的交集（及可分性）问题在诸多优化领域中均具有重要地位，因此本文的结论具备更为广泛的适用范围。