2. Méthode du simplexe son analyse Transformation de max en min • Considérons le problème de maximisation max f(w) Sujet à w ex C Rn oùf:x- RI. Transformation de • Considérons le pro Sujet à w CX c Rn m orq7 Sni* to View • Soit w* un point de X ou le maximum est atteint. Sujet à w ex c Rn RI. • Soit w* un point de X où le maximum est atteint. ?? Donc f(w*) f(w) Donc – s – f(w) X • Par conséquent – f(wk) = min – f(w) Sujet à WEX c Rn et w* est un point de X où la fonction – f(w) atteint son minimum. Sujet à w EX c Rn VwE X – – f(w) X Sujet à weX c Rn t est un point de X où la fonction – f(w) atteint son minimum. • Ainsi qu’on max f(w) ou qu’on min – f(w), on retrouve la même sol. opt. (w) – f(w) 33 de résolution graphique • Méthodes pour problème ne comportant que deux variables • Revenons au problème du restaurateur après l’avoir transformer en un problème de min: min z = -8x- 6y Sujet ? 5x + 30 2x + gy 24 x,yàO Domaine réalisable • Traçons la droite 5x + = 30 L’ensemble des points qui satisfont la contrainte 5x + gy 30 sont sous cette droite car l’origine satisfait cette relation 2x+ = 24 2x gy 24 BY = 18 x + 18 sont sous cette droite car PAGF 37 -O ety=O z -O x=Oety=6=>z= – 36 X+3y=18 Résolution • Considérons la fonction economque • Plus on s’éloigne de l’origine, plus la valeur diminue: – 48 5x+3y=300 0x-6 y=ooo ony=o 5x+3y=30 économique : z = -8x – 6y. • Plus on s’éloigne de forigine, 5 z — – 54. x=6ety- x=3ety 48 3 Transformons les contraintes d’inégalité du problème du restaurateur en égalité avec les variables d’écart u, p et h: min z = min z – 5x + 3y + u 2x + 24 + p =24 IX + 18 •h=18 x, y, u, p, h 20 • Les contraintes constituent un système de 3 équations omportant 5 variables.
Exprimons 3 des variables en fonction des 2 autres Méthode du simplexe – forme algébrique variables. Exprimons 3 des variables en fonction des 2 autres: 30 p 24 -2x-3y h = 18-1x-3Y • En fixant x et y nous retrouvons les valeurs des autres variables. • Il suffit de trouver les valeurs non né atives de x et y qui entraînent des PAGF s 7 la valeur de x, ou bien celle de y, ou bien celles des deux. • Mais nous choisissons d’augmenter la valeur d’une seule variable. • Puisque nous cherchons à minimiser z, il est avantageux d’augmenter la aleur de x puisque pour chaque augmentation d’une unité de x e ntraîne une diminution de 8 unités de z.
Augmentation limitée de la variable qui augmente • Mais l’augmentation de x est limitée par les contraintes de non négativité des variables u, p et h: – 30 – =24-2x-3YÈO • Puisque la valeur de y est maintenue à O, ceci est équivalent ? 30/5-6 = 24-2″ > o xg24/2=12 = 18- XÉ18 • Donc la solution demeure réalisable aussi longtemps que min (6, 12, 18} 6. Nouvelle solution 3 – 8x – 6y La nouvelle solution est donc x = 6, y = u = O, p = 12, h = 12 et z = —48. Cette solution est la seule pour le système précédent lorsque y = puisque la matrice des coefficients des variables u, p et h est non singulière. Par conséquent, pour retrouver une autre solution différente, il faut que y ou u prennent une valeur positive. Précédemment, ranalyse était facilitée par le fait que les variables x et y qui pouvaient être modifiées étaient à droite. Transformation du système • Isolons donc y et u du côté droit des équations. ?? Utilisons l’équation où x et u apparaissent pour exprimer x en fonction de u = 30 – 5x -3y 5x = 30 = 24-2x-3y = 18 -1x-3y et y: 0 – 5x-3y (5x 30 0-3 PAGF 7 7 3/5y -24-2x 3y p = 24-2(6 – – 3/5Y)-3Y p = 12 – 9/5}/ = 18-1x 3Y z = O — 8x —6y • Substituons la valeur de x dans les autres équations = 30 — 5x —3y x = 24 – 2x- 3y = 12 + – = 18-1x-3y 18-(6- 1/5u-3/5y)-3y 12+ – 12/5y z=o-8x-6Y • Utilisons l’équation où x et u a araissent pour exprimer x en 48 + 8/5u – 6/5y Système équivalent • Nous obtenons un nouveau système équivalent au précédent (dans le sens où les deux systèmes ont les mêmes solutions réalisables) • Notons qu’il n’est pas intéressant d’augmenter u car alors la valeur de z augmente ?? Nous répétons le processus précédent en augmentant la valeur de y = 12+ 2/5u – 9/5y = 12+ 1/511 – 12/5Y + 8/5u – 6/5y Nouvelle itération • Mais raugmentation de y est limité par les contraintes de non négativité des variables x, pet h: 1/5u-3/5Y>O 12+ 2/5u – 9/5y 12+ 1/5u- • puisque la valeur de u est maintenue à O, cecl est équlvalent ? = 6-3/5po YS 10 = 12- PAGF 33 O et z Solution optimale • Isolons donc h et u du côté drolt des équations. • Utilisons l’équation où y et h apparaissent pour exprimer y en fonction de h et u. ?? Substituons la valeur de y dans les autres équations. ?? Le système devient = 3- 1/4u+ 1/4h 3 1 + 3/-4h -5 + 1/12u – 5/12h – 54 + + 1/2h • La solution y -5, u = O, x — 3, p 3, h = O (dont la valeur z- donc optimale puisque les coefficients de u et h sont positifs. • En effet la valeur de z ne peut qu’augmenter lorsque u ou h augmente. Type de solutions considérées • Nous n’avons considéré que des solutions où il n’y a que trois variables positives! • Comme il ya 5 variables, il y a au plus CIC] CIC] = = 10 solutions n 3D3! 22 différentes de ce type. • Pourrait-il exister une meilleure solution qui aurait un nombre de variables
