Ainsi, les transitions successives d'un base conjuguéeà l'autre, ils s'exécutent jusqu'à ce qu'ils obtiennent une solution au problème ou établissent son insolvabilité. Chaque transition d'un pseudoplan à un autre est une itération (une étape).

Chaque itération contient deux étapes. Dans un premier temps, ils découvrent si le pseudo-plan est plan optimal problème direct, et sinon, si le problème peut être résolu. Pour ce faire, il est nécessaire de calculer et d'établir leurs signes. La deuxième étape consiste à mettre en œuvre transformation élémentaire- (une itération) méthode d'exclusion complète Jordan-Gauss, conduisant à un nouveau pseudo-plan avec une valeur inférieure fonction objectif.

Description de l'algorithme. Le problème LP doit être spécifié sous la forme canonique (1.1), (1.2) ou réduit à celle-ci. À la recherche de base conjuguée double problème et le désigner . Développons A 0 dans les vecteurs de base A i1 ,.,A im conformément à (1.9) et trouvons le pseudoplan tâche directe.

Explorons les signes (x i0). Si le cas se présente, alors le pseudo-plan initial est plan optimal tâche directe. S'il y a des composantes négatives (x i0), on calcule les coefficients décompositions vectorielles A j par vecteurs base conjuguée(х ij) conformément à (1.8).

Si pour certains r tel que x r0<0 , все то задача не разрешима (второй случай), и на этом процесс вычислений заканчивается.

Si le troisième cas se produit (c’est-à-dire pour tout r tel que x r0<0 , по крайней мере одна из компонент х rj <0 ), то переходим к второму этапу. С этой целью составляют таблицу k -й итерации (аналогичную tableau simplexe), qui se compose de (m+2) lignes et (n+1) colonnes (tableau 6.1).

La colonne B x du tableau, comme d'habitude, contient les vecteurs (A i) de la base du pseudoplan xk, et la colonne A 0 - les composantes de base du pseudoplan (x i0 (k)). La ligne d'indice (m+1) est remplie de paramètres qui sont des estimations des vecteurs A j :

valeur - la valeur de la fonction objectif pour un pseudoplan

L'itération k est complétée en remplissant la partie principale du tableau (de la première à la (m+1) ème lignes).

Tableau 6.1.

C			C1	C2	.	C j	.	CN
	Bx	Un 0	Un 1	Un 2	.	Un J	.	Un
C1	X1	X10	X11	X12	.	X1j	.	X1n
C2	X2	X20	X21	X22	.	X2j	.	X2n
.	.	.	.	.	.	.	.	.
C je	X je	Xi0	Xi1	Xi2	.	X ij	.	X dans
.	.	.	.	.	.	.	.	.
Cm	Xm	Xm0	Xm1	Xm2	.	X mj	.	X minutes
					.		.
					.		.

Lors de la première étape (k+1) - et les itérations déterminent si le premier, le deuxième ou le troisième cas se produit.

Dans le troisième cas, on passe à la deuxième étape. Tout d'abord, le vecteur A r est déterminé, qui doit être dérivé de la base. Son indice r est déterminé à partir de la condition

Seuls les postes pour lesquels x rj sont pourvus dans la ligne<0 . Вектор А l , который должен быть введен в базис, находят из условия

Après avoir déterminé la ligne guide r et la colonne l, les éléments de la partie principale du tableau de la (k+1)ième itération sont calculés à l'aide de relations de récurrence

(1.15)

Où x ri est l’élément guide de transformation.

Schéma de calcul de l'algorithme méthode double simplexe similaire au schéma de calcul de la méthode simplexe. Les formes des tableaux sont similaires.

La différence entre les méthodes est qu'avec la méthode simplexe, une transition séquentielle est effectuée d'une solution de base réalisable (plan de référence) du problème à une autre, et avec méthode double simplek- passage d'un pseudoplan à un autre.

La différence formelle entre les schémas informatiques de ces méthodes ne se manifeste que dans les règles de transition d'une base à une autre, ainsi que dans les signes d'optimalité et d'insolvabilité du problème. Dans la méthode simplexe, le vecteur introduit dans la base est d'abord déterminé, puis le vecteur exclu de la base est déterminé, et dans méthode double simplexe cet ordre est inversé.

Notons quelques propriétés importantes méthode double simplexe.

Contrairement au direct

Un exemple de résolution d'un problème à l'aide de la méthode du simplexe, ainsi qu'un exemple de résolution d'un problème double, sont considérés.

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 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. Le modèle mathématique du problème a alors 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 :

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.

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.

La 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 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 ;

11.4. MÉTHODE DOUBLE SIMPLEX

