Programmation linéaire outil effficace pour la plannification optimale de la production dans une entreprise industrielle .Cas de la Briqueterie Rwandaise Ruliba

b. L'efficacité de l'algorithme du simplexe

Après plus de 40 ans d'utilisation, l'algorithme du simplexe a fait ses preuves. Il peut résoudre, même sur micro-ordinateur, des modèles comportant des milliers de variables et de contraintes.

Au fil des années, l'implantation de cet algorithme s'est raffinée, il existe présentement de multiples versions de l'algorithme du simplexe, dont la méthode révisée, la méthode primal-dual, la méthode duale etc. Chacune a son champ d'application propre, où elle s'avère plus efficace que les autres.

Le comportement général de l'algorithme du simplexe a été abondamment étudié. Le nombre d'opérations arithmétiques qu'il requiert dans la résolution d'un modèle linéaire continu dépend à la fois de la taille du modèle et du nombre d'itérations nécessaires pour parvenir à une solution optimale, ce nombre d'itérations étant lui-même lié à la taille. La taille d'un modèle est mesurée par le nombre de données nécessaires pour le définir : en pratique, on utilise généralement comme mesures le nombre « n » de variables ainsi que le nombre « m » de contraintes, technologiques.

Deux approches s'offrent à qui veut décrire le nombre d'itération de l'algorithme du simplexe pour atteindre une solution d'un modèle linéaire de taille donnée : ou bien établir le nombre espéré d'itérations pour atteindre cette solution optimale ou bien compter le nombre d'itérations requises dans le cas le plus intraitable^41(*). Cette seconde approche mène au résultat suivant : il existe des modèles linéaires pour lesquels l'obtention d'une solution optimale requiert autant de tableaux, chacun comptant pour une itération.

Il y a toutefois une règle de pratique , certes empirique mais qui s'appuie sur une expérience longue de 40 ans : le nombre d'itérations nécessaires pour obtenir un tableau optimal d'un modèle provenant d'un problème pratique est habituellement compris entre 1,5 m et 2 m, où m est le nombre de contraintes technologiques.

3.5. Programmation linéaire et le dual

3.5.1. Le dual

Dans la programmation linéaire, tout problème de maximisation (minimisation) a un problème de minimisation (maximisation) qui lui correspond. Le problème initial s'appelle le primal ; le problème correspondant s'appelle le dual. La meilleure façon d'exprimer la relation entre les deux est l'utilisation des paramètres qu'ils ont en commun. Par exemple on peut soit maximiser l'utilité sous une contrainte budgétaire soit, minimiser le coût associé à l'obtention d'un certain niveau d'utilité. Dans une entreprise de production, on peut maximiser la production ou minimiser le coût sous contrainte d'un certain niveau de production.

Exemple : soit le problème initial ou le primal,

Maximiser = g₁x₁ + g₂x₂ + g₃x₃

Sous contraintes

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ b₁

a₂₁x₁ + a₂₂x₂ + a₂₃x₃ b₂

a₃₁x₁ + a₃₂x₂ + a₃₃x₃ b₃

x₁, x₂, x₃ 0

Le problème dual correspondant est :

Minimiser F = b₁z₁ + b₂z₂ + b₃z₃

a₁₁z₁ + a₂₁z₂ + a₃₁z₃ g₁

a₁₂z₁ + a₂₂z₂ + a₃₂z₃ g₂

a₁₃z₁ + a₂₃z₂ + a₃₃z₃ g₃

z₁, z₂, z₃ 0

* ⁴¹ NORBERT, Y. : OP. cit., P. 217