A Proposal to the Solution of Multiobjective Linear Fractional Programming Problem
Abstract
We have proposed a new solution to the Multiobjective Linear Fractional Programming Problem (MOLFPP). The proposed solution is based on a theorem that deals with nonlinear fractional programming with single objective function and studied in the work by Dinkelbach, 1967. As a new contribution, we have proposed that is an efficient solution of MOLFPP if is an optimal solution of problem , where is for all i. Hence, MOLFPP is simply reduced to linear programming problem (LPP). Some numerical examples are provided in order to illustrate the applications of the proposed method. The optimization software package, namely, WinQSB (Chang, 2001), has been employed in the computations.
1. Introduction
Fractional programming concerns with the optimization problem of one or several ratios of functions subject to some constraints. These ratios are quantities that measure the efficiency of system, such as cost/profit, cost/time, cost/volume, and output/worker, while several ratios of functions are measured in different scales at the existence of some conflicts. The optimal solution for an objective function may not be an optimal solution for some other objective functions. Therefore, one needs to find the notion of the best compromise solution, also known as nondominant solution [1, 2].
In the literature, for various types of fractional programming, there are many different sorts of studies; some of them deal with theory [3–6], and some of them concern with solution methods [2, 7–18] and applications [19]. Dinkelbach [7] presented the algorithm based on a theorem by Jagannathan [20] concerning the relationship between fractional and parametric programming and restated and proved this theorem in somewhat simpler way. Leber et al. proposed [19] to use a fractional programming algorithm (the Dinkelbach algorithm) to calculate the melting temperature of pairings of two single DNA strands in biology.
If both the numerator and dominator of these ratios of functions in fractional programming are linear functions under some technological linear restrictions, then we have the multiple objective linear fractional programming (MOLFP) problems. There are so many studies including different approaches to solve different models of MOLFP problems in literature. Kornbluth and Steuer [21] proposed some possible linear fractional criteria [1] and have presented a generalized approach for solving a goal programming with linear fractional criteria [22]. Luhandjula [23] proposed a linguistic variable approach to solve a MOLFP problem. This approach simply and adequately describes imprecise aspirations of the decision maker to obtain a solution that is in some sense good in his/her opinion. These linguistic descriptions are considered as fuzzy objectives and are aggregated as in fuzzy linear programming [1].
Dutta et al. [24] modified the linguistic approach of Luhandjula such as to develop a method which yields always an efficient solution for optimising MOLFP problem. Stancu-Minasian and Pop [2] pointed out certain shortcomings in the work of Dutta et al. and have given the correct proof of theorem, which validates the obtaining of the efficient solutions. Lee and Tcha [25] developed iterative solution method to generate a sequence of linear inequality problems by parameterizing objective values to obtain a compromise solution of MOLFP problem. Chakraborty and Gupta [22] have presented a different methodology that always yields an efficient solution for solving MOLFP problem. In this methodology, MOLFPP may be solved easily with the transformation y = tx, t > 0 resulting in a multiple objective linear programming (MOLP) problem. t has been considered as the least value of both 1/Di(x) if objective function Zi(x) ≥ 0 for some x in the feasible region and 1/ − Ni(x) if objective function Zi(x) < 0, for each x in the feasible region. After original MOLFP problem reduces to an equivalent MOLP problem, the resulting MOLP problem is solved using fuzzy set theoretical approach by suitably defined membership functions and using min operator introduced by Zimmerman.
In this paper, we have investigated a solution to the MOLFP problem based on a theorem previously studied by Dinkelbach [7]. We have proposed that a feasible solution of MOLFPP is an efficient solution of MOLFPP if is an optimal solution of problem , where is for all i. Thus, MOLFPP is reduced to linear programming problem (LPP), and its solution procedure can be easily applied.
1.1. Linear Fractional Programming Problem (LFPP)
cT, dT ∈ Rn, α, β ∈ R are assumed to be nonempty convex and compact set in Rn.
Theorem 1. Consider
For some ξ ∈ X, N(ξ) ≥ 0, if (2a) reaches a (global) maximum at x = x*, then (2b) reaches a (global) maximum at point (t, y) = (t*, y*), where y*/t* = x*and the objective functions at these points are equal [22, 26].
Theorem 2 (see [22], [26].)If (2a) is a standard concave-convex fractional programming problem which reaches a (global) maximum at point x*, then the corresponding transformed problem (2b) attains the same maximum value at a point (t*, y*), where y*/t* = x*. Moreover (2b) has a concave objective function and a convex feasible set.
Theorem 3 (see [7].)z* = N(x*)/D(x*) = max{N(x)/D(x)∣x ∈ X} if and only if F(z*, x*) = max {N(x) − z*D(x)∣x ∈ X} = 0.
2. Proposed Approach for Objective Functions of MOLFP Problem
Definition 4. is an efficient solution of MOLFP if there is no such that , i = 1,2, …, k, , for at least one i.
In this study, in order to solve MOLFP problem in (3), we can maximize each objective function Zi(x) subject to the given set of constraints using one of the methods proposed for single fractional objective function in [27] or others. Let and be the global maximum points and values of each objective function Max {Zi(x) = (cix + αi)/(dix + βi)| x ∈ X} for all i = 1,2, …, k. Now, we can prove that the solution is an efficient solution of Max {Zi(x) = (cix + αi)/(dix + βi), i = 1,2, …, k∣x ∈ X}.
If is an optimal solution of problem: , where is for all i = 1,2, …, k.
Let maximise problem ; then we can write inequality for any feasible solution x ∈ X. Hence,
From these inequalities, one obtains , for all i, x ∈ X.
We have for all i:
Both via Theorem 3 and the inequality , one can write that for all i. If maximise the problem , then it is an efficient solution of Max {Zi(x) = (cix + αi)/(dix + βi), i = 1,2, …, k ∣x ∈ X}. Now, assume that is not an efficient of MOLFPP; then there exists a feasible solution x of MOLFPP and for all i and at least one j, where . It follows that , for all i and at least one j. Summing the k-inequalities, we have . This inequality leads to a contradiction.
Thus, we have made a proposal for the solution of MOLFP based on the above proof. These examples considered by Chakraborty and Gupta in [22] use Zimmermann’s min operator for the fuzzy model.
3. Numerical Examples
Example 1. Let us consider a MOLFPP with two objectives as follows:
It is observed that Z1 < 0, Z2 ≥ 0, for each x in the feasible region:
This MOLFPP is equivalent to the following LPP. The given MOLFP problem can be written as
The solution of the ealier linear programming problem is obtained as x1 = 3, x2 = 2.
The solution for original problem is given by
Example 2. Let us consider a MOLFPP with three objectives as follows:
It is observed that Z1 < 0, Z2 ≥ 0, Z3 ≥ 0 for each x in the feasible region. These values are −53/26 ≤ Z1 ≤ −14/23, 139/121 ≤ Z2 ≤ 23/17, and 8/17 ≤ Z3 ≤ 14/17.
The earlier MOLFP problem is equivalent to the following LP problem:
The solution of the above linear programming problem is obtained as x1 = 3, x2 = 2. The solution for the given MOLFP problem is given by
4. Conclusion
In this paper, we have presented a new solution to the Multiobjective Linear Fractional Programming Problem (MOLFPP). The solution is based on a theorem proposed in [7] dealing with nonlinear fractional programming with single objective function. With the help of this suggested approach, all of linear fractional objective functions of MOLFP problem become a single objective function. Furthermore the MOLFP problem is transformed into LPP. Thus, the complexity and the computations in solving MOLFP problem reduce in a certain amount. We used two numerical examples solved with different methods in [18, 22, 28].
Conflict of Interests
The author declares that there is no conflict of interests regarding the publication of this paper.
