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

La validation des modèles

Dans cette optique, quelle que soit l'utilisation normative ou descriptive

d'un modèle, il est indispensable, avant de s'en servir pour prendre une décision, de vérifier sa qualité. Les décisions prises sur base d'un modèle qui ne représente pas la réalité ne peuvent pas être meilleures, et sont souvent pires, que celles qui sont prises sans modèle du tout.

Mais vérifier la qualité d'un modèle est une démarche logique beaucoup plus compliquée qu'on ne le croit. Il faut d'abord naturellement, s'assurer de sa cohérence interne : les relations algébriques qui constituent le modèle correspondent-elles à ce que l'on sait par ailleurs du phénomène étudié ?

Mais cela n'est pas suffisant : beaucoup de modèles paraissent tout à fait crédibles sur cette base, et donnent cependant des résultats tout à fait farfelus. Il est donc nécessaire de trouver un moyen de comparer les résultats du modèle avec ceux qu'il « aurait dû » donner s'il avait fonctionné parfaitement : c'est ce qu'on fait, lorsqu'on soumet une théorie à l'épreuve de la vérification expérimentale.

La chose est plus difficile dans le cas des études économiques à cause du grand nombre de variables et de relations impliquées dans des modèles de grandes dimensions.

Dans le cas d'un modèle purement descriptif, il est en principe possible de

pratiquer un test historique, c'est-à-dire de faire fonctionner le modèle dans un environnement observé dans le passé, et de comparer les valeurs prédites par le modèle à celles qui ont été effectivement enregistrées.

La validation des modèles normatifs est encore beaucoup plus compliquée, puisqu'on ne peut cette fois se fier à l'observation de décisions passées. Le mieux est alors sans doute d'essayer de comparer, du point de vue du décideur, la qualité des prescriptions du modèle à celle des solutions qui auraient été retenues sans son aide.

3.3. Méthode de résolution d'un programme linéaire.

Un programme linéaire peut être résolu soit par la méthode graphique, soit par la méthode algébrique.

3.4.1. Méthode des graphiques.

La programmation linéaire a pour objectif de déterminer l'affectation optimale de ressources rares entre les activités ou produits concurrents. Les situations économiques demandent souvent qu'on optimise une fonction sous plusieurs contraintes prenant la forme d'inégalités.

Dans la méthode graphique, seules les variables d'activités ou variables réelles seront utilisées. Il n'y aura donc pas de variables d'écart ni de variables artificielles après traduction du problème posé en modèle mathématique, on se bornera seulement à :

- représenter graphiquement les droites - limites (équations provenant des

inéquations de départ) ;

- délimiter la frontière de l'enveloppe polygonale, c'est à dire à construire le

domaine d'acceptabilité ;

- remplacer successivement les coordonnées de chaque sommet du polygone

dans la fonction économique afin d'obtenir la combinaison optimale cherchée

(minimum ou maximum).

En général, pour chercher le minimum, on optera pour le point le plus voisin de l'origine, alors que pour le maximum ce sera le point le plus éloigné. On pourra utiliser, à la place de l'énumération de tous les points du polygone d'acceptabilité, le procédé qui consiste à déplacer la droite de la fonction économique parallèlement à son inclinaison à l'origine et en chacun des sommets du domaine d'acceptabilité. Pour le coût, on retiendra la droite la plus voisine de l'origine et pour le maximum, la plus éloignée. Le premier sommet sera le minimum et le dernier atteint le maximum cherché.

3.4.2. Méthode algébrique

Avant de passer à la méthode algébriques pour résoudre un programme linéaire voyons, d'abord les différentes formes d'un programme linéaire.

3.4.2.1. Formes canoniques

Lorsque l'ensemble des contraintes se présente sous forme d'inégalités

( ou ) on parle de la forme canonique. Toutefois, il convient de distinguer d'un programme canonique de type I d'un programme canonique de type II.

