# Interior Point Method for Solving Fuzzy Number Linear Programming Problems Using Linear Ranking Function

Authors: Yi-hua Zhong; Yan-lin Jia; Dandan Chen; Yan Yang
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Recently, various methods have been developed for solving linear programming problems with fuzzy number, such as simplex method and dual simplex method. But their computational complexities are exponential, which is not satisfactory for solving large-scale fuzzy linear programming problems, especially in the engineering field. A new method which can solve large-scale fuzzy number linear programming problems is presented in this paper, which is named a revised interior point method. Its idea is similar to that of interior point method used for solving linear programming problems in crisp environment before, but its feasible direction and step size are chosen by using trapezoidal fuzzy numbers, linear ranking function, fuzzy vector, and their operations, and its end condition is involved in linear ranking function. Their correctness and rationality are proved. Moreover, choice of the initial interior point and some factors influencing the results of this method are also discussed and analyzed. The result of algorithm analysis and example study that shows proper safety factor parameter, accuracy parameter, and initial interior point of this method may reduce iterations and they can be selected easily according to the actual needs. Finally, the method proposed in this paper is an alternative method for  solving fuzzy number linear programming problems.


---

## Body

## 1. Introduction

Linear programming is one of the most widely used decision-making tools for solving real-word problems. However, real word situations are characterized by imprecision rather than exactness. Then, fuzzy linear programming (FLP) has been developed to treat uncertainty of optimization problems, such as fuzzy data envelopment analysis and fuzzy network optimization [1–3]. Since 1970, various attempts have been made to study FLP problem [4–32]. The concept of FLP was first proposed by Tanaka et al. [4] in the framework of the fuzzy decision of Bellman and Zadeh [5]. For solving FLP, defuzzification methods have been widely studied for some years and applied to fuzzy control and fuzzy expert systems. The most common transforming method is ranking fuzzy numbers method, which is to establish a one-to-one correspondence between fuzzy numbers and real numbers according to the definite rule. Then, every fuzzy number is mapped to a point on the real line. Ranking is a viable approach for ordering fuzzy numbers. A special version of ranking function was first proposed by Yager [33].Then, many researchers have considered various kinds of FLP problems and have proposed some approaches for solving these problems [8–28]. Maleki et al., Ganesan and Veeramani, and Nasseri et al. [8–12] presented simplex methods for solving fuzzy number linear programming (FNLP) and linear programming with fuzzy variables (FVLP) using the concept of comparison of fuzzy numbers and linear ranking function. This method is similar to the simplex method that was used for solving linear programming problems in crisp environment. Nasseri and Khabiri [13] proposed a revised simplex algorithm for FVLP, which is useful for sensitivity analysis on FVLP. Furthermore, there is a revised simplex algorithm for FNLP problems using linear ranking function proposed [14], which is useful for sensitivity analysis on FNLP. Nasseri et al. [15] considered a kind of linear programming which includes the triangular fuzzy numbers in its parameters and proposed a revised simplex algorithm for an extended linear programming problem which is equivalent to the original fuzzy linear programming problem. Ebrahimnejad [16] obtained some new results in FLP and gave a new method to obtain an initial fuzzy basic feasible solution for solving FLP problems. Nasseri and Alizadeh [17] thought that finding a basic feasible solution (BFS) is not straightforward and some works to make the simplex algorithm start might be needed, so they proposed a penalty method to solve FVLP problems in which the BFS is not readily available. Ebrahimnejad et al. [18] proposed a new method for bounded linear programming with fuzzy cost coefficients called the bounded fuzzy primal simplex algorithm. Some scholars [19–25] studied duality in FLP. Mahdavi-Amiri, Nasseri and Ebrahimnejad presented the dual simplex algorithm for solving FNLP problem [19, 20] and the dual simplex algorithm for FVLP problem [21]. Ebrahimnejad et al. [22] introduced another efficient method, primal-dual simplex algorithm, to obtain a fuzzy solution of FVLP problem. Ebrahimnejad and Nasseri [23] studied dual simplex algorithm for bounded linear programming with fuzzy numbers. Ebrahimnejad and Nasseri [24] defined a new dual problem for the linear programming problem with trapezoidal fuzzy variables as a linear programming problem with trapezoidal fuzzy variables and deduced the duality results such as weak duality, strong duality, and complementary slackness theorems. Nasseri et al. [25] established the dual of a linear programming problem with symmetric trapezoidal fuzzy numbers, where the coefficients and variables are symmetric trapezoidal fuzzy numbers, and developed some duality results for the fuzzy primal and fuzzy dual problems. Ebrahimnejad and Nasseri [26] used the complementary slackness to solve FNLP and FVLP problems without the need of a simplex tableau. Sigarpich et al. [27] gave a new method for solving the degeneracy in linear programming problems with fuzzy variables by a definite linear function for ranking symmetric triangular fuzzy numbers. Chanas [28] presented the possibility of the identification of a complete fuzzy decision in fuzzy linear programming by use of the parametric programming technique.Sensitivity analysis is a basic tool for studying perturbations in optimization problems. There is considerable research on sensitivity analysis for some models of operations research and management science such as linear programming and investment analysis. So, many scholars studied the sensitivity analysis for FVLP [29–31] and FNLP [32]. They considered the following variations: change in the cost vector, change in the right-hand side vector, change in the constraint matrix, addition of a new activity (trapezoidal fuzzy variable), and addition of a new constraint.In a word, existing methods solving FNLP problems are mainly using the concept of comparison of fuzzy numbers and linear ranking function to change the fuzzy number into crisp number, using simplex method and its revised method to solve these FNLP problems. Because the time complexity of simplex methods [10, 11] or revised simplex algorithm [14] is exponential, its iterations will increase rapidly with increasing the number of decision-making variables and constraint conditions. This paper wants to propose a new interior point method to improve the efficiency of solving large-scale FNLP problems, which will revise the feasible direction and step size as well as terminate condition in common interior point method by using trapezoidal fuzzy numbers, linear ranking function, fuzzy vector, and their operations.This paper is organized as follows. We demonstrate some preliminaries of fuzzy set theory and the concept of ranking functions in Section2. The simplex method for solving FNLP will be reviewed in Section 3. A new interior point method for solving FNLP will be proposed in Section 4. Example study and algorithm analysis will be shown in Section 5. Finally, we will allocate the Section 6 to conclusions.


