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

a. La méthode du simplexe

La méthode du simplexe est une technique algébrique itérative qui permet de trouver la solution optimale d'une façon ordonnée et concise. La présentation pratique de cette méthode est la suivante :

Soit x₁, x₂..........x_j,........x_n variables qui rendent maximale la relation :

F = c₁x₁ + c₂x₂ + ........+ c_jx_j + ........+ c_nx_n

Tout en satisfaisant aux conditions suivantes :

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + ......+ a_ijx_j +..........+ a_1nx_n b₁

a₂₁x₁ + a₂₂ + a₂₃x₃ + ......+ a_2jx_j +.........+ a_2nx_n b_n

_{......... .......... ......... ............}

a_i1x₁ + a_i2x₂ + a_i3x₃ +........+a_ijx_j +..........+ a_inx_n b_i

_{........ .......... ..........} .......

A_m1x₁ + a_m2x₂ + a_m3x₃ +........+a_mjx_j +..........+ a_mnx_n b_m

et telle que

x₁, x₂, x₃,.......,x_j,.......x_n 0

« F » s'appelle la fonction économique. Les inéquations sont les contraintes du problème. Le programme mathématique obtenu est connu sous le nom de programme linéaire. Il n'est évidemment possible de résoudre ce problème par le raisonnement, ni non plus par une construction graphique pour un problème de plus de trois variables. Notre modèle qui compte vingt quatre variables de décision et vingt contraintes prendrait quelques jours pour trouver une réponse juste.

Le mathématicien DANTZIG a eu le mérite d'établir un algorithme qui permet de résoudre ce genre de programme linéaire et d'atteindre la solution optimale par plusieurs itérations. Ce procédé, également connu sous le nom de méthode du simplexe, est exposé dans le paragraphe qui suit :

1^ère phase

Transformation des inéquations en équations et présentation condensée du problème. Chaque inéquation peut être ramenée à une équation en introduisant une inconnue supplémentaire, que l'on appelle variable d'écart ; nous la notons x_n+1 ( Il ne faut pas la confondre avec les autres variables dites principales).

Ainsi, l'inéquation de rang i devient :

a_i1x₁ + a_i2x₂ +.........+ a_ijx_j +..........+ a_inx_n + x_n+i = b_i

Tableau n° 1 : Tableau initial du simplexe.

	C1 C2 C3..... Cj....., Cn 0 0 .......... 0	F
	x1 x2 x3..... xj...... xn xn+1... xn+2... xn+m
xn+1 xn+2 ....... Xn+i ...... xn+m	a11 a12 a13.... a1j..... a1n 1 0 ...... 0 a21 a22 a23.... a2j..... a2n 0 1 ...... 0 ..... ..... ..... .... .... ..... ..... ...... ai1 a12 ai3.... aij..... ain 0 0 .... 1 0 ..... ..... ..... .... .... ..... ..... am1 am2 am3.... amj..... amn 0 0 ...........1	b1 b2 ..... bi ..... bm

Source : Cours de recherche opérationnelle.

Nous formons le tableau ci-dessous des coefficients, a_ij, b_i, et c_j afin de simplifier l'écriture. Chaque colonne correspond à une variable x_j, inscrite dans la deuxième ligne, la dernière colonne est formée par les termes constants. Ce tableau sera complété et transformé dans les phases suivantes.

2^ème phase : Recherche d'une solution de base

Rappelons qu'une solution de base est un ensemble de valeurs des variables x_j qui satisfont à toutes les conditions du problème, mais qui ne rendent pas la fonction économique optimale. La deuxième phase consiste toujours à rechercher une solution de base.

Comme on le verra ensuite, la méthode de DANTZIG permet de trouver la solution par itérations ; il est donc intéressant d'adopter, pour solution de base, une solution aussi rapprochée que possible de la solution finale ; cela diminue le nombre d'itérations à effectuer. Si aucune solution n'apparaît, on prendra la solution suivante, évidente, mais très éloignée de la solution finale.

La solution initiale de la base doit annuler toutes les variables principales (initiales) du modèle linéaire. Les variables d'écart seront de base dans la première solution de base.

