Tâche programmation linéaire de la forme ax = b où a est la matrice des coefficients, b est le vecteur de contrainte.
Exemple:

Dans chaque problème LP, les valeurs des variables sont recherchées à la condition que :

• ces valeurs satisfaisaient un système équations linéaires ou les inégalités ;
• à ces valeurs, la fonction objectif se tournerait vers un minimum ou un maximum.

Instructions. Sélectionnez le nombre de variables et le nombre de lignes (nombre de contraintes). La solution résultante est enregistrée dans un fichier Word.

Un des méthodes universelles LP est une méthode simplexe, qui peut toutefois être utilisée si le problème LP a une forme canonique.

Définition. Le problème LP a une forme canonique si toutes les contraintes du système sont constituées uniquement d'équations (sauf les inégalités exprimant la non-négativité des variables) et fonction cible doit être minimisé.
Un exemple d'un tel problème LP sous forme canonique est le problème 1 – un problème de transport équilibré avec un système de contraintes (1) et une fonction objectif (2).
Cependant, dans la plupart des problèmes économiques, le système de contraintes comprend le plus souvent initialement non seulement des équations, mais aussi des inégalités.

Déclaration. Tout problème général de LP peut être réduit à Forme canonique.
La réduction du problème LP général à une forme canonique est obtenue en introduisant de nouvelles variables (appelées supplémentaires).
Le système de contraintes (3) de ce problème est constitué de quatre inégalités. En introduisant des variables supplémentaires oui 1 ≥ 0, oui 2 ≥ 0, oui 3 ≥ 0, oui 4 ≥ 0, on peut passer au système de restrictions :

Ces variables supplémentaires oui j'ai une signification économique absolument claire, à savoir la quantité de temps de travail non utilisé (temps d'arrêt de la machine je-ème type).
Par exemple, si les machines du premier type ont fonctionné pendant les 18 heures, alors x + y = 18, donc y 1 = 0. Mais nous admettons la possibilité d'une utilisation incomplète du temps de fonctionnement de la première machine X + oui<18. В этом случае oui 1 prend une valeur positive et peut être considéré comme un délai non utilisé. Par exemple, connaissant la solution à ce problème du paragraphe 3.3.2, X = 12, oui= 6, on peut conclure du système de restrictions (3.9) que oui 1 = oui 2 = oui 3 = 0, et oui 4 = 12 – 6 = 6. Autrement dit, les machines des premier, deuxième et troisième types utilisent entièrement leur temps de travail. Mais la quatrième machine n'est qu'à moitié chargée, 6 heures, et, compte tenu du plan optimal, est inactive. Peut-être qu'après de telles conclusions, le chef d'entreprise voudra-t-il le charger d'autres travaux, le louer pour cette période, etc.
Ainsi, en introduisant des variables supplémentaires, nous pouvons réduire toute contrainte de type inégalité à une équation.

Considérons le problème du mélange. Le système de restrictions a la forme :
Les inégalités ont été tournées vers « plus », donc, en introduisant des variables supplémentaires y 1, y 2, y 3 ≥ 0, elles doivent être soustraites du côté gauche afin de l'égaliser avec le droit. On obtient un système de restrictions sous forme canonique :
Les variables y i auront également un sens économique. Si vous vous souvenez du contenu pratique du problème, alors la variable y 1 signifiera la quantité de substance en excès A dans le mélange, y 2 signifiera la quantité de substance en excès DANS dans le mélange oui 3 – excédent AVEC dans le mélange.
La tâche de trouver la valeur maximale de la fonction objectif peut être réduite à trouver le minimum de la fonction - F en raison de l'évidence de l'énoncé max F = –min (– F). Regardez l'image : si à un moment donné X= X 0 fonction oui= F(X) atteint son maximum, alors la fonction oui= –F(X), symétrique à celui-ci par rapport à l'axe BŒUF, au même moment X 0 atteindra un minimum, et F maximum = – (– F minutes) à X = X 0 .

Conclusion. Pour représenter le problème LP sous forme canonique il faut :