## 2. Preliminaries

In this section, we review some necessary concepts of fuzzy set theory and the ranking function and then present some definition about fuzzy vectors.Definition 1 (see [5, 19]).
A convex fuzzy setA~ on R is a fuzzy number if the following conditions hold.(i)
Its membership function is piecewise continuous.(ii)
There exist three intervals[a,b], [b,c], and [c,d] such that μA~ is increasing on [a,b], equal to 1 on [b,c], decreasing on [c,d], and equal to 0 elsewhere.Definition 2 (see [5, 19]).
LetA~=(aL,aU,α,β) denote the trapezoidal fuzzy number, where (aL-α,aU+β) is the support of A~ and [aL,aU] is its core.Remark 3.
We denote the set of all trapezoidal fuzzy numbers byF(R).Theorem 4 (see [5, 19]).
Ifa~=(aL,aU,α,β) and b~=(bL,bU,γ,θ) are two trapezoidal fuzzy numbers, then(i)
for anyx>0,  x∈R, xa~=(xaL,xaU,xα,xβ),(ii)
for anyx<0,  x∈R, xa~=(xaU,xaL,-xβ,-xα),(iii)
a~+b~=(aL+bL,aU+bU,α+γ,β+θ).Definition 5 (see [34]).
The functionℛ:F(R)→R which maps each fuzzy number into the real line is called a ranking function, where a natural order exists.Theorem 6 (see [34]).
Ifa~,b~∈F(R), then(i)
a~≥ℛb~ if and only if ℛ(a~)≥ℛ(b~);(ii)
a~>ℛb~ if and only if ℛ(a~)>ℛ(b~);(iii)
a~=ℛb~ if and only if ℛ(a~)=ℛ(b~);(iv)
a~≤ℛb~ if and only if ℛ(a~)≤ℛ(b~).Definition 7 (see [34]).
If a ranking functionℛ such that
(1)ℛ(ka~+b~)=kℛ(a~)+ℛ(b~)
for any a~,b~∈F(R),  k∈R, then ℛ is a linear ranking function on F(R).Theorem 8 (see [33]).
The forms of linear ranking functions onF(R) are often given as follows:(i)
ℛ(a~)=cLaL+cUaU+cαα+cββ, where a~=(aL,aU,α,β) and cL,  cU,  cα,  cβ are constants, at least one of which is nonzero;(ii)
ℛ(a~)=(1/2)∫01‍(infa~λ+supa~λ)dλ, that is, reduced to
(2)ℛ(a~)=aL+aU2+14(β-α).Corollary 9 (see [34]).
For any trapezoidal fuzzy numbera~, the relation a~≥0~ holds if there exist ε≥0 and α≥0 such that a~≥ℛ(-ε,ε,α,α). One realizes that ℛ(-ε,ε,α,α)=0 (one also consider that a~=ℛ0~ if and only if ℛ(a~)=0). Thus, without loss of generality, throughout the paper one lets 0~=(0,0,0,0) as the zero trapezoidal fuzzy number.Corollary 10 (see [34]).
For any two trapezoidal fuzzy numbersa~=(aL,aU,α,β) and b~=(bL,bU,γ,θ), a~≥ℛb~ if and only if aL+aU+(1/2)(β-α)≥bL+bU+(1/2)(θ-γ).Definition 11.
Afuzzy vector of n dimension on F(R) is an n-tuple on F(R): c~=(c~1,c~2,…,c~n), where the fuzzy number c~i is called the ith component of it, 1≤i≤n.Definition 12.
Letc~=(c~1,c~2,…,c~n) and d~=(d~1,d~2,…,d~n) be two fuzzy vectors whose sum is defined as
(3)c~+d~=(c~1+d~1,c~2+d~2,…,c~n+d~n).Remark 13.
It is quite easy to get the following rules:(i)
commutativity:c~+d~=d~+c~;(ii)
associativity:(c~+d~)+e~=c~+(d~+e~);(iii)
neutral Element:0~+c~=c~+0~=c~.Definition 14.
Leta∈R,  c~=(c~1,c~2,…,c~n) be a fuzzy vector; scalar multiplication of c~ by a is defined as
(4)ac~=(ac~1,ac~2,…,ac~n).Remark 15.
It is quite easy to get the following rules:(i)
distributivity over fuzzy vectors:a(c~+d~)=ac~+ad~;(ii)
distributivity over number:(a+b)c~=ℛac~+bc~.Definition 16.
Letc~=(c~1,c~2,…,c~n); ranking function operation of c~ is defined as
(5)ℛ(c~)=(ℛ(c~1),ℛ(c~2),…,ℛ(c~n)).Remark 17.
It is quite easy to obtain(6)ℛ(kc~+d~)=kℛ(c~)+ℛ(d~),
where c~,d~∈(F(R))n and k∈R.Definition 18.
Leta=(a1,a2,…,an),  c~=(c~1,c~2,…,c~n); vector multiplication of c~ by a is defined as
(7)ac~T=(a1,a2,…,an)(c~1,c~2,…,c~n)T=∑i=1n‍aic~i.


## 3. Simplex Method for Solving Fuzzy Number Linear Programming

