Programmation linéaire, éléments de planification de réseaux et théorie des jeux. Algorithme pour la méthode graphique de résolution du ZLP

26.02.2019

Problème canonique programmation linéaire V forme vectorielle a la forme :

Les coordonnées positives des solutions admissibles sont associées à des vecteurs de conditions. Ces systèmes de vecteurs sont dépendants, puisque le nombre de vecteurs qu'ils contiennent est supérieur à la dimension des vecteurs.

Solution de base du système est appelé un quotient dans lequel les variables non primaires ont des valeurs nulles. Tout système d'équations a un nombre fini de solutions de base égal à , où est le nombre d'inconnues et est le rang du système de vecteurs de condition. Les coordonnées de base dont les coordonnées satisfont à la condition de non-négativité sont référence.

La solution de référence un problème de programmation linéaire est dit admissible pour lequel les vecteurs de conditions correspondant aux coordonnées positives , sont linéairement indépendants.

Le nombre de coordonnées non nulles de la référence ne peut pas dépasser le rang du système de vecteurs de condition (c'est-à-dire le nombre d'équations linéairement indépendantes du système de contraintes).

Si le nombre de coordonnées non nulles solution de référence est égal à , alors cette solution est appelée Non dégénéré , sinon, si le nombre de coordonnées non nulles de la solution de référence est inférieur à , une telle solution est appelée Dégénérer .

La base de la solution de référence est la base d'un système de vecteurs de conditions du problème, qui comprend des vecteurs correspondant à des coordonnées non nulles de la solution de référence.

Théorème . Toute solution de support est un point central de la région des solutions réalisables .

Théorème . Tout coin de la région des solutions réalisables est une solution de référence .

Exemple.

Considérons une méthode graphique pour résoudre un problème d'optimisation linéaire en utilisant l'exemple d'un problème de planification de production à
= 2.

L'entreprise fabrique des produits de deux types A et B. Pour la fabrication de produits, elle dispose de matières premières de trois types C, D et E en volumes de 600, 480 et 240 unités, respectivement. Les taux de consommation de ressources par unité de production de chaque type sont connus et sont présentés dans le tableau. 14.1

Solution:

Le bénéfice de la vente du produit A est de 40 millions de roubles et celui du produit B de 50 millions de roubles. Il est nécessaire de trouver les volumes de production des produits A et B qui assurent un profit maximum.

Construisons modèle mathématique tâches, pour lesquelles nous désignons et - les volumes de production des produits A et B, respectivement.

Le bénéfice de l’entreprise sur la vente des produits A et des produits B sera alors :

Les restrictions de ressources ressembleront à :

Bien entendu, les volumes de production doivent être non négatifs .

Nous trouverons la solution au problème formulé en utilisant une interprétation géométrique. Définissons d'abord un polygone de solutions, pour lequel nous écrivons le système de contraintes d'inégalité sous forme d'équations et les numérotons :

Chacune des équations écrites représente une ligne droite sur un plan, les 4ème et 5ème lignes droites étant les axes de coordonnées.

Pour construire la première droite, on retrouve les points de son intersection avec les axes de coordonnées : à , et quand . Ensuite, nous nous intéressons à quel côté de la droite sera situé le demi-plan correspondant à la première inégalité. Pour déterminer le demi-plan souhaité, on prend un point et, en substituant ses coordonnées dans l'inégalité, on voit qu'il est satisfait. Puisque le point se trouve à gauche de la première ligne, le demi-plan sera également à gauche de la ligne . Sur la fig. 14.1 l'emplacement du demi-plan par rapport à la première droite est marqué par des flèches.

Les 2ème et 3ème lignes ont été construites de la même manière et les demi-plans correspondant aux 2ème et 3ème inégalités ont été trouvés. Points satisfaisant des contraintes , sont dans le premier quadrant.

L’ensemble des points qui satisfont simultanément toutes les contraintes est l’ODD du système de contraintes. Une telle zone sur le graphique (Fig. 14.1) est un polygone.

Tout point du polygone de solution satisfait le système de contraintes du problème et constitue donc sa solution. Cela suggère que ce problème d’optimisation linéaire a de nombreuses solutions réalisables, c’est-à-dire qu’il est multivarié. Nous devons trouver une solution qui génère un profit maximum.

Pour trouver ce point, nous assimilons la fonction à zéro et construisons une droite qui lui correspond. Vecteur gradient d'une fonction directe a des coordonnées .

Riz. 14.1

Représentons le vecteur sur le graphique et construisons une ligne droite de la fonction perpendiculaire au vecteur de la Fig. 14.1. En déplaçant la droite de la fonction parallèlement à elle-même dans la direction du vecteur, on voit que dernier point du polygone de solution que coupe la droite de la fonction est le point d'angle B. Par conséquent, au point B, la fonction atteint sa valeur maximale. On trouve les coordonnées du point B en résolvant un système d'équations dont les lignes se coupent en un point donné.

Après avoir résolu ce système, nous constatons que .

Par conséquent, si l'entreprise fabrique des produits dans les volumes trouvés, elle percevra un bénéfice maximum égal à :

(millions de roubles).

L'algorithme de résolution d'un problème de programmation linéaire par la méthode graphique est le suivant :

1. La région des solutions réalisables est construite ;

2. Un vecteur normal à la ligne de niveau est construit avec le point d'application à l'origine ;

3. L'une des lignes de niveau passant par l'origine des coordonnées est tracée perpendiculairement au vecteur normal ;

4. La ligne de niveau se déplace vers la position de la ligne droite de référence. Le maximum ou le minimum de la fonction sera situé sur cette ligne.

En fonction du type de domaine de solution réalisable et fonction objectif la tâche peut avoir la seule solution, un nombre infini de solutions ou n'en avoir aucune solution optimale.

Sur la fig. La figure 14.3 montre le cas où la droite de la fonction est parallèle au segment AB appartenant à l'ODR. Le maximum de la fonction est atteint au point A et au point B, et, par conséquent, en tout point du segment AB, puisque ces points peuvent être exprimés comme une combinaison linéaire des points d'angle A et B.

