An analytic method based on plane decomposition for solving two-stage fuzzy EV programming problem

1 Introduction

To model random uncertainty in decision-making process, stochastic programming was proposed by Dantzig [1], Charnes and Cooper [2], which offers a rigorous methodology to formulate optimization model affected by stochasticity. Furthermore, to characterize the dynamic nature of decision-making processes in practice, two-stage stochastic programming was formulated by Dantzig [1], Beale [3], Walcup and Wets [4], in which there are two optimization problems to solved. First-stage decisions are taken in the presence of stochastic uncertainty. In the second stage, recourse problem arises to perform the corrective actions where the recourse decisions (second-stage decisions) are taken after observing the realizations of random parameters. The coefficient matrix of the recourse decision vector is referred to as recourse matrix, which characterizes the feature of the recourse problem. However, the first-stage decisions are chosen by taking the future effects into account. Therefore, recourse function is employed to measure the future effects which is expressed by computing the expected value of the second-stage value function.

On account of solving two-stage stochastic programming by analytic method, L-shaped method based on cutting plane technology was developed by Van Slyke and Wets [5], which is one kind of Benders decomposition [6] and includes two main frameworks: feasibility cut and optimality cut. For instance, Marti [7] modeled the plastic design problem of mechanical structures as a two-stage stochastic linear programming with complete fixed recourse, and solved it by the L-shaped decomposition method. Two-stage stochastic linear programming is usually used to model the resilience system [8]. For other features of two-stage stochastic linear programming, the interested reader may refer to the books [9, 10] and the references therein.

Taking into account fuzzy uncertainty, fuzzy programming problems have been widely studied by many academic researchers. Baykasoglu and Gocken [11] presented a review of fuzzy mathematical programming models. Based on fuzzy theory [12, 13], many fuzzy programming problems were proposed, such as fuzzy multi-objective programming [14, 17], two-stage robust integer programming [15], supplier management [16], supply chain network design [18]. Credibility theory is a mathematical tool to deal with subjective uncertainty, it has been widely used in the literature, the interested reader may refer to [19, 20]. Within the framework of credibility theory, robust/reliability based optimization [21], p-hub center problems [22], fuzzy value-at-risk (VaR) optimization model [23], and location-routing problems [24] were formulated by researchers.

To cope with fuzzy dynamic modeling problem, Liu [25] firstly proposed two-stage fuzzy programming problem. Several examples of such two-stage programming problem with fuzzy variable can be found in fuzzy random programming with recourse [26], recourse-based facility-location problem [27], geometric programming problem [28], and uncapacitated hub location problem with recourse [29]. For the general two-stage fuzzy programming problems, due to the lack of linearity on fuzzy expected value operator, recourse function could not maintain the convexity of the second-stage value function. Then, cutting plane method could not apply directly to two-stage fuzzy programming due to recourse function without the desirable convexity. Therefore, two-stage fuzzy programming problems were usually solved by heuristic algorithms. Despite the considerable effects to solve two-stage fuzzy programming by many researchers through heuristic algorithms, the analytic solution method is also required urgently to solve this programming problem with accuracy and more efficiency.

The aim of this paper is to develop an analytic solution method based on plane decomposition to solve two-stage fuzzy programming problems. To the best of our knowledge, this issue has not yet been studied in two-stage fuzzy programming literatures. Taking advantage of credibility theory and L-S integral [30, 31], we show the formulation of two-stage fuzzy EV programming, discuss its properties, and then develop a new plane decomposition algorithm for solving this two-stage programming problem. The contributions of this study are summarized as three aspects:

We provide two EV definitions by means of L-S integral, and basic properties as well as Cauchy-Schwarz inequality on EV operator.

The remainder of paper is structured as follows. Section 2 provides two EV definitions by two different L-S measures, and discusses on the properties of EV operator. Section 3 focuses on two-stage fuzzy EV programming problem. Section 4 develops a new plane decomposition algorithm for solving this two-stage fuzzy programming problem. An application example is conducted in Section 5. Finally, Section 6 gives the conclusions.

2 L-S integral and EV

Combing with Lebesgue measure theory, L-S integral is developed on the basis of Riemann-Stieltjes integral which is produced for integrating one function with respect to another function. L-S integral is a powerful integration method especially in probability theory. We refer to the books [30, 31] for details on L-S integral and the references therein.

L-S integral is a class of linear integral with respect to L-S measure. By L-S integral, we can formulate the EV definitions of fuzzy variable and fuzzy variable’s function. Under different L-S measures generated by two types of nondecreasing functions, we will provide two definitions of EV to demonstrate the relation between L-S measure and EV.

Case I: Univariate Integral