In this section, we recall the definition of FNLP and the fuzzy primal simplex algorithm to FNLP.Definition 19 (see [11, 19]).
AnFNLP problem is defined as follows
(8)maxz~=ℛc~Txs.t.Ax≤b,s.t.x≥0,
where b∈Rm,  x∈Rn,  A∈Rm×n,  c~∈(F(R))n, and ℛ is a linear ranking function.Remark 20.
There is another equivalent form of (8) as follows:
(9)maxz~=ℛc~Txs.t.Ax≤b,
where A∈R(m+n)×n and the other symbols are the same as in (8).Algorithm 21 (see [11]).
The fuzzy primal simplex algorithm.Assumption.  A basic feasible solution with basis B and the corresponding simplex tableau is at hand.(i)
The basic feasible solution is given byxB=B-1b and xN=0. The fuzzy objective value is z~=ℛ(c~BxB).(ii)
Letz~k-c~k=minj{z~j-c~j},  j=1,…,n,  j≠Bi,  i=1,…m. If z~k-c~k≥ℛ0; then stop. The current solution is optimal; else go to step (iii).(iii)
Ifyk≤0, then stop; the problem is unbounded. Otherwise determine the index of the variable xBr leaving the basis as follows:
(10)bryrk=min1≤i≤m{biyik∣yik>0}.(iv)
Pivot onyrk and update the simplex tableau. Go to step (ii).Remark 22.
The idea of this algorithm is to start from a vertex; each step of its iteration is moving to a better vertex until the optimal solution is found or infeasible solution is proved.In Algorithm21, searching adjacent vertexes is just only along the edge, and each iteration calculation is very small. But simplex method should go a long way to reach the optimal solution along the feasible region boundary through almost each vertex. For the feasible region of the large-scale application, a problem may have a lot of vertexes, this “boundary method” will encounter the problem of huge calculation generating by iteration. In order to reduce the iterations, alternative method is moving along the “short path” in internal of the feasible region. However, the usual interior point method always needs to consider all the feasible directions in each step of iteration in order to find the best one.Fortunately, we know that Karmarkar’s interior point method [35] is not searching forward along the surface of the feasible region but directly approaching to the optimal solution along search directions in the internal of the feasible region. But this method cannot be used directly to solve FNLP problems. So, in the next section, we will propose a revised interior point method, which can be used directly to solve FNLP problem.


## 4. A Revised Interior Point Method for Solving Fuzzy Number Linear Programming

In this section, we propose a revised interior-point method to solve FNLP problem.


### 4.1. The Idea of Revised Interior Point Method

The basic idea of revised interior point is first starting from an interior pointx0 and getting a subsequent point to increase objective function value along the feasible direction, then starting from this interior point, and getting a new subsequent point to make objective function value increase along other feasible direction. Repeating the previous steps will produce a sequence of point {xk} which is subject to c~Txk+1≥ℛc~Txk, where c~Txk+1≥ℛc~Txk are the operations of ranking function and fuzzy vector. When the iteration is subjected to termination criterion, it will stop. The key of this method is choosing a feasible direction to improve objective function value.


### 4.2. The Derivation of Computational Formula

Combined with the slack variablev, the problem (9) is converted into the following form:
(11)maxz~=ℛc~Txs.t.Ax+v=b,s.t.v≥0.In thekth iteration, define vk≥0,  vk∈Rm, subject to vk=b-Axk. Then, define the diagonal matrix Dk=diag(1/V1k,1/V2k,…,1/Vmk).Letw=Dkv, problem (11) is changed as follows:
(12)maxz~=ℛc~Txs.t.Ax+Dk-1w=b,s.t.w≥0.
Choose the search direction d=[dxdw]T; then it must be one solution of the following equation:
(13)DkAdx+dw=0,(14)ATDk(DkAdx+dw)=0,dx=-(ATDk2A)-1ATDkdw.
Then,
(15)c~Tdx=ℛc~T[-(ATDk2A)-1ATDkdw]=ℛ-[DkA(ATDk2A)-1c~]Tdw.
To maximize c~Tdx, that is to say, maximize ℛ(c~Tdx), combined with (6) and (7), then
(16)dw=-ℛ(DkA(ATDk2A)-1c~)=-DkA(ATDk2A)-1ℛ(c~).
From (13) and (16), we get
(17)dx=(ATDk2A)-1ℛ(c~).
From w=Dkv,
(18)dv=Dk-1dw=-A(ATDk2A)-1ℛ(c~)=-Adx.
After getting the search direction dx, we need to determine the step size. Let
(19)xk+1=xk+λdx,
where the step size λ should guarantee that point xk+1 is in the feasible region; it should satisfy the following inequalities:
(20)A(xk+λdx)<b,λAdx<b-Axk,-λdv<vk.
Let
(21)α=min{Vik-(dv)i∣(dv)i<0,i∈(1,2,…,m)}.
Take
(22)λ=γα,
where γ∈(0,1). Then, we can get xk+1 from xk along the direction dx, where c~Txk+1>ℛc~Txk.


### 4.3. Steps of the Revised Interior Point Algorithm

From the idea of revised interior point method and the derivation of calculation formula, steps of the revised interior point algorithm to solve model (9) are shown as follows.Step 1.
Give an initial interior pointx0, a safety factor parameter γ∈(0,1), accuracy parameter ϵ>0, and iteration k=0.Step 2.
Compute(23)Vk=b-Axk.Step 3.
Set the diagonal matrix(24)Dk=diag(1V1k,1V2k,…,1Vmk).Step 4.
Using the vector multiplication of fuzzy vectors (7), compute
(25)d~x=(ATDk2A)-1·c~;
then combined with (6), (5) and (2), the feasible direction is
(26)ℛ(d~x)=(ATDk2A)-1ℛ(c~).Step 5.
Compute the vector(27)dV=-A·ℛ(d~x).Step 6.
Let(28)λ=γ·min{Vik-(dV)i∣(dV)i<0,i∈(1,2,…,m)}.Step 7.
Compute the next point:(29)xk+1=xk+λ·ℛ(d~x).Step 8.
Using the vector multiplication of fuzzy vectors (7) and ranking function (2), compare ℛ(c~Txk+1-c~Txk)/ℛ(c~Txk) with ϵ. If ℛ(c~Txk+1-c~Txk)/ℛ(c~Txk)<ϵ, then algorithm terminates and xk+1 is the optimal solution; else k∶=k+1, and go to Step 2.


