Methoden der Ganzzahligen Optimierung

وظایف بهینه‌سازی نقش فزاینده‌ای در تجارت و فناوری بازی می‌کند. مشکلاتی که در آن متغیرهای خاص فقط می توانند مقادیر گسسته ای را به خود بگیرند، اهمیت فزاینده ای پیدا می کنند. به هر حال، وظایف بهینه‌سازی که در آن کمیت‌ها اتفاق می‌افتد یا در آنها جایگزین \"درست\" یا \"نادرست\" رخ می‌دهد به طور طبیعی منجر به مشکلات بهینه‌سازی اعداد صحیح می‌شود. از نظر تاریخی، اولین روش‌ها برای حل مشکلات حمل و نقل و نقشه‌برداری بودند. این دسته از برنامه های خطی اعداد صحیح دارای خاصیت مهمی هستند که وقتی برنامه خطی معمولی مرتبط برای مقادیر اولیه اعداد صحیح حل می شود، یک جواب عدد صحیح به خودی خود ایجاد می کند. این مورد برای انواع دیگر مسائل بهینه سازی اعداد صحیح نیست. اولین روش حل موثر برای مسائل بهینه سازی اعداد صحیح خطی عمومی به Gomory (1958) برمی گردد. از آن زمان تاکنون، تکنیک‌های بسیار متنوعی برای حل این مشکلات به بهترین شکل ممکن استفاده شده است. این شامل روش‌های شمارش، ملاحظات ترکیبی، هندسی و نظری گروهی و همچنین کاربرد بهینه‌سازی دینامیکی است. هنوز مشخص نشده است که کدام یک از این روش ها برای یک مشکل خاص مطلوب تر است. این کتاب پس از پرداختن به مبانی ریاضی مسائل بهینه سازی اعداد صحیح و پس از مقدمه ای کوتاه بر تئوری برنامه های خطی و نظریه دوگانگی، ابتدا به مسائل انتقال و انتساب می پردازد. آخرین تحولات نیز در نظر گرفته شده است، مانند مشکل ترکیب بهینه یا ایجاد جدول زمانی مدارس. این با بحث در مورد روش های Gomory، با تاکید ویژه بر روش عدد صحیح خالص (دوم) Gomory دنبال می شود.

Optimierungsaufgaben spielen in Wirtschaft und Technik eine immer wichtigere Rolle. Dabei gewinnen Probleme, in denen gewisse Variable nur diskrete Werte annehmen können, zunehmend an Bedeutung. Führen doch Optimierungsaufgaben, in denen Stückzahlen vorkommen oder in denen die Alternative "wahr" oder "falsch" auftritt, in natürlicher Weise auf ganzzahlige Optimierungsprobleme. Historisch gesehen waren es die Transport-und Zuordnungsprobleme, zu deren Lösung die ersten Verfahren entwickelt wurden. Diese Klasse von ganzzahligen linearen Programmen besitzt die wichtige Eigenschaft, daß sich bei Lösung des zugehörigen gewöhnlichen linearen Programmes bei ganzzahligen Ausgangswerten von selbst eine ganzzahlige Lösung ergibt. Bei anderen Typen von ganzzahligen Optimierungsaufgaben ist dies nicht der Fall. Das erste effektive Lösungsverfahren für allgemeine lineare ganz­ zahlige Optimierungsprobleme geht auf Gomory (1958) zurück. Seither wurden die verschiedensten Techniken angewendet, um solche Probleme möglichst gut zu lösen. Dazu gehören Enumerationsverfahren, kombina­ torische, geometrische und gruppentheoretische Überlegungen wie auch die Anwendung der dynamischen Optimierung. Welches dieser Verfahren für ein spezielles Problem das günstigste ist, ist bis heute noch ungeklärt. Im vorliegenden Buch werden nach Behandlung der mathematischen Grundlagen ganzzahliger Optimierungsprobleme sowie nach einer kurzen Einführung in die Theorie linearer Programme und in die Theorie der Dualität zunächst Transport-und Zuordnungsprobleme behandelt. Dabei werden auch neueste Entwicklungen berücksichtigt, wie etwa das Optimum­ Mix-Problem oder die Erstellung von Schulstundenplänen. Daran schließt sich eine Diskussion der Verfahren von Gomory an, wobei im besonderen auf das reinganzzahlige (zweite) Verfahren von Gomory Wert gelegt wurde.