Concepts de base méthode simplexe résoudre un problème de programmation linéaire.

Parmi méthodes universelles En résolvant la programmation linéaire, la plus courante est la méthode simplex (ou méthode simplex), développée par le scientifique américain J. Dantzig. L'essence de cette méthode est que l'on obtient d'abord une option réalisable qui satisfait à toutes les restrictions, mais qui n'est pas nécessairement optimale (la soi-disant solution de référence initiale) ; l'optimalité est obtenue en améliorant successivement la version originale sur un certain nombre d'étapes (itérations). La recherche de la solution de référence initiale et le passage à la solution de référence suivante sont effectués sur la base de l'application de la méthode Jordan-Gauss discutée ci-dessus pour le système. équations linéaires sous forme canonique, dans laquelle le problème de programmation linéaire original doit être préalablement écrit ; le sens de transition d'une solution de référence à une autre est choisi en fonction du critère d'optimalité (fonction objectif) du problème d'origine.

Méthode simplexe est basé sur les propriétés suivantes du problème de programmation linéaire :

· N'existe pas extrême local, différent du mondial. Autrement dit, s’il y a un extremum, alors c’est le seul.

· L'ensemble de tous les plans d'un problème de programmation linéaire est convexe.

· La fonction objectif ZLP atteint sa valeur maximale (minimale) au coin du polyèdre solution (à son sommet). Si la fonction objectif prend sa valeur optimale en plusieurs points d'angle, alors elle atteint la même valeur en tout point convexe. combinaison linéaire ces points.

· Chaque point d'angle du polyèdre solution correspond au plan support de la ZLP.

Considérons deux variétés de la méthode simplex : la méthode simplex à base naturelle et la méthode simplex à base artificielle (ou méthode M).

Méthode simplex avec base naturelle

Pour appliquer cette méthode, le problème de programmation linéaire doit être formulé sous forme canonique, et la matrice du système d'équations doit contenir une sous-matrice unitaire de dimension. Dans ce cas, le plan de référence initial (solution de base non négative) est évident.

Pour être précis, supposons que le premier T Les vecteurs matriciels du système sont matrice d'identité. Alors le plan de référence initial s’impose : .

L'optimalité du plan de référence est vérifiée à l'aide du critère d'optimalité, en passant à un autre plan de référence— en utilisant les transformations de Jordan-Gauss et en utilisant le critère d'optimalité.

Le plan de référence résultant est à nouveau vérifié pour son optimalité, etc. Le processus se termine par un nombre fini d'étapes, et à la dernière étape, soit l'insolvabilité du problème est révélée (il n'y a pas d'optimum final), soit le plan de référence optimal et le la valeur optimale correspondante de la fonction objectif est obtenue.

Le signe d’optimalité réside dans les deux théorèmes suivants.

Théorème 1.Si pour un vecteur non inclus dans la base la condition suivante est satisfaite :

, Où ,

Vous pourrez alors obtenir un nouveau plan de référence, pour lequel la valeur de la fonction objectif sera supérieure à celle d'origine ; il peut y avoir deux cas :

1. Si toutes les coordonnées du vecteur à entrer dans la base sont non positives, alors le problème de programmation linéaire n'a pas de solution ;

2. S'il existe au moins une coordonnée positive pour le vecteur à introduire dans la base, alors un nouveau plan de référence peut être obtenu.

Théorème 2.Si la condition est satisfaite pour tous les vecteurs , alors le plan résultant est optimal.

Sur la base du critère d'optimalité, le vecteur qui donne la valeur négative minimale de la différence simplexe est introduit dans la base : .

Pour que la condition de non-négativité des valeurs du plan de référence soit satisfaite, le vecteur est dérivé de la base G, Ce qui donne la relation positive minimale :

; , .

Doubler Appelé guide , Colonne et élément
— Guides (ce dernier est aussi appelé Permissif élément).

Les éléments de la chaîne d'entrée correspondant à la chaîne guide dans la nouvelle table simplex sont calculés à l'aide des formules :

Et tout autre élément ème Les lignes sont recalculées à l'aide des formules :

Les valeurs des variables de base du nouveau plan de référence (indicateurs dans la colonne « plan ») sont calculées à l'aide des formules :

Pour ; , Pour .

Si plus petite valeur est obtenu pour plusieurs vecteurs de base, alors pour éliminer la possibilité de cyclage (répétition de base), la méthode suivante peut être appliquée.

Les quotients obtenus en divisant tous les éléments de ligne ayant donné la même valeur minimale par leurs éléments guides sont calculés. Les quotients résultants sont comparés dans les colonnes de gauche à droite, en tenant compte des valeurs nulles et négatives. Au cours du processus d'analyse, les lignes dans lesquelles il existe des ratios élevés sont ignorées et un vecteur correspondant à la ligne dans laquelle le plus petit quotient est trouvé en premier est dérivé de la base.

Pour utiliser la procédure ci-dessus de la méthode simplexe pour minimiser une forme linéaire, vous devez rechercher le maximum de la fonction , puis prenez le maximum résultant avec le signe opposé. Ce sera le minimum requis du problème de programmation linéaire original.

Méthode simplex avec base artificielle (méthode M)

La méthode du simplexe à base artificielle est utilisée dans les cas où il est difficile de retrouver le plan de référence initial du problème de programmation linéaire original écrit sous forme canonique.

M.-méthode consiste à appliquer les règles de la méthode du simplexe à ce qu'on appelle Tâche M. Il est obtenu à partir de l'original en ajoutant au côté gauche du système d'équations sous la forme canonique du problème de programmation linéaire original de tels vecteurs unitaires artificiels avec des variables artificielles non négatives correspondantes de sorte que la matrice nouvellement obtenue contienne un système d'unités. vecteurs linéairement indépendants. DANS forme linéaire Si le problème initial est maximisé, un terme est ajouté, qui est le produit du nombre ( -M ) par la somme de variables artificielles, où M. - un nombre positif assez important.

