PHPSimplex

Optimiser les ressources avec Optimisation Linéaire



Théorie de la méthode du Simplexe

Adaptation du modèle à la méthode du Simplexe
Type d'optimisation.
Inscrivez changement des termes indépendants
Normalisation des contraintes
Développement de la méthode du Simplexe
Méthode du Simplexe
Méthode des Deux Phases
Identifier des anomalies et des solutions
Méthode Graphique
Exemple de la méthode du Simplexe
Exemple de la méthode Graphique
Comparaison de la méthode du Simplexe et Graphique

 

La méthode du Simplexe est une procédure itérative qui permet d'améliorer la résolution de la fonction objectif à chaque étape. Le processus se termine lorsque vous ne pouvez pas continuer à améliorer la valeur, c'est-à-dire, on a atteint la solution optimale (la valeur la plus élevée ou la plus basse possible, selon le cas).

à partir de la base de la valeur de la fonction objectif en un point quelconque, le procédé est de trouver un autre point qui améliore la valeur précédente. Comme indiqué dans la méthode Graphique, ces points sont les sommets du polygone (ou polyèdre ou polychore, si le nombre de variables est supérieur à deux), qui est la région déterminée par les contraintes que le problème est soumis (dite région faisable). La recherche est effectuée par les déplacements des arêtes du polygone, du sommet courant jusqu'à un élément adjacent qui permet d'améliorer la valeur de la fonction objectif. Chaque fois que la région faisable sera présente, vu que le nombre de sommets et d'arêtes est fini, il est possible de trouver la solution.

La méthode du Simplexe est basé sur la propriété suivante: si la fonction objectif Z ne prend pas sa valeur maximale au niveau du sommet A, puis, il y a une arête dont le point de départ est A et le long de laquelle la valeur de Z augmente.

Il sera nécessaire de tenir compte que la méthode du Simplexe fonctionne uniquement avec les contraintes du problème dont les contraintes sont du type "≤" (inférieur ou égal) et ses coefficients indépendants sont supérieurs ou égaux à 0. Ainsi, les restrictions devraient être normalisées pour répondre à ces exigences avant de commencer l'algorithme du Simplexe. Dans le cas où les contraintes de type "≥" (supérieur ou égal) ou "=" (égal) apparaissent après ce processus, ou on ne peut pas les modifier, il sera nécessaire d'utiliser d'autres méthodes de résolution, étant la méthode de Deux Phases la plus courante.

Adaptation du modèle à la méthode du Simplexe

La forme standard du modèle de problème consiste d'une fonction objectif sous des contraintes déterminées:

Fonction objectif: c1·x1 + c2·x2 + ... + cn·xn
sous les contraintes: a11·x1 + a12·x2 + ... + a1n·xn = b1
a21·x1 + a22·x2 + ... + a2n·xn = b2
...
am1·x1 + am2·x2 + ... + amn·xn = bm
x1,..., xn ≥ 0

Le modèle doit accomplir les conditions suivantes:

  1. L'objectif sera de maximiser ou minimiser la valeur de la fonction objectif (par exemple, augmenter les bénéfices ou réduire les pertes, respectivement).
  2. Toutes les contraintes doivent être des équations d'égalité (identités mathématiques).
  3. Toutes les variables (Xi) doivent être une valeur positive ou nulle (condition de non-négativité).
  4. Les termes indépendants (bi) de chaque équation doivent être non négatifs.

Nous devons adapter la modélisation du problème à la forme standard pour l'application de l'algorithme du Simplexe.

Type d'optimisation.

Comme mentionné précédemment, l'objectif de la méthode sera d'optimiser la valeur de la fonction objectif. Mais, il y a deux options: obtenir la valeur optimale supérieure (maximiser) ou d'obtenir la valeur optimale inférieure (minimiser).

Il y a également des différences dans l'algorithme entre l'objectif de maximisation et celui de la minimisation à propos du critère de condition d'arrêt pour terminer les itérations et les conditions d'entrée et de sortie de la base. Ainsi:

Cependant, il est possible de normaliser l'objectif du problème afin de toujours appliquer les mêmes critères par rapport à la condition d'arrêt de l'algorithme et les conditions d'entrée et sortie des variables de la base. De cette façon, si l'objectif est de minimiser la solution, on peut changer le problème à un autre équivalent de maximisation, simplement en multipliant la fonction objectif par "-1". Autrement dit, le problème de minimiser Z est équivalent au problème de maximisation (-1)·Z. Une fois la solution obtenue, il faudra aussi la multiplier par (-1).

Avantages: Pas besoin de s'inquiéter par des nouveaux critères d'arrêt, de condition d'entrée ou de sortie de base puisqu'ils ne changent pas.

Inconvénients: Dans le cas où la fonction a tous les coefficients de ses variables basiques positifs, et en plus les contraintes sont du type d'inégalité "≤", si on effectue le changement de ces coefficients ils restent négatifs en accomplissant la condition d'arrêt dans la première itération (conformément à la ligne de la valeur de la fonction objectif, toutes les valeurs sont positives ou zéro). Obtenant dans ce cas par défaut, une valeur optimale pour la fonction égale à zéro.

Solution: Ce problème n'existe pas vraiment, étant donné que pour que la solution soit supérieur à zéro, il est nécessaire qu'une contrainte ait imposé la condition " ≥" (et il serait un modèle pour la méthode des Deux Phases). Dans le cas en question, la vraie solution doit être zéro.

Inscrivez changement des termes indépendants

On dit aussi que les termes indépendants (bi) de chaque équation doivent être non négatifs afin d'utiliser la méthode du Simplexe. à cette fin, si certaines des contraintes présentent un terme indépendant plus bas que 0 il faudra la multiplier par "-1" (en tenant compte du fait que cette opération affecte également au type de contrainte).

Avantages: Avec cette simple modification de signes dans les contraintes correspondantes on facilite l'application de la méthode du Simplexe au problème de la modélisation.

Inconvénients: On peut trouver que dans les contraintes où on doit modifier les signes des constantes, les types d'inégalités sont "≤" (après l'opération, ils resteront du type "≥"), donc il sera nécessaire de développer la méthode des Deux Phases. Cet inconvénient n'est pas maîtrisable, mais autrement il pourrait se produire dans le cas contraire et d'être bénéfique si les termes indépendants sont négatives dans toutes les contraintes d'inégalité de type "≥". S'il y a des contraintes du type "=" ils n'entraînent pas des avantages ou désavantages car il serait toujours nécessaire d'appliquer la méthode des Deux Phases.

Normalisation des contraintes

Une autre condition du modèle standard du problème est que toutes les contraintes sont des équations d'égalité (autrement dites, contraintes d'égalité), il faudra changer les contraintes d'inégalité ou les inéquations en ces identités mathématiques.

La condition de non-négativité des variables (x1, ..., xn ≥ 0) est la seule exception et reste identique.

Dans ce dernier cas, il est clair que les variables artificielles sont en violation des lois de l'algèbre, de sorte qu'il sera nécessaire d'assurer que ces variables artificielles ont une valeur de 0 dans la solution finale. Ceci est accompli par la méthode des Deux Phases et donc on devra toujours le faire chaque fois qu'on a ce genre de variables.

Le tableau suivant résume le type de variable qui apparaît dans l'équation normalisée et son signe selon les inégalités:

Forme d'inégalité Forme de la nouvelle variable
- excès + artificielle
= + artificielle
+ écart

Développement de la méthode du Simplexe

Une fois le modèle standardisé, il peut être nécessaire d'appliquer la méthode du Simplexe ou la méthode des Deux Phases. Voir dans la figure la manière d'actuation pour atteindre la solution du problème modélisé.

Algorithme du Simplexe

Les étapes de chaque méthode sont expliquées pas à pas ci-dessous, en précisant les aspects à prendre en considération.

Méthode du Simplexe
Méthode des Deux Phases

La méthode des Deux Phases est utilisée lorsque les variables artificielles apparaissent sous forme standard ou canonique du problème. La première phase vise à résoudre le problème auxiliaire Z' afin de minimiser la somme des variables artificielles et de le rendre nul (dans le but d'éviter les incohérences mathématiques). Après avoir résolu le premier problème, et tant qu'il est comme prévu le résultat, le tableau qui en résulte est réorganisé pour une utilisation dans la deuxième phase sur le problème d'origine.

