Qu'est-ce que la programmation linéaire entière?

Des problèmes de programmation linéaires entiers surviennent lorsque vous essayez 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 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 maximisée ou minimisée et une ou plusieurs équations restrictives qui mettent des limites aux variables inconnues.Pour que le système soit linéaire, chaque restriction doit être une équation linéaire;Autrement dit, il ne doit contenir aucun cas de la variable inconnue avec des exposants supérieurs à un.

Les systèmes linéaires réguliers peuvent être résolus facilement à l'aide d'un ordinateur.Le programme peut identifier une solution en trouvant le dérivé et en le définissant égal à zéro.Il peut ensuite vérifier que le point est un maximum ou un minimum en vérifiant son voisinage immédiat sur la fonction.Tant que la dérivée est définie à chaque point le long de la fonction, l'ordinateur n'a qu'un nombre limité de solutions possibles à vérifier.

La programmation linéaire devient une programmation linéaire entière avec l'ajout de la restriction entière.Cela signifie que le problème reste le même, mais la réponse doit être constituée de 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ées;Il est cependant réfléchi du monde réel, dans lequel les éléments viennent souvent en unités discrètes et indivisibles.Cela rend la programmation linéaire entière importante pour les applications commerciales, car les entreprises souhaitent maximiser autant que possible les bénéfices mais ne peuvent 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 nécessaire à un ordinateur pour résoudre le système est indéterminé.Avec des restrictions entières, les ordinateurs ne peuvent pas utiliser l'outil de la dérivée car il n'y a aucune garantie que le point zéro du dérivé tombera sur un entier.La solution sera l'entier avec la valeur la plus élevée ou la plus basse de tous les entiers, donc l'ordinateur devrait les vérifier tous mdash;Un processus qui pourrait prendre un temps infini.

Les programmeurs ont développé une heuristique, ou des méthodes de résolution de problèmes, pour faire face à la complexité de ces problèmes.Une méthode pour résoudre les problèmes de programmation linéaire entier est l'algorithme de branche et lié, dans lequel l'ordinateur résout une série de problèmes liés à celui d'origine pour réduire la plage de valeurs disponibles à une solution.Pour des problèmes complexes, cependant, cela peut prendre beaucoup de temps.