Problèmes de Minimisation et Problèmes Irréguliers - Cours de La Recherche Opérationnelle
COURS DE LA RECHERCHE OPÉRATIONNELLE
Cours Recherche Opérationnelle
Chapitre 1 : Formulation d’un programme linéaire (PL)I. Introduction
II. Les conditions de formulation d’un PL
III. Les étapes de formulation d’un PL
IV. Présentation Théorique
V. Exemples de formulations
Chapitre 2 : Résolution d’un programme linéaire (PL)
I. Introduction
II. Système d’axes
III. Représentation graphique des contraintes
IV. Représentation de la fonction objectif
V. Recherche de la solution optimale
a. Résolution graphique
b. Résolution par énumération :
VI. Exemples
VII. Analyse de sensibilité
Chapitre 3 :La Méthode de Simplexe
I. Introduction
II. Mise sous forme standard
III. Revue algébrique de la méthode du simplexe
IV. La méthode des tableaux
a. Tableau de simplexe initial
b. Amélioration de la solution
c. Calcul des tableaux suivants
V. Résumé de la procédure de la méthode du simplexe
VI. Exemple
Chapitre 4 : Problèmes de Minimisation et Problèmes Irréguliers
I. Introduction
II. Les variables artificielles
III. Les problèmes de minimisation
IV. Les problèmes irréguliers
a. Les problèmes impossibles
b. Les problèmes à solutions multiples
c. Les problèmes à solution infinie
d. Les problèmes à solution dégénérée
Chapitre 5 : Dualité et analyse de sensibilité
I. Introduction
II. Interprétation économique
III. Dualité
a. Définition
b. Propriétés et signification économique du programme dual
c. Tableau de correspondance primal-dual
III. Analyse de sensibilité
a. Analyse de sensibilité sur les Cj
b. Analyse de sensibilité sur les bj
c. Analyse de sensibilité sur les coefficients aij
IV. Introduction d’une nouvelle activité
a. Introduction d’une nouvelle variable de décision
b. Introduction d’une nouvelle contrainte
Chapitre 6 : Introduction à la Programmation Dynamique
I. Introduction
II. Exemple prototype. Le problème du voyageur
III. Caractéristiques d’un problème de programmation dynamique
IV. Programmation dynamique déterministe
a. Introduction
b. Problème du type plus court chemin
c. Répartition optimale des moyens
d. Résolution d'un programme linéaire
Problèmes de Minimisation et Problèmes Irréguliers
I. Introduction
Dans le chapitre précédent tous les programmes linéaires qu’on a traité sont du type : Maximiser une fonction linéaire sous contraintes de type inférieur ou égale (et avec un second membre positif).
Or dans beaucoup de problèmes réels, on peut retrouver des contraintes de type supérieur ou égale et/ou de type égale, ainsi que des problèmes où on a à minimiser au lieu de maximiser.
Dans ce chapitre, on étudiera les modifications à apporter à la méthode du simplexe pour qu’elle puisse résoudre tous ces types de programmes.
II. Les variables artificielles
Considérons le programme linéaire suivant :
Max 5x1 + 6x2
S.c -x1 + x2 ≤4
5x1 + 3x2 = 60
x2 ≥ 5
x1 ≥ 0 , x2 ≥ 0
L'introduction des variables d'écart dans le programme linéaire donne
Max 5x1 + 6x2 + 0S1 + 0S2
S.c -x1 + x2 + S1 = 4
5x1 + 3x2 = 60
x2 - S2 = 5
x1≥ 0 , x2≥ 0, S1≥ 0, S2≥ 0
Afin de générer une solution réalisable de base initiale pour la méthode de simplexe, on a annulé les variables de décision x1 et x2 . Ceci nous permet de commencer à partir de l’origine O. Or, on vérifie bien que l’origine n’est pas une solution réalisable. La question qui se pose est comment nous allons réécrire le programme de manière qu’on puisse construire le tableau de simplexe initial à l’origine.
Pour arriver à cette fin, on doit ressortir une astuce mathématique qui se résume à l’introduction de nouvelles variables, dite variables artificielles A1 et A2.
Ces variables n’ont aucune interprétation, comme leur nom l’indique, ils sont conçus artificiellement pour nous aider à utiliser la procédure de simplexe et à formuler le tableau initial à partir de l'origine.
Si on ajoute ces deux variables artificielles A1 et A2 respectivement à la 2ème et 3ème contrainte, le programme devient le suivant.
Max 5x1 + 6x2 +...
S.c -x1 + x2 + S1 = 4
5x1 + 3x2 + A1 = 60
x2 -S2 + A2 = 5
x1≥ 0, x2≥ 0, S1≥ 0, S2≥ 0 , a1 ≥ 0, a2≥ 0
Maintenant on peut obtenir une solution initiale de base du système d’équations, si on pose x1 = x2 = 0.
La solution initiale est
x1 = 0
x2 = 0
S1 = 4
S2 = 0
A1 = 60
A2 = 5
Cette solution n’est pas réalisable puisque x2 n’est pas supérieur à 50. Ainsi, il est important de distinguer entre une solution réellement réalisable et une solution du programme linéaire réécrit pour la procédure du simplexe. Certes, une solution réalisable du problème réel reste toujours une solution réalisable pour le programme linéaire transformé, le contraire n’est pas toujours vrai.
On peut conclure que tant que les variables artificielles restent dans la base, la solution demeure non réalisable réellement pour notre programme.
Une manière pour garantir que ces variables artificielles sortent de la base avant d’atteindre la solution optimale est de leur associée un grand coût -M dans la fonction objectif. Ainsi, si ces variables restent dans la base ils vont causer une diminution importante de la valeur de la fonction objectif. Ce qui nous contraignent à les faire sortir le plutôt possible de la base.
La fonction objectif s’écrit donc :
Max z = 5x1 + 6x2 - M A1 - M A2
avec M un très grand nombre (exemple: M ≥1010) .
En appliquant de ces modifications, le tableau de simplexe initial est
5
|
6
|
0
|
0
|
-M
|
-M
| |||
x1
|
X2
|
S1
|
S2
|
A1
|
A2
| |||
0
|
S1
|
4
|
-1
|
1
|
1
|
0
|
0
|
0
|
-M
|
A1
|
60
|
(5)
|
3
|
0
|
0
|
1
|
0
|
-M
|
A2
|
5
|
0
|
1
|
0
|
-1
|
0
|
1
|
De la même manière que précédemment essayons de retrouver la variable entrante te la variable sortante :
La variable entrante est x1 (5 +5M ≥ 6 + 4M avec M assez grand) et la variable sortante est A1 . Le tableau de simplexe qui suit est :
Le tableau de simplexe après la deuxième itération indique que la variable sortante est A2.
Remarque: Simplification du tableau
Les deux première itérations on fait sortir de la base les variables artificielles A1 et A2. Leurs effets nets est maintenant négatif et très élevé, elles ne pourront donc pas être sélectionnées à l’itération suivante, ni même ultérieurement comme on peut facilement le constater. Donc on peut supprimer du tableau la colonne relative à A1 et A2.
En appliquant la règle ci-dessus, on obtient le tableau de simplexe suivant :
5
|
6
|
0
|
0
| |||
x1
|
x2
|
S1
|
S2
| |||
0
|
S2
|
5
|
0
|
0
|
5/8
|
1
|
5
|
x1
|
6
|
1
|
0
|
-3/8
|
0
|
6
|
x2
|
10
|
0
|
1
|
5/8
|
0
|
5
|
6
|
15/8
|
0
| |||
0
|
0
|
-15/8
|
0
|
Le tableau ci-dessus est optimal car tous les effets nets sont négatifs ou nuls. Donc la solution optimale est :
x1 = 6
x2 = 10
S1 = 0
S2 = 5
Remarque: cas où le second membre négatif
Le problème qui peut se poser est que l’une des variables du second membre soit négative. Par exemple supposons que lors de la formulation on trouve une contrainte de ce type :
x1 - x2 ≥ -4
La condition qu’il faut vérifier avant de se lancer dans la réécriture de cette contrainte, en vue de construire le programme standard, est la nonégativité du second membre.
Ainsi, on doit modifier la contrainte avant de commencer la standardisation et la réécrire comme suit :
-x1 + x2 ≤ 4
Exercice :
Réécrire convenablement ces contraintes:
(1) x1 + 3x2 - 5x3 = - 20
(2) -x1 + 3x2 ≥ - 5
(3) 5x1 - 2x2 ≤ - 10
III. Les problèmes de minimisation
Il y a deux manières de résoudre un problème de minimisation en utilisant la méthode de simplexe.
La première méthode nécessite le changement de la règle de choix de la variable entrante. Dans un problème de maximisation la règle est de choisir comme variable entrante celle qui a le plus grand effet net positif non nul. Ceci parce que notre objectif est de choisir la variable qui en entrant dans la base va engendrer un profit supplémentaire et ainsi accroître la valeur de la fonction objectif. Pour un problème de minimisation, on va utiliser la règle inverse. C’est-à-dire la variable entrante est celle à laquelle on associe la plus petite valeur négative non nulle de l’effet net cj - zj.
Ceci va nous amener aussi à changer notre règle d’arrêt de la procédure de simplexe et de définir le tableau optimal, comme celui où tous les effets nets
cj - zj sont positifs ou nuls.
cj - zj sont positifs ou nuls.
Essayons d’appliquer la méthode de simplexe sur le problème de médecine : Min x1 + x2
Sc 2x1 + x2 ≥ 12
5x1 + 8x2 ≥ 74
x1 + 6x2 ≥ 24
x1 ≥ 0 , x2 ≥ 0
Pour permettre à la méthode de simplexe de démarrer de l’origine, il faut comme on l’a déjà vu dans le cas de problème de maximisation, introduire les variables artificielles.
Avec les problèmes de maximisation on attribue à ces variables un coefficient
-M dans la fonction objectif pour les contraindre à quitter la base rapidement. Dans le cas de problèmes de minimisation, on a intérêt à changer le coefficient de ces variables en M (M très grand) afin d’arriver au même résultat et de les faire sortir de la base.
-M dans la fonction objectif pour les contraindre à quitter la base rapidement. Dans le cas de problèmes de minimisation, on a intérêt à changer le coefficient de ces variables en M (M très grand) afin d’arriver au même résultat et de les faire sortir de la base.
Avant de construire le tableau de simplexe initial, on réécrit le programme linéaire relatif au problème de médecine avec les variables artificielles.
Min x1 + x2 + MA1 + MA2+ MA3
Sc 2x1 + x2 - S1 + A1 = 12
5x1 + 8x2 - S2 + A2 = 74
x1 + 6x2 - S3 + A3 = 24
x1 , x2 , S1 , S2 , S3 , A1 , A2 ≥ 0
Le tableau de simplexe initial est :
Après 4 itérations, on trouve le tableau de simplexe optimal suivant :
5
|
6
|
0
|
0
|
0
| |||
x1
|
x2
|
S1
|
S2
|
S3
| |||
1
|
x1
|
8
|
1
|
0
|
-8/11
|
1/11
|
0
|
0
|
S3
|
26
|
0
|
0
|
2
|
-1
|
1
|
1
|
x2
|
2
|
0
|
1
|
5/11
|
-2/11
|
0
|
1
|
1
|
-3/11
|
-1/11
|
0
| |||
0
|
0
|
3/11
|
1/11
|
0
|
On retrouve la même solution obtenue par la méthode graphique :
x1 = 8
x2 = 2
S1 = 0
S2 = 0
S3 = 26
Z = 10
Après avoir vérifier que le second membre des contraintes est positif, le tableau suivant résume les transformations à faire subir à notre programme linéaire avant de le résoudre par la méthode de simplexe :
Quand la contrainte est
|
Pour la fonction objectif d’un problème de
| |
Maximisation | Minimisation | |
Ajouter une variable d’écart
|
Attribuer un coefficient nul pour la variable d’écart
| |
II- de type « = » Ajouter une variable d’écart et une variable artificielle
|
Attribuer un coefficient -M pour variable artificielle
|
Attribuer un coefficient M pour la variable artificielle
|
III- de type « ≥ »
Ajouter une variable artificielle et une variable d’écart avec un signe "-"
|
Attribuer un coefficient nul pour la variable d’écart et un coefficient - M pour variable
artificielle
|
Attribuer un coefficient nul pour la variable d’écart et un coefficient M pour variable artificielle
|
Le tableau suivant résume les étapes de la méthodes de simplexe relatif aux problèmes de maximisation et minimisation :
Etape
|
Maximisation
|
Minimisation
|
1
|
Formuler un programme linéaire pour le problème réel.
|
Formuler un programme linéaire pour le problème réel.
|
2
|
Vérifier que le second membre du programme linéaire est positif sinon modifier les contraintes
|
Vérifier que le second membre du programme linéaire est positif sinon modifier les contraintes
|
3
|
Ecrire le programme linéaire sous une forme standard
|
Ecrire le programme linéaire sous une forme standard
|
4
|
Construire le premier tableau de simplexe
|
Construire le premier tableau de simplexe
|
5
|
Choisir comme variable entrante dans la base celle qui admet le plus grand effet net positif cj-zj.
|
Choisir comme variable entrante dans la base celle qui admet le plus petit effet net négatif cj-zj.
|
6
|
Choisir la variable sortante de la base celle qui admet le plus petit ratio supérieur à zéro.
|
Choisir la variable sortante de la base celle qui admet le plus petit ratio supérieur à zéro.
|
7
|
Construire le nouveau tableau en utilisant la règle de pivot
|
Construire le nouveau tableau en utilisant la règle de pivot
|
8
|
Faire le test d’optimalité. Si
(cj-zj) ≤ 0 pour toutes les variables (hors base) donc la solution obtenue est optimale. Sinon retourner à l’étape 5. |
Faire le test d’optimalité. Si
(cj-zj) ≥ 0 pour toutes les variables (hors base) donc la solution obtenue est optimale. Sinon retourner à l’étape 5. |
La deuxième méthode pour résoudre un problème de se base sur le résultat suivant « Résoudre un problème min ctx sujet à un ensemble de contraintes est équivalent à résoudre un problème max -ctx sujet au même ensemble de contraintes ». Ces deux problèmes sont équivalents dans la mesure où ils donnent le même vecteur des solutions optimales. La seule différence est que la valeur de la solution max -ctx est l’opposé de la solution de min ctx; (i.e. min ctx = - max -ctx).
Donc pour résoudre le programme linéaire relatif au problème de médecine, on peut résoudre le problème de maximisation suivant:
Max - x1 - x2
S.c. 2x1 + x2 ≥ 12
5x1 + 8x2 ≥74
x1 + 6x2 ≥ 24
x1 , x2 ≥ 0
On peut vérifier facilement que la méthode de simplexe appliquée au programme ci-dessus, engendre le même vecteur de solutions optimales.
IV. Les problèmes irréguliers
Après avoir examiner comment on peut résoudre un programme linéaire par la méthode de simplexe, on s’intéresse dans cette section aux problèmes irréguliers, qu'on peut rencontrer lors de la résolution d’un programme linéaire par la méthode de simplexe. Donc, l’objet de cette section est de reconnaître ces problèmes et de les résoudre par la méthode de simplexe.a. Les problèmes impossibles
Graphiquement, on a caractérisé ces problèmes par un ensemble de solutions réalisables vide. Avec la méthode de simplexe, on reconnaît que le problème est impossible si une ou plusieurs variables artificielles sont présentes dans la base dans le tableau de simplexe optimal, ce qui signifie que la solution donnée par ce tableau n’est pas réellement réalisable.
Exemple:
Vérifions à l’aide de la méthode de simplexe, que le problème suivant est réellement impossible :
Max 4 x1 + 3x2
Sc x1 + x2 ≤ 2
3x1 + x2 ≥ 10
x1 , x2 ≥ 0
En introduisant les variables d’écarts et les variables artificielles le programme s’écrit:
Max 4x1 + 3x2 - MA1
Sc x1 + x2 - S1 = 2
3x1 + x2 - S2 + a1 = 10
x1 , x2 , S1 , S2 , A1 ≥ 0
4
|
3
|
0
|
0
|
-M
| |||
x1
|
x2
|
S1
|
S2
|
a1
| |||
4
|
x1
|
2
|
1
|
1
|
1
|
0
|
0
|
-M
|
a1
|
5
|
0
|
-2
|
-3
|
-1
|
1
|
4
|
4+2M
|
1+3M
|
M
|
-M
| |||
0
|
-1-2M
|
-1-3M
|
-M
|
0
|
Le tableau de simplexe ci-dessus est optimal avec une variable artificielle dans la base.
Remarque : Un programme de maximisation ou de minimisation avec seulement des contraintes de type « ≤ » ne peut pas être impossible (sous l’hypothèse que le second membre b est positif). Ceci est dû au fait que lors de la résolution de ce genre de programme par la méthode de simplexe on n'utilise pas des variables artificielles. Donc il est impossible de les retrouver dans la solution optimale.
b.Les problèmes à solutions multiples
Graphiquement, ce problème est caractérisé par le fait que la pente de la droite représentant la fonction objectif (z = 0) est égale à la pente de l’une des contraintes restrictives. Lorsqu’on utilise la méthode de simplexe, on identifie ce problème lorsqu’un des effets nets (relatif à une variable hors base) est nul. L’exemple de la section 3 du précédent chapitre représente un problème avec solutions multiples.c. Les problèmes à solution infinie
Graphiquement, ce problème est caractérisé par le fait qu’on peut déplacer la droite de la fonction objectif indéfiniment de manière à accroître la valeur, en gardant toujours une intersection non vide avec l’ensemble des solutions réalisables.
Avec la méthode de simplexe, on reconnaît ce problème lorsque la variable entrante n’admet aucune limite sur sa valeur d’entrée, c’est à dire que tous les ratios Qi/aijo sont négatifs ou nuls.
Exemple
Max x1 + 2x2
Sc x1 + x2 ≥ 2
x2 ≤ 3
x1 , x2 ≥ 0
On introduit les variables d’écart et les variables artificielles, le programme linéaire devient :
Max x1 + 2x2 + 0S1 + 0S2 - Ma1
Sc x1 + x2 - S1 + a1 = 2
x2 + S2 = 3
x1 , x2 , S1 , S2 , a1 ≥ 0
Les tableaux de simplexe sont :
1
|
2
|
0
|
0
| ||||
x1
|
x2
|
S1
|
S2
| ||||
2
|
x2
|
3
|
0
|
1
|
0
|
1
|
∞
|
0
|
S1
|
1
|
-1
|
0
|
1
|
1
|
-1
|
0
|
2
|
0
|
2
| ||||
1
|
0
|
0
|
-2
|
Le dernier tableau montre que la variable x1 n’admet aucune limite sur sa valeur de sortie.
d. Les problèmes à solution dégénérée
Graphiquement, on appelle solution dégénérée le point où plusieurs contraintes concourent (un nombre supérieur ou égale à trois contraintes). Un programme linéaire est dit dégénérée si une ou plusieurs variables dans la base optimale sont nulles. Dans la résolution graphique ce problème n’est pas difficile à résoudre, mais avec la méthode de simplexe il peut causer des difficultés.
Exemple
Max z = 2x1 + 0 x2 + 3/2 x3
s.c. x1 - x2 ≤ 2
2x1 + x3 ≤ 4
x1 + x2 + x3 ≤ 3
x1, x2, x3 ≥ 0
La solution optimale de ce problème est :
x1 = 1
x2 = 0
x3 = 2
z = 5
La forme standard du programme linéaire est
Max 2x1 + 0 x2 + 3/2x3 + 0 S1 + 0 S2 + 0 S3
Sc x1 - x2 + S1 = 2
2x1 + x3 + S2 = 4
x1 + x2 + x3 + S3 = 3
x1, x2, x3, S1, S2, S3 ≥ 0
Le tableau de simplexe initial est :
La variable entrante est x1, mais les deux premières contraintes donnent la même valeur minimale du ratio. Ceci indique que lorsque x1 passe à 2, les variables d’écart S1 et S2 vont s’annuler malgré que l’un des deux demeure encore dans la base.
Choisissons arbitrairement de faire sortir de la base la variable d’écart S1.
La nouvelle solution réalisable de base est :
x1 = 0
x2 = 0
x3= 1
S1 = 2
S2 = 0
S3 = 0
et la valeur de la fonction objectif z = 4. Cette solution de base est dite dégénérée. Continuons les itérations relatives à la méthode de simplexe. La variable entrante est x2.
Le problème est qu’un des ratios est nul ce qui indique qu’on ne peut pas augmenter la valeur de x2 puisque la valeur de la fonction objectif ne va pas augmenter et reste égale à 4.
Si on réitère une autre fois, en remplaçant S2 par x2 dans la base on obtient :
2
|
0
|
3/2
|
0
|
0
|
0
| ||||
x1
|
x2
|
x3
|
S1
|
S2
|
S3
| ||||
2
|
x1
|
2
|
1
|
0
|
1/2
|
0
|
1/2
|
0
|
4
|
0
|
x2
|
0
|
0
|
1
|
1/2
|
-1
|
1/2
|
0
|
0
|
0
|
S3
|
1
|
0
|
0
|
0
|
1
|
-1
|
1
|
∞
|
2
|
0
|
0
|
0
|
1
|
0
| ||||
0
|
0
|
1/2
|
0
|
-1
|
0
|
↑
Ce tableau n’est pas optimal, la variable entrante est x3 et la variable sortante est x2. On remarque aussi que ce passage d’une solution à une autre ne s’accompagne pas d’une augmentation de la valeur de la fonction objectif.
On peut facilement vérifier que nous somme en train de cycler sans atteindre la solution optimale. Ce genre de cyclage dans la méthode de simplexe est dangereux et on doit l’identifier avant de commencer à résoudre le problème, sinon on passera un temps énorme sans atteindre la solution optimale.
Pour terminer cette section, il faut noter que ce n'est pas tout problème de dégénérescence qui peut conduire à un cyclage.
Exemple
Max 10 x1 + 9x2
Sc 7/10x1 + x2 ≤ 630
1/2 x1 +5/6x2 ≤ 480
x1 + 2/3x2 ≤ 708
1/10 x1 +1/4x2 ≤ 135
x1 ,, x2 ≥ 0
Essayer de résoudre ce programme par la méthode de simplexe (choisir en cas de deux quotients égaux, celui qui se trouve dans la ligne supérieure).
Commentaires
Enregistrer un commentaire