Sinon, le problème n'est pas faisable, c'est-à-dire, il n'y a pas de solution et il ne faudra pas continuer avec la deuxième phase.

PHASE 1

Cette première étape est analogue à la méthode du Simplexe, à exception de la construction de le premier tableau, en plus d'avoir besoin de tenir compte du résultat obtenu pour déterminer si la deuxième phase se développe.

Dans ce cas, le dernier tableau de cette phase sera, avec quelques modifications, utilisée en tant que tableau initiale pour la deuxième phase.

PHASE 2

La deuxième phase de la méthode des Deux Phases est élaborée exactement comme la méthode du Simplexe, sauf qu'avant de commencer les itérations il faut supprimer les colonnes correspondantes aux variables artificielles, et reconstruire le tableau d'origine.

À partir de ce point, toutes les itérations, jusqu'atteindre la solution optimale du problème, ne montrent aucune différence avec la méthode du Simplexe.

Identifier des anomalies et des solutions

Solution optimale: lorsque la condition d'arrêt est accomplie et il n'y a pas des variables artificielles en base avec une valeur positive (les valeurs sont indiquées dans la colonne P0), l'optimalité est atteinte. La valeur Z0 actuelle est la solution optimale du problème, elle est accomplie pour les variables qui sont en base. Si c'est un problème de minimisation, la valeur optimale obtenue est multipliée par "-1".

Solutions infinies: accomplie la condition d'arrêt, si une variable de décision non-base a une valeur 0 dans la ligne Z, veut dire qu'il y a une autre solution qui fournit la même valeur optimale pour la fonction objectif. Dans ce cas, le problème admit une infinité de solutions, toutes comprises dans le segment (ou une partie du plan, région de l'espace, etc., selon le nombre de variables du problème) défini par A·X1 + B·X2 = Z0. Grâce à une nouvelle itération et en faisant que la variable de décision ayant 0 dans la ligne Z entre en base, une solution différente est obtenue pour la même valeur optimale.

Solution illimité (restreinte): si toute la colonne de la variable entrante en base a tous les éléments négatifs ou nuls, il s'agit d'un problème restreint, c'est-à-dire, qu'il a une solution illimitée. Il n'y a aucune valeur optimale spécifique pour la fonction objectif, mais lorsque la valeur des variables augmente, la valeur Z augmente également sans violer les contraintes.

Il n'y a pas de solution: lorsqu'aucun point ne satisfait toutes les contraintes du problème, l'infaisabilité se produit n'ayant pas de solution possible pour cela. Dans ce cas, après avoir fini toutes les itérations de l'algorithme, il y a des variables artificielles en base dont la valeur est supérieure à zéro.

Même résultat variable entrante: quand il y a une égalité dans la condition de décision de variables entrantes on peut choisir l'une d'elles sans affecter la solution finale. Par contre, il y a une influence dans le nombre d'itérations nécessaires pour obtenir la solution. Il est conseillé d'opter pour les variables de base, car elles sont celles qui feront partie de la solution optimale.

Même résultat variable sortante: on peut de nouveau choisir l'une d'elles. Toutefois, afin de ne pas prolonger le problème et d'éviter l'entrée dans une boucle sans fin (cas dégénéré), on discrimine en faveur des variables de décision pour qu'elles restent dans la base. Dans le cas d'être dans la première phase de la méthode des Deux Phases, on optera pour sortir de base les variables artificielles.

Curiosité en Phase 1: à la fin de la phase 1, si le problème initial a une solution, toutes les variables artificielles dans la ligne indicatrice doivent être réglées sur " 1".

Peut être nul l'élément pivot? Non, l'élément pivot est toujours strictement positif puisqu'on n'effectue que les quotients parmi de valeurs non négatives et supérieures à zéro (face à un problème de maximisation).

Copyright ©2006-2016 PHPSimplex. Tous droits réservés.
Suivez-nous sur Twitter
X

PHPSimplex
Version 0.81

Copyright ©2006-2016. Tous droits réservés.

Développé par:
Daniel Izquierdo Granja
Juan José Ruiz Ruiz

Traduction en langue anglais par:
Luciano Miguel Tobaria

Traduction en langue française par:
Ester Rute Ruiz