A common formula to compute the efficient sets of a class of multiple objective linear programming problems

Abstract

Finding the efficient set of a multiple objective linear programming (MOLP) problem is difficult and finding the efficient sets of many MOLP problems is still more difficult. In this paper, a common formula to compute the efficient sets of an arbitrary number of the MOLP problems corresponding to different right-hand side vectors is dealt with. We show that all the previously discovered methods and future methods for determining the efficient set of a MOLP problem which are not based on the efficient basic set of this MOLP problem cannot find such a common formula. In addition, our common formula is the union of the least number of descriptor sets for faces of the constraint polyhedrons among all possible common formulae for computing the efficient sets of the above MOLP problems. In order to increase the usefulness of the common formula, we give an efficient method for determining the efficient basic set of a MOLP problem. Some comparisons between our method and the methods for finding all extreme points of a convex polyhedral set in determining the efficient basic set of a MOLP problem are presented. A numerical example is given to illustrate the method.

Keywords:

• multiple objective programming
• maximal efficient faces
• efficient basic set

AMS Subject Classifications:

• 90C29
• 90C50
• 90C90

Acknowledgements

I am grateful to Professor Ferenc Forgó for his helpful comments and discussions along this work. I thank referees for their suggestions which greatly improved the presentation of the paper.