Comment construire une table simplexe. Résoudre le problème en utilisant la méthode du simplexe tabulaire. Méthode de programmation linéaire en analyse économique

Étape 0. Étape préparatoire.

Nous réduisons le problème LP à une forme spéciale (15).

Étape 1. Compilation tableau simplexe, correspondant à la forme spéciale :

A noter que ce tableau correspond à une solution de base admissible
problèmes (15). La valeur de la fonction objectif sur cette solution

Étape 2. Contrôle d'optimalité

Si parmi les éléments de la ligne d'index il y a des tables simplex
il n'y a pas un seul élément positif alors
, la solution optimale au problème LP est trouvée :. L'algorithme se termine.

Étape 3. Contrôle d'indécidabilité

Si parmi
il y a un élément positif
, et dans la colonne correspondante
il n'y a pas un seul élément positif
, alors la fonction objectif L est illimité par le bas sur l’ensemble admissible. Dans ce cas, il n’existe pas de solution optimale. L'algorithme se termine.

Étape 4. Sélection d'une colonne principale q

Parmi les éléments
choisir l'élément positif maximum
.Nous déclarons cette colonne comme étant la colonne principale (permissive).

Étape 5. Sélection de la ligne principale p

Parmi les éléments positifs de la chronique
trouver l'élément
, pour lequel l'égalité est vraie

.

Chaîne p Nous déclarons qu'il est leader (permettant). Élément
Nous déclarons qu'il est le leader (si nous le permettons).

Étape 6. Conversion de tables simplexes

Nous créons une nouvelle table simplexe dans laquelle :

a) au lieu de la variable de base écrire , au lieu d'une variable non basique écrire ;

b) l'élément leader est remplacé par la valeur inverse
;

c) tous les éléments de la première colonne (sauf
) multiplier par
;

d) tous les éléments de la ligne directrice (sauf
) multiplier par ;

e) les éléments restants du tableau simplex sont transformés selon le schéma « rectangle » suivant.

Le produit de trois facteurs est soustrait de l'élément :

le premier est l'élément correspondant de la première colonne ;

le second est l'élément correspondant de la ligne directrice ;

le troisième est l'inverse de l'élément principal
.

L'élément transformé et les trois facteurs qui lui correspondent sont précisément les sommets du « rectangle ».

Étape 7 Le passage à l'itération suivante s'effectue en revenant à l'étape 2.

2.3. Algorithme de la méthode simplex pour le problème maximum

L'algorithme de la méthode simplex pour le problème maximum ne diffère de l'algorithme pour le problème minimum que par les signes de la ligne d'index des coefficients de la fonction objectif
, à savoir :

À l'étape 2 :
:

À l'étape 3
. La fonction objectif est illimitée d'en haut sur l'ensemble admissible.

À l'étape 4:
.

2.4. Un exemple de résolution d'un problème en utilisant la méthode du simplexe

Résolvez le problème écrit sous la forme (15).

Créons un tableau simplexe :

Puisque les coefficients de la droite de la fonction objectif sont non négatifs, la solution de base initiale n’est pas optimale. La valeur de la fonction objectif pour cette base L=0.

Sélectionnez la première colonne - c'est la colonne correspondant à la variable .

Sélectionnez la ligne directrice. Pour ce faire, nous trouvons
. Par conséquent, la ligne directrice correspond à la variable .

On transforme la table simplex en introduisant une variable dans la base et en sortant la variable de la base. On obtient le tableau :

Une itération de la méthode est terminée. Passons à une nouvelle itération. Le tableau résultant n’est pas optimal. La solution de base correspondant au tableau a la forme . La valeur de la fonction objectif sur cette base L= -2.

La première colonne ici est la colonne correspondant à la variable . Ligne directrice – la ligne correspondant à la variable . Après avoir effectué les transformations, on obtient un tableau simplexe :

Une autre itération terminée. Passons à une nouvelle itération.

