Neben den Problemen der linearen Optimierung hat wohl die diskrete Optimierung unter den mathematischen Optimierungsmethoden die groBte praktische Aufmerk samkeit gefunden. Das ist sicher nicht zuletzt in der Tat sache begriindet, daB viele Modelle der linearen Optimie rung automatisch zu Aufgaben der diskreten Optimierung fUhren, wenn die Ganzzahligkeit fUr gewisse Modellvaria bIen gefordert wird. Eine derartige Ganzzahligkeitsforde rung ergibt sich aber haufig aus der okonomischen Pro blemsituation. So lassen sich z. B. bei der Losung eines Transportproblems nur ganze Anzahlen von Gtiterwagen einsetzen; die Planung eines Investitionsprojektes laBt nur den Einsatz ganzer Zahlen von Maschinen oder den Bau ganzer Zahlen von Fabrikanlagen 6konomisch rele vant erscheinen; die Planung des Bedarfs von Arbeits kraften kann mit der Ganzzahligkeitsforderung verbunden sein. Daher ist es keineswegs vielfach die Frage, ob die Ganzzahligkeit gewisser Modellvariablen okonomisch als gegeben angesehen werden kann. VielIllJilhr werfen die sich beim LosungsprozeB ergebenden Komplikationen das Problem auf, ob der Verzicht auf diese Ganzzahligkeits forderung okonomisch moglich erscheint. Weiterhin hat eine Reihe von diskreten Optimierungsmodellen kombi natorischen Charakters das Interesse der Anwender an derartigen Optimierungsmethoden gefordert, da sie ein fache und praktisch wichtige Problemsituationen be schreiben. Methoden der diskreten Optimierung sind heute bereits Gegenstand einer Ftille von Publikationen. Es gibt Mono graphien und umfassende Darstellungen selbst zu Teil- Vorwort 4 problemen der diskreten Optimierung und ihrer Anwen dung. Daher bin ich wohl dem Leser die Antwort auf die Frage schuldig, von welcher Zielstellung ich im folgenden ausgehen mochte.

Inhalt

Problemstellungen der diskreten Optimierung.- 1.1. Einleitende Bemerkungen.- 1.2. Mathematische Klassifizierung diskreter Optimierungsprobleme.- 1.3. Lineare ganzzahlige Optimierungsprobleme.- 1.4. Lineare 01-Probleme.- 2. Die numerische Problematik bei der ganzzahligen Optimierung.- 2.1. Die Problematik der Rundung nicht ganzzahliger Werte.- 2.2. Allgemeine Bemerkungen zur numerischen Problematik der Lösungsverfahren.- 3. Transport-, Zuordnungs- und Verteilungsprobleme.- 3.1. Das ganzzahlige klassische Transportproblem.- 3.2. Das Zuordnungsproblem.- 3.3. Ganzzahlige Verteilungsprobleme.- 4. Einige weitere Modellstrukturen der diskreten Optimierung.- 4.1. Modelle der Sortimentsplanung.- 4.2. Investitionsmodelle.- 4.3. Das Rucksackproblem.- 4.4. Das Lokalisationsproblem.- 4.5. Das Rundfahrtproblem.- 4.6. Reihenfolgeprobleme.- 5. Überführung anderer Probleme in diskrete Optimierungsaufgaben.- 5.1. Fixkostenprobleme.- 5.2. Aufgaben mit trennbarer Zielfunktion.- 6. Schnittebenen verfahren.- 6.1. Einteilung der Lösungsverfahren der diskreten Optimierung.- 6.2. Das Lösungsprinzip der Schnittebenen verfahren.- 6.3. Konstruktion der GOMORY-Schnitte.- 6.4. Endlichkeit des Verfahrens.- 6.5. Weitere Schnittebenenverfahren der diskreten Optimierung.- 6.6. Allgemeine Beurteilung der Schnittebenenverfahren.- 7. Entscheidungsbaumverfahren.- 7.1. Einteilung der Entscheidungsbaumverfahren.- 7.2. Der Lösungsgedanke der Branch-and-bound-Methodik.- 7.3. Anwendung auf das Rucksackproblem.- 8.4. Anwendung auf lineare Optimierungsaufgaben mit Ganzzahligkeitsforderungen.- 7.5. Aufzählungsmethoden.- 7.6. Dynamische Optimierung.- 7.7. Das Erweiterungsprinzip.- 7.8. Übersicht über die Entscheidungsbaumverfahren.- 7.9. Allgemeine Beurteilung der Entscheidungsbaumverfahren.- 8.Heuristische Verfahren.- 8.1. Vorbereitende Betrachtungen.- 8.2. Einteilung der heuristischen Verfahren.- 8.3. Stochastische Suchverfahren.- 8.4. Eröffnungsverfahren.- 8.5. Suboptimierende Iterationsverfahren.- 9. Lösung spezieller diskreter Modellstrukturen.- 9.1. Aufgaben mit Ganzzahligkeitsforderungen.- 9.2. Fixkostenprobleme.- 9.3. Aufgaben mit trennbarer Zielfunktion.- 9.4. Lokalisationsprobleme.- 9.5. Rundfahrtprobleme.- 9.6. Reihenfolgeprobleme.