Simplexe variantes algo -Programmation linaire

Simplexe variantes algo -Programmation linaire - Recherche o

Télécharger PDF

Variantes de l'algorithme du simplexe

Les deux phases du simplexe

Pour initialiser l’algorithme du simplexe, il faut disposer d’une base réalisable initiale.

Cependant, une telle solution de base initiale n’est pas toujours évidente. De plus, en général, nous ne savons même pas si le domaine réalisable n’est pas vide.

La phase I du simplexe a pour objectifs :

D'indiquer si le problème est réalisable (c'est-à-dire, si son domaine n’est pas vide).
Si oui, de fournir l’information nécessaire pour générer une solution réalisable initiale.

Cas simple

Dans un cas simple de problème de programmation linéaire, l'introduction de variables d'écart peut immédiatement fournir une base réalisable initiale.

Problème du restaurateur transformé

Pour le problème du restaurateur, nous transformons les contraintes d’inégalité en égalité en introduisant des variables d’écart (u, p, h). Par exemple, une contrainte comme 5x + 3y ≤ 30 devient 5x + 3y + u = 30, avec u ≥ 0.

L'objectif économique de ce problème est généralement de minimiser une fonction de coût.

Cas plus compliqué

Dans certains problèmes, notamment ceux avec des contraintes de type "supérieur ou égal" (≥) ou des égalités, les variables d'écart seules ne suffisent pas à former une base réalisable initiale, car leurs valeurs pourraient être négatives si les termes de droite sont négatifs, violant ainsi les conditions de non-négativité.

Cas général et variables artificielles

Dans le cas général où le problème de programmation linéaire est sous la forme standard, et qu'une base réalisable initiale n'est pas directement disponible, on construit un problème auxiliaire.

Pour cela, nous introduisons des variables artificielles t₁, t₂, ..., t_m, une pour chaque contrainte où une variable de base initiale est manquante. Ces variables permettent de créer une solution de base réalisable pour le problème auxiliaire.

Les contraintes modifiées prennent la forme où chaque contrainte est augmentée d'une variable artificielle, par exemple :

b₁ = a₁₁x₁ + ... + a_1nx_n + t₁
...
b_m = a_m1x₁ + ... + a_mnx_n + t_m

Toutes les variables (x_j et t_i) doivent être non négatives. Les variables artificielles t₁, ..., t_m forment alors une base réalisable initiale pour ce système quand les variables originales sont nulles.

Problème artificiel

Le problème artificiel de la phase I est formulé en remplaçant la fonction économique originale par une nouvelle fonction d’objectif qui vise à minimiser la somme des variables artificielles : min w = t₁ + t₂ + ... + t_m.

L'objectif est de s'assurer que toutes les variables artificielles sont nulles à la fin de la phase I, indiquant que le problème original est réalisable.

Problème artificiel équivalent

Pour résoudre le problème artificiel avec l’algorithme du simplexe, il est souvent nécessaire de le transformer pour que la fonction objectif w soit exprimée uniquement en fonction des variables non basiques. Cela se fait en soustrayant chacune des contraintes de la fonction objectif.

Résolution du problème de la phase I

Ce problème est résolu à l’aide de l’algorithme du simplexe. Les variables artificielles fournissent une solution de base initiale immédiate, car elles peuvent prendre des valeurs non négatives lorsque les variables du problème original sont fixées à zéro.

Le problème artificiel est toujours borné inférieurement par 0 (w ≥ 0), car les variables artificielles sont non négatives.

Résultat de la phase I

À la fin de la phase I, l'algorithme du simplexe permet de tirer les conclusions suivantes :

Si la valeur optimale min w de la fonction économique du problème artificiel est positive (min w > 0), alors le domaine réalisable du problème original est vide. Cela signifie que le problème original n'est pas réalisable.
Si la valeur optimale min w de la fonction économique du problème artificiel est nulle (min w = 0), alors le domaine réalisable du problème original n’est pas vide. Dans ce cas, il existe une solution réalisable du problème de la phase I où toutes les variables artificielles sont égales à 0. Les valeurs des variables originales correspondantes constituent une solution de base réalisable pour le problème original.

Cette conclusion est démontrable : si le problème original est réalisable, il existe une solution où toutes les variables artificielles peuvent être nulles, résultant en un min w = 0.

Solution initiale pour poursuivre la phase II

Lorsque la valeur minimale de w est égale à 0, nous pouvons passer à la phase II. Nous utilisons l'information contenue dans le tableau du simplexe de la dernière itération de la phase I pour construire une base réalisable initiale pour le problème original.

Deux scénarios principaux doivent être considérés.

Cas 1: Aucune variable artificielle n'est variable de base

Si à la fin de la phase I, aucune variable artificielle n'est dans la base, toutes les variables de base sont des variables originales (x_j). Pour continuer avec le problème original, on élimine les colonnes des variables artificielles du tableau et on remplace la dernière ligne par la fonction économique du problème original. Les coûts relatifs des variables de base sont alors ajustés à 0.

Cas 2: Certaines variables artificielles sont des variables de base

Si une variable artificielle t_k demeure dans la base à la fin de la phase I, étant donné que min w = 0, sa valeur doit être 0 dans la solution optimale. Cette situation se produit généralement lorsque la contrainte associée à t_k a un terme de droite b_i égal à 0.

Deux sous-cas sont possibles pour gérer ces variables artificielles dans la base :