Let ( Γ , P ( Γ ) , Cr ) be a credibility space, where Γ a universe, P ( Γ ) is the power set of Γ and Cr is a set function defined on P ( Γ ) . Suppose that ξ is a fuzzy variable defined on credibility space ( Γ , P ( Γ ) , Cr ) , and the monotone nondecreasing function of fuzzy variable ξ is usually defined as α ( t ) = Cr { ξ ≤ t } , t ∈ ℝ . Then we define the L-S α-Measure μ _α  (I) of interval I with end points a, b as follows μ α ( I ) = { α ( b + ) - α ( a - ) , I = [ a , b ] , α ( b + ) - α ( a + ) , I = ( a , b ] , α ( b - ) - α ( a - ) , I = [ a , b ) , α ( b - ) - α ( a + ) , I = ( a , b ) , and a < b . where α ( x - ) = lim t ↑ x α ( t ) , α ( x + ) = lim t ↓ x α ( t ) .

Definition 1. Let ξ be a fuzzy variable with nondecreasing function α (·), and f (x) a real-value function on ℝ . Then the EV of fuzzy variable function f (ξ) is defined as E [ f ( ξ ) ] = ∫ ℝ f ( t ) d α .

Specially, in the case that f (x) = x, the EV of fuzzy variable ξ can be achieved by E [ ξ ] = ∫ ℝ t d α .

In particular, when ξ is a discrete fuzzy variable with realizations ξ ˆ 1 , ξ ˆ 2 , … , ξ ˆ K , its monotone nondecreasing function α (t) is formulated as a left-continuous step function. Then E [ f ( ξ ) ] = ∑ k = 1 K f ( ξ ˆ k ) [ α ( ξ ˆ k ) - α ( ξ ˆ k - ) ] .

Example 1. Let ξ be a discrete fuzzy variable with following possibility distribution: ξ ∼ ( - 1 3 4 7 12 0.3 0.2 0.8 1 0.5 )

Firstly, calculate the monotone nondecreasing function of fuzzy variable ξ, α ( t ) = Cr { ξ ≤ t } = { 0 , t < - 1 , 0.15 , - 1 ≤ t < 4 , 0.4 , 4 ≤ t < 7 , 0.75 , 7 ≤ t < 12 , 1 , t ≥ 12 .

Then E [ ξ ] = ∫ ℝ t d α = ∑ k = 1 4 ξ ˆ k [ α ( ξ ˆ k ) - α ( ξ ˆ k - ) ] = ( - 1 ) × ( 0.15 - 0 ) + 3 × ( 0.15 - 0.15 ) + 4 × ( 0.4 - 0.15 ) + 7 × ( 0.75 - 0.4 ) + 12 × ( 1 - 0.75 ) = 6.3 .

Case II: Multivariate Integral

We now turn to show the EV definition of fuzzy variable’s function with more than one fuzzy variables, and adopt product measure α₁ × α₂ × ⋯ × α _n -measure as the L-S measure to construct L-S integral.

Let ξ _i , i = 1, 2, …, n be fuzzy variables defined on a credibility measure space ( Γ , P ( Γ ) , Cr ) . For each i, the monotone nondecreasing function of fuzzy variable ξ _i is computed by α i ( t i ) = Cr { ξ i ≤ t i } , t i ∈ ℝ . Let μ _{α i} be the L-S α-measure generated by monotone nondecreasing function α _i  (·), then we define the L-S α₁ × α₂ × ⋯ × α _n -measure of the polyhedron I₁ × I₂ × ⋯ × I _n , denoted by μ_{α1×α2×⋯×α n} , and μ α 1 × α 2 × ⋯ × α n ( I 1 × I 2 × ⋯ × I n ) = μ α 1 ( I 1 ) × μ α 2 ( I 2 ) × ⋯ × μ α n ( I n ) .

Definition 2. Let ξ _i be a fuzzy variable with monotone nondecreasing function α _i  (·) for i = 1, 2, …, n respectively, and f (x₁, x₂, …, x _n ) a real-value function on ℝ n . Then the EV of the function f (ξ₁, ξ₂, …, ξ _n ) is defined as E [ f ( ξ ) ] = E [ f ( ξ 1 , ξ 2 , … , ξ n ) ] = ∫ ℝ ∫ ℝ ⋯ ∫ ℝ f ( t 1 , t 2 , … , t n ) d α 1 d α 2 ⋯ d α n .

For more details about L-S measure generated by joint nondecreasing function, the interested reader may refer to [32].

In the case that ξ₁, ξ₂, …, ξ _n are discrete fuzzy variables with monotone nondecreasing function α _i  (·), i = 1, 2, …, n, respectively, we employ a fuzzy vector ξ , which is constructed by ξ₁, ξ₂, …, ξ _n and can be represented as ξ  = (ξ₁, ξ₂, …, ξ _n ) with realizations ξ ˆ k = ( ξ ˆ 1 i , ξ ˆ 2 j , … , ξ ˆ n l ) for k = 1, 2, …, K and K = N₁ × N₂ × ⋯ × N _n , where N _i is the number of realizations of fuzzy variable ξ _i for i = 1, 2, …, n. Then, according to Definition 2, the EV of f ( ξ ) = f (ξ₁, ξ₂, …, ξ _n ) can be computed as E [ f ( ξ ) ] = E [ f ( ξ 1 , ξ 2 , … , ξ n ) ] = ∑ i = 1 N 1 ∑ j = 1 N 2 ⋯ ∑ l = 1 N n f ( ξ ˆ 1 i , ξ ˆ 2 j , … , ξ ˆ n l ) · [ α 1 ( ξ ˆ 1 i ) - α 1 ( ξ ˆ 1 i - ) ] [ α 2 ( ξ ˆ 2 j ) - α 2 ( ξ ˆ 2 j - ) ] ⋯ [ α n ( ξ ˆ n l ) - α n ( ξ ˆ n l - ) ] .

For the sack of simplicity, we employ the notation Δα (·) to denote the variation of the joint monotone nondecreasing functions α₁ × α₂ × ⋯ × α _n at each realization ξ ˆ k = ( ξ ˆ 1 i , ξ ˆ 2 j , … , ξ ˆ n l ) , k = 1, 2, …, K, i.e., Δ α ( ξ ˆ k ) = [ α 1 ( ξ ˆ 1 i ) - α 1 ( ξ ˆ 1 i - ) ] [ α 2 ( ξ ˆ 2 j ) - α 2 ( ξ ˆ 2 j - ) ] ⋯ [ α n ( ξ ˆ n l ) - α n ( ξ ˆ n l - ) ] .

Then, the EV of f ( ξ ) can also be rewritten as E [ f ( ξ ) ] = ∑ k = 1 K f ( ξ ˆ k ) Δ α ( ξ ˆ k ) .

According to the above EV definitions, we can deduce several properties of EV operator as follows.

Proposition 1. Let ξ and η be fuzzy variables, we have

(Normality) If ξ ≥ 0, then E [ξ] ≥0;

Proof. i) The assert i) holds obviously.