· Un programme canonique de type I est un programme dans lequel les contraintes d'inégalités sont tournées dans le sens « inférieur ou égal » l'objectif recherché étant la maximisation de la fonction critère ou fonction économique.

· Un programme canonique de type II a des contraintes d'inégalités tournées dans le sens « supérieur ou égal » et l'objectif est un minimum.

Exemple

Max. Z = c₁x₁ + c₂x₂ + c₃x₃

s/c

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

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

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

x₁ o, x₂ o, x₃ o

Min. Z = c₁x₁ + c₂x₂ + c₃x₃

s/c

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

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

a₃₁X₁ + a₃₂X₂ + a₃₃X₃ b₃

x₁ o, x₂ o, x₃ o

3.4.2.2. Forme mixte

Parfois, les contraintes sont tournées les unes dans un sens, les autres dans le sens opposé, l'objectif pouvant être soit un minimum, soit un maximum. Mais on peut également avoir un mélange d'égalité (=) ou inégalité ( ou ). Un tel programme est un programme mixte. On dit aussi qu'il se présente sous forme mixte.

Exemple

Max. Z = c₁x₁ + c₂x₂ + c₃x₃

s/c a₁₁x₁ + a₁₂x₂ + a₁₃x₃ b₁

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

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

x₁ o, x₂ o, x₃ o

3.4.2.3. Forme standard

Toutes les contraintes représentent des égalités. L'objectif pouvant être le maximum ou le minimum.

Exemple

Max. Z = c₁x₁ + c₂x₂ + c₃x₃

s/c a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + x₄ = b₁

a₂₁x₁ + a₂₃x₃ + x₅ = b₂

a₃₁x₁ + a₃₂x₂ + a₃₃x₃ + x₆ = b₃

x₁ o, x₂ o, x₃ o, x₄ 0, x₅ 0 , x₆ 0

Soulignons que dans la méthode simpliciale, tout programme se présentant sous forme canonique, doit être ramené sous la forme standard avec introduction de variables d'écart ou artificielles selon le cas et selon les règles bien précises.

3.4.3 Méthode matricielle

Un programme linéaire s'écrit min (max) z = c^Tx

s.c : Ax = b

x = 0

où c^T = (c₁,c₂..............c_n)

x₁ a₁₁ a₁₂....a_1n

x₂ a₂₁ a_22...... a_2n

x = . ; A = . .

. . .

x_n a_m1 a_m2....a_mn

b₁

b₂

b = .

.

b_m

Le système de contrainte Ax = b ; x = 0 nous donne l'ensemble de solutions réalisables ou admissibles du programme linéaire. Cet ensemble est un polygone ou polyèdre convexe. La méthode consiste à visiter les sommets de cet ensemble convexe de façon à améliorer progressivement la valeur de la fonction objectif. La valeur x* qui donne la meilleure valeur de la fonction économique est appelée solution optimale de ce programme linéaire.

Considérons :

A₁, A₂,......An les « n » colonnes de la matrice A (A = a_ij ). A_j est un vecteur colonne possédant m lignes.

Soit B = (A₁, A₂....A_m) la matrice carrée des colonnes correspondant aux variables de base et D = (A_m+1,.........A_n).

x₁ le vecteur des variables de base et,

.

Soit x_B = .

x_n

x_n+1 le vecteur des variables hors base.

x_N = .

.

x_n+m

x_B

alors x =

x_N

Ax = b peut s'écrire avec la nouvelle notion

X_B

B N = b

X_N

Ou encore BX_B + NX_N = b

Dans la base B, la solution correspondante est X_B

X_B s'obtient comme suit :

BX_B + NX_N = b

BX_B = b - NX_N

X_B = B^-1 (b - NX_N)

Comme X_N = 0 (car X_N = V.H.B)

X_B = B^-1.b

Rien ne nous prouve que cette solution est optimale. Après avoir déterminé une solution de base ; voyons maintenant les conditions d'optimalité.