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

Enoncé des conditions d'optimalité39(*)

Cas de minimisation

La solution X_B = B^-1.b = 0 : X_N = 0 est optimale

ssi C_N - _B^T.N = 0 ; avec ^T_B = C^T_B.B^-1 optimale pour le Dual.

C_N - ^T_B.N sont les coûts réduits des variables hors base.

Dans le cas de minimisation les coûts réduits doivent être supérieurs ou égaux à zéro.

Cas de maximisation

La solution X_B = B^-1.b = 0, X_N = 0 est optimale ;

ssi C_N - ^T_BN =0 ; avec ^T_B = C^T_B.B^-1 optimale pour le Dual.

Où B  : représente une base qui est une sous matrice de A

N  : représente une sous matrice de A représentant les coefficients des

variables hors base.

C_B  : coefficient des variables de base dans la fonction économique

C_N  : coefficient des variables hors base dans la fonction économique

Vérification de l'optimalité de la solution de base^40(*)

Partons de la fonction économique

Z = C^TX

Z = C_BX_B + C_NX_N (1)

Précédemment nous avons vu que

X_B = B^-1 (b - NX_N)

Remplaçons X_B par sa valeur dans (1). Nous avons :

Z = C_B B^-1 (b - NX_N) + C_NX_N

Z = C_B B^-1 b - B^-1.NX_N + C_NX_N

z = C_B . B^-1 _. b - C_B. B^-1 . NX_N + C_NX_N

Z = C_B.B^-1b + C_NX_N - C_B.B^-1.NX_N

Mettons X_N en évidence

Z = C_B.B^-1b + C_N - C_B .B^-1.N X_N

Comme on l'a vu plus haut, ^T_B = C^T_B.B^-1 _.

La fonction économique aura l'allure suivante :

Z = ^T_B. b + ( C_N - ^T_BN) X_N

Cette expression est fonction des variables hors base. On peut tirer la condition d'optimalité de la solution de base X_B = B^-1b 0, X_N 0 pour un problème de minimisation C^TX

S.C : A_X = X

X 0

il faut alors qu'on ait des coûts réduits positifs ou nuls.

C_N - ^T_BN 0

Qu'est - ce qu'on remarque dans cette équation ?

Nous remarquons que Z comprend deux termes :

· le premier C_B.B^-1.b est une constante qui n'est autre que la valeur de la fonction économique du sommet X_B

· le second terme C_N - ^T_B.N X_N est une forme linéaire des seules variables hors base.

Si (C_N - ^T_B.N ) 0 , on comprend qu'il sera désavantageux de rendre positive l'une des V.H.B. Les sommets pour lesquels X_N = 0 sont nuls, est donc optimal.

La précédente égalité nous permet de soupçonner que la base est optimale. Ce critère peut ne pas être une condition nécessaire d'optimalité (cas de dégénérescence). Dans le cas de dégénérescence, il est théoriquement possible que l'algorithme cycle c'est - à - dire qu'on ait une suite infinie de changement de base nous laissant au même point. Après avoir vu une brève description de la méthode matricielle voyons celle des tableaux du simplexe.

* ³⁹ NJIYOBIRI, J.B. : Cours de recherche opérationnelle, LIC II, économie, U.L.K, Kigali, 2001-2002 inédit.

.

* ⁴⁰ NJIYOBIRI, J.B. : Op. cit.