Considérons méthode simplexe pour résoudre des problèmes programmation linéaire(LP). Il repose sur le passage d'un plan de référence à un autre, au cours duquel la valeur de la fonction objectif augmente.
L'algorithme de la méthode simplexe est le suivant :
- Nous transformons le problème original sous forme canonique en introduisant des variables supplémentaires. Pour les inégalités de forme ≤, les variables supplémentaires sont introduites avec un signe (+), mais si de forme ≥, alors avec un signe (-). Des variables supplémentaires sont introduites dans la fonction objectif avec des signes correspondants avec un coefficient égal à 0 , parce que la fonction cible ne doit pas changer sa signification économique.
- Les vecteurs sont écrits P jeà partir des coefficients des variables et de la colonne des termes libres. Cette action détermine le nombre de vecteurs unitaires. La règle est qu’il doit y avoir autant de vecteurs unitaires qu’il y a d’inégalités dans le système de contraintes.
- Après cela, les données source sont saisies dans un tableau simplex. Des vecteurs unitaires sont introduits dans la base, et en les excluant de la base, la solution optimale est trouvée. Les coefficients de la fonction objectif s'écrivent avec le signe opposé.
- Un signe d'optimalité pour un problème LP est que la solution est optimale si dans f– dans la ligne tous les coefficients sont positifs. Règle pour trouver la colonne d'activation - consultée f– une chaîne et parmi ses éléments négatifs, le plus petit est sélectionné. Vecteur P je son contenant devient permissif. La règle de choix d'un élément de résolution - les rapports des éléments positifs de la colonne de résolution aux éléments du vecteur sont compilés P 0 et le nombre qui donne le plus petit rapport devient l'élément résolvant par rapport auquel la table simplex sera recalculée. La ligne contenant cet élément est appelée ligne d'activation. S’il n’y a aucun élément positif dans la colonne résolution, alors le problème n’a pas de solution. Après avoir déterminé l’élément résolvant, ils procèdent au recalcul d’une nouvelle table simplexe.
- Règles pour remplir un nouveau tableau simplex. L'unité est mise à la place de l'élément de résolution, et les autres éléments sont supposés égaux 0 . Le vecteur de résolution est ajouté à la base, dont le vecteur zéro correspondant est exclu, et les vecteurs de base restants sont écrits sans modifications. Les éléments de la ligne de résolution sont divisés par l'élément de résolution et les éléments restants sont recalculés selon la règle du rectangle.
- Ceci est fait jusqu'à f– tous les éléments de la chaîne ne deviendront pas positifs.
Envisageons de résoudre le problème en utilisant l'algorithme discuté ci-dessus.
Donné:
Nous réduisons le problème à forme canonique:
On compose les vecteurs :
Remplissez le tableau simplexe :
:
Recalculons le premier élément du vecteur P 0, pour lequel on fait un rectangle de nombres : et on obtient : 
.
Nous effectuons des calculs similaires pour tous les autres éléments de la table simplex :
Dans le plan reçu f– la ligne contient un élément négatif – (-5/3), vecteur P1. Il contient dans sa colonne un seul élément positif, qui sera l'élément habilitant. Recalculons le tableau concernant cet élément :
Aucun élément négatif dans f– la ligne signifie trouvé plan optimal
:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).
- Ashmanov S.A. Programmation linéaire, M : Nauka, 1998,
- Ventzel E.S. Recherche opérationnelle, M : Radio soviétique, 2001,
- Kuznetsov Yu.N., Kuzubov V.I., Volochenko A.B. Programmation mathématique, M : Lycée, 1986.
Solution de programmation linéaire personnalisée
Vous pouvez commander tous les devoirs dans cette discipline sur notre site Internet. Vous pouvez joindre des fichiers et spécifier des délais à
Si vous avez déjà compris la méthode graphique de résolution de problèmes de programmation linéaire, il est temps de passer à méthode simplexe. Contrairement à la première, elle n'a pratiquement aucune restriction sur le problème (nombre quelconque de variables, signes différents, etc.) et est modifiée en fonction du type de problème (par exemple, la méthode M ou la méthode des bases artificielles).
Lors de la résolution d'un problème simplexe à l'aide de la méthode de calcul, les calculs sont généralement effectués (pour des raisons de compacité et de clarté) dans des tableaux ( simplexe tabulaire-méthode), et le dernier tableau avec la solution optimale contient un élément important Informations Complémentaires: solution double problème, les bilans de ressources, les informations sur les ressources rares, etc., qui permettent une analyse économique du problème de programmation linéaire (voir exemple 3 ci-dessous).
Des exemples de solutions aux problèmes utilisant la méthode simplex sont publiés gratuitement pour votre commodité - étudiez, recherchez des solutions similaires, résolvez. Si vous avez besoin d'aide pour des tâches comme celle-ci, accédez à : Solution de programmation linéaire personnalisée.
Résoudre des problèmes à l'aide de la méthode du simplexe : exemples en ligne
Tâche 1. L'entreprise produit des étagères de salle de bains en deux tailles : A et B. Les agents commerciaux estiment que jusqu'à 550 étagères pourraient être vendues sur le marché par semaine. Chaque étagère de type A nécessite 2 m2 de matériel, et chaque étagère de type B nécessite 3 m2 de matériel. L'entreprise peut recevoir jusqu'à 1200 m2 de matériel par semaine. Pour fabriquer une étagère de type A, 12 minutes de temps machine sont nécessaires, et pour fabriquer une étagère de type B - 30 minutes ; La machine peut être utilisée 160 heures par semaine. Si le bénéfice de la vente d'étagères de type A est de 3 unités monétaires, et celui des étagères de type B de 4 unités monétaires. unités, alors combien d’étagères de chaque type doivent être produites par semaine ?
Élaboration d'un modèle mathématique et d'une solution ZLP utilisant la méthode simplexe(pdf, 33 Ko)
Tâche 2. Résolvez un problème de programmation linéaire en utilisant la méthode du simplexe. 
Solution par la méthode du simplexe avec une base artificielle (pdf, 45 Ko)
Tâche 3. L'entreprise fabrique 3 types de produits : A1, A2, A3, en utilisant deux types de matières premières. Les coûts de chaque type de matière première par unité de production, les réserves de matières premières pour la période de planification, ainsi que le bénéfice d'une unité de production de chaque type sont connus.
- Combien d’articles de chaque type doivent être produits pour maximiser le profit ?
- Déterminer le statut de chaque type de matière première et sa valeur spécifique.
- Déterminer l'intervalle maximum de variation des stocks de chaque type de matière première, dans lequel la structure du plan optimal, c'est-à-dire La nomenclature de production ne changera pas.
- Déterminez la quantité de produits fabriqués et le profit de la production lors de l'augmentation du stock de l'un des types rares de matières premières jusqu'à la valeur maximale possible (dans la plage de production donnée).
- Déterminez les intervalles de variation du profit d'une unité de production de chaque type auxquels le plan optimal résultant ne changera pas.
Solution d'un problème de programmation linéaire avec analyse économique (pdf, 163 Ko)
Tâche 4. Résoudre un problème de programmation linéaire méthode simplexe: 
Solution par la méthode du simplexe tabulaire avec recherche du plan de référence (pdf, 44 Ko)
Tâche 5. Résolvez un problème de programmation linéaire en utilisant la méthode du simplexe : 
Solution par la méthode du simplexe tabulaire (pdf, 47 Ko)
Tâche 6. Résoudre le problème en utilisant la méthode du simplexe, en considérant comme plan de référence initial le plan donné dans la condition : 
Solution par méthode manuelle simplexe (pdf, 60 Ko)
Tâche 7. Résolvez le problème en utilisant la méthode du simplexe modifié.
Pour fabriquer deux types de produits A et B, trois types sont utilisés équipement technologique. Pour produire une unité du produit A, l'équipement du premier type utilise a1=4 heures, l'équipement du deuxième type a2=8 heures et l'équipement du troisième type a3=9 heures. Pour fabriquer une unité du produit B, l'équipement du premier type utilise b1=7 heures, l'équipement du deuxième type b2=3 heures et l'équipement du troisième type b3=5 heures.
Les équipements du premier type peuvent fonctionner pour la production de ces produits pendant pas plus de t1=49 heures, les équipements du deuxième type pendant pas plus de t2=51 heures, les équipements du troisième type pendant pas plus de t3=45 heures.
Le bénéfice de la vente d'une unité du produit fini A est ALPHA = 6 roubles et le produit B est BETTA = 5 roubles.
Élaborer un plan de production pour les produits A et B, garantissant un profit maximum de leur vente.
Solution utilisant la méthode du simplexe modifié (pdf, 67 Ko)
Tâche 8. Trouver solution optimale méthode double simplexe
Solution par la méthode du dual simplexe (pdf, 43 Ko)
Exemples de solutions à des problèmes de programmation linéaire
Méthodes pour résoudre des problèmes de programmation linéaire
Solutions de référence à un problème de programmation linéaire
Soit un problème de programmation linéaire en notation canonique
dans des conditions
Nous désignerons par l'ensemble des systèmes de solutions (2) – (3). Supposons que , où est le rang de la matrice , et est le nombre d'équations du système (2).
À partir du système de vecteurs colonnes de la matrice, nous sélectionnons un sous-système de vecteurs linéairement indépendant. Cela existe parce que. Ce système constitue la base de . Notons par , . Appelons ensemble de valeurs fondamentales indice , – sous-matrice de base matrices Nous appellerons les coordonnées du vecteur basique , si , et non basique V sinon.
Écrivons le système (2) sous la forme . Divisons les termes du côté gauche en basiques et non basiques, c'est-à-dire
Définissons une solution particulière de ce système comme suit. Mettons toutes les variables non fondamentales égales à zéro dans (4). Alors le système (4) prendra la forme
Appelons (5) sous-système de base système d'équations (2). Désignons par un vecteur composé des coordonnées de base du vecteur . Alors le système (2) peut être réécrit sous forme de matrice vectorielle
Puisque la sous-matrice est basique, elle
non dégénéré. Par conséquent, le système (6) a une solution unique. La solution particulière du système (2) ainsi obtenue sera appelée solution de référence problème de programmation linéaire directe correspondant à la base. (Parfois, la solution de référence est aussi appelée basique ). Comme on peut le constater, la base correspond à une solution de support unique. Évidemment, le nombre de solutions de support est limité.
Sur cette base, nous déterminons également la solution de référence au problème de programmation double linéaire. Rappelons que le problème dual du problème canonique a la forme
dans des conditions
Écrivons le système (8) sous la forme
Rappelons que l'ensemble des solutions du système (8) est noté .
Définissons le vecteur des variables duales à partir de la condition de remplir les contraintes de base du système (9) comme égalités. On obtient le système suivant équations linéaires:
Notons par un vecteur composé de ba-
coordonnées zis du vecteur. Le système (10) peut alors être réécrit sous forme de matrice vectorielle
Le système (11) présente également une solution unique.
Appelons-le justificatif (basique )décision problème de programmation linéaire double correspondant à la base. Cette solution de référence est également déterminée de manière unique.
Ainsi, toute base correspond à deux vecteurs - respectivement deux solutions de support et des problèmes de programmation linéaire directe et double.
Définissons plus en détail les types de bases et de solutions de support suivants. Si toutes les coordonnées de la solution support sont non négatives, alors la base à laquelle correspond cette solution support est appelée acceptable plan de référence problème de programmation linéaire directe, et la solution de référence correspondant à la même base est appelée pseudoplan double problème. En effet, pour que la base soit admissible, la non-négativité des coordonnées de la base suffit. Notez que le plan de référence est un vecteur réalisable du problème de programmation linéaire directe ().
Si la solution de référence satisfait toutes les restrictions (9) du problème dual, alors la base à laquelle correspond cette solution de référence est appelée doublement valable . Dans ce cas, le vecteur est appelé plan de référence problème de programmation linéaire double, et la solution de référence correspondant à la même base
ça s'appelle pseudoplan tâche directe.
Pour la double recevabilité d’une base, il suffit de satisfaire uniquement les inégalités non fondées. Notez que le plan de référence est un vecteur réalisable du problème de programmation linéaire double ().
Nous notons les différences entre les côtés gauche et droit des inégalités (9) par , . Alors la double recevabilité d'une base peut être établie en vérifiant la non-négativité de l'ensemble. Notez que, comme cela découle directement de la définition, tous les résidus de base sont égaux à zéro ().
Un exemple de résolution d'un problème direct et dual en utilisant la méthode du simplexe
Il suffit donc de veiller à ce que les inégalités perdurent pour tout le monde.
Théorème 1. LaisserEt– solutions de référence du problème de programmation linéaire correspondant à une certaine base, alors l'égalité est vraie .
Preuve . A partir des définitions des solutions de support, il est facile d'obtenir les égalités
d'où la validité du théorème.
Théorème 2. (Critère d'optimalité des solutions de support) Si baseest simultanément recevable et doublement recevable, alors les solutions de support correspondantesEtsont des solutions, respectivement, aux problèmes de programmation linéaire directe et dual.
Preuve. La validité de cette affirmation découle de la théorie de la dualité en programmation linéaire et du théorème 1.
Théorème 3. Une solution admissible au problème (1) – (3) est un plan de référence du problème si et seulement s’il s’agit du sommet d’un ensemble polyédrique convexe.
Preuve. Laisser – plan de référence du problème (1) – (3). Prouvons que – haut de l'ensemble . Par définition, un plan de référence – solution de référence admissible correspondant à une base, c'est-à-dire – résoudre un système d'équations linéaires par rapport à des variables
Il est facile de voir que ce système a une solution unique. Cela signifie que le plan d'appui de la face contenant le point , a une dimension 0. Par conséquent, – haut de l'ensemble .
Dos. Laisser – le haut de l'ensemble. Prouvons que – plan de référence du problème (1) – (3). Puisque est un sommet, c'est une face de l'ensemble dont la dimension est nulle. Par conséquent, le vecteur il y a au moins zéro composant, dont nous désignons l'ensemble des nombres . Ainsi, – la seule solution au système
Où . Il reste donc à prouver que le système de vecteurs est linéairement indépendant. Supposons le contraire. Il existe ensuite des nombres qui ne sont pas tous égaux à zéro, tels que . C'est pourquoi
Cela signifie que le système (12) a une solution différente de , ce qui contredit le caractère unique de sa solution. Ainsi, la base et le vecteur – le plan de référence correspondant au problème (1) – (3). C'est ce qu'il fallait.
Notez qu'une solution admissible au problème (7), (8) (le problème dual (1) – (3)) est également un plan de support si et seulement s'il est le sommet de l'ensemble admissible.
Date de publication : 2015-01-10 ; Lire : 695 | Violation des droits d'auteur de la page
Studopedia.org - Studopedia.Org - 2014-2018 (0,005 s)…
Pour être précis, nous supposons que le problème à résoudre est de trouver le minimum.
1. Réduire le problème de programmation linéaire à une forme canonique.
Après avoir introduit des variables supplémentaires, nous écrivons le système d’équations et la fonction linéaire sous une forme appelée système étendu :
Nous supposons que toutes les variables supplémentaires ont le même signe que les termes libres ; sinon nous utilisons ce qu'on appelle M.– une méthode qui sera discutée ci-dessous.
2. Définissez les variables de base et libres.
3. Nous entrons le système étendu d'origine dans la première table simplexe. La dernière ligne du tableau, qui donne l'équation de fonction linéaire les objectifs sont appelés évaluation. Il indique les coefficients de la fonction objectif. Dans la colonne de gauche du tableau, nous notons les principales variables (base), dans les colonnes suivantes, nous notons les coefficients des variables libres. L'avant-dernière colonne contient les membres libres du système étendu. La dernière colonne est préparée pour les relations d'estimation nécessaires pour déterminer la variable de base basée sur la relation (6.29).
4. Déterminer la possibilité de résoudre le problème par valeurs selon les théorèmes 6.7,…, 6.9.
5. Sélectionnez l'élément de résolution (référence).
Résoudre un problème de production à l'aide de la méthode du simplexe tabulaire
Si le critère d'optimalité n'est pas rempli (les conditions du théorème 6.7 ou 6.8 ne sont pas remplies), alors le plus grand coefficient négatif absolu de la dernière ligne détermine la colonne de résolution (de référence). 
.
Nous composons les ratios estimés de chaque ligne selon les règles suivantes :
1 0) si tous et ont des signes différents ;
2 0) si tout et ;
3 0) si ;
4 0) 0 si et ;
5 0) si et ont les mêmes signes.
Définissons. S'il n'y a pas de minimum final, alors le problème n'a pas d'optimum final (). Si le minimum est fini, alors sélectionnez la ligne q, sur laquelle il est réalisé (n'importe lequel, s'il y en a plusieurs), et appelez-le la ligne de résolution (de référence). À l’intersection de la ligne et de la colonne de résolution se trouve un élément de résolution (de référence).
6 0) Passez à la table suivante selon les règles :
a) dans la colonne de gauche, nous écrivons une nouvelle base : au lieu de la variable principale - une variable, c'est-à-dire Échangeons les variables et ;
b) mettre 1 à la place de l'élément de support ;
c) à d'autres endroits de la ligne de référence dans nouveau tableau laisser les éléments du tableau d'origine ;
d) aux places restantes de la colonne de référence, mettre les éléments correspondants du tableau d'origine, multipliés par –1 ;
d) pour le reste places gratuiteséléments , , dans le nouveau tableau, notez les nombres , , , qui se trouvent comme suit :
Pour simplifier les calculs utilisant ces formules, elles peuvent être formulées comme "Règles des rectangles"(Fig. 6.8) : les éléments sur les diagonales d'un rectangle avec des sommets (ou , , , , ou , , , ) sont multipliés (le produit qui ne contient pas l'élément support est pris avec un signe moins) et les produits résultants sont ajouté ;
f) diviser tous les éléments reçus du nouveau tableau par l'élément de référence.
7 0) Déterminer par la valeur de l'élément s'il est trouvé valeur optimale fonction cible. Si la réponse est négative, poursuivez la décision (retour au point 6).
Riz. 6.8. Règle du rectangle pour déterminer les nombres :
une − , b − , c − .
Un algorithme de conversion de tables simplexes pour des solutions de base admissibles non dégénérées est considéré, c'est-à-dire la situation décrite par le théorème 6.9 était remplie. Si le problème de programmation linéaire d'origine est dégénéré, alors au cours de sa résolution à l'aide de la méthode du simplexe, des solutions de base dégénérées peuvent apparaître. Dans ce cas, des étapes inactives de la méthode simplexe sont possibles, c'est-à-dire itérations dans lesquelles f(x) ne change pas. Le bouclage est également possible, c'est-à-dire une séquence sans fin d'étapes inactives. Pour l'éviter, des algorithmes spéciaux ont été développés - les anticyclines. Cependant, dans l'écrasante majorité des cas, les étapes inutilisées sont remplacées par des étapes avec une diminution de la fonction objectif, et le processus de solution s'achève à la suite d'un nombre fini d'itérations.
Exemple 6.8. Résolvez le problème donné dans l’exemple 6.7 en utilisant la méthode du simplexe.
⇐ Précédent45678910111213Suivant ⇒
Date de publication : 2015-01-23 ; Lire : 174 | Violation des droits d'auteur de la page
Studopedia.org - Studopedia.Org - 2014-2018 (0,002 s)…
Accueil >> Exemple n°3. Méthode simplexe. Trouver la plus grande valeur d'une fonction (base artificielle)
Méthode simplexe
| — | x1 | + | x2 | ≥ | 1 | |
| x1 | + | 3 | x2 | ≤ | 15 | |
| — | 2 | x1 | + | x2 | ≤ | 4 |
| Une variable est dite de base pour une équation donnée si elle est incluse dans cette équation avec un coefficient de un et n'est pas incluse dans les équations restantes (à condition qu'il y ait un nombre positif à droite de l'équation). Si chaque équation a une variable de base, alors le système est dit avoir une base. L'idée de la méthode simplexe est de passer d'une base à une autre, en obtenant une valeur de fonction qui n'est au moins pas inférieure à celle existante (chaque base correspond à une seule valeur de fonction). Comment s’effectue le passage d’une base à une autre ? |
| 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 | 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 |
Il n'y a aucun coefficient positif parmi les coefficients de ligne sélectionnés. On retrouve donc valeur la plus élevée fonctions F.
Répondre:
x 1 = 3 x 2 = 4
Fmax = 13
Accédez à la solution à votre problème
© 2010-2018, pour toute question merci d'écrire à [email protégé]
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 b 1 = 240, b 2 = 200, b 3 = 160 unités. Dans le même temps, pour la vente d'un groupe de marchandises pour 1 000 roubles. chiffre d'affaires des marchandises, la ressource du premier type est consommée à hauteur de 11 = 2 unités, la ressource du deuxième type à hauteur de 21 = 4 unités, la ressource du troisième type à hauteur de 31 = 4 unités. Pour la vente de 2 et 3 groupes de marchandises pour 1 000 roubles. le chiffre d'affaires est consommé en fonction de la ressource du premier type à hauteur de a 12 = 3, a 13 = 6 unités, la ressource du deuxième type à hauteur de a 22 = 2, a 23 = 4 unités, la ressource de le troisième type d'un montant de a 32 = 6, a 33 = 8 unités . Bénéficiez de la vente de trois groupes de biens pour 1 mille.
Méthode simplexe pour résoudre ZLP
frotter. le chiffre d'affaires est respectivement c 1 = 4, c 2 = 5, c 3 = 4 (milliers de 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é.
Au problème direct de la planification du chiffre d'affaires, résolu par la méthode simplexe, composer double problème programmation linéaire.
Installer paires conjuguées de variables problèmes directs et doubles.
D'après des paires conjuguées de variables, de la solution du problème direct on obtient solution du double problème, dans lequel il est produit évaluation des ressources, dépensé pour la vente de biens.
Résoudre le problème en utilisant la méthode du simplexe
Soit x 1, x 2, x 3 le nombre de biens vendus, en milliers de roubles, 1, 2, 3 - ses groupes, respectivement. Alors modèle mathématique la tâche a la forme :
F = 4 x 1 + 5 x 2 + 4 x 3 ->max
Nous résolvons la méthode du simplexe.
Nous introduisons des variables supplémentaires x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 pour transformer les inégalités en égalités.
Prenons comme base x 4 = 240 ; x5 = 200 ; x6 = 160.
Nous entrons les données dans tableau simplexe
Tableau simplex n°1
Fonction objectif :
0 240 + 0 200 + 0 160 = 0
Nous calculons les estimations à l'aide de la formule :
Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0
Puisqu’il existe des estimations négatives, le plan n’est pas optimal. Note la plus basse :
Nous introduisons la variable x 2 dans la base.
Nous définissons une variable issue de la base. Pour ce faire, on trouve le plus petit rapport non négatif pour la colonne x2.
= 26.667
Plus petit non négatif : Q 3 = 26,667. Nous dérivons la variable x 6 de la base
Divisez la 3ème ligne par 6.
De la 1ère ligne, soustrayez la 3ème ligne, multipliée par 3
De la 2ème ligne, soustrayez la 3ème ligne, multipliée par 2
On calcule :
On obtient un nouveau tableau :
Tableau simplex n°2
Fonction objectif :
0 160 + 0 440/3 + 5 80/3 = 400/3
Nous calculons les estimations à l'aide de la formule :
Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6
Puisqu'il existe une estimation négative Δ 1 = - 2/3, le plan n'est pas optimal.
Nous introduisons la variable x 1 dans la base.
Nous définissons une variable issue de la base. Pour ce faire, on trouve le plus petit rapport non négatif pour la colonne x 1.
Plus petit non négatif : Q 3 = 40. Nous dérivons la variable x 2 de la base
Divisez la 3ème ligne par 2/3.
De la 2ème ligne, soustrayez la 3ème ligne, multipliée par 8/3
On calcule :
On obtient un nouveau tableau :
Tableau simplex n°3
Fonction objectif :
0 160 + 0 40 + 4 40 = 160
Nous calculons les estimations à l'aide de la formule :
Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1
Puisqu’il n’y a pas de notes négatives, le plan est optimal.
Solution du problème :
Répondre
x1 = 40 ; x2 = 0 ; x3 = 0 ; x4 = 160 ; x5 = 40 ; x6 = 0 ; Fmax = 160
Autrement dit, il est nécessaire de vendre le premier type de biens pour un montant de 40 000.
frotter. Il n'est pas nécessaire de vendre des biens des types 2 et 3. Dans ce cas, le profit maximum sera de F max = 160 000 roubles.
Solution du double problème
Le double problème a la forme :
Z = 240 ans 1 + 200 ans 2 + 160 ans 3 ->min
Nous introduisons des variables supplémentaires y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 pour transformer les inégalités en égalités.
Les paires conjuguées de variables des problèmes directs et duaux ont la forme :
A partir du dernier tableau simplexe n°3 du problème direct, on trouve la solution du problème dual :
Z min = F max = 160 ;
oui 1 = Δ 4 = 0 ; y 2 = Δ 5 = 0 ; y 3 = Δ 6 = 1 ; y 4 = Δ 1 = 0 ; y 5 = Δ 2 = 1 ; y 6 = Δ 3 = 4 ;
Répondre
oui 1 = 0 ; y2 = 0 ; oui 3 = 1 ; Zmin = 160 ;
La méthode simplexe est une procédure de calcul basée sur le principe d'amélioration séquentielle des solutions lors du passage d'un point de base (solution de base) à un autre. Dans ce cas, la valeur de la fonction objectif s'améliore.
La solution de base est l'une des solutions réalisables situées aux sommets de la région valeurs acceptables. En vérifiant l'optimalité sommet après sommet du simplexe, ils arrivent à l'optimum souhaité. La méthode du simplexe est basée sur ce principe.
Un simplexe est un polygone convexe dans un espace à n dimensions avec n+1 sommets qui ne se trouvent pas dans le même hyperplan (l'hyperplan divise l'espace en deux demi-espaces).
Par exemple, la ligne des contraintes budgétaires divise les biens en disponibles et indisponibles.
Il a été prouvé que si une solution optimale existe, alors elle sera certainement trouvée après un nombre fini d'itérations (étapes), sauf en cas de « cyclage ».
L'algorithme de la méthode simplexe comprend un certain nombre d'étapes.
Première étape. Un premier modèle d'optimisation est construit. Ensuite, la matrice originale de conditions est transformée en la forme canonique réduite, qui se distingue de toutes les autres formes canoniques en ce sens :
a) les membres droits des conditions (termes libres bi) sont des quantités non négatives ;
b) les conditions elles-mêmes sont des égalités ;
c) la matrice de conditions contient une sous-matrice unitaire complète.
Si les termes libres sont négatifs, alors les deux côtés de l'inégalité sont multipliés par - 1 et le signe de l'inégalité est inversé. Pour transformer les inégalités en égalités, des variables supplémentaires sont introduites, qui indiquent généralement la quantité de ressources sous-utilisées. C'est leur signification économique.
Enfin, si, après avoir ajouté des variables supplémentaires, la matrice de conditions ne contient pas de sous-matrice d’identité complète, alors des variables artificielles sont introduites qui n’ont aucun sens économique. Ils sont introduits uniquement pour obtenir la sous-matrice d'identité et commencer le processus de résolution du problème en utilisant la méthode du simplexe.
Dans une solution optimale au problème, toutes les variables artificielles (IA) doivent être égales à zéro. Pour ce faire, des variables artificielles sont introduites dans la fonction objectif du problème avec de grands coefficients négatifs (-M) lors de la résolution du problème au maximum, et avec de grands coefficients positifs (+M) lorsque le problème est résolu au min. Dans ce cas, même une valeur non nulle insignifiante de la variable artificielle diminuera (augmentera) fortement la valeur de la fonction objectif. En règle générale, M doit être 1 000 fois supérieur aux valeurs des coefficients des variables principales.
Deuxième étape. Un premier tableau simplexe est construit et une première solution de base est trouvée. L'ensemble des variables qui forment la sous-matrice d'identité est pris comme solution de base initiale. Les valeurs de ces variables sont égales aux termes libres. Toutes les autres variables hors base sont nulles.
Troisième étape. La vérification de l'optimalité de la solution de base est effectuée à l'aide d'estimations spéciales des coefficients de la fonction objectif. Si toutes les estimations des coefficients de la fonction objectif sont négatives ou égales à zéro, alors la solution de base existante est optimale. Si au moins une estimation du coefficient de la fonction objectif est supérieure à zéro, alors la solution de base existante n'est pas optimale et doit être améliorée.
Quatrième étape. Transition vers une nouvelle solution de base. Évidemment, le plan optimal devrait inclure une variable qui augmente au maximum la fonction objectif. Lors de la résolution de problèmes pour un profit maximum, le plan optimal inclut les produits dont la production est la plus rentable. Ceci est déterminé par la valeur positive maximale de l’estimation du coefficient de la fonction objectif.
La colonne du tableau simplex avec ce numéro à cette itération est appelée colonne générale.
Pour trouver la ligne générale, tous les membres libres (ressources) sont répartis dans les éléments correspondants de la colonne générale (taux de consommation des ressources par unité de produit). Le plus petit est sélectionné parmi les résultats obtenus. La droite correspondante à une itération donnée est appelée la droite générale. Elle correspond à la ressource qui limite la production à une itération donnée.
Un élément d'un tableau simplex situé à l'intersection d'une colonne générale et d'une ligne est appelé élément général.
Ensuite, tous les éléments de la chaîne générale (y compris le membre libre) sont divisés en élément général. A la suite de cette opération, l'élément général devient égal à un. Ensuite, il faut que tous les autres éléments de la colonne générale deviennent égaux à zéro, c'est-à-dire la colonne générale devrait devenir unique. Toutes les lignes (sauf la ligne générale) sont converties comme suit. Articles reçus nouvelle ligne sont multipliés par l'élément correspondant de la colonne générale et le produit résultant est soustrait des éléments de l'ancienne ligne.
On obtient les valeurs des nouvelles variables de base dans les cellules correspondantes de la colonne des termes libres.
Cinquième étape. L'optimalité de la solution de base résultante est vérifiée (voir la troisième étape). Si c'est optimal, alors les calculs s'arrêtent. Dans le cas contraire, il faut trouver une nouvelle solution de base (quatrième étape), etc.
Méthode simplexe
Un exemple de résolution de problèmes d'optimisation de programmation linéaire à l'aide de la méthode simplexe
Soit il faut trouver le plan de production optimal pour deux types de produits (x1 et x2).
Données initiales :
Construisons un modèle d'optimisation
– limitation des ressources A;
– limitation des ressources B.
Réduisons le problème à la forme canonique réduite. Pour ce faire, il suffit d'introduire les variables supplémentaires X3 et X4. En conséquence, les inégalités se transforment en égalités strictes.
Construisons la table simplex initiale et trouvons la solution de base initiale. Ce seront des variables supplémentaires, puisqu'elles correspondent à une sous-matrice unitaire.
1ère itération. Recherchez la colonne générale et la ligne générale :
L'élément général est 5.
2ème itération. La solution de base trouvée n'est pas optimale, car La ligne de notation (Fj-Cj) contient un élément positif. Recherchez la colonne générale et la ligne générale :
max(0,0,3,-1,4,0) = 0,2
La solution trouvée est optimale puisque toutes les estimations spéciales de la fonction objectif Fj – Cj sont égales à zéro ou négatives. F(x)=29x1=2; x2=5.
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, nous obtenons une solution au problème double, dans laquelle les ressources dépensées pour vendre des 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...
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 à le 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 |
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) :
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 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 à l'aide de la méthode élément minimum et rechercher la solution optimale en utilisant 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 | Étape #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 | F-1 |
| - | 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 | W-0 | |
| -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 | W-0 | |
| 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-1 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
F-13 |
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
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.
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 à le 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.