Des résultats des paragraphes précédents, il résulte que pour obtenir une solution au problème initial, on peut passer au problème dual et, à l'aide d'estimations de son plan optimal, définir solution optimale tâche originale.

Le passage au problème dual n'est pas nécessaire, car si l'on considère le premier tableau simplexe avec une base supplémentaire unitaire, il est facile de remarquer que le problème original est écrit dans les colonnes, et le dual est écrit dans les lignes.

Comme nous l’avons montré, lors de la résolution d’un problème direct à n’importe quelle itération, la différence, c'est à dire. ordre de grandeur -coefficient de la variable, est égal à la différence entre les côtés droit et gauche de la contrainte correspondante du problème dual. Si, lors de la résolution d'un problème direct avec une fonction objectif maximisée, l'itération ne conduit pas à une solution optimale, alors au moins pour une variable et seulement à l'optimum pour toutes différence .

Considérant cette condition prenant en compte la dualité, on peut écrire

.

Ainsi, si, Que . Cela signifie que lorsque la solution au problème direct est sous-optimale, la solution au problème double n’est pas réalisable. D'un autre côté à . Il s’ensuit que la solution optimale du problème direct correspond à une solution admissible du problème dual.

Cela a permis de développer une nouvelle méthode de résolution de problèmes de programmation linéaire, qui produit d'abord une solution inacceptable, mais « meilleure qu'optimale » (dans la méthode simplexe habituelle, on trouve d'abord acceptable, Mais sous-optimal solution). Nouvelle méthode, appelé méthode double simplexe , assure la réalisation des conditions d'optimalité de la solution et son « rapprochement » systématique de la région des solutions réalisables. Lorsque la solution résultante s’avère réalisable, le processus itératif de calcul se termine, puisque cette solution est également optimale.

La méthode dual simplex permet de résoudre des problèmes de programmation linéaire dont les systèmes de contraintes, à base positive, contiennent des termes libres de tout signe. Cette méthode permet de réduire le nombre de transformations du système de contraintes, ainsi que la taille de la table simplexe. Considérons l'application de la méthode dual simplex à l'aide d'un exemple.

Exemple. Trouver le minimum d'une fonction

sous restrictions

.

Passons à la forme canonique :

sous restrictions

Le tableau simplexe initial a la forme

Basique variables	X 1	X 2	X 3	X 4	X 5	Solution
X 3 X 4 X 5	–3 –4	–1 –3				–3 –6
	–2	–1

Solution de base initialeoptimale, mais pas acceptable.

Comme la méthode simplex habituelle, la méthode de résolution considérée est basée sur l'utilisation de conditions d'admissibilité et d'optimalité.

Condition de recevabilité. La variable de base négative la plus grande en valeur absolue est sélectionnée comme variable exclue (s'il existe des alternatives, le choix est fait arbitrairement). Si toutes les variables de base sont non négatives, le processus de calcul se termine puisque la solution résultante est réalisable et optimale.

Condition optimalité. La variable incluse dans la base est sélectionnée parmi les variables non fondamentales comme suit. Les rapports des coefficients du côté gauche sont calculés-équations aux coefficients correspondants de l'équation associée à la variable exclue. Relations avec des personnes positives ou valeur nulle les dénominateurs ne sont pas pris en compte. Dans le problème de minimisation, la variable d'entrée doit correspondre au plus petit des rapports spécifiés, et dans le problème de maximisation, au rapport qui est le plus petit en valeur absolue (s'il existe des alternatives, le choix est fait arbitrairement). Si les dénominateurs de tous les ratios sont nuls ou positifs, le problème n’a pas de solution réalisable.

Après avoir sélectionné les variables à inclure dans la base et à exclure pour obtenir prochaine décision l'opération habituelle de conversion des lignes d'une table simplex est effectuée.

Dans cet exemple, la variable exclue est. Les ratios calculés pour déterminer la nouvelle variable de base sont donnés dans le tableau suivant :

Variables	X 1	X 2	X 3	X 4	X 5
L'équation X 4 - équation	–2 –4	–1 –3
Attitude

La variable incluse est sélectionnée X 2. La conversion de chaîne ultérieure aboutit à une nouvelle table simplex :

Basique variables	X 1	X 2	X 3	X 4	X 5	Solution
X 3 X 2 X 5						–1 –1

Nouvelle solution également optimal, mais toujours inacceptable. Comme nouvelle variable exclue, nous choisissons (arbitrairement) X 3. Définissons la variable à inclure.

Variables	X 1	X 2	X 3	X 4	X 5
L'équation X 4 - équation
attitude

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, au cours duquel la valeur de la fonction objectif augmente.

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

1. 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.
2. 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.
3. 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é.
4. 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.
5. 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.
6. 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 : 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 à

Elle consiste à construire un plan optimal infaisable puis à le convertir en un plan admissible sans violer l'optimalité.

Algorithme pour la méthode dual simplex

1) sélectionner une ligne de résolution basée sur l'élément négatif en valeur absolue le plus grand de la colonne des termes libres ;
2) sélectionner la colonne de résolution en fonction du plus petit rapport en valeur absolue des éléments L de la ligne aux éléments négatifs de la ligne de résolution ;
3) recalculer le tableau simplex selon les règles de la méthode simplex habituelle ;
4) l'optimalité de la solution est vérifiée. Un signe de l'obtention d'une solution optimale admissible est l'absence d'éléments négatifs dans la colonne des membres libres.
Remarques
1. S’il n’y a pas un seul élément négatif dans la ligne de résolution, le problème est insoluble.
2. Si les contraintes du problème sont spécifiées par des inégalités de type « ≥ », la méthode du dual simplex élimine le besoin d'introduire des variables artificielles.

