# A Proposal to the Solution of Multiobjective Linear Fractional Programming Problem

Authors: Nuran Güzel
Journal: Abstract and Applied Analysis
 (2013)

---

## 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 thatx¯ is an efficient solution of MOLFPP if x¯ is an optimal solution of problem Maxx∈X∑i=1k(Ni(x)-Zi*Di(x)), where is Zi*=Ni(xi*)/Di(xi*) 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.


---

## Body

## 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 x- of MOLFPP is an efficient solution of MOLFPP if x-∈Rn is an optimal solution of problem Maxx∈X∑i=1k(Ni(x)-Zi*Di(x)), where is Zi*=Ni(xi*)/Di(xi*) 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)

The general LFPP is defined as follows:(1)MaximizeX∈xN(x)D(x).N(x)=cTx+α, D(x)=dTx+β are valued and continuous functions on X and dTx+β≠0 for all X and X={x∣Ax=b,x≥0}, x∈Rn, b∈Rm, A∈Rn×m.c
T
,
d
T
∈
R
n, α,β∈R are assumed to be nonempty convex and compact set in Rn.Theorem 1.
Consider(2a)MaxN(x)D(x)s.t.00Ax≤b,x≥0,x∈X={x∣Ax=b,x≥0}⟹D(x)>0.(2b)MaxtN(yt)s.t.0A(yt)-b≤0,00tD(yt)≤1,00t>0,y≥0.
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.


## 1.1. Linear Fractional Programming Problem (LFPP)

The general LFPP is defined as follows:(1)MaximizeX∈xN(x)D(x).N(x)=cTx+α, D(x)=dTx+β are valued and continuous functions on X and dTx+β≠0 for all X and X={x∣Ax=b,x≥0}, x∈Rn, b∈Rm, A∈Rn×m.c
T
,
d
T
∈
R
n, α,β∈R are assumed to be nonempty convex and compact set in Rn.Theorem 1.
Consider(2a)MaxN(x)D(x)s.t.00Ax≤b,x≥0,x∈X={x∣Ax=b,x≥0}⟹D(x)>0.(2b)MaxtN(yt)s.t.0A(yt)-b≤0,00tD(yt)≤1,00t>0,y≥0.
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

