On Some Fuzzy Optimization Problems

Presentation on theme: "On Some Fuzzy Optimization Problems"— Presentation transcript:

1 On Some Fuzzy Optimization Problems
主講人：胡承方博士 義守大學工業工程與管理學系 April 16, 2010

2 模糊理論 Zadeh (1965) 首創模糊集合 (Fuzzy Set) 何謂「Fuzzy」 今天天氣「有點熱」 顧客的滿意度「頗高」
從清華大學到竹科的距離「很近」 義守大學是一所「不錯」的大學

3 模糊與機率不同處之比較 模 糊 機 率 元素歸屬程度 集合的發生率 不涉及統計 使用統計 訊息愈多 模糊仍存在 不確定性遞減 處理真的程度
模　糊 機　率 元素歸屬程度 集合的發生率 不涉及統計 使用統計 訊息愈多 模糊仍存在 不確定性遞減 處理真的程度 是可能性 或預期的情形 模糊 機率 模糊且隨機

4 模糊理論 將人類認知過程中(主要為思考與推理)之不確定性，以數學模式表之。
把傳統的數學從只有『對』與『錯』的二值邏輯(Binary logic)擴展到含有灰色地帶的連續多值(Continuous multi-value)邏輯。

5 模糊理論 利用『隸屬函數』(Membership Function)值來描述一個概念的特質，亦即使用0與1之間的數值來表示一個元素屬於某一概念的程度，這個值稱為該元素對集合的隸屬度(Membership grade)。 當隸屬度為1或0時便如同傳統的數學中的『對』與『錯』，當介於兩者之間便屬於對與錯之間的灰色地帶。

6 傳統集合(Crisp Sets) 傳統集合是以二值邏輯(Binary Logic)為基礎的方式來描述事物，元素x和集合A的關係只能是A或A，是一種『非此即彼』的概念。以特徵函數表示為：

7 模糊集合(Fuzzy Sets) 而模糊集合則是指在界限或邊界不分明且具有特定事物的集合，以建立隸屬函數(Membership Function)來表示模糊集合，也就是一種『亦此亦彼』的概念。

8 隸屬函數(Membership Functions)
假設宇集(universe)U={x1, x2,…, xn}， 是定義在U之下的模糊集合， 為模糊集合之隸屬函數(Membership Function)。 表示模糊集合 中xi的隸屬程度(Degree of Membership)。

9 Example Ex: The weather is “good” A(x) A fuzzy set A(x) A crisp set

10 Example ……………...

11 Characteristic function
傳統與模糊集合不同處之比較 傳統集合 模糊集合 Characteristic function 特徵函數 A(x) X{0,1} Membership function 隸屬函數 X[0,1]

12 模糊集合表示法 宇集U為有限集合 宇集U無限集合或有限連續 一般的表示方法

13 Example Ex: A: The weather is “hot”

14 模糊集合之運算 聯集（Union） 交集（Intersection） 補集（Complement）

15

16 Example Ex: two fuzzy set and find 1 x

17 Example (15)= (15)  (15) =min( (15), (15)) =min(1,0)=0
(15)= (15)  (15) =min( (15), (15)) =min(1,0)=0 (20)= (20)  (20) =min( (20), (20)) =min(0.7,0.2)=0.2

18 a-截集(a -cut或a -level) 模糊集合 的a-截集定義為: 而模糊集合 取a -截集所形成的區間範圍為

19

20 Fuzzy numbers Two classes One class has 30 students

