Branch and Bound: Eine Einführung: Unterlagen Für Einen Kurs Des Instituts Für Operations Research Der Eth Zürich

ISBN-13: 9783540061120 / Niemiecki / Miękka / 1972 / 176 str.

Franz Weinberg; F. Weinberg

Opis

Es gibt eine grosse Menge von betriebswirtschaftlichen Entscheidungsfragen, die sich mit den nunmehr bereits als herkommlich geltenden Optimierungs methoden des Operations Research nicht behandeln la sen, sei es beispiels weise, dass die Zielfunktion und auch einzelne Restriktionen nicht konvex sind, sei es, dass nur ganzzahlige Losungen toleriert werqen, sei es, dass die von einzelnen Variablen angenommenen Zahlenwerte Einfluss auf die Gultigkeit ganzer Restriktionengruppen nehmen. So wachsen z. B. die Kosten der Lagerhaltung als Sprungfunktion mit der Er richtung jedes zusatzlichen Warenhauses und sie nehmen fur jedes bestehende Warenhaus meist konkav mit der Quantitat der gelagerten Guter zu. Dieser nicht-konvexe Charakter kann sich in einer Zielfunktion (Kosten-Minimierung) oder in einer Restriktion aussern (Nicht-Ueberschreitung einer Kostenlimite). Die Anzahl von Warenhausern ist offenbar eine ganze Zahl, deren Optimum unter Angabe der zugehorigen geographischen Standorte gesucht werden mag. Die Notwendigkeit der Berucksichtigung ortsgebundener Restriktionen fur einzelne Warenhauser (z.B. Provenienzvorschriften betreffend deren eigene Guterversorgung) ist vom Werte der logischen Variablen" abhangig, der angibt, ob ein bestimmtes Warenhaus errichtet werden soll oder nicht. Es wurde nicht schwer fallen, eine lange Liste von derartigen Problemen auf zuzahlen, die alle sehr erhebliche finanzielle Bedeutung fur eine Unternehmung annehmen. Diese Probleme haben schon immer bestanden; es ist interessant, dass sie in letzter Zeit immer haufiger genannt werden und der Ruf nach ihrer Losung mit immer grosserer Dringlichkeit ertont."

Spis treści

1 Branch and Bound: Eine Einführung.- 2 Das Handelsreisenden-Problem.- 3 Ein Branch and Bound-Algorithmus zur Bestimmung einer exakten Lösung des Maschinenbelegungsplanproblems für 3 Maschinen.- 4 Vertreter-Touren mit zeitlich variabler Dringlichkeit.- 5 Das verallgemeinerte Knapsack-Problem.- 6 Zusammenhang zwischen Dynamischer Programmierung und Branch and Bound.- 7 Diskussion der Modellwahl am Beispiel des Travelling-Salesman Problems.- 8 Ganzzahlige, Null-Eins- und Gemischt-Ganzzahlige Programmierung im Zusammenhang mit der Branch and Bound-Technik.- 9 Optimales Rangieren.- 10 Optimale Bildung von Nahgüterzügen.- 11 Gemeinsame Losgrössenrechnung für Teilevarianten bei deterministischem Bedarf.