Objet de la prestation. Calculatrice en ligne utilisée pour résoudre des problèmes de programmation linéaire Méthode P sous les formes d'enregistrement suivantes : la forme d'enregistrement de base de la méthode simplex, sous la forme d'un tableau simplex, dans la méthode simplex modifiée.
Instructions pour résoudre les problèmes méthode double simplexe. Sélectionnez le nombre de variables et le nombre de lignes (nombre de contraintes), cliquez sur Suivant. La solution obtenue est stockée dans Fichier Word(voir un exemple de solution utilisant la méthode dual simplex).
Dans le même temps, des restrictions comme x je ≥ 0 n'en tenez pas compte.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
Utiliser le service dans mode 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, méthode graphique (géométrique), méthode de Brown .
Extremum d'une fonction de deux variables
Problèmes de programmation dynamique
Répartir 5 lots homogènes de marchandises entre trois marchés de manière à obtenir revenu maximum dès 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 |
Dans la méthode P, le plan optimal est obtenu en se déplaçant le long de pseudo-plans. Pseudoplan- un plan dans lequel les conditions d'optimalité sont satisfaites, et parmi les valeurs des variables de base x i il y a des nombres négatifs. Algorithme méthode double simplexe comprend les étapes suivantes :
- Élaborer un pseudo-plan. Le système de contraintes du problème initial conduit à un système d'inégalités de sens « ≤ ».
- Vérification de l'optimalité du plan. Si la condition d’optimalité n’est pas satisfaite dans le plan de référence résultant, alors le problème est résolu en utilisant la méthode du simplexe.
- Sélection de la première ligne et de la première colonne. Parmi les valeurs négatives des variables de base, les plus grandes en valeur absolue sont sélectionnées. La ligne correspondant à cette valeur est la ligne leader.
- Calcul d'un nouveau plan de référence. Nouveau plan est obtenu en recalculant la table simplexe à l'aide de la méthode Jordan-Gauss. Passez ensuite à l'étape 2.
Exemple. L'entreprise doit produire des unités A1, A2 et A3 conformément au plan de production. Chaque type de produit peut être fabriqué sur deux machines.
Comment répartir le travail des machines pour que le temps total consacré à l'exécution du plan soit minime ? La matrice des coûts et la ressource temps de chaque machine sont données. Notez le modèle de l'opération étudiée sous une forme permettant l'utilisation de la méthode P.
On sait que la teneur en n nutriments A, B et C dans l'alimentation doit être d'au moins des unités m1, m2, m3, respectivement. Trois types d'aliments contiennent ces nutriments. La teneur en unités nutritives dans un kilogramme de chaque type de produit est indiquée dans le tableau. déterminer le régime alimentaire quotidien qui fournit quantité requise nutriments à un coût minime.
Tâche : Résolvez le problème à l'aide de l'algorithme de la méthode dual simplex.
Réduisons le système de restrictions au système d'inégalités de sens ≤ en multipliant les droites correspondantes par (-1).
Déterminons la valeur minimale de la fonction objectif F(X) = 4x 1 + 2x 2 + x 3 sous les conditions de contrainte suivantes.
- x 1 - x 2 ≤-10
2x 1 + x 2 - x 3 ≤8
Pour construire le premier plan de référence, on réduit le système d'inégalités à un système d'équations en introduisant des variables supplémentaires (passage à la forme canonique).
Dans la première inégalité de sens (≤), nous introduisons la variable de base x 4 . Dans la deuxième inégalité de sens (≤), nous introduisons la variable de base x 5 .
-1x 1 -1x 2 + 0x 3 + 1x 4 + 0x 5 = -10
2x 1 + 1x 2 -1x 3 + 0x 4 + 1x 5 = 8
La matrice des coefficients A = a(ij) de ce système d'équations a la forme :
| UNE= |
|
x4, x5,
En supposant que les variables libres sont égales à zéro, on obtient le premier plan de référence :
X1 = (0,0,0,-10,8)
| Base | B | x1 | x2 | x3 | x4 | x5 |
| x4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
Itération #1
Le plan 0 dans un tableau simplexe est un pseudo-plan, nous déterminons donc la première ligne et la première colonne.
La ligne principale sera la première ligne et la variable x 4 doit être dérivée de la base.
3. Définition d'une nouvelle variable de base. Valeur minimumθ correspond à la 2ème colonne, soit la variable x 2 doit être saisie dans la base.
| Base | B | x1 | x2 | x3 | x4 | x5 |
| x4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
| θ | 0 | -4: (-1) = 4 | -2: (-1) = 2 | - | - | - |
4. Recalcul de la table simplexe. Nous effectuons des transformations de la table simplexe en utilisant la méthode Jordano-Gauss.
| Base | B | x1 | x2 | x3 | x4 | x5 |
| x2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
Présentons le calcul de chaque élément sous forme de tableau :
| B | x1 | x2 | x3 | x4 | x5 |
| -10: -1 | -1: -1 | -1: -1 | 0: -1 | 1: -1 | 0: -1 |
| 8-(-10 1):-1 | 2-(-1 1):-1 | 1-(-1 1):-1 | -1-(0 1):-1 | 0-(1 1):-1 | 1-(0 1):-1 |
| 0-(-10 -2):-1 | -4-(-1 -2):-1 | -2-(-1 -2):-1 | -1-(0 -2):-1 | 0-(1 -2):-1 | 0-(0 -2):-1 |
Itération #2
1. Vérification du critère d'optimalité.
Le plan 1 dans un tableau simplexe est un pseudo-plan, nous déterminons donc la première ligne et la première colonne.
2. Définition d'une nouvelle variable libre.
Parmi les valeurs négatives des variables de base, on sélectionne la plus grande en valeur absolue.
La deuxième ligne sera en tête et la variable x 5 doit être dérivée de la base.
3. Définition d'une nouvelle variable de base. La valeur minimale de θ correspond à la troisième colonne, c'est-à-dire la variable x 3 doit être saisie dans la base.
À l'intersection de la ligne et de la colonne principales se trouve un élément de résolution (RE) égal à (-1).
| Base | B | x1 | x2 | x3 | x4 | x5 |
| x2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
| θ | 0 | - | - | -1: (-1) = 1 | - | - |
4. Recalcul de la table simplexe. Nous effectuons des transformations.
| Base | B | x1 | x2 | x3 | x4 | x5 |
| x2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
| B | x1 | x2 | x3 | x4 | x5 |
| 10-(-2 0):-1 | 1-(1 0):-1 | 1-(0 0):-1 | 0-(-1 0):-1 | -1-(1 0):-1 | 0-(1 0):-1 |
| -2: -1 | 1: -1 | 0: -1 | -1: -1 | 1: -1 | 1: -1 |
| 20-(-2 -1):-1 | -2-(1 -1):-1 | 0-(0 -1):-1 | -1-(-1 -1):-1 | -2-(1 -1):-1 | 0-(1 -1):-1 |
Dans la colonne de base, tous les éléments sont positifs. Passons à l'algorithme principal de la méthode simplexe.
Itération #3
1. Vérification du critère d'optimalité.
Il n'y a aucune valeur positive parmi les valeurs de la chaîne d'index. Par conséquent, ce tableau détermine le plan optimal pour le problème.
| Base | B | x1 | x2 | x3 | x4 | x5 |
| x2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
Le plan optimal peut s'écrire comme suit : x 1 = 0, x 2 = 10, x 3 = 2
F(X) = 2 10 + 1 2 = 22
Le fil, les boutons et le tissu sont utilisés pour fabriquer trois types de chemises. Les stocks de fil, de boutons et de tissu, les normes de leur consommation pour coudre une chemise sont indiquées dans le tableau. Trouver le profit maximum et le plan de production de produits optimal qui le garantit (trouver).
| chemise 1 | chemise 2 | chemise 3 | Réserves | fils (m.) | 1 | 9 | 3 | 96 | boutons (pièces) | 20 | 10 | 30 | 640 | textile ( | 1 | 2 | 2 | 44 | Bénéfice (r.) | 2 | 5 | 4 |
La solution du problème
Construction de maquettes
À travers et le nombre de chemises des 1er, 2e et 3e types destinées à la sortie.
Ensuite, les restrictions de ressources ressembleront à ceci :
De plus, selon le sens de la tâche
Fonction objectif exprimant le bénéfice perçu :
Nous obtenons le problème de programmation linéaire suivant :
Réduire un problème de programmation linéaire à une forme canonique
Réduisons le problème à Forme canonique. Introduisons des variables supplémentaires. Nous introduisons toutes les variables supplémentaires dans la fonction objectif avec un coefficient égal à zéro. Nous ajoutons des variables supplémentaires aux côtés gauches des restrictions qui n'ont pas de forme préférée, et nous obtenons des égalités.
Résoudre le problème en utilisant la méthode du simplexe
Remplissez le tableau simplexe :
Puisque nous résolvons le problème au maximum, la présence de nombres négatifs dans la ligne d'index lors de la résolution du problème au maximum indique que nous n'avons pas obtenu la solution optimale et qu'il faut passer du tableau de la 0ème itération au suivant.
On passe à l'itération suivante comme suit :
la première colonne correspond
La ligne clé est déterminée par le rapport minimum de termes libres et de membres de la première colonne (relations simplex) :
A l'intersection de la colonne clé et de la ligne clé, nous trouvons l'élément d'activation, c'est-à-dire 9.
Passons maintenant à la compilation de la 1ère itération : Au lieu d'un vecteur unitaire, nous introduisons le vecteur .
DANS nouveau tableauà la place de l'élément d'activation, nous écrivons 1, tous les autres éléments de la colonne clé sont des zéros. Les éléments de chaîne clé sont divisés en éléments d'activation. Tous les autres éléments du tableau sont calculés à l'aide de la règle du rectangle.
La colonne clé de la 1ère itération correspond à
L'élément résolvant est le nombre 4/3. Nous dérivons le vecteur de la base et introduisons le vecteur à la place. On obtient le tableau de la 2ème itération.
La colonne clé de la 2ème itération correspond à
On retrouve la ligne clé, pour cela on définit :
L'élément résolvant est le nombre 10/3. Nous dérivons le vecteur de la base et introduisons le vecteur à la place. On obtient le tableau de la 3ème itération.
| № | PA | cB | Ao | x1 | x2 | x3 | x4 | x5 | x6 | Simplexe | 2 | 5 | 4 | 0 | 0 | 0 | relation | 0 | x4 | 0 | 96 | 1 | 9 | 3 | 1 | 0 | 0 | 32/3 | x5 | 0 | 640 | 20 | 10 | 30 | 0 | 1 | 0 | 64 | x6 | 0 | 44 | 1 | 2 | 2 | 0 | 0 | 1 | 22 | F j - c j | 0 | -2 | -5 | -4 | 0 | 0 | 0 | 1 | x2 | 5 | 32/3 | 1/9 | 1 | 1/3 | 1/9 | 0 | 0 | 32 | x5 | 0 | 1600/3 | 170/9 | 0 | 80/3 | -10/9 | 1 | 0 | 20 | x6 | 0 | 68/3 | 7/9 | 0 | 4/3 | -2/9 | 0 | 1 | 17 | F j - c j | 160/3 | -13/9 | 0 | -7/3 | 5/9 | 0 | 0 | 2 | x2 | 5 | 5 | -1/12 | 1 | 0 | 1/6 | 0 | -1/4 | -- | x5 | 0 | 80 | 10/3 | 0 | 0 | 10/3 | 1 | -20 | 24 | x3 | 4 | 17 | 7/12 | 0 | 1 | -1/6 | 0 | 3/4 | 204/7 | F j - c j | 93 | -1/12 | 0 | 0 | 1/6 | 0 | 7/4 | 3 | x2 | 5 | 7 | 0 | 1 | 0 | 1/4 | 1/40 | -3/4 | x1 | 2 | 24 | 1 | 0 | 0 | 1 | 3/10 | -6 | x3 | 4 | 3 | 0 | 0 | 1 | -3/4 | -7/40 | 17/4 | F j - c j | 95 | 0 | 0 | 0 | 1/4 | 1/40 | 5/4 |
Dans la ligne d'index, tous les termes sont non négatifs, donc la solution suivante au problème de programmation linéaire est obtenue (nous l'écrivons à partir de la colonne des termes libres) :
Il faut coudre 24 chemises du 1er type, 7 chemises du 2ème type et 3 chemises du 3ème type. Dans ce cas, le bénéfice perçu sera maximum et s'élèvera à 95 roubles.
Vous pouvez trouver de l'aide pour résoudre vos problèmes à ce sujet en envoyant un message sur VKontakte, Viber ou en remplissant le formulaire. Le coût de la résolution des devoirs commence à partir de 7 BYR. par tâche (200 roubles russes), mais pas moins de 10 roubles biélorusses. (300 RUB) pour la totalité de la commande. Conception détaillée. Le coût de l'assistance à l'examen en ligne (dans ce cas, un prépaiement de 100 % est requis) est de 30 BYR. (1000 roubles russes) pour résoudre le ticket.
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éterminez la solution optimale au problème d’origine.
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 à 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 |
Voici une solution manuelle (et non applet) de deux problèmes utilisant la méthode simplex (similaire à la solution applet) avec des explications détaillées afin de comprendre l'algorithme de résolution de problèmes utilisant la méthode simplex. Le premier problème ne contient que des signes d'inégalité « ≤ » (problème avec une base initiale), le second peut contenir des signes « ≥ », « ≤ » ou « = » (problème avec une base artificielle), ils sont résolus différemment.
Méthode simplex, résolution d'un problème avec une base initiale
1)Méthode simplexe pour un problème avec une base initiale (tous les signes de contraintes d'inégalité " ≤ ").
Écrivons le problème dans canonique forme, c'est-à-dire nous réécrivons les restrictions d'inégalité sous forme d'égalités, en ajoutant bilan variables :
Ce système est un système avec une base (base s 1, s 2, s 3, chacun d'eux n'est inclus que dans une seule équation du système à coefficient 1), x 1 et x 2 sont des variables libres. Les problèmes à résoudre par la méthode du simplexe doivent avoir les deux propriétés suivantes : - le système de contraintes doit être un système d'équations avec une base ; -les termes libres de toutes les équations du système doivent être non négatifs.
Le système résultant est un système avec une base et ses termes libres sont non négatifs, nous pouvons donc appliquer méthode simplexe. Créons la première table simplexe (itération 0) pour résoudre le problème sur méthode simplexe, c'est à dire. un tableau des coefficients de la fonction objectif et un système d'équations pour les variables correspondantes. Ici « BP » désigne la colonne des variables de base, « Solution » désigne la colonne des membres de droite des équations du système. La solution n'est pas optimale, car il y a des coefficients négatifs dans la ligne z.
itération de la méthode simplexe 0
|
Attitude |
|||||||
Pour améliorer la solution, passons à l'itération suivante méthode simplexe, nous obtenons le tableau simplex suivant. Pour ce faire, vous devez sélectionner activer la colonne, c'est à dire. une variable qui sera incluse dans la base à la prochaine itération de la méthode simplexe. Il est sélectionné par le plus grand coefficient négatif absolu de la ligne z (dans le problème du maximum) - dans l'itération initiale de la méthode simplex, il s'agit de la colonne x 2 (coefficient -6).
Sélectionnez ensuite activer la chaîne, c'est à dire. une variable qui quittera la base à la prochaine itération de la méthode simplexe. Il est sélectionné par le plus petit rapport de la colonne « Décision » aux éléments positifs correspondants de la colonne de résolution (colonne « Rapport ») - dans l'itération initiale, il s'agit de la ligne s 3 (coefficient 20).
Élément permissif est à l'intersection de la colonne de résolution et de la ligne de résolution, sa cellule est surlignée en couleur, elle est égale à 1. Ainsi, à la prochaine itération de la méthode simplexe, la variable x 2 remplacera s 1 dans la base. Notez que la relation n'est pas recherchée dans la z-string ; un tiret « - » y est placé. S'il existe des relations minimales identiques, alors l'une d'entre elles est sélectionnée. Si tous les coefficients de la colonne résolution sont inférieurs ou égaux à 0, alors la solution du problème est infinie.
Remplissons le tableau suivant « Itération 1 ». Nous l'obtiendrons à partir du tableau « Itération 0 ». Le but des transformations ultérieures est de transformer la colonne de résolution x2 en une colonne unitaire (avec un un à la place de l'élément de résolution et des zéros à la place des éléments restants).
1) Calculez la ligne x 2 du tableau « Itération 1 ». Tout d'abord, on divise tous les membres de la ligne résolvante s 3 du tableau « Itération 0 » par l'élément résolvant (il est égal à 1 dans ce cas) de ce tableau, on obtient la ligne x 2 dans le tableau « Itération 1 » . Parce que l'élément résolvant dans ce cas est égal à 1, alors la ligne s 3 du tableau « Itération 0 » coïncidera avec la ligne x 2 du tableau « Itération 1 ». Ligne x 2 du tableau Itération 1, nous avons obtenu 0 1 0 0 1 20, les lignes restantes du tableau Itération 1 seront obtenues à partir de cette ligne et des lignes du tableau Itération 0 comme suit :
2) Calcul de la ligne z du tableau « Itération 1 ». Au lieu de -6 dans la première ligne (ligne z) de la colonne x2 du tableau Itération 0, il devrait y avoir un 0 dans la première ligne du tableau Itération 1. Pour cela, multipliez tous les éléments de la ligne x 2 du tableau "Itération 1" 0 1 0 0 1 20 par 6, on obtient 0 6 0 0 6 120 et additionnez cette ligne avec la première ligne (z - ligne) du tableau "Itération 0" -4 -6 0 0 0 0, on obtient -4 0 0 0 6 120. Un zéro 0 apparaît dans la colonne x 2, le but est atteint. Les éléments de la colonne de résolution x 2 sont surlignés en rouge.
3) Calcul de la ligne s 1 du tableau « Itération 1 ». Au lieu de 1 sur s 1 ligne du tableau « Itération 0 », il devrait y avoir un 0 dans le tableau « Itération 1 ». Pour cela, multipliez tous les éléments de la ligne x 2 du tableau "Itération 1" 0 1 0 0 1 20 par -1, obtenez 0 -1 0 0 -1 -20 et ajoutez cette ligne avec s 1 - ligne du tableau "Itération 0" 2 1 1 0 0 64, nous obtenons la ligne 2 0 1 0 -1 44. Dans la colonne x 2, nous obtenons le 0 requis.
4) Calculez la ligne s 2 du tableau « Itération 1 ». A la place 3 dans la ligne s 2 du tableau "Itération 0", il devrait y avoir 0 dans le tableau "Itération 1". Pour cela, multipliez tous les éléments de la ligne x 2 du tableau "Itération 1" 0 1 0 0 1 20 par -3, on obtient 0 -3 0 0 -3 -60 et ajoutez cette ligne avec s 1 - ligne de le tableau "Itération 0" 1 3 0 1 0 72, on obtient la ligne 1 0 0 1 -3 12. Dans la colonne x 2, on obtient le 0 requis. La colonne x 2 du tableau "Itération 1" est devenue une unité, elle contient un 1 et le reste 0.
Les lignes du tableau « Itération 1 » sont obtenues selon la règle suivante :
Nouvelle ligne = Ancienne ligne – (Coefficient de colonne de résolution de l’ancienne ligne)* (Nouvelle ligne de résolution).
Par exemple, pour une z-string nous avons :
Ancienne chaîne z (-4 -6 0 0 0 0) -(-6)*Nouvelle chaîne de résolution -(0 -6 0 0 -6 -120) =Nouvelle chaîne z (-4 0 0 0 6 120).
Pour les tableaux suivants, le recalcul des éléments du tableau se fait de la même manière, nous l'omettons donc.
méthode simplexe itération 1
|
Attitude |
|||||||
En résolvant la colonne x 1, en résolvant la ligne s 2, s 2 quitte la base, x 1 entre dans la base. Exactement de la même manière, nous obtenons les tableaux simplex restants jusqu'à obtenir un tableau avec tous les coefficients positifs dans la ligne z. C'est le signe d'une table optimale.
méthode simplexe itération 2
|
Attitude |
|||||||
En résolvant la colonne s 3, en résolvant la ligne s 1, s 1 quitte la base, s 3 entre dans la base.
méthode simplexe itération 3
|
Attitude |
|||||||
Dans la ligne z, tous les coefficients sont non négatifs, donc la solution optimale x 1 = 24, x 2 = 16, z max = 192 est obtenue.
Cette méthode est une méthode d'énumération ciblée de solutions de référence à un problème de programmation linéaire. Elle permet, en un nombre fini d'étapes, soit de trouver une solution optimale, soit d'établir qu'il n'existe pas de solution optimale.
Le contenu principal de la méthode simplexe est le suivant :- Indiquer une méthode pour trouver la solution de référence optimale
- Indiquer la méthode de transition d'une solution de référence à une autre, à laquelle la valeur de la fonction objectif sera plus proche de la valeur optimale, c'est-à-dire indiquer un moyen d'améliorer la solution de référence
- Définissez des critères qui vous permettent d'arrêter rapidement de rechercher des solutions d'assistance à la solution optimale ou de tirer une conclusion sur l'absence de solution optimale.
Algorithme de la méthode simplexe pour résoudre des problèmes de programmation linéaire
Afin de résoudre un problème à l'aide de la méthode du simplexe, vous devez procéder comme suit :- Amener le problème sous forme canonique
- Trouver la solution de support initiale avec une « base unitaire » (s'il n'y a pas de solution de support, alors le problème n'a pas de solution en raison de l'incompatibilité du système de contraintes)
- Calculer les estimations des décompositions vectorielles à partir de la solution de référence et remplir le tableau de la méthode simplexe
- Si le critère d'unicité de la solution optimale est satisfait, alors la solution du problème se termine
- Si la condition d’existence d’un ensemble de solutions optimales est remplie, alors toutes les solutions optimales sont trouvées par simple énumération
Un exemple de résolution d'un problème en utilisant la méthode du simplexe
Exemple 26.1Résolvez le problème en utilisant la méthode du simplexe :
Solution:
Nous mettons le problème sous forme canonique.
Pour ce faire, nous introduisons une variable supplémentaire x 6 de coefficient +1 à gauche de la première contrainte d'inégalité. La variable x 6 est incluse dans la fonction objectif avec un coefficient nul (c'est-à-dire qu'elle n'est pas incluse).
On a:
Nous trouvons la solution d’accompagnement initiale. Pour ce faire, nous assimilons les variables libres (non résolues) à zéro x1 = x2 = x3 = 0.
On a Solution de référence X1 = (0,0,0,24,30,6) avec base unitaire B1 = (A4, A5, A6).
Nous calculons estimations des décompositions vectorielles conditions à partir de la solution de référence selon la formule :
Δ k = C b X k - c k
- C b = (c 1, c 2, ..., c m) - vecteur de coefficients de la fonction objectif pour les variables de base
- X k = (x 1k, x 2k, ..., x mk) - vecteur d'expansion du vecteur correspondant A k selon la base de la solution de référence
- C k est le coefficient de la fonction objectif pour la variable x k.
Les estimations des vecteurs inclus dans la base sont toujours égales à zéro. La solution de référence, les coefficients d'expansion et les estimations des expansions des vecteurs de condition basés sur la solution de référence sont écrits en tableau simplexe:
En haut du tableau, pour faciliter le calcul des estimations, sont inscrits les coefficients de la fonction objectif. Dans la première colonne "B" sont écrits les vecteurs inclus dans la base de la solution de référence. L'ordre dans lequel ces vecteurs sont écrits correspond au nombre d'inconnues autorisées dans les équations de contraintes. Dans la deuxième colonne du tableau « C b » les coefficients de la fonction objectif pour les variables de base sont écrits dans le même ordre. À emplacement correct Les coefficients de la fonction objectif dans la colonne « C b » de l'estimation des vecteurs unitaires inclus dans la base sont toujours égaux à zéro.
Dans la dernière ligne du tableau avec les estimations de Δ k dans la colonne « A 0 » sont écrites les valeurs de la fonction objectif sur la solution de référence Z(X 1).
La solution de support initiale n'est pas optimale, puisque dans le problème du maximum les estimations Δ 1 = -2, Δ 3 = -9 pour les vecteurs A 1 et A 3 sont négatives.
Selon le théorème d'amélioration de la solution support, si dans un problème maximum au moins un vecteur a une estimation négative, alors vous pouvez trouver une nouvelle solution support sur laquelle la valeur de la fonction objectif sera plus grande.
Déterminons lequel des deux vecteurs conduira à un incrément plus important dans la fonction objectif.
L'incrément de la fonction objectif se trouve par la formule : .
On calcule les valeurs du paramètre θ 01 pour les première et troisième colonnes à l'aide de la formule :
On obtient θ 01 = 6 pour l = 1, θ 03 = 3 pour l = 1 (tableau 26.1).
On retrouve l'incrément de la fonction objectif en introduisant dans la base le premier vecteur ΔZ 1 = - 6*(- 2) = 12, et le troisième vecteur ΔZ 3 = - 3*(- 9) = 27.
Par conséquent, pour une approche plus rapide de la solution optimale, il est nécessaire d'introduire le vecteur A3 dans la base de la solution de référence au lieu du premier vecteur de la base A6, puisque le minimum du paramètre θ 03 est atteint dans la première ligne ( l = 1).
On effectue la transformation de Jordan avec l'élément X13 = 2, on obtient la deuxième solution de référence X2 = (0,0,3,21,42,0) avec la base B2 = (A3, A4, A5). (Tableau 26.2)
Cette solution n'est pas optimale, puisque le vecteur A2 a une estimation négative Δ2 = - 6. Pour améliorer la solution, il faut introduire le vecteur A2 dans la base de la solution de référence.
Nous déterminons le numéro du vecteur dérivé de la base. Pour ce faire, on calcule le paramètre θ 02 pour la deuxième colonne, il est égal à 7 pour l = 2. Par conséquent, on dérive le deuxième vecteur de base A4 de la base. On effectue la transformation de Jordan avec l'élément x 22 = 3, on obtient la troisième solution de référence X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Tableau 26.3).
Cette solution est la seule optimale, puisque pour tous les vecteurs non inclus dans la base les estimations sont positives
Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.
Répondre: max Z(X) = 201 à X = (0,7,10,0,63).
Méthode de programmation linéaire en analyse économique
Méthode de programmation linéaire permet de justifier la solution économique la plus optimale dans des conditions de restrictions sévères liées aux ressources utilisées dans la production (immobilisations, matériaux, ressources en main d'œuvre). L'utilisation de cette méthode en analyse économique permet de résoudre des problèmes liés principalement à la planification des activités d'une organisation. Cette méthode permet de déterminer les niveaux de sortie optimaux, ainsi que les directions pour le plus utilisation efficace ressources de production dont dispose l’organisation.
Grâce à cette méthode, on résout les problèmes dits extrêmes, qui consistent à trouver des valeurs extrêmes, c'est-à-dire le maximum et le minimum des fonctions de quantités variables.
Cette période est basée sur la solution du système équations linéaires dans les cas où les phénomènes économiques analysés sont liés par une dépendance linéaire et strictement fonctionnelle. La méthode de programmation linéaire est utilisée pour analyser des variables en présence de certains facteurs limitants.
Il est très courant de résoudre le problème dit de transport en utilisant la méthode de programmation linéaire. Le contenu de cette tâche est de minimiser les coûts encourus dans le cadre de l'opération Véhicule dans le cadre des restrictions existantes concernant le nombre de véhicules, leur capacité de transport, la durée de leur exploitation et s'il existe un besoin d'entretien quantité maximale clients.
En plus, cette méthode est largement utilisé pour résoudre les problèmes de planification. Cette tâche consiste en une telle répartition du temps de fonctionnement pour le personnel d'une organisation donnée qui serait la plus acceptable tant pour les membres de ce personnel que pour les clients de l'organisation.
Cette tâche consiste à maximiser le nombre de clients servis dans des conditions de limitation du nombre de membres du personnel disponibles, ainsi que du fonds de temps de travail.
Ainsi, la méthode de programmation linéaire est assez courante dans l’analyse de placement et d’utilisation. divers types ressources, ainsi que dans le processus de planification et de prévision des activités des organisations.
Néanmoins, la programmation mathématique peut également être appliquée aux phénomènes économiques dont la relation n’est pas linéaire. A cet effet, des méthodes de programmation non linéaires, dynamiques et convexes peuvent être utilisées.
La programmation non linéaire repose sur la nature non linéaire de la fonction objectif ou des contraintes, ou des deux. Les formes de la fonction objectif et des contraintes d'inégalité dans ces conditions peuvent être différentes.
La programmation non linéaire est utilisée en analyse économique, notamment pour établir la relation entre des indicateurs exprimant l'efficacité des activités d'une organisation et le volume de cette activité, la structure des coûts de production, les conditions du marché, etc.
La programmation dynamique repose sur la construction d'un arbre de décision. Chaque niveau de cet arbre sert d'étape pour déterminer les conséquences décision précédente et d'éliminer les options inefficaces pour cette solution. Ainsi, programmation dynamique a une nature en plusieurs étapes et en plusieurs étapes. Ce type de programmation est utilisé en analyse économique pour trouver options optimales développement de l'organisation, aujourd'hui et à l'avenir.
La programmation convexe est un type de programmation non linéaire. Ce type de programmation exprime le caractère non linéaire de la relation entre les résultats des activités d’une organisation et ses coûts. La programmation convexe (alias concave) analyse le convexe fonctions objectives et systèmes convexes de restrictions (points valeurs acceptables). La programmation convexe est utilisée dans l'analyse des activités économiques dans le but de minimiser les coûts, et la programmation concave dans le but de maximiser les revenus dans le cadre des restrictions existantes sur l'action des facteurs qui influencent les indicateurs analysés de manière opposée. Par conséquent, avec les types de programmation considérés, les fonctions objectives convexes sont minimisées et les fonctions objectives concaves sont maximisées.