Analyse post-optimale de sensibilité

Lorsque la solution de base optimale du problème de PL est analysée pour répondre aux questions relatives aux changements dans sa formulation, l’étude porte le nom d’ analyse de sensibilité.

On appelle post-optimisation l’ensemble des techniques permettant d’obtenir l’optimum du problème de PL lorsque certaines données ont subi des modifications.

On considère le problème de programmation linéaire général sous sa forme stand art:

LP

Cette étude peut être motivée par plusieurs raisons :

  • les données du problème ne sont pas connues avec exactitude, auquel cas il est important de déterminer dans quelle mesure cela affecte la solution proposée;
  • on souhaite évaluer les conséquences d’un changement de politique qui modifierait les données du problème.
Ce cours ne donnera pas d’explication mathématique formelle. Les coûts marginaux, réduits et l’analyse de sensibilité peuvent être obtenus par de nombreux logiciels lors de la résolution du simplexe. Nous donnerons seulement des exemples afin d’en comprendre l’utilité.

Coûts marginaux

On appelle coût marginal d’un bien l’augmentation minimale de dépenses, par rapport à la solution optimale, qui résulterait de l’utilisation d’une unité supplémentaire de ce bien, lorsque le problème posé consiste à produire des biens au moindre coût.

Si le problème posé consiste à transformer des biens pour vendre une production avec un meilleur profit et l’augmentation maximale de revenu qui résulte de la possibilité de disposer d’une unité supplémentaire de l’un des biens, est la valeur marginale de ce bien. Très souvent, on emploie également dans ce cas le qualificatif coût marginal.

Les coûts marginaux y* sont donc les effets nets associés aux variables d’écart, puisque ce sont ces variables qui déterminent les excédents (ou les insuffisances) de biens. Il s’agit des valeurs des variables dans la ligne Z.

Si une variable d’écart n’est pas nulle, dans la solution optimale, c’est que le bien correspondant est déjà excédentaire. Par conséquent, le fait de disposer d’une unité supplémentaire de ce bien n’aura aucune influence sur le revenu. La variable d’écart a une valeur marginale nulle.

Par contre, si une variable d’écart est nulle dans la solution optimale, c’est que le bien correspondant est totalement utilisé. Par la suite une variation de la disponibilité aura généralement une influence sur le revenu. C’est pourquoi cette variable d’écart nul dans la solution optimale à une valeur marginale non nulle, et cette valeur marginale précise la variation de la fonction économique résultant de l’utilisation d’une unité supplémentaire du bien associé.

simplexe3

avec comme vecteur solution x* = (2,6).

On peut mesurer la sensibilité de la solution optimale à un changement d’un terme de droite ou d’un coefficient dans l’objectif.

Étude 1 : variation dans la fonction objectif

On souhaite examiner comment la solution optimale varie lorsque le coefficient d’une des variables dans la fonction objectif varie. Modifier les cj revient à modifier la pente de la fonction objectif.

La variation d’un coefficient dans la fonction objectif sur un certain intervalle n’entraîne pas de modification de la solution optimale. En dehors de cet intervalle, on a une nouvelle solution qui reste elle-même optimale sur un autre intervalle. On peut ainsi mettre en évidence un nombre fini d’intervalles de variation pour cj, avec sur chacun d’eux une solution invariante.

LP2

La valeur de la j-ème variable à l’optimum x*j mesure l’augmentation de la fonction objectif si l’on accroît d’une unité le coût unitaire cj. Comportement logique et trivial puisque la fonction objectif est composé de la somme des cj*xj.

Changeons la fonction objectif par max z’ =4*x1 + 5*x2. La valeur de la fonction objectif évoluera de x*1 = 2, tandis que le vecteur solution ne sera pas modifiée comme le montre la résolution graphique :

simplexe6

De même si c1 passe de 3 à 2, seule la valeur de la fonction objectif sera modifiée. Pour calculer l’intervalle sur lequel le coefficient x*1 est valide, nous devons faire évoluer la fonction objectif jusqu’à ce qu’elle soit parallèle aux autres contraintes.

C’est-à-dire quand la pente de la fonction objectif est égale à la pente des contraintes saturées pour le vecteur solution s* :

  • z = c1*x1 + 5*x2 et 2*x2 = 12 donc -c1/5 = 0, c1 = 0;
  • z = c1*x1 + 5*x2 et 3*x1 + 2*x2 = 18 donc -c1/5 = -3/2, c1 =15/2.