Dans le problème qui en résulte, le plan de référence original est évident. Lorsqu’on applique la méthode du simplexe à ce problème, les estimations dépendront désormais du nombre M. . Pour comparer les estimations, vous devez vous rappeler que M. est un nombre positif assez grand, donc les variables artificielles seront d'abord dérivées de la base.

En train de résoudre M- Les problèmes doivent être barrés dans les vecteurs artificiels du tableau simplex lorsqu'ils quittent la base. Si tous les vecteurs artificiels quittent la base, alors nous obtenons le problème initial. Si la solution optimale M- Les problèmes contiennent des vecteurs artificiels ou M- Le problème est insoluble, alors le problème initial est également insoluble.

Grâce aux transformations, le nombre de variables d'entrée qui composent base artificielle, peut être réduit à un.

Pour appliquer la méthode du simplexe avec une base naturelle, le KZLP doit contenir une sous-matrice unitaire de taille mxm - dans ce cas, le plan de support initial (une solution de base non négative du système de contraintes KZLP) est évident.
Pour être précis, nous supposons que les m premiers vecteurs de la matrice du système d'équations constituent la matrice identité. Alors le plan de référence initial est évident - (b 1, b 2,..., b m,0,...,0).
L'optimalité du plan de référence est vérifiée à l'aide du critère d'optimalité ; le passage à un autre plan de référence s'effectue à l'aide des transformations de Jordan-Gauss utilisant le critère d'optimalité mathématique. L'optimalité du plan de référence résultant est à nouveau vérifiée, et ainsi de suite. Le processus se termine par un nombre fini d'étapes, et à la dernière étape soit l'insolvabilité du problème est révélée (il n'y a pas d'optimum final), soit un plan de référence optimal et la valeur optimale correspondante du CF sont obtenus.
Le critère mathématique d’optimalité se compose des deux théorèmes suivants :
1. Si pour tous les vecteurs A 1, A 2,…, A n la condition est satisfaite
Où ,
alors le plan de référence résultant est optimal.
2. Si pour un vecteur non inclus dans la base la condition est satisfaite , vous pourrez alors obtenir un nouveau plan de référence dont la valeur CF sera supérieure à celle d'origine, et il peut y avoir deux cas :
- si toutes les composantes du vecteur à entrer dans la base sont non positives, alors le LLP n'a pas de solution (il n'y a pas d'optimum final) ;
- s'il y a au moins une composante positive du vecteur à introduire dans la base, alors un nouveau plan de référence peut être obtenu.
Sur la base du critère d'optimalité, le vecteur A k est introduit dans la base, ce qui donne la valeur négative minimale de la différence simplexe :
Pour que la condition de non-négativité des valeurs du plan de référence soit satisfaite, on dérive du vecteur A r la base, qui donne le rapport d'évaluation positif minimum

La ligne A r est appelée un guide, la colonne A k et l'élément a r k sont appelés des guides.
Les éléments de la ligne directrice dans le nouveau tableau simplexe sont calculés à l'aide des formules :
UN i-ème éléments lignes - selon les formules :
Les valeurs du nouveau plan de référence sont calculées à l'aide des formules :
pour je = r ;
Le processus de décision se poursuit soit jusqu'à ce qu'un plan optimal soit obtenu, soit jusqu'à ce que le TF soit établi comme illimité. Si parmi les différences simplexes (estimations) du plan optimal, seules les estimations correspondant aux vecteurs de base sont nulles, alors cela indique le caractère unique du plan optimal. Si une estimation nulle correspond à un vecteur non inclus, alors cas général cela veut dire que plan optimal pas le seul.
Note. Pour utiliser la procédure donnée pour minimiser fonction linéaire f (x 1 ,x 2 ,…, x n) vous devez rechercher le maximum - f (x 1 ,x 2 ,…, x n), puis prendre le maximum résultant avec le signe opposé. La solution optimale est la même.
Exemple. Obtenez une solution basée sur le modèle :
Ce problème (modèle) de programmation linéaire, réduisons-le à forme canonique en introduisant des variables supplémentaires x3 et x4 :
Le KZLP a le nombre requis de colonnes simples, c'est-à-dire a un plan de référence initial évident (0,0,300,150). La solution est réalisée selon la méthode simplexe avec une base naturelle et les calculs sont présentés dans des tableaux simplexes :

j. Valeurs optimales les variables sont égales : x1*=75, x2* =75 (variables principales), x3* =0, x4* =0 (variables supplémentaires). Valeur maximale la fonction objectif est 375.
Ainsi, dans le problème évoqué ci-dessus utilisation optimale ressources limitées, optimales programme de fabrication consiste en une version de 75 unités. produits du premier type et 75 unités. produits du deuxième type. Ce programme est associé au revenu maximum de la vente de produits finis – 375 USD.

Nombre			DANS	2	3	0	0
simplex-	Base		plan					Q
tableaux
	A3	0	300	1	3	1	0	100
0	A4	0	150	1	1	0	1	150
		*f(x)*	0	-2	-3	0	0
	A2	3	100	1/3	1	1/3	0	300
je	A4	0	50	2/3

L'un des plus courants et des plus populaires problèmes d'optimisation en logistique – problème de transport . DANS look classique il s'agit de trouver l'optimal ( ceux. associé à coûts minimes ) plan de transport de marchandises.

Par exemple, nous avons une chaîne de magasins de détail qui exige un certain montant marchandises. Il existe également un certain nombre d'entrepôts de fournisseurs où sont stockées les marchandises requises. De plus, chaque entrepôt dispose d’un stock différent de ces marchandises. De plus, nous connaissons les tarifs - les coûts de transport d'1 produit de chaque entrepôt à chaque magasin.

Il est nécessaire d'élaborer un plan de transport afin que les magasins reçoivent la quantité requise de marchandises avec au moindre coût pour le transport. C’est précisément dans de tels cas (et dans bien d’autres) que le problème des transports doit être résolu.

Matériel théorique sur le problème des transports

(Problème Monge-Kantorovitch) - problème de mathématiques programmation linéaire type spécialà propos de la recherche répartition optimale objets homogènes de la batterie aux récepteurs tout en minimisant les frais de déplacement.