La ligne de la fonction objectif ne contient pas de valeurs positives, ce qui signifie que la solution de base correspondante est optimale et l'algorithme se termine.

Conférence 3. Tableaux simplexes. Algorithme de la méthode simplexe.

§ 3 MÉTHODE SIMPLEXE

3.1. Idée générale de la méthode simplexe. Interprétation géométrique

La méthode graphique est applicable à une classe très restreinte de problèmes de programmation linéaire : elle peut résoudre efficacement des problèmes ne contenant pas plus de deux variables. Les théorèmes de base de la programmation linéaire ont été considérés, d'où il résulte que si un problème de programmation linéaire a une solution optimale, alors il correspond à au moins un point d'angle du polyèdre de solution et coïncide avec au moins une des solutions de base admissibles du système de contraintes. Une manière de résoudre tout problème de programmation linéaire a été indiquée : énumérer un nombre fini de solutions de base réalisables du système de contraintes et sélectionner parmi elles celle sur laquelle la fonction objectif fait la solution optimale. Géométriquement, cela correspond à énumérer tous les points d’angle du polyèdre solution. Une telle recherche exhaustive conduira finalement à une solution optimale (si elle existe), mais sa mise en œuvre pratique est associée à d'énormes difficultés, car pour des problèmes réels, le nombre de solutions de base réalisables, bien que finies, peut être extrêmement important.

Le nombre de solutions de base admissibles à rechercher peut être réduit si la recherche n'est pas effectuée de manière aléatoire, mais en tenant compte des modifications de la fonction linéaire, c'est-à-dire s'assurer que chaque solution suivante est « meilleure » (ou du moins « pas pire ») que la précédente, selon les valeurs de la fonction linéaire (en l'augmentant lors de la recherche d'un maximum, en la diminuant lors de la recherche d'un minimum
). Cette recherche permet de réduire le nombre d'étapes pour trouver l'optimum. Expliquons cela avec un exemple graphique.

Laissez la région des solutions réalisables être représentée par un polygone ABCDE. Supposons que son point d'angle UN correspond à la solution de base réalisable originale. Une recherche aléatoire nécessiterait de tester cinq solutions de base réalisables correspondant aux cinq coins du polygone. Cependant, il ressort clairement du dessin qu'après le sommet UN il est avantageux de se déplacer vers un sommet voisin DANS, puis au point optimal AVEC. Au lieu de cinq, nous n'avons parcouru que trois sommets, améliorant ainsi constamment la fonction linéaire.

L'idée d'améliorer successivement la solution a constitué la base d'une méthode universelle de résolution de problèmes de programmation linéaire - méthode simplex ou méthode d'amélioration séquentielle du plan.

La signification géométrique de la méthode du simplexe consiste en une transition séquentielle d'un sommet du polyèdre de contrainte (appelé initial) au voisin, dans lequel la fonction linéaire prend la meilleure (du moins pas la pire) valeur par rapport au but du problème ; jusqu'à ce que la solution optimale soit trouvée - le sommet où la valeur optimale de la fonction objectif est atteinte (si le problème a un optimal final).

La méthode simplexe a été proposée pour la première fois par le scientifique américain J. Danzig en 1949, mais en 1939, les idées de la méthode ont été développées par le scientifique russe L.V. Kantorovitch.

La méthode du simplexe, qui permet de résoudre tout problème de programmation linéaire, est universelle. Actuellement, il est utilisé pour les calculs informatiques, mais des exemples simples utilisant la méthode du simplexe peuvent être résolus manuellement.

Pour mettre en œuvre la méthode simplexe - amélioration séquentielle de la solution - il faut maîtriser trois éléments principaux :

un procédé permettant de déterminer toute solution de base initiale réalisable à un problème ;

la règle de transition vers la meilleure (plus précisément, pas la pire) solution ;

critère de vérification de l’optimalité de la solution trouvée.