• transformer les inégalités incluses dans le système de contraintes du problème en équations en introduisant des variables supplémentaires ;
• si la fonction objectif F→max (maximise), il est remplacé par la fonction – F→ min (qui est minimisé).

Dans sa formulation originale, le PLP peut permettre diverses formes d'enregistrement. Ainsi, dans certains problèmes, il est nécessaire de maximiser la fonction objectif, dans d'autres, il est nécessaire de la minimiser ; certaines contraintes linéaires peuvent prendre la forme d'égalités, d'autres d'inégalités, etc.

Pour assurer l'uniformité de l'enregistrement des PAP, ce qu'on appelle Forme canonique enregistrements.

Le ZLP est dit écrit sous forme canonique s’il a la forme suivante :

Notons les caractéristiques suivantes de la forme canonique :

1) il est nécessaire de minimiser la fonction objectif ;

2) toutes les restrictions linéaires, à l'exception des exigences de non-négativité des variables, ont la forme d'égalités ;

Des exigences de non-négativité sont imposées à toutes les variables.

Montrons que tout ZLP peut être réduit à une forme canonique.

1) Si dans le ZLP il est nécessaire de maximiser la fonction objectif f, alors nous posons g = - f et nécessitent de minimiser la fonction g. Le résultat sera un nouveau ZLP, équivalent à celui d’origine dans le sens où toute solution optimale au problème initial sera une solution optimale au nouveau problème et vice versa.

2) Supposons que le ZLP ait une contrainte linéaire de la forme

Remplaçons cette restriction par les deux restrictions suivantes :

Où z - une nouvelle variable qui est introduite dans la fonction objectif avec un coefficient de 0 (c'est-à-dire que la variable z n'est pas introduite dans la fonction objectif). La valeur de la variable z peut être ignorée après avoir résolu un nouveau problème.

De même, la contrainte de vue est remplacée par deux contraintes :

3) Supposons que dans le ZLP toutes les variables ne soient pas soumises à l'exigence de non-négativité. Alors chaque variable , qui n'est pas soumis à l'exigence de non-négativité, peut être représenté comme la différence de deux variables non négatives :

Chaque occurrence d'une variable dans la fonction objectif ou les contraintes nous le remplaçons par la différence
. Après avoir résolu le nouveau problème en utilisant (2.6), nous revenons aux variables précédentes.

Grâce à ces techniques, tout ZLP est réduit à une forme canonique.

Exemple. Réduire à la forme canonique

Faisons les étapes décrites.

Nous obtenons maintenant le ZLP sous forme canonique :

2.7. Le concept d'un plan de soutien.

Laissez le VLP être donné sous forme canonique (2.3 - 2.5). Supposons que le système d’équations (2.4) se réduit à la forme Jordan avec des membres droits non négatifs :

(2.6)

Où
.

En assimilant les variables libres à zéro, on obtient la solution de base du système (2.4)

En raison des conditions
l'ensemble des valeurs des variables (2.7) satisfait également aux contraintes (2.5). Donc (2.6) est décision acceptable du PPP.

La solution admissible (2.7) s’appelle base admissible décision ou plan de base du ZLP. Dans ce cas, ils disent que les variables
constituer une base recevable.

Il s'avère que si l'ODR est représenté géométriquement, alors chaque plan de support du ZLP correspond au sommet du polyèdre. Le théorème suivant est donc vrai.

Si le ZLP peut être résolu, alors il existe un plan de support optimal.

3. Méthode simplex pour résoudre des problèmes

3.1. Caractéristiques générales et 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. Pour presque tous les ordinateurs, des programmes standard ont été développés pour résoudre des problèmes à l'aide de la méthode simplex.

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 parcourt pas tous les plans de référence (ce qui serait souvent impossible en raison de leur grand nombre), mais, à partir d'un plan de référence initial, elle 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.

À décision du PPP La méthode du simplexe peut être utilisée pour distinguer les étapes suivantes :

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.

Tâches du député

Le ZLP général s'appelle <,=,>=)bi (i=1,n) (2) soumis à xj>

