Les problèmes de programmation linéaire surviennent lorsque vous tentez de résoudre des systèmes linéaires, tout en précisant que toutes les variables inconnues doivent être des entiers ou des nombres entiers. Les systèmes linéaires sont des ensembles d'équations qui décrivent une situation pour laquelle le programmeur tente de trouver une solution. Ils se composent généralement d'une équation qui doit être agrandie ou réduite et un ou plusieurs équations restriction qui a mis des limites sur les variables inconnues. Pour que le système soit linéaire, chaque restriction doit être une équation linéaire, c'est, il doit contenir aucun cas de la variable inconnue avec des exposants de plus d'un.
Les systèmes linéaires réguliers peuvent être résolus facilement en utilisant un ordinateur. Le programme peut trouver une solution en trouvant le dérivé et le mettre à zéro. On peut alors vérifier que le point est un maximum ou un minimum en vérifiant son voisinage immédiat de la fonction. Tant que le dérivé est défini en chaque point de la fonction, l'ordinateur ne dispose que d'un nombre limité de solutions possibles à vérifier.
La programmation linéaire devient programmation linéaire avec l'ajout de la restriction entier. Cela signifie que le problème reste le même, mais la réponse doit consister en des valeurs entières pour les valeurs inconnues: elles doivent être des nombres entiers. Parfois, cela signifie que la solution sera sous-optimale par rapport au cas dans lequel les fractions sont autorisés, il est réfléchissante, cependant, du monde réel, dans lequel les éléments viennent souvent en unités discrètes indivisibles. Cela rend programmation linéaire important pour les applications commerciales, car les entreprises veulent maximiser les profits, autant que possible, mais ne peut pas choisir de vendre une fraction d'un produit.
Une fois que les restrictions entières sont en place, le problème de la résolution du système linéaire est NP-complet. Cela signifie que le temps qui est nécessaire pour un ordinateur de résoudre le système est indéterminée. Avec restrictions entiers, les ordinateurs ne peuvent pas utiliser l'outil du dérivé car il n'y a aucune garantie que le point zéro de la dérivée va tomber sur un entier. La solution sera le nombre entier avec la plus haute ou la plus basse de tous les nombres entiers, afin que l'ordinateur devra vérifier tous - un processus qui pourrait prendre un temps infini.
Les programmeurs ont développé des heuristiques ou des méthodes de résolution de problèmes, pour faire face à la complexité de ces problèmes. Une méthode de résolution de problèmes de programmation linéaire est la branche algorithme de séparation, dans lequel l'ordinateur résout une série de problèmes liés à l'original pour affiner la gamme de valeurs disponibles à une solution. Pour des problèmes complexes, cependant, cela peut prendre un certain temps.