Difference between revisions of "Fuzzy programming"

From optimization
Jump to: navigation, search
(References)
(Examples)
Line 87: Line 87:
  
 
=Examples=
 
=Examples=
 +
This simple example for Water Resources Management [3] shows how triangular fuzzy programs can be applied to real life situations. NO1 and NO2 provide water to other nodes, while A1 and A2 are water consumers. The goal of this problem is to calculate the amount of water
 +
 +
Known:
 +
Water into N1: 66L
 +
Water into N2: 59L
 +
 +
Max Demand:
 +
A1: 49L
 +
A2: 35L
 +
N3 = N1-A1+ 0.3A1 (Water into N3 is water from N1 plus about 30% of water from A1)
 +
 +
Minimum flows:
 +
Into N4: 47L
 +
From N2 to N3: 8L
 +
 +
Revenue from Centers:
 +
A1: $1/L
 +
A2: $1.5/L
 +
 +
<math>
 +
\max x1 + 1.5x2\\
 +
x1 \le 66\\
 +
x2 \le 59\\
 +
x1 \le 49\\
 +
x2 \le 35\\
 +
66+59 - 0.7x1 - x2 \ge 47\\
 +
59-x2 \ge 8\\
 +
x1,x2 \ge 0\\
 +
</math>
 +
 +
[[File:Water.png]]
 +
 +
<math>
 +
p_1 = \begin{pmatrix}
 +
49 \\
 +
52 \\
 +
55
 +
\end{pmatrix}
 +
</math>
 +
 +
<math>
 +
p_2 = \begin{pmatrix}
 +
35 \\
 +
37 \\
 +
39
 +
\end{pmatrix}
 +
</math>
 +
 +
<math>
 +
QN_1 = \begin{pmatrix}
 +
49 \\
 +
52 \\
 +
55
 +
\end{pmatrix}
 +
</math>
 +
 +
<math>
 +
QN_1 = \begin{pmatrix}
 +
49 \\
 +
52 \\
 +
55
 +
\end{pmatrix}
 +
</math>
  
 
=Conclusion=
 
=Conclusion=

Revision as of 20:23, 7 June 2015

Author: Irina Baek
Steward: Dajun Yue and Fenqi You

Contents

Introduction

Fuzzy programming is one of many optimization models that deal with optimization under uncertainty. This model can be applied when situations are not clearly defined and thus have uncertainty, or an exact value is not critical to the problem. For example, categorizing people into young, middle aged and old is not completely clear, so overlap of these categories may exist as can be seen in the image below.

Young, middle-aged, and old are not strictly defined categories, and may result in overlap.

Logical Reasoning

Unlike binary models, where an event is either black or white, fuzzy programming allows for a grey spectrum between the two extremes. As a result, it increases the possible applications since most situations are not bipolar, but consist of a scale of values. A linear function is often used to describe the membership function (u), which describes the 'grey spectrum' where constraint violation is permitted [1]


u(x) = 
\begin{cases}
1  & {ax \le b} \\
1- \frac{ax-b}{ \Delta b} & b < ax \le b+ \Delta b \\
0 &  b + \Delta b < ax
\end{cases}

Continuing with the age analogy - if young ranges from ages 0 to 30, we can define 0 to 18 as being definitely young, so u = 1. However, as we increase the age from there young is not explicitly defined, and can be given lower u values, as these ages are defined as "less young".

Methods

There are several types of fuzzy programming that can deal with different situations. Flexible programming and possibilistic programming will be described here.

Flexible programming

This type of programming can be applied when there is uncertainty in the coefficient values, and a certain amount of deviation is acceptable. Starting from a typical LP model defined as:


\begin{align}
\max c^t x \\
s.t. \; & Ax \le b \\
& x \ge 0 
\end{align}

We use ~ to identify the fuzzy (or flexible) parameters. By making the inequalities fuzzy, the user of the program can set an approximate goal to minimize/maximize an objective function rather than a completely realistic value. Furthermore, this fuzzy relation can be interpreted as "essentially smaller than or equal" instead of "smaller than or equal"


\begin{align}
\tilde{max} c^t x \\
s.t. \; & Ax \tilde{\le} b \\
& x \ge 0 
\end{align}

If the user has a certain objective value they would like to reach, this can be combined and further simplified to:


\begin{align}
Find \; x \\
s.t. \; & c^t x \tilde{\ge} z \\
& Ax \tilde{\le} b\\
& x \tilde{\ge} 0
\end{align}

The two constraints can be combined and the problem is further simplified to:


\begin{align}
Find \; x \\
s.t. \; & \hat{A}x \; \tilde{\le} \hat{b} \\
\end{align}

u_o is the membership function for the initial objective while u_i is the membership function for the constraints. These membership functions describe how closely the fuzzy inequalities are satisfied, we can describe the optimal decision to be:


\max \min {u_i(x)} = \max u_o(x)

An optimal solution to this problem can be found by solving


max \; min \;  1- \frac{\hat{A}_i x - b_i}{\Delta b_i}

A new variable λ is used to construct an LP that can be solved easily

 \max  \lambda \;\;\;\; s.t.  \bar{A} x + \lambda \le \bar{b}, x \ge 0, 0 \le \lambda \le 1

where  \bar{A} \; \text{and} \; \bar{b} \; \text{are} \; \bar{a}_{ij} = \hat{a}_{ij}/ \Delta b_i  \; \text{and} \; \bar{b}_i = 1 + (\hat(b_i) / \Delta b_i)

Possibilistic programming

In possibilistic programming

Applications

Examples

This simple example for Water Resources Management [3] shows how triangular fuzzy programs can be applied to real life situations. NO1 and NO2 provide water to other nodes, while A1 and A2 are water consumers. The goal of this problem is to calculate the amount of water

Known: Water into N1: 66L Water into N2: 59L

Max Demand: A1: 49L A2: 35L N3 = N1-A1+ 0.3A1 (Water into N3 is water from N1 plus about 30% of water from A1)

Minimum flows: Into N4: 47L From N2 to N3: 8L

Revenue from Centers: A1: $1/L A2: $1.5/L

Failed to parse(syntax error): \max x1 + 1.5x2\\ x1 \le 66\\ x2 \le 59\\ x1 \le 49\\ x2 \le 35\\ 66+59 - 0.7x1 - x2 \ge 47\\ 59-x2 \ge 8\\ x1,x2 \ge 0\\


Water.png


p_1 = \begin{pmatrix}
49 \\
52 \\
55 
\end{pmatrix}


p_2 = \begin{pmatrix}
35 \\
37 \\
39 
\end{pmatrix}


QN_1 = \begin{pmatrix}
49 \\
52 \\
55 
\end{pmatrix}


QN_1 = \begin{pmatrix}
49 \\
52 \\
55 
\end{pmatrix}

Conclusion

References

[1] http://www.researchgate.net/profile/Nikolaos_Sahinidis/publication/222687527_Optimization_under_uncertainty_state-of-the-art_and_opportunities/links/5463babb0cf2c0c6aec4f7a8.pdf [2] http://www.worldacademicunion.com/journal/jus/jusVol01No2paper03.pdf [3] http://www.ewra.net/ew/pdf/EW_2004_7-8_03.pdf