Méthode simplex de programmation linéaire
Méthode simplex de programmation linéaire!
Tout problème de programmation linéaire impliquant deux variables peut être facilement résolu à l'aide d'une méthode graphique, car il est plus facile de traiter un graphique en deux dimensions. Toutes les solutions possibles de la méthode graphique se situent dans la zone réalisable du graphique et nous avons utilisé pour tester les points d’angle de la zone réalisable afin de déterminer la solution optimale, c’est-à-dire l’un des points d’angle de la zone réalisable utilisée comme solution optimale. Nous avions l'habitude de tester tous les points de coin en plaçant ces valeurs dans une fonction objective.
Mais si le nombre de variables augmente de deux, il devient très difficile de résoudre le problème en traçant son graphique, car le problème devient trop complexe. La méthode simplex a été développée par GB Dantzig, un mathématicien américain.
Cette méthode est un traitement mathématique de la méthode graphique. Ici aussi, différents points d'angle de la zone réalisable sont testés pour optimiser. Mais il n'est pas possible de tester tous les points de coin, car le nombre de points de coin augmente avec la multiplicité à mesure que le nombre d'équations et de variables augmente. Le nombre maximum de ces points à tester peut être
m + n m = m + 1! / m! n!
où m est le nombre de et n le nombre de variables.
Dans la méthode simplex, le nombre de points de coin à tester est donc considérablement réduit grâce à l’utilisation d’un algorithme très efficace qui permet d’obtenir un point de solution optimal en quelques itérations. Prenons un exemple et procédons étape par étape.
La fonction objectif est de maximiser Z = 12x 1 + 15x 2 + 14x 3
Soumis à conditions
Étape 1:
(a) Le côté droit de toutes les contraintes doit être zéro ou + ve. S'ils sont -ve alors ils doivent être rendus en multipliant les deux côtés par (-1) et le signe d'inégalité serait inversé. Dans cet exemple, RHS est déjà + ve ou zéro.
(b) Toutes les inégalités sont converties en égalités en ajoutant ou en soustrayant des variables vides ou excédentaires. Ces variables de jeu ou de surplus sont introduites car il est plus facile de traiter les égalités que les inégalités dans le traitement mathématique.
Si la contrainte est ≤ type, les variables de jeu sont ajoutées si la contrainte est ≥ type, la variable excédentaire est soustraite. Ici, les variables de jeu s, s 2 et s 3 sont ajoutées en trois dans les égalités (i), (ii) et (iii), nous obtenons.
Et la fonction objective devient
Maximiser Z = 12x 1 + 15x 2 + 14x 3 + os 1 + os 2 + os 3
Étape 2:
Trouver la solution de base réalisable initiale:
Nous commençons avec une solution réalisable, puis passons à la solution optimale lors des prochaines itérations. La solution réalisable initiale est de préférence choisie comme étant l’origine, c’est-à-dire où les variables régulières, par exemple dans ce cas, x v x 2, x 3 prennent des valeurs nulles. soit x 1 x 2, x 3 = 0
et nous obtenons s 1 = 0, s 2 = 0 et s 3 = 100 des inégalités (i), (ii) et (iii)
Les variables de base sont les variables qui figurent actuellement dans la solution. Par exemple, S v S 2 et S 3 sont les variables de base de la solution initiale.
Les variables non basiques sont les variables égales à zéro et qui ne font pas partie de la solution actuelle. Par exemple, x 1, x 2 et x 3 sont les variables non basiques de la solution initiale.
Les informations ci-dessus peuvent être exprimées dans le tableau 1
Dans le tableau, la première ligne représente les coefficients de la fonction objectif, la deuxième ligne représente différentes variables (premières variables régulières, puis variables lentes / excédentaires). Les troisième, quatrième et cinquième lignes représentent les coefficients des variables dans toutes les contraintes.
La première colonne représente les coefficients des variables de base (variables de solution actuelles) dans l'objectif (e i ), la seconde colonne représente les variables de base (variables de solution actuelles) et la dernière colonne représente, du côté droit des contraintes, sous forme standard. C'est-à-dire qu'après avoir encombré toutes les inégalités en égalités, dans n'importe quel tableau, les valeurs actuelles des variables de solution actuelles (variables de base) sont données par RHS.
Dans le tableau 1, la solution actuelle est la suivante:
S 1 = 0, S 2 = 0, S 3 = 100
Bien entendu les variables non basiques X v X 2 et X 3 seront également nulles
Dégénérescence chaque fois qu'une variable de base prend une valeur nulle, la solution actuelle est dite dégénérée, car dans le problème actuel S 1 = 0 et S 2 = 0, le problème peut être résolu en remplaçant S 1 = t et S 2 = t où t est très petit nombre + ve.
Étape 3:
Test d'optimalité.
Un test d'optimalité peut être effectué pour déterminer si la solution actuelle est optimale ou non. Pour cette première écriture, écrivez la dernière ligne sous la forme de (E j ) où
Ej = Σ ei. Un ij.
Où a ij représente les coefficients de la matrice d’identité du corps pour la sixième ligne de la rangée, c’est-à-dire la première colonne du tableau. Dans la dernière ligne, écrivez la valeur de (Cj - Ej) où c ; représente les valeurs de la première ligne et E j représente les valeurs de la dernière ligne. (Cj - Ej) représente l'avantage d'apporter toute variable non basique à la solution actuelle, c'est-à-dire en la rendant basique.
Dans le tableau 2, les valeurs de Cj - Ej sont 12, 15 et 14 pour X v X 2 et X 3 . Si l'une des valeurs de Cj - Ej est + ve, cela signifie que la plupart des valeurs positives représentent la variable introduite dans la solution actuelle augmenterait la fonction objectif au maximum. Dans le cas présent, X 2 est la variable potentielle à entrer dans la solution pour la prochaine itération. Si toutes les valeurs de la ligne (Cj - Ej) sont négatives, cela signifie que la solution optimale a été atteinte.
Étape 4:
Itérer vers la solution optimale:
Maximum la valeur de Cj - Ej donne la colonne clé comme indiqué dans le tableau
Par conséquent, X 2 est la variable entrante, c’est-à-dire qu’il deviendrait fondamental et entrerait dans la solution. Hors de la variable non basique existante, il faut sortir et devenir non basique. Pour trouver quelle variable doit être supprimée, divisez les coefficients de la colonne RHS par les coefficients correspondants dans la colonne clé pour obtenir la colonne Ratio. Recherchez maintenant la valeur la moins positive dans la colonne Ratio et cela donnerait la ligne de clé. Dans le problème actuel, nous avons trois valeurs, t, µ et 100, et parmi celles-ci, t est la plus faible. Par conséquent, la ligne correspondant à t dans la colonne Ratio serait la ligne de clé. Et S., serait la variable de départ. L'élément à l'intersection de la ligne et de la colonne de clé est l'élément clé.
Maintenant, tous les éléments de la colonne clé, à l'exception de l'élément clé, doivent être mis à zéro et l'élément clé à l'unité. Ceci est fait à l'aide des opérations de lignes comme c'est le cas pour les matrices. Ici, l'élément clé est déjà unité et les autres éléments de la colonne clé sont mis à zéro en ajoutant -1 fois la première ligne de sa troisième ligne et obtenir le tableau suivant.
Par conséquent, la deuxième solution possible devient
X 1 = 0, X 2 = t et X 3 = 0 par z = 15t
Dans le nouveau tableau, s 1 a été remplacé par X 2 dans les variables de base et, par conséquent, la colonne a également été modifiée.
Étape 5:
En examinant les valeurs Cj -Ej du tableau 3, nous constatons que x 1 a les valeurs les plus positives de 27, indiquant de ce fait que la solution peut être encore améliorée en intégrant x 1 dans la solution, c'est-à-dire en la rendant basique. Par conséquent, x 1 colonne est la colonne clé, recherchez également la ligne de clé comme expliqué précédemment et complétez le tableau 5.
L’élément clé du tableau 5 s’avère être 2 et il est fait unité. Tous les autres éléments de la colonne clé sont mis à zéro à l’aide des opérations sur les lignes et nous obtenons enfin le tableau 6. Le premier élément clé est créé en divisant cette ligne par 2. Ensuite, en ajoutant des multiples appropriés de cette ligne dans une autre, nous obtenons le tableau 6.
Le tableau 6 montre que la solution n’est pas optimale, car Cj-Ej a toujours une valeur égale à 1/2, elle donne la colonne clé et la ligne correspondante est trouvée, l’élément clé correspondant à celui indiqué dans le tableau 7.
Maintenant, par des opérations de rangées appropriées, nous faisons d’autres éléments dans la colonne clé nuls, comme indiqué dans le tableau 8.
On peut constater que puisque toutes les valeurs de la ligne Cj-Ej sont soit -ve, soit zéro, la solution optimale a été atteinte.
La solution finale est x 1 = 40 tonnes
x 2 = 40 tonnes
x 3 = 20 tonnes
comme t est très petit, il est négligé.
Exemple 1:
Résoudre le problème suivant par la méthode simplex
Maximiser Z = 5x 1 + 4x 2
Sous réserve de 6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6
-x 1 + x 2 ≤ 1
x 2 ≤ 2
et x 1 x 2 ≥0
Solution:
Ajoutez les variables de jeu S 1, S 2, S 3, S 4 dans les quatre contraintes pour éliminer les inégalités.
Nous obtenons 6x 1 + 4x 2 + s 1 = 24
x 1 + 2x 2 + s 2 = 6
-x 1 + x 2 + s 3 = 1
x 2 + s 4 = 2
Sous réserve de x 1, x 2, s 1, s 2, s 3 et s 4 > 0
La fonction objective devient
Maximiser Z = 5x 1 + 4x 2 0s 1 + 0s 2 + 0s 3 + 0s 4
Le tableau 1 qui est formé est donné ci-dessous. On peut voir que X 1 est la variable entrante et S, la variable sortante. L'élément clé dans le tableau 1 devient l'unité et tous les autres éléments de cette colonne sont mis à zéro.
Le tableau 2 peut indiquer que X 2 est la variable entrante et S 2, la variable sortante.
Le tableau 5 montre que toutes les valeurs de la ligne Cj-Ej sont -ve ou zéro. Par conséquent, la solution optimale a été obtenue.
La solution est x 1 = 3, x 2 = 3/2
Z max = 5x 3 + 4x = 3/2
= 15 + 6 = 21 Ans.
Big M- Méthode
Prenons le problème suivant pour illustrer la méthode Big M.
Réduire Z = 2y 1 + 3y 2
sous réserve de contraintes y 1 + y 2 ≥ 5
y 1 + 2y 2 ≥ 6
y 1, y 2 ≥ 0
Conversion en format standard:
Maximiser Z = -2y 1 - 3y 2 + Os, + 0s 2
c'est-à-dire que le problème de minimisation est converti en problème de maximisation en multipliant RHS de la fonction objectif par -1.
Contraintes y 1 + y 2 - s 1 = 6… (i)
y, + y 2 - s 2 = 6… (ii)
y 1 y 2, s 1 s 2 ≥ 0
Ici, les variables excédentaires s1, s2 et soustraites des contraintes (i) et (ii) respectivement.
Maintenant, y 1, y 2 peuvent être pris comme variables non basiques et mis égal à zéro pour obtenir s v s 2 comme variables basiques où s 1 = -5, s 2 = -6.
C'est une solution irréalisable car les variables excédentaires s 1 et s 2 ont des valeurs -ve. Afin de résoudre ce problème, nous ajoutons les variables artificielles A 1 et A 2 dans l'équation. (i) et (ii) respectivement pour obtenir
y 1 + y 2 –s 1 + A 1 = 5… (iii)
y 1 + 2y 2 - s 2 + A 2 = 6… (iv)
Où y 1 y 2, s 1, s 2, A 1, A 2 ≥ 0
et la fonction objective devient
Maximiser Z 1 = -2y 1 - 3y 2 + 0s 1 + 0s 2 - MA 1 - MA 2
On peut constater que nous avons délibérément appliqué de très lourdes pénalités aux variables artificielles de la fonction objectif sous la forme de -MA1 et MA 2, où M est un très grand nombre +. Le but est que les variables artificielles apparaissent initialement dans la solution de base de départ.
Parce que les variables artificielles diminuent très largement la fonction objectif en cas de pénalités, l'algorithme simplex élimine les variables artificielles de la solution lors des itérations initiales. Par conséquent, les variables artificielles introduites pour résoudre le problème n'apparaissent pas dans la version finale. Solution. Les variables artificielles ne sont qu'un appareil de calcul. Ils maintiennent les équations de départ en équilibre et fournissent une astuce mathématique pour obtenir une solution de départ.
La table initiale devient
Puisque Cj-Ej est + ve dans certaines colonnes, la solution donnée par le tableau 1 n’est pas optimale. On peut voir que sur -2 + 2M et -3 + 3M, -3 + 3M est le plus positif, M étant un très grand nombre + ve. L'élément clé se trouve comme indiqué dans le tableau 1; l'unité et tous les autres éléments de cette colonne sont mis à zéro. Nous obtenons le tableau 2.
Le tableau 2 montre que la solution optimale n’est toujours pas atteinte et qu’il existe une meilleure solution. Y 1 est la variable entrante et A 1 est la variable sortante. Nous obtenons le tableau 3.
Le tableau 3 montre que la solution optimale a été atteinte et que la solution est
Y 1 = 4, Y 2 = 1
Valeur minimale de Z = 2x 4 + 3x 1 = 11 unités Ans.
Solution non liée:
Un problème de programmation linéaire est réputé avoir une solution illimitée lorsque, dans la colonne des ratios, nous obtenons toutes les entrées, soit -ve ou zéro, et il n'y a aucune entrée + cinq. Cela indique que la valeur de la variable entrante sélectionnée dans la colonne clé peut être aussi grande que nous le souhaitons sans violer la condition réalisable et que le problème est réputé avoir une solution illimitée.
Nombre infini de solutions:
On dit qu'un problème de programmation linéaire a un nombre infini de solutions si, lors d'une itération quelconque, dans la ligne Cj-Ej, nous avons toutes les valeurs nulles ou -ve. Cela montre que la valeur optimale est atteinte. Mais comme l'une des variables régulières a une valeur zéro dans la ligne Cj-Ej, on peut en conclure qu'il existe une solution optimale alternative.
Un exemple de ce type de tableau est donné ci-dessous.
On peut voir que la solution optimale a été atteinte puisque toutes les valeurs de la ligne Cj-Ej sont nulles ou égales à -ve. Mais X 1 est une variable non basique et sa valeur est 0 dans la ligne Cj-Ej, cela indique que X peut être importé. solution, mais cela n’augmentera pas la valeur de la fonction objective et il existe une alternative optimale.
Cas de solution envisageable:
Dans certains LPP, on peut constater que, tout en résolvant le problème des variables artificielles, la ligne Cj-Ej montre que la solution optimale est atteinte, alors que la solution actuelle contient toujours une variable artificielle ayant une valeur de + vp. Dans de telles situations, on peut en conclure que le problème n’a aucune solution réalisable.
Exemple 2:
Solution:
Afin de résoudre le problème, des variables artificielles devront être ajoutées dans LHS afin d'obtenir la solution de base réalisable initiale. Introduisons les variables artificielles A 1, A 2, A 3, les contraintes ci-dessus peuvent être écrites comme.
Maintenant, si ces variables artificielles apparaissent dans la solution finale en ayant quelques valeurs + v, alors l'égalité de l'équation soit (i), (ii) ou (iii) est perturbée. Par conséquent, nous souhaitons que les variables artificielles ne figurent pas dans la solution finale et appliquons par conséquent une pénalité importante à la fonction objectif, qui peut être écrite ainsi.
Maximiser Z = Y, + 2Y 2 + 3Y 3 - Y 4 - MA, - MA 2 - MA 3
Maintenant, si nous prenons y 1 Y 2, y 3 et y 4 comme variables non fondamentales et mettons Y 1 = Y 2 = y 4 = 0, nous obtenons la solution initiale sous la forme A 1 = 15, A 2 = 20 et A 3 = 10 et A 1, A 2, A 3 et A 4 sont des variables de base (variables dans la solution actuelle) pour commencer. Les informations ci-dessus peuvent être mises dans le tableau 1.
AS Cj-Ej est positif, la solution actuelle n’est pas optimale et une meilleure solution existe donc.
Itérer vers une solution optimale
Effectuer des itérations pour obtenir une solution optimale, comme indiqué dans le tableau ci-dessous.
Puisque Cj-Ej est nul ou négatif dans toutes les colonnes, la solution de base optimale réalisable a été obtenue. Les valeurs optimales sont
Y 1 = 5/2, Y 2 = 5/2, Y 3 = 5/2, Y4 = 0
Aussi A 1 = A 2 = 0 et Z max = 15 Ans.
