Was ist eine ganzzahlige lineare Programmierung?

Ganzzahl lineare Programmierprobleme treten auf, wenn Sie versuchen, lineare Systeme zu lösen und gleichzeitig anzugeben, dass alle unbekannten Variablen Ganzzahlen oder ganze Zahlen sein müssen.Lineare Systeme sind Gleichungssätze, die eine Situation beschreiben, in der der Programmierer versucht, eine Lösung zu finden.Sie bestehen normalerweise aus einer Gleichung, die maximiert oder minimiert werden muss, und eine oder mehrere Einschränkungsgleichungen, die unbekannte Variablen Grenzen setzen.Damit das System linear ist, muss jede Einschränkung eine lineare Gleichung sein;Das heißt, es darf keine Instanzen der unbekannten Variablen mit Exponenten enthalten.

Regelmäßige lineare Systeme können einfach mit einem Computer gelöst werden.Das Programm kann eine Lösung identifizieren, indem sie das Ableitungen finden und gleich Null setzen.Es kann dann überprüfen, ob der Punkt maximal oder minimal ist, indem die unmittelbare Nachbarschaft in der Funktion überprüft wird.Solange das Derivat an jedem Punkt entlang der Funktion definiert ist, hat der Computer nur eine begrenzte Anzahl möglicher Lösungen, um zu überprüfen.Dies bedeutet, dass das Problem gleich bleibt, aber die Antwort muss aus ganzzahligen Werten für die unbekannten Werte bestehen: Sie müssen ganze Zahlen sein.Manchmal bedeutet dies, dass die Lösung im Vergleich zu dem Fall, in dem Fraktionen zulässig sind, suboptimal ist.Es spiegelt jedoch die reale Welt wider, in der Elemente häufig in diskreten, unteilbaren Einheiten vorhanden sind.Dies macht die ganzzahlige lineare Programmierung für Geschäftsanwendungen wichtig, da Unternehmen die Gewinne so weit wie möglich maximieren möchten, sich jedoch nicht dafür entscheiden können, einen Bruchteil eines Produkts zu verkaufen.

Sobald die Ganzzahlbeschränkungen vorhanden sind, ist das Problem der Lösung des linearen Systems NP-vollständig.Dies bedeutet, dass die Zeit, die für einen Computer erforderlich ist, um das System zu lösen, unbestimmt ist.Mit ganzzahligen Beschränkungen können Computer das Tool des Derivats nicht verwenden, da es keine Garantie gibt, dass der Nullpunkt des Derivats auf eine Ganzzahl fällt.Die Lösung ist die Ganzzahl mit dem höchsten oder niedrigsten Wert aller Ganzzahlen, sodass der Computer sie alle und mdash überprüfen muss.Ein Prozess, der unendlich viel Zeit in Anspruch nehmen könnte.

Programmierer haben Heuristiken oder Methoden zur Problemlösung entwickelt, um mit der Komplexität dieser Probleme umzugehen.Eine Methode zur Lösung von ganzzahligen linearen Programmierproblemen ist der Zweig- und gebundene Algorithmus, bei dem der Computer eine Reihe von Problemen löst, die mit dem ursprünglichen bezogen werden, um den verfügbaren Wertebereich auf eine Lösung einzugrenzen.Für komplexe Probleme kann dies jedoch lange dauern.