Branch and Bound: Eine Einführung: Unterlagen für einen Kurs by Giancorrado Escher (auth.), Prof. Dr. Franz Weinberg (eds.)

By Giancorrado Escher (auth.), Prof. Dr. Franz Weinberg (eds.)

Es gibt eine grosse Menge von betriebswirtschaftlichen Entscheidungsfragen, die sich mit den nunmehr bereits als herkömmlich geltenden Optimierungs­ methoden des Operations study nicht behandeln la§sen, sei es beispiels­ weise, dass die Zielfunktion und auch einzelne Restriktionen nicht konvex sind, sei es, dass nur ganzzahlige Lösungen toleriert werqen, sei es, dass die von einzelnen Variablen angenommenen Zahlenwerte Einfluss auf die Gültigkeit ganzer Restriktionengruppen nehmen. So wachsen z. B. die Kosten der Lagerhaltung als Sprungfunktion mit der Er­ richtung jedes zusätzlichen Warenhauses und sie nehmen für jedes bestehende Warenhaus meist konkav mit der Quantität der gelagerten Güter zu. Dieser nicht-konvexe Charakter kann sich in einer Zielfunktion (Kosten-Minimierung) oder in einer Restriktion äussern (Nicht-Ueberschreitung einer Kostenlimite). Die Anzahl von Warenhäusern ist offenbar eine ganze Zahl, deren optimal unter Angabe der zugehörigen geographischen Standorte gesucht werden magazine. Die Notwendigkeit der Berücksichtigung ortsgebundener Restriktionen für einzelne Warenhäuser (z.B. Provenienzvorschriften betreffend deren eigene Güterversorgung) ist vom Werte der logischen Variablen" abhängig, der angibt, ob ein bestimmtes Warenhaus errichtet werden soll oder nicht. Es würde nicht schwer fallen, eine lange Liste von derartigen Problemen auf­ zuzählen, die alle sehr erhebliche finanzielle Bedeutung für eine Unternehmung annehmen. Diese Probleme haben schon immer bestanden; es ist interessant, dass sie in letzter Zeit immer häufiger genannt werden und der Ruf nach ihrer Lösung mit immer grösserer Dringlichkeit ertönt.

Show description

Read or Download Branch and Bound: Eine Einführung: Unterlagen für einen Kurs des Instituts für Operations Research der ETH Zürich PDF

Similar research books

Case-Based Reasoning Research and Development: 20th International Conference, ICCBR 2012, Lyon, France, September 3-6, 2012. Proceedings

This publication constitutes the completely refereed post-conference court cases of the twentieth overseas convention on Case-Based Reasoning examine and improvement (ICCBR 2012) held in Lyon, France, September 3-6, 2012. The 34 revised complete papers provided have been conscientiously chosen from fifty one submissions. The displays and posters lined quite a lot of CBR themes of curiosity to either practitioners and researchers, together with foundational concerns protecting case illustration, similarity, retrieval, and version; conversational CBR recommender structures; multi-agent collaborative structures; info mining; time sequence research; net purposes; wisdom administration; criminal reasoning; healthcare structures and making plans and scheduling platforms.

Recent Advances in Nitric Oxide Research

The overseas Symposium on fresh Advances in Nitric Oxide examine used to be held in Sapporo, Japan, in September 1997. Researchers from Japan and the USA met to proportion their newest findings at the debatable functionality of NO within the human physique. The papers contained during this quantity, which have been provided on the Sapporo Symposium, concentrate on newly came upon mechanisms of NO construction and NO toxicity.

Critical Thinking: Understanding and Evaluating Dental Research

This paintings goals to aid readers develop into extra discerning shoppers of dental literature. It presents an creation to medical procedure, size, statistical inferences, interpretation, examine techniques and good judgment. an issue part permits readers to check their serious pondering abilities.

Emerging Research in Computing, Information, Communication and Applications: ERCICA 2015, Volume 1

This court cases quantity covers the court cases of ERCICA 2015. ERCICA presents an interdisciplinary discussion board for researchers, expert engineers and scientists, educators, and technologists to debate, debate and advertise study and expertise within the upcoming components of Computing, info, communique and their purposes.

Additional info for Branch and Bound: Eine Einführung: Unterlagen für einen Kurs des Instituts für Operations Research der ETH Zürich

Example text

Die Nullelemente (3,2) und (5,1) stellen die einzigen beiden Wegstücke dar, durch welche man die bisher ausgewählten Bögen zu einer Tour schliessen kann. Ergebnis, nach N-1 = 4 Branch-Schritten: 1) Reihenfolge der Besuche: 0 - 3 - 2 - 4 - 5 - 1 - 0 2) Länge des resultierenden Weges: 63 Der zugehörige Lösungsbaum, wie er bis jetzt erzeugt wurde, ist in Abb. 7 dargestellt. - 30 - 58 Abb. 7 Bisher erzeugter Lösungsbaum 2) Prüfung der gefundenen Lösung auf Optimalität Durch Vergleich der bisher berechneten Bounds mit der gefundenen Lösung sieht man, dass nur der Knoten (0, 3) für weitere Untersuchungen in Frage kommt, während (1,0), (4,5) und (2,4) ausscheiden.

Branching. Die Nullelemente (3,2) und (5,1) stellen die einzigen beiden Wegstücke dar, durch welche man die bisher ausgewählten Bögen zu einer Tour schliessen kann. Ergebnis, nach N-1 = 4 Branch-Schritten: 1) Reihenfolge der Besuche: 0 - 3 - 2 - 4 - 5 - 1 - 0 2) Länge des resultierenden Weges: 63 Der zugehörige Lösungsbaum, wie er bis jetzt erzeugt wurde, ist in Abb. 7 dargestellt. - 30 - 58 Abb. 7 Bisher erzeugter Lösungsbaum 2) Prüfung der gefundenen Lösung auf Optimalität Durch Vergleich der bisher berechneten Bounds mit der gefundenen Lösung sieht man, dass nur der Knoten (0, 3) für weitere Untersuchungen in Frage kommt, während (1,0), (4,5) und (2,4) ausscheiden.

Reduktionskonstante = 5 nach 1(=7) P 2. Element für nächsten BranchSchritt. Entweder (2,4) oder (5,1); Entscheid zugunsten (2,4) p 3. Neu erzeugte Knoten: 4(=8) O® OQ) ~~ O® OG) §] cp Abb. 5 Reduzierte Matrix D 3 für 3-Städteproblem und neu erzeugte Knoten beim 3. Branching 73 - 29 - Schritt 4 Analog Schritt 1, ausgeführt auf D 3 . Ergebnis: 1. Reduktionskonstan te = 7 nac h 1( =7) 2( =9) 2. Neu erzeugte Knoten: von ~ ~ 3( =7) co 5( =9) OG> O€) B ~ Rest: 2 X 2-Matrix mit zwei unendlichen und zwei verschwindenden Elementen.

Download PDF sample

Rated 4.18 of 5 – based on 15 votes