Solution simplex pour les nuls. Un exemple de résolution d'un problème. Méthode simplexe pour résoudre LLP. Résoudre le problème en utilisant la méthode du simplexe tabulaire

02.03.2019

Un exemple de résolution d'un problème à l'aide de la méthode du simplexe est considéré, ainsi qu'un exemple de solution double 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 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 produits pour 1 000 roubles. 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, respectivement 1, 2, 3 groupes. Alors modèle mathématique la tâche a la forme :

F = 4 x 1 + 5 x 2 + 4 x 3 ->max

0)))(~)" title="delim(lbrace)(matrix(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

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 :

Nous obtenons 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.

Le 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 au 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 marchandises pour un montant de 40 000 roubles. Les produits des types 2 et 3 ne doivent pas être vendus. 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

Titre="delim(lbrace)(matrix(4)(1)((2a_1 + 4a_2 + 4a_3>=4) (3a_1 + 2a_2 + 6a_3>=5) (6a_1 + 4a_2 + 8a_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

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 ;

Considérons méthode simplexe pour résoudre des problèmes de programmation linéaire (LP). Il repose sur le passage d'un plan de référence à un autre, dans lequel la valeur fonction objectif augmente.

L'algorithme de la méthode simplexe est le suivant :

Nous traduisons le problème initial en vue 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 numéro qui donne plus petit rapport devient un élément résolvant par rapport auquel la table simplexe 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, procédez au recalcul nouveau simplexe– des tableaux.
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 mettons le problème sous 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 : Ecole Supérieure, 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 besoin de résoudre un problème de programmation linéaire à l'aide de tables simplexes, alors notre service en ligne je te donnerai grande aide. La méthode simplex implique une énumération séquentielle de tous les sommets de la région valeurs acceptables afin de trouver le sommet où la fonction prend une valeur extrême. Lors de la première étape, une solution est trouvée, qui est améliorée à chaque étape suivante. Cette solution est dite basique. Voici la séquence d'actions lors de la résolution d'un problème de programmation linéaire à l'aide de la méthode du simplexe :

Premier pas. Dans le tableau compilé, vous devez tout d’abord regarder la colonne avec les membres libres. S'il contient des éléments négatifs, il est alors nécessaire de passer à la deuxième étape, sinon à la cinquième.

Deuxième étape.

Dans un deuxième temps, il est nécessaire de décider quelle variable exclure de la base et laquelle inclure afin de recalculer le tableau simplex. Pour ce faire, nous parcourons la colonne avec les termes libres et y trouvons un élément négatif. La ligne avec un élément négatif sera appelée leader. On y trouve l'élément négatif maximum en module, la colonne correspondante est celle esclave. S'il y a des valeurs négatives parmi les termes libres, mais pas dans la ligne correspondante, alors un tel tableau n'aura pas de solutions. La variable de la première ligne située dans la colonne des termes libres est exclue de la base, et la variable correspondant à la première colonne est incluse dans la base.

Tableau 1.	Membres gratuits sous restrictions	Variables non fondamentales
Tableau 1.	Membres gratuits sous restrictions	x1	x2	...	xl	...	xn
xn+1	b1	un 11	un 12	...	un 1l	...	un 1n
xn+2	b2	un 21	un 22	...	un 2l	...	un 2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
xn+r	b2	un r1	un r2	...	un rl	...	arn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
xn+m	bm	un m1	un m2	...	un ml	...	une minute
F(x)max	F 0	-c 1	-c 2	...	-c 1	...	-c n

Troisième étape. À la troisième étape, nous recalculons la table simplex entière en formules spéciales

, ces formules peuvent être vues en utilisant .

Quatrième étape. Si après recalcul il reste des éléments négatifs dans la colonne des termes libres, alors passez à la première étape s'il n'y en a pas, puis à la cinquième ; Cinquième étape. Si vous avez atteint la cinquième étape, alors vous avez trouvé une solution acceptable. Toutefois, cela ne signifie pas qu’il soit optimal. Ce ne sera optimal que si tous les éléments de la chaîne F sont positifs. Si ce n'est pas le cas, alors il faut améliorer la solution, pour laquelle on retrouve pour le prochain recalcul la première ligne et la première colonne selonà l'algorithme suivant