Symétrique < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > Canonique mixte.

min f(x) = -max(-f(x))

<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>

Interprétation géométrique de la fonction objectif et des contraintes du ZLP. Formulation géométrique du ZLP.

Soit le problème f=c1x1+c2x2-max (1)

a11x1+a12x2<=b1 }

am1x1+am2x2<=bm}

x1>=0, x2>=0 (3)

Le plan du problème (x1,x2) est un point du plan. Chaque inégalité a-nous 2 représentations. est un demi-plan. Un demi-plan est un ensemble convexe. Convexe est appelé un ensemble dans lequel les points du segment de connexion (x1 et x2) appartenant à cet ensemble appartiennent également à l'ensemble. C-ma 2 représente l'intersection de demi-plans. En traversant, vous pouvez obtenir :

1) zone fermée polygonale convexe.

2) zone polygonale ouverte convexe

3) point unique

4) ensemble vide

5) poutre et segment

Interprétation géométrique de la fonction objectif : La fonction 1 est une famille de droites parallèles, appelées lignes de niveau (lignes de valeur constante de la fonction objectif). Les dérivées partielles de la fonction par rapport à x1 et x2 montrent le taux d'augmentation de la fonction objectif le long des coordonnées des axes. Vecteur de dégradé montre la direction de l'augmentation la plus rapide de la fonction objectif. Pour les problèmes 1-3, le vecteur gradient = (c1; c2) quitte le point (0,0) et est dirigé vers le point de coordonnées (c1; c2). Le vecteur gradient est perpendiculaire aux lignes de niveau. L'intersection des demi-plans est généralement appelée zone de solutions admissibles (ADD).

Le théorème principal de LP. Diagramme schématique solution du ZLP, qui découle de ce théorème.

Si le ZLP a une solution, alors la fonction objectif atteint une valeur extrême en au moins un des points extrêmes du polyèdre plan. Si la fonction objectif atteint une valeur extrême en plus d’un point extrême, alors elle atteint une seule et même valeur, qui est une combinaison linéaire convexe de celles-ci, en tout point. Lors de la résolution manuelle de ZLP, il est pratique d'utiliser une entrée tabulaire.

PA		SP -Xm+1 -Xm+2 -Xn
x1	b1o	b11 b12 b1n-m
x2	b2o	b21 b22 b2n-m
xm	bm	bm1 bm2 bmn-m
F	huer	bo1 bo2 bon-m

Algorithme de la méthode simplexe.

1. amener le modèle de problème sous forme canonique ;

2. retrouver le plan de référence initial ;

3. écrivez le problème sous une forme simple. tableau;

5. passer à un nouveau plan de référence, à un nouveau symp. tableau. Pour passer à un nouveau plan de référence, il suffit de remplacer une variable de base par une variable gratuite. La variable incluse dans la base et la colonne de résolution correspondante sont déterminées par le plus grand élément négatif absolu de la ligne f. La variable qui exclut de la base et la ligne de résolution correspondante sont déterminées par le plus petit rapport simplexe, c'est-à-dire la relation des éléments de la colonne unité avec l'élément correspondant de la colonne résolution. Le rapport simplex est une quantité non négative. À l'intersection de la ligne de résolution et de la colonne de résolution se trouve un élément de résolution par rapport auquel la transformation simplexe est effectuée de la manière suivante. règle : 1. les éléments de la chaîne d'autorisation sont divisés en éléments d'autorisation ; 2. les éléments de la colonne de résolution sont divisés en éléments de résolution et changent de signe en opposé ; 3. les éléments restants du tableau sont réorganisés selon la règle du rectangle :

bij bis bkj=(bkj*bis-bij*bks)/bi

Le deuxième théorème de la dualité.

si l'un des problèmes duaux a un plan optimal, alors l'autre peut également être résolu, c'est-à-dire a un plan optique. Dans ce cas, les valeurs extrêmes des fonctions objectifs coïncident (j=de 1 à n) Σcjxj*= (i=de 1 à m)Σbiyi* si dans l'original. problème, la fonction objectif est illimitée sur l’ensemble des plans, puis dans double problème le système de restrictions est incohérent.