Pour utiliser la méthode du simplexe, le problème de programmation linéaire doit être réduit à la forme canonique, c'est-à-dire le système de contraintes doit être présenté sous forme d'équations.

La littérature décrit de manière suffisamment détaillée : trouver le plan de support initial (solution de base initiale admissible), également en utilisant la méthode des bases artificielles, trouver le plan de support optimal, résoudre des problèmes à l'aide de tableaux simplexes.

3.2. Algorithme de la méthode simplexe.

Considérons la solution du ZLP en utilisant la méthode du simplexe et présentons-la en relation avec le problème de maximisation.

1. Sur la base des conditions du problème, son modèle mathématique est compilé.

2. Le modèle complété est converti sous la forme canonique. Dans ce cas, une base avec un plan de référence initial peut être identifiée.

3. Le modèle canonique du problème est écrit sous la forme d'un tableau simplexe afin que tous les termes libres soient non négatifs. Si le plan de référence initial est sélectionné, passez à l'étape 5.

Table simplex : un système d'équations de contraintes et une fonction objectif sont saisis sous forme d'expressions résolues par rapport à la base initiale. Une ligne contenant les coefficients de la fonction objectif
, appelé
–string ou chaîne de fonction cible.

4. Trouver le plan de référence initial en effectuant des transformations simplexes avec des éléments à résolution positive correspondant aux relations simplexes minimales, et sans prendre en compte les signes des éléments
–lignes. Si au cours des transformations une ligne 0 est rencontrée, dont tous les éléments, à l'exception du terme libre, sont des zéros, alors le système d'équations de contraintes du problème est incohérent. Si nous rencontrons une ligne 0 dans laquelle, à part le terme libre, il n'y a pas d'autres éléments positifs, alors le système d'équations restrictives n'a pas de solutions non négatives.

Nous appellerons la réduction du système (2.55), (2.56) à une nouvelle base transformation simplexe . Si la transformation simplexe est considérée comme une opération algébrique formelle, alors on peut remarquer qu'à la suite de cette opération, les rôles sont redistribués entre deux variables incluses dans un certain système de fonctions linéaires : une variable passe de dépendante à indépendante, et l'autre , au contraire, d'indépendant à dépendant. Cette opération est connue en algèbre sous le nom Étape d'élimination de la Jordanie.

5. Le plan de soutien initial trouvé est examiné pour déterminer son optimalité :

a) si dans
– il n’y a pas d’éléments négatifs dans la ligne (sans compter le terme libre), alors le plan est optimal. S’il n’y a pas de zéros, alors il n’y a qu’un seul plan optimal ; s'il y a au moins un zéro, alors il existe un nombre infini de plans optimaux ;

b) si c
– il y a au moins un élément négatif dans la ligne, qui correspond à une colonne d'éléments non positifs, alors
;

c) si dans
– la ligne comporte au moins un élément négatif, et sa colonne comporte au moins un élément positif, vous pouvez alors passer à un nouveau plan de référence plus proche de celui optimal. Pour ce faire, la colonne spécifiée doit être désignée comme colonne de résolution, en utilisant le rapport simplex minimum, trouver la ligne de résolution et effectuer une transformation simplex. Le plan de référence résultant est à nouveau examiné pour déterminer son optimalité. Le processus décrit est répété jusqu'à ce qu'un plan optimal soit obtenu ou jusqu'à ce que l'insolvabilité du problème soit établie.

La colonne de coefficients d'une variable incluse dans la base est appelée résolution. Ainsi, sélectionner une variable entrée dans la base (ou sélectionner une colonne de résolution) par l'élément négatif
-strings, nous fournissons une fonction croissante
.