The vector-maximum Multiple Objective Linear Fractional programming (MOLFP) problem is defined as follows:(3)Maximize{Z(x)=(N1(x)D1(x),N2(x)D2(x),…,00000000000000000Nk(x)Dk(x))∣x∈X},
where X={x∈Rn/Ax≤b,x≥0} is convex and nonempty bounded set, A is an m×n constraint matrix, x is an n-dimensional vector of decision variable, and b∈Rm, k≥2,  Ni(x)=ciTx+αi, Di(x)=diTx+βi,  for all i=1,…,k, ciT,diT∈Rn, αi,βi∈R,  for all i=1,…,k,  Di(x)=dix+βi>0, for all i=1,…,k, for all x∈X.Definition 4.
x
-
∈
R
n is an efficient solution of MOLFP if there is no x^∈Rn such that Ni(x^)/Di(x^)≥Ni(x-)/Di(x-), i=1,2,…,k, Ni(x^)/Di(x^)>Ni(x-)/Di(x-), 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 xi* and Zi* 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 x- is an efficient solution of Max{Zi(x)=(cix+αi)/(dix+βi),i=1,2,…,k∣x∈X}.
Ifx- is an optimal solution of problem: Max{∑i=1k(Ni(x)-Zi*Di(x)),∣x∈X}, where is Zi*=Ni(xi*)/Di(xi*) for all i=1,2,…,k.
Letx- maximise problem Max{∑i=1k(Ni(x)-Zi*Di(x))∣x∈X}; then we can write inequality ∑i=1k(Ni(x)-Zi*Di(x))≤∑i=1k(Ni(x-)-Zi*Di(x-)) for any feasible solution x∈X. Hence,
(4)∑i=1k(Ni(x)-Zi*Di(x))≤∑i=1k(Ni(x-)-Zi*Di(x-))≤∑i=1kmax{Ni(x)-Zi*Di(x)}≤∑i=1k(Ni(xi*)-Zi*Di(xi*))=000000000000000000forx∈X.
From these inequalities, one obtainsNi(x)-Zi*Di(x)≤Ni(x-)-Zi*Di(x-)≤0, for all i, x∈X.
We haveDi(x)[Ni(x)/Di(x)-Zi*]≤Di(x-)[Ni(x-)/Di(x-)-Zi*] for all i:
(5)[Ni(x)Di(x)-Zi*]≤Di(x-)Di(x)[Ni(x-)Di(x-)-Zi*].
Both via Theorem3 and the inequality Di(x-)/Di(x)≥1, one can write that [Ni(x)/Di(x)-Zi*]≤[Ni(x-)/Di(x-)-Zi*]and[Ni(x)/Di(x)]≤[Ni(x-)/Di(x-)] for all i. If x- maximise the problem Max{∑i=1k(Ni(x)-Zi*Di(x))∣x∈X}, then it is an efficient solution of Max{Zi(x)=(cix+αi)/(dix+βi),i=1,2,…,k∣x∈X}. Now, assume that x- is not an efficient of MOLFPP; then there exists a feasible solution x of MOLFPP and Ni(x-)/Di(x-)≤Ni(x)/Di(x) for all  i and Nj(x-)/Dij(x-)<Nj(x)/Dj(x) at least one  j, where x,x-∈X. It follows that Ni(x-)/Di(x-)≤Ni(x)/Di(x)≤Z*, Ni(x-)-Zi*Di(x-)≤Ni(x)-Zi*Di(x) for all i and Nj(x-)-Zj*Di(x-)<Nj(x)-Zi*Di(x) at least one  j. Summing the k-inequalities, we have ∑i=1k(Ni(x)-Zi*Di(x))≤∑i=1k(Ni(x-)-Zi*Di(x-)). 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:(6)Max{Z1(x)=-3x1+2x2x1+x2+3,Z2(x)=7x1+x25x1+2x2+1}s.t.0x1-x2≥12x1+3x2≤15x1≥3x1,x2≥0.
It is observed thatZ1<0, Z2≥0, for each x in the feasible region:
(7)-157≤Z1≤-1423,139121≤Z2≤10577,
This MOLFPP is equivalent to the following LPP. The given MOLFP problem can be written as(8)Max{-3x1+2x2+1423(x1+x2+3)000000+7x1+x2-10577(5x1+2x2+1)},s.t.0x1-x2≥1,2x1+3x2≤15,x1≥3,x1,x2≥0.
The solution of the ealier linear programming problem is obtained asx1=3, x2=2.
The solution for original problem is given by(9)x1=3,x2=2,Z1=-58,Z2=2320.Example 2.
Let us consider a MOLFPP with three objectives as follows:(10)Max{Z1(x)=-3x1+2x2x1+x2+3,0000000Z2(x)=7x1+x25x1+2x2+1,0000000Z3(x)=x1+4x22x1+3x2+2},s.t.0x1-x2≥1,2x1+3x2≤15,x1+9x2≥9,x1≥3,x1,x2≥0.
It is observed thatZ1<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:(11)Max{-3x1+2x2-1423(x1+x2+3)0000000+7x1+x2-2317(5x1+2x2+1)+x10000000+4x2-1417(2x1+3x2+2)},s.t.0x1-x2≥12x1+3x2≤15x1+9x2≥9x1≥3.
The solution of the above linear programming problem is obtained asx1=3, x2=2. The solution for the given MOLFP problem is given by
(12)x1=3,x2=2,Z1=-58,Z2=2320,Z3=1114.


## 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].



---

*Source: 435030-2013-11-03.xml*