### 4.4. Choice of the Initial Interior Point

Generally, setx0=(∥b∥/∥R(Ac~)∥)·R(c~) to be the initial interior point. And if V0=b-Ax0>0, then go to Step 2 in Section 4.3; otherwise formulate a new fuzzy number linear programming as follows:
(30)maxz~=ℛc~Tx+M~xas.t.Ax-xae≤b,
where M~>ℛ0~ is a big fuzzy number, e=(1,1,…,1)T and xa is artificial variable.And ifxa0>|min{(vi0)∣i=1,…,m}|, then (x0,xa0) must be the interior point of (30). Now, the problem (30) can be solved by the revised interior point method.Ifxak<0 in the kth iteration, stop solving the problem (30) and set xk to be the initial interior point of the problem (9).If there is the optimal solution of problem (30), and xak>0, then the problem (9) is not feasible.


## 4.1. The Idea of Revised Interior Point Method

The basic idea of revised interior point is first starting from an interior pointx0 and getting a subsequent point to increase objective function value along the feasible direction, then starting from this interior point, and getting a new subsequent point to make objective function value increase along other feasible direction. Repeating the previous steps will produce a sequence of point {xk} which is subject to c~Txk+1≥ℛc~Txk, where c~Txk+1≥ℛc~Txk are the operations of ranking function and fuzzy vector. When the iteration is subjected to termination criterion, it will stop. The key of this method is choosing a feasible direction to improve objective function value.


## 4.2. The Derivation of Computational Formula

Combined with the slack variablev, the problem (9) is converted into the following form:
(11)maxz~=ℛc~Txs.t.Ax+v=b,s.t.v≥0.In thekth iteration, define vk≥0,  vk∈Rm, subject to vk=b-Axk. Then, define the diagonal matrix Dk=diag(1/V1k,1/V2k,…,1/Vmk).Letw=Dkv, problem (11) is changed as follows:
(12)maxz~=ℛc~Txs.t.Ax+Dk-1w=b,s.t.w≥0.
Choose the search direction d=[dxdw]T; then it must be one solution of the following equation:
(13)DkAdx+dw=0,(14)ATDk(DkAdx+dw)=0,dx=-(ATDk2A)-1ATDkdw.
Then,
(15)c~Tdx=ℛc~T[-(ATDk2A)-1ATDkdw]=ℛ-[DkA(ATDk2A)-1c~]Tdw.
To maximize c~Tdx, that is to say, maximize ℛ(c~Tdx), combined with (6) and (7), then
(16)dw=-ℛ(DkA(ATDk2A)-1c~)=-DkA(ATDk2A)-1ℛ(c~).
From (13) and (16), we get
(17)dx=(ATDk2A)-1ℛ(c~).
From w=Dkv,
(18)dv=Dk-1dw=-A(ATDk2A)-1ℛ(c~)=-Adx.
After getting the search direction dx, we need to determine the step size. Let
(19)xk+1=xk+λdx,
where the step size λ should guarantee that point xk+1 is in the feasible region; it should satisfy the following inequalities:
(20)A(xk+λdx)<b,λAdx<b-Axk,-λdv<vk.
Let
(21)α=min{Vik-(dv)i∣(dv)i<0,i∈(1,2,…,m)}.
Take
(22)λ=γα,
where γ∈(0,1). Then, we can get xk+1 from xk along the direction dx, where c~Txk+1>ℛc~Txk.


## 4.3. Steps of the Revised Interior Point Algorithm

From the idea of revised interior point method and the derivation of calculation formula, steps of the revised interior point algorithm to solve model (9) are shown as follows.Step 1.
Give an initial interior pointx0, a safety factor parameter γ∈(0,1), accuracy parameter ϵ>0, and iteration k=0.Step 2.
Compute(23)Vk=b-Axk.Step 3.
Set the diagonal matrix(24)Dk=diag(1V1k,1V2k,…,1Vmk).Step 4.
Using the vector multiplication of fuzzy vectors (7), compute
(25)d~x=(ATDk2A)-1·c~;
then combined with (6), (5) and (2), the feasible direction is
(26)ℛ(d~x)=(ATDk2A)-1ℛ(c~).Step 5.
Compute the vector(27)dV=-A·ℛ(d~x).Step 6.
Let(28)λ=γ·min{Vik-(dV)i∣(dV)i<0,i∈(1,2,…,m)}.Step 7.
Compute the next point:(29)xk+1=xk+λ·ℛ(d~x).Step 8.
Using the vector multiplication of fuzzy vectors (7) and ranking function (2), compare ℛ(c~Txk+1-c~Txk)/ℛ(c~Txk) with ϵ. If ℛ(c~Txk+1-c~Txk)/ℛ(c~Txk)<ϵ, then algorithm terminates and xk+1 is the optimal solution; else k∶=k+1, and go to Step 2.


## 4.4. Choice of the Initial Interior Point

Generally, setx0=(∥b∥/∥R(Ac~)∥)·R(c~) to be the initial interior point. And if V0=b-Ax0>0, then go to Step 2 in Section 4.3; otherwise formulate a new fuzzy number linear programming as follows:
(30)maxz~=ℛc~Tx+M~xas.t.Ax-xae≤b,
where M~>ℛ0~ is a big fuzzy number, e=(1,1,…,1)T and xa is artificial variable.And ifxa0>|min{(vi0)∣i=1,…,m}|, then (x0,xa0) must be the interior point of (30). Now, the problem (30) can be solved by the revised interior point method.Ifxak<0 in the kth iteration, stop solving the problem (30) and set xk to be the initial interior point of the problem (9).If there is the optimal solution of problem (30), and xak>0, then the problem (9) is not feasible.


## 5. Algorithm Analysis and Example Study

In this section, first we analyze the algorithm. Then, an example in the practical production is given. At last, we analyze some factors influencing the results of this method through the given example.


### 5.1. Algorithm Analysis