x₁ = x₂ = x₃ =........ = x_j = ....... = x_n = 0

x_n+1 = b₁

x_n+2 = b₂

x_n+i = b_i

x_n+m= b_m

C'est cette solution que nous retiendrons ici.

Nous constatons que la solution de base comprend n variables nulles. Quant aux autres qui sont égales aux bi portées dans la dernière colonne du tableau établi en première phase, nous les inscrivons dans une colonne supplémentaire, placée en première position. D'où le tableau n°2 suivant

Tableau n° 2 : Présentation d'une solution de base

	C1 C2 C3..... Cj....., Cn 0 0 .......... 0	F
	x1 x2 x3..... xj...... xn xn+1... xn+2... xn+m
Xn+1 Xn+2 ....... Xn+i ...... Xn+m	a11 a12 a13.... a1j..... a1n 1 0 ...... 0 a21 a22 a23.... a2j..... a2n 0 1 ...... 0 ..... ..... ..... .... .... ..... ..... ...... ai1 a12 ai3.... aij..... ain 0 0 .... 1 0 ..... ..... ..... .... .... ..... ..... am1 am2 am3.... amj..... amn 0 0 ...........1	b1 b2 ..... bi ..... bm

Source : note de cours de recherche opérationnelle.

Ce tableau a la signification suivante :

Une solution du problème consiste à donner aux variables inscrites dans la première colonne les valeurs correspondantes de la dernière colonne ; quant autres variables, elles sont nulles.

3^ème phase : Amélioration de la solution de base.

Il est claire que la fonction économique F correspondant à la solution de base est nulle, il est claire également qu'elle sera augmentée si nous construisons une nouvelle solution dans laquelle figurera une variable x_j ; il y a intérêt pour cela à choisir la variable x_j dont le coefficient c_j est le plus grand.

Soit k l'indice de cette variable. Donner une valeur à x_k n'est possible qu'en diminuant les valeurs de toutes les variables x_n+1 à x_n+m, mais ceci est sans inconvénient puisque celles-ci ne figurent pas dans la fonction économique.

(on peut aussi dire qu'elles y figurent avec le coefficient zéro).

Il est donc intéressant de donner à x_k la valeur la plus grande possible.

Or, dans chaque équation de rang i, la plus grande valeur possible de x_k est obtenue pour x_n+i = o et vaut x_k = b_i/a_ik

Désignons alors par « r » l'indice i pour lequel le rapport b_i/a_ik est minimal ( on ne tiendra pas compte des valeurs négatives, qui n'ont évidemment pas de sens).

On voit alors qu'une nouvelle solution du problème est trouvée ; elle est constituée par l'ensemble suivant :

x₁ = x₂ = x₃ =......= x_j = ......x_n = 0

x_n+r = 0

x_k = b_r/a_rk

x_n+1 = b₁ - a_1k . b_r/a_rk

x_n+i = b_i - a_ik . b_r/a_rk

x_n+m = b_n - a_mk . b_r/a_rk

On dit qu'on a sorti la variable x_n+r de la base pour y faire entrer la variable x_k. La fonction économique qui était précédemment nulle, a maintenant pour valeur :

F = C_k . b_r/a_rk

Pratiquement, on repère tout d'abord le plus grand coefficient c_j, soit c_k puis on adjoint au tableau n°2 une nouvelle colonne, dans laquelle on forme les rapports b_i/a_ik

C'est le tableau ci-dessous, sur lequel les variables sortantes et entrantes sont repérées par des flèches.

Tableau n°3 : opération du pivot

	C1 C2 Ck..... Cj....., Cn Z
	x1 x2 xk..... xj...... xn xn+1... .... xn+m
Xn+1 Xn+i ....... Xn+r ...... Xn+m	a11 a12 a1k.... a1j..... a1n 1 ...... 0 ai1 ai2 aik.... aij..... ain 0 1 ......0 ..... ..... ..... .... .... ..... ...... ar1 ar2 ark.... Arj..... arn 0 1 0 ..... ..... ..... .... .... ..... ..... am1 am2 amk.... amj..... amn 0 ........1	b1 bi ..... br ..... bm	b1/a1k bi/aik ..... br/ark ..... bm/amk
		b

