Qu'est-ce que la programmation linéaire en nombres entiers?
Des problèmes de programmation linéaire entiers apparaissent lorsque vous tentez de résoudre des systèmes linéaires tout en spécifiant que toutes les variables inconnues doivent être des entiers ou des nombres entiers. Les systèmes linéaires sont des ensembles d'équations décrivant une situation pour laquelle le programmeur tente de trouver une solution. Ils consistent généralement en une équation qui doit être maximisée ou minimisée et une ou plusieurs équations restrictives qui limitent les variables inconnues. Pour que le système soit linéaire, chaque restriction doit être une équation linéaire; c'est-à-dire qu'il ne doit contenir aucune occurrence de la variable inconnue avec des exposants supérieurs à un.
Les systèmes linéaires classiques peuvent être facilement résolus à l'aide d'un ordinateur. Le programme peut identifier une solution en trouvant la dérivée et en la réglant à zéro. Il peut ensuite vérifier que le point est maximum ou minimum en vérifiant son voisinage immédiat sur la fonction. Tant que la dérivée est définie en chaque point de la fonction, l'ordinateur n'a qu'un nombre limité de solutions à vérifier.
La programmation linéaire devient une programmation linéaire en nombre entier avec l’ajout de la restriction en nombre entier. Cela signifie que le problème reste le même, mais que la réponse doit être constituée de valeurs entières pour les valeurs inconnues: il doit s'agir de nombres entiers. Parfois, cela signifie que la solution sera sous-optimale par rapport au cas dans lequel les fractions sont autorisées; Il reflète toutefois le monde réel, dans lequel les éléments sont souvent présentés en unités distinctes et indivisibles. Cela rend la programmation linéaire entière importante pour les applications métiers, car les entreprises veulent maximiser leurs profits mais ne peuvent pas choisir de vendre une fraction de produit.
Une fois que les restrictions relatives aux nombres entiers sont en place, le problème de la résolution du système linéaire est NP-complet. Cela signifie que le temps nécessaire à un ordinateur pour résoudre le système est indéterminé. Avec les restrictions relatives aux nombres entiers, les ordinateurs ne peuvent pas utiliser l'outil de la dérivée car rien ne garantit que le point zéro de la dérivée tombera sur un entier. La solution sera le nombre entier avec la valeur la plus élevée ou la plus faible parmi tous les nombres entiers, de sorte que l’ordinateur devra toutes les vérifier, processus qui pourrait prendre un temps infini.
Les programmeurs ont développé des méthodes heuristiques, ou des méthodes de résolution de problèmes, pour traiter la complexité de ces problèmes. Une méthode de résolution de problèmes de programmation linéaire en nombres entiers est l’algorithme de branchement et lié, dans lequel l’ordinateur résout une série de problèmes liés au problème original afin de réduire la plage de valeurs disponible à une solution. Pour des problèmes complexes, toutefois, cela peut prendre beaucoup de temps.