Le coefficient x*1 est donc valide pour c1 compris entre 0 et 15/2.

Étude 2 : variation dans le second membre

Lorsque le second membre d’une contrainte varie (dans un certain intervalle), si cette contrainte n’était pas saturée, alors la solution ne change pas et la valeur optimale de la fonction objectif non plus. Ce résultat est évident puisque la solution optimale ne vérifiant pas avec égalité la contrainte, on peut faire varier (un peu) le second membre sans « toucher » à la solution optimale.

En revanche, si la contrainte était vérifiée avec égalité à l’optimum, on dispose d’un intervalle de variation pour le second membre tel que :

  • La solution change mais les variables nulles restent nulles et les variables non nulles restent non nulles : la structure de la solution ne change pas.
  • La variation du second membre i entraîne une variation de la valeur optimale de la fonction objectif égale à ui*di, donc proportionnelle à di.
Le coefficient de proportionnalité est appelé variation marginale ou coût dual ou profit marginal. Le coût dual ui est égal à la variation de la valeur optimale de la fonction objectif lorsque le second membre augmente d’une unité.

Si on sort de l’intervalle, on a un nouveau coût dual. On peut ainsi mettre en évidence un nombre fini d’intervalles de variation pour le second membre avec, sur chacun d’eux, une valeur pour le coût dual.  Sur les différents intervalles, l’analyse de sensibilité ne donne pas la solution optimale puisque les valeurs numériques des variables dépendent de la valeur exacte du second membre.

LP3

Considérons dans l’exemple que b1 =4 devient b’1 = 5. Effectuons une résolution graphique du nouveau problème :

simplexe4

L’évolution de ce second membre n’a pas modifié la solution optimale, la valeur de la fonction objectif ne change pas. Il était facile de prédire ce changement car le coût marginal de la variable d’écart y*1 est nulle : z’* – z* = y*1 = 0.

Quand est-il de la diminution de b1 ? Comme l’explication sur les coûts marginaux l’explique, la diminution de 1 du second membre entraîne une diminution de la valeur de la fonction objectif d’un montant égal au coût marginal. Donc la diminution de 1 n’entraînera pas de modification.

L’augmentation et la diminution ne modifient pas la valeur de la fonction objectif sur un petit intervalle, mais si b1 est inférieur à 2, nous voyons sur la résolution graphique que la solution optimale sera modifiée. L’intervalle de validité de y*1 =0 est donc pour b1 entre 2 et l’infini.

Considérons maintenant une augmentation du troisième second membre à b’3 = 19. Puisque le coût marginal n’est pas nul, la solution optimale sera modifiée comme le montre la résolution graphique.

simplexe5

Nous pouvons donc interpréter le coût marginal par : la diminution ou la perte d’une unité du troisième second membre entraînera une évolution de y*3 de la valeur de la fonction objectif sur un intervalle b3 comprit entre 12 et 24.

Étude 3 : variation des variables hors base

Le coût réduit de la variable hors base xj, noté dj, mesure l’augmentation de la fonction objectif si l’on accroît d’une unité la valeur de la variable hors base. Le coût réduit dj est l’opposé du coefficient de la variable dans la ligne objectif.

Reprenons l’exemple précédent avec une nouvelle contrainte et une nouvelle variable :

simplexe7

Nous avons le coût réduit suivant : d3 = -2. Cela signifie que de construire une unité de x3  diminuerait la valeur de la fonction objectif de 2 (puisqu’elle est hors base x*3 = 0).

Vérifions par le calcul : fixons x3 à 1. Nous obtenons les trois inéquations suivantes : x1 ≤ 3; 2*x2 ≤ 10; 3*x1 + 2*x2 ≤ 15. Le vecteur (5/3, 5) est solution du système. Nous avons donc une évolution de x1 de 5/3 – 2 = -1/3 et x2 = 5 -6 = -1 dans la fonction objectif (nouvelle valeur – ancienne valeur). Son coût évolue donc de -1/3*c1 – 1*c2 + 1*c3 = -2 (1*c3 car nous passons d’une production de 0 à 1). Nous retrouvons bien la valeur du coût réduit de x3.
Pour que x3 devienne rentable, il faut que son coût augmente au moins de l’opposé de son coût réduit.
Publicités