Théorème sur le rang de la matrice TK.

Le rang de la matrice A du problème de transport est inférieur de un au nombre d'équations : r(A)=m+n-1.

39. Algorithme de construction du plan de référence initial du ZLP.

Pour retrouver le plan de référence initial, nous pouvons suggérer ce qui suit algorithme:

1. écrire le problème sous la forme d'un tableau de Jordan afin que tous les éléments de la colonne des termes libres soient non négatifs, c'est-à-dire l'inégalité aio>=0 (i=1,m) était satisfaite. Les équations dans lesquelles les termes libres sont négatifs sont d'abord multipliées par -1.

		-x1….. -xn
0=	a1o	a11…. a1n
…..	…..	………………………..
0=	mon ami	am1…..amn
f=		-c1…. -cn

Transformez le tableau en utilisant les étapes d'élimination de Jordan, en remplaçant les zéros dans la colonne de gauche par le x correspondant. En même temps, à chaque étape permissif peut être sélectionné toute colonne contenant au moins un élément positif. La ligne de résolution est déterminée par le plus petit des rapports des termes libres aux éléments positifs correspondants de la colonne de résolution. Si, au cours du processus d'élimination, une ligne 0 est rencontrée, dont tous les éléments sont nuls et que le terme libre est non nul, alors le système d'équations de contraintes n'a pas de solutions. Si nous rencontrons une ligne 0 dans laquelle, hormis le terme libre, il n'y a pas d'autres éléments positifs, alors l'ensemble des équations restrictives n'a pas de solutions non négatives. articulation, puis après un certain nombre d'étapes, tous les zéros de la colonne de gauche seront remplacés par x et obtiendrons ainsi une certaine base, et, par conséquent, un plan de référence correspondant.

40. Algorithme de construction du plan de référence optimal du ZLP.

Le plan de soutien initial de Ho est examiné pour déterminer son optimalité.

S'il n'y a pas d'éléments négatifs dans la ligne f (sans compter le terme libre), le -plan est optimal. S'il n'y a pas non plus d'éléments nuls dans la ligne f, alors il n'y a qu'un seul plan optimal ; si parmi les éléments il y a au moins un zéro, alors il existe un nombre infini de plans optimaux. S'il y a au moins un élément négatif dans la ligne f et qu'il n'y a aucun élément positif dans la colonne correspondante, alors la fonction objectif n'est pas limitée dans zone valide. Le problème est insoluble. S'il y a au moins un élément négatif dans la ligne f et que dans chaque colonne contenant un tel élément il y a au moins un élément positif, vous pouvez alors passer à un nouveau plan de référence plus proche du plan optimal. Pour ce faire, la colonne avec un élément négatif dans la ligne f est considérée comme permissif; Ils déterminent la chaîne de résolution à partir de la relation simplex minimale et effectuent l'étape d'élimination de Jordan. Le plan de référence résultant est à nouveau examiné pour déterminer son optimalité. Ceci est répété jusqu'à ce que le plan de référence optimal soit trouvé ou que l'insolvabilité du problème soit établie.

Algorithme de la méthode Gomori.

1. En utilisant la méthode du simplexe, le plan optimal pour le problème est trouvé. Si tous les composants plan optimal dans son ensemble, alors il est optimal. DANS sinon allez au point 2

2. Parmi les composantes non entières, vous devez sélectionner celle dont la partie fractionnaire est la plus grande et, à l'aide de la ligne correspondante du tableau simplex, formuler la coupure correcte à l'aide de la formule

(n-m,s=1)∑ (αkm+1)Xm+1≥(βk)

3. Transformez l'inégalité formulée en une égalité nulle équivalente et incluez-la dans un tableau simplexe avec un plan optimal non entier

4. Le problème étendu qui en résulte est résolu à l’aide de la méthode du simplexe. Si le plan obtenu n'est pas un nombre entier, passez à l'étape 2.