The time complexity of simplex methods [10, 11] or revised simplex algorithm [14] is exponential. Generally speaking, the simplex method has the following shortcomings.(i)
Iterations are rising rapidly as the number of planning variables and constraints increasing.(ii)
The simplex method is terminated in optimal basis of original and dual programs. Although it has reached optimal solution in the degenerate case, it often needs to iterate the basis many times in order to prove that it is optimal.As we know, interior point methods (IPMs) are the most effective methods for solving a large-scale linear optimization problem. Since the creative work of Karmarkar [35], many researchers have proposed and analyzed various IPMs for LP and a large amount of results have been reported. And Karmarkar’s IPM has a polynomial time complexity and it approaches directly the optimal solution from the feasible region through the internal. Because the iteration of Karmarkar’s interior point algorithm is less changing as the number of planning variables and constraints increases, it is more outstanding to solve the large-scale FNLP problem by using the revised interior point method proposed in this paper.


### 5.2. Example Study

Question. Suppose a factory produces two products representing with 1 and 2; they are made by manual system and machine system in two shift works a day. The detailed relationship between production capacity and pure profit is shown in Table 1. The daily demand of users for the products 1 and 2 is 5 and 10, respectively. So, how to arrange production to get the maximum pure profit and meet users’ requirements?Table 1
The relationship among product demand, production capacity, and pure profit.
Product
Daily demand
Manual system
Machine system
Production capacity
Pure profit
Production capacity
Pure profit
Shift 1
Shift 2
Shift 1
Shift 2
1
5
3
(
8
,
10
,
2
,
6
)
(
10,12,1
,
17
)
4
(
6,8
,
1,5
)
(
9,11,1
,
5
)
2
10
5
(
3
,
5
,
1
,
5
)
(
4,6
,
2,6
)
7.5
(
2,4
,
2,6
)
(
4,7
,
1,3
)Remark 23.
In Table1, the measure unit of daily demand is ton, the measure unit of production capacity is tons per shift, and the measure unit of pure profit is thousand dollars per ton.Remark 24.
In Table1, the pure profit of each product in each shift is fuzzy. If its pure profit is about 10 after investigation, then it may be presented as a trapezoidal fuzzy number, that is (8,10,2,6).Solution.  (i) Letx1
: the output of product 1 in shift 1 produced by manual system;x2
: the output of product 1 in shift 2 produced by manual system;x3
: the output of product 2 in shift 1 produced by manual system;x4
: the output of product 2 in shift 2 produced by manual system;x5
: the output of product 1 in shift 1 produced by machine system;x6
: the output of product 1 in shift 2 produced by machine system;x7
: the output of product 2 in shift 1 produced by machine system;x8
: the output of product 2 in shift 2 produced by machine system.(ii) Now an FNLP model is established as follows:(31)maxz~=ℛ(8,10,2,6)x1+(10,12,1,17)x2+(3,5,1,5)x3maxz~=ℛ+(4,6,2,6)x4+(6,8,1,5)x5+(9,11,1,5)x6maxz~=ℛ+(2,4,2,6)x7+(4,7,1,3)x8s.t.x1+x2+x5+x6≤5s.t.x3+x4+x7+x8≤10s.t.x1≤3s.t.x2≤3s.t.x3≤5s.t.x4≤5s.t.x5≤4s.t.x6≤4s.t.x7≤7.5s.t.x8≤7.5s.t.5x1+3x3≤15s.t.5x2+3x4≤15s.t.15x5+8x7≤60s.t.15x6+8x8≤60s.t.xi≥0,i=1,2,…,8.Remark 25.
These inequalities5x1+3x3≤15,  5x2+3x4≤15,  15x5+8x7≤60,  and 15x6+8x8≤60 are simplified from x1/3+x3/5≤1,  x2/3+x4/5≤1,  x5/4+x7/7.5≤1,  and x6/4+x8/7.5≤1, respectively, which is convenient for the following computation.(iii) Then, solve the FNLP problem (31). If using simple method, it is complicated. So, we adopt the revised interior point method proposed in Section 4.3.Step 1.
Givenϵ=0.1,  x0=[1.72.91.90.10.20.10.77.1]T and γ=0.95,  k=0.Step 2.
ComputeVk=b-Axk,  k=0, then (32)V0=[0.10.21.30.13.14.93.83.974.367.90.80.251.41.71.72.91.90.10.20.10.77.1]T.Step 3.
Set the diagonal matrixDk=diag(1/V1k,1/V2k,…,1/Vmk),  k=0, then (33)D0=diag[1050.7692100.32260.20410.26320.25640.01350.01471.2550.01950.58820.58820.34480.5263105101.42860.1408].Step 4.
Computed~x=(ATDk2A)-1·c~,  k=0, then (34)d~x=[(0.99801.35320.23631.1384)(0.00160.00210.00040.0018)(-2.4963-1.82272.10010.4359)(-0.0158-0.01160.01330.0028)(-0.1704-0.12440.14330.0297)(-1.1411-0.83320.96000.1992)(-2.0983-1.53211.76520.3664)(3.49314.78410.83534.0247)].
Then combined with (5) and (2), the feasible direction is
(35)ℛ(d~x)=[1.401130.0022-2.57555-0.01633ℛ(d~x)-0.1758-1.17735-2.16494.93595]T.Step 5.
Compute the vectordV=-A·ℛ(d~x),  k=0; then (36)dV=[-0.0726-0.1531-0.0726-0.01550.03660.0112-0.00170.0102-0.0837-0.1172-0.2532-0.0439-0.6945-0.78410.07260.0155-0.0366-0.01120.0017-0.01020.08370.1172]T.Step 6.
Letλ=γ·min{Vik/[-(dV)i]∣(dV)i<0,i∈(1,2,…,m)},  k=0; then step size λ=1.1944.Step 7.
Computexk+1=xk+λ·ℛ(d~x),  k=0; then
(37)x1=[1.78672.91851.85630.08660.20200.08780.79997.24]T.Step 8.
Computeℛ(c~Txk+1-c~Txk)/ℛ(c~Txk)=4.2345>ϵ=0.1; then k=0+1=1 and go to Step 2. Repeat the similar calculation until ℛ(c~Txk+1-c~Txk)/ℛ(c~Txk)<ϵ=0.1, and get the results.Above all, the number of iteration is 5 and the results are listed in Table2.Table 2
The interior point value and the corresponding objective function value of each iteration.
Interior  point value
Objective  function value
1
[
1.7867
2.9185
1.8563
0.0866
0.2020
0.0878
0.7999
7.24
]
T
(81.9560119.151717.651098.1049)
2
[
1.8604
2.9674
1.8674
0.0432
0.1220
0.0463
0.6698
7.4085
]
T
(82.4542119.836217.558498.2900)
3
[
1.9628
2.9964
1.7165
0.0023
0.0369
0.0023
0.7878
7.4918
]
T
(82.6160120.096017.749798.7180)
4
[
1.9975
2.9984
1.6701
0.0019
0.0022
0.0019
0.8322
7.4949
]
T
(82.6559120.149017.830898.8179)
5
[
1.9980
2.9995
1.6694
0.0007
0.0017
0.0008
0.8314
7.4984
]
T
(82.6633120.161517.830098.8263)The optimal solution is[1.99802.99951.66940.00070.00170.00080.83147.4984]T and the optimal fuzzy value of the objective function is (82.6633120.161517.830098.8263). Then, the maximum pure profit is about ℛ(82.6633120.161517.830098.8263)=121.661475 thousand dollars.