Il est un peu plus difficile de déterminer la variable à exclure de la base. Pour ce faire, ils composent les rapports des termes libres aux éléments positifs de la colonne de résolution (ces relations sont appelées simplex) et trouvent le plus petit d'entre eux, qui détermine la ligne (de résolution) contenant la variable exclue. Le choix d'une variable exclue de la base (ou le choix d'une droite résolvante) selon la relation simplexe minimale garantit, comme cela a déjà été établi, la positivité des composantes de la base dans le nouveau plan de référence.

Au point 3 de l’algorithme, on suppose que tous les éléments de la colonne des termes libres sont non négatifs. Cette exigence n'est pas nécessaire, mais si elle est remplie, toutes les transformations simplexes ultérieures sont effectuées uniquement avec des éléments de résolution positifs, ce qui est pratique pour les calculs. S'il y a des nombres négatifs dans la colonne des termes libres, alors l'élément résolvant est choisi comme suit :

1) regardez la ligne correspondant à un terme libre négatif, par exemple – une ligne, et sélectionnez tout élément négatif qu'elle contient, et la colonne correspondante est considérée comme résolvante (on suppose que les contraintes du problème sont cohérentes) ;

2) constituer les relations des éléments de la colonne de termes libres avec les éléments correspondants de la colonne résolvante qui ont les mêmes signes (relations simplex) ;

3) choisir la plus petite des relations simplexes. Cela déterminera la chaîne d'activation. Que ce soit, par exemple, r-doubler;

4) à l'intersection de la colonne et de la ligne de résolution, un élément de résolution est trouvé. Si l'élément est permissif –chaînes, puis après la transformation simplexe le terme libre de cette chaîne deviendra positif. Sinon, à l'étape suivante, nous reviendrons sur -doubler. Si le problème peut être résolu, après un certain nombre d'étapes, il ne restera plus d'éléments négatifs dans la colonne des termes libres.

Si une certaine situation de production réelle est exprimée sous la forme d'un PLP, alors les variables supplémentaires qui doivent être introduites dans le modèle lors du processus de conversion à la forme canonique ont toujours une certaine signification économique.

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 résultant, nous remplaçons le système d'inégalités par un système d'équations linéaires en y introduisant des variables non négatives supplémentaires ( 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) est 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

Si l'énoncé du problème contient des restrictions avec le signe ≥, alors elles peuvent être réduites à la forme ∑a ji b j en multipliant les deux côtés de l'inégalité par -1. Introduisons m variables supplémentaires x n+j ≥0(j =1,m) et transformons les restrictions sous forme d'égalités

(2)

Supposons que toutes les variables initiales du problème x 1 , x 2 ,..., x n sont non basiques. Alors les variables supplémentaires seront basiques, et une solution particulière au système de contraintes a la forme

x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m. (3)

Puisque dans ce cas la valeur de la fonction objectif F 0 = 0, nous pouvons représenter F(x) comme suit :

F(x)=∑c je x je +F 0 =0 (4)

Le tableau simplex initial (tableau simplex 1) est compilé sur la base des équations (2) et (4). Si les variables supplémentaires x n+j sont précédées d'un signe « + », comme dans (2), alors tous les coefficients devant les variables x i et le terme libre b j sont entrés dans le tableau simplex sans modification. Lors de la maximisation de la fonction objectif, les coefficients sont inscrits dans la rangée inférieure du tableau simplex avec des signes opposés. Les termes libres du tableau simplex déterminent la solution au problème.

L'algorithme pour résoudre le problème est le suivant :

1ère étape.

Les membres de la colonne des membres gratuits sont visualisés. S'ils sont tous positifs, alors une solution de base admissible a été trouvée et il faut passer à l'étape 5 de l'algorithme, qui correspond à la recherche de la solution optimale. Si la table simplex initiale contient des termes libres négatifs, alors la solution n'est pas valide et vous devez passer à l'étape 2.

2ème étape.

x2

Pour trouver une solution admissible, elle est effectuée, et il est nécessaire de décider laquelle des variables non fondamentales inclure dans la base et quelle variable supprimer de la base.	Tableau 1.	variables de base
		Membres gratuits sous restrictions	Variables non fondamentales	...	x1	...
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	...	F(x)max	...	-c 1

