Integer-Programmierung

Ein lineares Programmierproblem wird verwendet, um entweder das Maximum oder das Minimum einer Zielfunktion zu finden, die einigen Beschränkungen unterliegt. Diese Beschränkungen sind normalerweise Ungleichungen. Wenn diese Randbedingungen erfüllt sind, erhält man eine zulässige Lösung. Wenn eine dieser Lösungen gemäß der Zielfunktion entweder das Maximum oder das Minimum ist, erhält man eine optimale Lösung/

In vielen Situationen des wirklichen Lebens kann es erforderlich sein, dass die Entscheidungsvariablen ganzzahlig sind, da man die Anzahl der erforderlichen Busse oder des Personals ermitteln muss, die eingesetzt werden müssen usw. Solche Klassen von Problemen werden als Integer-Programmierprobleme bezeichnet.

Ganzzahlige Programmierprobleme können nicht mit der Simplex-Methode gelöst werden, sie müssen mit der Branch-and-Bound-Methode gelöst werden. Man kann sich den zulässigen Bereich, der von den Randbedingungen eingeschlossen ist, in einem konvexen Optimierungsproblem vorstellen, bei dem horizontale und vertikale Linien an jedem ganzzahligen Punkt gezeichnet werden. Die Lösung des Problems der Integer Linear Programming wird daher auf eine der horizontalen oder vertikalen Linien innerhalb des zulässigen Bereichs fallen. Die zulässige Menge ist nicht mehr konvex und wird aufgrund ihrer nicht konvexen Natur sehr mühsam zu lösen.

Es gibt verschiedene Arten von Methoden, die verwendet werden, um Probleme der Integer Linear Programming zu lösen. Die am häufigsten verwendete Methode ist die Branch-and-Bound-Methode.

Branch and Bound beinhaltet das Lockern der Integer-Beschränkungen und das Lösen des linearen Programms unter Verwendung entweder der grafischen oder der Simplex-Methode. Wenn sich nach Lockerung der Ganzzahlbeschränkungen alle Entscheidungsvariablen als Ganzzahlen herausstellen, dann ist die Lösungsmenge richtig.

Wenn die Lösung des entspannten linearen Programms jedoch keine ganzzahligen Werte als Lösungen der Entscheidungsvariablen liefert, muss man eine Branch-and-Bound-Technik anwenden, indem man das ursprüngliche Problem mit einem beschränkten ganzzahligen Wert der Entscheidungsvariablen löst, der dem Satz von Beschränkungen hinzugefügt wird. Wenn diese neue Problemmenge gelöst ist und sie mit ganzzahligen Werten einen optimalen Wert liefert, dann gibt es möglicherweise bessere Werte und daher müssen andere Zweige untersucht werden. Schließlich muss die Lösung von einem der Knoten in den besuchten Zweigen ausgewählt werden, die entweder das Maximum oder das Minimum ist. Wir müssen immer wieder eine lineare Relaxation des Problems mit neueren ganzzahligen Schranken lösen und nach der bestmöglichen Lösung im Kontext suchen. Für ein niederdimensionales Integer-Programming-Problem kann es besser sein, eine grafische Methode zur Lösung des Problems zu verwenden.

Eine Erweiterung des Integer-Programmierproblems ist das 0-1 Integer-Programmierproblem, bei dem Entscheidungsvariablen nur 0 oder 1 annehmen können. Diese Art von Problemen ist besonders nützlich, um ähnliche Probleme wie das Rucksackproblem zu lösen.


Source by Srinivasa Gopal

About admin

Check Also

Kann man Computerprogrammierer werden?

Der Einstieg in die Computerprogrammierung ist lukrativ, da Sie gut bezahlt werden. Obwohl diese Softwarebranche …

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.