ii) 1 ^o . Let ξ and η be discrete fuzzy variables with realizations ξ ˆ 1 , ξ ˆ 2 , … , ξ ˆ N 1 and η ˆ 1 , η ˆ 2 , … , η ˆ N 2 , and nondecreasing functions α₁, α₂ correspond to fuzzy variables ξ and η respectively, then E [ ξ ] = ∑ i ξ ˆ i [ α 1 ( ξ ˆ i ) - α 1 ( ξ ˆ i - ) ] , E [ η ] = ∑ j η ˆ j [ α 2 ( η ˆ j ) - α 2 ( η ˆ j - ) ] .

On the other hand, according to Definition 2, we have E [ a ξ + b η ] = ∑ i ∑ j ( a ξ ˆ i + b η ˆ j ) [ α 1 ( ξ ˆ i ) - α 1 ( ξ ˆ i - ) ] · [ α 2 ( η ˆ j ) - α 2 ( η ˆ j - ) ] = a E [ ξ ] ∑ j [ α 2 ( η ˆ j ) - α 2 ( η ˆ j - ) ] + b E [ η ] · ∑ i [ α 1 ( ξ ˆ i ) - α 1 ( ξ ˆ i - ) ] = a E [ ξ ] + b E [ η ] .

The above equation holds due to the fact that ∑ j [ α 2 ( η ˆ j ) - α 2 ( η ˆ j - ) ] = ∑ i [ α 1 ( ξ ˆ i ) - α 1 ( ξ ˆ i - ) ] = 1 .

2 ^o . If ξ and η be non-negative continuous fuzzy variables, there exist two discrete fuzzy variable sequences {ξ _n } and {η _n } such that ξ _n  ↑ ξ, η _n  ↑ η, and E [aξ _n  + bη _n ] = aE [ξ _n ] + bE [η _n ]. Let n→ ∞, then assert ii) also holds in this case.

3 ^o . When ξ and η are arbitrary continuous fuzzy variables, then they can be denoted as ξ = ξ⁺ - ξ^- and η = η⁺ - η^-, where ξ⁺ = max {ξ, 0} and ξ^- = - min {ξ, 0}. Note that ξ⁺, ξ^-, η⁺, η^- are non-negative continuous fuzzy variables.

iii) If ξ ≥ η, then ξ - η ≥ 0. It follows from assert i) and assert ii) that E [ξ - η] = E [ξ] - E [η] ≥0, then assert iii) holds.

