Un grand nombre de problèmes économiques sont réduits à des modèles mathématiques linéaires. Traditionnellement, on les appelle modèles de programmation linéaire. La programmation linéaire signifie une planification linéaire, c'est-à-dire recevoir plan optimal-solutions aux problèmes de structure linéaire. Il est généralement utilisé par les spécialistes des unités du siège pour résoudre les difficultés de production. Des exemples typiques d'applications du modèle de programmation linéaire sont les suivants :

planification intégrée de la production (établissement de calendriers de production qui minimisent les coûts totaux dus aux variations des taux d'intérêt) ;

planifier la gamme de produits (déterminer la structure optimale de la production alimentaire pour l'homme) ;

acheminement de la production d'un produit (détermination de l'itinéraire technologique optimal pour fabriquer un produit) ;

régulation des stocks (détermination de la combinaison optimale de produits dans l'entrepôt) ;

planification de la production (établissement de plannings minimisant les coûts, prenant en compte les coûts de maintien des stocks, le paiement des heures supplémentaires et des commandes externes) ;

planification de la distribution des produits, etc.

Dans sa forme la plus générale, la programmation linéaire se réduit à un problème d'optimisation et s'écrit sous la forme suivante :

Pour résoudre un problème d'optimisation, il suffit de trouver sa solution optimale, c'est-à-dire indiquer
tel que F(X 0 )≥ F(X) à n'importe
, ou pour le cas de minimisation - F(X 0 )≤ F(X) à n'importe
.

Un problème d’optimisation n’est pas résolu s’il n’a pas de solution optimale. En particulier, le problème de maximisation ne sera pas résolu si fonction objectif F(X) n'est pas borné par le haut sur l'ensemble admissible W.

Les méthodes de résolution des problèmes d'optimisation dépendent à la fois du type de fonction objectif F(X) , et de la structure de l'ensemble admissible W. Si la fonction cible du problème est une fonction P. variables, alors les méthodes de résolution sont appelées méthodes de programmation mathématique.

Un problème de programmation linéaire est un problème de recherche opérationnelle dont le modèle mathématique a la forme :

Dans le même temps, le système équations linéaires(2) et les inégalités (3), (4), qui déterminent l'ensemble admissible de solutions au problème W, est appelé le système de contraintes d'un problème de programmation linéaire, et la fonction linéaire F(X) appelée fonction objectif, ou critère d’optimalité.

Si le modèle mathématique du problème programmation linéaire a la forme :

alors ils disent que le problème est présenté sous forme canonique.

Tout problème de programmation linéaire peut être réduit à un problème de programmation linéaire dans Forme canonique, déplaçant la maximisation vers la minimisation, des contraintes d'inégalité aux contraintes d'égalité, et remplaçant les variables qui n'obéissent pas à la condition de non-négativité. Maximiser une certaine fonction équivaut à minimiser la même fonction prise avec le signe opposé et vice versa.

La règle pour amener un problème de programmation linéaire sous forme canonique est la suivante :

1) si dans le problème initial il faut déterminer le maximum fonction linéaire, alors vous devez changer le signe et rechercher le minimum de cette fonction ;

2) si le côté droit des restrictions est négatif, alors cette restriction doit être multipliée par (-1) ;

3) s'il existe des inégalités entre les restrictions, alors en introduisant des variables supplémentaires non négatives, elles sont transformées en égalités ;

4) si une variable X k n'a pas de restrictions de signe, alors il est remplacé (dans la fonction objectif et dans toutes les restrictions) par la différence entre deux nouvelles variables non négatives : X k = X’ k - X 1 , où 1 est un indice libre, X’ k ≥ 0, X 1 ≥ 0.

En résumant ce qui précède, nous pouvons tirer les conclusions suivantes :

1. Les contraintes dans les problèmes de programmation linéaire peuvent être exprimées à la fois par des égalités et des inégalités.

2. Une fonction linéaire peut tendre vers un maximum et un minimum.

3. Les variables du modèle sont toujours non négatives.

4. À partir de n’importe quel problème de programmation linéaire, vous pouvez passer au problème de programmation linéaire canonique (principal).

Chaque problème de programmation linéaire peut être comparé à un autre problème de programmation linéaire qui est double du problème d'origine (direct).

Considérons un problème de programmation linéaire de la forme suivante :

	………………………..

Le problème nécessite de maximiser la fonction objectif ; toutes les contraintes sont des inégalités de signe ≤, toutes les variables X 1 , X 2 ,…,X P. P. variables de contrôle et m restrictions. Coefficients des variables dans la fonction objectif : c 1 , c 2 ,…, c n; membres gratuits : b 1 , b 2 ,…, b m .

Le problème de programmation dual linéaire a la forme :

	………………………..

Dans un problème dual, il faut trouver le minimum de la fonction objectif, les contraintes - inégalités de signe ≥, les variables de contrôle oui 1 , oui 2 ,…, oui m non négatif. La tâche contient m variables de contrôle et n restrictions. Coefficients de la fonction objective du problème b 1 , b 2 ,…, b m sont les termes libres du problème de programmation linéaire original, et les termes libres double problème c 1 , c 2 ,…, c n – coefficients de la fonction objectif du problème de programmation linéaire original. La matrice des coefficients du problème dual est transposée, c'est-à-dire Les lignes sont remplacées par des colonnes et les colonnes sont remplacées par des lignes.

Les problèmes (9) – (10) et (11) – (12) forment une paire de problèmes, appelée double paire en programmation linéaire.

Le problème dual par rapport au problème original se compose selon les règles suivantes :

1. La fonction objective du problème initial est fixée au maximum et la fonction objective du problème double est fixée au minimum.

2. Matrice UN(13)

,

composé de coefficients pour les inconnues dans le système de contraintes (10) du problème original (9) – (10) et d'une matrice similaire dans le problème dual (11) – (12) sont obtenus l'un de l'autre par transposition.

3. Le nombre de variables dans le problème dual (11) – (12) est égal au nombre de restrictions dans le système (10) du problème d'origine et au nombre de restrictions dans le système (12) du problème dual. est égal au nombre de variables du problème d’origine.

4. Les coefficients des inconnues dans la fonction objectif (11) du problème dual sont les termes libres dans le système (10) du problème d'origine, et les membres droits dans les contraintes du système (12) du problème le problème dual sont les coefficients des inconnues dans la fonction objectif (9) du problème original.

5. Si la variable X j du problème initial (9) – (10) ne peut prendre que des valeurs non négatives, alors j- La contrainte dans le système (12) du problème dual est une inégalité de la forme ≥. Si la variable X j peut prendre des valeurs à la fois positives et négatives, alors j- La contrainte dans le système (12) est l'équation. Des connexions similaires ont lieu entre les contraintes (10) du problème initial et les variables du problème dual. Si je- Si la contrainte dans le système (10) du problème initial est une inégalité, alors je- Je suis la variable du double problème oui je ≥ 0. Si je- Si la contrainte est une équation, alors la variable oui je peut prendre des valeurs positives et négatives.

L'idée d'une amélioration séquentielle de la solution a constitué la base d'une méthode universelle pour résoudre des problèmes de programmation linéaire - la méthode simplex. La signification géométrique de cette méthode consiste en une transition séquentielle d'un sommet du polyèdre de contrainte (appelé initial) au voisin, dans lequel la fonction linéaire prend la meilleure (du moins pas la pire) valeur (par rapport à l'objectif du problème) jusqu'à ce qu'elle soit trouvée. La solution optimale est le sommet où la valeur optimale de la fonction but est atteinte (si le problème a un optimum final). Les idées de la méthode ont été publiées par le scientifique russe L.V. Kantorovitch en 1939

Pour appliquer la méthode du simplexe, des variables supplémentaires sont introduites dans les contraintes du problème oui 1 , oui 2 ,…, oui je et la condition du problème initial prend la forme :

	……….…………………..

Cet énoncé peut être présenté sous la forme d'un tableau - le premier tableau de la méthode simplex (tableau 1.1).

Tableau 1.1.

Premier tableau simplexe

	Membres gratuits	Variables libres
		X 1	X 2		X n
oui 1	b 1	un 11	un 12		un 1n
oui 2	b 2	un 21	un 22		un 2n
oui m	b m	un m1	un m2		un minute
Ligne d'index		-c 1	-c 2		-c n

Pour compiler un tableau simplexe, vous pouvez appliquer certaines règles.

1. Pour le premier tableau :

a) écrivez dans la première colonne oui m– les variables de base qui sont dans les équations de gauche ;

