Unscharfe Optimierung
Wintersemester 2005/2006
Vorlesung
Dienstags, 09.15–11.00, MIB-1107
Übung
Dienstags (gerade Woche), 11.00–13.00,
MIB-1107
VeranstalterDr. Tatiana Starostina
E-mail: [email protected] Tel. 3786
Sprechstunde nach Vereinbarung
Unscharfe Optimierung
Unscharfe Optimierung
1). M. Delgado, J. Kacprzyk, J.-S. Verdegay, M.A. Vila (ed.) Fuzzy Optimization: Recent Advances Physica-Verlag, Heidelberg, 1994.
2). H. Bandemer and S. Gottwald Fuzzy Sets, Fuzzy Logic, Fuzzy Methods with ApplicationsJohn Wiley & Sons, Chichester 1995.
3). H.-J. ZimmermannFuzzy Set Theory and its Applications2nd ed., Kluwer Academic Publishers, Dordrecht, 1991.
4). C.R. Bector, Suresh Chandra Fuzzy Mathematical Programming and Fuzzy Matrix GamesSpringer-Verlag, Berlin Heidelberg, 2005.
Literatur
Unscharfe Optimierung
Überblick
Optimierung
1) im Sinne der Mathematik:die Bestimmung optimaler zulässiger Punkte eines Optimierungsproblems hinsichtlich einer gegebenen Zielfunktion
2) in der Informatik: die Verbesserung der Effizienz eines Computerprogramms
3) Umgangssprachlich:meist eine Verbesserung eines Vorgangs oder Zustands bzgl. Qualität,Kosten, Geschwindigkeit, Effizienz und Effektivität.
Unscharfe Optimierung
ÜberblickMathematische
Optimierung
Minimieren oder maximieren f(x),
Xx ,
wobei f(x) – Zielfunktion des Optimierungsproblems; x – zulässige Lösung;
X – zulässiger Bereich.
Lineare Optimierung
Nichtlineare Optimierung
Konvexe Optimierung
Dynamische Optimierung
Diskrete Optimierung
ParametrischeOptimierung
Nichtkonvexe Optimierung
Unscharfe Optimierung
Problembereich „Unschärfe“ bei Optimierungsmodellen
Optimierungsmodell
Algorithmus
Problembereich „Unschärfe“
Modell- beschreibung
Daten
Unscharfe Optimierung
Die Bedeutung der unscharfen Daten und Modelle
Unscharfe Daten:
„X gehört zu den großen Menschen“: Jemand, der 1,60 m groß ist, wird mit einer Zugehörigkeit von 0,2 zu den großen Menschen gerechnet.
Dagegen wird jemand, der 1,85 m groß ist, mit einer Zugehörigkeit von 0,8 zu den großen Menschen gerechnet.
Die Aussage „Y ist dick“hängt von den Attributen Körpergröße, Körperumfang und Gewicht ab.
Unscharfe Optimierung
Die Bedeutung der unscharfen Daten und Modelle
Unscharfe Daten:
Die Auffassung über die Daten beeinflusst auch die Werte von Daten.
Beispiel:Die Frage ist „Wann schließen die Geschäfte?“
Die Antwort „Um 18 Uhr“.
Das kann bedeuten: 1) alle Geschäfte sind um 18 Uhr zu;2) einige Geschäfte schließen bereits um 17 Uhr, andere dagegen erst um 20 oder 21 Uhr.
Eine entsprechende Zugehörigkeitsverteilung zur Aussage „Die Geschäfte sind geschlossen“ lässt sich dann über die Zeit aufstellen.
Unscharfe Optimierung
Die Bedeutung der unscharfen Daten und Modelle
18 x
1
)(x
1
17 18 21 x
)(x
Scharfe Zahl:
x =18Unscharfe Zahl:
x = „etwa 18“
Unscharfe Optimierung
Die Bedeutung der unscharfen Daten und Modelle
Unscharfe Daten:
Scharfe und unscharfe Regionen
(a)scharfe Darstellung;
(b) unscharfe
Darstellung
See
.9
1
1111
1
1
1
1
1 1
1 1
111 1
1
1 1 1
1 1
1111
1
1
1
1
.7
111
1 1
.9
.8
.8
.9
.8
.4
.4
.4
.5
.5
.5
.7
.4
.6
.1
.1
.2
.1
.1
.1
.2
.1
0 0
0 0 0 0
000
0 0 00000
0
0 0 0 0
0
0
0
0
0
00
0
0
0
0
00
0
0
0
0
001
11 11
1
1
11
11
1 1 1
1
111
1
1111
1
111
11
.9
.8
.8
.9.4
.5
.5
.3
.6
.2
.1
.1
.2
.10 .50 0 0
1 1 1 1 1 1
1
11
11
0
0
0
0
0
0
0
0
0
0
0
0
0
0
00
0
0
0
0
0
0
0
0
0
0
0 0
00
0 0 .9
.6
.9
.3
.6.2 .9
.9.6
Wald
(a)
(b)
Unscharfe Region: See Unscharfe Region: Wald
Unscharfe Optimierung
Die Bedeutung der unscharfen Daten und Modelle
Unscharfe Modelle:
Beispiele:
1v
2v
3v 4v
5v
0,9
0,5
0,3
0,7
0,1
1
0,4
0,2
Unscharfer Graph Unscharfe Relation
x2
x1
x3
y1
y2
y3
y4
z1
z2
z3
1/5
1/9
1/8
1
1/2
1/6
1/3
1/7
1
1/51
1/4
1/9
1/6
2/3
1/3
2/3
Unscharfe Optimierung
Arten der Unschärfe
„Unschärfe“:
• nichtexakte Bedeutung des Wortes oder • mangelnde Information und die fehlende Möglichkeit, einen Begriff
exakt beschreiben zu können
Unsicherheit
zufällige Unsicherheit
emotionale Unsicherheit
informelle Unsicherheit
Abb. Arten der Unsicherheit
Wahrscheinlichkeiten für das menschliche Komplexität in der Eintreten von Ereignissen Empfindungen Beschreibung des
Begriffs
Unscharfe Optimierung
Quellen der Unschärfe
nicht genug Informationen liegen in der augenblicklichen
Situation vor
Unschärfe
das Erfassen und Abbildendes Systems ist subjektiv verschieden
Klassische Mengen Unscharfe Optimierung
Es sei X die Grundmenge und A eine Teilmenge von X: XA .
Ein Element gehört in der klassischen Mengenlehre entweder zu einer Menge A, oder aber es gehört nicht zu dieser Menge.
Wenn ein Element x von X zu A gehört, schreibt man: Ax .
Definition. Es sei X eine Grundmenge und A eine Teilmenge von X. Dann heißt die Funktion χA: X →{0,1} mit
Ax
AxA ,0
,1
Indikatorfunktion oder charakteristische Funktion der Menge A.
Unscharfe Optimierung
A~
ist eine unscharfe Teilmenge von X, wenn die Zugehörigkeit der Elemente x von
X zu A~
durch eine Zugehörigkeitsfunktion )(~ xA charakterisiert wird.
Die Werte der Zugehörigkeitsfunktion liegen im Intervall [0,1].
Beispiel: )(~ x
A =0 wenn Ax
~ , )(~ x
A =1 wenn Ax
~ vollständig,
)(~ xA =0,8 wenn Ax
~ mit einem der Zahl 0,8
entsprechenden Zugehörigkeitsgrad.
Definition. Ist X eine Menge (von Objekten, die hinsichtlich einer unscharfen Aussage zu bewerten sind), so heißt
XxxxAA
:)(,:~
~ .
eine unscharfe Menge auf X.
)(~ xA wird Zugehörigkeitsfunktion genannt und ist eine reellwertige Funktion,
]1;0[)(~ xA , Xx .
Unscharfe Menge zur Modellierung der Unschärfe
Unscharfe Menge zur Modellierung der Unschärfe
Unscharfe Optimierung
Beispiel: (Modellierung unscharfer Begriffe)
Unscharfe Begriffe in der Umgangssprache:
”groß“, ”klein“, ”schnell“, ”reich“, ”schön“, ”warm“, ”kalt“, ”heiß“ usw.
Kontext beachten!
Beispiel:
Betrachten den unscharfen Begriff ”klein“ mit Bezug auf Kosten. Grundmenge: X = {10, 20, 50, 100, 150, 200, 400, 700, 1000}.
„Kleine“ Kosten: {(10; 1), (20; 0,97), (50; 0,85), (100; 0,75), (150; 0,7), (200; 0,6), (400; 0,5), (700; 0,25), (1000; 0,1)}.
Unscharfe Menge zur Modellierung der Unschärfe
Unscharfe Optimierung
Beispiel:Abb. A): Menge A - die Menge der günstigen Preise für ein Paar Schuhe. Dann stellt 49,98 EURO noch einen günstigen Preis dar, dagegen würde ein um 3 Cent höherer Preis von 50,01 EURO nicht mehr als günstig angesehen werden.
Abb. B): Darstellung der unscharfen Menge der günstigen Preise für ein Paar Schuhe. Die Gleichung (x) = 0,7 besagt, dass der Wert x=23 mit dem Zugehörigkeitsgrad
=0,7 als günstiger Preis angesehen wird.
25 50 x
1
)(x A 1
A~
)(x
25 50 x Abb. A) Abb. B)
Unscharfe Mengen Unscharfe Optimierung
Unscharfe Mengen werden durch Zugehörigkeitsfunktionen (ZGF) repräsentiert.Die Art der Darstellung ist von Grundmenge X abhängig
X hat endlich viele Elemente Besitzt X sehr viele Elemente oder ist X ein Kontinuum, z.B. kontinuierliche Messgrößen
diskrete Darstellung von ZGF parametrische Darstellung von ZGF
1 3 4 7 9 12 x
1 0,9
0,7 0,6 0,4 0,3
)(x
Unscharfe Mengen Unscharfe Optimierung
Operationen A~ und B
~ seien zwei unscharfe Teilmengen der Grundmenge X: A~ X , B
~ X. Grundmenge X : 1)( xX Enthaltensein A
~ X: )()(~ xx XA
Komplement: )(1)( ~~ xxAA
Schnittmenge: ))(),((min)( ~~~~ xxxBABA
Vereinigung: ))(),((max)( ~~~~ xxxBABA
Algebraisches Produkt: )()()( ~~~~ xxxBABA
Algebraische Summe: )()()()()( ~~~~~ˆ~ xxxxxBABABA
Differenz: )()( ~~~\
~ xxBABA
Disjunkte Summe: )()()
~~()
~~(
~~ xxBABABA
Xx .
Unscharfe Optimierung
Unscharfe Modelle
UnscharfeRelationen
UnscharfeGraphen
Klassifizierung der unscharfen Optimierungsprobleme
Unscharfe Optimierungsprobleme
Modelle mit unscharfen Daten
Unscharfe Optimierung
Optimierungsmodelle mit unscharfen Daten
Optimierungsmodelle
UnscharfeLineare
Optimierungs-modelle
UnscharfeNichtlineare
Optimierungs-modelle
UnscharfeDynamische
Optimierungs-modelle
UnscharfeDiskrete
Optimierungs-modelle
UnscharfeParametrischeOptimierungs-
modelle
Unscharfe Entscheidungen
Entscheidungen mit mehreren Zielen
Entscheidungen mit mehreren Attributen
Unscharfe Optimierung
Unscharfe GraphenEs gibt zwei Typen von unscharfen Graphen.
Definition 1
Ein unscharfer ungerichteter Graph des ersten Typs )~
,(~
EVG besteht aus zwei Mengen:
V ist eine nichtleere scharfe Menge von Knoten, }{ ivV , iI = {1,2,...,n};
},:)),/(),({(~
VvvvvvvE jkjkjkE ist eine unscharfe Menge von Kanten,
wobei Vvv jk , und ),( jkE vv - der Wert der Zugehörigkeitsfunktion E
für die Kante ),( jk vv , njk ,...,1, .
1v
2v
3v 4v
5v
0,9
0,5
0,3
0,7
0,1
1
0,4
0,2
Beispiel 1)
~,(
~EVG ,
},,,,{ 54321 vvvvvV ,
))}.,/(2,0()),,/(4,0(
)),,/(1()),,/(1,0(
)),,/(3,0()),,/(7,0(
)),,/(5,0()),,/(9,0{(~
5554
4152
4233
3221
vvvv
vvvv
vvvv
vvvvE
Unscharfe Optimierung
Unscharfe Graphen des ersten Typs
Definition 2
Beispiel 2
Ein unscharfer gerichteter Graph des ersten Typs EVG~
,~ besteht aus zwei
Mengen: V ist eine scharfe Menge von Knoten, }{ ivV , iI = {1,2,...,n};
},:),/),({(~
VvvvvvvE jkjkjkE ist eine unscharfe Menge von Kanten
oder Pfeilen, wobei VVvv jk , und ),( jkE vv ist der Wert der
Zugehörigkeit der gerichteten Kante jk vv , zur unscharfen Menge der
gerichteten Kanten (Pfeilen) E~
.
1v
2v
3v 4v
5v
0,4
0,8
0,7
0,6
0,1 0,9
0,5
1
EVG~
,~ ,
},,,,{ 54321 vvvvvV ,
)}.,/9,0(),,/1,0(
),,/6,0(),,/1(
),,/5,0(),,/7,0(
),,/8,0(),,/4,0{(~
1555
5434
3152
4321
vvvv
vvvv
vvvv
vvvvE
Unscharfe Optimierung
Die Mengen der Nachbarn, Vorgänger undNachfolger in unscharfen Graphen
Gibt es in einem ungerichteten unscharfen Graphen )~
,(~
EVG eine Kante ( jk vv , ), so heißen kv Nachbar von jv und jv Nachbar von kv .
)(~
kvN - die Menge der Nachbarn eines Knotens kv .
Gibt es in einem gerichteten unscharfen Graphen EVG~
,~ einen Pfeil
jk vv , , dann heißen kv Vorgänger von jv und jv Nachfolger von kv .
)(~
kvP - die Menge der Vorgänger eines Knotens kv ;
)(~
kvS - die Menge der Nachfolger von kv .
Die Mengen )(~
kvN , )(~
kvP und )(~
kvS sind unscharf.
Unscharfe Optimierung
Die Mengen der Nachfolger in unscharfen Graphen
Beispiel
Wir definieren den gerichteten unscharfen Graph EVG~
,~ aus dem
Beispiel 2 in folgender Form: )~
,(~
SVG :
},,,,{ 54321 vvvvvV ,
)}/5,0(),/4,0{()(~
321 vvvS ;
)}/7,0{()(~
52 vvS ;
)}/8,0{()(~
43 vvS ;
)}/6,0(),/1{()(~
534 vvvS ;
)}/1,0(),/9,0{()(~
515 vvvS .
1v
2v
3v 4v
5v
0,4
0,8
0,7
0,6
0,1 0,9
0,5
1
Unscharfe Optimierung
Beispiel 3
Sei },...,{ 1 nvvV die Knotenmenge des unscharfen Graphen (Digraphen).
Dann heißt die dem unscharfen Graphen des ersten Typs )~
,(~
EVG zugeordnete
n×n Matrix nnkjV uGU
)~
( mit den Elementen ),( jkEkj vvu , njk ,...,1,
Adjazenzmatrix von G~
.
Für einen unscharfen gerichteten Graph EVG~
,~ wird eine Adjazenzmatrix
nnkjV uGU
~
mit jkEkj vvu , , njk ,...,1, gebildet.
Matrixform der unscharfen Graphen
1v 2v 3v 4v 5v
1v 2v 3v 4v 5v
1v 0 0,9 0 1 0 1v 0 0,4 0,5 0 0
2v 0,9 0 0,5 0,3 0,1 2v 0 0 0 0 0,7
3v 0 0,5 0,7 0 0 3v 0 0 0 0,8 0
4v 1 0,3 0 0 0,4 4v 0 0 1 0 0,6
)~
(GUV
5v 0 0,1 0 0,4 0,2
GUV
~
5v 0,9 0 0 0 0,1
Ein unscharfer ungerichteter Graph hat immer eine symmetrische
Adjazenzmatrix. D.h. njk ,...,1, gilt: ),( jkE vv = ),( kjE vv .
Unscharfe Optimierung
Definition 3
A ist eine Grundmenge. Gegeben ist eine unscharfe Menge V~
in A, wobei )}/)({(
~vvV A , Av .
Ein Graph )~
,~
(~
EVG ist ein unscharfer ungerichteter Graph des zweiten Typs, wenn
V~
eine unscharfe Menge von Knoten ist: )}/)({(~
vvV A , Av , nV ~ und
)},/(),({(~
jkjkE vvvvE ist eine unscharfe Menge von Kanten, wobei
Vvv jk , , njk ,...,1, . Hier V heißt Träger der Menge V~
.
V~
ist die Mächtigkeit oder Kardinalität.
Als Träger V bezeichnet man den Bereich der Grundmenge A, dem eine Zugehörigkeit μV>0 zugeordnet ist.
Unscharfe Graphen des zweiten Typs
Unscharfe Optimierung
Unscharfe Graphen des zweiten Typs
Definition 4
A ist eine Grundmenge. Gegeben ist eine unscharfe Menge V~
in A, wobei )}/)({(
~vvV A , Av .
Ein Graph EVG~
,~~
ist ein unscharfer gerichteter Graph des zweiten Typs,
wenn
V~
eine unscharfe Menge von Knoten ist: )}/)({(~
vvV A , Av , nV ~
und },/,{(~
jkjkE vvvvE ist eine unscharfe Menge von gerichteten
Kanten (Pfeilen), wobei Vvv jk , , njk ,...,1, und V ist der Träger der
Menge V~
.
Unscharfe Optimierung
Unscharfe Graphen des zweiten TypsBeispiel 4
)~
,~
(~
EVG , )}/8,0(),/4,0(),/2,0(),/7,0(),/1{(~
54321 vvvvvV ,
))}.,/(5,0()),,/(4,0(
)),,/(1,0()),,/(9,0()),,/(3,0()),,/(7,0()),,/(8,0()),,/(6,0{(~
2544
534342325131
vvvv
vvvvvvvvvvvvE
Beispiel 5
EVG~
,~~
, )}/7,0(),/5,0(),/9,0(),/6,0(),/2,0{(~
54321 vvvvvV ,
)}.,/1(),,/2,0(),,/4,0(
),,/8,0(),,/5,0(),,/9,0(),,/3,0(),,/6,0{(~
155553
4333523221
vvvvvv
vvvvvvvvvvE
1v
2v
3v
4v
5v
0,7
0,3
0,9
0,6
0,8
0,1
1v
2v
3v 4v
5v
0,6
0,3 0,4
0,5
0,9
1
0,8
0,2
0,5
0,4
0,7
1
0,2
0,4
0,8 0,6
0,7
0,2
0,5 0,9
Unscharfe Optimierung
Transformation der unscharfen GraphenUnscharfer
gerichteter Graph des zweiten Typs
EVG~
,~~
'~
,'~
EVG
Unscharfer gerichteter Graph des ersten Typs
gekoppelte Graphen
In diesem Fall ist V der Träger der Menge V~
und die unscharfe Menge von gerichteten Pfeilen '
~E ist die folgende:
},:),/),({('~
' VvvvvvvE jkjkjkE , wobei VVvv jk , und die Funktion
)(&)(&),(),(' jVkVjkEjkE vvvvvv .
Mit minimax Operation: ))(),(),,((min),(' jVkVjkEjkE vvvvvv .
Mit Wahrscheinlichkeitsrechnung:
)()(),(),(' jVkVjkEjkE vvvvvv .
Unscharfe Optimierung
Eingangs- und Ausgangsgrad eines Knotens in unscharfen Graphen
Die Anzahl der Nachbarn eines Knotens iv eines Graphen heißt Grad )( iv von iv . Die Anzahl der Nachfolger eines Knotens iv eines gerichteten
Graphen heißt positiver Grad oder Ausgangsgrad )( iv von iv . Die Anzahl der Vorgänger eines Knotens iv heißt negativer Grad
oder Eingangsgrad )( iv :
)()( ii vNv ; )()( ii vSv ; )()( ii vPv .
Hier, )( ivN ist der Träger der unscharfen Menge )(~
ivN der Nachbarn des Knotens iv .
)( ivS und )( ivP sind entsprechend die Träger der unscharfen
Menge )(~
ivS der Nachfolger und der Menge )(~
kvP der Vorgänger des Knotens iv .
Unscharfe Optimierung
Numerische Charakteristiken der Knoten der unscharfen Graphen
Konjunktiver Eingangsgrad des Knotens iv :
),(&)()(
& ijEvPv
i vvvij
Konjunktiver Ausgangsgrad des Knotens iv :
),(&)()(
& jiEvSv
i vvvij
Disjunktiver Eingangsgrad des Knotens iv :
),()()(
ijEvPv
i vvvij
Disjunktiver Ausgangsgrad des Knotens iv :
),()()(
jiEvSv
i vvvij
Mittelwert des Eingangsgrads
des Knotens iv :
)(
),()(
1)(
ij vPvijE
iiav vv
vPv
Mittelwert des Ausgangsgrads
des Knotens iv :
)(
),()(
1)(
ij vSvjiE
iiav vv
vSv
Unscharfe Optimierung
Unscharfe Teilgraphen
Definition 6
Ein unscharfer Graph )'~
,'(~
EVH heißt Teilgraph des Graphen
)~
,(~
EVG , wenn VV ' und EE~
'~ , wobei
}',:)),/(),({('~
' VvvvvvvE slslslE und ),(),(' slEslE vvvv
', Vvv sl . Definition 7 Ist VV ' , so hat der durch 'V induzierte Teilgraph
)'~
,'(~
EVH von )~
,(~
EVG die Knotenmenge 'V und enthält
genau alle Kanten ),( sl vv von G~
mit ', Vvv sl , wobei
}',:)),/(),({('~
' VvvvvvvE slslslE und ),(),(' slEslE vvvv ,
', Vvv sl .
Unscharfe Optimierung
Unscharfe Teilgraphen
1
~H und 2
~H sind induzierte unscharfe
Teilgraphen von )~
,(~
EVG
1v 3v 4v 5v
0,8
0,6
0,1
0,9
0,3
2
~H 1
~H
1v 2v 3v 4v 5v 0,4
0,8 0,7
0,6
0,1
0,9
0,5
0,3
)~
,(~
EVG
Beispiel 6
Unscharfe Optimierung
Unscharfe Teilgraphen
3
~H ist ein unscharfer Teilgraph von )
~,(
~EVG
1v 2v 3v 4v 5v
0,2 0,6
0,3
0,8
0,5
0,3
1v 2v 3v 4v 5v 0,4
0,8 0,7
0,6
0,1
0,9
0,5
0,3
)~
,(~
EVG
3
~H
Beispiel 7
Unscharfe Optimierung
Unscharfes Enthaltsein und unscharfe Gleichheit von unscharfen Graphen
Der Grad des Enthaltenseins des Graphen 1
~G im Graphen 2
~G wird
wie folgt definiert:
))()((&&)~
,~
( 2121211
yyGG vvVVyVv
.
Ein Wert
))()((&&)~
,~
( 1212212
yyGG vvVVyVv
.
heißt der Grad des Enthaltenseins des Graphen 2
~G im Graphen 1
~G .
Ein Wert
)~
,~
(&)~
,~
()~
,~
( 122121 GGGGGG .
heißt der Grad der unscharfen Gleichheit von unscharfen Graphen
1
~G und 2
~G .
Unscharfe Optimierung
Unscharfes Enthaltsein und unscharfe Gleichheit von unscharfen Graphen
Beispiel 8
1v
2v
3v 0,6
0,7
1v 2v
3v
0,2
0,5
0,8
0,3
1
~G 2
~G
7,0)~
,~
( 21 GG
21
~~~GG
8,0)
~,
~( 12 GG
12
~~~GG
7,0)~
,~
( 21 GG
21
~~~GG
Unscharfe Optimierung
Operationen von unscharfen Graphen
Es seien 111
~,
~SVG und 222
~,
~SVG unscharfe gerichtete Graphen.
Definition 8 Ein unscharfer Graph
SVVGG~
,~~
2121
wird die Vereinigung von 111
~,
~SVG und 222
~,
~SVG genannt, wobei
))(~
)(~
)(~
()( 2121 vSvSvSistVVv . Definition 9 Ein unscharfer Graph
SVVGG~
,~~
2121
wird der Durchschnitt von 111
~,
~SVG und 222
~,
~SVG genannt, wobei
))(~
)(~
)(~
()( 2121 vSvSvSistVVv .
Unscharfe Optimierung
Operationen von unscharfen Graphen
Definition 10 Ein unscharfer Graph
111
~~SVG
wird das Komplement von 111
~,
~SVG genannt, wobei
11
~\)(
~SVvS .
Definition 11 Ein unscharfer Graph
\2121
~,\
~\
~SVVGG
wird Differenz von 111
~,
~SVG und 222
~,
~SVG genannt, wobei
))(~
)(~
)(~
()\( 21\21 vSvSvSistVVv .
Unscharfe Optimierung
Operationen von unscharfen Graphen
Definition 12 Ein unscharfer Graph
SVVGG~
,:~~
2121
wird disjunkte Summe von 111
~,
~SVG und 222
~,
~SVG genannt,
wobei
))(~
)(~
())(~
)(~
()(~
)( 212121 vSvSvSvSvSistVVv .
Unscharfe Optimierung
Operationen von unscharfen Graphen
1v
2v
3v
0,3 0,4
4v
5v 3v
0,2
0,6
0,8
1 1
~G
4v
0,7
0,2 0,5 0,8
0,6
0,8
0,3
0,9
2
~G
1v
2v
3v
0,3
0,4
5v
1
21
~~GG
4v
0,7
0,2 0,8 0,8
0,6
0,9
0,3
0,6
0,8
21
~~GG
0,2
4v
3v
0,5
1
~G
1v
2v
3v
0,7
1
1
4v
0,3
0,8 0,5 0,2
0,4 1
1
1
1
0,6
1 1
1v
2v
0,3
21
~\
~GG
0,8
0,6
21
~~GG
0,3
1v
2v
0,8
5v
0,6
Unscharfe Optimierung
Operationen von unscharfen Graphen Definition 13
Ein unscharfer Graph G~
heißt das Produkt von Graphen 111
~,
~SVG und
222
~,
~SVG . G
~ wird definiert als
SVVGGG~
,~~~
2121 ,
wobei 21 VV kartesisches Produkt der Mengen von Knoten 1V und 2V ist;
21
~~~SSS .
Dabei wenn
}|)/)({()(~
)( 1111 VvvvvSistVv kkkii und
}|)/)({()(~
)( 2222 VyyyySistVy jjjjj , dann
}),(|)),/(),({(),(~
)),(( 2121 VVyvyvyvyvSistVVyv jijijijiji , wobei
)}(),(min{),( 21 jiji yvyv .
Unscharfe Optimierung
Operationen von unscharfen Graphen
Beispiel
1v 1y 2y 3y 1
0,8
0,7 2v 0,6
2
~G 1
~G
Kartesisches Produkt 21
~~~GGG :
),( 21 yv
),( 22 yv
),( 31 yv
),( 32 yv
),( 11 yv
0,6
0,6
0,8
0,7
Unscharfe Optimierung
Operationen von unscharfen Graphen Definition 14 Ein unscharfer Graph
)~
,(~~~
2121 SVVGGG
wird Summe von unscharfen Graphen 1
~G und 2
~G genannt, wobei
21 VV kartesisches Produkt der Mengen von Knoten 1V und 2V ist, und
))(~
}({}){)(~
(),(~
)),(( 2121 jijijiji ySvyvSyvSistVVyv .
1v
1y 2y 3y 1
0,8
0,7
2v 0,6
2
~G
),( 21 yv
),( 22 yv
),( 31 yv
),( 11 yv
),( 12 yv
),( 32 yv
0,6
0,8
0,8
0,8
0,6 1
1
0,7
0,7
0,6
1
~G 21
~~~GGG
Beispiel