-c 2

-c n

Pour ce faire, sélectionnez l'un des éléments négatifs de la colonne de termes libres (que ce soit b 2 en tête ou en résolution. S'il n'y a pas d'éléments négatifs dans la ligne avec un terme libre négatif, alors le système de contraintes est incohérent et le problème n'a pas de solution. Dans le même temps, la variable qui est la première à changer de signe lorsque le NP x l sélectionné augmente est exclue du BP. Ce sera x n+r, dont l'indice r est déterminé à partir de la condition

ceux. la variable qui a le plus petit rapport entre le terme libre et l'élément de la première colonne sélectionnée. Cette relation est appelée relation simplexe. Seules les relations simplexes positives doivent être considérées. La ligne correspondant à la variable x n+r s'appelle

diriger ou permettre. L'élément du tableau simplex a rl, situé à l'intersection de la première ligne et de la première colonne, est appelé l'élément principal ou résolvant.

Tout d’abord, le nouveau tableau simplex remplira la ligne et la colonne qui étaient en tête du tableau simplex précédent. L'expression (5) signifie que l'élément a" rl à la place de l'élément de tête est égal à l'inverse de l'élément du tableau simplex précédent. Les éléments de la ligne a ri sont divisés par l'élément de tête, et les éléments de la colonne a jl sont également divisés par l'élément principal, mais sont pris avec le signe opposé. Les éléments b" r et c" l sont calculés selon le même principe.

Le reste des formules peut être facilement écrit en utilisant .

Le rectangle est construit selon l'ancienne table simplex de telle sorte qu'une de ses diagonales est formée par les éléments recalculés (a ji) et dominants (a rl) (Fig. 1). La deuxième diagonale est déterminée de manière unique. Pour trouver un nouvel élément a" ji, le produit des éléments de la diagonale opposée divisé par l'élément principal est soustrait de l'élément a ji (ceci est indiqué par le signe « - » à côté de la cellule). Éléments b" j, (j≠r) et c" i sont recalculés de la même manière. (i≠l).

4ème étape.

L'analyse de la nouvelle table simplexe commence par la 1ère étape de l'algorithme. L'action se poursuit jusqu'à ce qu'une solution de base réalisable soit trouvée, c'est-à-dire tous les éléments de la colonne float doivent être positifs.

5ème étape.

Nous pensons qu'une solution de base acceptable a été trouvée. On regarde les coefficients de la droite de la fonction but F(x) . Un signe de l'optimalité d'un tableau simplexe est la non-négativité des coefficients des variables non fondamentales dans la ligne F.

Riz. 1. Règle du rectangle Si parmi les coefficients de la ligne F il y en a des négatifs (à l'exception du terme libre), alors vous devez passer à une autre solution de base. Lors de la maximisation de la fonction objectif, la base inclut l'une des variables non fondamentales (par exemple x l), dont la colonne correspond à la valeur absolue maximale du coefficient négatif c l dans la ligne du bas du tableau simplex. Cela permet de sélectionner la variable dont l'augmentation entraîne une amélioration de la fonction objectif. La colonne correspondant à la variable xl est appelée colonne de tête. Dans le même temps, cette variable x n+r est exclue de la base dont l'indice r est déterminé par la relation simplex minimale :

La ligne correspondant à x n+r est appelée leader, et l'élément du tableau simplex a rl, situé à l'intersection de la ligne principale et de la colonne principale, est appelé

Lors de l'optimisation de la solution, si tous les éléments de la première colonne sont non positifs, la première ligne ne peut pas être sélectionnée. Dans ce cas, la fonction dans la région des solutions réalisables au problème n'est pas bornée par le haut et F max ->&∞.

Si, à l'étape suivante de recherche d'un extremum, l'une des variables de base devient égale à zéro, alors la solution de base correspondante est dite dégénérée. Dans ce cas, ce qu'on appelle un cyclage se produit, caractérisé par le fait que la même combinaison de BP commence à se répéter avec une certaine fréquence (la valeur de la fonction F est préservée) et il est impossible de passer à une nouvelle solution de base réalisable. . Le bouclage est l’un des principaux inconvénients de la méthode simplexe, mais il est relativement rare. En pratique, dans de tels cas, ils refusent généralement d'entrer dans la base la variable dont la colonne correspond à la valeur absolue maximale du coefficient négatif dans la fonction but, et sélectionnent au hasard une nouvelle solution de base.

Exemple 1. Résoudre le problème

max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7 ; x 1 + 4x 2 ≥8 ; x 2 ≤4 ; x 1,2 ≥0)