b) variables libres un minute placé dans la rangée supérieure du tableau ;

c) les coefficients devant les variables libres sont écrits dans les colonnes restantes.

2. Pour les tableaux suivants :

a) le plus petit élément négatif dans la ligne d'index est sélectionné lors de la recherche du maximum, mais le plus grand élément positif est sélectionné lors de la recherche du minimum, à l'exclusion du vecteur de termes libres ;

b) cet élément définit le vecteur colonne clé et il est entré dans la base ;

c) les composantes du vecteur de termes libres sont divisées par les éléments positifs de la colonne clé ;

d) le plus petit est sélectionné parmi les rapports obtenus ;

e) un vecteur ligne contenant le plus petit quotient positif est le vecteur clé et est dérivé de la base ;

f) à l'intersection des lignes clés et de la colonne se trouve un élément permissif ;

g) transformation matricielle :

Chaque élément de chaîne clé est divisé en un élément d'activation. Les quotients résultants sont les éléments de ligne clés du tableau suivant,

Colonne clé dans nouveau tableau– des zéros, à l'exception de l'élément résolvant,

Les éléments restants du nouveau tableau sont calculés selon le schéma suivant :

Nouvel élément = Ancien élément –

- Élément de ligne clé*Élément de colonne clé

Élément permissif