Pour faciliter la compréhension, il est considéré comme un problème sur le plan optimal de transport des marchandises depuis les points de départ ( par exemple, les entrepôts) aux points de consommation ( par exemple, les magasins), avec des coûts de transport totaux minimes.

A la forme suivante :

Où: Z- les frais de transport des marchandises ;
X- le volume de chargement ;
C- coût (tarif) de transport d'une unité de fret ;
UN- stock fournisseur ;
B- demande du consommateur ;
m- nombre de fournisseurs ;
n- nombre de consommateurs.

Plan général pour résoudre un problème de transport par la méthode du potentiel

Le problème des transports peut être résolu diverses méthodes, en partant de la méthode simplexe et recherche simple, et en terminant par la méthode. L’une des méthodes les plus utilisées et les plus adaptées dans la plupart des cas est l’amélioration itérative du plan de transport.

Son essence est la suivante : nous trouvons un certain plan de référence et le vérifions pour optimalité (Z → min). Si le plan est optimal, une solution a été trouvée. Dans le cas contraire, il améliore le plan autant de fois que nécessaire jusqu'à ce que le plan optimal soit trouvé.

Ci-dessous se trouve algorithme pour résoudre un problème de transport sous la forme la plus générale :

Construire une table de transport.
Vérification du problème pour la fermeture.
Élaboration d'un plan de base.
Vérification du plan de prise en charge pour dégénérescence.
Calcul des potentiels pour le plan de transport.
Vérification de l'optimalité du plan de référence.
Redistribution des fournitures.
Si la solution optimale est trouvée, passez à l’étape 9, sinon passez à l’étape 5.
Calcul des coûts totaux de transport de marchandises.
Construction d'un graphe de transport.

Instructions détaillées pour résoudre un problème de transport

1. Construire une table de transport

Nous construisons un tableau où nous indiquons les stocks de matériaux disponibles dans les entrepôts des fournisseurs ( Aï), et les besoins des usines ( Bj) dans ces matériaux.

Dans le coin inférieur droit des cellules du tableau, nous saisissons la valeur des tarifs pour le transport de marchandises ( Cij).

2. Vérification du problème pour la fermeture

Désignons le stock total de marchandises de tous les fournisseurs par le symbole UN, et la demande totale de fret pour tous les consommateurs est symbolisée B.

Le problème des transports s'appelle fermé, Si A = B. Si UNE≠B, alors le problème du transport s'appelle ouvrir. Au cas où problème clos Toutes les fournitures de fret seront retirées des fournisseurs et toutes les demandes des consommateurs seront satisfaites. Au cas où tâche ouverte Pour résoudre ce problème, vous devrez introduire des fournisseurs ou des consommateurs fictifs.

Vérifions la tâche pour la fermeture :

A = 10 + 20 + 30 = 60

B = 15 + 20 + 25 = 60

A = B, donc ce problème de transport est clos.

3. Etablir un plan de référence

Compose préliminaire ( justificatif) plan de transport. Il n’est pas nécessaire que ce soit optimal. Il ne s'agit que d'une sorte de « brouillon », de « croquis », en améliorant lequel nous arriverons progressivement au plan optimal.

Il y a différents méthodes pour trouver un plan de référence. Les plus courants sont les suivants :

a) Méthode de l'angle nord-ouest. Montrer

L'essence de la méthode est simple : les cellules de la table de transport sont remplies séquentiellement au maximum volumes possibles transport, dans le sens de haut en bas Et de gauche à droite. Autrement dit, la cellule en haut à gauche est remplie en premier ( cellule "nord-ouest"), puis le suivant à droite, etc. Ensuite, ils passent à une nouvelle ligne et la remplissent à nouveau de gauche à droite. Et ainsi de suite jusqu'à ce que la table soit complètement remplie.

Une description détaillée de la méthode et un exemple peuvent être trouvés.

b) Méthode des éléments minimaux. Montrer

La méthode est que pour remplir les cellules de la table de transport, sélectionnez une cellule avec minimal valeur tarifaire. Ensuite, la cellule suivante avec le tarif le plus bas est sélectionnée et ainsi de suite jusqu'à ce que le tableau soit rempli ( tous les stocks et besoins seront remis à zéro).

c) Rapprochement de Vogel. Montrer

La base de la méthode est de trouver différences(modulo) entre une paire de tarifs minimaux dans chaque ligne et colonne. Puis dans la ligne ou la colonne avec le plus grand la différence remplit la cellule le plus petit tarif. Ensuite, toutes ces actions sont répétées à nouveau, seulement dans ce cas les cellules remplies ne sont plus prises en compte.
Une description détaillée de l'approximation de Vogel et un exemple peuvent être trouvés

d) Méthode de double préférence. Montrer

L'essence de la méthode est que les cellules avec le tarif le plus bas sont marquées en lignes puis en colonnes. Ensuite, les cellules sont remplies dans l'ordre suivant : d'abord les cellules avec deux marques, puis avec un, enfin sans marques.
Une description détaillée de la méthode et un exemple peuvent être trouvés

4. Vérification du plan de prise en charge de la dégénérescence

Les cellules du tableau dans lesquelles sont enregistrés les transports différents de zéro sont appelées basique, et le reste (vide) - gratuit.

Le plan s'appelle dégénérer, si le nombre de cellules de base qu'il contient est inférieur à m + n -1. Si lors de la résolution du problème un plan dégénéré est obtenu, alors il doit être reconstitué en insérant un transport nul dans le nombre de cellules manquantes et en transformant ainsi ces cellules en cellules de base ( le solde global et le coût total de transport du plan ne changeront pas). Cependant, il est impossible de reconstituer le plan en choisissant des cellules au hasard. Le plan doit être acyclique !

Un plan est dit acyclique si ses cellules de base ne contiennent pas de cycles. Faire du vélo dans la table de transport il y a plusieurs cellules reliées par une polyligne fermée de sorte que deux sommets adjacents de la polyligne soient situés soit dans la même ligne, soit dans la même colonne. Ci-dessous se trouve exemple de boucle:

Une ligne brisée peut avoir des points d'auto-intersection, mais pas dans les cellules du cycle.

