Beispiel: Ein Betrieb fertigt zwei Produkte mit einem Stückgewinn von 110 DM bzw. 160 DM. Für die Herstellung stehen drei Maschinen I, II und III mit einer Kapazität von 120 Stunden bzw. 100 Stunden bzw. 40 Stunden zur Verfügung. Das erste Produkt benötigt auf den Maschinen I und III je eine Stunde, auf der Maschine II drei Stunden Bearbeitungszeit, das zweite Produkt auf den Maschinen I und II je vier Stunden und auf der Maschine III zwei Stunden Bearbeitungszeit.
An m Lieferorten sind die Mengen ai i = 1 bis m eines Gutes vorhanden, während in n Empfangsorten die Mengen bj, j = 1 bis n benötigt werden. Bekannt sind außerdem die Transportkosten ci,j für den Transport einer Einheit des Gutes vom Lagerort i zum Empfangsort j. Gesucht ist der Transportplan, bei dem die Summe der Transportkosten am kleinsten ist.
Beim Zuordnungsproblem ist eine optimale Zuordnung von n Elementen einer Menge zu den n Elementen einer anderen Menge gesucht, wobei für jede Einzelzuordnung eine Bewertung vorliegt. Beispielsweise sind vier Personen A, B, C, D vier Aufgaben I, II, III, IV zuzuordnen. Nicht jede Person ist für eine Aufgabe gleichge-eignet. Die Eignung ist aus der Bewertungsmatrix erkennbar.
Das Rundreiseproblem gehört in den größeren Problemkreis der Reihenfolge-Probleme. Es ist unter ihnen wohl das populärste und unter der Bezeichnung „travelling salesman“ bekannt: Von einem Ausgangsort ist die optimale Reiseroute durch die anderen vorgegebenen Orte gesucht. Dabei soll jeder Ort genau einmal erreicht werden und die Reise soll im Ausgangsort enden. Bekannt sind die Entfernungen zwischen den Orten. Unter dem Optimum wird meist der kürzeste Weg der Rundreise (geringste Kosten, geringster Zeitaufwand) verstanden. Als Optimum kann aber auch das Maximum (z. B. bei einer Inspektions- oder Besichtigungsrundreise) gesucht sein.
In den beiden vorangehenden Kapiteln bildet die Permutation die Grundlage zur Lösung der Probleme. Bei anderen Problemen werden die Kombinationen aus n Elementen zu je k mit oder ohne Wiederholung und mit oder ohne Berücksichtigung der Reihenfolge benötigt. Daher wollen wir in diesem Kapitel in einem Programm die Erstellung aËer dieser Kombinationen vornehmen. (Es wird nicht die Anzahl der Kombinationen berechnet — dazu siehe [5], S. 167ff. — sondern die Kombinationen selbst werden erstellt!)
Bei der Dynamischen Planungsrechnung werden nicht alle möglichen Lösungen (wie bei der Vollständigen Enumeration) berechnet, sondern man bricht eine Berechnung ab, wenn der augenblickliche Zwischenwert der Teillösung keine bessere Lösung liefern kann als eine andere, vergleichbare Lösung. Im Gegensatz zu der Begrenzten Enumeration, wo man die Berechnungen sequentiell durchgeführt hat, geht man bei der Dynamischen Planungsrechnung parallel vor. Wir veranschaulichen den Sachverhalt an einem „Baum“ genannten Graph.
Das Branch-and-Bound-Verfahren gehört mit der Begrenzten Enumeration und der Dynamischen Planungsrechnung zu den Entscheidungsbaumverfahren und steht mit ihnen der Vollständigen Enumeration gegenüber. Während man bei der Begrenzten Enumeration streng sequentiell, bei der Dynamischen Planungsrechnung streng parallel vorgeht, um Teillösungen auszuschließen, die für eine Optimallösung nicht in Frage kommen, stellt das Branch-and-Bound-Verfahren eine Mischung aus beiden dar. Man verfolgt im Entscheidungsbaum einen Zweig solange, wie er vermuten läßt, daß er zur Optimallösung führt. Dabei findet man neue Optimalitätsgrenzen (bound), durch die Teile des Entscheidungsbaumes abgezweigt (branch) werden. Beim Branch-and-Bound kann man also auf allen Stufen des Entscheidungsbaumes gleichzeitig Knoten in der Berechnung haben, die noch zur Optimallösung führen können.
Die Abb. 42 zeigt einen Netzplan mit 9 Tätigkeiten, die an den Kanten mit ihrer Dauer eingetragen sind. Jede Tätigkeit hat einen Vorgänger-Knoten und einen Nachfolge-Knoten. Die Knoten sind lückenlos aufsteigend so numeriert, daß ein Nachfolge-Knoten eine höhere Nummer hat als ein Vorgänger-Knoten. Der erste Knoten, der Start-Knoten hat die niedrigste Nummer 1, der letzte Knoten, der Ziel-Knoten, hat die höchste Knoten-Nummer.
Gustav Kastner
Backmatter
Metadaten
Titel
Operations Research mit BASIC auf Commodore 2000/3000, 4000/8000