Si la ligne (colonne) nulle contient zéro, alors la colonne correspondante (ligne 0 dans la nouvelle table ne changera pas.

3. Les points « a » - « g » sont répétés jusqu'à ce qu'il ne reste plus un seul élément négatif dans la ligne d'index lors de la recherche du maximum (mais pas un seul élément positif lors de la recherche du minimum).

Exemple 1.1. Il est nécessaire de prendre une décision sur le plan optimal pour la production de tricots pendant un mois chez Sviyazh OJSC en utilisant la méthode simplex.

Nous déterminerons un plan de production de modèles de tricots pour hommes afin d'obtenir un profit maximum avec les ressources données en utilisant la construction modèle mathématique. Les données initiales sont présentées dans le tableau 1.2.

Tableau 1.2.

Donnée initiale

Ressources ( je)	Type de produit ( j)				Réserve de ressources ( b je)
	Pantalon de sport modèle 7060	Pull homme modèle 55-1	Pull homme modèle 38-0	Modèle de combinaison de sport
	consommation de ressources spécifiques ( un je)
Travail
Matériel
Équipement
	X 1	X 2	X 3	X 4

Les données initiales sur la consommation spécifique de ressources matérielles et de main-d'œuvre sont présentées dans le tableau. 1.2 conformément à la documentation réglementaire et technologique en vigueur dans l'organisation. La ligne "Ressources matérielles" enregistre le taux de consommation du type de matériau le plus rare (limité0) - le fil de laine. Ce matériau a le taux de consommation et le coût les plus élevés.

La ligne « Équipement » montre l'intensité de travail récapitulative de la fabrication d'une unité de produit en heures standard comme total pour toutes les opérations partielles. D'autres types de ressources sont également pris en unités naturelles : ressources en main-d'œuvre - en heures ; matériel - en dm 2.

La ligne « Bénéfice » reflète le bénéfice de la vente d'une unité de produit, tiré du devis prévu pour une unité de produit.

À travers X 1 , X 2 , X 3 , X 4 indiqué la quantité de produits fabriqués pour chaque type d'assortiment.

Selon la règle de construction d’un problème de programmation linéaire standard, créons un modèle mathématique :

Dans les contraintes du problème, nous introduisons des variables supplémentaires oui 1 , oui 2 , oui 3 et réécrivez la condition problématique sous la forme d’une équation :

La dernière déclaration peut être présentée sous la forme du tableau 1.3 - le premier tableau de la méthode du simplexe, que nous utiliserons pour résoudre le problème de programmation linéaire.

Tableau 1.3.

Premier tableau simplexe

	Membres gratuits	Variables libres
		X 1	X 2	X 3	X 4
oui 1
oui 2
oui 3
Ligne d'index

La première colonne contient oui je – les variables de base sont celles à gauche de l'équation, et les variables libres X j placé dans la première rangée du tableau. Les colonnes restantes contiennent les coefficients des variables libres. La ligne d'index est le résultat de la soustraction des coefficients devant les variables libres de zéro.

Pour construire le tableau suivant, le plus petit élément négatif de la ligne d'index est sélectionné (c'est 222). Cet élément définit le vecteur colonne clé et il est introduit dans la base. Les composantes du vecteur de termes libres sont divisées par les éléments positifs de la colonne clé et le plus petit est sélectionné parmi les ratios résultants. Le vecteur ligne contenant le plus petit quotient positif est le vecteur clé et est dérivé de la base ( oui 2 ). À l'intersection des lignes clés et de la colonne se trouve un élément d'activation (c'est 55,50).

Chaque élément de chaîne clé est ensuite divisé en un élément d'activation. Les quotients résultants sont les éléments de la ligne clé du tableau suivant. En conséquence, le deuxième tableau simplex a été obtenu (tableau 1.4).

Tableau 1.4.

Deuxième table simplex

	Membres gratuits	Variables libres
		X 1	X 2	X 3	X 4
oui 1
oui 2
oui 3
Ligne d'index

Puisqu'un élément négatif est apparu dans la ligne d'index, toutes les étapes similaires doivent être répétées et un troisième tableau simplex doit être construit.

Le résultat est un tableau. 1.5.

Tableau 1.5.

Table simplexe finale

	Membres gratuits	Variables libres
		X 1	X 2	X 3	X 4
oui 1
oui 2
oui 3
Ligne d'index

Sur la base du tableau 1.5, nous pouvons tirer des conclusions : dans la colonne des termes libres, tous les éléments sont positifs (cela signifie que la solution résultante est admissible) ; dans la ligne d'index, tous les éléments sont également positifs (cela signifie que la solution résultante est optimale, c'est-à-dire qu'elle maximise la fonction objectif) ; le plan optimal serait les valeurs suivantes :
(c'est-à-dire qu'ils sont basiques) ;
(puisqu'ils sont gratuits) ; fonction objectif L= 4 201 195.

Il résulte également du tableau 1.5 que la variable de base oui 3 =9716, et variables libres oui 1 = oui 2 = 0, c'est-à-dire dans le plan optimal, les réserves de main-d'œuvre et de ressources matérielles sont égales à zéro, puisqu'elles sont pleinement utilisées. Une réserve de ressources matérielles oui 2 = 9716, ce qui indique son excédent.

Ainsi, suite à l'application de la méthode de programmation linéaire, il a été décidé de produire des pulls pour hommes du modèle sélectionné à hauteur de 3981 pièces, des pulls pour hommes modèle 55-1 à hauteur de 29 875 pièces.

La programmation linéaire est une branche des mathématiques qui étudie les méthodes de résolution de problèmes extrêmes caractérisés par une relation linéaire entre des variables et un critère d'optimalité linéaire.

Quelques mots sur le terme programmation linéaire lui-même. Cela nécessite une compréhension correcte. Dans ce cas, la programmation n’est bien entendu pas la compilation de programmes informatiques. Ici, la programmation doit être interprétée comme la planification, l'élaboration de plans, l'élaboration d'un programme d'action.

À Problèmes mathématiques La programmation linéaire comprend des études sur des situations de production et économiques spécifiques, qui, sous une forme ou une autre, sont interprétées comme des problèmes concernant utilisation optimale ressources limitées.

L'éventail des problèmes résolus à l'aide des méthodes de programmation linéaire est assez large. C'est par exemple :

· le problème de l'utilisation optimale des ressources dans la planification de la production ;

· problème de mélange (planification de la composition du produit) ;

· le problème de trouver la combinaison optimale divers types les produits destinés au stockage en entrepôt (gestion des stocks ou « problème du sac à dos ») ;

· tâches de transport (analyse de la localisation de l'entreprise, mouvement des marchandises).

La programmation linéaire est la section la plus développée et la plus utilisée de la programmation mathématique (elle comprend en outre : les nombres entiers, dynamiques, non linéaires, programmation paramétrique). Ceci s'explique comme suit :

· les modèles mathématiques d'un grand nombre de problèmes économiques sont linéaires par rapport aux variables requises ;

· ce type de problème est actuellement le plus étudié. Des méthodes spéciales ont été développées à cet effet, à l'aide desquelles ces problèmes sont résolus, ainsi que des programmes informatiques correspondants ;

· de nombreux problèmes de programmation linéaire, après avoir été résolus, ont trouvé de nombreuses applications ;

· certains problèmes qui, dans la formulation originale, ne sont pas linéaires, après un certain nombre de restrictions et d'hypothèses supplémentaires, peuvent devenir linéaires ou être réduits à une forme telle qu'ils peuvent être résolus par des méthodes de programmation linéaire.

Le modèle économique et mathématique de tout problème de programmation linéaire comprend : une fonction objectif dont il faut trouver la valeur optimale (maximale ou minimale) ; restrictions sous la forme d'un système d'équations linéaires ou d'inégalités ; exigence de non-négativité des variables.

En général, le modèle s'écrit comme suit :

fonction objectif :

F = c1x1 + c2x2 + ... + cnxn → max(min);

restrictions :

a11x1 + a12x2 + ... + a1nxn (≤ = ≥) b1,

a21x1 + a22x2 + ... + a2nxn (≤ = ≥) b2,

am1x1 + am2x2 + ... + amnxn (≤ = ≥) bm;

exigence de non-négativité :

Le problème est de trouver la valeur optimale de la fonction tout en satisfaisant les contraintes.

Donc, La programmation linéaire est une branche de la programmation mathématique qui étudie les méthodes de résolution de problèmes extrêmes caractérisés par une relation linéaire entre des variables et un critère linéaire.

Une condition nécessaire pour poser un problème de programmation linéaire sont les restrictions sur la disponibilité des ressources, le montant de la demande, la capacité de production de l'entreprise et d'autres facteurs de production.

L'essence de la programmation linéaire est de trouver les points de la plus grande ou de la plus petite valeur d'une certaine fonction sous un certain ensemble de restrictions imposées aux arguments et formant un système de restrictions qui, en règle générale, a un nombre infini de solutions. Chaque ensemble de valeurs de variables (arguments de la fonction F) qui satisfont le système de contraintes est appelé plan admissible du problème de programmation linéaire. La fonction F dont le maximum ou le minimum est déterminé est appelée fonction objectif du problème. Un plan admissible sur lequel le maximum ou le minimum de la fonction F est atteint est appelé plan optimal du problème.

Le système de restrictions qui détermine de nombreux plans est dicté par les conditions de production. La tâche de la programmation linéaire (LP) est de sélectionner le plan le plus rentable (optimal) parmi un ensemble de plans réalisables.

Méthode simplexe est le principal dans programmation linéaire . La résolution du problème commence par considérer l’un des sommets du polyèdre des conditions. Si le sommet étudié ne correspond pas au maximum (minimum), alors ils se déplacent vers le voisin, augmentant la valeur de la fonction objectif lors de la résolution du problème pour le maximum et la diminuant lors de la résolution du problème pour le minimum. Ainsi, passer d’un sommet à un autre améliore la valeur de la fonction objectif. Étant donné que le nombre de sommets du polyèdre est limité, en un nombre fini d'étapes, il est garanti de trouver la valeur optimale ou d'établir le fait que le problème est insoluble.

Cette méthode est universelle, applicable à tout problème de programmation linéaire dans Forme canonique. Le système de contraintes est ici un système d'équations linéaires dans lequel le nombre d'inconnues plus de quantitééquations. Si le rang du système est r , alors nous pouvons choisir r inconnues, que nous exprimerons à travers les inconnues restantes. Pour plus de précision, nous supposons que les premières inconnues consécutives sont sélectionnées X 1 , X 2 , ..., Xr . Alors notre système d’équations peut s’écrire

Il peut être amené à cette forme tout système commun , par exemple, par la méthode gaussienne. Certes, il n'est pas toujours possible de l'exprimer en termes des premières r inconnues restantes (nous l'avons fait pour la précision de la notation). Cependant, un tel r il y aura certainement des inconnues. Ces inconnues (variables) sont dites basiques, le reste est libre.

En attribuant certaines valeurs aux variables libres et en calculant les valeurs des variables de base (exprimées en termes de variables libres), nous obtiendrons diverses solutions notre système de restrictions. Ainsi, n’importe quelle solution peut être obtenue. Nous nous intéresserons aux solutions particulières obtenues dans le cas où les variables libres sont égales à zéro. De telles solutions sont appelées basique, il y en a autant qu'il existe de différents types fondamentaux d'un système de restrictions donné. La solution de base s'appelle solution de base admissible ou Solution de référence, si les valeurs des variables qu'il contient ne sont pas négatives. Si les variables sont considérées comme fondamentales X 1 , X 2 , ..., Xr , alors la solution (b 1 , b 2 ,..., b r , 0, ..., 0) apportera son soutien à condition que b 1 , b 2 ,..., b r ≥ 0 .

La méthode du simplexe est basée sur un théorème appelé théorème fondamental de la méthode du simplexe. Parmi les plans optimaux d'un problème de programmation linéaire sous forme canonique il existe nécessairement une solution de référence à son système de contraintes. Si le plan optimal du problème est unique, alors il coïncide avec une solution de référence. Il existe un nombre fini de solutions différentes de support au système de contraintes. Ainsi, une solution au problème sous forme canonique pourrait être recherchée en énumérant les solutions de référence et en choisissant parmi elles celle pour laquelle la valeur F le plus grand. Mais, premièrement, toutes les solutions de référence sont inconnues et doivent être trouvées, et, deuxièmement, dans les problèmes réels, il existe un grand nombre de ces solutions et une recherche directe est difficilement possible. La méthode simplexe est une certaine procédure d'énumération dirigée des solutions de support. Sur la base d'une certaine solution de référence trouvée à l'avance à l'aide d'un certain algorithme de la méthode simplexe, nous calculons une nouvelle solution de référence sur laquelle la valeur de la fonction objectif F pas moins que l'ancien. Après une série d’étapes, nous arrivons à une solution de référence, qui est le plan optimal.

Ainsi, la méthode du simplexe introduit un certain ordre à la fois lors de la recherche de la première solution de base (initiale) et lors du passage à d'autres solutions de base. Son idée est la suivante.

Ayant système de restrictions , réduit à une forme générale, c'est-à-dire à un système de m équations linéaires avec n variables (m< n) , trouver n'importe quelle solution de base ce système, en ne se souciant que de le trouver le plus simplement possible.

Si la première solution de base trouvée s'avérait être acceptable , puis vérifie-le optimalité. Si ça pas optimal , alors un passage à un autre s'effectue, nécessairement solution de base admissible .

La méthode du simplexe garantit qu'avec cette nouvelle solution la forme linéaire, si elle n'atteint pas l'optimum, s'en rapprochera. Ils font de même avec la nouvelle solution de base réalisable jusqu’à ce qu’ils trouvent une solution optimale.

Si la première solution de base trouvée s'avère être inacceptable , alors en utilisant la méthode du simplexe, il est possible de transition vers d'autres solutions de base, qui nous rapprochent de la région des solutions admissibles, jusqu'à ce qu'à une étape de décision soit la solution de base s'avère admissible et l'algorithme de la méthode simplex lui soit appliqué, soit nous sommes convaincus de l'incohérence du système de restrictions.

Ainsi, l'application de la méthode du simplexe se divise en deux étapes : trouver une solution fondamentale admissible au système de contraintes ou établir le fait de son incompatibilité ; trouver la solution optimale.
De plus, chaque étape peut comprendre plusieurs étapes correspondant à l'une ou l'autre solution de base. Mais comme le nombre de solutions de base est toujours limité, le nombre d’étapes de la méthode du simplexe est également limité.

Le schéma donné de la méthode simplex exprime clairement sa nature algorithmique (la nature d'une instruction claire sur l'exécution d'opérations séquentielles), ce qui permet de programmer et de mettre en œuvre avec succès cette méthode sur un ordinateur. Les problèmes avec un petit nombre de variables et de contraintes peuvent être résolus méthode simplexe manuellement.

Sans nous attarder plus en détail sur l'essence de l'algorithme, nous décrirons son côté informatique. Calculs utilisant la méthode simplexe sont organisés sous la forme tableaux simplexes, qui sont une représentation abrégée du problème de programmation linéaire sous forme canonique. Avant de compiler tableaux simplexes la tâche devrait être converti , système de restrictions réduit à forme de base acceptable, à l'aide duquel les variables de base doivent être exclues de la fonction cible. Nous examinerons ci-dessous la question de ces transformations préliminaires. Nous supposerons maintenant qu'ils ont déjà été terminés et que la tâche a la forme suivante.

La programmation linéaire représente des méthodes permettant de résoudre une certaine classe de problèmes de recherche de valeurs extrêmes (vérification ou min). Ils reposent sur la résolution d’un système d’équations linéaires lorsque la dépendance est strictement fonctionnelle. Le modèle de programmation linéaire comporte trois composantes : la fonction cible (maximisée ou minimisée), le système de contraintes et la condition de non-négativité des variables. L'appareil mathématique de programmation linéaire est utilisé pour résoudre des problèmes économiques, techniques, militaires, etc.

Dans les problèmes économiques de planification optimale, résoudre la fonction objectif revient à trouver le maximum, par exemple, du profit, du volume de production, de la productivité du travail ou le minimum des coûts courants, des investissements en capital, du temps d'exécution des travaux, etc.

Dans le même temps, il convient de noter que tous les problèmes de planification optimale ne peuvent pas être formulés et résolus dans le cadre d'une programmation linéaire. Pour ce faire, quatre conditions fondamentales doivent être remplies.

• 1. Le problème doit être clairement formulé et quantifié critère d'optimalité, ce qui n'est pas si facile à faire en pratique. La performance d'une entreprise est le plus souvent jugée par un certain nombre d'indicateurs : volume de production, gamme et qualité des produits, rentabilité de la production, etc. Le choix d'un critère peut être loin d'être le meilleur du point de vue d'un autre et vice versa. .
• 2. Important partie intégrante Les problèmes de programmation linéaire sont restrictions, liés aux ressources disponibles, aux besoins ou à d’autres facteurs. Dans une économie réelle, il n’est pas toujours possible de prendre également en compte l’interaction grande quantité facteurs, c’est pourquoi un modèle simplifié est élaboré pour refléter plus fidèlement la nature réelle.
• 3. La programmation linéaire implique un choix d'options et n'est applicable que lorsque les conditions spécifiques du problème économique le déterminent liberté de choix.
• 4. Le modèle doit contenir uniquement des équations ou inégalités linéaires, ceux. toutes les variables du problème doivent être à la première puissance. Les véritables dépendances économiques ne sont pas toujours linéaires.

Compte tenu des conditions correspondantes et approximation de la situation économique pour résoudre des problèmes de programmation linéaire, il faut également tenir compte du fait qu'imposer des restrictions trop strictes sur des quantités variables peut conduire à une incohérence de l'ensemble du système de conditions initiales du problème.

Selon la nature des problèmes à résoudre, les méthodes de programmation linéaire peuvent être divisées en deux groupes.

• 1.Méthodes universelles. Avec leur aide, tous les problèmes de programmation linéaire peuvent être résolus. Le plus courant est méthode simplexe, proposé par J. Danzig, méthode de résolution des multiplicateurs, développé par l'académicien L.V. Kantorovitch en 1939, environ 10 ans avant son apparition à l'étranger.
• 2. Méthodes spéciales. Ces méthodes sont plus simples que les méthodes universelles, mais ne sont pas applicables à toutes les tâches. Ceux-ci inclus méthode de distribution pour résoudre le problème du transport, méthode de résolution des termes A. L. Lurie, méthode des loyers différentiels A. L. Brudno, Méthode hongroise.

Un groupe spécial de méthodes de programmation linéaire comprend méthodes approximatives, qui diffèrent des autres en ce qu'ils ne garantissent pas une solution strictement optimale au problème, mais ils sont simples et bien adaptés aux calculs manuels. Ceux-ci inclus méthode d'indexation, Méthode d'approximation de Vogel et etc.

Méthode simplexe. Pour mieux comprendre l'idée de la méthode simplexe, envisagez de résoudre le problème de l'optimisation de l'utilisation des ressources afin d'obtenir un profit maximum.

Exemple 2.21

Il existe une production auxiliaire qui utilise les matériaux restant de la production principale. Cette usine de production produit des portes de différents assortiments : avec utilisation de verre (gamme LAN) et sans verre (gamme DV). Les ventes de ces produits sont assurées, c'est-à-dire les produits peuvent être fabriqués dans n'importe quel rapport, mais il existe une limitation du nombre d'emplois dans l'atelier et des ressources en matériaux de base. La tâche consiste à planifier pour l'atelier une production mensuelle qui génère le plus grand profit possible.

La tâche ne fixe pas de conditions pour l'utilisation obligatoire de la totalité du volume des ressources. Il est nécessaire que la consommation du temps de travail ne dépasse pas les limites spécifiées.

Considérons programme 1, qui implique la production uniquement de portes de la gamme DV, sans utiliser de verre pour leur production.

Si vous diffusez uniquement la télévision, en utilisant toutes les ressources disponibles, alors elles suffiront à diffuser :

• - par temps de travail : 520/9,2 = 56 (pièces) ;
• - bois : 24/0,3 = 80 (pièces).

Toutes les ressources sont donc suffisantes pour produire seulement 56 portes.

Le bénéfice de cette émission s'élèvera à 168 000 roubles. (56 3000).

Programme 2 suppose la production uniquement de portes de la gamme LAN. Dans ce cas, il y aura suffisamment de ressources pour libérer :

• - mais temps de travail : 520/4 = 130 (pièces) ;
• - bois : 24/0,6 = 40 (pièces) ;
• - verre : 40/2 = 20 (pièces).

De manière optimale, il est possible de produire seulement 20 portes LAN, ce qui est limité par la présence de verre. Cela nécessitera 12 m de bois, à partir de la partie restante, il est possible de produire 40 pièces supplémentaires. portes de la gamme DV. Pour la production de 20 pièces. GLACE et 40 pcs. DV nécessitera 448 heures-homme.

Le bénéfice sera de 160 000 roubles. (20-2 + ​​40-3). Le premier programme est donc préférable. Il existe d'autres options.

Les limites de cette tâche sont :

Traçons une ligne droite sur le graphique Lu correspondant à la première inégalité : La deuxième inégalité correspond à la droite b2 :

La troisième inégalité du graphique correspond à une droite parallèle à l'axe des abscisses L 3 :

Étant donné que le plan de publication doit être basé sur les cinq contraintes du problème, la zone de solutions réalisables dans ce cas sera un polygone ombré.

La valeur maximale de la fonction objectif trouvée dans les calculs précédents correspondra aux points de la droite :

Le polygone limite le domaine des solutions possibles au problème. Parmi la masse de solutions, vous devez choisir celle où la valeur du profit est maximale. Dans notre cas, l'ego sera le point d'intersection des lignes L ( Et 1 2 . Ensuite, le système d'équations linéaires est résolu :

En résolvant le système, on obtient : le profit est donc :

Si la droite correspondant à la fonction objectif (en méthode graphique) passe par le sommet du polygone, alors le problème a une seule option optimale. S'il coïncide avec le côté du polygone, le problème a de nombreuses solutions.

La solution optimale doit passer soit par un sommet, soit par un côté du polygone. Ainsi, l’un des sommets correspond à la solution optimale, mais on ne sait pas au départ lequel.

La méthode graphique est simple et visuelle, mais son application est limitée.

Avec trois variables, il faudrait construire un polyèdre en système multidimensionnel coordonnées Avec quatre variables ou plus image graphique impossible. Mais il est possible d’imaginer l’espace multidimensionnel de manière abstraite. Si la condition du problème est cohérente, alors la région des valeurs admissibles (ADV) forme un polygone convexe dans un espace à n dimensions.

Dans ce cas, la solution optimale, si elle existe, est nécessairement obtenue à un sommet du polyèdre (éventuellement à plusieurs).

Ainsi, pour trouver une solution à un problème de programmation linéaire, il suffit d'énumérer les options correspondant aux sommets du polyèdre. C’est ce qu’on appelle les plans de référence. Cependant, dans tâches complexes ils sont peut-être trop nombreux et la détermination des plans de référence nécessitera une quantité énorme de calculs.

La méthode du simplexe permet d'effectuer une recherche ordonnée des sommets d'un polyèdre.

Regardons la séquence de calculs utilisant la méthode du simplexe à l'aide d'un exemple.

Exemple 2.23

L'entreprise dispose de trois groupes d'équipements (I, II, III), sur lesquels sont fabriqués quatre types de produits (A, B, C, D). Tous les produits ont des ventes illimitées et l'entreprise peut donc planifier un programme d'assortiment dans la gamme donnée.

Les restrictions suivantes s'appliquent :

• - disponibilité des équipements de base ;
• - des normes de délais de traitement de chaque type de produit sur les équipements de chaque groupe ;
• - le montant du bénéfice perçu par l'entreprise par unité d'un type spécifique de produit.

Vous devez obtenir un profit maximum.

Problème que vous recherchez : X (- éd. UN; X 2 - éd. B ; X 3 - éd. DANS; X 4 - éd. G.

Bénéfice maximal :

Restrictions :

Pour résoudre le problème en utilisant la méthode du simplexe, on transforme toutes les inégalités en égalités. Pour ce faire, nous introduisons trois variables supplémentaires non négatives dans le problème : X 5 , x6, x 7 et ajoutez-les au côté gauche de l'inégalité :

Dans leur sens économique, les variables supplémentaires ne sont rien d'autre que la durée de fonctionnement inutilisée d'un équipement spécifique. Pour résoudre des problèmes à l'aide de la méthode simplex, des tableaux simplex spéciaux sont compilés.

Dans la plupart ligne supérieure les coefficients de la fonction objectif sont enregistrés. Les variables supplémentaires correspondent à des coefficients nuls. Les équipements inutilisés ne génèrent pas de profit. Les mêmes indicateurs zéro sont dans la colonne AVEC contre chaque variable supplémentaire.

En remplissant la ligne Zj - CJ ont leurs propres caractéristiques. À l'étude Zj pour chaque colonne. Il est obtenu comme la somme des produits des valeurs des colonnes AVEC par les coefficients de colonne correspondants j. Puisque dans la version originale dans la colonne AVEC sont 0, alors la valeur Zj pour toutes les colonnes est 0 et la valeur Zj - Cj= -Cj. Ainsi, dans la version initiale, les coefficients de la fonction objectif sont ici fixés avec le signe opposé. Toutes les variables principales sont mises à 0 et ne sont pas incluses dans la base de notre problème. Les variables supplémentaires sont égales aux valeurs limites selon les équations d'origine. Cela signifie que rien n’est produit, aucune ressource n’est utilisée et la valeur de la fonction objectif est 0 (pas de profit).

La solution au problème consiste à introduire séquentiellement les principales variables dans le plan jusqu'à obtenir la solution optimale. Dans ce cas, à chaque étape du calcul vous ne pouvez saisir qu’une seule variable. Dans ce cas, une autre variable est supprimée de la base, car avec trois restrictions, il ne peut y avoir plus de trois variables dans la base.

Puisque le problème est résolu par maximum profit, vous devez commencer par le produit le plus rentable. Dans notre cas, il s'agit d'ed. D. Introduit dans la base x4. Déterminons comment la publication de la publication peut être envisagée. D. Cela dépend de la quantité de ressources et des normes de coûts. Les équipements du groupe I peuvent traiter 3 000 articles. (24 000/8), le groupe II n'est pas impliqué dans la production de G et le groupe III peut être utilisé pour traiter 30 000 articles. On accepte la plus petite des valeurs (3000 éd.), dans le tableau de la colonne « base » X 4 mettre en place X 5 (l'équipement du groupe I est égal à zéro, puisqu'il est entièrement utilisé). Numéro 8 à l'intersection xA Et X 5 appelé élément de guidage ou général, clé, permissif.

Doubler X 4 dans le nouveau tableau est obtenu en divisant la ligne de la variable de sortie X 5 du tableau précédent sur l'élément de guidage. En colonne AVEC 0,8 est saisi - le montant du bénéfice par unité de publication. D. Après cela, la colonne « plan » est recalculée. Sur les équipements du groupe II éd. G n'est pas traité et dans la nouvelle version le fonds de son temps reste inchangé (12 000 minutes).

Le fonds de temps des équipements du groupe III diminuera de 3000 minutes (1 minute x x 3000 pièces), donc 27 000 minutes resteront inutilisées. Le chiffre suivant dans la colonne « plan » est de 2 400 roubles. (0,8 3000) - bénéfice à cette option. Après la colonne « plan », toutes les autres colonnes du tableau simplex sont recalculées, à l'exception de la ligne de la variable d'entrée. Dans le même temps, il convient de garder à l'esprit que dans les colonnes de toutes les variables incluses dans la base, à l'intersection des lignes et des colonnes du même nom, il y a toujours une unité et que les éléments restants de la colonne sont égaux. à zéro.

Vous pouvez donc immédiatement remplir les colonnes x4, x6 Et x7. Il est conseillé de recalculer selon la « règle du triangle ». Afin de calculer n'importe quel coefficient dans la nouvelle version, vous devez trouver trois nombres dans le tableau simplex : le nombre qui remplace ce coefficient dans la version précédente ;

• - un nombre dans la même ligne de l'option précédente, mais dans la colonne de la variable d'entrée ;
• - un nombre qui se trouve dans la nouvelle version dans la même colonne avec le coefficient souhaité, mais dans la ligne de la variable nouvellement saisie (les éléments de cette ligne ont déjà été calculés précédemment).

Les trois nombres du tableau forment un triangle rectangle. Pour déterminer le coefficient recherché, il faut soustraire le produit des deux autres angles du nombre situé au sommet de l'angle droit.

Par exemple, pour column.gr

On fait le calcul :

pour le coefficient par ligne

pour le facteur de ligne x 7 :

Indicateur de ligne Zj - CJ peut être calculé de deux manières :

a) selon la formule

b) selon la règle du « triangle » :

Nous effectuons les calculs de la même manière pour les autres colonnes de la nouvelle version du tableau simplex.

Nous devons maintenant savoir si la deuxième option est optimale ou si elle peut être améliorée. Pour ce faire, regardez la ligne Zj - Cj. S'il contient des nombres négatifs, l'option peut être améliorée.

De 0,3 frotter. pour chaque unité de produit introduite, le profit augmentera une fois entré dans les chiffres de base ! (éd. A) et de 0,1 frotter. lors de l'introduction des numéros 3 (éd. B). Ces chiffres peuvent sembler contredire les données originales : selon lesquelles ed. Et cela rapporte 0,4 roubles. profit, B - 0,5 frotter. Mais le fait est que à ce stade Dans cette tâche, l'introduction de ces produits dans le plan entraînera le déplacement d'un certain nombre de produits précédemment introduits. D, afin de libérer les équipements du groupe I pour leur production.

A l'étape suivante, il est plus approprié d'introduire X ((éd. A), puisqu’il correspond au plus grand nombre négatif en valeur absolue. Semblable à l’option précédente, nous définirons le nombre d’éd. Ou il peut être inclus dans le plan, en tenant compte du fait qu'il contient déjà la sortie d'une publication. D. Pour cela, on divise les nombres de la colonne « plan » par les coefficients correspondants (uniquement positifs) de la colonne de la variable d'entrée X ( et parmi les quotients obtenus on sélectionne le plus petit :

Il s'ensuit que dans nouvelle option pas plus de 4 000 éditions ne peuvent être entrées dans le calcul. Et puisque le facteur limitant est l’équipement du groupe II. Par conséquent, la variable X ( remplacera la variable dans la base x siècle

A l'intersection d'une colonne xx et des cordes x6 nous trouvons et mettons en évidence l'élément guide - 3. Ensuite, nous calculons la chaîne de la variable saisie en divisant les éléments de la chaîne x6 de la version précédente sur l'élément de guidage. Ensuite on calcule la colonne « plan » :

Le bénéfice avec la nouvelle option sera de :

Selon la règle décrite, remplissez les colonnes suivantes. En regardant à travers la ligne Zj - CJ on voit qu'elle ne contient que des zéros et des éléments positifs, ce qui signifie que l'option 3 est la solution optimale et ne peut être améliorée. Il ne comprend que deux types de produits sur quatre. Variable x3 correspond dans la dernière ligne à 0. Cela signifie que l'introduction au plan dans l'étape suivante x3 n'augmentera pas les profits, mais ne les réduira pas non plus, et le résultat qui en résultera sera également optimal. Diviser les nombres de la colonne « plan » par les coefficients de la colonne x3 et en choisissant le minimum parmi ceux obtenus, on détermine que cette variable doit être introduite dans la base à la place de la variable ^. Grâce aux transformations ultérieures, nous obtenons un nouveau plan optimal, qui prévoit la sortie de 2182 éditions. UN (X () et 5455 éd. B (.g3). Trouvons quelques autres options optimales pour résoudre notre problème. Option/ : 50% du premier programme et 50% du deuxième programme :

Option II : 80% du premier programme et 20% du deuxième programme :

Ces options génèrent également un bénéfice de 3 600 RUB.

La présence de plusieurs plans d'efficacité pratiquement égale permet de déterminer un certain nombre d'options intermédiaires, ce qui donne dans les problèmes économiques caractéristiques supplémentaires pour l'analyse et la sélection qualitative des plus acceptables d'entre eux.

Lors de la résolution de problèmes à l'aide de la méthode du simplexe, des cas de « dégénérescence » peuvent survenir. À T restrictions, un plan non dégénéré contient toujours T variables positives, et le reste p-t les variables du problème ne sont pas incluses dans la base et sont égales à zéro. Cependant, il est possible qu'une ou plusieurs des variables incluses dans la base soient égales à zéro, c'est-à-dire la présence d'un ou plusieurs zéros dans la colonne « plan » d'un tableau simplexe. Ce plan s'appelle dégénérer. Avec un plan dégénéré, la présence de nombres négatifs dans la ligne Zj - Cj ne signifie pas que l'option suivante entraînera une augmentation de la valeur de la fonction objectif. Elle peut rester inchangée, et ce pendant non seulement une, mais aussi plusieurs étapes successives. C'est ce qui se passe boucle, ce qui empêche d'autres calculs et ne peut être surmonté qu'à l'aide de techniques spéciales.

Actuellement, lors de la résolution de problèmes d'optimisation, ils sont largement utilisés. Ordinateur personnel. Dans ce cas, le système est utilisé feuilles de calcul "Microsoft Excel».

Pour résoudre des problèmes d'optimisation dans MS Excel utilisez le module complémentaire Rechercher une solution, qui est appelé à partir de l'élément de menu principal « Outils ».

Si en version Exceller installé sur votre ordinateur, ce sous-élément du menu « Service » est manquant, vous devez appeler l'élément de menu « Modules complémentaires » et sélectionner « Rechercher une solution » dans la liste proposée des modules supplémentaires.

Regardons un exemple d'utilisation de ce complément, en l'utilisant pour résoudre le problème de planification de la production.

Exemple 2.24

L'entreprise fabrique les produits A, B, C, D à partir de trois types de ressources. Le modèle mathématique a la forme suivante : check/(X) = 7,5π* 1 +3x2+ 6dg 3 + 12.g 4 (fonction objectif - coût total de production).

Les restrictions sur les réserves de ressources et la non-négativité des variables sont les suivantes :

Créons un modèle dans l'éditeur Exceller.

Maintenant, mettons-le dedans cette tâche informations numériques.

Dans les cellules vides sélectionnées (les valeurs de la fonction objectif et les côtés gauches des inégalités), il est nécessaire de saisir des formules qui affichent les connexions et les relations entre les nombres sur le bureau.

Cellules C 4 - F a sont appelés Exceller variable (dans notre modèle, ce sont des variables inconnues). La recherche d'une solution lors de leur modification permettra de trouver la valeur optimale de la fonction objectif. Les valeurs initialement saisies dans ces cellules sont généralement des zéros (les cellules non remplies sont traitées par défaut comme contenant des valeurs nulles).

Vous devez maintenant saisir les formules. Dans notre modèle mathématique, la fonction objectif est le produit d'un vecteur de coefficients et d'un vecteur d'inconnues. En effet, l'expression peut être considérée

comme le produit du vecteur (7, 5, 3, b, 12) par le vecteur (.g, X 2 , je-*, xA).

DANS Exceller Il existe une fonction SUMPRODUCT qui permet de trouver le produit scalaire des vecteurs. Cette fonction doit être appelée dans la cellule n°5, et les adresses des cellules contenant les coefficients des équations (dans ce cas, C5) doivent être précisées comme vecteurs multipliés : F5), et les cellules dans lesquelles les valeurs seront placées à la suite de la solution x et x 2, x 3, x 4(cellules SA : FA).

Chaque côté gauche de la contrainte est également un produit de deux vecteurs : la ligne correspondante de la matrice de coûts et un vecteur d'inconnues. Expression 2x + x2+ 0Dg 3 + 4x l(pour la première contrainte 2x, +x2 + 0,5x3 + 4 x 4 2400) sera considéré comme le produit d'un vecteur de coefficients (2,1,0,5,4) et d'un vecteur de variables (x et x 2, x 3, x 4).

Dans la cellule réservée à la formule du côté gauche de la première contrainte ((79), on appelle la fonction SUMPRODUCT. Comme adresses des vecteurs multipliés, on rentre l'adresse de la ligne de coefficients C9 : /0 et l'adresse des valeurs des variables C4 : FA.

Dans les quatre cellules restantes de la colonne « Partie gauche », nous saisissons des formules similaires en utilisant la ligne correspondante de la matrice des coûts. Un fragment de l'écran avec les formules saisies ressemble à ceci.

Au moment de l'appel du service « Recherche de solution », les formules des membres gauches des contraintes et la formule de la valeur de la fonction objectif doivent être saisies sur le bureau avec le problème.

Dans le menu « Service », sélectionnez « Rechercher une solution ». Dans la fenêtre qui apparaît, saisissez les informations suivantes :

• a) définir l'adresse de cellule pour la valeur de fonction cible n° 5 comme cellule cible ;
• b) cocher la « case » sur l'option « valeur maximale », puisque dans ce cas la fonction objectif du revenu est soumise à la maximisation ;
• c) l'adresse de la ligne de valeurs des variables C4 est saisie sous forme de cellules modifiables : F4 ;
• d) à droite de la fenêtre destinée à la saisie des restrictions, cliquez sur le bouton « Ajouter », un formulaire de saisie des restrictions apparaîtra ;

e) dans la partie gauche du formulaire « Cell Link », saisissez l'adresse de la formule pour la partie gauche de la première contrainte g 9, le signe d'inégalité requis est sélectionné (dans notre cas,

f) toutes les contraintes de la tâche sont saisies de la même manière, après quoi on appuie sur le bouton « OK ».

La fenêtre « Rechercher une solution » avec les informations saisies ressemble à ceci.

Ensuite, vous devez cliquer sur le bouton « Options », cocher les « cases » Modèle linéaire" et "Valeurs non négatives", puisque dans ce cas le problème concerne la programmation linéaire, et la contrainte nécessite des valeurs non négatives.

Cliquez ensuite sur « OK », « Exécuter », après quoi la fenêtre de résultat de la solution apparaît.

Si, à la suite de toutes les actions, vous recevez une fenêtre avec le message « Solution trouvée », vous avez alors la possibilité de recevoir trois types de rapports, qui sont utiles lors de l'analyse de sensibilité du modèle. DANS dans cet exemple Enregistrez simplement la solution trouvée en cliquant sur « OK ». En conséquence, une solution au problème a été obtenue.

Si, à la suite de la résolution du problème, une fenêtre apparaît avec un message sur l'impossibilité de trouver une solution, cela signifie qu'une erreur a été commise dans la formulation du problème (les formules de contraintes n'ont pas été remplies, le « drapeau » , la maximisation (minimisation), etc. n'a pas été définie correctement).

Dans la fenêtre « Rechercher une solution » se trouve un bouton « Options ».

Cochez la case « Afficher les résultats de l'itération » et cliquez sur « OK ».

Cliquez ensuite sur le bouton « Exécuter ».

MS Excel affichera la fenêtre suivante.

La feuille de travail montrera les résultats de la première itération.

Après cela, cliquez sur le bouton « Continuer », les résultats de la deuxième itération sont affichés sur la feuille de calcul.

Cliquez à nouveau sur le bouton « Continuer » et la feuille de calcul affiche les résultats de la troisième itération.

La prochaine fois que vous cliquerez sur le bouton « Continuer », le programme affichera la fenêtre « Résultats de la recherche de solution », dans laquelle vous devrez enregistrer la solution trouvée et sélectionner le type de rapport.

DANS cette section le format général pour résoudre les problèmes d'optimisation dans Exceller. En fonction de la modèles économiques, effectuez les modifications appropriées.

Les rapports ressemblent à ceci.

1. Rapport sur les résultats.

2. Rapport de durabilité.

3. Rapport sur les limites.

Considérons maintenant un exemple dans lequel le modèle mathématique a la même forme, mais les contraintes ont des signes différents.

Exemple 2.25

L. Disons que le modèle mathématique est le suivant : Il a les restrictions suivantes :

Rapport de durabilité.

B. Supposons maintenant que le modèle mathématique ait d'autres restrictions :

Dans ce cas, nous avons les résultats suivants à partir des rapports.

Rapport de durabilité.

• Pour résoudre le même problème, nous utiliserons l'une des méthodes de programmation linéaire - graphique. Exemple 2.22 Introduisons la notation suivante : x( - le nombre requis de portes DV, x2 - le nombre requis de portes ICE.

La programmation linéaire est considérée comme une réalisation révolutionnaire qui a donné à l'homme la capacité de formuler des objectifs généraux et de trouver, grâce à la méthode du simplexe, des solutions optimales à une large classe de problèmes pratiques de prise de décision d'une grande complexité.

Programmation linéaire– une discipline mathématique consacrée à la théorie et aux méthodes de résolution de problèmes sur les extrema des fonctions linéaires sur les ensembles n-espace vectoriel dimensionnel défini par des systèmes d'équations linéaires et d'inégalités.

On peut dire que programmation linéaire applicable à la résolution de modèles mathématiques de ces processus et systèmes qui peuvent être basés sur l'hypothèse d'une représentation linéaire du monde réel.

Problème de programmation linéaire(LP), consiste à trouver le minimum (ou maximum) d'une fonction linéaire sous contraintes linéaires.

La programmation linéaire est utilisée pour résoudre les problèmes économiques suivants :

1. Le problème de la gestion et de la planification de la production.

2. Problèmes de détermination du placement optimal de l'équipement sur navires de mer, dans les ateliers.

3. Le problème de la détermination du plan optimal de transport de marchandises (problème de transport).

4. Le problème de la répartition optimale du personnel.

5. Problèmes de mélanges, d’alimentation (planification de la composition des produits), etc.

3. MODÈLE DE PROGRAMMATION LINÉAIRE, SA REPRÉSENTATION DANS LES TABLEAUX ÉLECTRONIQUES MS EXCEL.

Traditionnellement, les sciences de gestion font référence à la construction de modèles détaillés, à la suite de l'analyse desquels sont prises les décisions de gestion. Aujourd'hui, des millions de managers utilisent des feuilles de calcul pour analyser les problèmes de leur entreprise. Les feuilles de calcul modernes disposent de nombreux outils puissants qui peuvent être utilisés pour analyser les modèles avec plus de précision, ce qui aboutit à des modèles plus équilibrés et plus proches de l'ajustement. solutions optimales. Avec l'utilisation croissante des feuilles de calcul dans le processus de gestion, les futurs professionnels doivent posséder des compétences en développement de modèles professionnels - comment « planifier » une feuille de travail vierge afin d'obtenir un modèle utile et pratique d'une situation commerciale sans se plonger dans les subtilités algorithmiques et mathématiques. des calculs.

Les principales étapes pour créer un modèle de programmation linéaire dans Excel :

1. Ecrire et tester un modèle de programmation linéaire symbolique. Le modèle est écrit sur papier sous forme mathématique.

2. Création et débogage d'un modèle de programmation linéaire tabulaire. A partir du modèle symbolique du produit médicamenteux, sa représentation est créée dans Excel .

3. Une tentative d'optimisation du modèle à l'aide du module complémentaire SOLUTION SEARCH.

4. UTILISER LE ADD-ON À LA RECHERCHE D'UNE SOLUTION.

À l'aide de feuilles de calcul, vous pouvez simuler des situations réelles et évaluer les résultats. En d'autres termes, à l'aide de feuilles de calcul, vous pouvez analyser les résultats des opérations et prédire les perspectives futures de l'entreprise. Ces tâches dans l'environnement MS Excel permet de résoudre avec le complément Rechercher une solution.

Trouver une solution – Il s'agit d'un module complémentaire conçu pour optimiser les modèles en présence de contraintes. Il se compose de deux composants logiciels : un programme écrit en Visual Basic, qui traduit les informations présentées sur la lettre de travail pour une représentation interne, qui est utilisée par un autre programme. Le deuxième programme se trouve dans la mémoire de l'ordinateur en tant que dossier distinct. module logiciel. Il effectue l'optimisation et renvoie la solution trouvée au premier programme, qui reprend les données de la feuille de calcul. En l'utilisant, vous pouvez trouver la valeur optimale de la formule, qui est stockée dans la cellule cible. Cette procédure fonctionne sur un groupe de cellules directement liées à une formule dans la cellule cible. Pour obtenir un résultat de formule dans une cellule cible, la procédure modifie la valeur dans les cellules qui affectent la recherche. Afin de réduire la pluralité de valeurs utilisées dans le modèle de problème, une contrainte est appliquée. Ces contraintes peuvent contenir une référence à d'autres cellules qui affectent la recherche.

Algorithme général pour travailler avec le complément Trouver une solution.

1. au menu Service sélectionner une équipe Trouver une solution.
2. Sur le terrain Définit la cellule cible Saisissez l'adresse de la cellule contenant la formule pour optimiser le modèle.
3. Pour maximiser la valeur d'une cellule cible en modifiant les valeurs des cellules d'influence, réglez le commutateur sur Valeur maximum. Pour minimiser la valeur de la cellule cible en modifiant les valeurs des cellules d'influence, réglez le commutateur sur Valeur minimum . Pour que la cellule cible acquière la valeur d'un nombre spécifique, placez le commutateur sur la position Signification et entrez le numéro approprié.
4. Sur le terrain Changer de cellule Saisissez les adresses des cellules dont les valeurs changent, en les séparant par des virgules. Les cellules modifiées doivent être directement ou indirectement liées à la cellule cible. Jusqu'à 200 cellules variables peuvent être installées.
5. Sur le terrain Restrictions saisissez toutes les restrictions imposées à la recherche d'une solution.
6. Cliquez sur le bouton Exécuter.
7. Pour enregistrer la solution trouvée, sélectionnez le commutateur dans la boîte de dialogue Résultats de la recherche de solutions positionner Enregistrez la solution trouvée. Pour reprendre les données saisies, réglez le commutateur sur Restaurer les valeurs d'origine.
8. Pour interrompre la recherche d'une solution, appuyez sur la touche Esс. MS Excel recalculera la feuille en tenant compte des valeurs de cellules trouvées qui affectent le résultat.

Algorithme robotique avec Nadbudova Trouver une solution.

5. RÉSOLUTION D'UN PROBLÈME DE PROGRAMMATION LINÉAIRE À L'AIDE D'UN PROGRAMME MS EXCEL.

Exemple. Confiserie pour réaliser trois types de caramel A, B, C utilise trois principaux types de matières premières : le sucre, la mélasse et la purée de fruits. Consommation standard de sucre pour la production de 1 kg de caramel de chaque type, respectivement, niveaux : 0,8 kg ; 0,5 kg ; 0,6kg ; mélasse – 04 kg ; 0,4kg ; 0,3kg ; purée de fruits – 0 kg ; 0,1kg ; 0,1 kg. Les confiseries peuvent être produites en toutes quantités (les ventes sont garanties), mais l'approvisionnement en matières premières est limité : réserves de sucre - 80 kg, mélasse - 60 kg, purée de fruits - 12 kg. Bénéfice de la vente de 1 kg de caramel UN est de 10 UAH, tapez DANS – 11 UAH, tapez AVEC – 12 UAH.

Tableau 1

Déterminez un plan de production de caramel qui garantit un profit maximal des activités de la confiserie.

Les méthodes de programmation linéaire sont utilisées pour résoudre de nombreux problèmes extrêmes souvent traités en économie. Résoudre de tels problèmes revient à trouver les valeurs extrêmes (maximales et minimales) de certaines fonctions de quantités variables.
La programmation linéaire repose sur la résolution d'un système d'équations linéaires (avec transformation en équations et inégalités), lorsque la relation entre les phénomènes étudiés est strictement fonctionnelle. Il se caractérise par une expression mathématique des variables, un certain ordre, une séquence de calculs (algorithme) et une analyse logique. Il ne peut être utilisé que dans les cas où les variables et les facteurs étudiés ont une certitude mathématique et des limites quantitatives, lorsque, à la suite d'une séquence connue de calculs, les facteurs sont interchangeables, lorsqu'il y a une logique dans les calculs, logique mathématique sont combinés avec une compréhension logiquement étayée de l'essence du phénomène étudié.
En utilisant cette méthode dans la production industrielle, par exemple, la productivité globale optimale des machines, des unités, des lignes de production est calculée (pour une gamme de produits donnée et d'autres valeurs données), et le problème de la découpe rationnelle des matériaux est résolu (avec un rendement optimal de pièces à usiner). DANS agriculture il est utilisé pour déterminer le coût minimum des rations alimentaires pour une quantité donnée d'aliments (par type et par nutriments qu'elles contiennent). Le problème du mélange peut également trouver une application dans la production en fonderie (composition de charge métallurgique). La même méthode est utilisée pour résoudre le problème des transports, le problème du rattachement rationnel des entreprises de consommation aux entreprises de production.
Tous les problèmes économiques résolus par programmation linéaire se distinguent par des solutions alternatives et certaines conditions limites. Résoudre un tel problème signifie choisir la meilleure, optimale, parmi toutes les options (alternatives) admissibles. L'importance et la valeur de l'utilisation de la méthode de programmation linéaire en économie sont que l'option optimale est sélectionnée parmi un nombre très important options alternatives. Il est presque impossible de résoudre de tels problèmes par d’autres méthodes.

A titre d'exemple, envisageons de résoudre le problème de l'utilisation rationnelle du temps de fonctionnement des équipements de production.
Conformément au plan opérationnel, la section de rectification a produit au cours de la première semaine de décembre 500 bagues pour roulements de type A, 300 bagues pour roulements de type B et 450 bagues pour roulements de type B. Toutes les bagues ont été rectifiées sur deux machines interchangeables. performances différentes. Le temps machine pour chaque machine est de 5000 minutes. La complexité des opérations (en minutes par anneau) dans la fabrication des différents anneaux est caractérisée par les données suivantes (tableau 6.5).
Tableau 6.5
Il est nécessaire de déterminer l'option optimale pour répartir les opérations entre les machines et le temps qui serait consacré à cette option optimale. Terminons la tâche en utilisant la méthode simplex.
Pour compiler un modèle mathématique de ce problème, nous introduisons ce qui suit symboles: jc, x2, xъ, - respectivement, le nombre de bagues pour roulements de types L, B, V, produites sur la machine I ; x4, x5, x6 - respectivement, le nombre de bagues pour roulements de types A, B, C, produits sur la machine II.
La forme linéaire reflétant le critère d’optimalité ressemblera à :
min a(x) = 4x,-f 10x2-f 10x3-f 6x4-f 8x5+20x6 avec restrictions
4х, -f 10х2 -f 10;t3 lt; 5000
6x4 -f 8x5 -f 20x6 ~lt; 5000
x, = 500
x2 + x5 = 300
x3 + x6 = 450
Xj^0,j=l, ..., 6

Transformons la condition du problème en introduisant des variables supplémentaires (auxiliaires) et fictives. Écrivons la condition comme ceci :
pointe lt;x(x) = 4dg, + 10x2+ 10x3 + 6x4 + 8x5 + 20x6+
+ Mx9 + Mx(0+Mx(,
Un système d'équations reflétant les conditions restrictives du temps informatique et de la quantité de produits fabriqués :
4x, + l(bc2 + 10x3 +x1 = 5000
6x4 + 8x5 + 20x6 + xs = 5000
Xj + x4 + x9 = 500
x2 + x5 + x10 = 300
XJ +X6 + *!1 = 450
-*,^0,7=1, ..., 11
La solution à ce problème est présentée dans le tableau. 6.6. L'option optimale a été obtenue à la septième étape (itération). Si la machine I produisait 125 bagues de roulement de type A, 450 bagues de roulement de type B et que la machine II produisait 375 bagues de roulement de type A et 300 bagues de roulement de type B, alors avec une telle charge d'équipement, 350 minutes de temps machine seraient libéré pour la machine II. Temps total passé sur option optimaleéquivaudrait à 9 650 minutes, alors que 10 000 minutes de temps informatique ont été réellement dépensées.
Un problème très typique résolu par programmation linéaire est le problème du transport. Son objectif est de minimiser la rotation du fret lors de la livraison des biens de consommation du fabricant au consommateur, des entrepôts et bases de gros aux points de vente au détail. Il peut être résolu en utilisant la méthode du simplexe ou la méthode de distribution.
La solution au problème du transport en utilisant la méthode de distribution a été donnée dans la troisième édition du manuel « Theory of Economic Analysis » (« Finance and Statistics », 1996).

Résoudre le problème de l'utilisation rationnelle des machines-outils par la méthode du simplexe

Base	Avec	Ro	4	10	10	6	8	20	0	0	m	m	m
			L	Rg	R.	L	R ъ		Pi	P8	R*	L 0	L,
L	0	5000	4	10	0	0	0	0	і	0	0	0	0
R,	0	5000	0	0	0	6	8	20	0	1	0	0	0
L	m	500	1	0	0	1	0	0	0	0	1	0	0
L 0	m	300	w	0	0	0	1	0	0	0	0	1	0
L.	m	450	0	0	1	0	0	1	0	0	0	0	1
Zj-Cj		1250M	M-4	M-10	M-10	M-6	M-8	M-20	0	0	0	0	0
Pi	0	3000	0	10	10	-4	0	0	0	0	-4	0	0
R*	0	5000	0	0	0	6	8	20	1	1	0	0	0
Ro	4	500	1	0	0	1	0	0	0	0	1	0	0
Lo	m	300	0	1	0	0	w	0	0	0	0	1	0
L.	m	450	0	0	1	0	0	1	0	0	0	0	1
zr-9		750L/+2000	0	M-10	M-10	-2	M-8	À PROPOS 2	0	0	-M + 4	0	0

Base	AVEC	P0	4	Pi	10	6	8	20	0	0	m	m	M.
			Pi	10	^3	je	P5	p6	Pi	R"	p9	Pi 0	RC
Pi	0	3000	0	10	10	-4	0	0	1	0	-4	0	0
R*	0	2600	0	-8	0	6	0	20	0	1	0	-8	0
Pi	4	500	1	0	0	1	0	0	0	0	1	0	0
P5	8	300	0	1	0	0	1	0	0	0	0	1	0
PR	M.	450	0	0	1	0	0	1	0	0	0	0	1
Zj-Cj		450L/+4400	0	-2	M-10	-2	0	M-20	0	0	-M+4	-M+8	0
R.	10	300	0	1	1	4 10	0	0	1 10	0	4 10	0	0
R%	0	2600	0	-8	0	6	0	20	0	1	0	-8	0
Pi	4	500	1	0	0	1	0	0	0	0	1	0	0
P5	8	300	0	1	0	0	1	0	0	0	0	1	0
RC	M.	150	0	-1	0	j4_ 10	0	1	_J_ 10	0	4 10	0	1
zrCj		150L/+7400	0	-M+S	0	- M-6 10	0	M-20	- ~M+1 10	0	-±m 10	- Af+8"	0

Base	Avec	L,	4	10	10	6	8	20	0	0			M.	M.	m
			L	Rg	L	je	PS	p6	Pi	dorloter;			P9	Lo	l.
L	10	300	0	1	1	4	0	0	1		0		4	0	0
						“10			Que				“ 10
p6	20	130	0	4	0	3	0	1	0		1		0	4	0
				~Ї0		10					20			10
je	4	500	1	0	0	1	0	0	0		0		1	0	0
PS	8	300	0	1	0	0	1	0	0		0		0	1	0
R\\	M.	20	0	6	0	1	0	0	1		1		4	4	1
				10		~10			Que		20		Que	10
Zj-Cj		20M+10000	0		0	-m	0	0	m+\		-m+\		--M	-*M	0
				10		10			10	20			10	10
je	10	380	0	14	1	0	0	0	3		2		12	0	0
				10					10		10		10
R%	20	70	0	14	0	0	0	1	3		2		12	16	-3
				10					10		10		10	10
L	4	300	1	6	0	0	0	0	1		1		-3		-10
											2
p5	8	300	0	1	0	0	1	0	0		0		0	1	0
P4	6	200	0	-6	0	1	0	0	-1		1		4	4	10
											’ 2
Z.-Ci		10000	0	0	0	0	0	0	1	1			-M	-M	-m

Base		Léger ;	4	10	10	6	8	20	0	0	m	m	je/
	Ô		L	Rg	ръ	R*	P5	P6	L	Pamper;	p9	L 0	l.
Rg	10	450	0	0	1	0	0	1	0	0
R%	0	350	0	7	0	0	0	5	3 5	1
L	4	125	1	5 2	0	0	0	5 2	1 4	0
PS	8	300	0	1	0	0	1	0	0	0
P4	6	375	0	5 2	0	1	0	5 2	1 4	0
Zj-Cj		9650	0	-7	0	0	0	-5	1 2	0