Nombre de cellules de base = 5

m + n – 1 = 3 + 3 – 1 = 5

Par conséquent, le plan de transport initial n’est pas dégénéré.

5. Calcul des potentiels pour le plan de transport

Pour analyser les plans résultants et leur amélioration ultérieure, il convient de saisir caractéristiques supplémentaires points d’origine et de destination, appelés potentiels.

Cette méthode d'amélioration des plans de transport s'appelle méthode potentielle . Il existe d’autres méthodes pour améliorer de manière itérative le plan de transport, mais nous ne les considérerons pas ici.

Comparons donc chaque fournisseur Ai et chaque consommateur Bj avec les valeurs Interface utilisateur Et Vj en conséquence, de sorte que pour toutes les cellules de base du plan, la relation suivante soit satisfaite :

Ui + Vj = Cij

Ajouter au tableau des transports ligne supplémentaire et une colonne pour Ui et Vj.

Supposons que U1 = 0.

On peut alors trouver V3 = C13 – U1 = 1 – 0 = 1.

Connaissant la V3, on peut désormais retrouver U3 :

Par analogie, on calcule tous les potentiels restants :

6. Vérification de l'optimalité du plan à l'aide de la méthode du potentiel

Pour chaque cellule libre du plan, on calcule les différences

ΔCij = Cij – (Ui + Vj)

et écrivez les valeurs résultantes dans les coins inférieurs gauches des cellules correspondantes.

Le plan est optimal, si toutes les différences ΔCij ≥ 0.

DANS dans ce cas plan - sous-optimal(ΔC22< 0), и его следует улучшить путем перераспределения поставок.

7. Redistribution des fournitures

Trouvons la cellule avec le plus grand valeur absolue différence négative ΔCij et construire un cycle dans lequel, à l'exception de cette cellule, toutes les autres sont basiques. Un tel cycle existe toujours et est unique.

Marquons la cellule avec une différence négative ΔCij avec un signe « + », la suivante avec un signe « - », et ainsi de suite, une par une.

Ensuite, nous trouvons la valeur minimale de la charge dans les cellules du cycle avec le signe « - » (ici c'est 5) et la saisissons dans la cellule libre avec le signe « + ». Ensuite, nous parcourons séquentiellement toutes les cellules du cycle, en leur soustrayant et en leur ajoutant alternativement la valeur minimale (conformément aux signes avec lesquels ces cellules sont marquées : où le moins est soustrait, où le plus est ajouté).

Nous obtenons nouveau plan de référence transport:

Puisqu’il y a plus de cellules de base que m + n – 1, nous rendons libre la cellule de base de valeur nulle :

On calcule à nouveau les valeurs potentielles et la différence ΔCij :

Cette fois toutes les différences ΔCij des cellules sont positives, donc, solution optimale trouvée.

8. Si la solution optimale est trouvée, passez à l’étape 9, sinon passez à l’étape 5.

Nous avons trouvé la solution optimale, alors passons au point 9.

9. Calcul des coûts totaux de transport de marchandises

Calculons frais de port totaux cargaison ( Z), correspondant au plan optimal que nous avons trouvé, selon la formule :

Zmin = 10 ∙ 1 + 15 ∙ 3 + 5 ∙ 2 + 15 ∙ 1 + 15 ∙ 2 = 110 deniers. unités

Le coût total de livraison de tous les produits, pour une solution optimale, est de 110 tanière. unités

10. Construction d'un graphe de transport

Après avoir trouvé le plan de transport optimal, nous le construirons. Les sommets du graphique seront « entrepôts » et « magasins ». Aux sommets nous indiquons les volumes correspondants de réserves et de besoins. Les arcs reliant les sommets du graphe correspondront à des transports non nuls. Nous signerons chacun de ces arcs, indiquant le volume de fret transporté.

Le résultat sera un graphique similaire à celui présenté ci-dessous :

Ça y est, le problème des transports est résolu. Félicitations!

Application pratique du problème des transports

Le problème du transport est utilisé dans de nombreux cas. Il s’agit de l’optimisation de l’approvisionnement en matières premières et fournitures pour entreprises manufacturières. Il s'agit de l'optimisation de la livraison des marchandises des entrepôts vers magasins de détail. C'est de l'optimisation transport de passagers, et bien plus encore.

Galyautdinov R.R.

Vue tabulaire du PPP. Simplex - tableaux.

MÉTHODE SIMPLEX POUR RÉSOUDRE ZLP

3.1. Caractéristiques générales et les principales étapes de la méthode simplexe

Les fondateurs de la méthode du simplexe sont le mathématicien soviétique L.V. Kantorovitch et le mathématicien américain J. Dantzig.

En utilisant la méthode du simplexe, vous pouvez résoudre n'importe quel problème ou découvrir son insolvabilité. De nombreuses classes particulières de problèmes peuvent être résolues par d’autres méthodes plus efficaces pour ces classes. Cependant, l’avantage de la méthode simplexe est sa polyvalence. Presque tous les ordinateurs ont été développés programmes standards résoudre ZLP simplexe- méthode.

Décrivons l'idée générale de la méthode du simplexe.

Nous pensons que le ZLP est écrit sous forme canonique et que la fonction objectif doit être minimisée. Comme nous le savons déjà, le plan optimal doit être recherché parmi les plans de base du ZLP. La méthode simplexe ne passe pas par tous les plans de référence (ce qui serait souvent impossible en raison de leur quantité énorme), et, à partir d'un plan de référence initial, il passe séquentiellement à d'autres plans de référence avec une diminution de la fonction objectif. La méthode simplex cesse de fonctionner lorsque le plan de référence optimal est trouvé ou que l'insolvabilité du problème est établie.

Lors de la résolution d'un problème à l'aide de la méthode du simplexe, les étapes suivantes peuvent être distinguées :

1) amener le ZLP à une forme canonique ;

2) réduire le système d'équations linéaires à la forme de Jordan avec des membres droits non négatifs tout en vérifiant simultanément l'insolvabilité du LLP en raison de l'incohérence du système de contraintes linéaires ;

3) étude du plan de référence pour l'optimalité ;

