chapitre

Recherche opérationnelle 1 Plan du cours Chapitre I : Introduction à la programmation linéaire ............................................................................... 2 Série 1 : Corrigés des exercices n° 1 à 2 et 5.......................................................................................... 4 Chapitre II : Résolution d’un PL par la méthode graphique ....................................................................... 9 Série 2 : Corrigés d’exercices ............................................................................................................... 20 Chapitre III : Résolution d’un PL par la méthode dite du « Simplexe ».................................................... 24 Série 3 : Corrigés d’exercices ............................................................................................................... 30 Chapitre IV : Méthode du Simplexe : Problème de minimisation et problème irrégulier.......................... 39 Chapitre V : Dualité......................................................................................................................................... Chapitre VI : Ordonnancement .......................................................................................................................... T.P. : Programme de résolution d’un PL : L.I.N.D.O......................................................................................... Recherche opérationnelle 2 R e c h e r c h e o p é r a t i o n n e l l e 18 CHAPITRE 1 Introduction à la programmation linéaire 02 20 05 I – I n t r o d u c t i o n La programmation linéaire est une classe de modèles mathématiques d’optimisation qui a pour objet la maximisation ou minimisation d’une fonction linéaire de variables ( appelée fonction objectifs soumise à des contraintes (équations ou inéquations ). Le terme « programmation » indique le fait que c’est un problème d’optimisation qui, du point de vue économique, concerne l’allocation efficace des rares ressources à certaines activités en vue de maximiser ( ou minimiser ) un certain objectif. Le terme « linéaire » indique que les relations mathématiques qui lient ces activités aux variables sont linéaires. L’une des décisions les plus fréquentes d’un gestionnaire est l’allocation des ressources entre des activités données en vue d’un objectif déterminé : La minimisation des coûts, la maximisation des profits où l’optimisation d’un critère quelconque de performance constitue l’une des préoccupations urgentes du chef d’entreprise surtout que ce dernier dispose de ressources limitées en matières premières, main d’œuvre et fonds. Donc, la programmation linéaire fournit au décideur une méthode pour la recherche des solutions optimales à ces problèmes d’allocation. I I – F o r m u l a t i o n d ’ u n m o d è l e d e d é c i s i o n 1 – Caractéristiques d’un programme linéaire (PL) Un PL est caractérisé par : A – Sa fonction économique ou fonction objectif ou fonction linéaire notée Z : Z = C1x1 + C2x2 + … + Cnxn x1,x2, …, xn = Variables Remarque : Si c’est un profit, on parle alors de maximiser Z. S’il s’agit de coûts, l’on parle alors de minimiser Z tout en respectant les contraintes. B – Des inconnues (x1,x2, …, xn) ou variables de décision. indépendantes dont on cherche les valeurs. C – Des contraintes qui doivent vérifier ces inconnues qui prennent la forme d’égalités ou inégalités. 2 – Formulation d’un PL Un menuisier fabrique des portes et des chaises. Quel est l’objectif du menuisier ? ⇒ Sa fonction objectif : Maximiser le profit. Recherche opérationnelle 3 Ce menuisier est soumis à des contraintes. On a : Z = C1x1+C2x2 Avec : x1 = la quantité produite de tables. x2 = la quantité produite de chaises. C1 = Prix de vente des tables. C2 = Prix de vente des chaises. Il est à noter que le profit unitaire généré par la vente d’une table est de 2D. Le profit unitaire généré par la vente d’une chaise est de 3D. D’où : Z = 2x1 +3x2 Supposons que : - 1 unité produite de tables nécessite 2 unités d’heures de main d’œuvre et 3 unités de matières premières. - 1 unité produite de chaises nécessite 4 unités d’heures de main d’œuvre et 2 unités de matières premières. - Le menuisier dispose de 120 heures de main d’œuvre et de 140 unités de matières premières. Disposer les données en tableau ! HM = Heures de main d’œuvre. MP = Matière première. ΠU = Profit unitaire (Π - pi – pour profit ). Le programme linéaire s’écrit sous la forme : Max Z = 2 x1 +3 x2 Sous les contraintes : 2x1 + 4x2 ≤ 120 3x1 +2x2 ≤ 240 avec toujours x1 ≥ 0 et x2 ≥ 0 . La formulation initiale d’un programme linéaire donne en général un problème sous la forme générale qui est : Max ou Min Z = C1x1 + C2x2+ … + Cnxn = ∑ = n i ii xC 1 S/C a11x1 + a12x2 + … + a1nxn ≥ b1 1er type . ≤ bi 2ème type . = bi 3ème type an1x1 + an2x2 + … + annxn Exemple de formulation Dans une raffinerie, on fait la distillation de 2 types de pétrole B1 et B2 pour déterminer 3 qualités d’essences E1, E2 et E3. La raffinerie doit approvisionner un distributeur d’essence. La distillation de 100 litres de B1 fournit 10 litres de E1, 10 litres de E2 et 20 litres de E3 alors que la distillation de la même quantité de B2 fournit 50 litres de E1, 40 litres de E2 et 20 litres de E3. La raffinerie doit satisfaire une commande de 500 litres de E1, 400 litres de E2 et 600 litres de E3. Sachant que les coûts par m3 sont de 20 d pour B1 et de 25 D pour B2, formulez le PL qui minimise le coût des quantités des bruts utilisés pour la satisfaction de la demande. x1 x2 Disposition HM 2 4 120 MP 3 2 240 ΠU 2 3 Recherche opérationnelle 4 R e c h e r c h e o p é r a t i o n n e l l e 19 CHAPITRE 1 Correction d’exercices de la série n°1 02 20 05 Rappels : Les étapes de la formulation d’un PL sont : c Fonction objectif : Max ou Min Z = C1x1 + C2x2+ … + Cnxn = ∑ = n i ii xC 1 d Variables de décision : xj e Contraintes : a11x1 + a12x2 + … + a1nxn ≥ b1 1er type . ≤ bi 2ème type . = bi 3ème type an1x1 + an2x2 + … + anmxn Remarque : Les contraintes forment un système matriciel : A X = b . C o r r i g é d e l ’ e x e r c i c e n ° 1 c Fonction objectif : Minimiser les coûts des quantités de brut. Zmin = C1x1 + C2x2 d Variables de décision : x1 : Quantité de brut de B1. x2 : Quantité de brut de B2. e Contraintes : Contraintes de satisfaction des commandes. D’où le PL suivant : Min Z = 20x1 + 25x2 C S 10 x1 + 50 x2 ≥ 500 10 x1 + 40 x2 ≥ 400 20 x1 + 20 x1 ≥ 600 avec x1 et x2 ≥ 0 C o r r i g é d e l ’ e x e r c i c e n ° 2 c Fonction objectif : Maximiser le profit max Π d Variables de décision : Quantités produites d’interrupteurs de type A : x1 Π Quantités produites d’interrupteurs de type B :x2 e Contraintes : La production est limitée par : a) 1re contrainte : Le temps de travail T = nombre d’heures de travail disponibles t1 = nombre d’heures nécessaires pour fabriquer un interrupteur de type A. Recherche opérationnelle 5 t2 = nombre d’heures nécessaires pour fabriquer un interrupteur de type B. T = t1 x1 + t2 x2 ≤ T T1 = 2 t2 Si x1 = 0 , on fabrique le maximum de B c’.à.d. x2 = 1000. Nous avons = t2 x2 = T 1000 t2 = T D’où : 2 t2 x1 + t2 x2 ≤ 1000 t2 2 x1 + x2 ≤ 1000 b) 2ème contrainte : L’isolant disponible x1 + x2 ≤ 600 c) 3ème contrainte : La quantité de fil de laiton x1 ≤ 400 x2 ≤ 700 D’où le PL suivant : Max Π = 0,4 x1 + 0,3 x2 C S 2 x1 + x2 ≤ 1000 x1 + x2 ≤ 600 x1 ≤ 400 x2 ≤ 700 avec x1 et x2 ≥ 0 C o r r i g é d e l ’ e x e r c i c e n ° 5 xi = nombre de chauffeurs qui commencent le travail au début de la période i de 2 heures. Pour avoir ai pendant la période i, on essaie de définir les contraintes par période : Période c : x1 + x2 + x3 + x4 + x5 + x6 + x7 +x8 + x9 + x10 +x11 + x12 ≥ a1 x1 + x10 + x11 + x12 ≥ a1 Période d : x1 + x2 + x11 + x12 ≥ a2 Période e : x1 + x2 + x3 + x12 ≥ a3 Période f : x1 + x2 + x3 + x4 ≥ a4 Périodes 5 à 12 : xk-3 + xk-2 + xk-1 +xk ≥ ak Exemple pour la période g : x2 + x3 + x4 + x5 Recherche opérationnelle 6 R e c h e r c h e o p é r a t i o n n e l l e 26 CHAPITRE 1 Introduction à la programmation linéaire 02 20 05 3 – La formulation algébrique d’un programme linéaire A – Forme générale G Et Forme standard S La formulation initiale d’un programme linéaire donne en général un problème sous une forme générale qui est la suivante : Forme générale G Max ou Min Z = C1x1 + C2x2+ … + Cnxn = ∑ = n j jj xC 1 C S a11x1 + a12x2 + … + a1nxn ≥ b1 1er type . ≤ bi 2ème type . = bi 3ème type an1x1 + an2x2 + … + anmxn Les variables de décision sont x1, x2, …, xn et la fonction économique à optimiser est représentée par Z. Les paramètres Cij, bi et aij sont des constantes connues d’avance. Trois types de contraintes sont généralement présentes : ≥ , ≤ ou = . Il y a aussi deux catégories de variables de décision : Certaines sont supposées ne prendre que des valeurs non négatives alors que d’autres peuvent prendre toute valeur réelle. Un PL sous forme générale (G) peut être transformé en un PL équivalent sous forme standard notée A ou S. Max Z = ∑ = n j jj xC 1 < - > Max Z = C1x1 + C2x2+ … + Cnxn C S ∑ jij xa ≤ bi xj ≥ 0 < - > a11x1 + a12x2 + … + a1nxn ≤ b1 a21x1 + a22x2 + … + a2nxn ≤ b2 ................................................ ................................................ ................................................ an1x1 + an2x2 + … + annxn ≤ bn La forme générale (G) se caractérise par le fait que c’est un problème où toutes les contraintes sont du type ≤ et les variables de décision sont non négatives. Sa forme standard (S) est : Max Z = ∑ jj xC C S ∑ jij xa = bi Recherche opérationnelle 7 xj ≥ 0 La forme standard se caractérise par des contraintes sous forme d’équations (égalité = ). B – Passage de la forme générale à la forme standard Un certain nombre de transformations algébriques permettent le passage de la forme générale à la forme standard : B1 – Si le problème consiste à minimiser Z Min Z = ∑ = n j jj xC 1 , on doit changer le sens d’optimisation i.e : Min Z = ∑ = n j jj xC 1 Max Z = ∑ = − n j jj xC 1 )( B2 – Si le sens d’inégalité des contraintes est de type supérieur ou égal ≥, l’on doit changer le sens d’inégalité (≤) : ∑ jij xa ≥ bi ∑ − jij xa )( ≤ -bi B3 – Si les contraintes sont de type (=), on doit convertir l’égalité en inégalité : ∑ jij xa = bi ∑ jij xa ≥ bi ⎪⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ ≤ ≤−⇔≥ ∑ ∑∑ b b- )( b i i jij ijijjij xa xaxa et B4 – Convertir une inégalité en égalité en introduisant des variables d’écart : ∑ jij xa ≤ bi ∑ jij xa + Si = bi ∑ jij xa ≥ bi ∑ jij xa - Si = bi Remarque : Les variables d’écart n’apportent aucune contribution à la fonction objectif. B5 – Dans le cas où les variables de décision sont libres ou sans contrainte de signe, l’on doit remplacer la variable xj par 2 variables non négatives. En d’autres termes, si xj est libre, on introduit : xj+ et xJ- ≥ 0 telles que : xj = xj+ - xJ- Quelques définitions et rappels Un PL sous forme standard (S) peut être écrit sous une forme matricielle en utilisant la notation suivante : Recherche opérationnelle 8 A = Matrice des coefficients techniques (aij) ⎟⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ = nmnn m m aaa aaa aaa A .... .. .. .. .. .... .... 21 22221 11211 C = Matrice des cj X = matrice des xi ⎟⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ = nc c c C .. . . . 2 1 ⎟⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ = nx x x X .. . . . 2 1 Pour avoir Max Z : Max Z = C’ X -- C’ est une matrice transposée de C tC. C S AX =b x ≥ 0 Une solution possible au PL est un vecteur X qui satisfait les contraintes AX = b. Recherche opérationnelle 9 R e c h e r c h e o p é r a t i o n n e l l e 26 CHAPITRE 2 Résolution d’un PL Méthode graphique 02 20 05 L’objet principal de ce chapitre est de proposer une méthode de résolution d’un problème linéaire ne comportant que 2 variables de décision. La méthode consiste en la délimitation de l’intersection des demi-plans représentant les inéquations des contraintes et en la recherche dans ce domaine des points donnant l’optimum de la fonction objectif. I D é f i n i t i o n s 1 - Solution possible non réalisable Elle respecte le principe de la non négativité et se trouve en dehors du polyèdre. Autrement dit, elle ne vérifie pas les contraintes fonctionnelles. 2 – Solution possible et réalisable Elle se trouve à l’intérieur du polyèdre. Autrement dit, elle vérifie toutes les contraintes ( contraintes fonctionnelles et contraintes de signe ). 3 – Solution réalisable de base ( notée SRB ) C’est un point extrême, sommet ou point extrémal du polyèdre : 4 – Solution réalisable non optimale C’est un point quelconque du domaine se trouvant à l’intérieur du polyèdre. 5 – Solution optimale C’est une solution réalisable de base maximisant la valeur de Z ( lorsque l’optimisation est une maximisation). Elle est obtenue en déplaçant la droite z vers le haut parallèlement à elle-même (même pente = même coefficient directeur de la droite : y = a x -- a est la pente, le coefficient directeur ) jusqu’au dernier contact avec un point extrême du polyèdre. A B C D Recherche opérationnelle 10 I I – R e c h e r c h e d e l a s o l u t i o n o p t i m a l e La recherche de l’optimum à l’aide de la méthode graphique ne peut s’appliquer aux problèmes de + de 2 variables de décision. La méthode graphique présente l’avantage d’être simple et permet l’illustration de certains principes de base pour une méthode plus générale ( méthode du Simplexe ). 1 – Représentation graphique des contraintes fonctionnelles Dans la région des solutions possibles, on se propose de déterminer l’ensemble des solutions réalisables c’.à.d. qui vérifient simultanément toutes les contraintes fonctionnelles. Pour cela, il nous faut d’abord connaître l’ensemble des points qui respectent chacune de ces contraintes, chaque contrainte fonctionnelle étant en relation linéaire correspond à un seul demi-plan limité par la droite qui représente cette contrainte au sens de l’égalité. La connaissance des demi-plans qui respectent la contrainte résulte d’une simple évaluation d’un point quelconque non situé sur la droite. Dans la pratique, on utilise le point origine de coordonnées (0,0). L’intersection des demi-plans constitue le polyèdre convexe : C’est le domaine des possibilités, domaine de disponibilité, polygone des contraintes. 2 - Recherche de la solution optimale Sachant que la droite qui correspond au profit Max doit traverser le domaine des solutions réalisables et qu’un déplacement vers le haut de cette droite fait croître la valeur de Z, le dernier point touché, le plus éloigné de l’origine correspond à la solution optimale. Remarque : A l’origine, x1 = 0 x2 = 0 Z = 0 T.A.F. : Comment représenter la droite de la fonction objectif ? Max Z = C1 x1 + C2 + x2 x C C C Zx 2 1 2 2 −= 2 1 2 1 2 C Zx C Cx +−= Constante1 2 1 2 +−= xC Cx En général, On fixe Z = 0, nous avons un premier point O de coordonnées ( 0,0 ), nous savons que par 2 points passe une droite, il suffit de déterminer un deuxième point : ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ =+−==Δ 0 : 0 2 1 2 1 2 C Znbx C Cxz O( 0,0 ) A( ?, ? ). ΔZ : Courbe de niveau Il suffit de représenter ΔZ pour le 1er niveau qui correspond à Z/C2 = 0 Z = 0 Recherche opérationnelle 11 3 – Solutions optimales : Différents cas possibles 1er cas : Pas de solution, le polyèdre est vide. 2ème cas : Il y a une solution unique optimale, elle se situe toujours à un sommet du polygone. 3ème cas : La solution optimale se situe sur un côté du polygone. Dans ce cas, la pente de la fonction objectif (Z) est identique à celle de la droite qui porte ce côté, plusieurs solutions optimales existent et fournissent le même gain. 4ème cas : Solutions infinies : La solution optimale se trouve rejetée à l’infini. -5 -4 -3 -2 -1 0 1 2 3 4 5 -5 -4 -3 -2 -1 1 2 3 4 5 Recherche opérationnelle 12 Exemple applicatif : soit le PL suivant : Max Z = 25 x1 + 15 x2 C S 2 x1 +2 x2 ≤ 240 3 x1 + x2 ≤ 140 x1 ≥ 0 et x2 ≥ 0 T.A.F. : Résoudre graphiquement ce PL ! Corrigé : 1re étape : Représentation des droites des contraintes Δ1 = 2 x1 + 2 x2 = 240 ⇔ x2 = 120 –x1 -- A(0,120) B(120,0) Δ2 = 3 x1 + x2 = 140 ⇔ x2 = 140 – 3 x1 -- C(0,140) D(40,20) 2ème étape : Représentation de la droite de la fonction objectif Z A B C D E Recherche opérationnelle 13 ΔZ = x2 = 1 2 1 x C C− ΔZ = x2 = 115 25 x− ΔZ = x2 = 13 5 x− -- O(0,0) E(120,-200) ⇒ La solution optimale est le point B. B = Δ1 ∩ Δ2 3ème étape : Déterminer les coordonnées de B ⇔ Résoudre le système suivant : ⎩⎨ ⎧ =+ =+ 1403 24022 21 21 xx xx et par substitution l’on a : ⎩⎨ ⎧ = =⇔ ⎩⎨ ⎧ = −= ⎩⎨ ⎧ =−+ −= 10x 110x 10 120x 1401203 120 1 2 1 12 11 12 x x xx xx d’où B(10,110) d’où Z* = 1900 Recherche opérationnelle 14 R e c h e r c h e o p é r a t i o n n e l l e 05 CHAPITRE 2 Résolution d’un PL Méthode graphique 03 20 05 Exemple applicatif n°2 : soit le PL suivant : Min Z = 24 x1 + 20 x2 C S x1 + x2 ≥ 30 x1 + 2 x2 ≥ 40 x1 ≥ 0 et x2 ≥ 0 T.A.F. : Résoudre graphiquement ce PL ! Corrigé : 1re étape : Représentation des droites des contraintes Δ1 = x1 + x2 = 30 ⇔ x2 = 30 –x1 -- A(0,30) B(30,0) Δ2 = x1 + 2 x2 = 40 ⇔ x2 = 20 – ½ x1 -- C(0,20) D(40,0) 2ème étape : Représentation de la droite de la fonction objectif Z ΔZ = x2 = 1 2 1 x C C− ΔZ = x2 = 120 24 x− ΔZ = x2 = 15 6 x− -- O(0,0) E(5,-6) Pour un problème de minimisation, on fait descendre la courbe ΔZ ⇒ le 1er point touché par ΔZ est alors le point D (40,0) = dernier point touché ⇔ 24 * 40 + 20 * 0 = 960 ⇒ Z* = 960. A B C D O E Recherche opérationnelle 15 Ce problème de minimisation ne diffère de celui de la maximisation que par la recherche des courbes de niveau qui donne la plus petite valeur de la fonction objectif tout en satisfaisant toutes les contraintes. Graphiquement, on déplace la droite de la fonction objectif parallèlement à elle-même à l’intérieur du domaine des possibilités. La fonction objectif diminue de valeur à mesure qu’on se rapproche de l’origine des axes. Cela correspond à l’optimum puisqu’il s’agit d’un point de minimisation. Différentes solutions possibles d’un PL par la méthode graphique 1er cas : Problème impossible Min Z = 3 x1 + 2 x2 C S x1 + 2 x2 ≤ 2 2 x1 + 4 x2 ≥ 8 x1 ≥ 0 et x2 ≥ 0 Soient Δ1 = x1 + 2 x2 = 2 ⇔ x2 = 1 – ½ x1 -- A(0,1) B(2,0) Δ2 = 2 x1 + 4 x2 = 8 ⇔ x2 2 – ½ x1 -- C(0,2) D(4,0) ΔZ = - 2 3− x1 -- O(0,0) E(2,-3) L’espace des solutions réalisables est vide ; c’est un problème impossible. 2ème cas : Problème à solutions multiples Max Z = x1 + 3 x2 C S 2 x1 + 6 x2 ≤ 30 x1 ≤ 10 x2 ≤ 4 x1 ≥ 0 et x2 ≥ 0 Soient Δ1 = 2 x1 + 6 x2 = 30 ⇔ x2 = 12 3 15 2 630 x x −⇔− -- A(0,5) B(3,4) Δ2 = x1 = 10 ⇔ Δ3 =x2 = 4 ΔZ = - 3 1− x1 -- O(0,0) E(3,-1) -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 -2 -1 1 2 3 4 5 6 A B Recherche opérationnelle 16 L’ensemble des points décrits par le segment [B,D] représente les solutions optimales du PL. C’est un problème à solutions multiples : D = Δ1 ∩ Δ2 ⇔ )4,3(4 3 4 3 154 4 3 15 2 1 2 1 2 12 D x x x x x xx ⇒ ⎩⎨ ⎧ = =⇔ ⎪⎩ ⎪⎨ ⎧ = −=⇔ ⎪⎩ ⎪⎨ ⎧ = −= ⇒ Z* = 15. 3ème cas : Problème avec solutions non-bornées Max Z = -2 x1 + 3 x2 C S x1 ≤ 5 2 x1 –3 x2 ≤ 6 x1 ≥ 0 et x2 ≥0 Soient : Δ1 = 5 Δ2 = x2 = -2 + 3 2 x1 -- A(0,-2) B(3,0) ΔZ = x2 = 3 2 x1 -- O(0,0) C(3,2) ⇒ On peut augmenter la valeur de la fonction objectif indéfiniment ( déplacement de ΔZ vers le haut ). Donc, la solution est non bornée. 4ème cas : Problème de dégénérescence Max Z = x1 +x2 C S 3 x1 + 2 x2 ≤ 40 x1 ≤ 10 x2 ≤ 5 x1 ≥ 0 et x2 ≥ 0 Soient : Δ1 =3 x1 + 2 x2 = 40 ⇔ x2 = 121 2 320 2 340 xx x −=⇔− -- A(0,20) B((20,-10) Δ2 = x1 = 10 Δ3 = x2 = 5 ΔZ = x2 = - x1 -- O(0,0) C(20,-20) La solution optimale B(10,5) est dite dégénérée si trois contraintes concourent en ce point. -1 0 1 2 3 4 5 6 -3 -2 -1 1 2 3 4 5 A B C 0 A B C Recherche opérationnelle 17 Exemple applicatif n°1 Max Z = 100 x1 + 200 x2 C S x1 + x2 ≤ 150 4 x1 +2 x2 ≤ 440 x1 + 4x2 ≤ 480 x1 ≤ 90 x1 ≥ 0 et x2 ≥ 0 Corrigé Soient les droites suivantes : Δ1 = x1 +x2 =150 ⇔ x2=150 – x1 -- A(0,150) B(150,0) Δ2 = 4 x1 + 2 x2=440 ⇔ x2 = 220 –2 x1 -- C(0,220) D(110,0) Δ3 = x1 +4 x2 = 480 ⇔ x2 = 120 –14 x1 -- E(0,120) F(480,0) Δ4 = x1 =90 ΔZ =-100200 x1 ⇔ -1 2 x1 -- O(0,0) G(220,-110) H est la solution optimale. H= Δ1 ∩ Δ3 ⇔ ⎩⎨ ⎧ x1 +x2 = 150 c x1 +4 x2 = 480 d ⇔ c - d = 330 ⇔ x2 = 110 x1 = 150-110 ⇒ x1 = 40 ⇒ H(40,110) � * = 40 * 100+110 * 200= 26000 � * = 26000 Recherche opérationnelle 18 Exemple applicatif n°2 Max Z = 30 x + 70 y C S 4 x + 10 y ≤ 80 14 x +8 y ≤ 112 x + y ≤ 10 x ≥ 0 et y ≥ 0 Exemple applicatif n°3 Max Z = 8 x + 2 y C S 2 x -6 y ≤ 12 5 x +4 y ≤ 40 x + 2 y ≥ 12 y ≤ 6 x ≥ 0 et y ≥ 0 Corrigé Soient les droites suivantes : Δ1 = 2 x – 6 y = 12 ⇔ y= 2 x – 12 6 ⇔ y = 1 3 x -2 -- A(0,-2) B(6,0) Δ2 = 5 x + 4 y = 40 ⇔ 10 –54x -- C(0,10) D(8,0) Δ3 = x + 2 y =12 ⇔ y = 6 –12x -- E(0,6) F(12,0) Δ4 = y = 6 ΔZ = y = –4 x -- O(0,0) G(1,-4) -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 -5 -4 -3 -2 -1 1 2 3 4 5 6 7 8 9 10 11 A B C D E F H Recherche opérationnelle 19 La solution optimale est le point J = Δ2 ∩ Δ3 ⇒ Le système suivant est donc à résoudre : ⎩⎨ ⎧x + 2 y =12 c 5 x + 4 y = 40 ⇔ ⎩⎨ ⎧2 x + 4 y = 24 5 x + 4 y = 40 ⇔ 3 x = 16 ⇒ x = 16 3 et y = 10 3 � * = 8 * 163 + 2 * 10 3 ⇔ � * = 1283 + 20 3 = 148 3 ⇒ � * = 1483 . Recherche opérationnelle 20 R e c h e r c h e o p é r a t i o n n e l l e 12 CHAPITRE 2 Correction des exercices de la série n°2 03 20 05 E x e r c i c e n ° 1 Fonction Objectif : Max Π = 100 x1 +200 x2 Variables de décision : x1 : Surface allouée à la culture des tomates. x2 : Surface allouée à la culture des piments. Contraintes : Main d’œuvre : x1 + 4 x2 ≤ 480 Eau : 4 x1 +2 x2 ≤ 440 Surface de terrain : x1 +x2 ≤ 150 Limitation du bureau du périmètre irrigué : x1 ≤ 90 Avec x1 ≥ 0 et x2 ≥ 0 Résolution : Voir exemple applicatif n° 1 du 052 2005. E x e r c i c e n ° 2 Fonction objectif : Minimiser le nombre de pilules à prescrire. Variables de décision : x1 = Nombre de pilules de petite taille. x2 = Nombre de pilules de grande taille. Contraintes : Au moins 12 graines d’aspirine 2 x1 +x2 ≥ 12 Au moins 74 grains de bicarbonate 5 x1 + 8 x2 ≥ 74 Au moins 24 grains de codéine x1 +6 x2 ≥ 24 Recherche opérationnelle 21 Résolution graphique Soient : Δ1 = 2 x1 + x2 = 12 ⇔ x2=12-2 x1 -- A(0,12) B(6,0) Δ2 = 5 x1 + 8x2 =74 ⇔ =374 – 5 8 x1 -- C(2,8) D(10,3) Δ3 = x1 + 6 x2 =24 ⇔ x2= 4 –16 x1 -- (E(0,4) F(12,2) ΔZ = x2= -x1 -- O(0,0) G(2,-2) Le point C(2,8) constitue la solution optimale, d’où � * = 10. E x e r c i c e n ° 3 Fonction objectif: Max Π = 900 x1 + 1000 x2 Variables de décision: x1 : nombre d’unités du produit P1 x2 : nombre d’unités du produit P2 A B C D E F G Recherche opérationnelle 22 Contraintes : Contraintes de temps 11 x1 + 9 x2 ≤ 9900 7 x1 + 12 x2 ≤ 8400 6 x1 + 16 x2 ≤ 9600 avec x1 ≥ 0 et x2 ≥ 0 Résolution Δ2 = 11 x1 + 9 x2 = 9900 ⇔ x2=1100 - -119 x1 A(0,1100) B(900,0) Δ2 = 7 x1 + 12 x2 = 8400 ⇔ x2=700 – 712 x1 C(0,700) D(1200,0) Δ3 = 6 x1 + 16 x2 = 9600 ⇔ x2= 600 –38 x1 E(0,600) F(1600,0) ΔZ = x2 = - 910 x1 O(0,0) G(1000,-900) La solution optimale est H = Δ3 ∩ Δ2 Recherche opérationnelle 23 ⇒ ⎩⎨ ⎧7 x1 + 12 x2 = 8400 c 6 x1 + 16 x2 = 9600d ⇒ 34 (6 x1 + 16 x2 ) = 9600 * 3 4 ⇒ ⎩⎪ ⎨⎪ ⎧ 7 x1 +12 x2 = 8400 92 x1 +12 x2 = 7200 ⇒ 52 x1 = 1200 ⇒ x1 = 1200 * 2 5 = 480 x2 = 420 d’où � * = 900 * 480 + 1000 * 420= 852000 ⇒ Z* = 852000 Recherche opérationnelle 24 R e c h e r c h e o p é r a t i o n n e l l e 12 CHAPITRE 3 La méthode du « Simplexe » 03 20 05 I - I n t r o d u c t i o n On a présenté dans le chapitre précédent une procédure graphique pour résoudre un PL à 2 variables. Par contre, dans la plupart des problèmes réels, on a plus de 2 variables à déterminer. Une procédure algébriques pour résoudre les PL avec plus de 2 variables fera l’objet de ce chapitre. C’est la méthode du « Simplexe ». Une implémentation de cette procédure a permis de résoudre des PL avec un peu plus de quelques milliers de variables. Le programme LINDO qu’on présentera supporte au plus 200 variables et 100 contraintes. Dans ce chapitre, la méthode du Simplexe est présentée pour les problèmes de la forme : Max tC x C S A x ≥ b x ≥ 0 et en utilisant le problème de l’agriculteur (cf. Série n°2, ex n°1) : Max Z = 100 x1 + 200 x2 C S x1 + x2 ≤ 150 4 x1 +2 x2 ≤ 440 x1 + 4x2 ≤ 480 x1 ≤ 90 x1 ≥ 0 et x2 ≥ 0 I I – M i s e s o u s f o r m e s t a n d a r d La mise sous forme standard consiste à introduire des variables supplémentaires ( 1 pour chaque contrainte ) de manière à réécrire les inégalités ( ≤ ) sous la forme d’égalités. Chacune de ces variables représente le nombre de ressources non utilisées. On les appelle “variables d’écart”. La forme générale s’écrit donc : Max C1x1 + C2x2+ … + Cnxn C S a11x1 + a12x2 + … + a1nxn ≤ b1 a21x1 + a22x2 + … + a2nxn ≤ b2 ................................................ ................................................ ................................................ an1x1 + an2x2 + … + annxn ≤ bn Recherche opérationnelle 25 La forme standard serait alors : Max C1x1 + C2x2+ … + Cnxn + 0 S1 + 0 S2 + … + 0 Sn C S a11x1 + a12x2 + … + a1nxn + S1 = b1 a21x1 + a22x2 + … + a2nxn + S2 = b2 ......................................................................................... ......................................................................................... ......................................................................................... an1x1 + an2x2 + … + anmxn Sm = bm Exemple : La forme standard du problème de l’agriculteur est : Max Z = 100 x1 + 200 x2 + 0 S1 + 0 S2 + 0 S3 + 0 S4 c C S x1 + x2 + S1 = 150 d 4 x1 + 2 x2 + S2 = 440 e x1 + 4 x2 + S3 = 480 f x1 + S4 = 90 g x1 ≥ 0, x2 ≥ 0, S1 ≥ 0, S2 ≥ 0, S3 ≥ 0 et S4 ≥ 0 h I I I – R e v u e a l g é b r i q u e d e l a m é t h o d e d u S i m p l e x e La question qui se pose est : Que demande-t-on d’une procédure algébrique? En premier lieu, on note que les contraintes du problème forment un système de 4 équations et 6 variables Or, il y a un nombre infini de solutions à ce système. Une procédure algébrique pour la résolution d’un PL doit être capable de retrouver les solutions des systèmes d’équations où il y a plus de varibales que de contraintes. En deuxième lieu, on peut noter que ce nesont pas toutes les solutions qui vérifient toutes les contraintes qui sont solutions au PL; ils doivent en plus satisfaire les contraintes de non négativité. Ainsi, un procédure algébrique doit être capable d’éliminer de l’ensemeble des solutions qui satisfait les contraintes celles qui n’arrivent pas à satisfaire les contraintes de non négativité. Finalement, une procédure algébrique pour résoudre lesPL doit être en mesure de choisir parmi lesoslutions réalisables celles qui maximisent la fonction objectif. La méthode du Simplexe est une procédure algébriquee qui tient compte de ces 3 considérations. Pour illustrer cette procédure, supposons que x2 = 0 et S1 = 0 : On a x2=S1 =0 D’où le système suivant : ⎩⎨ ⎧ X1= 1504 x1 + S2 = 440 x1 + S3 =480 x1 + S4 =90 D’où les solutions suivantes : x1 = 150 x2 = 0 S1 = 0 S2 = -160 S3 = 330 Recherche opérationnelle 26 S4 = -60 Les variables x1, S2, S3 et S4 , non nulles, sont dites « variables de base » ( notées VB ) et les variables S1 et x2, nulles, sont dites « variables hors base » ( notées VHB). Généralement, si on a un PL standard constitué de n variables et m contraintes avec n ≥ m, alors une solution de base ( c’est un extrême ) est obtenue en annulant n-m variables et en résolvant les m contraintes pour déterminer les valeurs des autres m variables. On note qu’une solution de base n’est pas toujours réalisable. C’est le cas de la solution qu’on vient de trouver. Une solution réalisable de base serait celle où : ⎩⎨ ⎧x1=x2=0 xj = 0 ⇔ ⎩⎨ ⎧S1 = 150S2 = 440 S3 =480 S4 = 90 Cette solution correspond à un point extrêm de l’ensmeble des solutions réalisables qui est l’origine O. Pour la méthode du Simplexe, une SRBi ( i.e. solution réalisable de base initiale ) est demandée. Une telle solution peut être retrouvée en annulant toutes les variables de décision ( ce qui correspond dans la méthode graphique au point d’origine O ). Apartir de ce point, la méthode du Simplexe va générer successivement des solutions réalisables de base pour notre système d’équations en s’assurant que la valeur de la fonction objectif est en train d’augmenter jusqu’à localiser la solution optimale du problème qui est un point extrême de l’espace des solutions réalisables, donc une solution réalisable de base. Ainsi, on peut décrire la méthode du Simplexe comme étant une procédure itérative qui passe de la SRBi à une autre solution réalisablede base jusqu’à atteindre la solution optimale. Recherche opérationnelle 27 R e c h e r c h e o p é r a t i o n n e l l e 19 CHAPITRE 3 La méthode du « Simplexe » 03 20 05 R a p p e l s PL de l’agriculteur : Forme générale Forme standard Max Z = 100 x1 + 200 x2 C S x1 + x2 ≤ 150 4 x1 +2 x2 ≤ 440 x1 + 4x2 ≤ 480 x1 ≤ 90 x1 ≥ 0 et x2 ≥ 0 Max Z = 100 x1 + 200 x2 + 0 S1 + 0 S2 + 0 S3 + 0 S4 C S x1 + x2 = 150 4 x1 +2 x2 = 440 x1 + 4x2 = 480 x1 = 90 x1 , x2 ≥ 0 et S1 , S2 , S3 , S4 ≥ 0 SRBi x1=x2=0 Π = 0 S1 = 150 S2 = 440 S3 = 480 S4 = 90 I V - L a m é t h o d e d u S i m p l e x e A – Tableau du Simplexe initial ( à l’origine ) Cj 100 200 0 0 0 0 Ci VB Qi x1 x2 S1 S2 S3 S4 Ri 0 S1 150 1 1 1 0 0 0 150 0 S2 440 4 2 0 1 0 0 220 0 S3 480 1 4 0 0 1 0 120 ⇐VS 0 S4 90 1 0 0 0 0 1 ∞ Zj 0 0 0 0 0 0 0 Cj - Zj 100 200 0 0 0 0 ⇑ VE Ri : Ratio . VE : Variable entrante ⇒ Correspond à la colonne Pivot. VS : Variable sortante ⇒ Correspond à la ligne Pivot. ∞ : lorsque division par zéro, tend vers l’infini. Cj – Zj : Effet de l’augmentation de la jème variable. On remarque qu’on a placé en première ligne les contributions unitaires de toutes les variabes (de décision & d’écart ) dans la fonction objectif. Recherche opérationnelle 28 Dans la 3ème ligne, on retrouve la 1re contrainte. La valeur 150 représente la valeur de S1 relative à la solution réalisable de base initiale ou SRBi. Dans la 1re colonne (Ci), on retrouve les contributions nulles des variables d’écart qui forment les SRBi. B – Amélioration de la solution Pour améliorer la solution, il faut générer une autre solution de base (point extrême) qui augmente la valeur de la fonction objectif, i.e. qu’on doit sélectionner une variable hors base ( VHB ) et variable de base (VB) et les permuter de telle façon que la nouvelle solution donne une plus grande valeurde la fonction objectif. Pour savoir si l’on peut améliorer notre SRBi , nous allons introduire 2 nouvelles lignes au-dessous du tableau du Simplexe : - La 1re ligne, notée Zj, représente la variation de la valeur de la fonction objectif qui résulte du fait qu’une unité de la variable corrrespondante à la jème colonne de la matrice A est amenée dans la base. Généralement, l’on a Zj = ∑aij Ci - La 2ème ligne, notée Ci – Zj , représente l’effet net de l’augmentation d’une unité de la jème variable. En analysant la ligne relative à l’évaluation nette Cj – Zj , on remarque qu’une augmentation d’une unité de la valeur x1 engendre un profit de 100D et qu’une augmentation d’une unité de la valeur de x2 engendre un profit supplémentaire de 200D .donc, si on a à choisir, on va opter pour une augmentation de la valeur de x2 . On dit que x2 est la variable entrante. Le problème est maintenant jusqu’où on peut augmenter x2. Cette augmentation ne peut pas se faire indéfiniment. Sous l’hypothèse que x1 reste nulle, on a : X1 + S1 = 150 2 x2 + S2 = 440 ⇒ S2 = 0, 2 x2 = 440 ⇒ x2 = 4402 ⇒ x2 = 220 4 x2 + S3 = 480 ⇒ S3 = 0, 4 x2 = 480 ⇒ x2 = 4804 ⇒ x2 = 120 S4 = 90 On peut voir que x2 peut prendre comme valeur maximale 120 ( Il ne faut pas oublier que les Si sont des variables positives ). SRBi SRB S1 = 150 S1 = S2 = 440 S2 = S3 = 480 x2 = 120 S4 = 90 S4 = C – Calcul du tableau suivant Cj 100 200 0 0 0 0 Ci VB Qi x1 x2 S1 S2 S3 S4 Ri 0 S1 30 3 4 0 1 0 -14 0 40 ⇐VS 0 S2 200 7 2 0 0 1 -12 0 400 7 200 X2 120 1 4 1 0 0 1 4 0 480 0 S4 90 1 0 0 0 0 1 90 Zj 24000 50 200 0 0 50 0 Cj - Zj 50 0 0 0 -50 0 ⇑ VE Recherche opérationnelle 29 Si Cj – Zj ≤ 0 ⇒ La solution est optimale. Dans notre cas : Solution non optimale = SRB ⇒ Nouvelle itération indispensable. Ce qui reste à déterminer sont les coefficients aij de la nouvelle matrice A et les valeurs Qi des variables de base. Ceci est réalisé en utilisant la règle du pivot : Étape c: Diviser la ligne du pivot par la valeur de l’élément pivot pour trouver la ligne transformée de la ligne du pivot. Étape d : À chacune des variables de base, on associe la valeur 1 à l’intersection de la ligne et de la colonne relatives à cette même variable et dans le reste de la colonne on trouve des zéros. Étape e : Pour calculer le reste des valeurs du tableau, on opère à des combinaisons linéaires dans le précédent tableau du Simplexe. Par exemple, pour calculer la nouvelle valeur qui va prendre la place de la valeur 150 devant la variable de base S1 on procède comme suit : 150 * 4 – (1 * 480 ) 4 =30 440 * 4 – 2 * 480 4 =200 90 *4 – 0 * 480 4 =90 1 * 4 – 1 * 1 4 = 3 4 D – Itération suivante Cj 100 200 0 0 0 0 Ci VB Qi x1 x2 S1 S2 S3 S4 100 X1 40 1 0 4 3 0 -13 0 0 S2 60 0 0 -143 1 2 3 0 200 X2 110 0 1 -13 0 1 3 0 0 S4 50 0 0 -43 0 1 3 1 Zj 26000 100 200 200 3 0 100 3 0 Cj - Zj 0 0 -2003 0 -1003 0 Cj – Zj ≤ 0 ⇒ Solution optimale SRB : x1 = 40 X2 = 110 Π = 26000 Recherche opérationnelle 30 R e c h e r c h e o p é r a t i o n n e l l e 26 CHAPITRE 3 Correction des exercices de la série n°3 03 20 05 R a p p e l s : L a m é t h o d e d u s i m p l e x e Étape c : FG ⇒ FS FG : Max C1x1 + C2x2+ … + Cnxn C S a11x1 + a12x2 + … + a1nxn ≤ b1 a21x1 + a22x2 + … + a2nxn ≤ b2 ................................................. ................................................. ................................................. an1x1 + an2x2 + … + anmxn ≤ bn FS : C1x1 + C2x2+ … + Cnxn + 0 S1 + 0 S2 + … + 0 Sn a11x1 + a12x2 + … + a1nxn + S1 = b1 a21x1 + a22x2 + … + a2nxn + S2 = b2 .................................................................................... .................................................................................... .................................................................................... an1x1 + an2x2 + … + anmxn Sn = bn x ≥ 0 si ≥ 0 Étape d : SRBi On annule toutes les variables de décision dans les équations des contraintes : SRBi ⎩⎪ ⎨⎪ ⎧S1 = b1S2 =b2 . . . . . Sn =bn La SRBi correspond à l’origine. Recherche opérationnelle 31 Étape e : Tableau initial du simplexe Cj C1 C2 C3 … 0 0 0 Ci VB Qi x1 x2 x3 … S1 S2 S3 … Ri 0 S1 b1 a11 a12 a13 … 1 0 0 … 0 S2 B2 a21 a22 a23 PIVOT 0 1 0 … Ligne Pivot 0 S3 B3 a31 a32 a33 … 0 0 1 … 0 S4 B4 a41 a42 a43 … 0 0 0 … … … … … … … … … … … … … … … … … … … … … … … Zj Cj - Zj Colonne pivot VE = Cj – Zj la plus grande possible. VS = celle qui possède le ratio le plus faible positif. Étape f : 2ème tableau du simplexe - Diviser la ligne pivot par l’élément pivot. - Marquer 1 dans chaque intersection d’une VRB avec elle-même et 0 à chaque intersection d’une VRB avec une autre VRB. - Cellules restantes : Procéder à des combinaisons linéaires comme suit : Erreur ! L’algorithme sera répété jusqu’à obtention de la solution optimale qui correspond à Cj – Zj ≤ 0 E x e r c i c e n ° 1 A - FG ⇒ FS FG FS Max Z = 2 x1 + 5 x2 C S x1 ≤ 400 x2 ≤ 300 x1 + x2 ≤ 600 avec x1 ≥ 0 et x2 ≥ 0 Max Z = 2 x1 + 5 x2 + 0 S1 + 0 S2 + 0 S3 C S x1 +S1 = 400 x2 + S2 = 300 x1 + x2 + S3 = 600 avec x1 , x2 ≥ 0 et S1 , S2 , S3 ≥ 0 B – SRBi S1 = 400 S2 = 300 S3 = 600 Recherche opérationnelle 32 C – Tableau initial Cj 2 5 0 0 0 Ci VB Qi x1 x2 S1 S2 S3 Ri 0 S1 400 1 0 1 0 0 ∞ 0 S2 300 0 1 0 1 0 300 ⇐VS 0 S3 600 1 1 0 0 1 600 Zj 0 0 0 0 0 0 Cj - Zj 2 5 0 0 0 ⇑ VE D – Nouvelle matrice transformée SRB = S1 x2 S3 1re étape : Diviser la ligne pivot par l’élément pivot. 2ème étape : Mettre 1 à chaque croisement de chaque variable de base avec elle-même. 3ème étape : Mettre 0 à chaque croisement de chaque variable de base avec une autre variable de base. Cj 2 5 0 0 0 Ci VB Qi x1 x2 S1 S2 S3 Ri 0 S1 400 1 0 1 0 0 400 5 x2 300 0 1 0 1 0 ∞ 0 S3 300 1 0 0 -1 1 300 ⇐VS Zj 1500 0 5 0 5 0 Cj - Zj 2 0 0 -5 0 ⇑ VE E – Nouvelle matrice transformée SRB : S1 x1 x2 Cj 2 5 0 0 0 Ci VB Qi x1 x2 S1 S2 S3 0 S1 100 0 0 1 1 -1 5 x2 300 0 1 0 1 0 2 x2 300 1 0 0 -1 1 Zj 2100 2 5 0 3 2 Cj - Zj 0 0 0 -3 -2 Les Cj – Zj ≤ 0 ⇒ C’est la solution optimale x1 = 300 x2 = 300 Πmax = 2100 Recherche opérationnelle 33 E x e r c i c e n ° 2 A - FG ⇒ FS FG FS Max Z = 100 x + 150 y C S 10 x + 4 y + S1 ≤ 160 x + y + S2 ≤ 20 10 x + 20 y + S3 ≤ 300 avec x ≥ 0 et y ≥ 0 Max Z = 100 x + 150 y + 0 S1 + 0 S2 + 0 S3 C S 10 x + 4 y + S1 = 160 x + y + S2 = 20 10 x + 20 y + S3 = 300 avec x , y ≥ 0 et S1 , S2 , S3 ≥ 0 B – SRBi S1 = 160 S2 = 20 S3 = 300 C – Tableau initial Cj 100 150 0 0 0 Ci VB Qi x y S1 S2 S3 Ri 0 S1 160 10 4 1 0 0 40 0 S2 20 1 1 0 1 0 20 0 S3 300 10 20 0 0 1 15 ⇐VS Zj 0 0 0 0 0 0 Cj - Zj 100 150 0 0 0 ⇑ VE D – Nouvelle matrice transformée SRB = S1 S2 y 1re étape : Diviser la ligne pivot par l’élément pivot. 2ème étape : Mettre 1 à chaque croisement de chaque variable de base avec elle-même. 3ème étape : Mettre 0 à chaque croisement de chaque variable de base avec une autre variable de base. Cj 100 150 0 0 0 Ci VB Qi x y S1 S2 S3 Ri 0 S1 100 8 0 1 0 -15 12.5 0 S2 5 1 2 0 0 1 - 120 10 ⇐VS 150 y 15 1 2 1 0 0 1 20 30 Zj 2250 75 150 0 0 7.50 Cj - Zj 25 0 0 0 -152 Recherche opérationnelle 34 ⇑ VE E – Nouvelle matrice transformée SRB : S1 x y Cj 100 150 0 0 0 Ci VB Qi x y S1 S2 S3 0 S1 20 0 0 1 -16 6 10 100 x 10 1 0 0 2 - 110 150 y 10 0 1 0 -1 1 10 Zj 2500 100 150 0 50 5 Cj - Zj 0 0 0 -50 -5 Les Cj – Zj ≤ 0 ⇒ C’est la solution optimale x = 10 y = 10 Πmax = 2500 E x e r c i c e n ° 3 A - FG ⇒ FS FG FS Max Z = 600 x1 + 540 x2 + 375 x3 C S x1 + x2 + x3 ≤ 12 x1 ≤ 5 80 x1 + 70 x2 +50 x3 ≤ 750 avec x1 , x2 et x3 ≥ 0 Max Z = 600 x1 + 540 x2 + 375 x3 + 0 S1 + 0 S2 + 0 S3 C S x1 + x2 + x3 +S1 = 12 x1 + S2 = 5 80 x1 + 70 x2 +50 x3 + S3 = 750 avec x1 , x2 ≥ 0 et S1 , S2 , S3 ≥ 0 B – SRBi S1 = 12 S2 = 5 S3 = 750 C – Tableau initial Cj 600 540 375 0 0 0 Ci VB Qi x1 x2 x3 S1 S2 S3 Ri 0 S1 12 1 1 1 1 0 0 12 0 S2 5 1 0 0 0 1 0 5 ⇐VS 0 S3 750 80 70 50 0 0 1 9,375 Zj 0 0 0 0 0 0 0 Cj - Zj 600 540 375 0 0 0 Recherche opérationnelle 35 ⇑ VE D – Nouvelle matrice transformée SRB = S1 x1 S3 Cj 600 540 375 0 0 0 Ci VB Qi x1 x2 x3 S1 S2 S3 Ri 0 S1 7 0 1 1 1 -1 0 7 600 x1 5 1 0 0 0 1 0 ∞ 0 S3 350 0 70 50 0 -80 1 5 ⇐VS Zj 3000 600 0 0 0 600 0 Cj - Zj 0 540 375 0 -600 0 ⇑ VE E – Nouvelle matrice transformée SRB : S1 x1 x2 Cj 600 540 375 0 0 0 Ci VB Qi x1 x2 x3 S1 S2 S3 Ri 0 S1 2 0 0 2 7 1 1 7 - 1 70 14 600 x1 5 1 0 0 0 1 0 5 ⇐VS 540 x2 5 0 1 5 7 0 - 8 7 1 70 - 35 8 Zj 5700 600 540 385,71 0 -17,14 7.71 Cj - Zj 0 0 -10.71 0 17.14 -7.71 ⇑ VE 8 La variable sortante est celle qui possède le ration le plus faible positif ! F – Nouvelle matrice transformée SRB : S1 = 0 S2 = 0 x2 = 540 Cj 600 540 375 0 0 0 Ci VB Qi x1 x2 x3 S1 S2 S3 0 S1 9 7 - 1 7 0 2 7 1 0 - 1 70 0 S2 5 1 0 0 0 1 0 540 x2 75 7 8 7 1 5 7 0 0 1 70 Zj 5785,71 617,14 540 385,71 0 0 7,71 Cj - Zj -17.14 0 -10.71 0 0 -7.71 Les Cj – Zj ≤ 0 ⇒ C’est la solution optimale x = 0 y = 757 Πmax = 5785.71 Recherche opérationnelle 36 E x e r c i c e n ° 4 A - FG ⇒ FS FG FS Max Z = 50 x1 + 60 x2 C S x1 + 2 x2 ≤ 8 2 x1 + 2 x2 ≤ 10 9 x1 + 4 x2 ≤ 36 avec x1 ≥ 0 et x2 ≥ 0 Max Z = 50 x1 + 60 x2 + 0 S1 + 0 S2 + 0 S3 C S x1 + 2 x2 +S1 = 8 2 x1 + 2 x2 + S2 = 10 9 x1 + 4 x2 + S3 = 36 avec x1 , x2 ≥ 0 et S1 , S2 , S3 ≥ 0 B – SRBi S1 = 8 S2 = 10 S3 = 36 C – Tableau initial Cj 50 60 0 0 0 Ci VB Qi x1 x2 S1 S2 S3 Ri 0 S1 8 1 2 1 0 0 4 ⇐VS 0 S2 10 2 2 0 1 0 5 0 S3 36 9 4 0 0 1 9 Zj 0 0 0 0 0 0 Cj - Zj 50 60 0 0 0 ⇑ VE D – Nouvelle matrice transformée SRB = x2 S2 S3 Cj 50 60 0 0 0 Ci VB Qi x1 x2 S1 S2 S3 Ri 60 x2 4 1 2 1 1 2 0 0 8 0 S2 2 1 0 -1 1 0 2 ⇐VS 0 S3 20 7 0 -2 0 1 20 7 Zj 240 30 60 30 0 0 Cj - Zj 20 0 -30 0 0 ⇑ VE E – Nouvelle matrice transformée SRB : x2 x1 S3 Cj 50 60 0 0 0 Ci VB Qi x1 x2 S1 S2 S3 60 x2 3 0 1 1 -12 0 50 x1 2 1 0 -1 1 0 0 S3 6 0 0 5 -7 1 Zj 280 50 60 10 20 0 Cj - Zj 0 0 -10 -20 0 Les Cj – Zj ≤ 0 ⇒ C’est la solution optimale. Recherche opérationnelle 37 x1 = 2 x2 = 3 Πmax = 280 E x e r c i c e n ° 5 A - FG ⇒ FS FG FS Max Z = 7 x1 + 5 x2 + 5x3 +4 x4 C S 2 x1 + 4x2 +2x3 + 3 x4 ≤ 45000 x1 +x2 ≤ 6000 x3 +x4 ≤ 7000 x1 + x3 ≤ 5000 x2 + x4 ≤ 6000 avec x1 , x2 , x3 et x4 ≥ 0 Max Z = 7 x1 + 5 x2 + 5x3 +4 x4 + 0 S1 + 0 S2 + 0 S3 + S4 + 0 S5 C S 2 x1 + 4x2 +2x3 + 3 x4 + S1 = 45000 x1 +x2 + S2 = 6000 x3 +x4 + S3 = 7000 x1 + x3 + S4 = 5000 x2 + x4 + S5 = 6000 avec x1 , x2 , x3 et x4 ≥ 0 et S1 , S2 , S3 , S4 et S5 ≥ 0 B – SRBi S1 = 45000 S2 = 6000 S3 = 7000 S4 = 5000 S5 = 6000 C – Tableau initial Cj 7 5 5 4 0 0 0 0 0 Ci VB Qi x1 x2 x3 x4 S1 S2 S3 S4 S5 Ri 0 S1 45000 2 4 2 3 1 0 0 0 0 22500 0 S2 6000 1 1 0 0 0 1 0 0 0 6000 0 S3 7000 0 0 1 1 0 0 1 0 0 ∞ 0 S4 5000 1 0 1 0 0 0 0 1 0 5000 ⇐VS 0 S5 6000 0 1 0 1 0 0 0 0 1 ∞ Zj 0 0 0 0 0 0 0 0 0 0 Cj - Zj 7 5 5 4 0 0 0 0 0 ⇑ VE D – Nouvelle matrice transformée SRB : S1 = 0 S2 = 0 S3 = 0 x1 = 7 S5 = 0 Cj 7 5 5 4 0 0 0 0 0 Ci VB Qi x1 x2 x3 x4 S1 S2 S3 S4 S5 Ri 0 S1 35000 0 4 0 3 1 0 0 -2 0 8750 0 S2 1000 0 1 -1 0 0 1 0 -1 0 1000 ⇐VS 0 S3 7000 0 0 1 1 0 0 1 0 0 ∞ 7 x1 5000 1 0 1 0 0 0 0 1 0 ∞ 0 S5 6000 0 1 0 1 0 0 0 0 1 6000 Zj 35000 7 0 7 0 0 0 0 7 0 Cj - Zj 0 5 -2 4 0 0 0 -7 0 Recherche opérationnelle 38 ⇑ VE E – Nouvelle matrice transformée SRB : S1 = 0 x2 = 5 S3 = 0 x1 = 7 S5 = 0 Cj 7 5 5 4 0 0 0 0 0 Ci VB Qi x1 x2 x3 x4 S1 S2 S3 S4 S5 Ri 0 S1 31000 0 0 4 3 1 -4 0 2 0 31000 3 5 x2 1000 0 1 -1 0 0 1 0 -1 0 ∞ 0 S3 7000 0 0 1 1 0 0 1 0 0 7000 7 x1 5000 1 0 1 0 0 0 0 1 0 ∞ 0 S5 5000 0 0 1 1 0 -1 0 1 1 5000 ⇐VS Zj 7 5 2 0 0 5 0 2 0 Cj - Zj 0 0 3 4 0 -5 0 -2 0 ⇑ VE F – Nouvelle matrice transformée SRB : S1 = 0 x2 = 5 S3 = 0 x1 = 7 x4 = 4 Cj 7 5 5 4 0 0 0 0 0 Ci VB Qi x1 x2 x3 x4 S1 S2 S3 S4 S5 0 S1 16000 0 0 1 0 1 -1 0 -1 -3 5 x2 1000 0 1 -1 0 0 1 0 -1 0 0 S3 2000 0 0 0 0 0 1 1 -1 -1 7 x1 5000 1 0 1 0 0 0 0 1 0 4 x4 5000 0 0 1 1 0 -1 0 1 1 Zj 60000 7 5 6 4 0 1 0 6 4 Cj - Zj 0 0 -1 0 0 -1 0 -6 -4 Les Cj – Zj ≤ 0 ⇒ C’est la solution optimale x1 = 5000 x2 = 1000 x3 = 0 x4 = 5000 Πmax = 60000 Recherche opérationnelle 39 R e c h e r c h e o p é r a t i o n n e l l e 02 CHAPITRE 4 Méthode du Simplexe Problème de minimisation & problèmes irréguliers 04 20 05 I – I n t r o d u c t i o n Dans le chapitre précédent, tous les PL qu’on a traités étaient du type : Maximiser une fonction linéaire C S Contraintes (avec un second membre positif ) < - > Max ∑ Ci xj C S ∑ aij xi ≤ bi ( avec bi ≥ 0 ) ( avec xi ≥ 0 et j : 1 .. n ) Or, dans beaucoup de problèmes réels, on peut retrouver des contraintes du type ≥ et/ou = ainsi que des problèmes où l’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. I I – P r o b l è m e s d e m i n i m i s a t i o n e t p r o b l è m e s a v e c c o n t r a i n t e s m i x t e s A – Cas de minimisation Cas d’un problème de minimisation avec contraintes du type ≤ : Min Z = ∑ Cj xj C S ∑ aij xj ≤ bi si, dans un PL, la fonction objectif doit être minimisée, on peut résoudre le PL : - En changeant la règle de choix de la variable et de la règle d’arrêt. On choisit comme variable entrante celle dont l’introduction réduit le plus la fonction objectif, i.e. celle dont le Cj – Zj est le plus grand négatif ; on s’arrête quand il n’est plus possible de réduire la fonction objectif i.e. lorsque toutes les Cj – Zj sont positives ou nulles. - ☺ On peut résoudre le PL en le réduisant à un problème de maximisation ; ceci peut être accompli en prenant l’opposé de la fonction objectif : Min Z = ∑ Cj xj ⇔ Max ( -Z ) = (-Cj) xj , les contraintes fonctionnelles et les contraintes formelles restant les mêmes. Dans ce cas, on peut Recherche opérationnelle 40 utiliser la méthode décrite pour le cas de maximisation en changeant le critère de sélection des V.E. de Cj - Zj à Zj –Cj . La solution est optimale lorsque Zj – Cj est négative ou nulle. B – Cas des contraintes fonctionnelles mixtes : Technique des variables artificielles Nous avons vu dans le chapitre précédent qu’un PL sous la Forme Générale : peut être facilement mis sous forme canonique en introduisant des variables d’écart. Cependant le PL original contient des contraintes du type (=) ou ( ≥ ) et/ou des éléments de bi qui ne sont pas tous non négatifs. FG Max Z = ∑ Cj xj C S ∑ aij xi ≤ bi avec bi ≥ 0 avec xj ≥ 0 j : 1 .. n Il peut être mis sous forme standard facilement mais ne sera pas sous forme canonique. On introduit dans cette section une méthode utilisant des variables artificielles à la forme canonique. On passe par les étapes suivantes : 1re étape : On part d’un Pl sous FG Max Z = ∑ Cj – xj C S ∑ aij xj ≤ bi ∑ aij xj = bi ∑ aij xj ≥ bi avec xj ≥ 0 2ème étape : Mettre le PL sous FS par l’introduction de variables d’écart. Les contraintes deviennent : C S ∑ aij xj + Si = bi ∑ aij xj = bi ∑ aij xj - Si = bi avec xj ≥ 0 et Si ≥ 0 Recherche opérationnelle 41 3ème étape : On introduit les variables artificielles et les contraintes deviennent : C S ∑ aij xj + Si = bi ∑ aij xj + Ai = bi ∑ aij xj - Si + Ai = bi avec xj ≥ 0 , Si ≥ 0 et Ai ≥0 Exemple de détermination de la F.C. avec des contraintes mixtes F.G. Max Z = - x1 – x2 C S 3 x1 + x2 = 3 4 x1 + 3x2 ≥ 6 x1 + 2 x2 ≤ 3 avec x1 et x2 ≥ 0 F.S. Max Z = - x1 – x2 C S 3 x1 + x2 = 3 4 x1 + 3x2 – S1 = 6 x1 + 2 x2 + S2 = 3 avec x1 , x2 ≥ 0 et S1 , S2 ≥ 0 F.C. Max Z = - x1 – x2 + 0 S1 + 0 S2 C S 3 x1 + x2 + A1 = 3 4 x1 + 3x2 – S1 + A2 = 6 x1 + 2 x2 + S2 = 3 avec x1 , x2 ≥ 0 , S1 , S2 ≥ 0 et A1 , A2 ≥ 0 La question qui se pose maintenant est : quels sont les coefficients des variables artificielles introduites dans la base dans la fonction objectif ? L’idée des variables artificielles est de leur affecter des coefficients non nuls et d’essayer de les annuler ce qui permettrait de trouver une F.C. complète et aussi une solution de base possible. La méthode de pénalité « Big M » Puisque dans une contrainte où l’on a introduit une variable artificielle qui est dans la base et qui peut être positive, la contrainte en question n’est pas satisfaite, il faut donc faire sortir ces variables artificielles rapidement de la base (en premier lieu) en vue d’obtenir une solution de base possible. Pour faire sortir ces variables de la base rapidement et en premier lieu, on leur affecte un coefficient pénalisateur très grand dans la fonction économique. Soit M > > ( M très grand positif ) . On écrit la fonction objectif de la sorte : Max Z = ii A M - S 0 +∑ jj xC Exemple : Max Z = - 2 x1 – x2 + 0 S1 + 0 S2 – M A1 - M A2 ( avec M >> 0 ) Le PL n’est pas sous forme entièrement canonique, car les coefficients des variables artificielles qui font Recherche opérationnelle 42 partie des variables de base ne sont pas nuls. Pour résoudre un PL avec des contraintes mixtes, il faut suivre la procédure suivante : c Introduire des coefficients pénalisateurs très grands attachés aux variables artificielles dans la fonction objectif. d Appliquer la méthode du Simplexe. Deux cas se présentent : 1er cas : Une variable artificielle au moins reste dans la base avec une valeur positive. Le problème n’a pas de solution. Malgré le poids pénalisateur très grand attaché à cette variable, il n’est pas possible de la rendre nulle. 2ème cas : toutes les variables artificielles sortent de la base ou bien il reste certaines artificielles dans la base mais avec valeurs nulles : Une solution de base possible est trouvée : C’est la solution optimale. Exemples applicatifs c Exemple de minimisation avec contraintes ≥ FG Soit le PL suivant : Min C = - 24 x1 + 20 x2 C S x1 + x2 ≥ 30 x1 + 2 x2 ≥ 40 avec x1 et x2 ≥ 0 FS Min C = - 24 x1 + 20 x2 + 0 S1 + 0 S2 C S x1 + x2 - S1 = 30 x1 + 2 x2 – S2 = 40 avec x1 , x2 ≥ 0 et S1 , S2 ≥ 0 FC Min C = - 24 x1 + 20 x2 + 0 S1 + 0 S2 + M A1 + M A2 C S x1 + x2 - S1 + A1 = 30 x1 + 2 x2 – S2 + A2 = 40 avec x1 , x2 ≥ 0 et S1 , S2 ≥ 0 Remarque : cas de minimisation : + M Ai cas de maximisation : - M Ai SRBi A1 = 30 A2 = 40 Recherche opérationnelle 43 Tableau initial Cj 24 20 0 0 M M Ci VB Qi x1 x2 S1 S2 A1 A2 Ri M A1 30 1 1 -1 0 1 0 30 M A2 40 1 2 0 -1 0 1 20 ⇐VS Zj 70 M 2 M 3 M -M -M M M Zj – Cj 2 M – 24 3 M –20 - M - M 0 0 ⇑ VE Remarque : Minimiser C =∑ Cj xj +∑ M Ai . On dit qu’on a pénalisé C, car M est très grand, donc minimise C prend le signe + M. Or M est très grand et on cherche un minimum donc cela pénalise C. Maximiser Z= ∑ Cj xj - ∑ M Ai . On pénalise Z, car M est très grand. Donc Maximiser Z prend le signe de – M. Or nous cherchons un maximum donc cela pénalise Z. 2ème itération : Matrice transformée SRB : A1 = M x2 = 20 Cj 24 20 0 0 M Ci VB Qi x1 x2 S1 S2 A1 Ri M A1 10 1 2 0 -1 1 2 1 20 ⇐VS 20 x2 20 1 2 1 0 - 1 2 0 ∞ Zj 10 M + 400 M 2 +10 20 -M M 2 -10 M Zj – Cj M 2 -14 0 -M M 2 -10 0 ⇑ VE 3ème itération SRB : S2 = 0 x2 = 20 Cj 24 20 0 0 Ci VB Q x1 x2 S1 S2 0 S2 20 1 0 - 1 2 1 20 x2 30 1 1 -1 0 Zj 600 20 20 20 30 Zj – Cj -4 0 -20 0 Zj – Cj ≤ 0 ⇒ solution optimale x1 = 0 x2 = 20 Recherche opérationnelle 44 C* = 600 d Exemple de minimisation avec contraintes mixtes Min C = 6 x1 + 4 x2 C S 3 x1 + 2 x2 ≥ 18 2 x1 + 4 x2 = 20 2 x2 ≤ 8 avec x1 et x2 ≥ 0 e Exemple de maximisation avec contraintes mixtes Max Z = 4 x1 + 3 x2 C S x1 + x2 = 10 x1 + 3 x2 ≤ 20 2 x1 – x2 ≥ 15 avec x1 et x2 ≥ 0 Recherche opérationnelle 45 R e c h e r c h e o p é r a t i o n n e l l e 09 CHAPITRE 4 Méthode du Simplexe Problème de minimisation & problèmes irréguliers 04 20 05 E x e m p l e d e m i n i m i s a t i o n a v e c c o n t r a i n t e s m i x t e s FG Min C = 6 x1 + 4 x2 C S 3 x1 + 2 x2 ≥ 18 2 x1 + 4 x2 = 20 2 x2 ≤ 8 avec x1 et x2 ≥ 0 Fc Min C = 6 x1 + 4 x2 + 0 S1 + 0 S2 + M A1 + M A2 C S 3 x1 + 2 x2 – S1 + A1 = 18 2 x1 + 4 x2 + A2 = 20 2 x2 + S2 = 8 avec x1 , x2 ≥ 0 S1 , S2 ≥ 0 , A1 , A2 ≥ 0 SRBi A1 = 18 A2 = 20 S2 =8 Tableau initial Cj 6 4 0 0 M M Ci VB Qi x1 x2 S1 S2 A1 A2 Ri M A1 18 3 2 -1 0 1 0 9 M A2 20 2 4 0 0 0 1 5 0 S2 8 0 2 0 1 0 0 4 ⇐VS Zj 38 M 5 M 6 M -M 0 M M Zj – Cj 5M-6 6M-4 -M 0 0 0 ⇑ VE Recherche opérationnelle 46 Cj 6 4 0 0 M M Ci VB Qi x1 x2 S1 S2 A1 A2 Ri M A1 10 3 0 -1 -1 1 0 103 M A2 4 2 0 0 -2 0 1 2 ⇐VS 4 x2 4 0 1 0 ½ 0 0 ∞ Zj 14M+16 5 M 4 -M -3M+2 M M Zj – Cj 5M-6 0 0 -3M+2 0 0 ⇑ VE Cj 6 4 0 0 M Ci VB Qi x1 x2 S1 S2 A1 Ri M A1 4 0 0 -1 2 1 2 ⇐VS 6 x1 2 1 0 0 -1 0 ∞ 4 x2 4 0 1 0 1 2 0 8 Zj 4M+28 6 4 -M 2M-4 M Zj – Cj 0 0 -M 2M-4 0 ⇑ VE Cj 6 4 0 0 Ci VB Qi x1 x2 S1 S2 0 S2 2 0 0 - 1 2 1 6 x1 4 1 0 - 1 2 0 4 x2 3 0 1 1 4 0 Zj 36 6 4 -2 0 Zj – Cj 0 0 -2 0 Zj – Cj ≤ 0 ⇒ Solution optimale ⎩⎪ ⎨⎪ ⎧ x1 = 4 x2 = 3 coût minimum=36 Remarque Nous résumons les différentes variables à introduire dans le modèle pour obtenir un PL initial de base : A- Dans chaque contrainte de type (≤ ) additionner des variables d’écart . B- Dans chaque contrainte de type (≥) soustraire une variable d’écart et ajouter une variable artificielle. C- Dans chaque contrainte de type (=) additionner des variables artificielles. E x e m p l e d e m a x i m i s a t i o n a v e c Recherche opérationnelle 47 c o n t r a i n t e s m i x t e s FG Max Z = 4 x1 + 3 x2 C S x1 + x2 = 10 x1 + 3 x2 ≤ 20 2 x1 – x2 ≥ 15 avec x1 et x2 ≥ 0 FC Max Z = 4 x1 + 3 x2 + 0 S1 + 0 S2 – M A1 - M A2 C S x1 + x2 + A1 = 10 x1 + 3 x2 + S1 = 20 2 x1 – x2 – S2 + A2 = 15 avec x1 , x2 ≥ 0 , S1 , S2 ≥ 0 et A1 , A2 ≥ 0 SRBi A1 =10 S1 =20 A2 = 15 Tableau initial du Simplexe A compléter ! Recherche opérationnelle 48 A u t r e m é t h o d e p o u r l a r è g l e d u p i v o t 1re étape On divise la ligne pivot par l’élément pivot et l’on obtient la nouvelle ligne pivot. C’est ce qu’on appelle « normalisation de la ligne pivot ». 2ème étape Pour transformer une ligne autre que celle du pivot, on opère des combinaisons linéaires entre la ligne considérée et la nouvelle ligne de pivot de manière à remplacer la colonne de pivot par une colonne unité. Pour cela, on retranche de la ligne considérée le produit de la nouvelle ligne de pivot par al avec al étant l’élément de la ligne à transformer dans la colonne de pivot : TL = L – al * TLP Avec TL = C’est la transformée d’une ligne quelconque. L = C’est la ligne à transformer. TLP = Transformée de la ligne de pivot. Exemple : Soit le T.I. suivant : Cj 25 15 0 0 Ci VB Qi x1 x2 S1 S2 Ri 0 S1 240 2 2 1 0 120 0 S2 140 3 1 0 1 1403 ⇐VS Zj 0 0 0 0 0 Cj – Zj 25 15 0 0 ⇑ VE TLP 140 3 3 3 1 3 0 3 1 3 TLP 140 3 1 1 3 0 1 3 L 240 2 2 1 0 al = élément de la ligne à transformer dans la colonne pivot = 2 al * TLP 2 * 140 3 2 * 1 2 * 1 3 2 *0 2 * 1 3 al * TLP 2803 2 2 3 0 2 3 TL = Transformée de la ligne L = L – al * TLP TL 240-2803 2-2 2- 2 3 1-0 0- 2 3 TL 4403 0 4 3 1 - 2 3 Recherche opérationnelle 49 D’où le tableau suivant : Cj 25 15 0 0 Ci VB Qi x1 x2 S1 S2 Ri 0 S1 440/3 0 4/3 1 -2/3 25 x1 140/3 1 1/3 0 1/3 Zj Cj – Zj I V – L e s p r o b l è m e s i r r é g u l i e r s a / Les problèmes impossibles On reconnaît que le problème est impossible si une ou plusieurs variables artificielles sont présentes dans la base dans le tableau du Simplexe optimal, ce qui signifie que la solution donnée par ce tableau n’est pas réellement réalisable. Exemple FG Max 4 x1 + 3 x2 C S x1 + x2 ≤ 2 3 x1 + x2 ≥ 10 avec x1 et x2 ≥ 0 FC Max 4 x1 + 3 x2 + 0S1 + 0 S2 – M A1 C S x1 + x2 + S1 = 2 3 x1 + x2 – S2 + A1 = 10 avec x1 , x2 ≥ 0 , S1, S2 ≥ 0 et A1 , A2 ≥ 0 SRBi S1 = 2 A1 = 10 Tableau initial Cj 4 3 0 0 -M Ci VB Qi x1 x2 S1 S2 A1 Ri 0 S1 2 1 1 1 0 0 2 ⇐VS -M A1 10 3 1 0 -1 1 10 3 Zj -10M -3M -M 0 M -M Cj – Zj 3M+4 3+M 0 -M 0 ⇑ VE Recherche opérationnelle 50 Cj 4 3 0 0 -M Ci VB Qi x1 x2 S1 S2 A1 4 x1 2 1 1 1 0 0 -M A1 5 0 -2 -3 -1 1 Zj 8-5M 4 4+2M 4+3M M -M Cj – Zj 0 -1-2M -4-3M -M 0 Cj – Zj ≤ 0 , mais il existe encore une variable artificielle dans la base ⇒ Il s’agit donc d’un problème impossible. b/ Problèmes à solutions multiples On identifie ce problème lorsque, dans la solution optimale, un des effets nets (relatif à une variable hors base : S1, S2 , …) est nul. Cj Ci VB Qi X1 x2 S1 S2 x1 x2 Zj Cj – Zj 0 0 0 -3 S1 : Variable hors base dont l’effet est nul. c / Problèmes avec solutions infinies On reconnaît ce problème lorsque la variable rentrante n’admet aucune limite sur sa valeur d’entrée c’est-à-dire que tous les ratios sont négatifs ou nuls. Exemple FG Max x1 + 2 x2 C S x1 + x2 ≥ 2 x2 ≤ 3 avec x1 et x2 ≥ 0 FC Max x1 + 2 x2 + 0 S1 + 0 S2 – M A1 C S x1 + x2 – S1 + A1 = 2 x2 + S2 = 3 avec x1 , x2 ≥ 0 , S1, S2 ≥ 0 et A1 ≥ 0 Après quelques itérations, on trouve le tableau suivant : Cj 1 2 0 0 Ci VB Qi x1 x2 S1 S2 Ri 2 x2 3 0 1 0 1 ∞ 0 S1 1 -1 0 1 1 -1 Zj 6 0 2 0 2 Cj – Zj 1 0 0 -2 ⇑ VE Ce tableau montre que la variable x2 n’admet aucune limite sur sa valeur de sortie : Donc la solution est infinie. Ratios négatifs ou nuls Recherche opérationnelle 51 d / Le problème à solution dégénérée Un PL est dit dégénéré si une ou plusieurs variables dans la base optimale sont nulles. Exemple FG Max Z = 2 x1 + 3 2 x3 C S x1 – x2 ≤ 2 2 x1 + x3 ≤ 4 x1 + x2 + x3 ≤ 3 avec x1 , x2 et x3 ≥ 0 FS Max Z = 2 x1 + 3 2 x3 + 0 S1 + 0 S2 + 0 S3 C S x1 – x2 + S1 = 2 2 x1 + x3 + S2 = 4 x1 + x2 + x3 + S3 = 3 avec x1 , x2 et x3 ≥ 0 et S1 , S2 et S3 ≥ 0 Tableau initial Cj 2 0 3 2 0 0 0 Ci VB Qi x1 x2 x3 S1 S2 S3 Ri 0 S1 2 1 -1 0 1 0 0 2 0 S2 4 2 0 1 0 1 0 2 ⇐VS 0 S3 3 1 1 1 0 0 1 3 Zj 0 0 0 0 0 0 0 Cj – Zj 2 0 3 2 0 0 0 ⇑ VE La variable rentrante est x1 , mais les 2 premières contraintes donnent la même valeur minimale ( même ratio ) de ratio. Ceci indique que lorsque x1 passe à 2, les variables d’écart S1 et S2 vont s’annuler bien que l’une des 2 demeure encore dans la base. Dans ce cas, il faut choisir arbitrairement de faire sortir de la base l’une ou l’autre des deux variables d’écart S1 ou S2. D’où le tableau suivant : ( on choisit de faire sortir S1 ) Cj 2 0 3 2 0 0 0 Ci VB Qi x1 x2 x3 S1 S2 S3 Ri 2 x1 2 1 -1 0 1 0 0 -2 0 S2 0 0 2 1 -2 1 0 0 ⇐VS 0 S3 1 0 2 1 -1 0 1 ½ Zj 4 2 -2 0 2 0 0 Cj – Zj 0 2 3 2 -2 0 0 Recherche opérationnelle 52 ⇑ VE S2 est une variable de base qui est nulle et la valeur de la fonction objectif est égale à 4. Cette solution de base est donc dite dégénérée : SRB ⎩⎪ ⎨⎪ ⎧x1=2 S2=0 S3=1 π = 4 Continuons les itérations relatives à la méthode du simplexe : Cj 2 0 3 2 0 0 0 Ci VB Qi x1 x2 x3 S1 S2 S3 Ri 2 x1 2 1 0 ½ 0 ½ 0 4 0 x2 0 0 1 ½ -1 ½ 0 0 ⇐VS 0 S3 1 0 0 0 1 -1 1 ∞ Zj 4 2 0 0 0 1 0 Cj – Zj 0 0 3 2 0 -1 0 ⇑ VE Ce tableau n’est pas optimal . x2 est une variable de base qui est nulle et la valeur de la fonction objectif est toujours égale à 4. Cette solution de base est donc dite dégénérée. SRB ⎩⎪ ⎨⎪ ⎧ x1=2 x2=0 S3 =1 π = 4 On remarque que ce passage d’une solution à une autre solution ne s’accompagne pas d’une augmentation de la valeur de la fonction objectif. On peut facilement vérifier que nous sommes en train de cycler sans atteindre la solution optimale. Ce genre de « cyclage » dans la méthode du 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. N.B. Il faut noter que ce n’est pas tout problème de dégénérescence qui peut conduire à un cyclage. CHAPITRE Recherche opérationnelle I – Introduction II – Formulation d’un modèle de décision 1 – Caractéristiques d’un programme linéaire (PL) 2 – Formulation d’un PL CHAPITRE Recherche opérationnelle Corrigé de l’exercice n°1 Corrigé de l’exercice n°2 Corrigé de l’exercice n°5 CHAPITRE Recherche opérationnelle 3 – La formulation algébrique d’un programme linéaire CHAPITRE Recherche opérationnelle I Définitions 1 - Solution possible non réalisable 2 – Solution possible et réalisable 3 – Solution réalisable de base ( notée SRB ) 4 – Solution réalisable non optimale 5 – Solution optimale II – Recherche de la solution optimale 1 – Représentation graphique des contraintes fonctionnelles 2 - Recherche de la solution optimale 3 – Solutions optimales : Différents cas possibles CHAPITRE Recherche opérationnelle Exemple applicatif n°2 CHAPITRE Recherche opérationnelle Exercice n°1 Fonction Objectif : Variables de décision : Contraintes : Exercice n°2 Fonction objectif : Variables de décision : Contraintes : Résolution graphique Exercice n°3 Fonction objectif: Variables de décision: Contraintes : Résolution CHAPITRE Recherche opérationnelle I - Introduction II – Mise sous forme standard III – Revue algébrique de la méthode du Simplexe CHAPITRE Recherche opérationnelle Rappels IV - La méthode du Simplexe A – Tableau du Simplexe initial ( à l’origine ) B – Amélioration de la solution C – Calcul du tableau suivant D – Itération suivante CHAPITRE Recherche opérationnelle Rappels : La méthode du simplexe Étape ( : FG ( FS Étape ( : SRBi Étape ( : Tableau initial du simplexe Étape ( : 2ème tableau du simplexe Exercice n°1 A - FG ( FS B – SRBi C – Tableau initial D – Nouvelle matrice transformée E – Nouvelle matrice transformée Exercice n°2 A - FG ( FS B – SRBi C – Tableau initial D – Nouvelle matrice transformée E – Nouvelle matrice transformée Exercice n°3 A - FG ( FS B – SRBi C – Tableau initial D – Nouvelle matrice transformée E – Nouvelle matrice transformée F – Nouvelle matrice transformée Exercice n°4 A - FG ( FS B – SRBi C – Tableau initial D – Nouvelle matrice transformée E – Nouvelle matrice transformée Exercice n°5 A - FG ( FS B – SRBi C – Tableau initial D – Nouvelle matrice transformée E – Nouvelle matrice transformée F – Nouvelle matrice transformée CHAPITRE Recherche opérationnelle Méthode du Simplexe I – Introduction II – Problèmes de minimisation et problèmes avec contraintes mixtes A – Cas de minimisation B – Cas des contraintes fonctionnelles mixtes : Technique des variables artificielles Exemple de détermination de la F.C. avec des contraintes mixtes F.G. F.S. F.C. La méthode de pénalité « Big M » Exemples applicatifs ( Exemple de minimisation avec contraintes ( FG FS FC SRBi Tableau initial 2ème itération : Matrice transformée 3ème itération ( Exemple de minimisation avec contraintes mixtes ( Exemple de maximisation avec contraintes mixtes CHAPITRE Recherche opérationnelle Méthode du Simplexe Exemple de minimisation avec contraintes mixtes FG Fc SRBi Tableau initial Remarque Exemple de maximisation avec contraintes mixtes FG FC SRBi Tableau initial du Simplexe Autre méthode pour la règle du pivot 1re étape  2ème étape Exemple : IV – Les problèmes irréguliers a / Les problèmes impossibles FG FC SRBi Tableau initial b/ Problèmes à solutions multiples c / Problèmes avec solutions infinies FG FC d / Le problème à solution dégénérée FG FS Tableau initial