Analyse post-optimale de sensibilité

Contenus

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 post-optimale 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:

méthode du simplexe sensibility analysis analyse post-optimale de sensibilité primal

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.

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é.

méthode du simplexe sensibility analysis analyse de sensibilité primal

avec comme vecteur solution x* = (2,6). Attention ici la ligne montre la valeur de Z et pas de -Z (d’où les valeurs positives).

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 c_j 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 c_j, avec sur chacun d’eux une solution invariante.

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 c_j. Comportement logique et trivial puisque la fonction objectif est composé de la somme des c_j*x_j.

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

De même si c₁ passe de 3 à 2, seule la valeur de la fonction objectif sera modifiée. Pour calculer l’intervalle sur lequel le coefficient x*₁ 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 = c₁*x₁ + 5*x₂ et 2*x₂ = 12 donc -c₁/5 = 0, c₁ = 0;
z = c₁*x₁ + 5*x₂ et 3*x₁ + 2*x₂ = 18 donc -c₁/5 = -3/2, c₁ =15/2.

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

Lorsque le problème est de grande dimension, il est possible de calculer la variation du coût à l’aide du simplexe en ajouter un delta sur le coût à varier comme sur l’exemple suivant :

La solution reste optimal tant que la ligne du -Z a des nombres négatifs donc si :

É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 à u_i*d_i, donc proportionnelle à d_i.

Le coefficient de proportionnalité est appelé variation marginale ou coût dual ou profit marginal. Le coût dual u_i 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.

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

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*₁ est nulle : z’* – z* = y*₁ = 0.

Quand est-il de la diminution de b₁ ? 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.

Pour connaitre les possibilités d’évolution du stock sans changer la valeur de la solution optimale, il faut rajouter un delta dans le second membre étudié comme le montre l’exemple suivant :

La solution reste optimale tant que le simplexe n’est pas dégénéré, c’est à dire que le second membre est positif :

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

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

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*₃ de la valeur de la fonction objectif sur un intervalle b₃ comprit entre 12 et 24.

Étude 3 : variation des variables hors base

Le coût réduit de la variable hors base x_j, noté d_j, 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 d_j est l’opposé du coefficient de la variable dans la ligne objectif Z.

La solution optimale ne changera pas tant que le coût de la variable hors base ne sera pas meilleure que la valeur optimale de la fonction objectif (donc si le coefficient est entre -infini et Z pour un problème de maximisation).

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

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

Vérifions par le calcul : fixons x₃ à 1. Nous obtenons les trois inéquations suivantes : x₁ ≤ 3; 2*x₂ ≤ 10; 3*x₁ + 2*x₂ ≤ 15. Le vecteur (5/3, 5) est solution du système. Nous avons donc une évolution de x₁ de 5/3 – 2 = -1/3 et x₂ = 5 -6 = -1 dans la fonction objectif (nouvelle valeur – ancienne valeur). Son coût évolue donc de -1/3*c₁ – 1*c₂ + 1*c₃ = -2 (1*c₃ car nous passons d’une production de 0 à 1). Nous retrouvons bien la valeur du coût réduit de x₃.

Pour que x₃ devienne rentable, il faut que son coût augmente au moins de l’opposé de son coût réduit.

Étude 4 : variation de la production

Si la valeur a_ij change dans une contrainte saturée, alors ni la solution optimale ni la valeur optimal ne sont conservées.

Si la valeur a_ij change dans une contrainte non saturée et d’une variable en base, alors la valeur peut varié entre + ou – l’infini (en fonction d’un min ou max) à S_i/ x*_i. avec S_i la variable d’écart.

En effet en ajoutant une variable delta dans le coût de la variable en base de la contrainte visé alors il suffit d’injecter le vecteur optimal et résoudre l’équation comme dans l’exemple suivant :

Si la valeur a_ij change dans une contrainte quelconque et d’une variable hors base, alors seul une variation négative (dans le cas d’un max) peut rendre le produit viable dans cette contrainte. Il faut alors résoudre le simplexe en incorporant le delta et vérifier ses différents critères d’optimalité.