4) étude du ZLP pour l'indécidabilité due au caractère illimité d'en bas sur l'ODD de la fonction objectif ;

5) transition vers un nouveau et « meilleur » plan de référence.

Pour réduire et organiser les enregistrements lors de la résolution d'un problème à l'aide de la méthode simplex, des tables dites simplex sont utilisées. Pour utiliser un tableau simplex, le ZLP doit être réduit sous forme tabulaire. C'est fait comme ça.

Laissez le ZLP être écrit sous forme canonique (2.3-2.5). Pour réduire le ZLP sous forme tabulaire, le système (2.4) doit d’abord être réduit à la forme Jordan avec des membres droits non négatifs. Supposons que cette forme de Jordan ait la forme (2.6). Exprimons à partir de (2.6) les variables de base en termes de variables libres :

En substituant dans la fonction objectif (2.3) aux variables de base leurs expressions par des variables libres selon les formules (3.1), on exclut ainsi les variables de base de la fonction objectif. La fonction objectif prendra la forme :

Sous forme de tableau, la fonction objectif s’écrit comme suit :

Où .

Notons les caractéristiques suivantes de la forme tabulaire du PPP :

a) le système d'équations linéaires est réduit à la forme de Jordan avec des membres droits non négatifs ;

b) les variables de base sont exclues de la fonction objectif et elle s'écrit sous la forme (3.3).

Passons maintenant à la description de la table simplexe. Laissez le ZLP s'écrire sous forme de tableau :

(3.4)

Ensuite, le tableau simplex complété ressemble à ceci.

Tableau 3.1.

Base	Variables	Membres gratuits
			...	xk			...
			...				...
			...				...
. . .	. .	. .	...	. .	. .	. .	...	. .	. . .
			...				...
f			...				....

Forfait de base PPL : ..., est appelé plan de référence correspondant à cette table simplexe. Comme le montre la formule (3.2), la valeur de la fonction objectif pour ce plan de référence est égale à γ 0.

Regardons un exemple. Réduisez le ZLP suivant sous forme tabulaire et remplissez le tableau simplex :

Premièrement, le ZLP devrait prendre une forme canonique. Pour ce faire, la fonction f doit être remplacé par -f :

Le système d’équations doit être écrit sous la forme Jordan avec des membres droits non négatifs. Accueil général les moyens par lesquels cela est réalisé seront discutés plus loin (Section 3.7). Dans notre exemple, une telle forme Jordan existe déjà avec les variables de base et . Excluons les variables de base de la fonction objectif - f. Pour ce faire, nous les exprimons en termes d'expressions libres et substituons ces expressions dans la fonction objectif.

La vue tabulaire du ZLP est la suivante :

Remplissons le tableau simplex (pour raccourcir les entrées, la première colonne s'intitule « B », la dernière colonne est « Q »).

Tableau 3.2.

B			Q
		-5
	-7	-2
-f	-4		-20

Le plan de référence correspondant à ce tableau simplexe a la forme :

La valeur de la fonction -f avec ce plan de référence est - 20.

Soit une table simplexe terminée. Formulons la condition d'optimalité du plan de référence.

Si la ligne du bas d'un tableau simplex contient tous les nombres sauf peut-être celui le plus à droite, non positif, alors le plan de référence correspondant à ce tableau est optimal.

Par souci de simplicité, nous justifierons la validité de cette affirmation par un exemple. Laissez le tableau simplex complété ressembler à :

Tableau 3.3.

B				Q
		-1
			-1
f	-5	-3	-1

La valeur de la fonction objectif pour le plan de référence correspondant au tableau simplexe est égale à 6. Écrivons la fonction objectif sous forme de tableau : , où . Puisque pour toute solution admissible du ZLP les variables ne prennent que des valeurs non négatives, alors à partir de dernière entrée la fonction objectif peut voir que sa valeur en tout point de l'ODD n'est pas inférieure à 6. Par conséquent, la valeur minimale de la fonction objectif sur l'ODD est 6 et elle est réalisée avec un plan de référence correspondant à la table simplex, .

3.4. La condition d'indécidabilité du ZLP en raison du caractère illimité d'en bas sur l'ODD de la fonction objectif.

Si la table simplexe est remplie pour le ZLP, alors l'ODD du problème n'est pas vide, donc le plan de référence correspondant à la table simplex appartient à l'ODD. Cependant, le ZLP peut être insoluble en raison du caractère illimité d’en bas sur l’ODD de la fonction objectif.

La condition d’indécidabilité est formulée comme suit.

Si un tableau simplex contient au moins une colonne, autre que celle la plus à droite, qui a un nombre positif dans la ligne du bas et des nombres non positifs dans toutes les autres lignes de la colonne, alors le ZLP est insoluble car l'ODD de la fonction objectif est illimitée depuis le bas.

Pour justifier cela, nous utiliserons à nouveau un exemple.

Tableau 3.4.

B				Q
			-2
	-3		-1
f		-1

La colonne de la ligne du bas contient un nombre positif et les lignes restantes contiennent des nombres non positifs. Prouvons l'indécidabilité du ZLP.

Écrivons la forme Jordan correspondant à la table simplexe et transférons les termes contenant , à côté droit. Nous obtenons

Soit a un nombre positif arbitraire. Évidemment, le ZLP a la solution réalisable suivante :. Calculons la valeur de la fonction objectif pour cette solution réalisable. Du tableau 3.4, nous avons :

. Avec la solution réalisable spécifiée f = 4 - 2a. De là, nous voyons que la valeur de la fonction objectif peut devenir aussi petite que désirée pendant suffisamment de temps. grande importance UN. En d’autres termes, la fonction objectif n’est pas bornée par le bas sur l’ODE. La ZLP est donc indécidable.

3.5. Transition vers un nouveau plan de référence.

Supposons que les conditions d’optimalité et d’indécidabilité ne soient pas satisfaites. Ensuite, la méthode simplexe passe à un nouveau plan de référence. Cette transition s'effectue en supprimant l'une des variables de base de la base et en introduisant l'une des variables libres dans la base. Dans ce cas, les deux conditions suivantes doivent être remplies :

1) la nouvelle base doit toujours être admissible, c'est-à-dire les membres droits de la forme Jordan correspondante doivent toujours être non négatifs ;