### 5.3. Analysis of Factors Influencing This Method Results

Factors influencing the results of this method are mainly safety factor parameterγ, accuracy parameter ϵ, and initial interior point x0. Take model (31) as an example.(i)
Table3 focuses on the safety factor parameter γ, where the values of accuracy parameter ϵ and initial interior point x0 are fixed. All test problems show that the selection of a safety factor parameter plays a significant role in the fast convergence. We can see that the algorithm converges to the near-optimal solutions quickly as the safety factor parameter is increasing.(ii)
Table4 focuses on the accuracy parameter ϵ, where the values of safety factor parameter γ and initial interior point x0 are fixed. All test problems show that the selection of accuracy parameter plays a critical role in the fast convergence. We can see that the algorithm converges slowly to the near-optimal solutions as the safety factor parameter is decreasing. Even so, the final result is more accurate. The value of ϵ generally depends on the actual need. Therefore, this method can adjust precision to meet the requirement according to the actual need.(iii)
Table5 focuses on the initial interior point x0, where the values of safety factor parameter γ and accuracy parameter ϵ are fixed. All test problems show that the selection of an initial interior solution plays a significant role in the fast convergence. We can see that the algorithm converges to the near-optimal solutions quickly as the initial interior point is more and more close to the optimal solution. That is to say, the iteration is more and more small and tends to be a constant.(iv)
Table6 focuses on the safety factor parameter γ and accuracy parameter ϵ, where the values of initial interior point x0 is fixed. We can see that the iterations are smaller as the values of the accuracy parameter and safety factor parameter are increasing; the influence of safety factor parameter is more obvious than accuracy parameter to the iterations.Table 3
The influence of the safety factor parameterγ on iterations (ϵ=0.1, x0=[11111115]T).
Parameterγ
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0.95
IterationsK
75
40
27
20
16
13
11
10
9
9Table 4
The influence of the accuracy parameterϵ on iterations (γ=0.5, x0=[11111115]T).
Parameterϵ
0.9
0.5
0.1
0.01
0.005
0.001
IterationsK
9
10
13
16
17
19Table 5
The influence of the initial interior pointx0 on iterations (γ=0.5,ϵ=0.01).
Initial  interior point
IterationsK
Initial  interior point
IterationsK
[
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
]
T
33
[
1
1
1
1
1
1
1
4
]
T
16
[
1
0.5
0.1
0.1
0.1
0.1
0.1
0.1
]
T
31
[
1
1.9
2
1
0.7
1.1
1.9
4
]
T
15
[
1
1
0.1
0.1
0.1
0.1
0.1
1
]
T
26
[
1.1
2.5
2.2
0.4
0.5
0.6
1.1
5
]
T
14
[
1
0.5
0.5
0.5
0.5
0.5
0.5
0.5
]
T
21
[
1.4
2.7
2.2
0.2
0.3
0.3
0.8
6.6
]
T
13
[
1
1
0.5
0.5
0.5
0.5
0.5
0.5
]
T
20
[
1.5
2.7
2
0.1
0.3
0.2
0.8
6.7
]
T
13
[
1
1
0.5
0.5
0.5
0.5
1
1
]
T
19
[
1.6
2.8
2.1
0.1
0.2
0.2
0.6
7
]
T
12
[
1
1
1
1
1
1
1
1
]
T
18
[
1.6
2.8
2
0.1
0.2
0.2
0.7
6.9
]
T
12
[
1
1
1
1
1
1
1
2
]
T
17
[
1.7
2.9
1.9
0.1
0.2
0.1
0.7
7.1
]
T
11
[
1
1
1
1
1
1
1
3
]
T
16Table 6
The influence of the accuracy parameterϵ and safety factor parameter γ on iterations (x0=[11111115]T).
Parameterγ
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0.95
IterationsK
ϵ
=
0.1
52
29
20
16
13
11
9
8
8
7
ϵ
=
0.01
75
40
27
20
16
13
11
10
9
9
ϵ
=
0.001
97
50
33
25
19
16
13
12
11
11


## 5.1. Algorithm Analysis

