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.