Si pendant le processus de résolution, une ligne apparaît avec un terme libre non entier et d'autres coefficients entiers, alors l'équation correspondante n'a pas de solution en nombres entiers. Dans ce cas, le problème initial est également insoluble en nombres entiers. La méthode de Gomori a une application limitée. Avec son aide, il est conseillé de résoudre de petits problèmes, car... le nombre d'interactions peut être très important.

Différentes formes Enregistrements ZLP (généraux, canoniques, symétriques)

Tâches du député: détermination du plan optimal, détermination du volume optimal de production, détermination de la combinaison optimale de cultures, formation de l'ensemble optimal d'actifs, maximisation des profits bancaires, etc.

Le ZLP général s'appelle problème de maximisation (minimisation) fonction linéaire f=Σcj*xj-max(min) (1) sous restrictions linéaires ∑aij *xj(=<,=,>=)bi (i=1,n) (2) à condition que xj>=0(j=1,n1), xj-arbitraire (j=n1+1,n)(3) où cj,aij, nombres bi-constants .

Symétrique La forme d'écriture du ZLP est appelée problème de maximisation de la fonction (1) sous contraintes linéaires dans les inégalités signées< либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком >ou = et variables non négatives. Canonique La forme d'écriture du ZLP est appelée le problème de la fonction maximum (1) sous contraintes linéaires d'égalités et de variables non négatives. Toute autre forme est appelée mixte.

min f(x) = -max(-f(x))

La transformation d'une inégalité en équation et vice versa s'effectue à partir du lemme : pour toute solution x1...xn de l'inégalité a1x1+...+anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) et vice versa. Chaque solution x1…xn,xn+1 de l’équation 6 et de l’inégalité 7 correspond à une solution x1…xn de l’inégalité 5.

Pour passer du formulaire back sim au formulaire back canonique, vous devez saisir équilibrer (égaliser) les variables. Ceci est basé sur le théorème des inégalités : toute inégalité peut être représentée comme une équation ou une simple inégalité.

: Problèmes de programmation linéaire (LPP)

1. Programmation linéaire

2. Types de problèmes de programmation linéaire

3. Formulaires d'enregistrement des PAP

4. Forme canonique des problèmes de programmation linéaire

Programmation linéaire

La programmation linéaire est une branche de la programmation mathématique utilisée pour développer des méthodes permettant de trouver un extremum. fonctions linéaires plusieurs variables avec des restrictions supplémentaires linéaires imposées aux variables.

En fonction du type de problèmes qu'elles résolvent, les méthodes LP sont divisées en universelles et spéciales. Grâce à des méthodes universelles, tous les problèmes de programmation linéaire (LPP) peuvent être résolus. Les modèles spéciaux prennent en compte les caractéristiques du modèle de problème, sa fonction objective et son système de contraintes.

La principale caractéristique des problèmes de programmation linéaire est que l’extremum de la fonction objectif se trouve à la limite de la région des solutions réalisables.

Figure 1 - Extremum de la fonction objectif

Le modèle mathématique du ZLP s’écrit comme suit :

max (ou min) Z=z(X),(1)

L'ODR peut être représenté par un système d'équations linéaires ou d'inégalités.

Le vecteur X = (x 1, x 2, .... x p) est un vecteur de contrôle ou un effet de contrôle.

Un plan admissible X, dans lequel le critère d'optimalité Z=z(X) atteint une valeur extrême, est dit optimal et est noté X*, la valeur extrême de la fonction objectif par Z*=z(X*).

Types de problèmes de programmation linéaire

Les méthodes de programmation linéaire sont largement utilisées dans les entreprises industrielles pour optimiser le programme de production, le répartir dans les ateliers et dans les intervalles de temps, lors du chargement des assortiments d'équipements, de la planification des flux de marchandises, de la détermination du plan de chiffre d'affaires, etc.

Le type de tâches le plus courant est tâche utilisation optimale ressources. Supposons qu'une unité de production (atelier, entreprise, association, etc.), en fonction des conditions du marché, des capacités techniques et des ressources disponibles, soit capable de produire n divers types produits connus sous les numéros j.