Utiliser la méthode du simplexe et donner une interprétation géométrique du processus de résolution.

Une interprétation graphique de la solution au problème est présentée dans la Fig. 2. La valeur maximale de la fonction objectif est atteinte au sommet de l'ODZP avec les coordonnées . Résolvons le problème en utilisant des tables simplexes. Multiplions la deuxième contrainte par (-1) et introduisons des variables supplémentaires pour amener les inégalités sous forme d'égalités, puis

Nous prenons les variables initiales x 1 et x 2 comme non basiques, considérons les variables supplémentaires x 3, x 4 et x 5 comme basiques et composons un tableau simplex (table simplex 2). La solution correspondant à la table simplexe. 2, n'est pas valide ; l'élément principal est délimité et sélectionné conformément à l'étape 2 de l'algorithme précédent. Le tableau simplex suivant. 3 définit une solution de base admissible ; le sommet de l'ODZP sur la figure 1 lui correspond. 2 L'élément principal est défini et sélectionné conformément à la 5ème étape de l'algorithme de résolution de problèmes. Tableau 4 correspond à la solution optimale du problème, donc : x 1 = x 5 = 0 ; x2 = 4 ; x3 = 3 ; x4 = 8 ; Fmax = 20.

Riz. 2. Solution graphique au problème

Méthode simplexe est un processus itératif de solution dirigée d'un système d'équations par étapes, qui commence par une solution de référence et, à la recherche de la meilleure option, se déplace le long des points d'angle de la zone de solution réalisable, améliorant la valeur de la fonction objectif jusqu'à ce que la fonction objectif atteint la valeur optimale.

Objet de la prestation. Le service est conçu pour résoudre en ligne des problèmes de programmation linéaire (LPP) à l'aide de la méthode simplex sous les formes de notation suivantes :

• sous forme de tableau simplexe (méthode de transformation de Jordan) ; formulaire d'enregistrement de base ;
• méthode du simplexe modifiée ; sous forme de colonnes ; sous forme de ligne.

Instructions. Sélectionnez le nombre de variables et le nombre de lignes (nombre de contraintes). La solution résultante est enregistrée dans un fichier Word et Excel.

Nombre de variables 2 3 4 5 6 7 8 9 10
Nombre de lignes (nombre de restrictions) 1 2 3 4 5 6 7 8 9 10

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
Grâce au service en ligne, vous pouvez déterminer le prix d'un jeu matriciel (bornes inférieure et supérieure), vérifier la présence d'un point selle, trouver une solution à une stratégie mixte en utilisant les méthodes suivantes : minimax, méthode simplex, graphique (géométrique ), méthode de Brown.
Extremum d'une fonction de deux variables
Problèmes de programmation dynamique
Répartissez 5 lots homogènes de marchandises entre trois marchés afin d'obtenir un maximum de revenus de leur vente. Les revenus des ventes sur chaque marché G(X) dépendent du nombre de lots vendus du produit X et sont présentés dans le tableau.

Volume de produit X (en lots)	Revenu G(X)
	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