iv) It follows from asserts ii) and iii) that assert iv) holds. In fact, for fixed ξ, arbitrary x 1 , x 2 ∈ ℝ and λ ∈ [0, 1], we have f ( λ x 1 + ( 1 - λ ) x 2 , ξ ) ≤ λ f ( x 1 , ξ ) + ( 1 - λ ) λ f ( x 2 , ξ ) , then E [ f ( λ x 1 + ( 1 - λ ) x 2 , ξ ) ] ≤ E [ λ f ( x 1 , ξ ) + ( 1 - λ ) f ( x 2 , ξ ) ] = λ E [ f ( x 1 , ξ ) ] + ( 1 - λ ) E [ λ f ( x 2 , ξ ) ] .

This completes the proof. □

Then, we provide the relation on EV operator, which is referred as to Cauchy-Schwarz inequality, and show the upper bound of EV of product of two fuzzy variables.

Proposition 2. (Cauchy-Schwarz inequality) Let ξ and η be fuzzy variables and ξ · η ≠ 0, we have E [ | ξ · η | ] ≤ E [ ξ 2 ] · E [ η 2 ] .

Proof. Firstly, we have E [ξ²] >0 and E [η²] >0. Let ξ ˜ = ξ E [ ξ 2 ] , η ˜ = η E [ η 2 ] , then 2 | ξ ˜ · η ˜ | ≤ ξ ˜ 2 + η ˜ 2 = ξ 2 E [ ξ 2 ] + η 2 E [ η 2 ] .

Taking EV operator E [·] to the both sides of the above inequality, then 2 E [ | ξ ˜ · η ˜ | ] ≤ 2 , it follows that Cauchy-Schwarz inequality holds. The proof is now completed. □

3 Formulation of two-stage fuzzy EV programming

By means of EV operator, we can formally present a generic two-stage EV programming problem with fixed recourse, which can be formulated as follows,

