Programmation Linéaire à valeurs entières


Cas particulier de la programmation linéaire : la solution ne peut être définie qu'au moyen de valeurs entières pour l'ensemble des variables.

L'utilisation d'une méthode telle que le simplex avec un arrondi sur les valeurs trouvées à l'optimum donne des résultats pouvant être très éloignés de la solution. Il faut donc utiliser une méthode spécifique.


Nous abordons trois de ces méthodes :

- décomposition binaire des variables, si cela est possible, et utilisation des techniques décrites pour les problèmes à valeurs binaires ;

- réductions successives de l'ensemble des solutions admissibles par des plans coupant, jusqu'à obtention par le simplex d'un optimum à variables entières ;

- arbre de recherche par séparation des ensembles de solutions admissibles, avec recherche de l'optimum en utilisant le simplex, jusqu'à découverte de l'optimum à variables entières..