New conditions for testing necessarily/possibly efficiency of non-degenerate basic solutions based on the tolerance approach

摘要

In this paper, a specific type of multiobjective linear programming problem with interval objective function coefficients is studied. Usually, in such problems, it is not possible to obtain an optimal solution which optimizes simultaneously all objective functions in the interval multiobjective linear programming (IMOLP) problem, requiring the selection of a compromise solution. In conventional multiobjective programming problems these compromise solutions are called efficient solutions. However, the efficiency cannot be defined in a unique way in IMOLP problems. Necessary efficiency and possible efficiency have been considered as two natural extensions of efficiency to IMOLP problems. In this case, necessarily efficient solutions may not exist and the set of possibly efficient solutions usually has an infinite number of elements. Furthermore, it has been concluded that the problem of checking necessary efficiency is co-NP-complete even for the case of only one objective function. In this paper, we explore new conditions for testing necessarily/possibly efficiency of basic non-degenerate solutions in IMOLP problems. We show properties of the necessarily efficient solutions in connection with possibly and necessarily optimal solutions to the related single objective problems. Moreover, we utilize the tolerance approach and sensitivity analysis for testing the necessary efficiency.