{ min x z = c T x + Q ( x ) subject to : A x = b , x ≥ 0 ,(1) where Q ( x ) = E [ Q ( x , ξ ) ] , E [·] is the EV operator, and

{ Q ( x , ξ ( γ ) ) = min y q ( γ ) T y subject to : W y = h ( γ ) - T ( γ ) x , y ≥ 0 .(2)

In the above formulation, we usually refer to Q ( x , ξ ) as the second-stage value function, and Q ( x ) is called as recourse function, which is equal to the EV of Q ( x , ξ ). The first-stage decision is represented by the vector x  = (x₁, x₂, …, x _{n 1} )  ^T , while the second-stage decision is represented by y  = (y₁, y₂, …, y _{n 2} )  ^T . The technology matrix A and recourse matrix W are known matrices of sizes m₁ × n₁ and m₂ × n₂ respectively, c and b are known vectors in ℝ n 1 and ℝ m 1 respectively. For each γ ∈ Γ, q ( γ ) ∈ ℝ n 2 , h ( γ ) ∈ ℝ m 2 , and T  (γ) is an m₂ × n₁ matrix ( T ₁ (γ) ,   T ₂ (γ) ,   … ,   T _{n 1}  (γ)), where T _i  (γ) is the i-th column of matrix T  (γ) for i = 1, 2, …, n₁. Therefore, we obtain a fuzzy vector ξ  = ( q  (γ)  ^T ,   h  (γ)  ^T ,   T ₁ (γ)  ^T ,   T ₂ (γ)  ^T ,   … ,   T _{n 1}  (γ)  ^T ) with n₂ + m₂ + n₁ × m₂ components. The decisions x are here-and-now (or first-stage) decisions that are taken before the realizations of the fuzzy parameter ξ is known, whereas the wait-and-see (or second-stage) decisions y can adapt to the realization of ξ .

Remark 1. Suppose that fuzzy vector ξ is constructed by discrete fuzzy variables ξ₁,  ξ₂,   … , ξ _n , and each fuzzy variable ξ _i possesses a monotone nondecreasing function α _i  (·). Then, according to Definition 2, the value of recourse function Q ( x ) at x can be computed by the formula Q ( x ) = E [ Q ( x , ξ ) ] = ∑ k = 1 K Q ( x , ξ ˆ k ) Δ α ( ξ ˆ k ) , where each realization ξ ˆ k = ( ξ ˆ 1 i , ξ ˆ 2 j , … , ξ ˆ n l ) can also be stated as ξ ˆ k = ( q ˆ k , h ˆ k , T ˆ 1 k ( γ ) T , T ˆ 2 k ( γ ) T , … , T ˆ n 1 k ( γ ) T ) , k = 1 , 2 , … , K . Meanwhile, for each ξ ˆ k , the second-stage value function Q ( x , ξ ˆ k ) can be obtained from the following programming problem

{ Q ( x , ξ ˆ k ) = min y q ˆ k T y subject to : W y = h ˆ k - T ˆ k x , y ≥ 0 .(3)

Let K₁ = { x  ∣ A x  =  b } be the set determined by the technology matrix A, and the set does not depend on the particular realization of fuzzy vector ξ . Let K₂ be the second-stage feasibility set, which can be stated as K 2 = { x ∣ Q ( x ) ≤ ∞ } . All elements in K₂ are those decisions x for which the second-stage problem has a feasible solution for almost every realization or scenario ξ ˆ k . Let Ξ be the support of fuzzy vector ξ , i.e., the smallest closed subset in ℝ such that Cr {γ ∣  ξ  (γ) ∈ Ξ} =1. The deterministic equivalent programming problem of this two-stage EV programming problem can be rewritten as

{ min x z = c T x + Q ( x ) subject to : x ∈ K 1 ∩ K 2 .(4)

Next, we will turn to demonstrate several theorems, which play an important role in the proposed decomposition algorithm. At first, to facilitate us to clarify the problem, define a set K 2 ( ξ ( γ ) ) = { x ∣ Q ( x , ξ ) < ∞ } = { x ∣ y ≥ 0 exists , s . t . W y = h ( γ ) - T ( γ ) x } which is referred to as “fuzzy elementary feasibility set”. In the following, we demonstrate the convex property of the second-stage feasibility set K₂ through fuzzy elementary feasibility set K₂ ( ξ  (γ)) under mild conditions.

Theorem 1. i) For a given fuzzy vector ξ , the fuzzy elementary feasibility set K₂ ( ξ  (γ)) is a convex polyhedron;

ii) When ξ is a finitely discrete fuzzy vector, K₂ is a convex polyhedron.

Proof. i) Let x ₁, x ₂ ∈ K₂ ( ξ ), x ¯ = λ x 1 + ( 1 - λ ) x 2 ( 0 ≤ λ ≤ 1 ) and W y ₁ =  h  (γ) -  T  (γ)  x ₁, W y ₂ =  h  (γ) -  T  (γ)  x ₂, then W [ y 1 + ( 1 - λ ) y 2 ] = h ( γ ) - T ( γ ) x ¯ . Due to y ₁ + (1 - λ)  y ₂ ≥ 0, then K₂ ( ξ  (γ)) is a convex set.

Let pos W = { t  ∣ W y  =  t ,  y ≥ 0} be a convex set. Now, we prove the polyhedron K₂ ( ξ  (γ)) by the set pos W. Consider some x and ξ  (γ), it follows from x  ∈ K₂ ( ξ  (γ)) that h  (γ) -  T  (γ)  x  ∈ pos W. If no y  ≥ 0 exists such that W y  =  h  (γ) -  T  (γ)  x , i.e. " x  ∉ K₂ ( ξ  (γ)) ⇔ some x and ξ  (γ) such that h  (γ) -  T  (γ)  x  ∉ pos W". Then, there exists a point h  (γ) -  T  (γ)  x , which does not belong to the convex set pos W. By the separation theorem of convex sets, there must exist some hyperplanes { x  ∣  σ ^T x  = 0} that separate h  (γ) -  T  (γ)  x from pos W. These hyperplanes satisfy σ ^T x  ≤ 0 for x ∈ pos W and σ [ h  (γ) -  T  (γ)  x ] >0. Because recourse matrix W is fixed, there are only finitely many different such hyperplanes. Combining the above two conclusions, K₂ ( ξ  (γ)) is a convex polyhedron.

ii) When ξ is a finitely discrete fuzzy vector, then K 2 = ⋂ ξ ∈ Ξ K 2 ( ξ ( γ ) ) , the intersection of finitely many convex polyhedron is also a convex polyhedron. The proof is now completed. □

Theorem 2. For arbitrary fuzzy vector ξ with the condition that E [ ξ ²]< ∞, then K₂ = ⋂  _{ξ ∈Ξ}K₂ ( ξ  (γ)) and K₂ is a convex set.

Proof. For ∀ x ∈ K₂, then Cr {γ ∣ Q ( x , ξ ) < ∞} =1. On the other hand Cr {γ ∣  ξ  (γ) ∈ Ξ} =1. We have { γ ∣ Q ( x , ξ ) < ∞ } ∩ { γ ∣ ξ ( γ ) ∈ Ξ } = { γ ∣ ξ ( γ ) ∈ Ξ , Q ( x , ξ ) < ∞ } which is a closed set of {γ ∣  ξ  (γ) ∈ Ξ} with credibility 1. Thus, Cr {γ ∣  ξ  (γ) ∈ Ξ, Q ( x , ξ ) < ∞} =1 and {γ ∣  ξ  (γ) ∈ Ξ} = {γ ∣  ξ  (γ) ∈ Ξ, Q ( x , ξ ) < ∞}. Then { ξ  ∣ Q ( x , ξ ) < ∞} ∈ Ξ. Therefore, x  ∈ ⋂  _{ξ ∈Ξ} { x  ∣ Q ( x , ξ ) < ∞}, K₂ ⊆ ⋂  _{ξ ∈Ξ}K₂ ( ξ  (γ)) .

