A revised simplex method of solving degenerate fuzzy number linear programming problems

1 Introduction

Since fuzzy optimization problems proposed by Zadeh in 1970s, the research on fuzzy programming problems got rapid development, especially on fuzzy linear programming (FLP). From a general view, the class of FLP can be broadly classified into three kinds of situations: fuzzy number linear programming (FNLP) in which only the cost coefficients are fuzzy numbers, linear programming with fuzzy variables (FVLP) in which the right-hand-side vectors and the decision variables are fuzzy numbers, fully fuzzy linear programming (FFLP) in which the cost coefficients, the right-hand-side vectors and the decision variables are fuzzy numbers.

FNLP is that the problem most attracts many researchers to focus among the FLP. By their various attempts, many research results have been achieved[1–21], which mainly includes transforming FNLP into classical or possibility linear programming to study its solution method by defining different fuzzy number, fuzzy order relation, linear ranking function [1–12]; directly solving it without transforming it into the classical linear programming with a linear programming method involving symmetrical triangular fuzzy numbers and symmetrical trapezoidal fuzzy numbers [4, 5]; the duality of FNLP problem and its solving method [15–17]; as well as the sensitivity analysis of FNLP and its extension [18–21].

Above studies are under an assumption that FNLP is non-degenerate, however degenerate FNLP is often encountered in solving practical problem and theoretical research. Up to now, there are a few papers reporting the studies of degenerate FLP [22, 23]. For example, Sigarpich etc. introduced a Fuzzy Degenerate Solution (FDS) by a definite linear function for ranking symmetric triangular fuzzy numbers in a Fuzzy Linear Programming problem (FLP) model, and investigated the occurrence of degeneracy in a Fuzzy Minimal Cost Flow Network in the physical meaning. To prevent of falling into cycling phenomenon in optimization process, they defined two new techniques of cycling prevention proper to fuzzy environment [22]. Yihua etc. studied the problem of degenerate FVLP in [23], in which they constructed a new problem related to the original problem, studied the relationships about the optimal solutions of the new problem and the original problem with the ranking function, and proposed a revised simplex method for finding the optimal solution of the original degenerate problems.

The focus of this paper is on the problems of degenerate FNLP and its solving. We shall use the same idea as reference [23] to study this problem. Firstly, a new problem related to the original degenerate problem is constructed. Then some theorems between the new problem and the original problem is proposed and proved. Next, a revised simplex method through improving the method of selecting the leaving base variable is presented. Finally, numerical example will be study to show the method presented in the paper to be correct.

2 Preliminaries

In this section, we recall some necessary concepts on fuzzy number and ranking function, their operations and the existing method for solving FNLP proposed by Mahdavi-Amiri and Nasseri, which are needed in the rest of the paper (taken from [6, 7]).

