Objet de la prestation. Le service est conçu pour la résolution de problèmes en ligne programmation linéaire(ZLP) en utilisant la méthode simplex dans les formes d'enregistrement 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 obtenue est stockée dans 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. Lors de la résolution, l'utilisation est automatiquement déterminée 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
Utiliser le service dans mode 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, méthode graphique (géométrique), méthode de Brown .
Extremum d'une fonction de deux variables
Problèmes de programmation dynamique
Répartir 5 lots homogènes de marchandises entre trois marchés de manière à obtenir revenu maximum dès 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 simplexe 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 simplexe 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 recherche valeur minimum(F(x) → min , voir un exemple de solution pour minimiser une fonction) et valeur maximale ((F(x) → max , voir un exemple de solution pour maximiser une fonction)
Une solution extrême est obtenue sur la limite de la région des solutions réalisables à l'un des sommets des coins du polygone, ou sur le segment entre deux points de coin 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.
Implémentation de la méthode simplexe en vigueur diverses fonctionnalités et les énoncés de problèmes, LP a 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 objectives des fonctions) ne contient pas d'éléments négatifs, elle trouvera donc 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. Solution double problème est dans la dernière table simplex. 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é.
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 | textile ( | 1 | 2 | 2 | 44 | Bénéfice (r.) | 2 | 5 | 4 |
La 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
Réduisons le problème à 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 rapport minimum de termes libres et de membres de la première colonne (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 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 |
Tous les termes de la ligne d'index sont non négatifs, nous obtenons donc solution suivante Problèmes de programmation linéaire (nous les écrivons dans 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, la réflexion surgit naturellement sur le chemin suivant Décisions PPP avec n'importe quel nombre 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 être très grand. 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
La tâche
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é.
- Vers le problème direct de la planification du chiffre d'affaires, résolu méthode 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 lequel les ressources dépensées pour la vente de biens sont estimées.
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...
La 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
Réduisons le problème à la 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 contrainte 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 rapport minimum de termes libres et de membres de la première colonne (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 :
Réduisons le problème à la 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
Considéré méthode graphique résoudre un problème de programmation linéaire (LPP) à deux variables. Un exemple de la tâche est donné Description détaillée construire un dessin et trouver une solution.
Solution au problème des transports
Le problème des transports est examiné en détail, son modèle mathématique et méthodes de solution - trouver le plan de référence à l'aide de la méthode élément minimum et recherche 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.
| - | x1 | + | x2 | - | S1 | = | 1 | ||||||||||
| x1 | +3 | x2 | + | S2 | = | 15 | |||||||||||
| - | 2 | x1 | + | x2 | + | S3 | = | 4 |
| - | x1 | + | x2 | - | S1 | + | R1 | = | 1 | |||||||||||
| x1 | +3 | x2 | + | S2 | = | 15 | ||||||||||||||
| - | 2 | x1 | + | x2 | + | S3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x1 | x2 | S1 | S2 | S3 | R1 | St. membre | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | F-1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W-0 |
| - | x1 | + | x2 | - | S1 | = | 1 | ||||||||||
| 4 | x1 | + | 3 | S1 | + | S2 | = | 12 | |||||||||
| - | x1 | + | S1 | + | S3 | = | 3 |
| x1 | x2 | S1 | S2 | S3 | St. membre | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F-1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F-1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F-13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
Une des méthodes de résolution des problèmes d'optimisation ( généralement associé à la recherche du minimum ou du maximum) la programmation linéaire est appelée . Méthode simplexe comprend tout un groupe d'algorithmes et de méthodes pour résoudre des problèmes de programmation linéaire. L'une de ces méthodes, qui consiste à enregistrer les données source et à les recalculer dans un tableau spécial, s'appelle méthode du simplexe tabulaire .
Considérons l'algorithme de la méthode du simplexe tabulaire en utilisant l'exemple de la solution tâche de production, ce qui revient à trouver un plan de production garantissant un profit maximum.
Données d'entrée pour le problème de la méthode simplexe
L'entreprise fabrique 4 types de produits et les traite sur 3 machines.
Les normes de temps (min./pièce) pour le traitement des produits sur les machines sont précisées par la matrice A :
Le fonds de temps de fonctionnement de la machine (min.) est précisé dans la matrice B :
Le bénéfice de la vente de chaque unité de produit (RUB/pièce) est donné par la matrice C :
Objectif de la tâche de production
Élaborer un plan de production qui maximisera le profit de l'entreprise.
Résoudre le problème en utilisant la méthode du simplexe tabulaire
(1) Notons X1, X2, X3, X4 le nombre prévu de produits de chaque type. Puis le plan souhaité : ( X1, X2, X3, X4)
(2) Écrivons les contraintes du plan sous la forme d'un système d'équations :
(3) Le bénéfice cible est alors :
C'est-à-dire que le profit résultant de la réalisation du plan de production devrait être maximum.
(4) Pour résoudre le problème extremum conditionnel qui en résulte, nous remplaçons le système d'inégalités par le système équations linéaires en y introduisant des variables supplémentaires non négatives ( X5, X6, X7).
(5) Acceptons ce qui suit plan de référence:
X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80
(6) Entrons les données dans tableau simplexe:
Dans la dernière ligne, nous saisissons les coefficients de la fonction objectif et sa valeur elle-même avec le signe opposé ;
(7) Sélectionnez dans la dernière ligne le plus grand (module) un nombre négatif.
Calculons b = N / Items_of_the_selected_column
Parmi les valeurs calculées de b on choisit moins.
L'intersection de la colonne et de la ligne sélectionnées nous donnera l'élément résolvant. On change la base en une variable correspondant à l'élément résolvant ( X5 à X1).
- L’élément résolvant lui-même passe à 1.
- Pour les éléments de la droite de résolution – a ij (*) = a ij / RE ( c'est-à-dire que nous divisons chaque élément par la valeur de l'élément de résolution et obtenons de nouvelles données).
- Pour les éléments de la colonne résolution, ils sont simplement remis à zéro.
- Nous recalculons les éléments restants du tableau en utilisant la règle du rectangle.
une ij (*) = une ij – (A * B / RE)
Comme vous pouvez le voir, nous prenons la cellule actuelle en cours de recalcul et la cellule contenant l'élément de résolution. Ils forment les coins opposés du rectangle. Ensuite, on multiplie les valeurs des cellules des 2 autres coins de ce rectangle. Ce travail ( UN * B) diviser par l'élément résolvant ( CONCERNANT). Et soustrayez de la cellule actuelle en cours de recalcul ( un ij) ce qui s'est passé. Nous obtenons une nouvelle valeur - un ij (*).
(9) Vérifiez à nouveau la dernière ligne ( c) sur présence de nombres négatifs. S'ils ne sont pas là, le plan optimal a été trouvé, on passe à la dernière étape de résolution du problème. Si c'est le cas, le plan n'est pas encore optimal et la table simplex doit être recalculée à nouveau.
Puisque nous avons à nouveau des nombres négatifs dans la dernière ligne, nous commençons une nouvelle itération de calculs.
(10) Puisqu’il n’y a aucun élément négatif dans la dernière ligne, cela signifie que nous avons trouvé le plan de production optimal ! À savoir : nous fabriquerons les produits qui ont été déplacés vers la colonne « Base » - X1 et X2. Nous connaissons le profit de la production de chaque unité de production ( matrice C). Il reste à multiplier les volumes de production trouvés des produits 1 et 2 avec un profit pour 1 pièce, on obtient le final ( maximum! ) profit pour un plan de production donné.
RÉPONDRE:
X1 = 32 pièces, X2 = 20 pièces, X3 = 0 pièce, X4 = 0 pièce.
P = 48 * 32 + 33 * 20 = 2 196 frotter.
Galyautdinov R.R.
© La copie du matériel n'est autorisée que si un lien hypertexte direct vers