The time complexity of simplex methods [10, 11] or revised simplex algorithm [14] is exponential. Generally speaking, the simplex method has the following shortcomings.(i)
Iterations are rising rapidly as the number of planning variables and constraints increasing.(ii)
The simplex method is terminated in optimal basis of original and dual programs. Although it has reached optimal solution in the degenerate case, it often needs to iterate the basis many times in order to prove that it is optimal.As we know, interior point methods (IPMs) are the most effective methods for solving a large-scale linear optimization problem. Since the creative work of Karmarkar [35], many researchers have proposed and analyzed various IPMs for LP and a large amount of results have been reported. And Karmarkar’s IPM has a polynomial time complexity and it approaches directly the optimal solution from the feasible region through the internal. Because the iteration of Karmarkar’s interior point algorithm is less changing as the number of planning variables and constraints increases, it is more outstanding to solve the large-scale FNLP problem by using the revised interior point method proposed in this paper.


## 5.2. Example Study

Question. Suppose a factory produces two products representing with 1 and 2; they are made by manual system and machine system in two shift works a day. The detailed relationship between production capacity and pure profit is shown in Table 1. The daily demand of users for the products 1 and 2 is 5 and 10, respectively. So, how to arrange production to get the maximum pure profit and meet users’ requirements?Table 1
The relationship among product demand, production capacity, and pure profit.
Product
Daily demand
Manual system
Machine system
Production capacity
Pure profit
Production capacity
Pure profit
Shift 1
Shift 2
Shift 1
Shift 2
1
5
3
(
8
,
10
,
2
,
6
)
(
10,12,1
,
17
)
4
(
6,8
,
1,5
)
(
9,11,1
,
5
)
2
10
5
(
3
,
5
,
1
,
5
)
(
4,6
,
2,6
)
7.5
(
2,4
,
2,6
)
(
4,7
,
1,3
)Remark 23.
In Table1, the measure unit of daily demand is ton, the measure unit of production capacity is tons per shift, and the measure unit of pure profit is thousand dollars per ton.Remark 24.
In Table1, the pure profit of each product in each shift is fuzzy. If its pure profit is about 10 after investigation, then it may be presented as a trapezoidal fuzzy number, that is (8,10,2,6).Solution.  (i) Letx1
: the output of product 1 in shift 1 produced by manual system;x2
: the output of product 1 in shift 2 produced by manual system;x3
: the output of product 2 in shift 1 produced by manual system;x4
: the output of product 2 in shift 2 produced by manual system;x5
: the output of product 1 in shift 1 produced by machine system;x6
: the output of product 1 in shift 2 produced by machine system;x7
: the output of product 2 in shift 1 produced by machine system;x8
: the output of product 2 in shift 2 produced by machine system.(ii) Now an FNLP model is established as follows:(31)maxz~=ℛ(8,10,2,6)x1+(10,12,1,17)x2+(3,5,1,5)x3maxz~=ℛ+(4,6,2,6)x4+(6,8,1,5)x5+(9,11,1,5)x6maxz~=ℛ+(2,4,2,6)x7+(4,7,1,3)x8s.t.x1+x2+x5+x6≤5s.t.x3+x4+x7+x8≤10s.t.x1≤3s.t.x2≤3s.t.x3≤5s.t.x4≤5s.t.x5≤4s.t.x6≤4s.t.x7≤7.5s.t.x8≤7.5s.t.5x1+3x3≤15s.t.5x2+3x4≤15s.t.15x5+8x7≤60s.t.15x6+8x8≤60s.t.xi≥0,i=1,2,…,8.Remark 25.
These inequalities5x1+3x3≤15,  5x2+3x4≤15,  15x5+8x7≤60,  and 15x6+8x8≤60 are simplified from x1/3+x3/5≤1,  x2/3+x4/5≤1,  x5/4+x7/7.5≤1,  and x6/4+x8/7.5≤1, respectively, which is convenient for the following computation.(iii) Then, solve the FNLP problem (31). If using simple method, it is complicated. So, we adopt the revised interior point method proposed in Section 4.3.Step 1.
Givenϵ=0.1,  x0=[1.72.91.90.10.20.10.77.1]T and γ=0.95,  k=0.Step 2.
ComputeVk=b-Axk,  k=0, then (32)V0=[0.10.21.30.13.14.93.83.974.367.90.80.251.41.71.72.91.90.10.20.10.77.1]T.Step 3.
Set the diagonal matrixDk=diag(1/V1k,1/V2k,…,1/Vmk),  k=0, then (33)D0=diag[1050.7692100.32260.20410.26320.25640.01350.01471.2550.01950.58820.58820.34480.5263105101.42860.1408].Step 4.
Computed~x=(ATDk2A)-1·c~,  k=0, then (34)d~x=[(0.99801.35320.23631.1384)(0.00160.00210.00040.0018)(-2.4963-1.82272.10010.4359)(-0.0158-0.01160.01330.0028)(-0.1704-0.12440.14330.0297)(-1.1411-0.83320.96000.1992)(-2.0983-1.53211.76520.3664)(3.49314.78410.83534.0247)].
Then combined with (5) and (2), the feasible direction is
(35)ℛ(d~x)=[1.401130.0022-2.57555-0.01633ℛ(d~x)-0.1758-1.17735-2.16494.93595]T.Step 5.
Compute the vectordV=-A·ℛ(d~x),  k=0; then (36)dV=[-0.0726-0.1531-0.0726-0.01550.03660.0112-0.00170.0102-0.0837-0.1172-0.2532-0.0439-0.6945-0.78410.07260.0155-0.0366-0.01120.0017-0.01020.08370.1172]T.Step 6.
Letλ=γ·min{Vik/[-(dV)i]∣(dV)i<0,i∈(1,2,…,m)},  k=0; then step size λ=1.1944.Step 7.
Computexk+1=xk+λ·ℛ(d~x),  k=0; then
(37)x1=[1.78672.91851.85630.08660.20200.08780.79997.24]T.Step 8.
Computeℛ(c~Txk+1-c~Txk)/ℛ(c~Txk)=4.2345>ϵ=0.1; then k=0+1=1 and go to Step 2. Repeat the similar calculation until ℛ(c~Txk+1-c~Txk)/ℛ(c~Txk)<ϵ=0.1, and get the results.Above all, the number of iteration is 5 and the results are listed in Table2.Table 2
The interior point value and the corresponding objective function value of each iteration.
Interior  point value
Objective  function value
1
[
1.7867
2.9185
1.8563
0.0866
0.2020
0.0878
0.7999
7.24
]
T
(81.9560119.151717.651098.1049)
2
[
1.8604
2.9674
1.8674
0.0432
0.1220
0.0463
0.6698
7.4085
]
T
(82.4542119.836217.558498.2900)
3
[
1.9628
2.9964
1.7165
0.0023
0.0369
0.0023
0.7878
7.4918
]
T
(82.6160120.096017.749798.7180)
4
[
1.9975
2.9984
1.6701
0.0019
0.0022
0.0019
0.8322
7.4949
]
T
(82.6559120.149017.830898.8179)
5
[
1.9980
2.9995
1.6694
0.0007
0.0017
0.0008
0.8314
7.4984
]
T
(82.6633120.161517.830098.8263)The optimal solution is[1.99802.99951.66940.00070.00170.00080.83147.4984]T and the optimal fuzzy value of the objective function is (82.6633120.161517.830098.8263). Then, the maximum pure profit is about ℛ(82.6633120.161517.830098.8263)=121.661475 thousand dollars.