21 模糊數(Fuzzy Numbers) If is a normal fuzzy set on R and is a closed interval for each then is a fuzzy number. (Note that: is a normal, if

22 模糊數的種類 三角形模糊數(Triangular Fuzzy Number) 梯形模糊數(Trapezoidal Fuzzy Number)
鐘形模糊數(Bell Shaped Fuzzy Number) 不規則模糊數(Non-Symmetric Fuzzy Number)

23 三角形模糊數

24 梯形模糊數

25 鐘形模糊數

26 不規則模糊數

27 模糊運算(Fuzzy Arithmetic)
模糊數加法 模糊數乘法 模糊數除法 模糊數倒數 模糊數開根號運算

28 模糊數加法 三角形模糊數 ：模糊數加法運算子 梯形模糊數

29 模糊數乘法 三角形模糊數(k>0)  ：模糊數乘法運算子 梯形模糊數

30 模糊數乘法 三角形模糊數(a1>0,a2>0)  ：模糊數乘法運算子 梯形模糊數

31 模糊數除法 三角形模糊數  ：模糊數除法運算子 梯形模糊數

32 Fuzzy Ranking

33 Why ranking fuzzy numbers ?
Two classrooms to be preassigned to two classes One large room One small room One class has 30 students One class has 25 students

34 Fuzzy Ranking Solving is to find optimal solutions to the system of fuzzy linear inequalities problem

35 Example

36 How to rank fuzzy numbers?
The study of fuzzy ranking began in 1970's Over 20 ranking methods were proposed No \best" method agreed

37

38

39

40

41

42

43

44

45

46 How to Select Fuzzy Ranking
Easy to compute Consistency Ability to discriminate Go with intuition Fits your model Consider combination of different rankings

47 Optimization Optimization models can be very useful.

48 Optimization models for Decision making

49 Past Industrial Experience
Optimization models can be very useful. Problems are harden to define than to solve. Most decision are made under uncertainty.

50 Fuzzy Optimization

51 Fuzzy Optimization and Decision making
fuzzy vector

52 Solution Methods -level approach Parametric approach
Semi-infinite programming approach Set-inclusion approach Possibilistic programming approach ……

53 Recent Development System of Fuzzy Inequalities
Fuzzy Variational Inequalities

54 Motivation LP K-K-T Optimality Conditions

55 Motivation NLP where is a convex set and is a
smooth real-valued function defined on .

56 Variational Inequalities
Find such that for each where means the inner product operation.

57 System of Fuzzy Inequalities
“ ” means “approximately less than or equal to”. Examples：

58 Fuzzy Inequalities – System I
“ ” means “approximately less than or equal to”.

59

60 Fuzzy Decision Making (Bellman/Zadeh,1970) Decision Making Model
Solving(*) is to find optimal solutions to

61 Equivalently, When is invertible

62 If , are convex and are concave, then a solution to (
If , are convex and are concave, then a solution to (*) can be obtained by solving a convex programming problem

63 Huard’s “Method of Centers” + Entropic Regularization Method reduce the problem to solving a sequence of unconstrained smooth convex programs with a sufficiently large p. ( Hu, C.-F. and Fang, S.-C., “Solving Fuzzy Inequalities with Concave Membership Functions”, Fuzzy Sets and Systems, vol. 99 (2),pp ,1998 )

64 Semi-infinite programming extension for
(Hu, C.-F. and Fang, S.-C., “A Relaxed Cutting Plane Algorithm for Solving Fuzzy Inequality Systems ”, Optimization, vol. 45, pp , 1999)

65 Extension to solving fuzzy inequalities with piecewise linear membership functions

66 (Hu, C.-F. and Fang, S.-C., “Solving Fuzzy Inequalities with Piecewise Linear Membership Functions”, IEEE Transactions on Fuzzy Systems, vol. 7 (2),pp ,April, 1999. Hu, C.-F. and Fang, S.-C., “Solving a System of Infinitely Many Fuzzy Inequalities with Piecewise Linear Membership Functions”, Computers and Mathematics with Applications, vol.40,pp , 2000.)

67 Fuzzy Inequalities – Systems II
Find such that

68 Fundamental Problem No universally accepted theory for ranking two fuzzy sets.

69 Simple Case Solving is to find optimal solutions to the semi-infinite programming problem

70 (Fang, S. -C. , Hu, C. -F. , Wang H. -F. and Wu, S. -Y
(Fang, S.-C., Hu, C.-F., Wang H.-F. and Wu, S.-Y., “Linear Programming with Fuzzy Coefficients in Constraints”, Computers and Mathematics with Applications, vol. 37 (10),pp , 1999.)

71 Fuzzy Variational Inequalities
An Optimization problem can be cast into a variational inequality problem Find such that where V is a nonempty, closed, convex subset of and is a point-to-point mapping.

72 Problem such that As difficult as an optimization problem with parameterized equilibrium constraints.

73 Fuzzy VI Problem

74 Maximizing Solution to

75 Optimization with parameterized equilibrium constraints
Bi-level programming — Gap function — Penalty method Maximum feasible problem — Bisection with auxiliary program — Analytic center cutting plane

76 Hu, C.-F., 2000, “Solving Variational Inequalities in a Fuzzy Environment”, Journal of Mathematical Analysis and Applications, Vol. 249, No. 2, pp Hu, C.-F., 2001, “Solving Fuzzy Variational Inequalities over a Compact Set”, Journal of Computational and Applied Mathematics,Vol. 129, pp

77 Fang, S.-C. and Hu, C.-F.,“Solving Fuzzy Variational Inequalities”, Journal of Fuzzy Optimization and Decision Making, vol. 1, No. 1,pp , 2002. Hu, C.-F., “Generalized Variational Inequalities with Fuzzy Relations”, Journal of Computational and Applied Mathematics, vol. 146, No. 1,pp , 2002.

78 Many Thanks