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

3.5.3. Théorème applicable au dual

Deux théorèmes ont une importance considérable pour la programmation linéaire^42(*).

1. La valeur optimale de la fonction objectif du primal est toujours égale à la valeur optimale de la fonction objectif du dual, dès qu'une solution optimale accessible existe.

2. Si, dans la solution optimale accessible,

i. Une variable de décision du programme primal a une valeur autre que zéro, la variable d'écart correspondante du programme dual a nécessairement une valeur optimale égale à zéro ;

ii. Une variable d'écart du primal a une valeur autre que zéro, la variable de décision correspondante du programme dual a nécessairement une valeur optimale égale à zéro.

Pour illustrer ce théorème nous allons nous servir de l'exemple.

Soit minimiser M = g₁x₁ + g₂x₂ + g₃x₃

Sous contrainte a₁₁x₁ + a₁₂x₂ + a₁₃x₃ b₁ (1)

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

x₁, x₂, x₃ 0

Nous allons utiliser ci-dessous les théorèmes relatifs du dual pour trouver la valeur optimale (1) de la fonction objectif du primal et (2) des variables de décision du primal. Le programme dual s'écrit :

Maximiser F = z1b1 + z2b2

Sous contrainte

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

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

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

Supposons que les solutions optimales du second programme sont les suivantes :

Z₁ = k₁ k₁ différent de 0

Z₂ = k₂ k₁ différent de 0

M = F F différent de 0

Comme la valeur optimale du dual est égale à F, le premier théorème relatif au dual veut que M soit égal à F.

Pour trouver les valeurs optimales des variables de décision du primal, on transforme les inégalités des contraintes en équation par la soustraction de variables d'écart dans le primal (I) et par l'adjonction de variables d'écart dans le dual (II). Afin de distinguer les variables d'écart du primal et du dual, on note les premières s_i et les secondes t_i

(I) a₁₁x₁ + a₁₂x₂ + a₁₃x₃ - s₁ = b₁

a₂₁x₁ + a₂₂x₂ + a₂₃x₃ - s₂ = b₂

avec x_j : variable de décision

s_i : écarts

(ii) a₁₁z₁ + a₂₁z₂ + t₁ = g₁

a₁₂z₁ + a₂₂z₂ + t₂ = g₂

a₁₃z₁ + a₂₃z₂ + t₃ = g₃

avec z_j : variable de décision

t_i : écarts

Remplaçons z₁ par k₁ et z₂ par k₂ pour trouver t₁, t₂, t₃ :

a₁₁k₁ + a₂₁k₂ + t₁ = g₁ (1)

a₁₂k₁ + a₂₂k₂ + t₂ = g₂ (2)

a₁₃k₁ + a₂₃k₂ + t₃ = g₃ (3)

Supposons qu'en résolvant (1) t₁ = R₁ et que pour (2) et (3) t₂ = t₃ = 0

Comme les variables (t₂, t₃ ) de la deuxième et troisième contrainte du dual sont égales à zéro, le deuxième théorème relatif au dual veut que les variables de décision correspondante du primal (x₂, x₃) ne soient pas nulles. Mais comme t₁ différent de o, la variable de décision correspondante x₁ est égale à zéro. Par conséquent x₁ = o

Le deuxième théorème relatif au dual affirme que si les variables de décision optimales du dual (z₁,z₂) ne sont pas égales à zéro, les variables d'écart correspondantes du primal (s₁,s₂) sont nécessairement nulles. Remplaçons s₁ et s₂ par 0 et intégrons le fait que x₁ = 0 (I) se réduit à a₁₂x₂ + a₁₃x₃ = b₁, a₂₂x₂ + a₂₃x₃ = b₂. La résolution simultanée par la règle de cramer nous permettra de trouver les valeurs des variables de décision du primal.

3.5.4. Avantages du dual

Les rapports entre le primal et le dual qui viennent d'être exposés montrent qu'on peut trouver la valeur optimale de la fonction objectif aussi bien par le dual que par le primal. En raison de la relation de complémentarité qui existe entre les variables de décision d'un programme et les variables d'écart de l'autre, la solution d'un programme fournit aussi la solution complète de l'autre. C'est un avantage parce que :

1. on peut résoudre des problèmes de minimisation en terme de maximisation, ce qui est souvent plus facile

2. dans le cas de problèmes où le primal compte trois variables de décision, le dual est ramené à un programme comportant deux variables de décision.

* ⁴² EDOUARD, D. : Mathématique pour l'économiste, Mc Graw Hill, 2^ème édition, London, 1992, P. 348.