La programmation linéaire en nombres entiers


François Clautiaux et Pierre Pesneau

Pour résoudre des problèmes d’optimisation, il peut être nécessaire de les mettre en équation dans des modèles mathématiques. La programmation linéaire en nombres entiers permet de le faire en utilisant uniquement des polynômes du premier degré, dont les variables doivent prendre des valeurs entières.

La programmation linéaire en nombres entiers s’appuie, comme son nom l’indique, sur la programmation linéaire, qui permet d’optimiser des fonctions du premier degré sur un ensemble défini par des inéquations du premier degré. L’intérêt de cette technique est que l’on dispose d’algorithmes très performants pour résoudre tout problème s’écrivant de cette manière.

 

Un exemple de programmation linéaire

 

L’entreprise Laivo fabrique des produits laitiers en gros. Le gérant veut déterminer les quantités de yaourt et de crème à fabriquer avant la fermeture annuelle afin de maximiser son profit en euros (€). La vente d’une tonne (t) de yaourts lui rapporte 500 €, tandis qu’une tonne de crème fraîche rapporte 450 €. L’entreprise sait d’expérience qu’elle ne vendra pas plus de huit tonnes de yaourts, et que la demande en crème est largement supérieure à ce qu’elle peut produire. Le temps de production est limité à soixante heures, sachant qu’il en faut six pour produire une tonne de yaourt et cinq pour une tonne de crème. Une fois produits, le yaourt et la crème sont stockés dans un espace modulaire limité à quinze unités de stockage. Il en faut une par tonne de yaourt, deux par tonne de crème.

 

 

 

Les données du problème.

 

Pour modéliser ... Lire la suite