11.4. MÉTHODE DUAL SIMPLEX
Il découle des résultats des sections précédentes que pour obtenir une solution au problème original, nous pouvons passer au problème dual et, en utilisant des estimations de sa conception optimale, déterminer la solution optimale au problème original.
La transition vers le problème dual n'est pas nécessaire, car si l'on considère le premier tableau simplex avec une base supplémentaire unitaire, il est facile de voir que les colonnes contiennent le problème d'origine et que le problème dual est écrit dans les lignes.
Comme cela a été montré, lors de la résolution du problème direct à n'importe quelle itération, la différence, c'est à dire. ordre de grandeur -coefficient avec une variable, est égal à la différence entre les côtés droit et gauche de la contrainte correspondante du problème dual. Si, lors de la résolution d'un problème direct avec une fonction objectif maximisable, l'itération ne conduit pas à une solution optimale, alors au moins pour une variable et seulement dans l'optimum pour tous différence .
En considérant cette condition avec prise en compte de la dualité, on peut écrire
.
Ainsi, si, alors . Cela signifie que lorsque la solution du problème primal n'est pas optimale, la solution du problème dual est invalide. D'autre part 
à . Ceci implique que la solution optimale du problème primal correspond à une solution admissible du problème dual.
Cela a permis de développer une nouvelle méthode pour résoudre les problèmes de programmation linéaire, lors de l'utilisation de laquelle, dans un premier temps, une solution inacceptable, mais «meilleure qu'optimale» est obtenue (dans la méthode simplexe habituelle, d'abord admissible, mais sous-optimal la solution). Une nouvelle méthode appelée méthode double simplexe, assure la satisfaction de la condition d'optimalité de la solution et son "approximation" systématique au domaine des solutions réalisables. Lorsque la solution obtenue s'avère admissible, le processus itératif de calculs se termine, puisque cette solution est également optimale.
La méthode du double simplexe permet de résoudre des problèmes de programmation linéaire dont les systèmes de contraintes, à base positive, contiennent des termes libres de signe quelconque. Cette méthode permet de réduire le nombre de transformations du système de contraintes ainsi que la taille du tableau simplexe. Considérons l'application de la méthode du double simplexe à l'aide d'un exemple.
Exemple. Trouver le minimum d'une fonction 
sous restrictions
.
Passons à la forme canonique :
sous restrictions
Le tableau simplex initial a la forme
|
De base variables |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
La solution |
|
X 3 X 4 X 5 |
–3 –4 |
–1 –3 |
–3 –6 |
|||
|
–2 |
–1 |
Solution de base initialeoptimale, mais pas acceptable.
Comme la méthode habituelle du simplexe, la méthode de résolution considérée est basée sur l'utilisation de conditions d'admissibilité et d'optimalité.
Condition d'admissibilité. La plus grande variable de base négative en valeur absolue est choisie comme variable exclue (s'il existe des alternatives, le choix est fait arbitrairement). Si toutes les variables de base sont non négatives, le processus de calcul se termine, puisque la solution résultante est faisable et optimale.
Condition optimalité. La variable incluse dans la base est sélectionnée parmi les variables non fondamentales comme suit. Les rapports des coefficients du côté gauche sont calculés-équations aux coefficients correspondants de l'équation associée à la variable exclue. Les relations avec des dénominateurs positifs ou nuls ne sont pas prises en compte. Dans le problème de minimisation de la variable d'entrée, le plus petit des rapports indiqués doit correspondre, et dans le problème de maximisation, le rapport avec la plus petite valeur absolue (s'il y a des alternatives, le choix est fait arbitrairement). Si les dénominateurs de tous les rapports sont nuls ou positifs, le problème n'a pas de solution réalisable.
Après avoir choisi les variables à inclure dans la base et à exclure, l'opération habituelle de transformation des lignes du tableau simplex est effectuée pour obtenir la solution suivante.
Dans cet exemple, la variable exclue est. Les ratios calculés pour déterminer la nouvelle variable de base sont présentés dans le tableau suivant :
|
variables |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
|
L'équation X 4 - équation |
–2 –4 |
–1 –3 |
|||
|
Attitude |
La variable à inclure est X 2 . La conversion de chaîne suivante entraîne une nouvelle table simplex :
|
De base variables |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
La solution |
|
X 3 X 2 X 5 |
–1 –1 |
|||||
Nouvelle solution également optimal, mais toujours invalide. Comme nouvelle variable exclue, nous choisissons (arbitrairement) X 3 . Définissons une variable incluse.
|
variables |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
|
L'équation X 4 - équation |
|||||
|
attitude |
Méthode simplexe - c'est une méthode de passage successif d'une solution de base (le sommet du polyèdre solution) du système de contraintes d'un problème de programmation linéaire à une autre solution de base jusqu'à ce que la fonction but prenne la valeur optimale (maximum ou minimum).
La méthode du simplexe est une méthode universelle qui peut résoudre n'importe problème de programmation linéaire, tandis que la méthode graphique ne convient que pour un système de contraintes à deux variables.
La méthode du simplexe a été proposée par le mathématicien américain R. Danzig en 1947, depuis, pour les besoins de l'industrie, cette méthode résout souvent des problèmes de programmation linéaire avec des milliers de variables et de contraintes.
Avant de passer à l'algorithme de la méthode du simplexe, quelques définitions.
Toute solution non négative d'un système de contraintes est appelée solution acceptable .
Qu'il y ait un système m restrictions de n variables ( m n).
Solution de base admissible est une solution contenant m non négatif Majeur (de base ) variables et n - m non essentiel . (non basique, ou libre ) variables. Les variables non fondamentales dans la solution de base sont égales à zéro, tandis que les variables principales, en règle générale, sont non nulles, c'est-à-dire qu'il s'agit de nombres positifs.
N'importe quel m variable système méquations linéaires avec n les variables sont appelées principale , si le déterminant des coefficients à eux est différent de zéro. Puis le reste n - m les variables sont appelées non essentiel (ou libre ).
Algorithme de méthode simplexe
- Étape 1. Amenez le problème de programmation linéaire à la forme canonique. Pour cela, déplacez les termes libres vers les membres de droite (si parmi ces termes libres sont négatifs, alors multipliez l'équation ou l'inégalité correspondante par - 1) et introduisez des variables supplémentaires dans chaque contrainte (avec un signe plus, si dans le inégalité d'origine le signe est inférieur ou égal à ", et avec un signe moins si "supérieur ou égal à").
- Étape 2. Si dans le système résultant méquations, alors m prendre les variables comme principales, exprimer les variables principales en termes de variables non fondamentales et trouver la solution de base correspondante. Si la solution de base trouvée s'avère admissible, passez à la solution de base admissible.
- Étape 3. Exprimez la fonction de but en fonction des variables mineures de la solution de base réalisable. Si le maximum (minimum) de la forme linéaire est trouvé et qu'il n'y a pas de variables non fondamentales avec des coefficients négatifs (positifs) dans son expression, alors le critère d'optimalité est rempli et la solution de base résultante est optimale - la solution est terminée. Si, lors de la recherche du maximum (minimum) d'une forme linéaire, son expression contient une ou plusieurs variables non fondamentales à coefficients négatifs (positifs), passez à une nouvelle solution de base.
- Étape 4. Parmi les variables non fondamentales incluses dans la forme linéaire avec des coefficients négatifs (positifs), choisissez celle qui correspond au plus grand coefficient (modulo) et transférez-la aux principales. Passez à l'étape 2.
Conditions importantes
Certains cas particuliers sont traités dans des articles distincts : quand fonction objectif maximale - infini, lorsque le système n'a pas de solution, et quand la solution optimale n'est pas la seule .
Ensuite, nous analyserons un exemple typique, où le système de contraintes est cohérent et il existe un optimum fini, et un seul. Une variante de la méthode du simplexe est méthode de distribution pour résoudre le problème de transport .
Méthode simplexe avec tableaux simplexes
En construisant des tableaux simplex, il est beaucoup plus facile de résoudre un problème de programmation linéaire que par des transformations algébriques, ce qui est montré dans le paragraphe suivant. Les tableaux Simplex sont très visuels. Il existe plusieurs types de règles pour travailler avec des tables simplex. Nous analyserons la règle, qui est le plus souvent appelée règle de la colonne principale et de la ligne principale.
Il serait utile d'ouvrir le manuel Actions avec des fractions dans une nouvelle fenêtre : il y en a assez, des fractions dans les problèmes sur la méthode du simplexe, pour ne pas dire plus.
Exemple.
Nous introduisons des variables non négatives supplémentaires et réduisons ce système d'inégalités à un système d'équations équivalent
.
Ceci a été fait en respectant la règle suivante : si le signe dans la contrainte d'origine est "inférieur ou égal à", alors la variable supplémentaire doit être ajoutée, et si "supérieur ou égal à", alors la variable supplémentaire doit être soustrait.
Les variables supplémentaires introduites sont considérées comme les principales (de base). Alors et sont des variables non basiques (libres).
En exprimant les variables principales (de base) en termes de non-base (libre), nous obtenons
Nous exprimons également la fonction de but en termes de variables non basiques (libres) :
A partir des coefficients des variables (inconnues) on construit le premier tableau simplex.
| Tableau 1 | ||||
| Inconnues de base | Membres gratuits | Inconnues lâches | Coefficients auxiliaires | |
| X1 | X2 | |||
| X3 | -2 | 1 | -2 | |
| X4 | -4 | -1 | -1 | |
| X5 | 2 | 1 | -1 | |
| X6 | 6 | 0 | 1 | |
| F | 0 | -1 | -2 | |
La dernière ligne du tableau, qui contient la fonction objectif et les coefficients des variables libres qu'elle contient, sera appelée la ligne d'index.
La solution résultante n'est pas optimale, car les coefficients des variables libres de la ligne d'index sont négatifs. C'est-à-dire que la solution optimale sera celle dans laquelle les coefficients des variables libres de la ligne d'index seront supérieurs ou égaux à zéro.
Pour passer au tableau suivant, trouvez le plus grand (modulo) des nombres et . Ce nombre est 2. Par conséquent, la colonne de tête est la colonne dans laquelle il est écrit
Pour déterminer la ligne de tête, on trouve le minimum des rapports des membres libres aux éléments de la colonne de tête, et si le numérateur a un nombre positif et le dénominateur est négatif, le rapport est considéré comme égal à l'infini.
.
Par conséquent, la ligne principale est celle dans laquelle il est écrit
L'élément dominant est donc -2.
Nous composons le second tableau simplex.
Nous entrons le nouvel élément de base dans la première ligne, et nous entrons dans la colonne dans laquelle il se trouvait, nous entrons une nouvelle variable libre
Remplissez la première ligne. Pour ce faire, nous divisons tous les nombres de la première ligne du tableau 1 par l'élément de tête et l'écrivons dans la colonne correspondante de la première ligne du tableau 2, à l'exception du nombre de la première colonne, où l'inverse de l'élément de tête élément est écrit (c'est-à-dire un divisé par l'élément de tête).
Remplissez la colonne des coefficients auxiliaires. Pour ce numéro de la colonne de tête du tableau 1, en plus de l'élément de tête, on écrit avec des signes opposés dans la colonne des coefficients auxiliaires du tableau 2.
| Tableau 2 | ||||
| Inconnues de base | Membres gratuits | Inconnues lâches | Coefficients auxiliaires | |
| X1 | X3 | |||
| X2 | 1 | -1/2 | -1/2 | |
| X4 | -3 | -3/2 | -1/2 | 1 |
| X5 | 3 | 1/2 | -1/2 | 1 |
| X6 | 5 | 1/2 | 1/2 | -1 |
| F | 2 | -2 | -1 | 2 |
Qui n'a pas encore ouvert dans une nouvelle fenêtre le manuel Actions avec des fractions, peut le faire maintenant, car il est temps.
Pour obtenir les lignes restantes du tableau 2, les nombres déjà dans la première ligne de ce tableau sont multipliés par le coefficient auxiliaire dans la ligne en cours de remplissage, et au résultat nous ajoutons le nombre du tableau 1, qui est dans la même ligne avec la variable correspondante.
Par exemple, pour obtenir le membre libre de la deuxième ligne, nous multiplions le nombre 1 par 1 et ajoutons le nombre -4 du tableau 1. On obtient -3. Nous trouvons le coefficient pour dans la deuxième ligne de la même manière : 
. Puisqu'il n'y a pas de colonne avec une nouvelle variable libre dans le tableau précédent, le coefficient de la deuxième ligne de la colonne de la nouvelle variable libre sera 
(c'est-à-dire qu'à partir du tableau 1, nous ajoutons 0, car il n'y a pas de colonne c dans le tableau 1).
La ligne d'index est remplie de la même manière :
La solution ainsi obtenue n'est à nouveau pas optimale, puisque les coefficients des variables libres de la ligne d'index sont à nouveau négatifs.
Pour passer au tableau simplex suivant, trouvons le plus grand (modulo) des nombres et , c'est-à-dire les modules des coefficients de la ligne d'index. Ce nombre est 2. Par conséquent, la colonne de tête est la colonne qui contient .
Pour rechercher la ligne de tête, trouvons le ratio minimum de membres libres par rapport aux éléments de la ligne de tête. On a:
.
Par conséquent, la ligne principale est celle dans laquelle est écrit, et l'élément principal est -3/2.
Compilation du troisième tableau simplex
Nous écrivons la nouvelle variable de base dans la première ligne. Dans la colonne où il se trouvait, nous entrons une nouvelle variable libre .
Première ligne:
Coefficients auxiliaires :
| Tableau 3 | ||||
| Inconnues de base | Membres gratuits | Inconnues lâches | Coefficients auxiliaires | |
| X4 | X3 | |||
| X1 | 2 | -2/3 | 1/3 | |
| X2 | 2 | -1/3 | -1/3 | 1/2 |
| X5 | 2 | 1/3 | -2/3 | -1/2 |
| X6 | 4 | 1/3 | 1/3 | -1/2 |
| F | 6 | -4/3 | -1/3 | 2 |
La solution résultante n'est à nouveau pas optimale, puisque les coefficients des inconnues libres dans la ligne d'index sont à nouveau négatifs.
Pour aller au quatrième tableau simplex, trouvons le plus grand des nombres et . Ceci est un nombre.
Par conséquent, la colonne de tête est celle avec .
Module minimal des relations des membres libres aux éléments de la colonne principale :
.
Par conséquent, la ligne principale est celle dans laquelle est écrit et l'élément principal est 1/3.
Dans le quatrième tableau simplex, nous écrivons la nouvelle variable de base dans la première ligne. Dans la colonne où il se trouvait, nous écrivons une nouvelle variable libre .
Première ligne:
Coefficients auxiliaires :
| Tableau 4 | ||||
| Inconnues de base | Membres gratuits | Inconnues lâches | Coefficients auxiliaires | |
| X5 | X3 | |||
| X4 | 6 | 3 | -2 | |
| X1 | 6 | 2 | -1 | 2/3 |
| X2 | 4 | 1 | -1 | 1/3 |
| X6 | 2 | -1 | 1 | -1/3 |
| F | 14 | 4 | -3 | 4/3 |
Calcul des lignes restantes en utilisant l'exemple de la deuxième ligne :
La solution résultante n'est pas non plus optimale, mais elle est déjà meilleure que les précédentes, car l'un des coefficients des variables libres de la ligne d'index est non négatif.
Pour améliorer le plan, passons au tableau simplex suivant.
Trouvez le plus grand des nombres 4 et . Ce nombre est 4. Par conséquent, la première colonne est .
Pour trouver la ligne principale, trouvez
.
Par conséquent, la ligne principale est celle qui contient . Mais ils étaient déjà ensemble parmi les variables libres. Par conséquent, pour transférer la variable suivante de libre à de base, nous sélectionnons une autre colonne principale - celle dans laquelle est écrit.
Pour trouver la ligne principale, trouvez
.
Par conséquent, la ligne clé est celle dans laquelle est écrit et l'élément principal est 1.
Dans le cinquième tableau simplex, la nouvelle variable de base est écrite sur la première ligne. Dans la colonne où il se trouvait, nous écrivons une nouvelle variable libre .
Première ligne:
Coefficients auxiliaires :
| Tableau 5 | ||||
| Inconnues de base | Membres gratuits | Inconnues lâches | Coefficients auxiliaires | |
| X5 | X6 | |||
| X3 | 2 | -1 | 1 | |
| X4 | 10 | 2 | ||
| X1 | 8 | 1 | ||
| X2 | 6 | 1 | ||
| F | 20 | 1 | 3 | 3 |
Essayons de savoir tout de suite si la solution n'est pas optimale. Par conséquent, pour les lignes restantes, nous calculons uniquement les termes libres (pour connaître les valeurs des variables de base lorsque les variables libres sont égales à zéro) et les coefficients des variables libres de la ligne d'index.
Membres gratuits :
En deuxième ligne ;
Dans la troisième ligne ;
Sur la quatrième ligne.
Ligne d'index :
Nous regardons le tableau simplex 5. Nous voyons que la solution optimale a été obtenue, puisque les coefficients des inconnues libres dans la ligne d'index sont non négatifs.
Méthode du simplexe avec transformations algébriques
Résolvons par transformations algébriques le même exemple que dans le paragraphe précédent. Il convient de noter que lors de la résolution de ce type de méthode simplexe, il est préférable de ne pas écrire la fonction objectif sous la forme , car il est facile de se confondre dans les signes. Mais dans ce cas, le point de l'algorithme qui détermine le critère d'optimalité sera modifié comme suit.
Si le maximum (minimum) de la forme linéaire est trouvé et qu'il n'y a pas de variables non fondamentales avec des coefficients positifs (négatifs) dans son expression, alors le critère d'optimalité est rempli et la solution de base résultante est optimale - la solution est terminée. Si, lors de la recherche du maximum (minimum) d'une forme linéaire, son expression contient une ou plusieurs variables non fondamentales avec des coefficients positifs (négatifs), passez à une nouvelle solution de base.
Exemple. Trouver le maximum d'une fonction sous contraintes
Étape I. Nous introduisons des variables non négatives supplémentaires et réduisons ce système d'inégalités à un système d'équations équivalent
.
Les variables supplémentaires introduites sont considérées comme les principales, car dans ce cas, la solution de base du système est facilement trouvée. Alors et sont des variables mineures.
En exprimant les principales variables en termes de variables non fondamentales, nous obtenons
Par conséquent, cette division des variables en basiques et non basiques correspond à la solution de base 
, qui est invalide (deux variables sont négatives), et donc non optimale. Passons de cette solution de base à une solution améliorée.
Pour décider quelle variable doit être transférée du non-principal au principal, considérez l'une des deux équations disponibles du dernier système avec des termes libres négatifs, par exemple, la seconde. Cela montre que et peuvent être traduits dans les variables principales, car dans cette équation, ils ont des coefficients positifs (par conséquent, lorsqu'ils augmentent, et cela se produira si nous traduisons l'un d'entre eux dans les variables principales, la variable augmentera).
Essayons de traduire dans la variable principale . Pour déterminer quelle variable doit être transférée du principal au non fondamental, nous trouvons la valeur absolue du plus petit rapport des membres libres du système aux coefficients à . Nous avons . Il est obtenu à partir de la troisième équation, qui montre que la variable doit être convertie en variables non fondamentales, ce qui est positif dans la solution de base d'origine. Par conséquent, la solution de base obtenue, comme celle d'origine, contient deux composantes négatives, c'est-à-dire qu'il n'y aura aucune amélioration dans la transition vers une telle solution de base.
Méthode simplexe− c'est une méthode d'énumération ordonnée des plans de référence (l'ordre est assuré par un changement monotone de la valeur de la fonction objectif lors du passage au plan suivant). Dans ce cas, il faut respecter le principe : chaque étape suivante doit améliorer ou, dans les cas extrêmes, ne pas aggraver la valeur de la fonction objectif.
Pour résoudre le LLP méthode du simplexe il est réduit à la forme canonique, c'est-à-dire à partir de restrictions - inégalités il faut faire des restrictions - égalités. Pour ce faire, chaque contrainte est complétée par une valeur supplémentaire non négative variable de bilan avec le signe "+" si le signe d'inégalité est "£", et avec le signe "-" si le signe d'inégalité est "³".
Dans la fonction objectif, ces variables supplémentaires entrent avec des coefficients nuls, c'est-à-dire l'entrée de la fonction cible ne changera pas. Chaque variable qui n'est pas soumise à la condition de non négativité peut être représentée comme la différence de deux variables non négatives : .
Si les contraintes de tâche reflètent la présence et la consommation de ressources, alors la valeur numérique de la variable supplémentaire dans le plan de tâche, écrite sous forme canonique, est égale à la quantité de ressource inutilisée.
Pour résoudre le problème par la méthode du simplexe, nous utiliserons tableaux simplex raccourcis d'un système d'équations linéaires et méthode d'élimination de Jordan modifiée.
1. Nous établissons le premier plan de base
La tâche reste la même. Ramenons la forme standard du système d'inégalités (1) dans la forme canonique du système d'équations en introduisant des variables d'équilibre supplémentaires X 3 , X 4 , X 5 ,X 6 .
Au sens économique, les valeurs des variables supplémentaires X 3 , X 4 , X 5 déterminer le solde des matières premières après la vente des produits.
La matrice du système d'équations résultant a la forme :
On voit que dans la matrice UN la base mineure du 4e ordre est le déterminant, composé de coefficients unitaires pour les variables supplémentaires X 3 , X 4 , X 5 ,X 6 , puisqu'il est non nul et égal à 1. Cela signifie que les vecteurs colonnes de ces variables sont linéairement indépendants, c'est-à-dire formulaire base, et les variables correspondantes X 3 , X 4 , X 5 ,X 6 sont de base(de base). variables X 1 , X 2 seront appelés libre(mineure).
Si variables libres X 1 et X 2 pour définir différentes valeurs, puis, en résolvant le système par rapport aux variables de base, nous obtenons un ensemble infini de solutions particulières. Si seules des valeurs nulles sont définies pour les variables libres, alors à partir d'un ensemble infini de solutions particulières, solutions de base- les régimes de base.
Pour savoir si les variables peuvent être basiques, il faut calculer le déterminant constitué par les coefficients de ces variables. Si ce déterminant n'est pas égal à zéro, alors ces variables peuvent être basiques.
Le nombre de solutions de base et le nombre correspondant de groupes de variables de base ne peuvent pas être supérieurs à , où n est le nombre total de variables, r est le nombre de variables de base, r≤ m≤ n.
Pour notre tâche r = 4; n= 6. Alors , c'est-à-dire 15 groupes de 4 variables de base sont possibles (soit 15 solutions de base).
Résolvons le système d'équations par rapport aux variables de base X 3 , X 4 , X 5 ,X 6:
En supposant que les variables libres X 1 = 0, X 2 = 0, on obtient les valeurs des variables de base : X 3 = 312; X 4 = 15; X 5 = 24;X 6 = -10, c'est-à-dire la solution de base sera = (0 ; 0 ; 312 ; 15 ; 24 ; -10).
Cette solution de base est inacceptable, car X 6 = –10 ≤ 0, et par la condition de contrainte X 6 ≥ 0. Donc, au lieu de la variable X 6 comme base, il faut prendre une autre variable parmi les variables libres X 1 ou X 2 .
Nous réaliserons la solution ultérieure en utilisant des tableaux simplex raccourcis, en remplissant les lignes du premier tableau avec les coefficients du système comme suit (tableau 1):
Tableau 1
F- la chaîne est appelée indice. Il est rempli de coefficients de fonction objectifs pris de signes opposés, puisque l'équation de la fonction peut être représentée par F = 0 – (– 4X 1 – 3X 2).
Dans la colonne des membres gratuits b je il y a un élément négatif b 4 = -10, c'est-à-dire la solution du système est invalide. Pour obtenir une solution valide (plan de base), l'élément b 4 doit être rendu non négatif.
Choisir X 6 - une ligne avec un membre libre négatif. Cette ligne contient des éléments négatifs. Choisissez l'un d'entre eux, par exemple, "-1" dans X 1 -colonne, et X 1 - colonne accepter comme colonne d'autorisation(il déterminera que la variable X 1 passera du gratuit au basique).
Nous partageons des membres gratuits b je sur les éléments pertinents un est colonne de résolution, on obtient relations évaluativesΘ je==(24, 15, 12, 10). Parmi ceux-ci, nous choisissons le plus petit positif (minΘ je=10), ce qui correspondra à ligne d'autorisation. La chaîne d'autorisation définit une variable xj, qui à l'étape suivante dépasse de la base et devient libre. C'est pourquoi X 6 -line est une ligne permissive, et l'élément "-1" est élément habilitant. Nous l'entourons. variables X 1 et X 6 sont échangés.
Rapports estimés Θ je dans chaque ligne sont déterminés par les règles :
1) Θ je= si b je et un est avoir des signes différents;
2) Θ je= ∞ si b je= 0 et un est < 0;
3) Θ je= ∞ si un est = 0;
4) Θ je= 0 si b je= 0 et un est > 0;
5) Θ je= si b je et un est ont les mêmes signes.
Nous passons à l'étape de l'élimination jordanienne modifiée (MJJI) avec un élément permissif et compilons un nouveau tableau (Tableau 2) selon la règle suivante :
1) à la place de l'élément de résolution (RE), une valeur est définie, son inverse, c'est-à-dire ;
2) les éléments de la ligne permissive sont divisés en RE;
3) les éléments de la colonne de résolution sont divisés en RE et le signe change ;
4) les éléments restants sont trouvés selon la règle du rectangle :
Du tableau. 2 montre que les membres gratuits dans b je-colonne sont non-négatifs, par conséquent, la solution admissible initiale est obtenue - premier plan de base= (10 ; 0 ; 182 ; 5 ; 4 ; 0). Dans ce cas, la valeur de la fonction F() = 40. Géométriquement, cela correspond au sommet F(10 ; 0) polygone de solution (Fig. 1).
Tableau 2
2. Nous vérifions l'optimalité du plan. Le plan de base n'est pas optimal, car dans F-line a un coefficient négatif "-4". Nous améliorons le plan.
3. Trouver une nouvelle ligne de base
Nous sélectionnons l'élément permettant selon la règle:
Nous choisissons le plus petit coefficient négatif dans F-ligne "-4", qui détermine la colonne d'activation - X 6 ; variable X 6 traduire en basique ;
On trouve les rapports Θ je, parmi eux on choisit le plus petit positif, qui correspond à la chaîne permissive :
min Θ je = min(14, 5, 2, ∞) = 2, donc X 5 - ligne - permissif, variable X 5 on traduit en libre (variables X 5 et X 6 sont échangés).
À l'intersection de la ligne et de la colonne permissives se trouve l'élément permissif "2" ;
Nous effectuons l'étape SHMZhI, nous construisons la table. 3 selon la règle ci-dessus et obtenir un nouveau plan de référence = (12 ; 0 ; 156 ; 3 ; 0 ; 2).
Tableau 3
4. Vérification de l'optimalité du nouveau plan de base
Le plan de base n'est pas non plus optimal, puisqu'en F-line a un coefficient négatif "-1". Valeur de la fonction F() = 48, ce qui correspond géométriquement au sommet E(12 ; 0) polygone de solution (Fig. 1). Nous améliorons le plan.
5. Trouver une nouvelle ligne de base
X 2 colonnes est permissif, puisque dans F-ligne le plus petit coefficient négatif "-1" est dans X 2 colonnes (Δ 2 = -1). Trouver le plus petit Θ je: min Θ je = min(≈ 9, 6, ∞, 24) = 6, donc X 4ème ligne - permissive. Elément permissif "1/2". Échange de variables X 2 et X quatre. Nous effectuons l'étape SHMZhI, nous construisons la table. 4, on obtient un nouveau plan de référence = (9 ; 6 ; 51 ; 0 ; 0 ; 5).
6. Vérification de l'optimalité du plan de base
À F-line, tous les coefficients sont non négatifs, par conséquent, le plan de référence est optimal. Correspond géométriquement à un point ré(9;6) (voir Fig. 1). Le plan optimal donne la valeur maximale de la fonction objectif c.u.
Principal l'idée d'une méthode simplex pour résoudre le LLP consiste en l'amélioration constante des solutions d'accompagnement LLP.
Il existe plusieurs manières d'écrire la méthode du simplexe.
- La forme de base de la méthode du simplexe ;
- Méthode du simplexe sous la forme d'un tableau simplexe ;
- Méthode du simplexe modifié ;
- Méthode du simplexe sous forme de colonne ;
- Méthode du simplexe sous forme de ligne.
Définissons la valeur maximale de la fonction objectif F(X) = 3x 1 +5x 2 +4x 3 sous les conditions de contrainte suivantes.
0,1x 1 +0,2x 2 +0,4x 3 ≤1100
0,05x 1 +0,02x 2 +0,02x 3 ≤120
3x1 +x2 +2x3 ≤8000
Pour construire le premier plan de référence, on réduit le système d'inégalités à un système d'équations en introduisant des variables supplémentaires (passage à la forme canonique).
0,1x1 + 0,2x2 + 0,4x3 + 1x4 + 0x5 + 0x6 = 1100
0,05x1 + 0,02x2 + 0,02x3 + 0x4 + 1x5 + 0x6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000
Notation de base de la méthode du simplexe
| La solution est effectuée en exprimant les variables de base par des variables non fondamentales : x0 = 3x1 +5x2 +4x3 x 4 = 1100-0,1x 1 -0,2x 2 -0,4x 3 x 5 = 120-0,05x 1 -0,02x 2 -0,02x 3 x 6 = 8000-3x 1 -x 2 -2x 3 |
Méthode du simplexe sous la forme d'un tableau simplexe
La solution est réalisée sous la forme d'un tableau simplex. Le formulaire est conçu pour le calcul sur ordinateur. Lors de l'utilisation d'une base artificielle, un nombre spécial M est utilisé (généralement 10000).| Planifier | Base | À | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 1 | x4 | 1100 | 0.1 | 0.2 | 0.4 | 1 | 0 | 0 | 5500 |
| x5 | 120 | 0.05 | 0.02 | 0.02 | 0 | 1 | 0 | 6000 | |
| x6 | 8000 | 3 | 1 | 2 | 0 | 0 | 1 | 8000 | |
| Ligne d'index | F(X1) | 0 | -3 | -5 | -4 | 0 | 0 | 0 | 0 |
| 2 | x2 | 5500 | 0.5 | 1 | 2 | 5 | 0 | 0 | 11000 |
| x5 | 10 | 0.04 | 0 | -0.02 | -0.1 | 1 | 0 | 250 | |
| x6 | 2500 | 2.5 | 0 | 0 | -5 | 0 | 1 | 1000 | |
| Ligne d'index | F(X2) | 27500 | -0.5 | 0 | 6 | 25 | 0 | 0 | 0 |
| 3 | x2 | 5375 | 0 | 1 | 2.25 | 6.25 | -12.5 | 0 | 11000 |
| x1 | 250 | 1 | 0 | -0.5 | -2.5 | 25 | 0 | 250 | |
| x6 | 1875 | 0 | 0 | 1.25 | 1.25 | -62.5 | 1 | 1000 | |
| Ligne d'index | F(X3) | 27625 | 0 | 0 | 5.75 | 23.75 | 12.5 | 0 | 0 |
Méthode du simplexe modifié
| Matrice des coefficients A = a ij Matrice b. |
Méthode du simplexe sous forme de colonne
| On passe à la forme colonnaire de la méthode du simplexe. Nous exprimons chaque variable en termes de variables non fondamentales. x 0 = 0-3(-x 1)-5(-x 2)-4(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 1 = 0-1(-x 1)+0(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 2 = 0+0(-x 1)-1(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 3 = 0+0(-x 1)+0(-x 2)-1(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 4 = 1100+0,1(-x 1)+0,2(-x 2)+0,4(-x 3)+1(-x 4)+0(-x 5)+0(-x 6) x 5 = 120+0,05(-x 1)+0,02(-x 2)+0,02(-x 3)+0(-x 4)+1(-x 5)+0(-x 6) x 6 = 8000+3(-x 1)+1(-x 2)+2(-x 3)+0(-x 4)+0(-x 5)+1(-x 6) Ce système correspond au tableau T 0 .
|
Méthode simplexe sous forme de chaîne
Comme base initiale admissible, on peut prendre B 0 =<4, 5, 6>. Il correspondra au tableau suivant.
|
La matrice Q, composée des coefficients du système, est appelée tableau recto correspondant à la base B. Un tableau simplex est appelé admissible, ou directement recevable, si q i0 ≥ 0. Les éléments q i0 de la dernière ligne du tableau simplexe Q sont appelés estimations relatives.
Formes de solution par la méthode de la base artificielle
Pour l'utilisation de variables artificielles introduites dans la fonction objectif, une pénalité dite de M est imposée, un très grand nombre positif, qui n'est généralement pas spécifié.La base résultante est appelée artificielle et la méthode de résolution est appelée méthode de base artificielle.
De plus, les variables artificielles ne sont pas liées au contenu de la tâche, mais elles permettent de construire un point de départ, et le processus d'optimisation force ces variables à prendre des valeurs nulles et assure l'admissibilité de la solution optimale.
Formes de solution par la méthode de base artificielle:
- M-méthode (tableau simplex);
- méthode du simplexe en deux étapes ou en deux phases (notation de base, méthode du simplexe modifié, méthode du simplexe sous forme de colonne, méthode du simplexe sous forme de ligne).
S'il y a des restrictions avec le signe ≥ dans la condition du problème, alors elles peuvent être réduites à la forme ∑a ji b j en multipliant les deux parties de l'inégalité par -1. On introduit m variables supplémentaires x n+j ≥0(j =1,m ) et on transforme les contraintes sous la forme d'égalités
(2)
Supposons que toutes les variables initiales du problème x 1 , x 2 ,..., x n sont non fondamentales. Alors les variables supplémentaires seront basiques, et une solution particulière au système de contraintes a la forme
X 1 = X 2 = ... = X n = 0, X n+ j = b j , j =1,m . (3)
Puisque dans ce cas la valeur de la fonction but F 0 = 0 , on peut représenter F(x) comme suit :
F(x)=∑c je X je + F 0 =0 (4)
Le tableau simplex initial (tableau simplex 1) est compilé sur la base des équations (2) et (4). Si les variables supplémentaires x n+j sont précédées du signe « + », comme dans (2), alors tous les coefficients avant les variables x i et le terme libre b j sont entrés dans le tableau simplex sans changement. Les coefficients de la fonction d'objectif lors de sa maximisation sont entrés dans la ligne inférieure du tableau simplex avec des signes opposés. Les membres libres de la table simplex déterminent la solution du problème.
L'algorithme de résolution du problème est le suivant :
1ère étape. Les éléments de la colonne des membres libres sont recherchés. S'ils sont tous positifs, alors une solution de base acceptable a été trouvée et il faut passer à l'étape 5 de l'algorithme, qui correspond à la recherche de la solution optimale. S'il y a des termes libres négatifs dans le tableau simplex initial, alors la solution n'est pas valide et vous devez passer à l'étape 2.
2ème étape. Pour trouver une solution faisable, il est nécessaire de décider laquelle des variables non fondamentales inclure dans la base et quelle variable retirer de la base.
Tableau 1.
| variables de base | Membres gratuits dans les restrictions | Variables non fondamentales | |||||
| x1 | x2 | ... | xl | ... | x n|||
| xn+1 | b 1 | un 11 | un 12 | ... | un 1l | ... | un 1n |
| xn+2 | b 2 | un 21 | un 22 | ... | un 2l | ... | un 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+r | b2 | un r1 | un r2 | ... | un rl | ... | un rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+m | b m | un m1 | un m2 | ... | aml | ... | amn |
| F(x)max | F0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Pour ce faire, choisissez l'un des éléments négatifs de la colonne des membres libres (que ce soit b 2 en tête ou en autorisant. S'il n'y a pas d'éléments négatifs dans la ligne avec un membre libre négatif, alors le système de restrictions est incohérent et le problème n'a pas de solution.
Dans le même temps, la variable qui est la première à changer de signe avec une augmentation du NP x l sélectionné est exclue du BP. Ce sera x n+r , dont l'indice r est déterminé à partir de la condition
ceux. la variable qui correspond au plus petit rapport du terme libre à l'élément de la colonne de tête sélectionnée. Cette relation s'appelle relation simplexe. Seules les relations simplex positives doivent être considérées.
La chaîne correspondant à la variable x n+r est appelée diriger ou permettre. L'élément du tableau simplex a rl , qui se trouve à l'intersection de la ligne de tête et de la colonne de tête, est appelé l'élément de tête ou de résolution. Trouver l'élément principal termine le travail avec chaque tableau simplex suivant.
3ème étape. Un nouveau tableau simplex est calculé, dont les éléments sont recalculés à partir des éléments du tableau simplex de l'étape précédente et marqués d'un prime, c'est-à-dire b" j , a" ji , c" je , F" 0 . Les éléments sont recalculés selon les formules suivantes :
Tout d'abord, la ligne et la colonne qui menaient dans le tableau simplex précédent seront remplies dans le nouveau tableau simplex. L'expression (5) signifie que l'élément a "rl à la place de l'élément de tête est égal à l'inverse de l'élément du tableau simplex précédent. Les éléments de la ligne a ri sont divisés par l'élément de tête, et les éléments de la la colonne a jl sont également divisées par l'élément de tête, mais sont prises avec le signe opposé. Les éléments b" r et c" l sont calculés selon le même principe.
Le reste des formules peut être facilement écrit en utilisant .
Le rectangle est construit selon l'ancien tableau simplex de telle sorte que l'une de ses diagonales soit formée par les éléments recalculés (a ji) et principaux (a rl) (Fig. 1). La deuxième diagonale est déterminée de manière unique. Pour trouver un nouvel élément a "ji, le produit des éléments de la diagonale opposée, divisé par l'élément principal, est soustrait de l'élément a ji (ceci est indiqué par le signe" - "à la cellule). De même, les éléments b" j, (j≠r) et c" i sont recalculés, (i≠l).
4ème étape. L'analyse d'un nouveau tableau simplex commence à partir de la 1ère étape de l'algorithme. L'action se poursuit jusqu'à ce qu'une solution de base réalisable soit trouvée, c'est-à-dire tous les éléments de la colonne des membres libres doivent être positifs.
5ème étape. Nous croyons qu'une solution de base acceptable a été trouvée. On regarde les coefficients de la droite de la fonction but F(x) . Un signe de l'optimalité d'un tableau simplex est la non-négativité des coefficients pour les variables non fondamentales dans la ligne F.
Riz. 1. Règle du rectangle
Si parmi les coefficients de la ligne F il y en a des négatifs (à l'exception du terme libre), alors vous devez passer à une autre solution de base. Lors de la maximisation de la fonction d'objectif, la base inclut celle des variables non fondamentales (par exemple, x l), dont la colonne correspond à la valeur absolue maximale du coefficient négatif c l dans la ligne inférieure du tableau simplex. Cela vous permet de sélectionner la variable dont l'augmentation entraîne une amélioration de la fonction d'objectif. La colonne correspondant à la variable x l est appelée colonne de tête. En même temps, cette variable x n+r est exclue de la base, dont l'indice r est déterminé par le rapport simplex minimal :
La ligne correspondant à x n+r est appelée ligne de tête, et l'élément du tableau simplexe a rl , qui est à l'intersection de la ligne de tête et de la colonne de tête, est appelé élément dirigeant.
6ème étape. selon les règles énoncées dans la 3e étape. La procédure se poursuit jusqu'à ce qu'une solution optimale soit trouvée ou qu'il soit conclu qu'elle n'existe pas.
Si, lors du processus d'optimisation de la solution dans la colonne principale, tous les éléments sont non positifs, la ligne principale ne peut pas être sélectionnée. Dans ce cas, la fonction dans le domaine des solutions admissibles du problème n'est pas bornée par dessus et F max ->&∞.
Si à l'étape suivante de la recherche d'un extremum l'une des variables de base devient égale à zéro, alors la solution de base correspondante est dite dégénérée. Dans ce cas, le soi-disant bouclage se produit, qui se caractérise par le fait que la même combinaison de BP commence à se répéter avec une certaine fréquence (la valeur de la fonction F est conservée dans ce cas) et il est impossible de passer à une nouvelle solution de base acceptable. Le bouclage est l'un des principaux inconvénients de la méthode du simplexe, mais il est relativement rare. En pratique, dans de tels cas, on refuse généralement d'entrer dans la base la variable dont la colonne correspond à la valeur absolue maximale du coefficient négatif dans la fonction but, et on choisit au hasard une nouvelle solution de base.
Exemple 1. Résoudre un problème
max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7 ; x 1 + 4x 2 ≥8 ; x 2 ≤4 ; x 1,2 ≥0)
Méthode du simplexe et donner une interprétation géométrique du processus de résolution.
L'interprétation graphique de la solution du problème est illustrée à la fig. 2. La valeur maximale de la fonction d'objectif est atteinte au sommet de l'ODZP avec les coordonnées . Résolvons le problème en utilisant des tableaux simplex. Nous multiplions la deuxième contrainte par (-1) et introduisons des variables supplémentaires pour amener les inégalités sous la forme d'égalités, puis
Les variables initiales x 1 et x 2 sont prises comme non fondamentales, et les variables supplémentaires x 3 , x 4 et x 5 sont considérées comme fondamentales et nous compilons un tableau simplexe (tableau simplex 2). La solution correspondant au tableau du simplexe. 2, n'est pas valide ; l'élément principal est délimité et sélectionné conformément à l'étape 2 de l'algorithme ci-dessus. L'onglet simplex suivant. 3 définit une solution de base admissible ; 2 L'élément principal est décrit et sélectionné conformément à la 5e étape de l'algorithme de résolution du problème. Languette. 4 correspond à la solution optimale du problème, donc : x 1 = x 5 = 0 ; x 2 \u003d 4; x 3 \u003d 3; x 4 = 8 ; F max = 20.
Riz. 2. Solution graphique du problème
