This paper presents a modification of one variant of Karmarkar's interior-point linearprogramming algorithm to multiobjective linear programming (MOLP) problems. We show that by taking the variant known as the af...
详细信息
This paper presents a modification of one variant of Karmarkar's interior-point linearprogramming algorithm to multiobjective linear programming (MOLP) problems. We show that by taking the variant known as the affine-scaling primal algorithm, generating locally-relevant scaling coefficients and applying them to the projected gradients produced by it, we can define what we refer to as anchoring points that then define cones in which we search for an optimal solution through interaction with the decision maker. Currently existing MOLP algorithms are simplex-based and make their progress toward the optimal solution by following the vertices of the constraints polytope. Since the proposed algorithm makes its progress through the interior of the constraints polytope, there is no need for vertex information and, therefore, the search for an optimal solution may prove less sensitive to problem size. We refer to the class of MOLP algorithms resulting from this variant as Affine-Scaling Interior multiobjective linear programming (ASIMOLP) algorithms.
In this paper, the concept of efficient solutions to the conventional multiobjective linear programming problems is extended to the fuzzy (possibilistic) coefficients case. Two kinds of efficient solution sets, i.e., ...
详细信息
In this paper, the concept of efficient solutions to the conventional multiobjective linear programming problems is extended to the fuzzy (possibilistic) coefficients case. Two kinds of efficient solution sets, i.e., a set of possibly efficient solutions and a set of necessarily efficient solutions, are defined as fuzzy sets whose membership grades represent the possibility and necessity degrees to which the solution is efficient. A test to check the possible efficiency is discussed when a feasible solution is given. To do this, we first consider the interval case, where all fuzzy (possibilistic) coefficients degenerate into interval coefficients. In this case, a set of possibly efficient solutions degenerates into a usual (crisp) set. A necessary and sufficient condition of the possible efficiency for the interval case is presented. This condition shows that the possible efficiency is checked by solving a system of linear inequalities. Extending this result to the fuzzy (possibilistic) case, the degree of possibility efficiency is obtained by solving a nonlinearprogramming problem. The nonlinearprogramming problem is solved by the simplex and bisection methods.
This paper develops a method for finding the whole set of efficient points of a multiobjectivelinear problem. Two algorithms are presented;the first one describes the set of all efficient vertices and all efficient r...
详细信息
This paper develops a method for finding the whole set of efficient points of a multiobjectivelinear problem. Two algorithms are presented;the first one describes the set of all efficient vertices and all efficient rays of the constraint polyhedron, while the second one generates the set of all efficient faces. The method has been tested on several examples for which numerical results are reported.
The current paper focuses on a multiobjective linear programming problem with interval objective functions coefficients. Taking into account the minimax regret criterion, an attempt is being made to propose a new solu...
详细信息
The current paper focuses on a multiobjective linear programming problem with interval objective functions coefficients. Taking into account the minimax regret criterion, an attempt is being made to propose a new solution i.e. minimax regret solution. With respect to its properties, a minimax regret solution is necessarily ideal when a necessarily ideal solution exists;otherwise it is still considered a possibly weak efficient solution. In order to obtain a minimax regret solution, an algorithm based on a relaxation procedure is suggested. A numerical example demonstrates the validity and strengths of the proposed algorithm. Finally, two special cases are investigated: the minimax regret solution for fixed objective functions coefficients as well as the minimax regret solution with a reference point. Some of the characteristic features of both cases are highlighted thereafter.
We consider a multiobjectivelinear program. We propose a procedure for computing all additive and multiplicative (percentage) tolerance in which all the objective function coefficients may simultaneously and independ...
详细信息
We consider a multiobjectivelinear program. We propose a procedure for computing all additive and multiplicative (percentage) tolerance in which all the objective function coefficients may simultaneously and independently vary while preserving the efficiency of a given solution. For a nondegenerate basic Solution, the procedure runs ill polynomial time. (C) 2007 Elsevier B.V. All rights reserved.
Optimization problems are often subject to various kinds of inexactness or inaccuracy of input data. Here, we consider multiobjective linear programming problems, in which two kinds of input entries have the form of i...
详细信息
Optimization problems are often subject to various kinds of inexactness or inaccuracy of input data. Here, we consider multiobjective linear programming problems, in which two kinds of input entries have the form of interval data. First, we suppose that the objectives entries are interval values, and, second, we suppose that we have an interval estimation of weights of the particular criteria. These two types of interval data naturally lead to various definitions of efficient solutions. We discuss six meaningful concepts of efficient solutions and compare them to each other. For each of them, we attempt to characterize the corresponding kind efficiency and investigate computational complexity of deciding whether a given solution is efficient.
Let a multiobjective linear programming problem and any efficient solution be given. Tolerance analysis aims to compute interval tolerances for (possibly all) objective function coefficients such that the efficient so...
详细信息
Let a multiobjective linear programming problem and any efficient solution be given. Tolerance analysis aims to compute interval tolerances for (possibly all) objective function coefficients such that the efficient solution remains efficient for any perturbation of the coefficients within the computed intervals. The known methods either yield tolerances that are not the maximal possible ones, or they consider perturbations of weights of the weighted sum scalarization only. We focus directly on perturbations of the objective function coefficients, which makes the approach independent on a scalarization technique used. In this paper, we propose a method for calculating the supremal tolerance (the maximal one need not exist). The main disadvantage of the method is the exponential running time in the worst case. Nevertheless, we show that the problem of determining the maximal/supremal tolerance is NP-hard, so an efficient (polynomial time) procedure is not likely to exist. We illustrate our approach on examples and present an application in transportation problems. Since the maximal tolerance may be small, we extend the notion to individual lower and upper tolerances for each objective function coefficient. An algorithm for computing maximal individual tolerances is proposed. (C) 2013 Elsevier B.V. All rights reserved.
We develop a primal-dual simplex algorithm for multicriteria linearprogramming. It is based on the scalarization theorem of Pareto optimal solutions of multicriteria linear programs and the single objective primal-du...
详细信息
We develop a primal-dual simplex algorithm for multicriteria linearprogramming. It is based on the scalarization theorem of Pareto optimal solutions of multicriteria linear programs and the single objective primal-dual simplex algorithm. We illustrate the algorithm by an example, present some numerical results, give some further details on special cases and point out future research.
We propose an interactive interior point method for finding the best compromise solution to a multiple objective linearprogramming problem. We construct a sequence X-0,X-1,...,X-k,... of smaller and smaller polytopes...
详细信息
We propose an interactive interior point method for finding the best compromise solution to a multiple objective linearprogramming problem. We construct a sequence X-0,X-1,...,X-k,... of smaller and smaller polytopes which shrink towards the compromise solution. During the kth iteration, we move from the center of polytope Xk-1 to the center of polytope X-k by performing a local optimization which consists of maximizing a linear function over an ellipsoid. (C) 2001 Elsevier Science B.V. All rights reserved.
We present some complexity results on checking necessary efficiency in interval multiobjective linear programming. Supposing that objective function coefficients perturb within prescribed intervals, a feasible point x...
详细信息
We present some complexity results on checking necessary efficiency in interval multiobjective linear programming. Supposing that objective function coefficients perturb within prescribed intervals, a feasible point x* is called necessarily efficient if it is efficient for all instances of interval data. We show that the problem of checking necessary efficiency is co-NP-complete even for the case of only one objective. Provided that x* is a non-degenerate basic solution, the problem is polynomially solvable for one objective, but remains co-NP-hard in the general case. Some open problems are mentioned at the end of the paper.
暂无评论