(branch-and-bound) Der Entscheidungsbaum ist ein zusammenhängender kreisloser Graph, der aus einem Ausgangsknoten, Entscheidungsknoten, Zufallsknoten und Endknoten besteht. Die einzelnen Knoten sind mit "Kanten" oder "Pfaden" verbunden, die bestimmte Aktionen darstellen. Der Entscheidungsbaum ermöglicht die graphische Darstellung einer mehrstufigen Entscheidung. Das Verfahren des branch-and-bound wurde von Little, Murty, Sweeney und Karel zur Lösung des , Travelling-Salesman-Problems entwickelt. Grundsätzlich kann jede beliebige Zielfunktion mit diesem Verfahren optimiert werden. Durch die Anwendung von Verzweigungs- und Begrenzungsregeln wird die Auswahl der möglichen Ergebnisse schrittweise auf die optimalen Lösungen reduziert.
(1) Ein deterministischer Entscheidungsbaum verdeutlicht grafisch ein mehrstufiges Entscheidungsproblem, bei dem den einzelnen Teilaktivitäten jeweils sichere Ergebnisse zugeordnet werden können. Die Kanten des Entscheidungsbaums kennzeichnen dabei die Einzelaktivitäten, die inneren Knoten die jeweiligen Entscheidungssituationen und die Endknoten die erzielbaren Endergebnisse. Beispiel: Ein Sparer will 100 DM für zwei Jahre anlegen und zieht folgende Möglichkeiten in Betracht: 2: Kauf eines Sparbriefs vom Typ I; Rückzahlung nach 2 Jahren 122 DM; a2: Kauf eines Sparbriefs vom Typ II; Zins nach 1 Jahr 10 DM, Zins und Tilgung nach 2 Jahren 110 DM; zy. Wie a2, aber Verkauf des Sparbriefs nach 1 Jahr zu 99 DM. In den Fällen a2 und a3 werden die nach einem Jahr freien Beträge für ein Jahr zu 11% angelegt. Folgender Entscheidungsbaum kennzeichnet die verschiedenen Handlungsalternativen sowie die — an den Endknoten vermerkten — Endvermögensbeträge: (2) Bei einem stochastischen Entscheidungsbaum wird zusätzlich noch die Möglichkeit berücksichtigt, dass die Ergebnisse der einzelnen Teilaktivitäten von unterschiedlichen, im Zeitpunkt t = 0 noch nicht sicher vorhersehbaren Umweltentwicklungen beeinflusst werden. Das Endergebnis des betrachteten Entscheidungsproblems ergibt sich dann aus der Überlagerung der in zeitlicher Folge zu treffenden Teilentscheidungen und der Entwicklung der Umweltkonstellationen, wie sie durch einen Zustandsbaum verdeutlicht werden kann. Ein stochastischer Entscheidungsbaum weist somit zwei Arten von Kanten auf: Aktivitätskanten, welche die einzelnen Teilaktivitäten verdeutlichen, und Umweltkanten, die die Umweltentwicklungen symbolisieren. Die Aktivitätskanten beginnen jeweils in Entscheidungsknoten und enden in Situationsknoten, die die durch eine bestimmte Teilentscheidung eingetretene Situation verdeutlichen. Die letzten Kanten enden schliesslich in Ergebnisknoten, die das bei einer bestimmten Abfolge von Teilentscheidungen und Umweltentwicklungen erzielbare Endergebnis kennzeichnen. Beispiel: In dem voran gegangenen Beispiel werden für den nach einem Jahr gegebenen Anlagezins mit jeweils 50%-iger Wahrscheinlichkeit Sätze von 9% oder 13% für möglich gehalten. Obiger, um die im Zeitpunkt t = 0 bestehende Unsicherheit über die künftige Zinsentwicklung erweiterter Entscheidungsbaum verdeutlicht diese Situation. Bei der Entscheidung zwischen Typ I und Typ II ist neben den bereits durch den deterministischen Entscheidungsbaum verdeutlichten "starren" Handlungsalternativen ai, a2, a3 zusätzlich die Möglichkeit zu berücksichtigen, bei Erwerb des Typs II je nach der Höhe des in t = 1 bekannten Anlagezinses für die zweite Periode eine unterschiedliche Folgeentscheidung zu treffen ("flexible" Handlungsalternative). Für die Erwartungswerte des Endvermögens der drei soeben genannten Handlungsalternativen ergeben sich jeweils die an den Endknoten des deterministischen Entscheidungsbaumes vermerkten Werte; mit 122 würde der höchste Erwartungswert also bei Kauf von Typ I erzielt. Die flexible Strategie, Typ II zu kaufen und bei 9%-igem Anlagezins in t = 1 auch zu behalten, bei 13%-igem Zins aber zu verkaufen, führt allerdings mit 0,5 • 120,9 4- 0,5 • 123,17 = 122,035 zu einem höheren Erwartungswert als bei Typ I. Dieses Beispiel zeigt, dass die Möglichkeit, bei den Folgeentscheidungen in späteren Zeitpunkten auf Umweltentwicklungen, die im ursprünglichen Planungszeitpunkt noch unsicher waren, inzwischen aber genau bekannt sind, ggf. auch unterschiedlich zu reagieren, für die Beurteilung der im Zeitpunkt t = 0 unmittelbar zur Disposition stehenden Ausgangsaktivitäten von ausschlaggebender Bedeutung sein kann. Die systematische Berücksichtigung dieses Umstandes stellt das Grundprinzip der flexiblen Planung dar. Literatur: Bitz, M., Entscheidungstheorie, München 1981, S. 325 ff. Hax, H., Entscheidungsmodelle in der Unternehmung, Reinbek 1974, S. 70 ff.
(in der Wirtschaftsinformatik) sind spezielle Verfahren des Data Mining und dienen der Vorhersage der Klassenzugehörigkeit eines Objektes (Klassifikation).
Vorhergehender Fachbegriff: Entscheidungsart | Nächster Fachbegriff: Entscheidungsbaumverfahren
Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken
|
|