Stratified simplex method for solving fuzzy multi-objective linear programming problem

Abstract

This paper is to deal with a kind of fuzzy multi-objective linear programming (FMOLP) problem with symmetric trapezoidal fuzzy numbers. Several methods has been proposed in order to obtain fuzzy efficient solution to FMOLP problem. In this paper, we change FMOLP problem into the complete stratified fuzzy linear programming problem, then use the stratified simplex method to obtain the fuzzy optimal solution directly without converting them to crisp linear programming problem. We then prove that this fuzzy optimal solution is the fuzzy efficient solution of the original FMOLP problem. A numerical example is given to illustrate the proposed method.

Keywords

Fuzzy multi-objective linear programming symmetric trapezoidal fuzzy numbers fuzzy efficient solution stratified simplex method

1 Introduction

Fuzzy set theory has been applied to many disciplines such as industrial applications, management sciences, control theory and mathematical modeling. Bellman and Zadeh [18] first proposed the definition of fuzzy set. Tanaka et al. [8] proposed the concept of fuzzy mathematical programming. Then several methods for solving fuzzy linear programming problem were proposed [3–5 , 19]. In many practical problems there usually lies not only one objective, then multi-objective linear programming (MOLP) has important application in many areas of management and engineering. Because of the complexity of the actual problem, the parameter values in MOLP problem cannot be accurately given, then in the actual decision makers consider the parameters as fuzzy numbers. Therefore, fuzzy multi-objective linear programming (FMOLP) problem with fuzzy numbers has more extensive application.

In order to obtain a satisfaction solution of FMOLP problem for a decision maker (DM) based on his/her subjective and preference, various FMOLP models have been proposed and the corresponding solution are also presented. For example, Toksar [13] proposed a Taylor series approach to solve multi-objective linear fractional programming. Ibrahim [10] proposed fuzzy goal programming approach to solve decentralized bi-level multi-objective programming problems. Lai and Hwang [21] used the fuzzy ranking function to solve FMOLP problem with triangular fuzzy numbers. Huang and Wu [9] transformed the fuzzy multi-objective programming problem into a single-objective programming problem by using the comprehensive coordination function with exponential weights. Luhandjula [14] proposed the concepts of α-possible feasibility and β-possible efficiency based on the concept of fuzzy number, and used the two concepts to solve FMOLP problems by transferring it into an auxiliary crisp MOLP problem. Jie Lu et al. [11] given the concept of adjustable satisfactory degree α, the definition of fuzzy number based solution concept and related theorems for solving an FMOLP problem with different degree α. Ganesan and Veeramani [12] defined a type of fuzzy arithmetic for symmetric trapezoidal fuzzy numbers. Using this definition fuzzy linear programming problem was solved directly with a primal simplex method. Ebrahimnejad [1] proposed a fuzzy revised simplex method to solve fuzzy linear programming. Behrouz et al. [4] extended the dual simplex method to solve the fuzzy linear programming problem with symmetric trapezoidal fuzzy numbers. Mahdavi and Nasseri [17] developed and presented the dual simplex algorithm directly using the primal tableau, for solving the linear programming problem with fuzzy numbers.

In this paper, we develop the simplex method for solving a type of FMOLP problems involving symmetric trapezoidal fuzzy numbers. We change the FMOLP problem into the complete stratified linear programming problem, then use the stratified simplex method to obtain the fuzzy optimal solution and prove this solution is the fuzzy efficient solution of the original FMOLP problems.

This paper is organized as follows: In Section 2, some basic definitions and arithmetic between two symmetric trapezoidal fuzzy numbers are presented. In Section 3, the general form of FMOLP problem is presented. Then the FMOLP problem is converted to the complete stratified fuzzy linear programming problem and the fuzzy efficient solution is obtained by using the stratified simplex method. In Section 4, the model and the algorithm of non-complete stratified fuzzy linear programming is discussed. An illustrative example is presented in Section 5 to demonstrate the method. Conclusions are discussed in Section 6.

2 Preliminaries

Some basic definitions, arithmetic operations and ranking function are reviewed in this section.

2.1 Basic definitions

Definition 2.1. [2] A fuzzy set $\tilde{A}$ , defined on the universal set of real numbers R is said to be a fuzzy number if its membership has the following characteristics:

$μ_{\tilde{A}}$ :R → [0, 1] is continuous.

$μ_{\tilde{A}} (x) = 0$ for all x ∈ (- ∞ , a) ∪ [d, ∞).

$μ_{\tilde{A}} (x)$ strictly increasing on [a, b] and strictly decreasing on [c, d].

$μ_{\tilde{A}} (x) = 1$ for all x ∈ [b, c], where a < b<c < d.

