Agence fédérale pour l'éducation

État établissement d'enseignement formation professionnelle supérieure

Université technique d'État de Perm

Branche Lysvenski

Département d'économie

Cours

en discipline" Analyse du système et recherche opérationnelle"

sur le thème : « Méthode Simplex sous forme de présentation »

Complété par un élève du groupe VIVT-06-1 :

Startseva N.S.

Vérifié par le professeur :

Moukhametianov I.T.

Lysva 2010

Introduction. 3

Programmation mathématique. 5

Méthode graphique. 6

Méthode du simplexe tabulaire. 6

Méthode base artificielle. 7

Méthode du simplexe modifiée. 7

Méthode Dual Simplex. 7

Vue générale du problème programmation linéaire. 9

Résoudre un problème de programmation linéaire à l'aide de la méthode du simplexe. 11

Procédures informatiques de la méthode simplexe. 11

Théorème 1 : 13

Théorème 2 : 14

Théorème 3 : 15

Théorème 4 : 15

Théorème 5 : 15

Transition vers le nouveau plan de référence. 15

Double tâche. 17

Théorème 1 (premier théorème de dualité) 18

Théorème 2 (théorème de la deuxième dualité) 18

Conclusion. 20

La solution optimale au problème de programmation linéaire figure parmi les solutions de référence. L'idée de la méthode du simplexe est que, selon une certaine règle, les solutions de référence sont triées jusqu'à ce que la solution optimale soit trouvée parmi elles. En triant les solutions de référence, nous trions essentiellement diverses variables de base, c'est-à-dire. , à l'étape suivante, une variable est transférée parmi les variables de base, et à la place une variable du nombre de variables libres vers le nombre de variables de base.

7x 1 +5x 2 →maximum

x 3 =19-2x 1 -3x 2 (0;0;19;13;15;18)

x 4 =13-2x 1 -x 2 plan de référence original

x 6 =18-3x 1 F(x 1 , x 2)=7*0+5*0=0

x je ≥0, (i=1,…n)

D'un point de vue intuitif, il est clair qu'il sera naturel d'augmenter x 1, puisque son coefficient est supérieur à celui de x 2. En laissant x 2 =0, on peut augmenter jusqu'à ce que x 3 , x 4 , x 5 , x 6 restent non négatifs.

x 1 =min(19/2;13/2;∞;18/3)=6

Cela signifie que lorsque x 1 =6, x 6 =0, c'est-à-dire que x 1 entre dans le nombre de base et x 6 entre dans le nombre de libres.

x 3 =19-2(6-1/3 x 6)-3 x 2 =19-12+2/3 x 6 -3 x 2 =7+2/3 x 6 -3 x 2

x 4 =13-2(6-1/3 x 6)- x 2 =1+2/3 x 6 - x 2

F(x 2 ; x 6) =42-7/3 x 6 +5 x 2

Avec un plan de référence donné (6;0;7;1;15;0) x 2, transfert des variables libres aux variables de base :

x 2 =min(∞;7/3;1/11;15/3)=1

Express x 2 à x 4

x2 =1+2/3 x6 - x4

Nous exprimons les variables inconnues et la fonction objectif en termes de variables libres :

x 3 =7+2/3 x 6 -3(1+2/3x 6 –x 4)= 7+2/3 x 6 -3-2x 6 +3x 4 =4-4/3x 6 +3 x 4

x 5 = 12-2x 6 +3x 4 -

F=42-7/3 x 6 +5(1+2/3x 2 - x 4) =47-7/3x 6 +10/3x 6 -5x 4 =47+x 6 -5x 4

x 6 est positif, il peut donc être augmenté

x6 =min(18;∞;3;6)=1

x 4 =4/3-4/9 x 6 - 1/3x 3

F=47+x 6 -5(4/3-4/9-1/3x 3)

DANS fonction objectif tous les coefficients des variables sont négatifs, la valeur de la fonction ne peut pas être augmentée, on transforme de même les variables restantes, on trouve le plan de référence, à partir duquel on détermine x 1, x 2.

1. L'intersection d'ensembles fermés, un ensemble de restrictions non triviales.

