Was ist ganzzahlige lineare Programmierung?
Ganzzahlige lineare Programmierprobleme treten auf, wenn versucht wird, lineare Systeme zu lösen, während angegeben wird, dass alle unbekannten Variablen Ganzzahlen oder ganze Zahlen sein müssen. Lineare Systeme sind Gleichungssysteme, die eine Situation beschreiben, für die der Programmierer versucht, eine Lösung zu finden. Sie bestehen normalerweise aus einer Gleichung, die maximiert oder minimiert werden muss, und einer oder mehreren einschränkenden Gleichungen, die unbekannten Variablen Grenzen setzen. Damit das System linear ist, muss jede Einschränkung eine lineare Gleichung sein. Das heißt, es dürfen keine Instanzen der unbekannten Variablen mit Exponenten größer als eins enthalten sein.
Normale lineare Systeme können leicht mit einem Computer gelöst werden. Das Programm kann eine Lösung identifizieren, indem es die Ableitung findet und auf Null setzt. Anschließend kann überprüft werden, ob der Punkt ein Maximum oder ein Minimum ist, indem die unmittelbare Umgebung der Funktion überprüft wird. Solange die Ableitung an jedem Punkt der Funktion definiert ist, hat der Computer nur eine begrenzte Anzahl möglicher Lösungen zu prüfen.
Die lineare Programmierung wird zur ganzzahligen linearen Programmierung, wobei die ganzzahlige Einschränkung hinzugefügt wird. Das heißt, das Problem bleibt gleich, aber die Antwort muss aus ganzzahligen Werten für die unbekannten Werte bestehen: Es müssen ganze Zahlen sein. Manchmal bedeutet dies, dass die Lösung im Vergleich zu dem Fall, in dem Brüche zulässig sind, nicht optimal ist. es spiegelt jedoch die reale Welt wider, in der Gegenstände oft in diskreten, unteilbaren Einheiten vorliegen. Aus diesem Grund ist 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 Teil eines Produkts zu verkaufen.
Sobald die ganzzahligen Beschränkungen vorliegen, ist das Problem der Lösung des linearen Systems NP-vollständig. Dies bedeutet, dass die Zeit, die ein Computer benötigt, um das System zu lösen, unbestimmt ist. Mit Einschränkungen für Ganzzahlen können Computer das Tool der Ableitung nicht verwenden, da nicht garantiert werden kann, dass der Nullpunkt der Ableitung auf eine Ganzzahl fällt. Die Lösung ist die Ganzzahl mit dem höchsten oder niedrigsten Wert unter allen Ganzzahlen, sodass der Computer sie alle überprüfen muss - ein Vorgang, der unendlich viel Zeit in Anspruch nehmen kann.
Programmierer haben Heuristiken oder Methoden zur Problemlösung entwickelt, um mit der Komplexität dieser Probleme fertig zu werden. Eine Methode zur Lösung ganzzahliger linearer Programmierprobleme ist der Branch-and-Bound-Algorithmus, bei dem der Computer eine Reihe von Problemen löst, die sich auf das ursprüngliche Problem beziehen, um den verfügbaren Wertebereich auf eine Lösung einzugrenzen. Bei komplexen Problemen kann dies jedoch lange dauern.