Algorithme de la méthode simplex comprend les étapes suivantes :

1. 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.
2. 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é.
3. Détermination de la première colonne et de la première ligne. Parmi les coefficients négatifs de la ligne d'indice, le plus grand en valeur absolue est sélectionné. Ensuite, les éléments de la colonne membre libre de la table simplex sont divisés en éléments du même signe de la colonne principale.
4. Construire un nouveau plan de référence. Le passage à un nouveau plan s'effectue suite au recalcul du tableau simplex selon la méthode Jordan-Gauss.

S'il faut trouver l'extremum de la fonction objectif, alors on parle de trouver la valeur minimale (F(x) → min, voir l'exemple d'une solution pour minimiser une fonction) et la valeur maximale ((F(x ) → max, voir l'exemple d'une solution pour maximiser une fonction)

Une solution extrême est obtenue à la limite de la région des solutions réalisables à l'un des sommets des points d'angle du polygone, ou sur le segment entre deux points d'angle adjacents.

Théorème fondamental de la programmation linéaire. Si la fonction objectif ZLP atteint une valeur extrême à un moment donné dans la région des solutions réalisables, alors elle prend cette valeur au point critique. Si la fonction objectif ZLP atteint une valeur extrême en plusieurs points d'angle, alors elle prend la même valeur en n'importe laquelle des combinaisons linéaires convexes de ces points.

L'essence de la méthode simplexe. Le déplacement vers le point optimal s'effectue en passant d'un point d'angle au point voisin, ce qui rapproche et plus rapidement X opt. Un tel schéma d'énumération de points, appelé la méthode simplexe, suggéré par R. Dantzig.
Les points d'angle sont caractérisés par m variables de base, de sorte que la transition d'un point d'angle à un point voisin peut être accomplie en changeant une seule variable de base dans la base en une variable d'une non-base.
La mise en œuvre de la méthode simplexe, en raison des diverses caractéristiques et formulations des problèmes LP, présente diverses modifications.

La construction des tables simplexes se poursuit jusqu'à ce que la solution optimale soit obtenue. Comment pouvez-vous utiliser un tableau simplexe pour déterminer que la solution à un problème de programmation linéaire est optimale ?
Si la dernière ligne (valeurs de la fonction objectif) ne contient pas d'éléments négatifs, elle trouvera donc le plan optimal.

Remarque 1. Si l'une des variables de base est égale à zéro, alors le point extrême correspondant à une telle solution de base est dégénéré. La dégénérescence se produit lorsqu'il existe une ambiguïté dans le choix de la ligne directrice. Vous ne remarquerez peut-être pas du tout la dégénérescence du problème si vous choisissez une autre ligne comme guide. En cas d'ambiguïté, la ligne avec l'index le plus bas doit être sélectionnée pour éviter les boucles.

Remarque 2. Soit à un point extrême toutes les différences simplexes non négatives D k ³ 0 (k = 1..n+m), c'est-à-dire une solution optimale est obtenue et il existe A k - un vecteur sans base pour lequel D k ​​= 0. Alors le maximum est atteint au moins en deux points, c'est-à-dire il existe un optimal alternatif. Si nous introduisons cette variable x k dans la base, la valeur de la fonction objectif ne changera pas.

Remarque 3. La solution au problème dual se trouve dans le dernier tableau simplexe. Les m dernières composantes du vecteur des différences simplexes (dans les colonnes des variables d'équilibre) sont la solution optimale au problème dual. Les valeurs des fonctions objectives des problèmes directs et duaux aux points optimaux coïncident.

Remarque 4. Lors de la résolution du problème de minimisation, le vecteur avec la plus grande différence simplexe positive est introduit dans la base. Ensuite, le même algorithme est appliqué que pour le problème de maximisation.

Si la condition « Il est nécessaire que les matières premières de type III soient entièrement consommées » est précisée, alors la condition correspondante est une égalité.