2) avec un nouveau plan de référence, la valeur de la fonction objectif ne doit pas dépasser sa valeur avec le plan de référence précédent.

La colonne d'un tableau simplex contenant la variable entrée dans la base s'appelle colonne générale. La ligne contenant la variable dérivée de la base s'appelle ligne générale. L'élément à l'intersection de la ligne générale et de la colonne générale est appelé élément général.

Règle de choix d'un élément général.

Toute colonne du tableau simplex autre que celle la plus à droite, qui a un nombre positif dans la ligne du bas, est sélectionnée comme colonne générale. Ensuite, seules les lignes du tableau simplex sont prises en compte, autres que la plus basse, qui ont des nombres positifs à l'intersection avec la colonne générale. Pour chacune de ces lignes, le rapport du terme libre à l'élément de la colonne générale est calculé. La ligne pour laquelle ce rapport est minimal est sélectionnée comme ligne générale. L'élément à l'intersection de la ligne générale et de la colonne générale sera l'élément général.

Illustrons cette règle avec un exemple.

Tableau 3.5.

B			Q
	2	-1

	-2
F

Vous pouvez sélectionner une colonne ou une colonne comme colonne générale. Choisissons (le plus souvent la colonne avec le plus grand nombre positif en bas est choisie). Commençons maintenant par choisir la ligne générale. Pour ce faire, considérons deux lignes - et . Nous réalisons des ratios 4:2 et 8:3. Le rapport 4:2 a une valeur plus petite, nous sélectionnons donc la première ligne comme ligne générale. Par conséquent, l’élément général est 2 – il se situe à l’intersection de la colonne et de la ligne.

Après avoir sélectionné l'élément général, vous devez passer à un nouveau plan de référence, dans lequel la variable devient basique et la variable x 1 devient libre. Le coefficient pour dans le nouveau formulaire Jordan doit être égal à 1. Par conséquent, la première ligne du tableau 3.5 est divisée par 2. Ensuite, en multipliant la première ligne résultante par (-3) et en l'ajoutant à la deuxième ligne , exclure de la deuxième équation. De même, en utilisant la procédure de Jordan, nous excluons de la troisième équation et de la fonction objectif (cette dernière nécessite vue tabulaire ZLP).

En conséquence, nous obtenons le tableau suivant.

Tableau 3.6

B						Q



f						-2

Veuillez noter que dans la colonne Q, les trois premières lignes contiennent des nombres non négatifs, c'est-à-dire : la nouvelle base est toujours valable. Ce n’est pas un fait fortuit : ce sera toujours le cas si la règle de choix d’une ligne générale est strictement respectée. De plus, la valeur de la fonction objectif avec le nouveau plan de référence est égale à -2, avec l'ancien elle était égale à 12. « Amélioration » du plan de référence garantit la règle de choix de la colonne générale. Même si nous ne prouvons pas strictement ces faits, il faut garder à l’esprit qu’ils se produisent toujours.

En regardant le tableau H.6, on constate que ni la condition d’optimalité du plan de référence ni la condition d’insolvabilité du ZLP ne sont remplies. Cela signifie que nous devons sélectionner à nouveau l'élément général et passer à une nouvelle table simplexe. Le lecteur peut le faire lui-même.

3.6. Algorithme tabulaire simplex.

Soit une table simplexe terminée. En résumant ce qui précède, nous obtenons prochain algorithme Décisions PPP méthode simplexe.

1. Si dans la rangée du bas du tableau simplex tous les nombres, sauf peut-être celui le plus à droite, sont non positifs, alors le plan de référence correspondant au tableau simplex est optimal et l'algorithme s'arrête. Sinon, passez au point 2.

2. Si le tableau simplex contient une colonne autre que celle de droite, qui a un nombre positif dans la ligne du bas et des nombres non positifs dans toutes les autres lignes, alors le ZLP est insoluble en raison du caractère illimité d'en bas sur l'ODD du fonction objectif, et l’algorithme s’arrête. Sinon, passez au point 3.

3. Sélectionnez n'importe quelle colonne autre que celle la plus à droite, qui a un nombre positif dans la ligne du bas - appelons-la générale. Ensuite, nous considérons les lignes du tableau simplex, autres que celle du bas, qui ont des nombres positifs dans la colonne générale. Pour chacune de ces lignes, on calcule le rapport du terme libre à l'élément de la colonne générale. La ligne pour laquelle cette relation est minimale est la ligne générale. L'élément à l'intersection de la colonne générale et de la ligne générale sera l'élément général. Allez au point 4.

4. Nous créons un nouveau tableau simplexe dans lequel :

1) la variable de la ligne générale est dérivée de la base ; une variable de la colonne générale est inscrite dans la base ;

2) la ligne générale est divisée en un élément général ;

3) en utilisant la procédure Jordan, tous les nombres de la colonne générale, à l'exception de 1, qui se trouve dans la ligne générale, sont composés égal à zéro. Allez au point 1.

Exemple I Résoudre en utilisant la méthode du simplexe

Le problème est écrit sous forme canonique, vous devez le mettre sous forme tabulaire. Le système d'équations est écrit sous la forme de Jordan avec des membres droits non négatifs (variables de base et ). Il est nécessaire de réduire la fonction objectif à une forme tabulaire. Pour ce faire, nous exprimons les variables de base en termes de variables libres

x 3 = 10 - 2x 1 - x 2

x4 = 8 - x1 - 2x2

et substituez-le dans la fonction objectif

Pour obtenir une forme tabulaire, on écrit la fonction comme suit :

Nous avons maintenant une vue tabulaire du ZLP :

Remplissons le premier tableau simplexe

Tableau 3.7

B					Q


F

Dans le tableau 3.7, les conditions d’optimalité et d’indécidabilité ne sont pas remplies. Choisissons comme colonne générale , qui a un nombre positif dans la ligne du bas. Ensuite, en comparant les ratios 10:3 et 8:1, nous sélectionnons la première ligne comme ligne générale. Dans le tableau, l'élément général est 2.