For ∀ x ∈ ⋂  _{ξ ∈Ξ}K₂ ( ξ  (γ)), and a fixed ξ , solving the programming problem (2), we can finding an optimal basis B which is a square submatrix of W, and Q ( x , ξ ) can be computed by Q ( x , ξ ) =  q _B  (γ)  ^T B^-1 ( h  (γ) -  T  (γ)  x ) where q _B  (γ) is the subvector of q  (γ) associated to the optimal basis B. Then, the recourse function can be rewritten as Q ( x ) = E [ Q ( x , ξ ) ] = E [ q B ( γ ) T B - 1 ( h ( γ ) - T ( γ ) x ) ] . Due to the condition that E [ ξ ²]< ∞, then E [ ( q B ( γ ) T ) 2 ] < ∞ , E [ ( h ( γ ) - T ( γ ) x ) 2 ] < ∞ .

According to Cauchy-Schwarz inequality of Proposition 2, we have E [ | Q ( x , ξ ) | ] < ∞ , i . e . , Q ( x ) < ∞ . Therefore, x  ∈ K₂ and ⋂ _{ξ ∈Ξ}K₂ ( ξ  (γ)) ⊆ K₂. We conclude that K₂ = ⋂  _{ξ ∈Ξ}K₂ ( ξ  (γ)) in this case. It follows from assert i) of Theorem 1 that K₂ ( ξ ) is a convex set, then K₂ is also a convex set. This completes the proof. □

In the following, we will demonstrate the convexity of second-stage value function Q ( x , ξ ) and recourse function Q ( x ) , and show that recourse function Q ( x ) is a convex polyhedral function on K₂.

Theorem 3. i) For a given fuzzy vector ξ , the second-stage value function Q ( x , ξ ) is a piecewise linear function, and Q ( x , ξ ) and recourse function Q ( x ) are convex functions on K₂;

ii) When ξ is a finitely discrete fuzzy vector with realizations ξ ˆ 1 , ξ ˆ 2 , … , ξ ˆ K , then Q ( x ) is a piecewise linear function on K₂.

Proof. i) Let B be the optimal basis of the programming problem (2), then Q ( x , ξ ) =  q _B  (γ)  ^T B^-1 ( h  (γ) -  T  (γ)  x ) which is linear in x on K₂. Due to the fact that second-stage programming problem (2) exists finitely different optimal bases, it follows that the value function Q ( x , ξ ) is a piecewise linear function for all x  ∈ K₂.

Let x ₁,   x ₂ ∈ K₂ and y 1 * , y 2 * be the optimal solutions to the second-stage programming problem (2) corresponding to x ₁,   x ₂ respectively, then Q ( x 1 , ξ ) = q ( γ ) T y 1 * , Q ( x 2 , ξ ) = q ( γ ) T y 2 * . On the other hand, for λ ∈ [0, 1], Q ( λ x 1 + ( 1 - λ ) x 2 , ξ ) = min { q ( γ ) T y ∣ W y = h ( γ ) - T ( γ ) [ λ x 1 + ( 1 - λ ) x 2 ] , y ≥ 0 } .

We know that λ y 1 * + ( 1 - λ ) y 2 * is a feasible solution to the above programming problem, let y ^* be an optimal solution of this problem, then Q ( λ x 1 + ( 1 - λ ) x 2 , ξ ) = q ( γ ) T y * ≤ q ( γ ) T [ λ y 1 * + ( 1 - λ ) y 2 * ] = λ Q ( x 1 , ξ ) + ( 1 - λ ) Q ( x 2 , ξ ) .

Therefore, Q ( x , ξ ) is a convex function. By the assert iv) of Proposition 1, we know that Q ( x ) = E [ Q ( x , ξ ) ] is also a convex function.

ii) When ξ is a finitely discrete fuzzy vector with realizations ξ ˆ 1 , ξ ˆ 2 , … , ξ ˆ K , then Q ( x ) = ∑ k = 1 K Q ( x , ξ ˆ k ) Δ α ( ξ ˆ k ) .

According to the above proof, the second-stage value function Q ( x , ξ ˆ k ) is a piecewise linear convex function in x , and Δ α ( ξ ˆ k ) > 0 , the linear summation of finite function Q ( x , ξ ˆ k ) is also a piecewise linear function in x on K₂. The proof of theorem is now completed. □

