PHPSimplex
Optimiser les ressources avec Optimisation Linéaire
Exemple (partie 1): méthode du Simplexe
Résoudre moyennant la méthode du Simplexe le prochain problème:
| Maximiser | Z = f(x,y) = 3x + 2y |
| sous les contraintes: | 2x + y ≤ 18 |
| 2x + 3y ≤ 42 | |
| 3x + y ≤ 24 | |
| x ≥ 0 , y ≥ 0 |
On considère les étapes suivantes:
- Réaliser un changement de variables et normaliser le signe des termes indépendants.
On effectue un changement dans la nomenclature des variables. La correspondance suivante s'établie:
- x devient X1
- y devient X2
étant positives les termes indépendants de toutes les contraintes il ne faut rien faire. Dans le cas contraire, il faudrait multiplier par "-1" dans les deux côtés de l'inéquation (en tenant compte que cette opération affecte aussi au type de contrainte).
- Normaliser les contraintes.
On transforme les inéquations en équations avec l'addition de variables d'écart, d'excès et artificielles selon le tableau suivant:
Forme d'inégalité Forme de la nouvelle variable ≥ - excès + artificielle = + artificielle ≤ + écart Dans ce cas, on introduit une variable d'écart (X3, X4 y X5) dans chacune des contraintes de la forme ≤, pour les transformer en égalités, avec ce résultat en équations linéaires:
2·X1 + X2 + X3 = 18 2·X1 + 3·X2 + X4 = 42 3·X1 + X2 + X5 = 24 - Ajuster la fonction objective à zéro.
Z - 3·X1 - 2·X2 - 0·X3 - 0·X4 - 0·X5 = 0
- écrire le tableau initial de la méthode du Simplexe.
Le tableau initial de la méthode du Simplexe est composé par tous les coefficients des variables de décision du problème original et les variables d'écart, excès et artificielles ajutées dans la deuxième étape (dans les colonnes, étant P0 0 le terme indépendant et le reste de variables Pi sont les mêmes que Xi), et les contraintes (dans les lignes). La colonne Cb a les coefficients des variables qu'on trouve dans la base.
La première ligne se compose des coefficients de la fonction objective, alors que la dernière ligne possède la valeur la fonction objective et les coûts réduits Zj - Cj.
On calcule la dernière ligne de la manière suivante: Zj = Σ(Cbi·Pj) pour i = 1..m, où si j = 0, P0 = bi et C0 = 0, et dans le cas contraire Pj = aij. Malgré d'être le premier tableau de la méthode du Simplexe et que tous les Cb sont nuls, on peut simplifier le calcul pour cette fois et disposer Zj = -Cj.
Tableau I . Itération 1ère 3 2 0 0 0 Base Cb P0 P1 P2 P3 P4 P5 P3 0 18 2 1 1 0 0 P4 0 42 2 3 0 1 0 P5 0 24 3 1 0 0 1 Z 0 -3 -2 0 0 0
- Condition d'arrêt.
Si l'objectif est la maximisation, quand dans la dernière ligne (ligne indicatrice) n'existe aucune valeur négative parmi les coûts réduits (colonnes P1 en avance), on obtient la condition d'arrêt.
Dans ce cas, on attend la fin de l'algorithme puisqu'on ne peut pas l'améliorer. La valeur de Z (colonne P0) est la solution optimale du problème.
Un autre cas possible, c'est que dans la colonne de la variable qui rentre en base toutes les valeurs sont négatives ou nuls. Indicative que le problème ne se trouve pas délimité et sa solution peut toujours être amélioré. Face à cette situation il n'est pas nécessaire de continuer réitérant indéfiniment et aussi on peut mettre fin à l'algorithme.
Lorsque cette condition n'est pas remplie, on exécute les processus suivants itérativement.
- élection de la variable entrante et sortante de la base.
D'abord, on établit la variable qui rentre en base. A cet effet, on choisit la colonne dont sa valeur dans la ligne Z est le plus basse entre tous les négatifs. Dans ce cas, cela serait la variable X1 (P1) de coefficient -3.
S'il y aurait deux ou plus de coefficients pareils qui satisfont aux conditions précédentes (en cas d'égalité), on choisira la variable de base.
La colonne de la variable qui rentre en base qu'on appelle colonne-pivot (en couleur vert).
Une fois obtenue la variable entrante en base, on détermine quelle sera la variable sortante. On prend la décision sur la base d'un simple calcul : diviser chaque terme indépendant (colonne P0) entre l'élément correspondant de la colonne-pivot, à condition que les deux éléments soient strictement positifs (supérieures à zéro). On opte par la ligne dont le résultat est minimal.
S'il y aurait un élément plus bas ou égal à zéro on n'effectue pas ce quotient. Lorsque tous les éléments de la colonne-pivot sont de cette condition on aurait accompli la condition d'arrêt et le problème aurait une solution sans partie bornée (voir la théorie de la méthode du Simplexe).
Dans cet exemple: 18/2 [=9] , 42/2 [=21] y 24/3 [=8]
Le terme de la colonne-pivot qui avait entraîné le plus petit quotient positif dans la division précédente indique la ligne de la variable d'écart qui sort de base. Dans ce cas, il se révèle X5 (P5), de coefficient 3. Cette ligne s'appelle ligne pivot (en couleur vert).
Au moment de calculer les quotients, si deux ou plus de résultats respectent la condition d'élection de l'élément qui sort de base (en cas d'égalité), on ne choisit pas les variables basiques (lorsque cela est possible).
L'intersection de la ligne pivot et la colonne pivot fait ressortir l'élément pivot, dans ce cas le 3.
- Actualiser le tableau.
On calcule les nouveaux coefficients du tableau de la manière suivante:
- Dans la ligne d'élément pivot de chaque nouvel élément est calculée en tant que:
Élément ligne pivot = Élément ancienne ligne pivot / Pivot
- Dans les lignes restantes chaque élément est calculé:
Nouvel élément ligne = Élément ancienne ligne - (Élément ancienne ligne en colonne pivot * Nouvel élément ligne pivot)
Ainsi on normalise l'élément pivot et sa valeur devient 1, alors que le reste d'éléments de la colonne pivot s'annulent (analogue à la méthode de Gauss-Jordan).
On montre les calculs pour la ligne P4:
Ancienne ligne P4 42 2 3 0 1 0 - - - - - - élément ancienne ligne en colonne pivot 2 2 2 2 2 2 x x x x x x Nouvelle ligne pivot 8 1 1/3 0 0 1/3 = = = = = = Nouvelle ligne P4 26 0 7/3 0 1 -2/3 Le tableau correspondant à cette deuxième itération est:
Tableau II . Itération 2ème 3 2 0 0 0 Base Cb P0 P1 P2 P3 P4 P5 P3 0 2 0 1/3 1 0 -2/3 P4 0 26 0 7/3 0 1 -2/3 P1 3 8 1 1/3 0 0 1/3 Z 24 0 -1 0 0 1 - Dans la ligne d'élément pivot de chaque nouvel élément est calculée en tant que:
- Après vérification de la condition d'arrêt, on s'aperçoit que parmi les éléments de la dernière ligne existe un numéro négatif, -1. On répète l'itération et on refait les processus 6 et 7.
- 6.1. La variable entrant en base est X2 (P2), variable qui correspond à la colonne où se trouve le coefficient -1.
- 6.2. Afin de calculer la variable qui sort, on divise les termes de la colonne P0 entre les termes correspondants de la nouvelle colonne pivot : 2 / 1/3 [=6] , 26 / 7/3 [=78/7] et 8 / 1/3 [=24] et comme le quotient positif le plus petit est 6, la variable qui sort est X3 (P3).
- 6.3. L'élément pivot est 1/3.
- 7. Si on actualise de nouveau les valeurs du tableau, on obtient:
Tableau III . Itération 3ème 3 2 0 0 0 Base Cb P0 P1 P2 P3 P4 P5 P2 2 6 0 1 3 0 -2 P4 0 12 0 0 -7 1 4 P1 3 6 1 0 -1 0 1 Z 30 0 0 3 0 -1
- Parmi les éléments de la ligne indicatrice verte, il y a encore un élément négatif, -1. Cela veut dire qu'on n'a pas obtenu la solution optimale et qu'on doit continuer à itérer (processus 6 et 7):
- 6.1. La variable entrant en base est X5 (P5), correspondant au coefficient -1.
- 6.2. On choisit la variable sortante en calculant le quotient entre les termes de la colonne de termes indépendants et les termes correspondants de la nouvelle colonne pivot : 6/(-2) [=-3] , 12/4 [=3], y 6/1 [=6] le quotient positif plus petit est 3, la variable sortante est X4 (P4).
- 6.3. L'élément pivot est 4.
- 7. Une fois actualisé tous les tableaux, on obtient le tableau suivant:
Tableau IV . Itération 4ème 3 2 0 0 0 Base Cb P0 P1 P2 P3 P4 P5 P2 2 12 0 1 -1/2 1/2 0 P5 0 3 0 0 -7/4 1/4 1 P1 3 3 1 0 3/4 -1/4 0 Z 33 0 0 5/4 1/4 0
- Fin de l'algorithme.
On découvre que dans la dernière ligne tous les coefficients sont positifs. On a accompli alors la condition d'arrêt.
La solution optimale est due à la valeur de Z dans la colonne des termes indépendants (P0), dans cet exemple: 33. Dans la même colonne, on peut avertir le point où on atteint, examinant les lignes correspondants aux variables de décision qui ont rentré en base: X1 = 3 y X2 = 12.
Si on annule le changement de variables, on obtient x = 3 e y = 12.