## 5.3. Analysis of Factors Influencing This Method Results

Factors influencing the results of this method are mainly safety factor parameterγ, accuracy parameter ϵ, and initial interior point x0. Take model (31) as an example.(i)
Table3 focuses on the safety factor parameter γ, where the values of accuracy parameter ϵ and initial interior point x0 are fixed. All test problems show that the selection of a safety factor parameter plays a significant role in the fast convergence. We can see that the algorithm converges to the near-optimal solutions quickly as the safety factor parameter is increasing.(ii)
Table4 focuses on the accuracy parameter ϵ, where the values of safety factor parameter γ and initial interior point x0 are fixed. All test problems show that the selection of accuracy parameter plays a critical role in the fast convergence. We can see that the algorithm converges slowly to the near-optimal solutions as the safety factor parameter is decreasing. Even so, the final result is more accurate. The value of ϵ generally depends on the actual need. Therefore, this method can adjust precision to meet the requirement according to the actual need.(iii)
Table5 focuses on the initial interior point x0, where the values of safety factor parameter γ and accuracy parameter ϵ are fixed. All test problems show that the selection of an initial interior solution plays a significant role in the fast convergence. We can see that the algorithm converges to the near-optimal solutions quickly as the initial interior point is more and more close to the optimal solution. That is to say, the iteration is more and more small and tends to be a constant.(iv)
Table6 focuses on the safety factor parameter γ and accuracy parameter ϵ, where the values of initial interior point x0 is fixed. We can see that the iterations are smaller as the values of the accuracy parameter and safety factor parameter are increasing; the influence of safety factor parameter is more obvious than accuracy parameter to the iterations.Table 3
The influence of the safety factor parameterγ on iterations (ϵ=0.1, x0=[11111115]T).
Parameterγ
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0.95
IterationsK
75
40
27
20
16
13
11
10
9
9Table 4
The influence of the accuracy parameterϵ on iterations (γ=0.5, x0=[11111115]T).
Parameterϵ
0.9
0.5
0.1
0.01
0.005
0.001
IterationsK
9
10
13
16
17
19Table 5
The influence of the initial interior pointx0 on iterations (γ=0.5,ϵ=0.01).
Initial  interior point
IterationsK
Initial  interior point
IterationsK
[
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
]
T
33
[
1
1
1
1
1
1
1
4
]
T
16
[
1
0.5
0.1
0.1
0.1
0.1
0.1
0.1
]
T
31
[
1
1.9
2
1
0.7
1.1
1.9
4
]
T
15
[
1
1
0.1
0.1
0.1
0.1
0.1
1
]
T
26
[
1.1
2.5
2.2
0.4
0.5
0.6
1.1
5
]
T
14
[
1
0.5
0.5
0.5
0.5
0.5
0.5
0.5
]
T
21
[
1.4
2.7
2.2
0.2
0.3
0.3
0.8
6.6
]
T
13
[
1
1
0.5
0.5
0.5
0.5
0.5
0.5
]
T
20
[
1.5
2.7
2
0.1
0.3
0.2
0.8
6.7
]
T
13
[
1
1
0.5
0.5
0.5
0.5
1
1
]
T
19
[
1.6
2.8
2.1
0.1
0.2
0.2
0.6
7
]
T
12
[
1
1
1
1
1
1
1
1
]
T
18
[
1.6
2.8
2
0.1
0.2
0.2
0.7
6.9
]
T
12
[
1
1
1
1
1
1
1
2
]
T
17
[
1.7
2.9
1.9
0.1
0.2
0.1
0.7
7.1
]
T
11
[
1
1
1
1
1
1
1
3
]
T
16Table 6
The influence of the accuracy parameterϵ and safety factor parameter γ on iterations (x0=[11111115]T).
Parameterγ
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0.95
IterationsK
ϵ
=
0.1
52
29
20
16
13
11
9
8
8
7
ϵ
=
0.01
75
40
27
20
16
13
11
10
9
9
ϵ
=
0.001
97
50
33
25
19
16
13
12
11
11


## 6. Conclusions

A new interior point method is presented to solve FNLP problems using linear ranking function in this paper. Compared with simplex method or revised simplex algorithm, this method is more outstanding in solving the large scale of the FNLP problem, for it has a polynomial time complexity. And some factors influencing the results of this method are analyzed. The result shows that proper safety factor parameter, accuracy parameter, and initial interior point of this method may reduce iterations and they can be selected easily according to the actual needs. Although a general method to select the initial point has been given in this paper, it is not feasible in some cases. For example, under the conditionV0=b-Ax0>0, the matrix ATDk2A may be singular and not reversible, then the search direction cannot be obtained, thus the algorithm cannot be performed. Therefore, future work may put forward an applicable broader method for the revised initial interior point.



---

*Source: 795098-2013-06-27.xml*