Un exemple de résolution d'un problème direct et dual en utilisant la méthode du simplexe. Résoudre un problème de programmation linéaire en utilisant la méthode du simplexe
Le fil, les boutons et le tissu sont utilisés pour fabriquer trois types de chemises. Les stocks de fil, de boutons et de tissu, les normes de leur consommation pour coudre une chemise sont indiquées dans le tableau. Trouver le profit maximum et le plan de production de produits optimal qui le garantit (trouver).
| chemise 1 | chemise 2 | chemise 3 | Réserves | fils (m.) | 1 | 9 | 3 | 96 | boutons (pièces) | 20 | 10 | 30 | 640 | textiles ( | 1 | 2 | 2 | 44 | Bénéfice (r.) | 2 | 5 | 4 |
Solution du problème
Construction de maquettes
À travers et le nombre de chemises des 1er, 2e et 3e types destinées à la sortie.
Ensuite, les restrictions de ressources ressembleront à ceci :
De plus, selon le sens de la tâche
Fonction objectif exprimant le bénéfice perçu :
Nous obtenons le problème de programmation linéaire suivant :
Réduire un problème de programmation linéaire à une forme canonique
Mettons le problème sous forme canonique. Introduisons des variables supplémentaires. Nous introduisons toutes les variables supplémentaires dans la fonction objectif avec un coefficient égal à zéro. Nous ajoutons des variables supplémentaires aux côtés gauches des restrictions qui n'ont pas de forme préférée, et nous obtenons des égalités.
Résoudre le problème en utilisant la méthode du simplexe
Remplissez le tableau simplexe :
Puisque nous résolvons le problème au maximum, la présence de nombres négatifs dans la ligne d'index lors de la résolution du problème au maximum indique que nous n'avons pas obtenu la solution optimale et qu'il faut passer du tableau de la 0ème itération au suivant.
On passe à l'itération suivante comme suit :
la première colonne correspond
La ligne clé est déterminée par le ratio minimum de membres libres et de membres de la colonne principale (relations simplex) :
A l'intersection de la colonne clé et de la ligne clé, nous trouvons l'élément d'activation, c'est-à-dire 9.
Passons maintenant à la compilation de la 1ère itération : Au lieu d'un vecteur unitaire, nous introduisons le vecteur .
Dans le nouveau tableau, à la place de l'élément d'activation, nous écrivons 1, tous les autres éléments de la colonne clé sont des zéros. Les éléments de chaîne clé sont divisés en éléments d'activation. Tous les autres éléments du tableau sont calculés à l'aide de la règle du rectangle.
La colonne clé de la 1ère itération correspond à
L'élément résolvant est le nombre 4/3. Nous dérivons le vecteur de la base et introduisons le vecteur à la place. On obtient le tableau de la 2ème itération.
La colonne clé de la 2ème itération correspond à
On retrouve la ligne clé, pour cela on définit :
L'élément résolvant est le nombre 10/3. Nous dérivons le vecteur de la base et introduisons le vecteur à la place. On obtient le tableau de la 3ème itération.
| № | PA | cB | Ao | x1 | x2 | x3 | x4 | x5 | x6 | Simplexe | 2 | 5 | 4 | 0 | 0 | 0 | relation | 0 | x4 | 0 | 96 | 1 | 9 | 3 | 1 | 0 | 0 | 32/3 | x5 | 0 | 640 | 20 | 10 | 30 | 0 | 1 | 0 | 64 | x6 | 0 | 44 | 1 | 2 | 2 | 0 | 0 | 1 | 22 | F j - c j | 0 | -2 | -5 | -4 | 0 | 0 | 0 | 1 | x2 | 5 | 32/3 | 1/9 | 1 | 1/3 | 1/9 | 0 | 0 | 32 | x5 | 0 | 1600/3 | 170/9 | 0 | 80/3 | -10/9 | 1 | 0 | 20 | x6 | 0 | 68/3 | 7/9 | 0 | 4/3 | -2/9 | 0 | 1 | 17 | F j - c j | 160/3 | -13/9 | 0 | -7/3 | 5/9 | 0 | 0 | 2 | x2 | 5 | 5 | -1/12 | 1 | 0 | 1/6 | 0 | -1/4 | -- | x5 | 0 | 80 | 10/3 | 0 | 0 | 10/3 | 1 | -20 | 24 | x3 | 4 | 17 | 7/12 | 0 | 1 | -1/6 | 0 | 3/4 | 204/7 | F j - c j | 93 | -1/12 | 0 | 0 | 1/6 | 0 | 7/4 | 3 | x2 | 5 | 7 | 0 | 1 | 0 | 1/4 | 1/40 | -3/4 | x1 | 2 | 24 | 1 | 0 | 0 | 1 | 3/10 | -6 | x3 | 4 | 3 | 0 | 0 | 1 | -3/4 | -7/40 | 17/4 | F j - c j | 95 | 0 | 0 | 0 | 1/4 | 1/40 | 5/4 |
Dans la ligne d'index, tous les termes sont non négatifs, donc la solution suivante au problème de programmation linéaire est obtenue (nous l'écrivons à partir de la colonne des termes libres) :
Il faut coudre 24 chemises du 1er type, 7 chemises du 2ème type et 3 chemises du 3ème type. Dans ce cas, le bénéfice perçu sera maximum et s'élèvera à 95 roubles.
Vous pouvez trouver de l'aide pour résoudre vos problèmes à ce sujet en envoyant un message sur VKontakte, Viber ou en remplissant le formulaire. Le coût de la résolution des devoirs commence à partir de 7 BYR. par tâche (200 roubles russes), mais pas moins de 10 roubles biélorusses. (300 RUB) pour la totalité de la commande. Conception détaillée. Le coût de l'assistance à l'examen en ligne (dans ce cas, un prépaiement de 100 % est requis) est de 30 BYR. (1000 roubles russes) pour résoudre le ticket.
Brève théorie
De nombreuses méthodes différentes ont été proposées pour résoudre des problèmes de programmation linéaire. Cependant, la méthode simplex s'est avérée être la plus efficace et la plus universelle d'entre elles. Il convient de noter que pour résoudre certains problèmes, d'autres méthodes peuvent être plus efficaces. Par exemple, pour un ZLP à deux variables, la méthode optimale est , et pour la résoudre, la méthode potentielle est utilisée. La méthode simplexe est basique et applicable à tout PPL sous forme canonique.
En relation avec le théorème principal de la programmation linéaire, l'idée se pose naturellement de la manière suivante de résoudre le LLP avec un nombre quelconque de variables. Trouvez en quelque sorte tous les points extrêmes du polyèdre des plans (il n'y en a pas plus de ) et comparez-y les valeurs de la fonction objectif. Une telle solution, même avec un nombre relativement petit de variables et de restrictions, est pratiquement impossible, car le processus de recherche de points extrêmes est comparable en difficulté à la résolution du problème initial, et de plus, le nombre de points extrêmes du polyèdre des plans peut s'avèrent être très grands. En lien avec ces difficultés, le problème de l'énumération rationnelle des points extrêmes s'est posé.
L'essence de la méthode simplexe est la suivante. Si un point extrême et la valeur de la fonction objectif à ce niveau sont connus, alors tous les points extrêmes auxquels la fonction objectif prend la pire valeur ne sont évidemment pas nécessaires. Par conséquent, le désir naturel est de trouver un moyen de passer d'un point extrême donné à un point meilleur adjacent le long du bord, de celui-ci à un point encore meilleur (pas pire), etc. Pour ce faire, vous devez avoir un signe qui il n’y a pas de meilleurs points extrêmes qu’un point extrême donné. C'est l'idée générale de la méthode simplex (méthode d'amélioration séquentielle du plan) actuellement la plus utilisée pour résoudre ZLP. Ainsi, en termes algébriques, la méthode du simplexe suppose :
- la capacité de trouver un premier plan de référence ;
- présence d'un signe d'optimalité du plan de référence ;
- la possibilité de passer à un plan de référence qui n'est pas le pire.
Exemple de solution de problème
Condition problématique
Pour vendre trois groupes de biens, une entreprise commerciale dispose de trois types de ressources matérielles et monétaires limitées d'un montant de , , , unités. Dans le même temps, pour la vente d'un groupe de marchandises pour 1 000 roubles. le chiffre d'affaires des marchandises consomme la ressource du premier type en nombre d'unités, la ressource du deuxième type en nombre d'unités, la ressource du troisième type en nombre d'unités. Pour la vente de 2 et 3 groupes de marchandises pour 1 000 roubles. le chiffre d'affaires des marchandises est dépensé en fonction de la ressource du premier type d'un montant de , unités, des ressources du deuxième type d'un montant de , unités, des ressources du troisième type d'un montant de , unités. Bénéficiez de la vente de trois groupes de produits pour 1 000 roubles. le chiffre d'affaires est respectivement de mille roubles.
- Déterminez le volume et la structure prévus du chiffre d'affaires commercial afin que le profit de l'entreprise commerciale soit maximisé.
- Pour le problème direct de la planification du chiffre d'affaires, résolu par la méthode du simplexe, créez un problème de programmation double linéaire.
- Établir des paires conjuguées de variables des problèmes directs et duaux.
- Selon des paires conjuguées de variables, à partir de la solution du problème direct, on obtient une solution au problème double, dans laquelle sont estimées les ressources consacrées à la vente de biens.
Si votre admission à la session dépend de la résolution d'un bloc de problèmes et que vous n'avez ni le temps ni l'envie de vous asseoir pour des calculs, utilisez les capacités du site. La commande de tâches ne prend que quelques minutes. Vous pouvez lire en détail (comment soumettre une demande, prix, conditions, modes de paiement) sur la page Acheter des solutions aux problèmes de programmation linéaire...
Solution du problème
Construction de maquettes
Désignons respectivement le chiffre d'affaires des 1er, 2e et troisième types de biens.
Puis la fonction objectif exprimant le profit perçu :
Limitations des ressources matérielles et monétaires :
De plus, selon le sens de la tâche
Nous obtenons le problème de programmation linéaire suivant :
Réduction à la forme canonique du ZLP
Mettons le problème sous forme canonique. Pour transformer les inégalités en égalités, nous introduisons des variables supplémentaires. Les variables sont incluses dans les restrictions avec un coefficient de 1. Nous introduisons toutes les variables supplémentaires dans la fonction objectif avec un coefficient égal à zéro.
La restriction a une forme préférable si, le membre de droite étant non négatif, le membre de gauche a une variable entrant avec un coefficient égal à un, et les contraintes d'égalité restantes ont un coefficient égal à zéro. Dans notre cas, les 1ère, 2ème, 3ème restrictions ont une forme préférée avec les variables de base correspondantes.
Solution utilisant la méthode simplexe
Nous remplissons le tableau simplex de la 0ème itération.
| PA | Simplexe relation |
8 | 6 | 4 | 0 | 0 | 0 | 0 | 520 | 16 | 18 | 9 | 1 | 0 | 0 | 65/2 | 0 | 140 | 7 | 7 | 2 | 0 | 1 | 0 | 20 | 0 | 810 | 9 | 2 | 1 | 0 | 0 | 1 | 90 | 0 | -8 | -6 | -4 | 0 | 0 | 0 |
Puisque nous résolvons le problème au maximum, la présence de nombres négatifs dans la ligne d'index lors de la résolution du problème au maximum indique que nous n'avons pas obtenu la solution optimale et qu'il faut passer du tableau de la 0ème itération au suivant.
On passe à l'itération suivante comme suit :
La première colonne correspond à .
La ligne clé est déterminée par le ratio minimum de membres libres et de membres de la colonne principale (relations simplex) :
A l'intersection de la colonne clé et de la ligne clé, nous trouvons l'élément d'activation, c'est-à-dire 7.
Nous commençons maintenant à compiler la 1ère itération. Au lieu d'un vecteur unitaire, nous introduisons le vecteur .
Dans le nouveau tableau, à la place de l'élément d'activation, nous écrivons 1, tous les autres éléments de la colonne clé sont des zéros. Les éléments de chaîne clé sont divisés en éléments d'activation. Tous les autres éléments du tableau sont calculés à l'aide de la règle du rectangle.
On obtient le tableau de la 1ère itération :
| PA | Simplexe relation |
8 | 6 | 4 | 0 | 0 | 0 | 0 | 200 | 0 | 2 | 31/7 | 1 | -16/7 | 0 | 1400/31 | 8 | 20 | 1 | 1 | 2/7 | 0 | 1/7 | 0 | 70 | 0 | 630 | 0 | -7 | -11/7 | 0 | -9/7 | 1 | - | 160 | 0 | 2 | -12/7 | 0 | 8/7 | 0 |
La colonne clé de la 1ère itération correspond à .
On retrouve la ligne clé, pour cela on définit :
A l'intersection de la colonne clé et de la ligne clé, nous trouvons l'élément d'activation, c'est-à-dire 31/7.
Le vecteur est dérivé de la base et le vecteur est introduit.
On obtient le tableau de la 2ème itération :
| PA | Simplexe relation |
8 | 6 | 4 | 0 | 0 | 0 | 4 | 1400/31 | 0 | 14/31 | 1 | 7/31 | -16/31 | 0 | 8 | 220/31 | 1 | 27/31 | 0 | -2/31 | 9/31 | 0 | 0 | 21730/31 | 0 | -195/31 | 0 | 11/31 | -65/31 | 1 | 7360/31 | 0 | 86/31 | 0 | 12/31 | 8/31 | 0 |
Dans la ligne d'index, tous les termes sont non négatifs, donc la solution suivante au problème de programmation linéaire est obtenue (nous l'écrivons à partir de la colonne des termes libres) :
Ainsi, il faut vendre 7,1 mille roubles. marchandises du 1er type et 45,2 mille roubles. marchandises du 3ème type. Il n'est pas rentable de vendre un produit du 2ème type. Dans ce cas, le bénéfice sera maximum et s'élèvera à 237,4 mille roubles. Si le plan optimal est mis en œuvre, la ressource restante du 3ème type sera de 701 unités.
Problème de double LP
Écrivons un modèle du double problème.
Pour construire un problème dual, vous devez utiliser les règles suivantes :
1) si le problème direct est résolu au maximum, alors le problème dual est résolu au minimum, et vice versa ;
2) dans le problème du maximum, les contraintes d'inégalité ont la signification ≤, et dans le problème de minimisation elles ont la signification ≥ ;
3) chaque contrainte du problème direct correspond à une variable du problème dual, et inversement, chaque contrainte du problème dual correspond à une variable du problème direct ;
4) la matrice du système de restrictions du problème dual est obtenue à partir de la matrice du système de restrictions du problème original par transposition ;
5) les termes libres du système de contraintes du problème direct sont les coefficients des variables correspondantes de la fonction objectif du problème dual, et vice versa ;
6) si une condition de non-négativité est imposée à la variable du problème direct, alors la contrainte correspondante du problème dual s'écrit comme une contrainte d'inégalité, sinon, alors comme une contrainte d'égalité ;
7) si une contrainte du problème direct s'écrit sous forme d'égalité, alors la condition de non-négativité n'est pas imposée à la variable correspondante du problème dual.
On transpose la matrice du problème original :
Mettons le problème sous forme canonique. Introduisons des variables supplémentaires. Nous introduisons toutes les variables supplémentaires dans la fonction objectif avec un coefficient égal à zéro. Nous ajoutons des variables supplémentaires aux côtés gauches des restrictions qui n'ont pas de forme préférée, et nous obtenons des égalités.
Solution du problème du double LP
Correspondance entre les variables du problème initial et du problème dual :
Sur la base du tableau simplexe, la solution suivante au problème de programmation double linéaire a été obtenue (nous l'écrivons à partir de la ligne du bas) :
Ainsi, la ressource du premier type est la plus rare. Son score est maximum et égal à . La ressource du troisième type est redondante - sa double valeur est nulle. Chaque unité supplémentaire de biens du 2ème groupe vendue réduira le profit optimal de
Une méthode graphique pour résoudre un problème de programmation linéaire (LPP) avec deux variables est considérée. À l'aide de l'exemple d'un problème, une description détaillée de la construction d'un dessin et de la recherche d'une solution est donnée.
Solution au problème des transports
Le problème du transport, son modèle mathématique et ses méthodes de solution sont examinés en détail - trouver le plan de référence par la méthode des éléments minimaux et rechercher la solution optimale par la méthode du potentiel.
Prise de décision dans des conditions d’incertitude
La solution d'un jeu matriciel statistique dans des conditions d'incertitude est considérée à l'aide des critères de Wald, Savage, Hurwitz, Laplace et Bayes. À l'aide d'un exemple de problème, la construction d'une matrice de paiement et d'une matrice de risque est présentée en détail.
Objet de la prestation. Le service est conçu pour résoudre en ligne des problèmes de programmation linéaire (LPP) à l'aide de la méthode simplex sous les formes de notation suivantes :
- sous forme de tableau simplexe (méthode de transformation de Jordan) ; formulaire d'enregistrement de base ;
- méthode du simplexe modifiée ; sous forme de colonnes ; sous forme de ligne.
Instructions. Sélectionnez le nombre de variables et le nombre de lignes (nombre de contraintes). La solution résultante est enregistrée dans un fichier Word et Excel.
Dans ce cas, ne tenez pas compte des restrictions telles que x i ≥ 0. S'il n'y a aucune restriction dans la tâche pour certains x i, alors le ZLP doit être converti en KZLP ou utiliser ce service. La solution détermine automatiquement l'utilisation Méthode M(méthode simplex avec base artificielle) et méthode simplex en deux étapes.Les éléments suivants sont également utilisés avec cette calculatrice :
Méthode graphique pour résoudre ZLP
Solution au problème des transports
Résoudre un jeu matriciel
Grâce au service en ligne, vous pouvez déterminer le prix d'un jeu matriciel (bornes inférieure et supérieure), vérifier la présence d'un point selle, trouver une solution à une stratégie mixte en utilisant les méthodes suivantes : minimax, méthode simplex, graphique (géométrique ), méthode de Brown.
Extremum d'une fonction de deux variables
Problèmes de programmation dynamique
Répartissez 5 lots homogènes de marchandises entre trois marchés afin d'obtenir un maximum de revenus de leur vente. Les revenus des ventes sur chaque marché G(X) dépendent du nombre de lots vendus du produit X et sont présentés dans le tableau.
| Volume de produit X (en lots) | Revenu G(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
Algorithme de la méthode simplex comprend les étapes suivantes :
- Elaboration du premier plan de base. Transition vers la forme canonique du problème de programmation linéaire en introduisant des variables d'équilibre supplémentaires non négatives.
- Vérification de l'optimalité du plan. S’il existe au moins un coefficient de ligne d’indice inférieur à zéro, alors le plan n’est pas optimal et doit être amélioré.
- Détermination de la première colonne et de la première ligne. Parmi les coefficients négatifs de la ligne d'indice, le plus grand en valeur absolue est sélectionné. Ensuite, les éléments de la colonne membre libre de la table simplex sont divisés en éléments du même signe de la colonne principale.
- Construire un nouveau plan de référence. Le passage à un nouveau plan s'effectue suite au recalcul du tableau simplex selon la méthode Jordan-Gauss.
S'il faut trouver l'extremum de la fonction objectif, alors on parle de trouver la valeur minimale (F(x) → min, voir l'exemple d'une solution pour minimiser une fonction) et la valeur maximale ((F(x ) → max, voir l'exemple d'une solution pour maximiser une fonction)
Une solution extrême est obtenue à la limite de la région des solutions réalisables à l'un des sommets des points d'angle du polygone, ou sur le segment entre deux points d'angle adjacents.
Théorème fondamental de la programmation linéaire. Si la fonction objectif ZLP atteint une valeur extrême à un moment donné dans la région des solutions réalisables, alors elle prend cette valeur au point critique. Si la fonction objectif ZLP atteint une valeur extrême en plusieurs points d'angle, alors elle prend la même valeur en n'importe laquelle des combinaisons linéaires convexes de ces points.
L'essence de la méthode simplexe. Le déplacement vers le point optimal s'effectue en passant d'un point d'angle au point voisin, ce qui rapproche et plus rapidement X opt. Un tel schéma d'énumération de points, appelé la méthode simplexe, suggéré par R. Dantzig.
Les points d'angle sont caractérisés par m variables de base, de sorte que la transition d'un point d'angle à un point voisin peut être accomplie en changeant une seule variable de base dans la base en une variable d'une non-base.
La mise en œuvre de la méthode simplexe, en raison des diverses caractéristiques et formulations des problèmes LP, présente diverses modifications.
La construction des tables simplexes se poursuit jusqu'à ce que la solution optimale soit obtenue. Comment pouvez-vous utiliser un tableau simplexe pour déterminer que la solution à un problème de programmation linéaire est optimale ?
Si la dernière ligne (valeurs de la fonction objectif) ne contient pas d'éléments négatifs, elle trouvera donc le plan optimal.
Remarque 1. Si l'une des variables de base est égale à zéro, alors le point extrême correspondant à une telle solution de base est dégénéré. La dégénérescence se produit lorsqu'il existe une ambiguïté dans le choix de la ligne directrice. Vous ne remarquerez peut-être pas du tout la dégénérescence du problème si vous choisissez une autre ligne comme guide. En cas d'ambiguïté, la ligne avec l'index le plus bas doit être sélectionnée pour éviter les boucles.
Remarque 2. Soit à un point extrême toutes les différences simplexes non négatives D k ³ 0 (k = 1..n+m), c'est-à-dire une solution optimale est obtenue et il existe A k - un vecteur sans base pour lequel D k = 0. Alors le maximum est atteint au moins en deux points, c'est-à-dire il existe un optimal alternatif. Si nous introduisons cette variable x k dans la base, la valeur de la fonction objectif ne changera pas.
Remarque 3. La solution au problème dual se trouve dans le dernier tableau simplexe. Les m dernières composantes du vecteur des différences simplexes (dans les colonnes des variables d'équilibre) sont la solution optimale au problème dual. Les valeurs des fonctions objectives des problèmes directs et duaux aux points optimaux coïncident.
Remarque 4. Lors de la résolution du problème de minimisation, le vecteur avec la plus grande différence simplexe positive est introduit dans la base. Ensuite, le même algorithme est appliqué que pour le problème de maximisation.
Si la condition « Il est nécessaire que les matières premières de type III soient entièrement consommées » est précisée, alors la condition correspondante est une égalité.
Il faut résoudre un problème de programmation linéaire.
Fonction objectif :
2x 1 +5x 2 +3x 3 +8x 4 →min
Conditions limites :
3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1
Portons le système de restrictions à une forme canonique ; pour cela il faut passer des inégalités aux égalités, avec l'ajout de variables supplémentaires.
Puisque notre problème est un problème de minimisation, nous devons le transformer en un problème de recherche maximale. Pour ce faire, on change les signes des coefficients de la fonction objectif par les signes opposés. Nous écrivons les éléments de la première inégalité inchangés, en ajoutant une variable supplémentaire x 5 et en changeant le signe « ≤ » en « = ». Puisque les deuxième et troisième inégalités ont des signes « ≥ », il faut inverser les signes de leurs coefficients et y introduire des variables supplémentaires x 6 et x 7, respectivement. En conséquence, nous obtenons un problème équivalent :
3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1
Nous procédons à la formation de la table simplexe initiale. Les coefficients de la fonction objectif de signe opposé sont inscrits dans la ligne F du tableau.
Membre gratuit |
|||||
| F | |||||
| X5 | |||||
| X6 | |||||
| X7 |
Dans le tableau que nous avons compilé, il y a des éléments négatifs dans la colonne des termes libres, parmi eux nous trouvons le maximum en module - c'est l'élément : -6, il définit la première ligne - X6. Dans cette ligne on retrouve également l'élément négatif maximum en module : -10 il se situe dans la colonne X3, qui sera la colonne de tête. La variable de la première ligne est exclue de la base et la variable correspondant à la première colonne est incluse dans la base. Recalculons la table simplexe :
| X1 | X2 | X6 | X4 | Membre gratuit | |
| F | 0.8 | 8.9 | 0.3 | 6.5 | -1.8 |
| X5 | 4.6 | 0.8 | -0.4 | 3 | 14.4 |
| X3 | 0.4 | -1.3 | -0.1 | 0.5 | 0.6 |
| X7 | -2.6 | -8.3 | -0.1 | 0.5 | -0.4 |
Dans le tableau que nous avons compilé, il y a des éléments négatifs dans la colonne des termes libres, parmi eux nous trouvons le maximum en module - c'est l'élément : -0,4, il définit la première ligne - X7. Dans cette ligne on retrouve également l'élément négatif maximum en module : -8,3 il se situe dans la colonne X2, qui sera la colonne de tête. La variable de la première ligne est exclue de la base et la variable correspondant à la première colonne est incluse dans la base. Recalculons la table simplexe :
| X1 | X7 | X6 | X4 | Membre gratuit | |
| F | -1.988 | 1.072 | 0.193 | 7.036 | -2.229 |
| X5 | 4.349 | 0.096 | -0.41 | 3.048 | 14.361 |
| X3 | 0.807 | -0.157 | -0.084 | 0.422 | 0.663 |
| X2 | 0.313 | -0.12 | 0.012 | -0.06 | 0.048 |
Puisqu’il n’y a pas d’éléments négatifs dans la colonne des termes libres, une solution admissible a été trouvée. La ligne F contient des éléments négatifs, ce qui signifie que la solution résultante n’est pas optimale. Définissons la colonne principale. Pour ce faire, on retrouvera dans la ligne F l'élément négatif avec le module maximum - soit -1,988. La première ligne sera celle pour laquelle le rapport du terme libre à l'élément correspondant de la première colonne est minimal. La première ligne est X2 et l'élément principal est : 0,313.
| X2 | X7 | X6 | X4 | Membre gratuit | |
| F | 6.351 | 0.31 | 0.269 | 6.655 | -1.924 |
| X5 | -13.895 | 1.763 | -0.577 | 3.882 | 13.694 |
| X3 | -2.578 | 0.152 | -0.115 | 0.577 | 0.539 |
| X1 | 3.195 | -0.383 | 0.038 | -0.192 | 0.153 |
Puisqu’il n’y a aucun élément négatif dans la chaîne F, la solution optimale a été trouvée. Puisque la tâche initiale était de trouver le minimum, la solution optimale sera le terme libre de la chaîne F, pris avec le signe opposé. F=1,924
avec des valeurs variables égales : x 3 =0,539, x 1 =0,153. Les variables x 2 et x 4 ne sont pas incluses dans la base, donc x 2 =0 x 4 =0.
Problèmes de programmation linéaire. Il s’agit d’une construction séquentielle caractérisant le processus considéré. La solution se décompose en trois étapes principales : sélection des variables, construction d'un système de contraintes et recherche d'une fonction objectif.
A partir de cette division, la condition problème peut être reformulée comme suit : extremum de la fonction objectif Z(X) = f(x1, x2, … ,xn) → max (min) et les variables correspondantes, si l'on sait qu'elles satisfaire le système de contraintes : Φ_i ( x1, x2, … ,xn) = 0 pour i = 1, 2, …, k;Φ_i (x1, x2, … ,xn)) 0 pour i = k+1, k+ 2, …, m.
Le système de restrictions doit être amené à une forme canonique, c'est-à-dire à un système d'équations linéaires, où le nombre de variables est supérieur au nombre d'équations (m > k). Dans ce système, il y aura certainement des variables qui pourront être exprimées à travers d’autres variables, et si ce n’est pas le cas, elles pourront alors être introduites artificiellement. Dans ce cas, les premières sont appelées base ou base artificielle, et les secondes sont dites gratuites.
Il est plus pratique de considérer la méthode du simplexe à l'aide d'un exemple spécifique. Soit une fonction linéaire f(x) = 6x1 + 5x2 + 9x3 et un système de contraintes : 5x1 + 2x2 + 3x3 ≤ 25 ; x1 + 6x2 + 2x3 ≤ 20 ; valeur de la fonction f(x).
Solution Dans un premier temps, spécifier de manière absolument arbitraire la solution initiale (de référence) du système d'équations, qui doit satisfaire le système de contraintes donné. Dans ce cas, l'introduction d'artificiel est nécessaire, c'est-à-dire variables de base x4, x5 et x6 comme suit : 5x1 + 2x2 + 3x3 + x4 = 25 ; x1 + 6x2 + 2x3 + x5 = 20 ;
Comme vous pouvez le constater, les inégalités ont été transformées en égalités grâce aux variables ajoutées x4, x5, x6, qui sont des quantités non négatives. Ainsi, vous avez amené le système à sa forme canonique. La variable x4 est incluse dans la première équation avec un coefficient de 1, et dans la deuxième équation avec un coefficient de 0, il en est de même pour les variables x5, x6 et les équations correspondantes, ce qui correspond à la définition de la base.
Vous avez préparé le système et trouvé la solution de référence initiale – X0 = (0, 0, 0, 25, 20, 18). Présentez maintenant les coefficients des variables et les termes libres des équations (les nombres à droite du signe « = ») sous forme de tableau pour optimiser la suite des calculs (voir figure).
L'essence de la méthode du simplexe est de donner à ce tableau une forme dans laquelle tous les nombres de la ligne L seront des valeurs non négatives. S’il s’avère que cela est impossible, alors le système ne dispose pas du tout de solution optimale. Tout d’abord, sélectionnez le plus petit élément de cette ligne, qui est -9. Le numéro est dans la troisième colonne. Convertissez la variable x3 correspondante en variable de base. Pour ce faire, divisez la ligne par 3 pour que la cellule finisse par 1.
Maintenant, vous avez besoin des cellules et passez à 0. Pour ce faire, soustrayez des nombres correspondants de la troisième rangée par 3. Des éléments de la deuxième rangée - les éléments de la troisième, multipliés par 2. Et, enfin, de les éléments de la rangée L - multipliés par (-9). Vous avez obtenu la deuxième solution de référence : f(x) = L = 54 avec x1 = (0, 0, 6, 7, 8, 0).