2. L'ensemble des solutions d'un système d'équations et d'équations linéaires non strictes est fermé.

αX=(αx 1 ,x 2 ,…, αxn)

X+Y=(x 1 +y 1, x 2 +y 2,… x n +y n)

Les coordonnées linéaires X 1 ,X 2 ,…X n sont appelées point P=λ 1 x 1 + λ 2 x 2 +…+ λ k x k

Définir P=(λ 1 x 1 + λ 2 x 2 +…+ λ k x k ) 0≤ h i ≤1 pour i= 1,…k n åR i =1, 1≤ i ≤k combinaison linéaire convexe de points x 1 ,x 2 ,…x n . Si k=2, alors cet ensemble est appelé un segment. X 1,X 2 – extrémités du segment. Un point d'angle d'un ensemble fermé est un point qui n'est pas une combinaison linéaire non triviale de points dans l'ensemble (point d'angle).

La non-trivialité signifie qu’au moins un des λ est différent de 0 ou 1.

Toute solution de référence à un problème de programmation linéaire constitue un point central de la région des solutions réalisables.

Si un problème de programmation linéaire a la seule solution, il se situe alors parmi les points d’angle de l’ODR. Et s'il y a plus d'une solution, alors parmi les solutions il y en a plusieurs angulaires, telles que l'ensemble de toutes les solutions est leur combinaison linéaire convexe.

La méthode du simplexe consiste à trouver d'abord une certaine solution de référence au problème (le plan de référence initial), puis, en passant délibérément d'un plan de référence à un autre, à rechercher le plan optimal. S'il y en a plusieurs, alors toutes celles des coins sont trouvées et l'ensemble des solutions est représenté comme leur combinaison linéaire.

Passer à un nouveau plan de référence

F1 =F(x1); F 2 =F(x 2) F 2 -F 1 =-υ k Δ k =F 2 peut être prouvé, où υ k est le minimum considéré ci-dessus, qui est déterminé en introduisant la k-ième variable dans la base, et Δ k =åс j x j ( 1) -С k, où n ≤ j ≤1, X 1 =(x 1 (1) ;x 2 (1) ;…x n (1)) est une estimation de la k-ième variable , donc si le problème du maximum est résolu, alors la valeur ΔF 2 doit être positive, Δk doit être négative. Lors de la résolution de problèmes minimaux, ΔF 2 est négatif, Δ k est positif. Ces valeurs sont calculées et si parmi ΔF 2 toutes les valeurs ne sont pas positives, alors lors de la résolution de problèmes sur le minimum, l'inverse est vrai. Si, lors de la résolution d'un maximum, il y en a plusieurs positifs parmi ΔF 2, alors nous introduisons dans la base le vecteur auquel cette valeur atteint un maximum, et si le problème est résolu pour un minimum et parmi ΔF 2 il y a plusieurs négatifs ceux, puis le vecteur avec valeur la plus basseΔF 2, c'est-à-dire avec le plus grand valeur absolue. Lorsque ces conditions sont remplies, la plus grande variation possible de la valeur de la fonction est garantie.

La solution au problème sera unique si pour tout vecteur x k non inclus dans la base, estime Δ k ≠0, si au moins un de ces Δ k = 0, alors la solution n'est pas unique, pour trouver une autre solution on passe à un autre plan de référence, y compris en base x k, où Δ k =0. C'est trop solutions de support transformez-les en combinaison linéaire, qui sera la solution au problème.

Si pour un certain Δ k les coefficients de la variable x k ≤ 0 contredisent la condition d'optimalité, alors le système de restrictions n'est pas limité, c'est-à-dire plan optimal n'existe pas.

Double problème

Le problème dual (DP) est un problème de programmation linéaire auxiliaire formulé en utilisant certaines règles directement à partir des conditions du problème direct. L'intérêt de déterminer la solution optimale à un problème direct en résolvant son double problème est dû au fait que les calculs lors de la résolution d'un DP peuvent s'avérer moins complexes que lors de la résolution d'un problème direct (DP). La complexité des calculs lorsque décision du PPP dépend davantage du nombre de contraintes que du nombre de variables. Pour accéder au PD, il faut que le PD soit rédigé sous forme canonique standard. Lors de la présentation du PP sous forme standard, les variables x j incluent également des variables redondantes et résiduelles.

Le double problème est le suivant :

1. m variables correspondant au nombre de contraintes du problème direct ;

2. n restrictions correspondant au nombre de variables du problème direct.

Le problème dual est obtenu par transformation structurelle symétrique des conditions du problème direct selon suivre les règles:

· Chaque contrainte b i PD correspond à une variable y i PD ;

· Chaque variable x j PD correspond à une contrainte C j PD ;

· Les coefficients pour x j dans les contraintes PD deviennent les coefficients du côté gauche de la contrainte PD correspondante ;

· Les coefficients C j pour x j dans la fonction cible du PD deviennent constants du côté droit de la contrainte PD ;

· Les constantes de contrainte b i PD deviennent des coefficients de la fonction cible PD.

Considérez les deux problèmes suivants :

F = С 1 x 1 +С 2 x 2 +... +С n x n →max

(5)

une 11 x 1 + une 22 x 2 + ... + une 1m x n ≤ b 1

une 21 x 1 + une 22 x 2 + ... + une 2m x n ≤b 2

une m1 x 1 + une m2 x 2 + ... + une mn x n ≤b m

x j ≥0 j=1,…,n

Z = b 1 x 1 +b 2 x 2 +... +b n x n →min

(6)

une 11 oui 1 + une 21 oui 2 + ... + une m1 oui 1 ≤ C 1

une 12 oui 1 + une 22 oui 2 + ... + une m 2 oui 2 ≤C 2

. . . . . . . . . . . . . . . . . . . . . . .

une 1 n y n + une 2 m y n + ... + une nm y n ≤C n

Dans ce travail de cours les fondations ont été posées méthodes mathématiques résoudre des problèmes de programmation linéaire. Par conséquent, une plus grande attention a été accordée aux sections suivantes :

1. Fondements des méthodes mathématiques et leur application ;

2. Résoudre des problèmes en utilisant la méthode du simplexe.

L'idée principale de la méthode du simplexe modifiée est d'utiliser le courant matrice inverse(et les données sources du problème) lors de l'exécution des calculs nécessaires pour déterminer les variables à inclure et à exclure. Représenter une matrice inverse sous forme multiplicative vous permet de calculer une séquence de matrices inverses directement à partir des données d'origine sans utiliser plusieurs opérations d'inversion pour chaque base. Comme dans la méthode simplexe habituelle, dans ce cas la base initiale est toujours la matrice identité I, dont l'inverse est cette matrice elle-même. Par conséquent, si
- séquence de matrices inverses correspondant aux itérations 1, 2,…,i, et
est la suite de matrices qui leur correspondent, alors

La séquence de substitutions conduit à la formule suivante :

(2.23)

Il convient de souligner que la représentation multiplicative de la matrice inverse n'est pas procédure nécessaire pour implémenter le schéma de calcul de la méthode simplexe modifiée, et à chaque itération, vous pouvez utiliser n'importe laquelle des méthodes pour inverser la base actuelle. Lors de l'utilisation de la méthode du simplexe modifiée, il est important que les matrices inverses soient calculées de manière à réduire l'impact des erreurs d'arrondi de la machine.

Les étapes de l'algorithme de la méthode simplex modifiée sont essentiellement les mêmes que celles de l'algorithme de la méthode simplex conventionnelle. Après avoir trouvé la base initiale I, le vecteur correspondant de coefficients de la fonction objectif est déterminé , dont les éléments se forment selon que les variables de base initiales sont résiduelles (redondantes) ou artificielles.

1. 2.7.2. Représentation multiplicative d'une matrice inverse

Dans la représentation multiplicative de la matrice inverse, une opération d'algèbre matricielle est utilisée pour calculer les éléments de la matrice inverse de la nouvelle matrice de vecteurs de base à partir de la matrice inverse connue de la base précédente, à condition que les deux bases considérées ne diffèrent que par un vecteur colonne. Cette méthode de représentation de la matrice inverse est pratique à utiliser spécifiquement dans le schéma de calcul de la méthode simplex, puisque les bases correspondant à chacune de deux itérations successives ne diffèrent que dans une seule colonne (en raison du remplacement du vecteur colonne éliminé du courant base avec un nouveau vecteur colonne). En d’autres termes, la matrice de base actuelle et une nouvelle matrice de base
, correspondant à l’itération suivante, ne diffèrent que par une seule colonne. Avec la représentation multiplicative de la matrice inverse
correspondant à la nouvelle base, elle est calculée en multipliant à gauche l'inverse de la matrice actuelle
dans une matrice formée selon certaines règles .

Définissons la matrice d'identité comme suit:

(2.24)

Où - vecteur colonne unitaire avec le i-ième élément, égal à un, et d'autres éléments, égal à zéro. Supposons que les matrices soient connues Et
, et vecteur matrices est remplacé par un nouveau vecteur ; comme il est d'usage lorsqu'on décrit la méthode du simplexe, le vecteur est défini comme inclus dans la base, et le vecteur - comme exclu de la base. Pour simplifier l'écriture des relations mathématiques, nous utilisons la définition suivante
,en même temps représentera le kème élément
. Alors la nouvelle matrice inverse
peut être calculé à l’aide de la formule suivante :

(2.25)

à condition que
. Si
, matrices
n'existe pas. Notez que la matrice obtenu à partir de la matrice en remplaçant son r-ième vecteur colonne colonne .

Il existe de nombreuses méthodes pour résoudre les problèmes de programmation linéaire. Considérons l'une d'elles, la méthode du simplex améliorée (modifiée)

Tout d’abord, expliquons ce qu’est la méthode simplexe. Le mot SIMPLEX dans son sens ordinaire signifie simple, non composite, par opposition à COMPLEXE.

Cette méthode a reçu plusieurs diverses formes(modifications) et a été développé en 1947 par G. Danzig.

L'essence de la méthode simplexe est que si le nombre d'inconnues plus de numéro des équations, alors ce système incertain avec d'innombrables solutions. Pour résoudre le système, toutes les inconnues sont arbitrairement divisées en basiques et gratuites. Le nombre de variables de base est déterminé par le nombre d'équations linéairement indépendantes. Les inconnues restantes sont gratuites. Ils reçoivent des valeurs arbitraires et sont remplacés dans le système. Tout ensemble d’inconnues libres peut recevoir un nombre infini de valeurs arbitraires, ce qui donnera un nombre infini de solutions. Si toutes les inconnues libres sont mises à zéro, alors la solution sera constituée des valeurs des inconnues de base. Cette solution est dite basique.

Dans la théorie de la programmation linéaire, il existe un théorème qui stipule que parmi les solutions de base du système, on peut trouver la solution optimale, et dans certains cas, plusieurs solutions optimales, mais toutes fourniront un extremum de la fonction objectif. Ainsi, si vous trouvez un plan de base et que vous l'améliorez, vous obtiendrez solution optimale. La méthode du simplexe est construite sur ce principe.

L'une des modifications de la méthode simplex est la méthode simplex améliorée. Dans la littérature, cette méthode se retrouve également sous le nom de méthode matricielle inverse ou méthode du simplexe modifié.

Lors de la résolution de problèmes de programmation linéaire dans lesquels n (le nombre de variables) est nettement supérieur à m (le nombre de contraintes), la méthode du simplexe améliorée nécessite beaucoup moins d'opérations de calcul et de mémoire informatique que les autres.

La méthode simplex améliorée met en œuvre la même idée de base que la méthode simplex conventionnelle, mais ici à chaque itération, ce n'est pas la totalité de la matrice A -1, l'inverse de la matrice de contraintes A, qui est recalculée, mais seulement la partie qui se rapporte à la base actuelle A. X.

Considérons étape par étape les étapes de résolution d'un problème de programmation linéaire à l'aide de la méthode du simplexe améliorée :

• 1. Au début du premier cycle on connaît la matrice inverse ( matrice d'identité), solution basique x b = b.
• 2. Pour chaque variable non fondamentale, on forme la différence caractéristique j à l'aide de l'équation :

j = c j -- = c j -- P j , (2)

où sont les variables duales, qui peuvent être trouvées comme suit :

où c x est le vecteur des coefficients de la fonction objectif pour les variables de base.

3. En supposant que la règle standard de sélection de la colonne de saisie soit utilisée, on trouve :

• 4. Si s 0, la procédure s'arrête. La solution de base actuelle est optimale.
• 5. Si s 0, calculez la colonne transformée :

= (, ...,) . (2.4)

Si tous valent 0, la procédure s'arrête : l'optimum est illimité.

7. Sinon, on retrouve la variable dérivée de la base :

8. Nous construisons une matrice agrandie :

et transformez-le avec l'élément principal. Les m premières colonnes donnent la matrice inverse de la nouvelle base.

9. Transformez la solution de base :

x b je x b je -- * , je r, (2.7)

et passez à l'étape 2.

Cette option est également appelée méthode du simplexe modifié car elle réduit la quantité de calcul à chaque étape. L’idée est qu’à chaque étape, la forme canonique du problème pour la base actuelle peut être obtenue indépendamment des autres formes directement à partir de la notation originale du problème LP standard.

Pour ce faire, vous avez besoin de :

• 1. Conserver l'enregistrement original de la tâche tout au long du fonctionnement de la méthode ; c'est le prix que vous devez payer pour de meilleures performances ;
• 2. Utiliser les coefficients dits simplex - multiplicateurs p - pour une transition directe de la représentation originale du problème à sa forme de base canonique actuelle ;
• 3. Utilisez la base inversée BO№ - une matrice de taille m x m, qui vous permet de calculer la première colonne aґs à chaque étape et de mettre à jour les facteurs simplex p.

La méthode simplex améliorée présente des avantages significatifs par rapport à la forme standard. Cela s'applique aux exigences de précision, de vitesse et de mémoire. La plupart Ces avantages sont déterminés par le fait qu'en règle générale, les matrices de grande taille problèmes linéaires(c'est-à-dire avec n>m>100) sont faiblement remplis, contenant un petit pourcentage d'éléments non nuls.

Une densité de 5 % ou moins est courante. Une forme améliorée de la méthode simplexe est mieux à même de tirer parti des avantages qui en découlent. Sous cette forme, les différences caractéristiques et le vecteur principal sont calculés directement à partir des données originales. Étant donné que la matrice d'origine est mal remplie et que la multiplication ne doit être effectuée que lorsque les deux facteurs sont différents de zéro, le temps de calcul est considérablement réduit.

De plus, l’utilisation uniquement des données originales signifie que la possibilité d’accumuler des erreurs d’arrondi est réduite. En revanche, les tableaux simplex standards, même s'ils sont initialement peu peuplés, sont rapidement remplis d'éléments non nuls grâce à un processus itératif. Ainsi, le temps de calcul augmente, et comme chaque table est calculée à partir de la précédente, l'accumulation d'erreurs peut commencer à jouer un rôle plus sérieux.

Soumettre votre bon travail à la base de connaissances est facile. Utilisez le formulaire ci-dessous

bon travail sur le site">

Les étudiants, étudiants diplômés, jeunes scientifiques qui utilisent la base de connaissances dans leurs études et leur travail vous en seront très reconnaissants.

Documents similaires

Solution géométrique tâches standards programmation linéaire à deux variables. Méthode universelle solutions problème canonique. L'idée principale de la méthode simplexe, mise en œuvre à l'aide d'un exemple. Implémentation tabulaire d'une méthode simplexe simple.

résumé, ajouté le 15/06/2010


Types de problèmes de programmation linéaire et formulation de problèmes. L'essence de l'optimisation en tant que branche des mathématiques et les caractéristiques des principales méthodes de résolution de problèmes. Le concept de la méthode simplexe, réel problèmes appliqués. Algorithme et étapes de résolution du problème de transport.

travail de cours, ajouté le 17/02/2010


Résoudre des problèmes de programmation linéaire à l'aide de méthodes graphiques et simplexes. Solution du problème double à celui d'origine. Déterminer le plan optimal d'affectation des consommateurs aux fournisseurs de marchandises homogènes, sous réserve de minimiser le kilométrage total du véhicule.

test, ajouté le 15/08/2012


Utiliser la méthode simplex pour résoudre des problèmes de programmation linéaire afin de calculer le volume de production quotidien. Vérification de l'optimalité du plan. Recalcul tableau simplexe Méthode Jordan-Gauss. Elaboration d'un modèle d'un problème de transport.

test, ajouté le 18/02/2014


Modèle économique et mathématique pour obtenir un profit maximum, sa solution méthode graphique. Algorithme de résolution d'un problème de programmation linéaire par la méthode du simplexe. Compilation double problèmes et et elle solution graphique. Solution matricielle de paiement.

test, ajouté le 11/05/2014


Bases de la modélisation mathématique processus économiques. Caractéristiques générales graphique et méthodes simplexes résoudre des problèmes de programmation linéaire directe et double. Caractéristiques de la formulation et de la méthodologie pour résoudre le problème du transport.

travail de cours, ajouté le 12/11/2010


Compilation modèle mathématique tâches. Calcul du plan de transport optimal avec le coût minimum selon la méthode du potentiel. La meilleure optionéquipement mobile spécial pour assistance technique gestion de production.

test, ajouté le 01/06/2014

MÉTHODE SIMPLEX MODIFIÉELa méthode simplex n'est pas la plus efficace
procédure informatique, puisqu'elle calcule et
stocke les informations qui ne sont pas nécessaires pour le courant
itération et ne peut pas être utilisé du tout pour
prendre des décisions lors des itérations ultérieures. Pour
coefficients des variables non principales dans l'équation
(0), coefficients des principales variables introduites
dans d'autres équations et les membres droits des équations à
Chaque itération utilise uniquement celle qui est pertinente
information. Une procédure est donc nécessaire pour
peut obtenir ces informations efficacement, sans
calculs et stockage de tous les autres coefficients
(c'est la méthode du simplexe modifiée).

Il calcule et stocke uniquement les informations
nécessaire pour à l'heure actuelle, et des données importantes
transporte sous une forme plus compacte.
Il utilise des opérations matricielles, donc
il est nécessaire de décrire le problème à l'aide de matrices.
Lettres MAJUSCULES, mises en évidence en gras
représentent des matrices, des majuscules,
ceux en gras représentent
vecteurs.
Les italiques sont des quantités scalaires, le zéro étant mis en surbrillance
(0) désigne le vecteur zéro (ses éléments sont égaux
zéro, lignes et colonnes), zéro (0)
représente le nombre normal 0. En utilisant
matrices formulaire standard modèles linéaires
la programmation prend la forme :

Maximiser Z = c x,
selon
A x ≤ b et x ≥ 0,
où c est un vecteur ligne
x, b et 0 vecteurs colonnes

A - matrice
Pour la forme augmentée, vecteur colonne
variables fictives :
Restrictions :
I = (m × m matrice d'identité)
0 = (n + m éléments du vecteur zéro)

Trouver une solution de base réalisable
L'approche générale de la méthode simplexe est d'obtenir
séquence d'amélioration des solutions OA jusqu'à
jusqu'à ce que l'optimal soit trouvé
solution. L'une des caractéristiques clés
méthode simplex modifiée - comment ça
trouve une nouvelle solution OD après l'avoir définie
principal (de base) et non basique (non basique)
variables. Compte tenu de ces variables, le résultat
solution principale – solution de m équations
Dans lequel n variables non fondamentales de n + m
éléments
sont mis à zéro.

Supprimer ces n variables en les mettant à zéro,
on obtient un système d'équations m avec m variables
(variables principales (de base)) :
où est le vecteur des variables de base :
obtenu en excluant les non-basiques (non-basiques)
variables :

Et la matrice de base
Le résultat obtenu en excluant les colonnes correspondant à
coefficients des variables non fondamentales de .
(De plus, les éléments xB et les colonnes B sont dans des formats différents.
d'accord). La méthode simplexe n'introduit que les éléments de base
variables telles que B soit non dégénéré, donc
la matrice inverse B-1 existera toujours.
Pour résoudre B x B = b, les deux côtés sont multipliés par B-1 :
B-1 B x B = B-1 b.

cB est un vecteur dont les éléments sont des coefficients
fonctions objectives (y compris les zéros pour les fonctions factices)
variables) pour les éléments xB correspondants.
La fonction objectif de cette solution de base est :

Exemple:
- Itération 0
donc
donc

10.

- Itération 1
donc
donc

11.

- Itération 2
donc
donc

12. Forme matricielle pour l'ensemble actuel d'équations

Forme matricielle pour un ensemble d'équations,
apparaissant dans le tableau simplexe pour toute itération
la méthode simplex originale. Pour le système source
équations, forme matricielle comme ça:
Opérations algébriques réalisées selon la méthode du simplexe (multiplier l'équation par une constante et ajouter
produit d'une équation par une autre) sont exprimés en
forme matricielle, après avoir multiplié les deux parties
le système d'équations d'origine dans le système correspondant
matrices

13.

14.

Cette matrice aura les mêmes éléments que la matrice identité
matrice, sauf que chaque produit
pour une certaine opération algébrique, il faudra
l'espace nécessaire pour effectuer cette opération,
en utilisant la multiplication matricielle. Même après la série
opérations algébriques sur plusieurs itérations,
on peut quand même conclure que cette matrice
devrait être pour toute la série, en utilisant ce que nous savons
côté droit nouveau systèmeéquations. Après tout
itérations, xB = B-1b et Z = cB B-1b, donc les côtés droits
le nouveau système d'équations a pris la forme

15.

Puisque nous effectuons la même série
opérations algébriques avec les deux côtés
ensemble original, pour multiplier le droit et
du côté gauche, nous utilisons la même matrice.
Ainsi,
Forme matricielle souhaitée du système d'équations
après toute itération :

16.

Exemple : forme matricielle obtenue après l'itération 2
pour le problème de la verrerie en utilisant B-1 et CB :

17.

En utilisant les quantités xB = B-1 b et Z = cB B-1 b :

18.

Seul B-1 doit être reçu pour le calcul
tous les nombres de la table simplex de l'original
paramètres de la tâche (A, b, cB). N'importe lequel de ces numéros
peut être obtenu individuellement comme
En règle générale, seule la multiplication vectorielle est effectuée
(une ligne par colonne) au lieu de complet
multiplication matricielle. Numéros requis pour
effectuer des itérations de la méthode simplexe peut être
recevoir selon vos besoins sans dépenser
calculs inutiles pour obtenir tous les chiffres.

19. Bref aperçu de la méthode du simplexe modifiée

1. Initialisation : Comme dans la méthode simplex originale.
2. Itération : Étape 1 Déterminer la base saisie (principale)
variables : comme dans la méthode simplex originale.
Étape 2 Déterminez les variables de base sortantes : Comme dans l'original
méthode simplex, à l'exception de ne compter que ceux nécessaires à
de ces nombres [coefficients des variables de base introduites dans
chaque équation sauf l'Éq. (0), puis, pour chacun strictement
coefficient positif côté droit cette équation].
Étape 3 Déterminez une nouvelle solution OD : obtenez B-1 et définissez xB=B-1b.
3. Analyse d'optimalité : Comme dans la méthode simplex originale, pour
sauf à compter uniquement les nombres nécessaires à cette analyse,
c'est-à-dire les coefficients des variables non fondamentales (non fondamentales) dans
Équation (0).
A l'étape 3 de l'itération, B-1 peut être obtenu à chaque fois en utilisant
standard programme informatique pour l'inversion (inversion)
matrices. Puisque B (puis B-1) change peu d’une itération à
autre, il est plus efficace d'obtenir un nouveau B-1 (noté B-1 nouveau) à partir de
B-1 dans l'itération précédente (B-1 ancien). (Pour la solution OA originale).