Lors de la production de produits, l'entreprise est limitée par les ressources disponibles, dont la quantité sera notée m, et le vecteur de ressources B = (b 1, b 2, ..., b t). Des coefficients technologiques a ij sont également connus, qui montrent le taux de consommation de la ième ressource pour la production d'une unité du j-ième produit. Efficacité de sortie de l'unité produits j-i caractérisé par le profit p j .

Il est nécessaire de déterminer le plan de production X = (x 1, x 2, ..., x p), maximisant le profit de l'entreprise avec des ressources données.

La fonction objectif ressemble à ceci

sous restrictions

Souvent la gamme de produits est établie par une organisation supérieure, c'est-à-dire ses volumes doivent être contenus dans certaines limites D en j et D en j : alors la restriction suivante est fixée :

Le modèle du problème de l'utilisation optimale des ressources sous-tend modèles d'optimisation du programme de production annuel de l'entreprise. Le modèle inclut des restrictions sur la durée de fonctionnement des équipements.

En gardant la même notation, on écrit respectivement par b j et c j le prix de vente et les coûts unitaires jième produits. Les critères suivants peuvent être considérés comme critères d’optimalité :

1) profit maximum

2) coûts de production minimaux

3) production maximale en termes de valeur (revenus des ventes de produits)

Exemple. L'entreprise peut fabriquer quatre types de produits 1, 2, 3 et 4. Les ventes de tout volume sont garanties. Au cours du trimestre, l'entreprise dispose d'un effectif de 100 équipes, de produits semi-finis pesant 260 kg et d'un équipement de machines de 370 équipes. Les taux de consommation de ressources et le profit par unité de chaque type de produit sont présentés dans le tableau 1.

Nécessaire:

a) maquiller modèle mathématique la tâche de déterminer un plan de production qui permettra d'atteindre un profit maximum ;

b) résoudre le problème de l'exigence d'emballage afin que le nombre d'unités du troisième produit soit 3 fois plus de quantité les unités en premier ;

c) découvrir l'assortiment optimal pour conditions additionnelles: produire au moins 25 unités du premier produit, pas plus de 30 unités du troisième, et le deuxième et le quatrième dans un rapport de 1:3.

Tableau 1

Donnée initiale

Modèle mathématique du problème :

fonction objectif :

max : Z=40x 1 +50x 2 +100x 3 +80x 4

avec restrictions :

a) pour les ressources en main-d'œuvre :

2,5x 1 +2,5x 2 +2x 3 +1,5x 4 ? 100 ;

pour les produits semi-finis :

4x1 +10x2 +4x3 +6x4 ? 260 ;

pour les machines-outils :

8x1 +7x2 +4x3 +10x4 ? 370 ;

condition de non-négativité :

b) l'exigence supplémentaire pour la configuration sera exprimée par la condition

3x 1 =x 3, soit 3x 1 x 3 =0 ;

c) présentons les conditions aux limites et la condition de configuration comme suit : x 1 ? 25,

x 3?30, 3*x 2 = x 4.

Le problème de la passation des commandes ou du chargement de groupes d'équipements interchangeables. Il s'agit de la répartition des commandes entre m (i=1,..., m) entreprises (magasins, machines, interprètes) ayant des caractéristiques de production et technologiques différentes, mais interchangeables en termes d'exécution des commandes. Il est nécessaire d'établir un plan de passation des commandes dans lequel la tâche serait accomplie et l'indicateur d'efficacité atteindrait une valeur extrême.

Formulons le problème mathématiquement. Supposons que n types de produits doivent être fabriqués à l’aide de m groupes homogènes d’équipements. Plan de production pour chaque type de produit certaine période donné par l'ensemble x j (j=1,2, …n). La puissance de chaque type d'équipement est limitée et égale à b i. La matrice technologique A=||a ij || est connue, où a ij est le nombre d'unités du j-ième produit produites par unité de temps pour i-ième équipement. La matrice C est une matrice de coûts, où c ij sont les coûts associés à la production jèmes unités produits sur le i-ième équipement. X est un vecteur du volume de sortie.