Definition 2.2. [2] A fuzzy number $\tilde{A} = (a, b, α, β)$ is said to be a trapezoidal fuzzy number if its membership function is given by $μ_{\tilde{A}} (x) = {\begin{matrix} 1 - \frac{(a - x)}{α}, & for & a - α \leq x < a, \\ 1, & for & a \leq x \leq b, \\ 1 - \frac{(x - b)}{β}, & for & b < x \leq b + β, \\ 0, & else . \end{matrix}$

If α = β, $\tilde{A}$ is said to be a symmetric trapezoidal fuzzy number.

Definition 2.3. [20] A ranking function is a function R : F (R) → R, where F (R) is a set of fuzzy numbers defined on set of real numbers, which maps each fuzzy number into the real line.

Let $\tilde{A} = (a, b, α, α)$ be a symmetric trapezoidal fuzzy number, $R (\tilde{A}) = \frac{a + b}{2}$ , then

$\tilde{A} ≻ \tilde{B}$ iff $R (\tilde{A}) > R (\tilde{B})$

$\tilde{A} ≺ \tilde{B}$ iff $R (\tilde{A}) < R (\tilde{B})$

$\tilde{A} ≃ \tilde{B}$ iff $R (\tilde{A}) = R (\tilde{B})$

Remark 2.1. We consider $\tilde{A} ≃ \tilde{0}$ if and only if $R (\tilde{A}) = 0$ . In this paper we let $\tilde{0} ≃ (0, 0, 0, 0)$ as the trapezoidal fuzzy number.

2.2 Arithmetic operations

In this section, arithmetic operation between two trapezoidal fuzzy numbers are reviewed [12].

Let ${\tilde{A}}_{1} = [a_{1}, b_{1}, α, α]$ and ${\tilde{A}}_{2} = [a_{2}, b_{2}, β, β]$ be two symmetric trapezoidal fuzzy numbers, λ is a real number, then

$λ \geq 0, λ \tilde{A_{1}} = [λ a_{1}, λ b_{1}, λ α, λ α]$

$λ < 0, λ \tilde{A_{1}} = [λ b_{1}, λ a_{1}, - λ α, - λ α]$

$\tilde{A_{1}} \oplus \tilde{A_{2}} = [a_{1} + a_{2}, b_{1} + b_{2}, α + β, α + β]$

$\tilde{A_{1}} \otimes \tilde{A_{2}} = [(\frac{a_{1} + b_{1}}{2}) (\frac{a_{2} + b_{2}}{2}) - w, (\frac{a_{1} + b_{1}}{2}) (\frac{a_{2} + b_{2}}{2}) + w, | b_{1} β + b_{2} α |, | b_{1} β + b_{2} α |]$

where $w = \frac{h - k}{2}, h = \max (a_{1} a_{2}, a_{1} b_{2}, b_{1} a_{2},$ b₁b₂) , k = min (a₁a₂, a₁b₂, b₁a₂, b₁b₂) .

3 FMOLP problem

A general model of FMOLP problem with n decision variables, m constraints and l objectives can be stated as follows:

(P1) Min $(\tilde{f_{1}} (\tilde{x}), \dots, \tilde{f_{l}} (\tilde{x})) = (\tilde{c_{1}} \tilde{x}, \dots, \tilde{c_{l}} \tilde{x})$

s.t. $A \tilde{x} ⪯ \tilde{b}$

$\tilde{x} ɛ \tilde{0}$

Where A = (a_ij) _m×n is a real matrix, $\tilde{c_{t}} = ({\tilde{c}}_{tj})_{1 \times n}$ (t = 1, …, l), $\tilde{b} = ({\tilde{b}}_{i})_{m \times 1}$ , $\tilde{x} = ({\tilde{x}}_{j})_{n \times 1}$ are fuzzy matrixes consisting of symmetric trapezoidal fuzzy numbers.

In problem (P1), it is unlikely that all objectives will simultaneously achieve their fuzzy optimal subjective to the given constrains. So in practice the DM usually choose fuzzy efficient solution as final decision according to the satisfaction degree of each objective [15]. The fuzzy efficient solution is defined as follows:

Definition 3.1. A fuzzy feasible solution ${\tilde{x}}^{*}$ of the FMOLP problem (P1) is said to be a fuzzy efficient solution if and only if there does not exist another fuzzy feasible solution ${\tilde{x}}^{0}$ such that $R ({\tilde{f}}_{k} ({\tilde{x}}^{0})) \leq R ({\tilde{f}}_{k} ({\tilde{x}}^{*}))$ for all k (k = 1, …, l) and $R ({\tilde{f}}_{j} ({\tilde{x}}^{0})) < R ({\tilde{f}}_{j} ({\tilde{x}}^{*}))$ for at least one j (j = 1, …, l).

3.1 Complete stratified problem

In practical problems, objective functions are usually divided into the different levels according to their importance. Then the FMOLP problem (P1) can be changed to a complete stratified fuzzy linear programming problem as follows:

(P2) Min ${[P_{k} {\tilde{f}}_{k} (\tilde{x})]}_{k = 1}^{l}$

s.t. $A \tilde{x} ⪯ \tilde{b}$

$\tilde{x} ɛ \tilde{0}$

Where P_k (k = 1, …, l) is the mark of the priority level, ${\tilde{f}}_{k} (\tilde{x})$ belongs to the kth priority level and P_k ⪢ P_k+1.

According to the above model, we know that different objective functions in problem (P1) have different levels. In order to find the fuzzy efficient solution of problem (P2), we solve it from the upper level, the fuzzy optimal solution on the lowest level is what we want.

The steps of solving problem (P2) can be summarized as follows:

ALG (3.1).

Step 1: Determine the fuzzy feasible region

Assuming the fuzzy feasible region $\tilde{X}$ of problem (P1) as the fuzzy feasible region of the upper level problem, i.e. ${\tilde{X}}^{1} = \tilde{X}$ , set k : =1;

Step 2: Minimize each level problem

Solving the following problem $min_{\tilde{x} \in {\tilde{X}}^{k}} {\tilde{f}}_{k} (\tilde{x})$ , then obtain the fuzzy optimal solution ${\tilde{x}}^{k}$ and the fuzzy optimal value ${\tilde{f}}_{k} ({\tilde{x}}^{k})$ ;

Step 3: Check the priority level

if k = l, put out ${\tilde{x}}^{*} = {\tilde{x}}^{l}$

if k < l, go to Step 4;

Step 4: Set ${\tilde{X}}^{k + 1} = {\tilde{x} \in {\tilde{X}}^{k} | R ({\tilde{f}}_{k} (\tilde{x})) \leq R ({\tilde{f}}_{k} (\tilde{x^{k}}))}$ and k : = k + 1, go to Step 2.

Theorem 3.1. Set $\tilde{E} (\tilde{f}, \tilde{X})$ is the fuzzy efficient set of problem (P1). If ${\tilde{x}}^{*}$ is the solution of problem (P2) that obtained by the ALG (3.1), then ${\tilde{x}}^{*} \in \tilde{E} (\tilde{f}, \tilde{X})$ .

Proof. Set ${\tilde{x}}^{k}, k = 1, \dots, l - 1$ is the fuzzy optimal solution of the kth priority stratify problem, ${\tilde{x}}^{*}$ is the fuzzy feasible solution of the former (l - 1) levels and also the fuzzy optimal solution of the lowest level. Suppose, on the contrary, that ${\tilde{x}}^{*} \notin \tilde{E} (\tilde{f}, \tilde{X})$ , then there exist a fuzzy feasible solution ${\tilde{x}}_{0} \in \tilde{X} = {\tilde{X}}^{1}$ , such that $R ({\tilde{f}}_{k} ({\tilde{x}}_{0})) \leq R ({\tilde{f}}_{k} ({\tilde{x}}^{*}))$ for all k, k = 1, …, l - 1 and $R ({\tilde{f}}_{j} ({\tilde{x}}_{0})) < R ({\tilde{f}}_{j} ({\tilde{x}}^{*}))$ for at least one j, j = 1, …, l - 1 . According to the definition of ${\tilde{X}}^{(k + 1)}$ , $R ({\tilde{f}}_{k} ({\tilde{x}}^{*})) \leq R ({\tilde{f}}_{k} ({\tilde{x}}^{k}))$ and ${\tilde{x}}_{0} \in {\tilde{X}}^{k}, k = 1, \dots, l - 1$ . Then $R ({\tilde{f}}_{k} ({\tilde{x}}_{0})) \leq R ({\tilde{f}}_{k} (\tilde{x^{k}}))$ for all k, k = 1, …, l - 1 and $R ({\tilde{f}}_{j} ({\tilde{x}}_{0})) < R ({\tilde{f}}_{j} (\tilde{x^{*}})) \leq R ({\tilde{f}}_{j} (\tilde{x^{j}}))$ for at least one j, j = 1, …, l - 1. Thus ${\tilde{x}}^{j} (1 \leq j \leq l - 1)$ is not the fuzzy optimal solution of the jth priority level, a contradiction.

3.2 Stratified simplex method

Now, using the simplex method, the stratified simplex method employs stratified simplex tableau is proposed to solve the FLOMP problem directly. A stratified simplex tableau for a problem with (n + m) decision variables (m of the slack variables), m constraints and l objectives is shown as Table 1.

Consider Table 1, where P_k denotes the kth level, ${\tilde{x}}_{B_{i}}$ is the ith fuzzy basic variable, y_.j = B^-1A_.j, where B is the basis matrix, A_.j denote the jth column of A. ${\tilde{λ}}_{. j} ≃ {\tilde{c}}_{B} B^{- 1} A_{. j} - {\tilde{c}}_{j}$ . With Table 1, we can obtain the fuzzy solution of problem (P2) directly. When we solve the (k+1)th level, in order to ensure the objective values of the former kth levels ${\tilde{f}}_{s} (\tilde{x}) = {\tilde{c}}_{s} \tilde{x}, s = 1, \dots, k$ can not exceed the optimal solution ${\tilde{f}}_{s}^{*}$ of the corresponding level, we must consider the following condition. When replace the leaving variable ${\tilde{x}}_{B_{i}}$ in the basic column with the entering variable ${\tilde{x}}_{j}$ , where ${\tilde{x}}_{j}$ is a nonbasic fuzzy variable, y_ij is a pivot element, after changing, we get the following new objective values. ${\tilde{f}}_{s} ≃ \tilde{f_{s}^{*}} - \frac{{\tilde{λ}}_{sj}}{y_{ij}} {\tilde{y}}_{i 0}, s = 1, \dots, k,$ j ≠ B_i, then $R ({\tilde{f}}_{s}^{*} - {\tilde{f}}_{s}) = R (\frac{1}{y_{ij}} {\tilde{λ}}_{sj} \tilde{y_{i}})$ , where $y_{ij} > 0, {\tilde{y}}_{i 0} ≻ \tilde{0}, {\tilde{f}}_{s} ⪯ \tilde{f_{s}^{*}}$ , which result in $R (\frac{1}{y_{ij}} {\tilde{λ}}_{sj} \tilde{y_{i}}) \geq 0$ , then $\frac{1}{y_{ij}} R ({\tilde{λ}}_{sj}) R ({\tilde{y}}_{i 0}) \geq 0$ , thus $R ({\tilde{λ}}_{sj}) \geq 0$ , i.e. ${\tilde{λ}}_{sj} ɛ 0$ .

Therefore, the condition of choosing the (k+1)th entering variable is

${\tilde{λ}}_{k + 1, j} ≻ 0$ and ${\tilde{λ}}_{s, j} ɛ 0, s = 1, \dots, k .$

Above all, the steps of the stratified simplex method can be summarized as follows:

ALG (3.2).

Step 1: Convert problem (P2) to the standard form as

(P3) Min ${[P_{k} \tilde{c_{k}} \tilde{x}]}_{k = 1}^{l}$

s.t. $A \tilde{x} + {\tilde{x}}_{B} ≃ b$

$\tilde{x} ɛ \tilde{0}, {\tilde{x}}_{B} ɛ \tilde{0}$

where ${\tilde{x}}_{B} = ({\tilde{x}}_{n + 1}, {\tilde{x}}_{n + 2}, \dots, {\tilde{x}}_{n + m})^{T}, {\tilde{x}}_{n + 1}, {\tilde{x}}_{n + 2}, \dots, {\tilde{x}}_{n + m}$ are fuzzy slack variables.

Step 2: Find an initial fuzzy basic feasible solution with basis B. Check ${\tilde{λ}}_{kj} (j = 1, \dots, n + m)$ in the row of P_k. If ${\tilde{λ}}_{kj} ⪯ 0$ for every j (1 ≤ j ≤ n + m), or ${\tilde{λ}}_{kj} ≻ 0$ but exist k′ < k such that ${\tilde{λ}}_{k^{'} j} ≺ 0$ , go to Step 5. Otherwise go to Step 3.

Step 3: Select q (1 ≤ q ≤ n + m) such that ${\tilde{λ}}_{kq} ≃ \max {{\tilde{λ}}_{kj} | {\tilde{λ}}_{k^{'} j} ɛ 0, k^{'} = 1, \dots, k - 1}$ . If y_iq ≤ 0 for all i (1 ≤ i ≤ m), stop, the primal FMOLP is infeasible, or else select the pivot column p by means of the following minimum ratio test:

$\frac{{\tilde{y}}_{p 0}}{y_{pq}} ≃ min_{1 \leq i \leq m} {\frac{{\tilde{y}}_{p 0}}{y_{iq}} | y_{iq} > 0}$

Then ${\tilde{x}}_{q}$ is the entering variable, ${\tilde{x}}_{p}$ is the leaving variable.

Step 4: Pivot on y_pq, we can obtain the new variables ${\begin{matrix} {\tilde{y}}_{p 0} : = \frac{{\tilde{y}}_{p 0}}{y_{pq}}, \\ y_{pj} : = \frac{y_{pj}}{y_{pq}}, & j = 1, 2, \dots, n + m, \\ {\tilde{y}}_{i 0} : = {\tilde{y}}_{i 0} - \frac{{\tilde{y}}_{p 0}}{y_{pq}} y_{iq}, & i = 1, 2, \dots, m, i \neq p, \\ y_{ij} : = y_{ij} - \frac{y_{pj}}{y_{pq}} y_{iq}, & i = 1, 2, \dots, m, i \neq p, \\ j = 1, 2, \dots, n + m, \\ {\tilde{λ}}_{sj} : = {\tilde{λ}}_{sj} - \frac{y_{pj}}{y_{pq}} {\tilde{λ}}_{sq}, & s = 1, 2, \dots, l, \\ j = 1, 2, \dots, n + m, \\ {\tilde{f}}_{s 0} : = {\tilde{f}}_{s 0} - \frac{{\tilde{y}}_{p 0}}{y_{pq}} {\tilde{λ}}_{sq}, & s = 1, 2, \dots, l, \\ {\tilde{x}}_{B_{p}} : = {\tilde{x}}_{q} . \end{matrix}$

then go to Step 2.

Step 5: If k = l, go to Step 6, or else if k < l, set k : = k + 1 and go to Step 2.

Step 6: Put out the solution, the fuzzy efficient solution is ${\tilde{x}}^{*} = ({\tilde{x}}_{1}, \dots, {\tilde{x}}_{n + m})^{T}$ , the fuzzy values are ${\tilde{f}}_{k^{*}} ≃ {\tilde{f}}_{k 0}, k = 1, \dots, l .$

Theorem 3.2.Set $\tilde{E} (\tilde{f}, \tilde{X})$ is the fuzzy efficient set of (P1). If ${\tilde{x}}^{*}$ is the fuzzy optimal solution of problem (P2) which obtained by the fuzzy stratified method, then ${\tilde{x}}^{*} \in \tilde{E} (\tilde{f}, \tilde{X})$ .

Proof. Let $\overset{˜^{'}}{x} = (\overset{˜^{'}}{x_{1}}, \dots, \overset{˜^{'}}{x_{n}}, \overset{˜^{'}}{x_{n + 1}}, \dots, \overset{˜^{'}}{x_{n + m}})^{T}$ . In the last simplex table, for all k (1 ≤ k ≤ l) and j (1 ≤ j ≤ n + m), ${\tilde{λ}}_{kj} ⪯ 0$ or ${\tilde{λ}}_{kj} ≻ 0$ and exist such that ${\tilde{λ}}_{k^{'} j} ≺ 0$ . According to Step 6 of ALG (3.2), we have ${\tilde{f}}_{k} (\overset{˜^{'}}{x}) ≃ {\tilde{f}}_{k 0}, k = 1, \dots, l .$ (1) Let $\tilde{x} = ({\tilde{x}}_{1}, \dots, {\tilde{x}}_{n}, {\tilde{x}}_{n + 1}, \dots, {\tilde{x}}_{n + m})^{T}$ , then ${\tilde{f}}_{k} (\tilde{x}) ≃ \sum_{j = 1}^{n + m} {\tilde{c}}_{kj} {\tilde{x}}_{j} ≃ {\tilde{f}}_{k 0} - \sum_{j = 1}^{n + m} {\tilde{λ}}_{kj} {\tilde{x}}_{j}, k = 1, \dots, l .$ (2)

Suppose ${\tilde{X}}^{1}$ is the fuzzy feasible region of (P3), Then $\overset{˜^{'}}{x} \in {\tilde{X}}^{1}$ (3)

Let ${\begin{matrix} {\tilde{f}}_{k}^{*} ≃ min_{\tilde{x} \in {\tilde{X}}^{k}} {\tilde{f}}_{k} (\tilde{x}) \\ {\tilde{X}}^{k + 1} = {\tilde{x} \in {\tilde{X}}^{k} | R ({\tilde{f}}_{k} (\tilde{x})) = R ({\tilde{f}}_{k}^{*})} \end{matrix}$ (4)

In the following, using mathematical induction,we prove ${\begin{matrix} {\tilde{f}}_{k} (\overset{˜^{'}}{x}) ≃ {\tilde{f}}_{k}^{*} \\ \overset{˜^{'}}{x} \in {\tilde{X}}^{k + 1} \end{matrix}$ (5)

If k = 1, then ${\tilde{λ}}_{1 j} ⪯ 0, j = 1, \dots, n + m$ , for all $\tilde{x} \in {\tilde{X}}^{1}$ , ${\tilde{f}}_{1} (\tilde{x}) ≃ {\tilde{f}}_{10} - \sum_{j = 1}^{n + m} {\tilde{λ}}_{1 j} {\tilde{x}}_{j} ɛ {\tilde{f}}_{10} ≃ {\tilde{f}}_{1} (\overset{˜^{'}}{x})$ , Therefor ${\tilde{f}}_{1} (\overset{˜^{'}}{x}) ≃ {\tilde{f}}_{1}^{*}$ , i.e. $R ({\tilde{f}}_{1} (\overset{˜^{'}}{x})) = R ({\tilde{f}}_{1}^{*})$ (6) from (3) (4) and (6) we have $\overset{˜^{'}}{x} \in {\tilde{X}}^{2}$ (7)

Hence Equation. (5) holds when k=1. Suppose Equation. (5) holds when k ≤ t, then we prove (5) is also holds when k = t + 1. Set $\tilde{x} = ({\tilde{x}}_{1}, \dots, {\tilde{x}}_{n + m}) \in {\tilde{X}}^{t + 1},$ then $\tilde{x} \in {\tilde{X}}^{t + 1} \subset {\tilde{X}}^{t} \subset \dots \subset {\tilde{X}}^{2}$ , therefor ${\tilde{f}}_{k} (\tilde{x}) ≃ {\tilde{f}}_{k}^{*}, k = 1, \dots, t$ .

From Equation. (1), Equations. (2) and (5), we have ${\tilde{f}}_{k 0} ≃ {\tilde{f}}_{k} (\overset{˜^{'}}{x}) ≃ {\tilde{f}}_{k}^{*} ≃ {\tilde{f}}_{k} ({\tilde{x}}^{0}) ≃ {\tilde{f}}_{k 0} - \sum_{j = 1}^{n + m} {\tilde{λ}}_{kj} {\tilde{x}}_{j}$ , then $\sum_{j = 1}^{n + m} {\tilde{λ}}_{kj} {\tilde{x}}_{j} ≃ \tilde{0}, k = 1, \dots, t .$ (8)

From Equation. (8), if ${\tilde{λ}}_{kj} \neq \tilde{0}$ , then ${\tilde{x}}_{j} ≃ 0$ , for all k, k = 1, ⋯ , t and all j, j = 1, ⋯ , n + m. Therefor in the (t+1)th, if ${\tilde{λ}}_{t + 1} j ≻ 0$ , there exist , then ${\tilde{x}}_{j} ≃ 0$ . Then for all $\tilde{x} \in {\tilde{X}}^{t + 1}$ , ${\tilde{f}}_{t + 1} (\tilde{x}) ≃ {\tilde{f}}_{(t + 1) 0} - \sum_{j = 1}^{n + m} {\tilde{λ}}_{t + 1 j} {\tilde{x}}_{j} ɛ {\tilde{f}}_{(t + 1) 0} ≃ {\tilde{f}}_{t + 1} (\overset{˜^{'}}{x})$ . Hence ${\tilde{f}}_{t + 1} (\overset{˜^{'}}{x}) ≃ {\tilde{f}}_{t + 1}^{*}$ , i.e. $R ({\tilde{f}}_{t + 1} (\overset{˜^{'}}{x})) = R ({\tilde{f}}_{t + 1}^{*})$ (9)

From Equations. (4) and (9), we have $\overset{˜^{'}}{x} \in {\tilde{X}}^{t + 2}$ (10)

Therefore, Equations. (9) and (10) indicate that when k = t + 1, Equation. (5) holds. Hence corresponding to the mathematical induction (5) holds.

Now, from Equations. (4) and (5) we have $\overset{˜^{'}}{x} = (\overset{˜^{'}}{x_{1}}, \dots, \overset{˜^{'}}{x_{n + m}}) \in {\tilde{X}}^{t + 1}$ is the solution that obtained by the ALG3.1. According to the Theorem 3.1, we know $\overset{˜^{'}}{x}$ is the fuzzy efficient solution of problem (P4), where

(P4) Min $(\tilde{f_{1}} (\tilde{x}), \tilde{f_{2}} (\tilde{x}), \dots, \tilde{f_{l}} (\tilde{x})) = (\tilde{c_{1}} \tilde{x}, \tilde{c_{2}} \tilde{x}, \dots,$ $\tilde{c_{l}} \tilde{x})$

s.t. $A \tilde{x} + {\tilde{x}}_{B} ≃ b$

$\tilde{x} ɛ \tilde{0}, {\tilde{x}}_{B} ɛ \tilde{0}$

there fore $\overset{˜^{'}}{x} = (\overset{˜^{'}}{x_{1}}, \dots, \overset{˜^{'}}{x_{n}})^{T}$ is the fuzzy efficient solution of problem (P1), i.e. ${\tilde{x}}^{*} \in \tilde{E} (\tilde{f}, \tilde{X})$ .

4 Non-complete problem

In Section 3 we consider the complete stratified fuzzy linear programming problem, but in practical problems, some objective functions are equally important, so the non-complete stratified fuzzy linear programming problem need to discuss.

Suppose there have m (m ≥ 2) objective functions.

${\tilde{f}}_{1}^{1} (\tilde{x}), \dots, {\tilde{f}}_{l_{1}}^{1} (\tilde{x}); {\tilde{f}}_{1}^{2} (\tilde{x}), \dots, {\tilde{f}}_{l_{2}}^{2} (\tilde{x}); \dots; {\tilde{f}}_{1}^{L} (\tilde{x}), \dots, {\tilde{f}}_{l_{L}}^{L} (\tilde{x}) .$

where l₁ + l₂ + … + l_L = m .

These objective functions belong to different levels. Suppose

the upper level is ${\tilde{F}}_{1} (\tilde{x}) ≃ ({\tilde{f}}_{1}^{1} (\tilde{x}), \dots, {\tilde{f}}_{l_{1}}^{1} (\tilde{x}))^{T}$ ,

the second level is ${\tilde{F}}_{2} (\tilde{x}) ≃ ({\tilde{f}}_{1}^{2} (\tilde{x}), \dots, {\tilde{f}}_{l_{2}}^{2} (\tilde{x}))^{T}, \dots$

the lowest level is ${\tilde{F}}_{L} (\tilde{x}) ≃ ({\tilde{f}}_{1}^{L} (\tilde{x}), \dots, {\tilde{f}}_{l_{L}}^{L} (\tilde{x}))^{T}$ .

Then we obtain the non-complete stratified fuzzy linear programming problem.

(P5) Min $[P_{1} {\tilde{F}}_{1} (\tilde{x}), P_{2} {\tilde{F}}_{2} (\tilde{x}), \dots, P_{L} {\tilde{F}}_{L} (\tilde{x})]$

s.t. $A \tilde{x} ⪯ \tilde{b}$

$\tilde{x} ɛ \tilde{0}$

The algorithm of solving (P5) can be summarized as follows:

ALG (4.1).

Step 1: Consider the kth level, determine the weight coefficient of each objective function according to the DM, then we have

${\tilde{Z}}_{k} (x) ≃ α_{1}^{k} {\tilde{f}}_{1}^{k} (\tilde{x}) + \dots + α_{l_{k}}^{k} {\tilde{f}}_{l_{k}}^{k} (\tilde{x}), k = 1, \dots, L .$

Step 2: Obtain the complete stratified fuzzy linear programming (P6)

(P6) Min ${[P_{k} {\tilde{Z}}_{k} (\tilde{x})]}_{k = 1}^{L}$

s.t. $A \tilde{x} ⪯ \tilde{b}$

$\tilde{x} ɛ \tilde{0}$

Step 3: Use ALG (3.2) to solve problem (P6).

5 A numerical example

For an illustration of the above method we consider the following example.

Example 5.1. Consider the following FMOLP problem:

min ${\tilde{f}}_{1} (\tilde{x}) ≃ (- 3, 1, 2, 2) {\tilde{x}}_{1} + (- 6, 0, 1, 1) {\tilde{x}}_{2}$

${\tilde{f}}_{2} (\tilde{x}) ≃ (- 2, 0, 1, 1) {\tilde{x}}_{1} + (- 5, 1, 1, 1) {\tilde{x}}_{3}$

${\tilde{f}}_{3} (\tilde{x}) ≃ (0, 2, 2, 2) {\tilde{x}}_{1} + (1, 3, 2, 2) {\tilde{x}}_{2} + (0, 2, 1, 1) {\tilde{x}}_{3}$

s.t. ${\tilde{x}}_{1} + {\tilde{x}}_{2} ⪯ (4, 6, 3, 3)$

${\tilde{x}}_{2} ⪯ (1, 3, 2, 2)$

$- {\tilde{x}}_{1} - {\tilde{x}}_{2} + {\tilde{x}}_{3} ⪯ (3, 5, 3, 3)$

${\tilde{x}}_{1}, {\tilde{x}}_{2}, {\tilde{x}}_{3} ɛ \tilde{0}$

Solution. Assume that the following stratified linear programming problem was obtained according to the decision maker.

min $[P_{1} {\tilde{f}}_{1}, P_{2} {\tilde{f}}_{2}, P_{3} {\tilde{f}}_{3}]$

s.t. ${\tilde{x}}_{1} + {\tilde{x}}_{2} ⪯ (4, 6, 3, 3)$

${\tilde{x}}_{2} ⪯ (1, 3, 2, 2)$

$- {\tilde{x}}_{1} - {\tilde{x}}_{2} + {\tilde{x}}_{3} ⪯ (3, 5, 3, 3)$

${\tilde{x}}_{1}, {\tilde{x}}_{2}, {\tilde{x}}_{3} ɛ \tilde{0}$

Introducing slack fuzzy variables ${\tilde{x}}_{4}, {\tilde{x}}_{5}$ and ${\tilde{x}}_{6}$ , we may write the first fuzzy primal simplex tableau as Table 2.

In Table 2, ${\tilde{λ}}_{12} ≃ (0, 6, 1, 1) ɛ \tilde{0}$ , ${\tilde{x}}_{5}$ is a leaving variable and ${\tilde{x}}_{2}$ is an entering variable. The new tableau is Table 3.

In Table 3, ${\tilde{λ}}_{11} ≃ (- 1, 3, 2, 2) ɛ \tilde{0}$ , ${\tilde{x}}_{4}$ is a leaving variable and ${\tilde{x}}_{1}$ is an entering variable. The new tableau is Table 4.

In Table 4, ${\tilde{λ}}_{23} ≃ (- 1, 5, 1, 1) ɛ \tilde{0}$ , ${\tilde{x}}_{6}$ is a leaving variable and ${\tilde{x}}_{3}$ is an entering variable. The new tableau is Table 5.

In Table 5, ${\tilde{λ}}_{25} ≃ (0, 2, 1, 1) ≻ \tilde{0}$ , but ${\tilde{λ}}_{15} ≺ \tilde{0}$ , then convert to the 3th level, ${\tilde{λ}}_{34} ≻ \tilde{0}$ but ${\tilde{λ}}_{24} ≺ \tilde{0}$ , ${\tilde{λ}}_{35} ≻ \tilde{0}$ but ${\tilde{λ}}_{15} ≺ \tilde{0}$ , ${\tilde{λ}}_{36} ≻ \tilde{0}$ but ${\tilde{λ}}_{21} ≺ \tilde{0}$ .

At the same time k = l = 3, therefore the fuzzy efficient solution is ${\tilde{x}}_{1} ≃ (1, 5, 5, 5), {\tilde{x}}_{2} ≃ (1, 3, 2, 2), {\tilde{x}}_{3} ≃ (5, 13, 10, 10)$ , the fuzzy optimal values are ${\tilde{f}}_{1} ≃ (- 28, 10, 18, 18)$ ,

${\tilde{f}}_{2} ≃ (- 65, 23, 28, 28), {\tilde{f}}_{3} ≃ (- 6, 38, 65, 65) .$

6 Conclusion

In this paper, we proposed a fuzzy stratified simplex method to obtain the optimal solution of the complete stratified fuzzy multi-objective linear programming problems. Then we prove this optimal solution is the fuzzy efficient solution of the FMOLP problems. The main advantage of the proposed method is that we can obtain the fuzzy optimal solution of the FMOLP problem directly by using the extended primal simplex method.

Acknowledgments

The project is supported by the National Natural Science Foundation (61074151) and (11371002) and Specialized Research Fund for the Doctoral Program of Higher Education (20131101110048).

References

Ebrahimnejad

2011

Some new results in linear programs with trapezoidal fuzzy numbers: Finite convergence of the Ganesan and Veeramani’s method and a fuzzy revised simplex method

Applied Mathematical Modelling 35 4526 4540

Kaufmann

Gupta

1985

Introduction to fuzzy arithmetic: Theory and applications

Van Nostrand Reinhold, 320 New York

Kumar

Kaur

Singh

2011

A new method for solving fully fuzzy linear programming problems

Applied Mathematical Modelling 35 817 823

Kherirfam

Verdegay

J-L

2012

The dual simplex method and sensitivity analysis for fuzzy linear programming with symmetric trapezoidal numbers

Fuzzy Optim Decis Making 10.1007/s10700-012-9152-7

Zhang

2006

A new approximate algorithm for solving multiple objective linear programming problems with fuzzy parameters

Appl Math Comput 174 524 544

Zimmermann

1978

Fuzzy programming and linear programming with sveral objective functions

Fuzzy Sets and Systems 1 45 55

Tanaka

Asai

1984

Fuzzy linear programming problems with fuzzy numbers

Fuzzy Set and Systems 13 1 10

Tanaka

Okudo

Asai

1974

On fuzzy mathematical programming

J Cybernet 3 37 46

Huang

Liu

2005

A coordination method for fuzzy multi-objective optimization of system reliability

Journal of Intelligent Fuzzy Systems 16 213 220

10.

Baky

2009

Fuzzy goal programming algorithm for solving decentralized bi-level multi-objective programming problems

Fuzzy Set and Systems 160 2701 2713

11.

Zhang

2007

On a generalized fuzzy goal optimization for solving fuzzy multi-objective linear programming problems

Journal of Intelligent Fuzzy Systems 18 83 97

12.

Ganesan

Veeramani

2006

Fuzzy linear programs with trapezolidal fuzzy numbers

Ann Oper Res 143 305 315

13.

Duran Toksar

2008

Taylor series approach to fuzzy multiobjective linear fractional programming

Information Sciences 178 1189 1204

14.

Luhandjula

1987

Multiple objective programming problems with possibilistic coefficients

Fuzzy Set and Systems 21 135 145

15.

Jiménez

Bilbao

2009

Pareto-optimal solutions in fuzzy multi-objective linear programming

Fuzzy Set and Systems 160 2714 2721

16.

Sakawa

Kato

1997

Interactive decision making for large-scale multiobjective linear programs with fuzzy number

Fuzzy Set and Systems 88 161 172

17.

Mahdavi-Amiri

Nasseri

2007

Duality results and a dual simplex method for linear programming problems with trapezoidal fuzzy variables

Fuzzy Set and Systems 158 1961 1978

18.

Bellman

Zadeh

1970

Decision making in a fuzy envionment

Management Sci 17 141 164

19.

Tong

1994

Interval number and fuzzy number linear programming

Fuzzy Set and Systems 66 301 306

20.

Liou

Wang

1992

Ranking fuzzy numbers with integral value

Fuzzy Sets and Systems 50 247 255

21.

Lai

Hwang

1992

A new approach to some possibilistic linear programming problems

Fuzzy Sets and Systems 49 121 133