Si la ligne de la variable artificielle t_k contient un coefficient non nul (a_ij ≠ 0) pour une variable originale x_j qui n'est pas de base, on peut effectuer une opération de pivot sur cet élément. Cela remplace t_k par x_j dans la base sans modifier la valeur de la fonction objectif (qui reste 0).
Si tous les coefficients des variables originales dans la ligne de la variable artificielle t_k sont nuls (∀j, a_ij = 0), cela indique que la contrainte correspondante est redondante. Elle peut être exprimée comme une combinaison linéaire des autres contraintes. Dans ce cas, cette ligne (et la variable artificielle) peut être éliminée du tableau sans altérer le domaine réalisable.

Après avoir traité toutes les lignes où des variables artificielles sont de base, on obtient un tableau où aucune variable artificielle ne fait partie de la base, ce qui nous ramène au Cas 1.

Notion de multiplicateurs du simplexe

La dernière ligne du tableau du simplexe à l'optimum contient les coûts relatifs des variables. Les multiplicateurs du simplexe, souvent représentés par le vecteur π, sont directement liés à ces coûts.

Le vecteur des multiplicateurs du simplexe (π) est un vecteur de dimension égale au nombre de contraintes (m). Il permet de calculer les coûts relatifs à partir des données originales du problème.

Chaque composante π_i du vecteur des multiplicateurs peut être interprétée comme un "poids" associé à la contrainte i. Ces poids sont tels que, en soustrayant une combinaison linéaire des lignes de contraintes pondérées par ces π_i de la ligne de la fonction objectif, les coûts relatifs des variables de base deviennent nuls.

Illustration avec le problème du restaurateur

Dans l'illustration du problème du restaurateur, la solution optimale est x = 3 et y = 5, résultant en une valeur de z = -54. Le vecteur des multiplicateurs optimaux est π^T = [-3/2, 0, -1/2].

Sensibilité de la valeur optimale aux modifications des termes de droite

Les multiplicateurs du simplexe associés à une base optimale sont des outils précieux pour l'analyse de sensibilité. Ils permettent de quantifier l’impact des changements dans les termes de droite (b_i) des contraintes sur la valeur optimale du problème.

Si nous considérons une modification (∆b) des termes de droite du problème original (b + ∆b), et si la base optimale B* du problème original demeure réalisable pour le nouveau problème, alors B* reste une base optimale.

La nouvelle valeur optimale (z'*) peut être calculée comme z'* = z* + Σ π_i * ∆b_i. Chaque multiplicateur π_i représente le taux unitaire de changement de la valeur optimale lorsque le terme de droite de la contrainte i est modifié d’une unité, à condition que la base optimale courante reste valide.

Domaine réalisable et résolution graphique

Considérons le problème du restaurateur avec ses contraintes :

5x + 3y ≤ 30 (b₁=30)
2x + 3y ≤ 24 (b₂=24)
1x + 3y ≤ 18 (b₃=18)
x, y ≥ 0

La fonction économique est z = –8x – 6y. La solution optimale est x = 3 et y = 5, avec z = –54. Le vecteur des multiplicateurs optimaux est π^T = [–3/2, 0, –1/2].

Analysons l'effet des modifications des termes de droite (b_i) :

Si b₁ (30) devient b₁ + ∆b₁ :
- Si ∆b₁ < 0, le domaine réalisable diminue.
- Si ∆b₁ > 0, le domaine réalisable augmente.
- La variation de la valeur optimale z* sera (-3/2) * ∆b₁.
Si b₂ (24) devient b₂ + ∆b₂ :
- Si ∆b₂ < 0, le domaine réalisable diminue.
- Si ∆b₂ > 0, le domaine réalisable augmente.
- La variation de z* sera (0) * ∆b₂. Un changement de b₂ n'affecte pas la valeur optimale tant que la base reste la même.
Si b₃ (18) devient b₃ + ∆b₃ :
- Si ∆b₃ < 0, le domaine réalisable diminue.
- Si ∆b₃ > 0, le domaine réalisable augmente.
- La variation de z* sera (-1/2) * ∆b₃.

Foire aux questions (FAQ)

Qu'est-ce que la phase I de l'algorithme du simplexe et à quoi sert-elle ?

La phase I de l'algorithme du simplexe est une étape préliminaire cruciale pour résoudre les problèmes de programmation linéaire. Son objectif principal est de trouver une solution de base réalisable initiale et de déterminer si le problème original possède un domaine réalisable non vide. Si la phase I conclut qu'il n'existe pas de solution réalisable, le problème est considéré comme irréalisable.

Quand utilise-t-on des variables artificielles dans l'algorithme du simplexe ?

Les variables artificielles sont introduites dans l'algorithme du simplexe lorsque le problème de programmation linéaire ne dispose pas d'une solution de base réalisable initiale évidente. C'est typiquement le cas pour les contraintes d'égalité ou les contraintes de type "supérieur ou égal" (≥) après leur transformation en égalités, où il manque une variable de base naturelle. Elles servent à construire un problème auxiliaire de phase I avec une base initiale claire.

Que représentent les multiplicateurs du simplexe en analyse de sensibilité ?

Les multiplicateurs du simplexe, également connus sous le nom de prix duaux ou prix marginaux, quantifient l'impact sur la valeur optimale de la fonction objectif d'une modification unitaire du terme de droite (la ressource ou la contrainte) d'une contrainte spécifique. Ils indiquent le taux de variation de la valeur optimale par rapport à cette modification, en supposant que la structure de la solution (la base optimale) reste inchangée. Ils sont essentiels pour comprendre les implications économiques des changements de ressources.