Theorem 4. Let ξ be a discrete fuzzy vector with realizations ξ ˆ k for k = 1, 2, …, K. Let π ¯ k denotes the optimal simplex multiplier corresponding to the solution to the second-stage programming problem (2) with x = x ¯ ∈ K 2 and realization ξ ˆ k , then π ¯ k ( h ˆ k - T ˆ k x ) ≤ Q ( x , ξ ˆ k ) , and ∑ k = 1 K π ¯ k ( h ˆ k - T ˆ k x ) Δ α ( ξ ˆ k ) is a support of the recourse function Q ( x ) .

Proof. For the realization ξ ˆ k , the dual programming of second-stage programming problem (2) can be stated as

{ max π π [ h ˆ k - T ˆ k x ] subject to : π W ≤ q ˆ k .(5)

Since π ¯ k is the optimal simplex multiplier for the second-stage programming problem (2) with x = x ¯ , according to the duality theory, we have π ¯ k ( h ˆ k - T ˆ k x ¯ ) = Q ( x ¯ , ξ ˆ k ) .

Because the constraints of dual programming (5) are independent of x , π ¯ k is a feasible solution to dual programming (5) for all x  ∈ K₂. Let π _k be the optimal solution to dual programming (5) corresponding to x , then π ¯ k ( h ˆ k - T ˆ k x ) ≤ π k ( h ˆ k - T ˆ k x ) = Q ( x , ξ ˆ k ) , k = 1 , 2 , … , K .

By multiplying Δ α ( ξ ˆ k ) to the both sides of the above inequality, then π ¯ k ( h ˆ k - T ˆ k x ) Δ α ( ξ ˆ k ) ≤ Q ( x , ξ ˆ k ) Δ α ( ξ ˆ k ) .

Taking summation from k = 1 to K, we have ∑ k = 1 K π ¯ k ( h ˆ k - T ˆ k x ) Δ α ( ξ ˆ k ) ≤ ∑ k = 1 K Q ( x , ξ ˆ k ) Δ α ( ξ ˆ k ) = Q ( x ) , which completes the proof of theorem. □

Theorem 5. Suppose that Q ( x ) is finite on K₂, and ξ is a finitely discrete fuzzy vector with realizations ξ ˆ 1 , ξ ˆ 2 , … , ξ ˆ K . Then Q ( x ) is a convex polyhedral function.

Proof. By letting x range over K₂, we know that only a finite number of supports ∑ k = 1 K π ¯ k ( h ˆ k - T ˆ k x ) Δ α ( ξ ˆ k ) of Q ( x ) can be generated, since each π ¯ k corresponds to an optimal basis B, which is a square submatrix of W. Moreover, recourse matrix W has only a finite number of square submatrices. On the other hand, for all x ¯ ∈ K 2 , there exists a support which satisfies that ∑ k = 1 K π ¯ k ( h ˆ k - T ˆ k x ¯ ) Δ α ( ξ ˆ k ) = Q ( x ¯ ) . Therefore, the upper envelope of this finite number of linear supports coincides with Q ( x ) . This completes the proof. □

These theorems above devote theoretical foundation to algorithm analysis, and play a key role in formulation of plane decomposition algorithm.

First of all, we provide the equivalent representation of programming problem (4) as follows

{ min x z = c T x + θ subject to : Q ( x ) ≤ θ , x ∈ K 1 ∩ K 2 .(6)

The analytic solution method based on plane decomposition solves the two-stage EV programming problem by considering that each scenario is independent and therefore the prime problem structure can be decomposed into a master problem (a relaxed formulation of the first-stage programming problem) and a number of subproblems to speed up the solution time. The decisions of these subproblems are linked to the master problem through the approximation θ of objective function of the second-stage programming problems. At the first iteration, θ is set to zero. Then, two main frameworks are used, one is feasibility cut and another is optimality cut, which add iteratively to the master problem of fuzzy EV programming problem. Therefore, the master problem will be updated by introducing new cut constraints at each iteration. This algorithm proceeds as follows:

Remark 2. In Step 3, we usually add the checking process on Δ α ( ξ ˆ k ) before deciding to carry on this step to obtain the optimal simplex multiplier of x ^v with respect to ξ ˆ k . In fact, if Δ α ( ξ ˆ k 0 ) = 0 , then the terms π k 0 v h ˆ k 0 Δ α ( ξ ˆ k 0 ) and π k 0 v T ˆ k 0 Δ α ( ξ ˆ k 0 ) are also equal to zero. These two terms have no effect on e_s+1 and E _s+1 respectively. Based on this fact, Step 3 only requires us to consider the optimality of any solution x ^v with respect to ξ ˆ 1 , ξ ˆ 2 , … , ξ ˆ k 0 - 1 , ξ ˆ k 0 + 1 , … , ξ ˆ K .

In order to illustrate the convergence of the algorithm, we now reasonable demonstrate that the algorithm will converge to the optimal solution at most a finite number of iterations.

Theorem 6. When two-stage fuzzy EV programming problem has a finite number of second-stage realizations, the plane decomposition algorithm applying to this programming problem converges to the optimal solution after finite iterations.

Proof. At first, we now prove that a finite number of feasibility cuts are generated to guarantee x ^v  ∈ K₂. In Step 2, a necessary condition for x ^v  ∈ K₂ is that σ k v [ h ˆ k - T ˆ k x v ] ≤ 0 .

On the one hand, there are only a finite number of optimal bases (the basis of W) solved in Step 2. On the other hand, it follows from Theorem 1 that the second-stage feasible set K₂ is a convex polyhedron when ξ is a finitely discrete fuzzy vector. Then we conclude that this algorithm can obtain a feasible solution as long as a finite number of such feasibility cuts exist in Step 2.

We then prove that at most finitely many optimality cuts are required to convergence to the optimal solution in Step 3. For the solution x ^v , the second-stage programming problem is solved repeatedly for each k = 1, 2, …, K, yielding optimal simplex multipliers π k v . If ( x ^v , θ ^v ) is optimal for programming problem (6), it follows that Q ( x v ) = θ v . Then, according to Theorem 4, this happens ∑ k = 1 K π k v ( h ˆ k - T ˆ k x v ) Δ α ( ξ ˆ k ) = θ v which justifies the termination criterion in this step. If ( x ^v , θ ^v ) is not optimal, then Q ( x v ) > θ v . Therefore, a new optimality cut ∑ k = 1 K π k v ( h ˆ k - T ˆ k x ) Δ α ( ξ ˆ k ) ≤ θ v or E s + 1 x + θ ≥ e s + 1 is generated. Because each π k v corresponds to one basis of programming problem (3), and there are only a finite number of different combinations of the K multipliers π k v , then this programming problem converges to the optimal solution after finite optimality cuts. This completes the proof. □

For clearly showing the solution process of the proposed algorithm, we carry out a numerical example to demonstrate the applicability of the proposed decomposition algorithm. The data of model are stated as follows A = ( 1 2 ) , b = ( 5 ) , c = ( 2 1 ) , W = ( 1 2 2 1 ) , q ( γ ) = ( η + 1 ξ ) , h ( γ ) = ( 2 ξ ξ ) , T ( γ ) = ( - ξ η η - 2 ξ ) , where ξ and η are discrete fuzzy variables with the following possibility distributions ξ ∼ ( 1 1.5 2 2.5 0.3 0.2 1 0.5 ) , η ∼ ( 0 1 ) .

Meanwhile, the monotone nondecreasing functions α₁, α₂ corresponding to two fuzzy variables ξ and η can be stated as α 1 ( t 1 ) = Cr { ξ ≤ t 1 } = { 0 , t 1 < 1 , 0.15 , 1 ≤ t 1 < 2 , 0.75 , 2 ≤ t 1 < 2.5 , 1 , t 1 ≥ 2.5 . α 2 ( t 2 ) = Cr { η ≤ t 2 } = { 0 , t 2 < 0 , 1 , t 2 ≥ 0 .

Then, fuzzy vector ξ = ( q ( γ ) T , h ( γ ) T , T 1 ( γ ) T , T 2 ( γ ) T ) is constructed by discrete fuzzy variables ξ and η, which is a discrete fuzzy vector with the following realizations ξ ˆ k , ξ ˆ 1 = ( 1 , 1 , 2 , 1 , - 1 , 0 , 0 , - 2 ) , ξ ˆ 2 = ( 1 , 1.5 , 3 , 1.5 , - 1.5 , 0 , 0 , - 3 ) , ξ ˆ 3 = ( 1 , 2 , 4 , 2 , - 2 , 0 , 0 , - 4 ) , ξ ˆ 4 = ( 1 , 2.5 , 5 , 2.5 , - 2.5 , 0 , 0 , - 5 ) .

In this case, for the realization ξ ˆ 2 , Δ α ( ξ ˆ 2 ) = [ α 1 ( ξ ˆ 2 ) - α 1 ( ξ ˆ 2 - ) ] [ α 2 ( η 1 ) - α 2 ( η 1 - ) ] = [ α 1 ( 1.5 ) - α 1 ( 1.5 - ) ] [ α 2 ( 0 ) - α 2 ( 0 - ) ] = 0 .

Due to this fact, for a given feasible solution x ^v , we need only to check the optimality of solution x ^v with respect to ξ ˆ 1 , ξ ˆ 3 and ξ ˆ 4 .

In the following, we turn to solve the two-stage fuzzy EV programming problem to show the iteration process of plane decomposition algorithm.

The First Iteration:

The Second Iteration: