Fuzzy Random Minimum Cost Network Flow Programming Problem Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

In this paper, a fuzzy random minimum cost flow problem is presented. In this problem, cost parameters and decision variables are fuzzy random variables and fuzzy numbers respectively. The object of the problem is to find optimal flows of a capacitated network. Then, two algorithms are developed to solve the problem based on Er-expected value of fuzzy random variables and chance-constrained programming. Furthermore, the results of two algorithms will be compared. An illustrative example is also provided to clarify the concept.

Network flow programming problems have many applications in the real world such as transportation problems, traffic problems in road systems, currents in an electrical circuit, fluids in pipes, or something travels through a network of nodes (Ahuja et al, 1993). The Minimum Cost network Flow (MCF) problem is one of the most important network flow problems. Indeed, it is a general form of network flow problems and has an important role in studying of network flow problems. Therefore, we can apply the results obtained by studying the MCF problem to other network flow problems such as transportation, maximum flow, assignment and shortest path problems (Shih and Stanley, 1999). This results can be included the solution approaches, imprecise extensions, etc.

There are two types of common uncertainties in the real-life world: randomness and fuzziness. We apply the fuzzy stochastic framework (Katagiri and Ishii, 2000, Puri and Ralescu, 1986) to handle uncertain and flexible temporal information contains both possibility and probability aspects. Fuzzy Random Variable (FRV) initiated by Kwakernaak (1978) is one of the appropriate ways to describe this type of uncertainty. Indeed, fuzzy stochastic theory (Wang and Zang, 1992; Wang and Zhong, 1993; Wang, 1999) can provide a useful framework for managing this uncertain and flexible temporal information.

In real situation, parameters of network flow problems have imprecise properties (Shih and Stanley, 1999; Okada and Soper, 2000; Lin and Wen, 2004; Eshghi and Nematian, 2008). This vagueness can be possibilistic imprecision, probability uncertainty or both of them. Fuzzy, random, and fuzzy random variables can be applied for it respectively.

In this paper, the minimum cost flow problem whose cost parameters are FRVs and the other parameters and decision variables are fuzzy variables is considered. Then, two approaches are designed to solve the Fuzzy Random Minimum Cost Flow (FRMCF) problem and experimental results on both of them are compared. One of the solution approaches is based on Er-expected value of FRVs and the other one is designed by using Chance-Constrained Programming () method (Charnes and Cooper 1959). Furthermore, fuzzy optimization method is used in both of the solution approaches.

We can calculate a proper confidence level for stochastic programming. In fact, provides a measure to evaluate the risk that a decision vector is not optimal probabilistically.

This paper is organized as follows: Section 2 presents some preliminaries on fuzzy stochastic theory. Then, the FRMCF problem is introduced in section 3. The mathematical programming models and two algorithms to solve the FRMCF problem are presented in sections 4 and 5. The concluding remarks and suggestions for further research are discussed in the last section.

2. Preliminaries

This section reviews some technical terms presented by Puri and Ralescu (1986). In the following definitions, we assume that is a probability space and is a possibility space where is universe, is the power set of and is a possibility measure defined on fuzzy sets. Furthermore, is a collection of all normalized fuzzy numbers whose -level sets are convex subsets of .

A fuzzy set on is called a fuzzy number if it is normal, convex and upper semi-continuous and its support set is compact. LR fuzzy number (Dubois and Prade, 1979, 1988) is a special fuzzy number used frequently. We will use standard fuzzy arithmetic, from the extension principle, to perform sums, products, etc. of fuzzy numbers (Dubois and Prade, 1980, Zadeh, 1973).

Definition 1. Let and be two LR fuzzy numbers then , , , and are also fuzzy numbers as follows:

Definition 2 (Hukuhara, 1967; Diamond and Korner, 1997). Let and be two LR fuzzy numbers, if the Hukuhara's difference exists it is given by

.

A fuzzy random variable (FRV) is a random variable and a Borel measurable function whose actual value is a fuzzy number (Puri and Ralescu, 1986). It is frequently used in uncertain systems.

Lemma 1 (Wang and Zang, 1992). If is a fuzzy random variable, then an α-cut is a random interval for every .

Expected value is a fundamental concept for FRV. In order to define the expected value of an FRV, several operators were introduced in literature [Liu and Liu, 2003; Wang and Zhong, 1993]. The expectation of a FRV is a fuzzy number (Wang 1992, 1993).

Definition 3 (Eshghi and Nematian, 2008). Let be a FRV then we can define the scalar expected value of , denoted by and called it Er-expected value of , as follows:

where and are expected values of and respectively.

Corollary 1. Let and be FRV and then

i) ii) iii) .

Definition 4(Buckley and Feuring, 2000). Let be a fuzzy number variable. The problem of minimization is equivalent to a multi-objective optimization problem as follows: .

Definition 5 (Buckley and Feuring, 2000). Let and be two fuzzy numbers. Then we have:

Now we discuss a method to evaluate the fuzzy random inequality or where and are fuzzy random variables. It is obvious that and in this case are fuzzy numbers and can be compared based on definition 5.

Definition 6. Let and be fuzzy random variables. Then the relations " " and "" are defined respectively as follows:

i) Iff

ii) Iff

3. Problem Formulation (Shih and Stanley, 1999)

A minimum cost flow problem is to find optimal flows of edges with the least cost in a capacitated network according to a number of resources of nodes and a capacity of edges. Let be a directed network where and are sets of nodes and edges respectively. This network has a cost and a capacity for every edge and a number of resources for every node, which distinguish the type of node. It is clear that node is a transit node if and it is a supplier (demander) if (). We suppose that and the MCF problem has feasible solution (Shih and Stanley, 1999). The MCF problem is formulated as follows:

where is the amount of flow on edge , . In our model, we assume that the costs are fuzzy random variables. Therefore, the cost function becomes a fuzzy random variable too. Furthermore, we suppose that the decision variables , the capacities and the resources are fuzzy number variables.

In the following model, called Fuzzy Random Minimum Cost Flow and denoted by FRMCF, we consider each cost term of FRMCF as a fuzzy random variable:

where is the Hukuhara difference operator, represents fuzzy random variables involved in the objective function. Furthermore, , and are fuzzy variables and represent the amount of flow on edge , the capacities of edge and the resource of node respectively.

In next section, we explain our solution approaches and compare the results of them. In addition, we will be able to obtain a measure to evaluate the risk of dis-optimality of a decision vector probabilistically.

4. Solution Approaches of FRMCF Problems

In this section, two solution approaches of FRMCF problem are proposed. Then their results are compared and a criterion is presented to measure the risk of non-optimality in decision variables.

4.1. Er-expected Value Programming Approach

First, we use the concept of Er-expected value of fuzzy random variables to convert fuzzy random version of problem to a fuzzy linear programming problem (Eshghi and Nematian, 2008). Then the minimization of fuzzy variables (Buckley and Feuring, 2000) and the concept of triangular fuzzy variables are used to convert fuzzy linear programming problem to a multi-objective optimization problem. Furthermore, we solve the multi-objective optimization problem by using Zimmermann fuzzy approach (Zimmermann, 1978). In this approach, Bellman and Zadeh's max-min operator (Bellman and Zadeh, 1970) has been used.

By using the concept of Er-expected value of fuzzy random variables and corollary (1), Problem (1) can be converted to the following fuzzy linear programming problem:

By considering the concept of fuzzy numbers, Problem (2) can be written as follows:

where , .

The following problem is generated if we apply the "Minimizing Fuzzy Number Variable Method" and fuzzy inequality approach to the Problem (3):

Let , and be lower bounds of , and respectively and , and be their initial tolerance values. By considering the membership function of fuzzy objective function and using Bellman and Zadeh's max-min operator, Problem (4) can be converted to the following problem:

The above problem is a linear programming problem and can be easily solved by one of the LP solver. If we suppose that, and are the optimal solution of Problem (5) then an Er-optimal solution of the original FRMCF problem can be obtained by , which are fuzzy numbers. Furthermore,

.

This approach is able to calculate the Er-optimal solution of the FRMCF problem. Now, we apply another approach contains other probabilistic information of FRV. In this approach, a chance-constrained programming is used.

4.2. Chance-Constrained Programming Approach

First, the concepts of fuzzy random variables, fuzzy variables and extended binary operation such as , and are used to convert the original problem to a multi-objective stochastic programming. Then, we use chance-constrained programming approach to solve it. Furthermore, Zimmermann fuzzy approach is used to solve the multi-objective programming problem.

Consider the following FRMCF problem:

By using the concept of extended binary operation and and fuzzy inequality approach, Problem (6) can be converted to the following problem:

The following problem is generated if we apply the "Minimizing Fuzzy Number Variable Method" to the Problem (7):

By using the chance-constrained multi-objective programming which is provided by Charnes and Cooper (1959), Problem (8) can be changed as follows:

Let and be lower bounds of and respectively, be upper bounds of and , and be their initial tolerance values. We use the membership function of fuzzy objective function and Bellman and Zadeh's max-min operator to convert Problem (9) to the following problem:

where is the predetermined confidence level provided by a decision maker. In this problem, the random variables can have different probability distributions. Therefore, several models will be found from Problem (10). Based on probability properties and expert opinions, a proper model will be selected and solved. Now we suppose that these random variables have normal distribution with a definite expectation and an exact variance. Therefore, we have the following mathematical programming:

We can obtain a local optimal solution of the above nonlinear programming problem (NLP) by LINGO 8.0 or obtain its global optimal solution by Global solver of LINGO 8.0. If we suppose that , and are the optimal solution of Problem (11), then a -optimal solution of the original FRMCF problem can be obtained by , where are LR fuzzy numbers.

Now, we compare these two approaches. Let and be optimal values of Er-expected and approach respectively. We can easily write FRMCF problem with Er-expected and approach as follows respectively:

where is the feasible region of Problem (1). Since for every then . Furthermore, we can obtain other relations for the left and right spread of fuzzy optimal values.

We can also calculate the risk of non-optimality of a decision vector with probability aspect by selecting a proper confidence level in approach.

The FRMCF problem was solved by the chance-constrained multi-objective programming with the predetermined confidence level. Therefore, the solution is related to a confidence level in the chance-constrained programming approach. However, we have a pure solution by the Er-expected value programming approach. If these two solutions are compared to each other, a confidence level will be obtained which is useful to evaluate probabilistically the optimality of a decision vector.

5. Algorithms for Solving FRMCF Problem

In the following steps, we describe the general steps of two algorithms for solving FRMCF problem with Er-expected and approach:

Algorithm 5.1 ( Er-expected approach)

Step 0. Define a membership function for each fuzzy and fuzzy random variable in Problem (1) and determine the Er-expected value of the fuzzy random variables.

Step1. Convert Problem (1) to Problem (2) by using the concept of Er-expected value of fuzzy random variables.

Step2. Convert Problem (2) to Problem (3) by using the concepts of fuzzy numbers.

Step3. Convert Problem (3) to Problem (4) by minimization of fuzzy variables and fuzzy inequality approaches.

Step4. Convert Problem (4) to Problem (5) by Bellman and Zadeh's max-min operator. Problem (5) is a linear programming model.

Step5 Solve Problem (5) as a Linear Programming model by one of the LP solvers. Let ,, be Er-expectedsolutions. Then the Er-optimal solution of the original problem is obtained by .

Algorithm 5.2 ( approach)

Step 0. Define a membership function for each fuzzy and fuzzy random variable in Problem (1).

Step1. Convert Problem (1) to Problem (6) by using the concept of fuzzy numbers.

Step2. Convert Problem (6) to Problem (7) by using the concept of extended binary operations and fuzzy inequality approach.

Step3. Convert Problem (7) to Problem (8) by minimization of fuzzy variables.

Step4. Convert Problem (8) to Problem (9) by using the chance-constrained multi-objective programming method.

Step5. Convert Problem (9) to Problem (11) by Bellman and Zadeh's max-min operator. Problem (11) is a nonlinear programming model.

Step6. Solve Problem (11) as a Nonlinear Programming model by LINGO 8.0 or Global solver of LINGO 8.0 . Let ,, be -approach solutions. Then the -optimal solution of the original problem is obtained by .

Now, a numerical example of a fuzzy random MCF problem is given to clarify the model discussed in this paper.

Example (Shih and Stanley, 1999). Assume that a network consists of 9 nodes and 13 edges as it is represented by the directed network shown in Fig.1. The resource of nodes, the capacity of edges, and the amount of flow on edges are fuzzy number variables. Suppose that is the fuzzy resource for the node , is fuzzy capacity of edge , and represents the amount of flow on edge . Furthermore, the costs of edges are fuzzy random variables. Suppose that is the fuzzy random cost for the edge where and are normal random variables. Furthermore, .

Furthermore, suppose that are random variables with exact expectation on and.

Now we have the following relations:

1

2

4

3

5

8

6

7

9

Fig.1. A network with 9 nodes and 13 edges.

In this example, we assume that fuzzy random costs are given in table 1 and fuzzy number capacities of edges and fuzzy number resources of nodes are given in Table 2 and Table4:

Table 1: Fuzzy random costs of edges

2

2.5

1

2

7

5.5

6.5

3

4

8

5

9

10

0.5

0.5

0

0.5

1

1

0.75

0.5

1

1

1.5

1

1

0.5

0

0.5

0.5

0.5

0.75

1

0.5

1.5

1

1

1

1.5

1

1

1

1

1

1

1

1

1

1

1

1

1

Table 2: Fuzzy number capacities of edges

14

17

13

10

14

15

15

24

20

19

13

15

20

12

15

12

8

13

13

12.5

20

16

18

12

13

19

13

16

13

9

12

12

13.5

21

18

19

12.5

14

18

Therefore, the values of are calculated as follows:

Table 3: The values of

2

2.375

1.125

2

6.875

5.4375

6.5625

3

4.125

8

4.875

9

10.125

Table 4: Fuzzy number resource of nodes

Supplier nodes

Demander nodes

Transit nodes

Apply the first proposed algorithm to the above fuzzy random minimum cost flow problem and solve the obtained LP problem by the one of the LP solver. The following LP model is generated:

The above model can be easily solved by LINGO 8.0, which is one of the commercial ILP solvers, and the optimal solution of the model is summarized in the fourth column of Table 7.

Now apply the second proposed algorithm to the above fuzzy random minimum cost flow problem and solve the obtained nonlinear programming problem by LINGO 8.0 or Global solver of LINGO 8.0. The following NLP model is generated by considering the predetermined confidence levels:

The above model can be solved by LINGO 8.0 and the local optimal solution of the model could be summarized in the fifth column of Table 7.

In order to compare the result of our model with the original MCF problem in which the resource of nodes, the amount of flow on edges and the cost and the capacity of edges are assumed to be deterministic, this example was also solved by considering the following assumptions: deterministic parameters are center (or mode) of uncertain parameters of MCF problem which is given in Table 5 and Table 6:

Table 5: Real costs and capacities of edges

2

2.5

1

2

7

5.5

6.5

3

4

8

5

9

10

14

17

13

10

14

15

15

24

20

19

13

15

20

Table 6: Real resources of nodes

Supplier nodes

Demander nodes

Transit nodes

For the real model, the following LP model is generated in which the variables are real:

The optimal solution in this case is also shown in the second column of Table 7.

Table 7: Numerical results of our example

MCF

Fuzzy random MCF

Er-expected approach

approach

2

(0, 0, 1)

(1, 1, 0)

(1, 1, 0)

17

(15, 13, 18)

(16, 14, 17)

(16, 14, 17)

13

(11, 10, 10)

(10, 9, 16)

(10, 9, 16)

8

(7.5, 6.5, 10)

(3.29, 2.29, 8.67)

(2.35, 1.35, 8.96)

10

(14, 14, 12)

(14, 14, 7)

(14, 14, 7)

5

(3.5, 3.5, 0)

(6.71, 6.71, 7.33)

(7.65, 7.65, 7.04)

15

(12.5, 11.5, 16)

(9.29, 8.29, 13.67)

(8.35, 7.35, 13.96)

2

(18, 18, 18)

(6.60, 6.60, 13)

(6.21, 6.21, 13)

2

(13.3, 13.3, 14.7)

(1.28, 1.28, 15.20)

(1.50, 1.50, 14.70)

5

(8.2, 8.2, 3.3)

(12.03,12.03, 5.13)

(12.35, 12.35, 5.34)

13

(1, 0, 0)

(12.40, 11.40, 0)

(12.79, 11.79, 0)

15

(14.3, 13.3, 14.7)

(13.68, 12.68, 15.20)

(14.29, 13.29, 14.70)

0

(0.7,0.7,1.3)

(1.32, 1.32, 0.80)

(0.71, 0.71, 1.29)

524.5

(575.6, 547.3, 549.8)

(573.4, 632.9, 613.4)

(574.2, 634.4, 614.3)

(618.4,573.3, 679.5)

(604.0, 594.9, 657.7)

We obtain the local optimal solution of the nonlinear programming model of approach. We can use piecewise linear approximation approach (Chien and Kuh, 1977; Williams 1999) to obtain an approximated global optimal solution as a suggestion for future research.

Let and be the Er-optimal and -optimal solutions of the original problem respectively. We can search a confidence level in which . This is a confidence level at the level of Er-expected value programming approach. Anyhow, a decision maker can select an appropriate confidence level based on his/her conditions.

By comparing the results, we can select as a proper confidence level and we use () to evaluate probabilistically the risk that a decision vector is not optimal.

As this result shows, the total flow cost has been increased but the amount of flow on edges of our model is more confident. In the fuzzy random model, the amount of flow on edges and the total flow cost are LR fuzzy variables which is vital for a top decision maker of real network problems and he/she can apply them in order to decide more confidently in compare with the real model which has real variables and has more risk for the decision maker.

6. Concluding remarks

In this paper, we introduced the FRMCF problem. Then, we proposed methods to solve it. These methods are respectively based on Er-expected value of fuzzy random variables and chance-constrained programming. We applied them to the problem in order to handle the uncertainty of FRMCFP. Furthermore, we used the optimization method of fuzzy number variables, fuzzy inequality approaches, and Bellman-Zadeh's max-min operator for multi-objective programming. In the fuzzy random model the amount of flow on edges and total flow cost are both fuzzy variables that are more flexible for a decision maker.

As suggestions for future research, we can use meta- heuristic methods to deal with the uncertainty of FRMCF problem. Furthermore, piecewise linear approximation approach can be used to obtain an approximated global optimal solution of obtained NLP problem.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.