En agissant conformément au point 4 de l’algorithme du simplexe tabulaire, passons au tableau 3.8.

Tableau 3.8

B		Q


F	-5	-22

Les conditions d’optimalité et d’indécidabilité ne sont pas satisfaites. Sélectionnez l'élément général dans le tableau 3.8 et passez au tableau suivant

Tableau 3.9

B					Q


F					-24

Le tableau 3.9 satisfait la condition d’optimalité.

Réponse : plan optimal

La valeur minimale de la fonction objectif f min = - 24.

Exemple 2. Résolvez en utilisant la méthode du simplexe :

Tout d'abord, le ZLP doit être amené à la forme canonique

Nous transformons maintenant le ZLP sous forme de tableau. Nous voyons que le système d’équations est écrit sous la forme de Jordan avec des membres droits non négatifs (et des variables de base z). Cependant, la fonction objectif comprend une variable de base. Nous avons:

Par conséquent, la vue tabulaire du ZLP est la suivante :

Remplissez le tableau simplex (tableau 3.10).

Tableau 3.10

B			z	Q
	-1
z		-2
g				-1

Après avoir sélectionné l'élément général, passez au tableau 3.11

Méthode simplexe. Algorithme. Signe d'optimalité du plan de référence.

De l'interprétation géométrique du ZLP, il est clair que le maximum ou le minimum de la fonction est atteint au point d'angle d'un polyèdre convexe - ODP - système de contraintes. Par conséquent, la méthode du simplexe est basée sur l'idée de considérer et de tester l'optimalité uniquement les points d'angle - les sommets du polyèdre, et non l'ensemble infini de ses points.

Riz. Interprétation géométrique de l'idée de la méthode du simplexe

dans le cas de deux (Figure a) et trois (Figure b) variables.

Simplexe est un polygone convexe dans un espace à n dimensions avec n+1 sommets qui ne se trouvent pas dans le même hyperplan (l'hyperplan divise l'espace en 2 demi-espaces).

Méthode simplexe est une procédure de calcul basée sur le principe d’amélioration séquentielle de la solution. Dans ce cas, on passe d’un point de base à un autre. La valeur de la fonction objectif s’améliore toujours.

Solution de base– c’est l’une des solutions acceptables trouvées dans l’ODR.

Les variables pour lesquelles un système d'équations linéaires est résolu sont appelées basique. Ensuite, toutes les autres variables sont appelées gratuit.

Il a été prouvé que si une solution optimale existe, alors elle sera trouvée en un nombre fini d’étapes, sauf en cas de bouclage.

Algorithme de la méthode simplexe :

1. Construisez un modèle mathématique du problème.

Transformez le modèle mathématique résultant en une forme canonique dans laquelle : les membres droits des conditions sont non négatifs ; les conditions sont des égalités (si nécessaire, introduire des variables artificielles).
Construisez un tableau simplexe et trouvez le plan de référence initial pour résoudre le problème. De nombreuses variables qui sont basique, sont pris comme solution de base initiale. Les valeurs de ces variables sont égales aux termes libres. Toutes les autres variables sont nulles.
L'optimalité de la solution de base est vérifiée à l'aide d'estimations spéciales des coefficients de la fonction objectif (voir la dernière ligne du tableau). Si le problème est résolu au maximum, alors toutes les estimations doivent être non négatives, si au minimum, alors toutes les estimations doivent être non positives.
Transition vers une nouvelle solution de base. Évidemment, le plan optimal devrait inclure une variable qui augmentera au maximum la fonction objectif. Lors de la résolution de problèmes maximum, le plan optimal inclut les produits dont la production est la plus rentable. Ceci est déterminé par la valeur positive maximale de l'estimation des coefficients de la fonction objectif. La colonne du tableau qui contient cette estimation est appelée la colonne principale. Si au moins un élément de la colonne est positif, alors la ligne générale est trouvée (sinon le problème n'a pas de solution optimale). S'il y a des zéros dans cette colonne, vous devez alors prendre une autre colonne. Pour trouver la ligne générale, tous les membres libres (ressources) sont répartis dans les éléments correspondants de la colonne générale (taux de consommation des ressources par unité de produit). Le plus petit est sélectionné parmi les résultats obtenus, et la ligne correspondante est appelée ligne générale. Elle correspond à une ressource qui limite la production à cette étape. Un élément de tableau simplex situé à l’intersection d’une ligne générale et d’une colonne est appelé élément général. Tous les éléments de la chaîne générale, y compris le membre libre, sont divisés en élément général. En conséquence, l'élément général devient égal à 1. Ensuite, il faut que tous les autres éléments de la colonne générale deviennent égaux à 0. La colonne générale doit devenir un. Toutes les lignes sauf la générale sont converties comme suit : éléments reçus nouvelle ligne multiplier par les éléments correspondants de la colonne générale et soustraire le produit résultant des éléments ancienne ligne. La valeur des nouvelles variables de base sera obtenue dans les cellules correspondantes de la colonne des termes libres (règle des rectangles).
L'optimalité de la solution basique résultante est vérifiée (étape n°4). Si elle est optimale, alors les calculs s'arrêtent, sinon une nouvelle solution de base est trouvée (étape n°5).

Signe d'optimalité du plan de référence

Si nous résolvons un problème pour max, alors toutes les estimations doivent être non négatives.

Si nous résolvons un problème pendant min, alors toutes les estimations doivent être non positives.

Si le plan de référence n’est pas optimal, vous devez passer à un meilleur plan de référence. Pour ce faire, nous choisissons le plus pire note. Cela correspondra à la colonne de résolution. Après cela, vous devez trouver la ligne d'activation.

Θ (la colonne des relations simplexes) n'est pas dessinée pour les lignes avec des valeurs négatives et nulles. De tous θ, nous choisissons le plus petit ; ceci est toujours fait, que le problème initial soit min ou max.

La ligne de résolution indique toujours quel élément doit être supprimé de la base, et la colonne de résolution indique toujours quel élément doit être introduit dans la base.