Source : note de cours de recherche opérationnelle 4^ème phase

Nous allons transformer le tableau précédent de telle façon que la variable entrante prenne effectivement place dans la première colonne, et que la signification du tableau donné en deuxième phase reste valable à savoir que les variables ne figurant pas dans la première colonne sont nulles, les autres prenant les valeurs portées dans l'avant dernière colonne. Il s'agit donc de remplacer la variable x_n+1 qui se trouve dans la première colonne, par la variable x_k

Ceci veut dire qu'il faut remplacer le système de « m » équations, dans lesquelles figurent x_k et une fois x_n+r, par un système dans lequel x_k n'apparaît qu'une fois. Ceci est facile si l'on se souvient qu'une équation linéaire d'un système d'équation peut toujours être remplacée par une combinaison linéaire d'équations de ce système. Ici, nous retranchons à chaque équation de rang i l'équation de rang r, multipliée par a_ik/a_rk.

Quant à l'équation de rang r, il suffit de diviser tous ses termes par a_rk. D'où un nouveau tableau dans lequel chaque terme a, b est remplacé par le terme a', b' tel que :

a'_ij = a_ij - a_ik . a_rj / a_rk

b'_i = b_i - a_ik . b_r / a_rk

Ce nouveau tableau s'écrit :

Tableau n° 4 : Tableau n° 3 après opération du pivot

C'1 C'2 O..... C'j........C'n Cn+1 Cn+m Z
x1 x2 xk..... xj...... xn xn+1... .... xn+m
Xn+1 Xn+2 Xn+I Xk Xn+m	a'11 a'12 0.... a'1j..... a'1n a'1,n+1..... a'1,n+m a'21 a'22 0.... a'2j..... a'2n a'i1 a'i2 0.... a'ij ar1/ark ar2/ark 1 a'm1 a'm2 0	b'1 b'2 b' br/ark b'm
		b

Source : note de cours de recherche opérationnelle

Le tableau n°4 se présente exactement comme le précédent (n°3). Nous pouvons donc grâce à lui, repérer à nouveau une variable dont le coefficient C'_j' soit le plus grand et l'introduire dans la deuxième solution par le même procédé. Ceci nous permet donc de construire une troisième solution.

Par le même procédé que celui qui a permis d'établir le tableau précédent à partir du n°3, nous pouvons construire des tableaux successifs représentant les différentes itérations.

Lorsque l'un des tableaux a tous ses coefficients C_j négatifs, il n'est plus possible de continuer pour un problème de maximisation, par contre pour un problème de

minimisation on continue parce que la valeur de la fonction économique continue à décroître. De cela, on a les conditions d'optimalité suivantes :

- pour un problème de maximisation, il faut que les coefficients des variables de base (coût réduits) soient négatifs.

- pour un problème de minimisation, il faut que tous les coefficients des

variables soient positifs si non la valeur de la fonction augmente alors qu'on

veut minimiser.

La solution du problème consiste alors à donner aux variables de la première colonne les valeurs correspondantes de la dernière colonne. Les variables qui ne sont pas dans la première colonne sont nulles.

Lorsqu'il s'agit d'un problème qui comprend plusieurs variables, la méthode du simplexe est applicable mais conduit à des tableaux très grands.

Pour avoir une solution, cela nécessite plusieurs itérations, on est face à un travail fastidieux. Grâce au développement de la technologie moderne, nous allons recourir à la méthode du simplexe révisée, capable d'exécuter les itérations en un peu de temps et aboutit à la solution optimale à l'aide du système informatisé.

Nous avons utilisé un logiciel appelé « STORM » qui nous a permis d'obtenir les valeurs optimales de toutes les variables d'une façon relativement aisée ; car la solution d'un programme linéaire de plusieurs variables risque de dépasser les capacités et la patience même d'un gestionnaire disposant de beaucoup d'expérience dans le domaine.