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 qui en résulte, nous remplaçons le système d'inégalités par le système équations linéaires en y introduisant des variables supplémentaires non négatives ( 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 entrons les coefficients pour fonction objectif et sa signification même a le signe opposé ;
(7) Sélectionnez dans la dernière ligne le plus grand (module) 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à - plan optimal trouvé, nous passons à 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
Lire aussi :
|
Théorème (sur le choix d'un élément résolvant)
S'il y a des éléments négatifs dans plusieurs colonnes de la z-ème ligne, alors la colonne de résolution doit être choisie comme étant la colonne qui a le produit maximum de la valeur absolue du coefficient dans la z-ème ligne et le rapport simplex minimum dans cette colonne.
Preuve:
Laissez l'élément être l'élément permettant. Suite à l'étape d'élimination de Jordan modifiée, le terme libre dans la ligne z sera le nombre égal à . Puisque et , la parenthèse dans cette expression sera toujours positive. Et comme la valeur de la fonctionnelle est toujours égale au terme libre, cette parenthèse représente l'ajout à la fonctionnelle qui est obtenu grâce à la démarche franchie.
Plus l'incrément que la fonctionnalité reçoit à chaque étape est grand, moins il faudra d'étapes (c'est-à-dire de calculs) pour atteindre l'optimum. L'ampleur de cet incrément dépend de la valeur absolue du coefficient et de la valeur du plus petit rapport simplex. Autrement dit, la colonne de résolution sera la colonne qui contient le maximum de ce produit.
Exemple : programmation linéaire :
Trouvons le maximum de la fonction
sous restrictions
Solution : créons une table Jordan.
Puisque ses membres libres sont positifs, le plan est un plan de soutien. Cependant, ce n’est pas optimal puisque les coefficients de la ligne z sont négatifs. On choisit parmi eux celui avec le plus grand produit en valeur absolue et le plus petit rapport simplexe. Nous considérons que la troisième colonne est résolvante, car elle a la plus grande valeur absolue 8 et les relations simplexes : respectivement ( , donc l'élément 1 de la troisième colonne sera résolu). Nous prenons l’étape d’élimination de Jordan modifiée et arrivons au tableau suivant.
À en juger par les coefficients de la ligne z, dans le tableau résultant solution optimale non accompli. Nous prenons la deuxième colonne avec un coefficient négatif dans la ligne z comme colonne de résolution (seule la première peut être la ligne de résolution). Une fois l’élément 5 trouvé, nous passons à l’étape suivante.
Dans la ligne z, tous les coefficients sont positifs ; le plan obtenu en assimilant les variables supérieures à zéro et les variables secondaires aux termes libres est optimal. On écrit les valeurs des principales inconnues du tableau : On calcule la valeur maximale de la fonctionnelle dans la dernière cellule du tableau :
Dans le tableau final, tous les déterminants sont non négatifs. Cela suggère que pour des valeurs inconnues, la fonctionnelle atteint un maximum
On suppose généralement qu'il n'y a aucun point dans l'ensemble des plans-problèmes où le dénominateur de la fonction objectif est égal à zéro. Sans perte de généralité, on peut supposer que .
Dans un problème de programmation linéaire fractionnaire, l’extremum de la fonction objectif est atteint au sommet du polyèdre solution. Cette similitude avec la programmation linéaire permet de résoudre des problèmes linéaires fractionnaires à l'aide de la méthode Stiefel.
Les calculs sont présentés sous forme de tableaux de Jordan. Dans ce cas, deux lignes inférieures sont allouées à la fonctionnelle : dans la première, nous écrivons les coefficients du numérateur et dans la seconde, le dénominateur. Le tableau 1 correspond au problème initial :
| –X 1 | –X 2 | … | –xj | … | –xn | ||
| oui 1 | un 11 | un 12 | … | un 1 j | … | un 1 n | un 1 |
| … | ……………………………………… | … | |||||
| et je | un je 1 | un je 2 | … | un ij | … | un dans | un je |
| … | ……………………………………… | … | |||||
| ouais | suis 1 | suis 2 | … | un mj | … | une minute | suis |
| z 1 | –p 1 | –p 2 | … | –p j | … | –pn | |
| z 2 | –q 1 | –q 2 | … | –q j | … | –qn |
À travers et je les différences entre les parties droite et gauche du système de restrictions sont indiquées :
et je= un je–un je 1 X 1 – un je 2 X 2 –un je 3 X 3 – … – une dans x n ³ 0.
Nous appellerons variables libres les variables situées dans la ligne de titre supérieure du tableau Jordan. Donner des variables gratuites valeurs nulles, on obtient la solution de base originale : . Ce vecteur ne peut pas être un plan de référence, car le dénominateur de l'objectif fonctionnel sur celui-ci est égal à zéro ( z 2 = 0). Par conséquent, parmi les membres libres du système de restrictions un 1 ,…, suis il doit y avoir des nombres négatifs (sinon la solution de base serait un plan de référence).
Par étapes d'éliminations de Jordan modifiées, de la même manière que lors de la résolution d'un problème de programmation linéaire (voir), on retrouve le plan originel du problème. Par conséquent kétapes on arrive au tableau 2 :
| –oui 1 | … | –xj | … | –xn | ||
| X 1 | b 11 | … | b 1 j | … | b 1 n | b 1 |
| .… | ……………………………………… | |||||
| et je | b je 1 | … | b je | … | poubelle | b je |
| …. | ……………………………………. | |||||
| ouais | bm 1 | … | b mj | … | bmn | bm |
| z 1 | F 1 | … | f j | … | fn | F |
| z 2 | g 1 | … | g j | … | g n | g |
Dans le tableau 2 tous les membres libres b je sont non négatifs, ce qui garantit la non-négativité des variables de base X 1 ,…, ouais. De plus (en raison du dénominateur positif de la fonction objectif z 2 sur un jeu de plans de référence). Le plan de référence initial est un vecteur de coordonnées . La valeur de la fonction objectif sur le plan de référence d'origine est .
Notez que si à l'une des étapes d'élimination de Jordan, l'une des conditions gratuites b je serai négatif, et tous les autres éléments je Les lignes seront non négatives, alors le problème n'aura pas de solution en raison du manque de plans.
Voyons comment la fonction objectif évolue lorsqu'on passe d'un plan de référence du problème à un autre. Il s'avère que le signe de la différence entre les nouvelles et anciennes valeurs de la fonction coïncide avec le signe du déterminant. Si. Parce que Puisque le polyèdre solution ne contient qu’un nombre fini de plans de support, alors en un nombre fini d’étapes nous arriverons au plan de support optimal.
Ce processus ne peut être entravé que par le caractère illimité du polyèdre des solutions. Dans ce cas, la fonction objectif peut avoir un extremum dit asymptotique (dans ce cas, un maximum). Le maximum asymptotique d'un problème de programmation linéaire fractionnaire est la limite supérieure exacte de la fonction objectif sur un ensemble de plans, qui n'est atteinte sur aucun des plans. Dans le cas où le problème présente un maximum asymptotique, dans le domaine des plans il est toujours possible de trouver un plan (et non de référence) sur lequel la fonction objectif prend une valeur arbitrairement proche du maximum asymptotique.
La méthode Stiefel permet de trouver non seulement le maximum, mais également le maximum asymptotique d'un problème de programmation linéaire fractionnaire. Examinons de plus près la transition d'un plan à l'autre et découvrons-le. Sélection de l'élément de résolution dans jème colonne, il faut se laisser guider par le principe de la relation simplexe minimale. Ceux. élément habilitant dans j La -ième colonne doit se trouver dans la ligne pour laquelle la relation simplexe est positive et minimale.
Parce que après avoir retrouvé le plan de référence initial, tous les côtés droits b je devenir non négatif, alors l'élément résolvant j La ème colonne peut être l'un de ses éléments positifs (). Si à chaque étape de la recherche du plan de référence optimal il y a (au moins un) élément positif dans la colonne de résolution sélectionnée, alors un tel problème a un maximum (éventuellement plusieurs).
Cependant, si à l'une des étapes une estimation est inférieure à zéro et que tous les éléments jème colonne. Ensuite, dans cette colonne, guidé par le principe de la relation simplex minimale, l'élément résolvant ne peut pas être sélectionné. Augmenter les valeurs de la variable libre xj de 0 à (voir tableau 2), on reste tout le temps dans le domaine des plans. Cela est dû au fait qu'une augmentation de la variable xj ne provoque pas de changement de signe en moins pour aucune des variables de base.
Notons par M la limite vers laquelle, en augmentant de façon monotone, tend la fonction objectif vers : . Ce nombre est le maximum asymptotique.
| 2 |
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. 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 | 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 |
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ément principal ou résolvant. La recherche de l'élément principal termine le travail avec chaque table simplexe régulière.
3ème étape. Une nouvelle table simplex est calculée dont les éléments sont recalculés à partir des éléments de la table simplex de l'étape précédente et sont marqués d'un nombre premier, c'est-à-dire b" j , une" ji , c" je , F" 0 . Les éléments sont recalculés à l'aide des formules suivantes :
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 de tête, 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é élément principal.
6ème étape. selon les règles décrites à l’étape 3. La procédure se poursuit jusqu'à ce qu'une solution optimale soit trouvée ou qu'il soit conclu qu'elle n'existe pas.
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 au-dessus de 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, il se produit ce qu'on appelle un cyclage, 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 produisent sélection aléatoire 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. La figure 3 définit une solution de base admissible, à laquelle correspond le sommet de l'ODZP de la figure 1. 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 Tâches
Examinons en détail comment les tableaux simplex sont recalculés (en utilisant l'exemple d'une itération). Qu'il y ait un tableau simplexe présenté sur Fig. 1. Le problème de la maximisation de la fonction objectif est résolu. La colonne résolution correspond à la variable x2, et la chaîne d'activation de la variable x3(chiffres rouges), à leur intersection se trouve un élément résolvant (une cellule avec un fond gris). La première chose que nous devons faire est de remplacer. La ligne de résolution indique quelle variable doit être dérivée de la base (dans notre cas x3), et la colonne de résolution indique quelle variable doit être incluse dans la base (dans notre cas x2). Sur Figure 2 le fait du remplacement est souligné par une ligne bleue.
Recalculons maintenant les éléments de la ligne de résolution. Pour ce faire, nous divisons simplement chacun d'eux en un élément résolvant (dans notre exemple 4 ). Et nous remettrons à zéro tous les éléments de la colonne de résolution, à l’exception de l’élément de la ligne de résolution. (Regarder Figure 2)
Image 1
Les cellules restantes du tableau (à l'exception de la colonne "Ratio") sont recalculées à l'aide de ce que l'on appelle règle rectangulaire, dont la signification est plus facile à comprendre avec un exemple. Supposons que nous devions recalculer l'élément entouré par Fig. 1 contour rouge. Tracez mentalement une ligne verticale à partir de celui-ci et ligne horizontale jusqu'à l'intersection, avec la ligne de résolution et la colonne de résolution. Les éléments situés aux intersections sont entourés de contours bleus (Voir Fig. 1). La nouvelle valeur de l'élément "rouge" sera égale à la valeur actuelle de l'élément moins le produit de l'élément "bleu" divisé par l'élément résolvant ("gris") (Voir Fig. 1). C'est-à-dire: 18 - (64 * -1) / 4 = 34
, est familier ici" *
" montre l'opération de multiplication.
On écrit la nouvelle valeur au même endroit (Voir Figure 2 contour rouge).
Figure 2
Grâce à cette règle, on remplit tous les éléments vides du tableau (sauf la colonne « Relation »). Voir Figure 3. Après cela, nous définirons une nouvelle colonne de résolution. Pour ce faire, analysons la ligne "Q" et puisque notre tâche est au maximum, nous y trouverons élément positif maximum, il déterminera la colonne de résolution. Dans notre cas c'est 3/2 . Tous les éléments de la colonne de résolution sont affichés en rouge (Voir Figure 3). Si après la prochaine itération dans la ligne "Q" il n'y aura aucun élément positif - cela signifie que la solution optimale a été atteinte, les itérations s'arrêtent. Si notre problème était au minimum, alors la colonne de résolution serait déterminée par l'élément négatif minimum, et si après la prochaine itération dans la ligne "Q" il n'y a aucun élément négatif, ce qui signifie que la solution optimale a été atteinte.
figure 3
Remplissons maintenant la colonne « Attitude ». Pour ce faire, vous devez diviser l'élément correspondant (dans la même ligne) de la colonne « Décision » par l'élément correspondant de la colonne résolution (Voir Figure 3). note, Quoi cette opération détenu seulement pour les positifséléments de la colonne et de la ligne de résolution "Q" n'est pas impliqué dans cette opération. Si après quelques itérations, il n'y a aucun élément positif dans la colonne de résolution, alors cette tâche est insoluble en raison du caractère illimité de la fonction objectif, les itérations s'arrêtent.
Après avoir rempli la colonne "Relation", nous définirons une nouvelle ligne de résolution. Il est déterminé élément minimal de la colonne « Attitude ». Dans notre cas c'est 32 , tous les éléments de la chaîne de résolution sont affichés en rouge (voir Figure 3). C'est là que se termine la prochaine itération, à la prochaine itération la variable x2 sera supprimée de la base (la nouvelle ligne de résolution nous l'indique), sa place sera prise par la variable x1(la nouvelle colonne de résolution nous l'indique) et tous les calculs seront répétés à nouveau.
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 :
- 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 nombre qui donne le plus petit rapport devient l'élément résolvant par rapport auquel la table simplex sera recalculée. La ligne contenant cet élément est appelée ligne d'activation. S’il n’y a aucun élément positif dans la colonne résolution, alors le problème n’a pas de solution. Après avoir déterminé l’élément résolvant, ils procèdent au recalcul d’une nouvelle table simplexe.
- Règles pour remplir un nouveau tableau simplex. L'unité est mise à la place de l'élément de résolution, et les autres éléments sont supposés égaux 0 . Le vecteur de résolution est ajouté à la base, dont le vecteur zéro correspondant est exclu, et les vecteurs de base restants sont écrits sans modifications. Les éléments de la ligne de résolution sont divisés par l'élément de résolution et les éléments restants sont recalculés selon la règle du rectangle.
- Ceci est fait jusqu'à F– tous les éléments de la chaîne ne deviendront pas positifs.
Envisageons de résoudre le problème en utilisant l'algorithme discuté ci-dessus.
Donné:
Nous 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 à