Exemple. Résolvez le problème en utilisant l'algorithme de la méthode dual simplex

L = x 1 + 4x 2 → min

Nous compilons le tableau simplex initial.

Baz.	x1	x2	x3	x4	x5	x6	x7	St.
x4	-2	-3		1	0	0	0	-20
x5	-5	1	-2	0	1	0	0	-12
x6	1	2	-1	0	0	1	0	2
x7	-1	4	-2	0	0	0	1	1
L	-1	-4	-1	0	0	0	0	0

L'absence d'estimations positives dans la ligne L indique l'optimalité de la solution originale, et la présence d'éléments négatifs dans la colonne des termes libres indique son inadmissibilité. Selon l'algorithme de la méthode dual simplex, nous sélectionnons la ligne de résolution en fonction de l'élément négatif le plus grand en valeur absolue de la colonne d'éléments libres. Dans notre exemple, la ligne d'habilitation est la première. La colonne d'activation est sélectionnée conformément à la règle énoncée au paragraphe 2 du schéma algorithmique. L'élément de résolution est (-4). Après recalcul on obtient le tableau suivant

Baz.	x1	x2	x3	x4	x5	x6	x7	St.
x3			1		0	0	0	5
x5			0		1	0	0	-2
x6			0		0	1	0	7
x7	0		0		0	0	1	11
L			0		0	0	0	5

En raisonnant de la même manière, nous obtenons un autre tableau

Baz.	x1	x2	x3	x4	x5	x6	x7	St.
x3	0		1			0	0
x1	1		0			0	0
x6	0		0			1	0
x7	0		0		0	0	1	11
L	0		0			0	0

L'absence d'éléments négatifs dans la colonne des termes libres indique qu'une solution optimale a été obtenue, .
Commentaire. Si Décision PPP et est inacceptable et non optimal, alors nous obtenons d'abord une solution admissible en utilisant l'algorithme de la méthode dual simplex, puis, selon les règles de la méthode simplex ordinaire, nous obtenons la solution optimale.
Exemple.
L = 5x 1 – x 2 – x 3 → maximum
ou

Compilation de la table simplex initiale

	x1	x2	x3	x4	x5	x6	x7	St.
x4	0		-2	1	0	0	0	-9
x5	1	-1	0	0	1	0	0	-1
x6	-1	-1	3	0	0	1	0	-8
x7	1	0	-1	0	0	0	1	4
L	-5	1	4	0	0	0	0	0

La solution n'est pas valide car la colonne factice contient des éléments négatifs et est sous-optimale car la ligne L a un score négatif (-5). Nous obtenons d’abord une solution réalisable en utilisant l’algorithme de la méthode dual simplex. Après recalcul on obtient le tableau simplex suivant

Baz.	x1	x2	x3	x4	x5	x6	x7	St.
x2	0	1	2	-1	0	0	0	9
x5	1	0	2	-1	1	0	0	8
x6	-1	0	5	-1	0	1	0	1
x7		0	-1	0	0	0	1	4
L	-5	0	2	1	0	0	0	-9

Il n’y a aucun élément négatif dans la colonne des termes libres, mais dans la ligne L il y a un score négatif (-5), ce qui signifie que la solution est acceptable et non optimale.
Nous utilisons la méthode simplex habituelle et obtenons les tableaux suivants

Baz.	x1	x2	x3	x4	x5	x6	x7	St.
x2	0	1	2	-1	0	0	0	9
x5	0	0	3	-1	1	0	-1	4
x6	0	0		-1	0	1	1	5
x1	1	0	-1	0	0	0	1	4
L	0	0	-3	1	0	0	5	11