Le modèle de problème prendra la forme suivante :

fonction objectif - minimiser les coûts de mise en œuvre de toutes les commandes

avec restrictions :

a) par puissance de l'équipement

b) pour la production

c) condition de non-négativité

Ce problème est appelé problème distributif ou de distribution.

Si pour certains types de produits le plan peut être dépassé, alors la limitation (b) prendra la forme

Les éléments suivants peuvent également être considérés comme bénéfice cible :

a) profit maximum

b) coût minimum du temps machine

Parce que Tout modèle contient des prémisses simplificatrices ; pour l'application correcte des résultats obtenus, une compréhension claire de l'essence de ces simplifications est nécessaire, ce qui permet finalement de tirer une conclusion sur leur admissibilité ou leur inadmissibilité. La simplification la plus significative des modèles considérés est l'hypothèse d'une relation directement proportionnelle (linéaire) entre les volumes de consommation de ressources et les volumes de production, qui est spécifiée à l'aide de normes de coût a ij . Évidemment, cette hypothèse n’est pas toujours vérifiée. Ainsi, les volumes de consommation de nombreuses ressources (par exemple, les immobilisations) changent brusquement - en fonction des changements dans le programme de production X. D'autres prémisses simplificatrices incluent des hypothèses sur l'indépendance des prix j des volumes x j, qui n'est valable que pour certaines limites de leur changement. Il est également important de connaître ces points « vulnérables » car ils indiquent des orientations fondamentales pour améliorer le modèle.

Formulaires d'enregistrement PAP

Il existe 3 formes d'enregistrement du PAP :

1) sous forme de fonctions

max(ou min)Z=,max(ou min)Z=,

2) forme vectorielle

(produit scalaire de vecteurs)

sous restrictions

A 1 x 1 +A 2 x 2 +..+A n x n = B

Où sont les vecteurs

C = (C 1, C 2 .. C n), X = (X 1, X 2 .. X n), et.

3) forme matricielle

sous restrictions

où C = (c 1, c 2,...c n),

Forme canonique des problèmes de programmation linéaire

Si toutes les contraintes d'un problème de programmation linéaire sont des équations et que des conditions de non-négativité sont imposées à toutes les variables x j, alors on parle de problème de programmation linéaire sous forme canonique ou problème canonique programmation linéaire (LLP).

sous restrictions

Pour passer du ZLP au CLLP, il faut passer des restrictions d'inégalité aux restrictions d'égalité et remplacer les variables qui n'obéissent pas aux conditions de non-négativité.

Règles pour amener ZLP sous forme canonique :

1) s'il y a des restrictions partie droite négatif, alors cette limite doit être multipliée par -1 ;

2) 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 ;

3) si une variable xk n'a aucune restriction de signe, alors elle est remplacée dans la fonction objectif et dans toutes les restrictions par la différence entre deux nouvelles variables non négatives : xk=x * k - xl, où l est l'indice récapitulatif, x * k>=, xl >=0.

Regardons un exemple. Ramenons-le à la forme canonique :

Introduisons les variables de nivellement x 4, x 5, x 6 dans chaque équation du système de contraintes. Le système s'écrira sous forme d'égalités, et dans les première et troisième équations du système de restrictions, les variables x 4, x 6 sont inscrites à gauche avec le signe « + », et dans la deuxième équation x 5 est saisi avec le signe « - ».

Les termes libres à la forme canonique doivent être positifs ; pour cela, multipliez les deux dernières équations par -1 :

Dans la forme canonique d'écriture de problèmes de programmation linéaire, toutes les variables incluses dans le système de contraintes doivent être non négatives. Supposons que

En substituant cette expression dans le système de contraintes et la fonction objectif et en écrivant les variables par ordre d'index croissant, on obtient un problème de programmation linéaire présenté sous forme canonique :

optimisation programmation linéaire simplexe