Methoden der Ganzzahligen Optimierung

Optimierungsaufgaben spielen in Wirtschaft und Technik eine immer wichtigere Rolle. Dabei gewinnen Probleme, in denen gewisse Variable nur diskrete Werte annehmen knnen, zunehmend an Bedeutung. Fhren doch Optimierungsaufgaben, in denen Stckzahlen vorkommen oder in denen die Alternative "wahr" oder "falsch" auftritt, in natrlicher Weise auf ganzzahlige Optimierungsprobleme. Historisch gesehen waren es die Transport-und Zuordnungsprobleme, zu deren Lsung die ersten Verfahren entwickelt wurden. Diese Klasse von ganzzahligen linearen Programmen besitzt die wichtige Eigenschaft, da sich bei Lsung des zugehrigen gewhnlichen linearen Programmes bei ganzzahligen Ausgangswerten von selbst eine ganzzahlige Lsung ergibt. Bei anderen Typen von ganzzahligen Optimierungsaufgaben ist dies nicht der Fall. Das erste effektive Lsungsverfahren fr allgemeine lineare ganz zahlige Optimierungsprobleme geht auf Gomory (1958) zurck. Seither wurden die verschiedensten Techniken angewendet, um solche Probleme mglichst gut zu lsen. Dazu gehren Enumerationsverfahren, kombina torische, geometrische und gruppentheoretische berlegungen wie auch die Anwendung der dynamischen Optimierung. Welches dieser Verfahren fr ein spezielles Problem das gnstigste ist, ist bis heute noch ungeklrt. Im vorliegenden Buch werden nach Behandlung der mathematischen Grundlagen ganzzahliger Optimierungsprobleme sowie nach einer kurzen Einfhrung in die Theorie linearer Programme und in die Theorie der Dualitt zunchst Transport-und Zuordnungsprobleme behandelt. Dabei werden auch neueste Entwicklungen bercksichtigt, wie etwa das Optimum Mix-Problem oder die Erstellung von Schulstundenplnen. Daran schliet sich eine Diskussion der Verfahren von Gomory an, wobei im besonderen auf das reinganzzahlige (zweite) Verfahren von Gomory Wert gelegt wurde.