Entscheidungsunterstützungssysteme IWI Frankfurt 2004 Entscheidungsunterstützungssysteme - Moderne Optimierungsmethoden für kombinatorische Probleme EUS

Entscheidungsunterstützungssysteme IWI Frankfurt 2004

Entscheidungsunterstützungssysteme

- Moderne

Optimierungsmethoden für kombinatorische Probleme

EUS SS 2004


Standardisierungsmodell

• Ein Kommunikationsnetz wird als Graph repräsentiert. • Die Knoten stellen die Kommunikationspartner (Mensch,

Maschine) dar, die Kanten deren Informationsbeziehung. • Beschreibt man das Standardisierungsproblem so, dass in

den Knoten i jeweils die Kosten (Ki) der Standardisierung zu tragen sind, wodurch dann auf den Kanten, die die Kosten der Informationsübermittlung (cij) darstellen sollen, Kosteneinsparungen realisiert werden können, wenn beide kommunizierenden Knoten den gleichen Standard eingeführt haben, ergibt sich die Fragestellung, welcher Knoten mit einem Standard auszustatten ist.

• Es besteht demnach ein Trade-Off zwischen den (Knoten-) Kosten der Implementierung eines Standards einerseits und der Einsparung von (Kanten-) Informationskosten andererseits.


3.7.2 Modell

• Dies bedeutet nicht, dass im Falle einer Standardisierung gar keine Kosten für die Informationsübermittlung anfallen.

• Die cij können vielmehr als Differenz zwischen den Informationskosten vor und nach Standardisierung interpretiert werden.

1K1

2K2

c12

c21

ijnij

vij ccc


Implementierungskosten: Standard 1 K1=10Standard 2 K2= 5

Einsparungspotential anKommunikationskosten:

A

C B

24

3

6

12

2 6

Stellen Sie das lineare Programm (Gleichungssystem) zu diesem Problem auf.


Gleichungssystem

• Kosten: (xA1+xB1+xC1) * 10 + (xA2+xB2+xC2) * 5

• Einsparungen auf den Kanten:A B: xA1* xB1*24+xA2+ xB2*6

A C: xA1* xC1* 6+ xA2+ xC2*2

…

• Restriktionenmehrere Standards (Beispiel A1): xA1 ≤ 1

maximal ein Standard (Beispiel A): xA1 + xA2 ≤ 1

Zielfu

nktio

n


A*-Algorithmus

? . . . . ?

A

C B

• Welche Verzweigung ist sinnvoll?– Entwerfen und Berechnen Sie die Verzeigung der

ersten Ebene beim exklusiven Standardisierungsproblem.

– Geben sie für jedes Blatt g und h* an!


Eine mögliche Lösung

xB1 = 1 (xB2 = 0)

g = -15 h = 0(xC1 = xC2 = 0)

g = 0 h* = 2 (xB2 = xC2 = 1)

xA1 = xA2 = 0

g = -5 h* = 10(xB2 = xC2 = 1)

xA2 = 1 (xA1 = 0)

xB2 = 1 (xB1 = 0)g = -4 h = 9(xC2 = 1)

xB1 = xB2 = 0g = -5 h* = 0(xC1 = xC2 = 0)

g = -10 h* = 14 (xB1 = 1)

xA1 = 1 (xA2 = 0)

A

C B


Lösung (2)

xC1 = 1 xC2 = 0 xC1 = 0 xC2 = 1 xC1 = xC2 = 0

g = -14 (h = 0) g = 5 (h = 0) g = -4 (h = 0)

xB2 = 1 (xB1 = 0)g = -4 h = 9(xC2 = 1)


Aufgabenzerlegung beim ToH–Problem II

Rekursive Zerlegung• Stochastische Zuweisung der Teilaufgaben an

freie identische Agenten• Zerlegung des Problems beendet, wenn Start-

und Zielzustände gleich• Ergebnis liegt vor, wenn alle Teilaufgaben an

den Start-Agenten zurückgegeben wurden• Mittel-zum-Zweck Heuristik reduziert die

Komplexität drastisch von b n auf O(log n)


Aufgabenzerlegung beim ToH–Problem III

Zerlegung ist nur effektiv, wenn:

• Teilprobleme unabhängig lösbar sind• Hierarchische Annäherung an optimale Lösung garantiert ist• Zahl der Abstraktionsebenen mit der Problemgröße wächst

• Verhältnis von Abstraktionsebenen zueinander log k beträgt

• Problem in gleichgroße Unterprobleme zerlegt werden kann• Mindestens so viele Agenten wie Unterprobleme existieren• Problemzerlegung und Ergebniszusammenfassung

vernachlässigbar wenig Zeit beanspruchen


Aufgabenzerlegung beim ToH–Problem I


Move L 1 - 3

L 1 - 3M 1 - 2 M 2 -

S 1 -

T 1-

Documents

Entscheidungsunterstützungssysteme IWI Frankfurt 2004 Entscheidungsunterstützungssysteme - Moderne Optimierungsmethoden für kombinatorische Probleme EUS