Definition 1. (trapezoidal fuzzy number) [21] A fuzzy number a ˜ = ( a L , a U , α , β ) is said to be a trapezoidal fuzzy number, if its membership function is given by function: μ a ˜ ( x ) = { x - ( a L - α ) α for a L - α ≤ x ≤ a L 1 for a L ≤ x ≤ a U ( a U + β ) - x β for a U ≤ x ≤ a U + β 0 else

Definition 2. (the arithmetic operations on fuzzy numbers) [7] If a ˜ = ( a L , a U , α , β ) and b ˜ = ( b L , b U , γ , θ ) are any two trapezoidal fuzzy numbers, then

x > 0, x ∈ R, x a ˜ = ( xa L , xa U , x α , x β ).

Definition 3. (ranking function) The function R : F ( R ) ⟶ R which maps each fuzzy number into the real line is called a ranking function, where a natural order exists.

Definition 4. (linear ranking function) For any a ˜ , b ˜ ∈ F ( R ) , k ∈ R, if a ranking function R such that R ( k a ˜ + b ˜ ) = k R ( a ˜ ) + R ( b ˜ ), then R is a linear ranking function on F (R).

Definition 5. (the form of linear ranking functions on F (R)) They are often as follows: (1) R ( a ˜ ) = c L a L + c U a U + c α α + c β β, where a ˜ = ( a L , a U , α , β ) and c _L , c _U , c _α , c _β are constants, at least one of which is nonzero.

(2) R ( a ˜ ) = 1 2 ∫ 0 1 ( inf a ˜ λ + sup a ˜ λ ) d λ, that is reduced to R ( a ˜ ) = a L + a U 2 + 1 4 ( β - α ).

Definition 6. (orders of ranking function) If a ˜ , b ˜ ∈ F ( R ), then

a ˜ ≥ R b ˜ if and only if R ( a ˜ ) ≥ R ( b ˜ ).

Esp. for any two trapezoidal fuzzy numbers a ˜ = ( a L , a U , α , β ) and b ˜ = ( b L , b U , γ , θ ), a ˜ ≥ R b ˜ if and only if a L + a U + 1 2 ( β - α ) ≥ b L + b U + 1 2 ( θ - γ ).

Definition 7. A FNLP problem is defined as:

min z ˜ = R cx ˜ s . t . Ax = b x ≥ 0(1) where b ∈ R m , x ∈ R n , A ∈ R m × n , c ˜ T ∈ ( F ( R ) ) n, R (A) = m and R is a linear ranking function.

Algorithm 1. [6] The fuzzy primal simplex algorithm

Assumption: A basic feasible solution with basis B and the corresponding simplex tableau is at hand.

Step 1: The basic feasible solution is given by x _B  = B ^-1 b and x _N  = 0. The fuzzy objective value is z ˜ = R c ˜ B x B.

Step 2: Let z ˜ k - c ˜ k = max j { z ˜ j - c ˜ j } , j = 1 , … , n , j ≠ B i , i = 1 , … , m. If z ˜ k - c ˜ k ≤ R 0, then stop, and the current solution is optimal.

Step 3: If y _k  ≤ 0, then stop and the problem is unbounded. Otherwise, determine the index of the variable x _{B r} leaving the basis as follows: b r y rk = min 1 ≤ i ≤ m { b i y ik : y ik > 0 }

Step 4: Pivot on y _rk , and update the simplex tableau. Go to Step 2.

In this section, the definition of degenerate problem is shown, and then some theorems relating to this degenerate problem are proposed and proved.

Definition 8. If the value of a basic variable is equal to zero in a basic feasible solution of the fuzzy number linear programming, then this fuzzy number linear programming is degenerate.

It is very difficult or almost impossible to solve this degenerate problem by existing method although it has an optimal solution. That is, if a basic feasible solution of the FNLP problem (1) is degenerate, then the problem may fall into cycling, i.e. the operation to find an optimal solution of the problem will repeat over and over for this same basic feasible solution. To solve this problem, we propose the idea of an revised algorithm as follows:

Instead of solving this problem directly, we construct an associated problem with (1), which provides a solution to the original problem and which avoids the possibility of degeneracy at any stage of the computations. In order to prevent cycling, we make a perturbation in the right hand side of the constraints of problem (1). This technique specifies the variable leaving the basis, such that if the simplex minimum ratio test produces several candidates, then it will guarantee no cycling. We introduce a small perturbation parameter into vector b (right hand side of the FNLP), then the formulating perturbed problem is as formula (2):

min z ˜ = R cx ˜ s . t . Ax = b ( ɛ ) x ≥ 0(2) b (ɛ) is replaced by b + ∑ i = 1 n ɛ i p j, where ɛ is unspecified, but positive, and p _j is the j-th column ofmatrix A.

Theorem 1. There exists a sufficient small number ɛ₀ > 0 to problem (1) such that for any ɛ, 0 < ɛ < ɛ₀, the perturbed problem (2) is not degenerate.

Proof. For A is row full rank, it can be decomposed as [B, N], where B is invertible. Generally, if former m columns of A are linear correlation, it can be changed through the column transformation to be linear independent. Accordingly, x = [x _B   x _N ]  ^T .

Since Ax = b (ɛ), we have x B = B - 1 b ( ɛ ) - B - 1 N x N = B - 1 ( b + ∑ j = 1 n ɛ j p j ) - B - 1 N x N = B - 1 b + ∑ j = 1 n ɛ j B - 1 p j - B - 1 N x N = b ¯ + ∑ j = 1 n ɛ j y j - B - 1 N x N where b ¯ = B - 1 b, y _j  = B ^-1 p _j .

We focus on the i-th component: x B i = b ¯ i + ɛ B i + ∑ j ∈ N y ij ɛ j - ∑ j ∈ N y ij x j , i = 1 , · · · , m where N is the index set of the non-basic variables and x _{B i} is one basic variable. At this point, the basic solution of the perturbed problem (2) is

x B i = b ¯ i + ɛ B i + ∑ j ∈ N y ij ɛ j , i = 1 , · · · , m(3) x j = 0 , j ∈ N

Let the right hand side of (3) be polynomial of t:

P ( t ) = b ¯ i + t B i + ∑ j ∈ N y ij t j(4) When t = ɛ, P (t) is equal to x _{B i} .

According to the advanced algebra, the polynomial (4) has at most n real roots for the degree of polynomial P (t) is at most n. Each basic solution is corresponding to m polynomials, and the possible number of the basic solution is at most C n m = n ! m ! * ( n - m ) ! . So, all the polynomial is always no more than mC n m = n ! ( m - 1 ) ! * ( n - m ) ! . Therefore, the number of the possible real roots for the the polynomial (4) is less than nmC n m = n * n ! ( m - 1 ) ! * ( n - m ) ! . That is, the number of P (t)’s real roots is finite. So, there is a ɛ ₀ > 0 such that p (t) has no real root in (0, ɛ ₀). Then for any ɛ, 0 < ɛ < ɛ ₀, the right hand of (3) is not equal to 0. That is, for each of the basic feasible solution, the value of base variable is greater than 0. Therefore, when ɛ is sufficiently small, the perturbed problem (2) is not degenerate. □

Theorem 2. If ɛ > 0 is sufficiently small and x (ɛ) ^* is the basic feasible solution of (2), then x (0) ^* is the basic feasible solution of (1).

Proof. According to (3), we can get x B i ( ɛ ) * = b ¯ i + ɛ B i + ∑ j ∈ N y ij ɛ j , i = 1 , · · · , m

When ɛ > 0 is sufficiently small, the perturbed problem (2) is not degenerate from Theorem 1, then b ¯ i + ɛ B i + ∑ j ∈ N y ij ɛ j > 0 , i = 1 , · · · , m

Let ɛ ⟶ 0, b ¯ i ≥ 0, i = 1, ·· · , m, then b ¯ = B - 1 b ≥ 0 and x ( 0 ) * = [ b ¯ 0 ] T is the basic feasible solution of (1). □

Corollary 1. If ɛ > 0 is sufficiently small and x (ɛ) ^* is the optimal solution of (2), then x (0) ^* is the optimal solution of (1).

Theorem 3. If there is no feasible solution of (2), then there is no feasible solution of (1).

Proof. Reduction to absurdity. Assumption x ^* is a feasible solution of (1), and let ɛ = (ɛ, ɛ ², ·· · , ɛ ⁿ )  ^T , where ɛ > 0. Then A ( x * + ɛ ) = A x * + A ɛ = b + ∑ j = 1 n ɛ j p j and x ^* + ɛ > 0. Therefore x ^* + ɛ is a feasible solution of (2). But (2) has actually no feasible solution. So the assumption is wrong and Theorem 3 holds. □

Remark 1. If ɛ > 0 is sufficiently small and the FNLP (2) is unbounded, then (1) is unbounded.

Through the previous section, the solution of problem (1) can be obtained by solving the problem (2), which can be solved by the fuzzy primal simplex algorithm [6]. However, to solve the problem (1) and avoid the complication of constructing the problem (2) every time, we propose a new solving method by revising the Algorithm 1.

The method of selecting the leaving basis variable of Step 3 in the Algorithm 1 is changed as follows:

b ¯ r y rk = min { b ¯ i y ik | y ik > 0 }(5) where b ¯ i = ( B - 1 b ( ɛ ) ) i. Combined with (3), (5) is changed to be (6).

b ¯ r y rk = min { b ¯ i y ik + ∑ j ∈ N y ij y ik ɛ j | y ik > 0 }(6) where b ¯ i = ( B - 1 b ) i and ɛ > 0 is sufficiently small. This value of (6) mainly depends on the low-order terms. The smallest ratio is found using lexicographical comparison, that is, comparing the coefficient of ɛ ^j from j = 0 to j = n.

Remark 2. According to the lexicographical comparison, it will not appear exactly the same corresponding coefficients of two polynomials, otherwise it contradicts r (A) = m.

Remark 3. The coefficient of ɛ ^j  (j = 1, ·· · , n) in (6) is the element of j-th column in the simplex tableau. So ɛ does not need to appear in the simplex tableau.

According to (6) and Remark 6 and 7, the step of determining the leaving basis variable is shown as follows:

Let I 0 = { r | b ¯ r y rk = min { b ¯ i y ik | y ik > 0 } }, if there is only one element r in I ₀, then x _{B r} is the leaving basis variable;

Then combined with the Algorithm 1, the revised fuzzy simplex method of degenerate FNLP is summarized in the Algorithm 2.

Algorithm 2. The revised fuzzy simplex algorithm of degenerate FNLP

Assumption: A basic feasible solution with basis B and the corresponding simplex tableau is at hand.

Step 1: The basic feasible solution is given by x _B  = B ^-1 b and x _N  = 0. The fuzzy objective value is z ˜ = R c ˜ B x B.

Step 2: Let z ˜ k - c ˜ k = max j { z ˜ j - c ˜ j } , j = 1 , … , n , j ≠ B i , i = 1 , … , m. If z ˜ k - c ˜ k ≤ R 0, then stop, and the current solution is optimal.

Step 3: If y _k  ≤ 0, then stop and the problem is unbounded. Otherwise to step 4.

Step 4: Let I 0 = { r | b ¯ r y rk = min { b ¯ i y ik | y ik > 0 } }, where b ¯ i = ( B - 1 b ) i. If there is only one element r in I ₀, then x _{B r} is the leaving basis variable. Otherwise to Step 5.

Step 5: Let j = 1.

Step 6: Let I j = { r | y rj y rk = min i ∈ I j - 1 { y ij y ik } }, if there is only one element r in I _j , then x _{B r} is the leaving basis variable. Otherwise to Step 7.

Step 7: Let j : = j + 1, and go back to step 6.

Step 8: Pivot on y _rk , and update the simplex tableau. Go back to Step 2.

Consider the following degenerate FNLP problem:

min z ˜ = R - ( 0 , 1 , 1 , 2 ) x 4 + ( 19 , 21 , 1 , 1 ) x 5 - ( 0 , 1 , 1 , 1 ) x 6 + ( 5 , 6 , 1 , 3 ) x 7 s . t . x 1 + 1 4 x 4 - 8 x 5 - x 6 + 9 x 7 = 0 x 2 + 1 2 x 4 - 12 x 5 - 1 2 x 6 + 3 x 7 = 0 x 3 + x 6 = 1 x j ≥ 0 , j = 1 , · · · , 7 .(7) where R is a linear ranking function.

First, the initial simplex tableau of (7) is given in Table 1.

Next, the solving process using the fuzzy primal simplex method [7] is demonstrated in Table 2 to Table 7.

Thus, using the Algorithm 1 which is fuzzy primal simplex method [7] to solve this problem (7), we can get that the problem fell into cycling after 6 iterations, see Table 2 to Table 7, which led to its optimal solution not be obtained.

Since the Algorithm 1 can not solve (7), we use the Algorithm 2 proposed in Section 4 to solve it.

Consider the Table 1, since max( 3 4 , 1 2 ) = 3 4, then x ₄ enters the basis.

First, compare the coefficient of ɛ ⁰, b 1 y 14 = b 2 y 24 = 0, then I ₀ ={ 1, 2 }. Next, compare the coefficient of ɛ ¹, y 11 y 14 = 4 > y 21 y 24 = 0, then I ₁ ={ 2 }. That is to say, x ₂ is the leaving variable. The result of pivoting on y ₂₄ is in the next tableau as in Table 8.

Since max( - 3 2 , - 2 , 5 4 , - 21 2 ) = 5 4, then x ₆ enters the basis.

First, compare the coefficient of ɛ ⁰, b 3 y 34 = 1, then I ₀ ={ 3 }. That is to say, x ₃ is the leaving variable. The result of pivoting on y ₃₆ is shown in Table 9.

So the optimal solution is (x ₁, x ₂, x ₃, x ₄, x ₅, x ₆, x ₇) = ( 3 4 , 0 , 0 , 1 , 0 , 1 , 0 ) and the optimal fuzzy objective value is (- 2, 0, 3, 2).

Aiming at the problems of existence about degenerate FNLP problem in theory and real world as well as few be studied, first, the degenerate FNLP problem is defined. Then, some relevant theorems are proposed and proved. Next, According to these theorems, a revised fuzzy simplex method is proposed. At last, the numerical example shows that the fuzzy primal simplex method [7] can not solving the degenerate FNLP problems, which fall into cycling after 6 iterations, but the proposed method can avoid the infinite loop,and the degenerate FNLP problem can be successfully solved only by 3 iterations.

As a result, the proposed method can solve the degenerate FNLP problem, and make up for deficiencies of the fuzzy primal simplex method in solving the degenerate FNLP problem.

Acknowledgements

This work is supported by both National Natural Science Foundation of China (No. 11401494) and Sichuan Provincial Education Department (No. 11ZA024).