A New Method for Determining all Maximal Efficient Faces in Multiple Objective Linear Programming
- PDF / 607,758 Bytes
- 25 Pages / 439.642 x 666.49 pts Page_size
- 94 Downloads / 189 Views
A New Method for Determining all Maximal Efficient Faces in Multiple Objective Linear Programming Ta Van Tu1
Received: 30 April 2015 / Revised: 6 September 2015 / Accepted: 9 September 2015 © Institute of Mathematics, Vietnam Academy of Science and Technology (VAST) and Springer Science+Business Media Singapore 2016
Abstract Most of the known methods for finding the efficient set of a multiple objective linear programming (MOLP) problem are bottom-up search methods. Main difficulties of the known bottom-up search methods are to find all efficient extreme points adjacent to and to enumerate all efficient faces incident to an efficient degenerate extreme point. Main drawbacks of these methods are that the computational cost is still large and an implementation of them is still difficult. In this paper we propose a new local bottom-up search method for finding all maximal efficient faces for an MOLP problem. Our method is based on the maximal descriptor index sets for efficient edges and extreme rays for the MOLP problem in which the maximal descriptor index sets for edges and extreme rays incident to an efficient degenerate extreme point are easily found on the basis of solving some special linear programming problems. In addition, all efficient extreme points adjacent to and all efficient faces incident to an efficient extreme point can be easily found without using the simplex tables corresponding to bases of this point. Our method can overcome difficulties caused by the degeneracy of faces and is easy to implement. Some comparisons of our method with the known bottom-up search methods are presented. A numerical example is given to illustrate the method. Keywords Multiple objective programming · Maximal efficient face · Maximal descriptor index set for a face Mathematics Subject Classification (2010) 90C29 · 90C90
Ta Van Tu
t [email protected] 1
Department of Operations Research, Corvinus University of Budapest, 1093 Budapest, Hungary
T. V. Tu
1 Introduction We consider a multiple objective linear programming (MOLP) problem “maximize” Cx, (1) Ax ≤ b, (2) where x ∈ R n , b ∈ R m , A and C are m × n and k × n matrices, respectively and polyhedron (2) has at least one extreme point. For brevity of presentation we shall use the following notation: For two vectors a = (a1 , . . . , an )T and b = (b1 , . . . , bn )T , a ≤ b if and only if ai ≤ bi for all i = 1, . . . , n, where T denotes matrix transposition; for two subsets 1 and 2 of a set, 1 ⊂ 2 if and only if 1 ⊆ 2 and 1 = 2 . Let L be the feasible set of problem (1)–(2). A point x 0 ∈ L is said to be efficient for problem (1)–(2) if there is no x 1 ∈ L such that Cx 0 ≤ Cx 1 and Cx 0 = Cx 1 . The set of all efficient points for problem (1)–(2) is called an efficient set of it and denoted by E. A nonempty subset F of the polyhedron L is said to be a face of L if there is a subset I of {1, . . . , m} such that F = S(I ) , where S(I ) = {x ∈ L | ai x = bi ∀i ∈ I } (3) and (ai , bi ) is the ith row of the matrix (A, b). Such a set I is called a descrip
Data Loading...
