Modèles mathématiques linéaires. Modèles mathématiques de problèmes de programmation linéaire Vue générale du modèle de programmation linéaire

Etablissement public d'enseignement supérieur

enseignement professionnel

"Université technique d'État de Moscou nommée d'après N.E. Bauman"

Succursale de Kalouga

"Résolution du problème de la programmation linéaire par la méthode du simplexe"

Le but du travail: étudier et apprendre à mettre en pratique le simplexe - une méthode de résolution des problèmes directs et duaux de la programmation linéaire

Partie théorique.

Formulation mathématique du problème de programmation linéaire.

Il résulte de l'habitude de considérer des problèmes de programmation mathématique qu'il est presque impossible de les résoudre en termes généraux. Il est conseillé de considérer des classes (types) de problèmes distincts. Pour chacune de ces classes, il est possible de formuler un algorithme de solution qui n'est acceptable que pour cette classe de problèmes. Les plus développés en programmation mathématique sont les problèmes de programmation linéaire (LP).

Dans les problèmes de programmation linéaire, la fonction objectif est linéaire et les conditions de contrainte contiennent des égalités linéaires et des inégalités linéaires. Les variables peuvent ou non être soumises à l'exigence de non-négativité. Le même problème de programmation linéaire peut être écrit sous différentes formes. Si toutes les contraintes sont sous forme d'inégalités, alors le problème est écrit sous forme standard. Si toutes ses limitations sauf

sont des égalités, alors le problème de programmation linéaire est écrit sous forme canonique.

,

Restrictions :

1. Les bonnes parties de toutes les contraintes doivent être non négatives . Si l'un des coefficients< 0, то необходимо коэффициенты ограничения слева и справа домножить на "-1" и изменить знак данного ограничения на противоположный;

2. Toutes les restrictions doivent être présentées sous la forme d'égalités, par conséquent, lors du passage de l'inégalité à l'égalité, l'appareil de variables supplémentaires est utilisé.

Si les contraintes initiales déterminent la consommation d'une ressource (le signe ""), alors les variables doit être interprété comme le reste ou la partie inutilisée de la ressource. Dans ce cas, c'est la variable résiduelle et elle est entrée dans l'équation avec le signe "+".

Si les contraintes initiales définissent un excès d'une ressource (signe ""), alors une variable d'excès est introduite signe "-".

Variable :

Toutes les variables doivent être non négatives, c'est-à-dire .

Si une variable n'a pas de limitation de signe, alors elle doit être représentée comme la différence de deux variables non négatives : , où . Une telle substitution doit être utilisée dans toutes les contraintes contenant cette variable, ainsi que dans l'expression de la fonction objectif.

Si une telle variable tombe dans la solution optimale, alors

Fonction cible :

A maximiser ou à minimiser.

Le système de restrictions sous forme d'égalités et d'inégalités forme un ensemble convexe - un polyèdre convexe. Cet ensemble peut être limité ou illimité. La fonction objectif d'un problème de programmation linéaire est également une fonction convexe. Ainsi, le problème de programmation linéaire est un cas particulier du problème de programmation convexe.

Considérons le système de contraintes pour un problème de programmation linéaire sous forme d'égalités

(1)

Le système (1) d'équations linéaires est cohérent s'il admet au moins une solution. Le système (1) est dit redondant si l'une des équations peut être exprimée comme une combinaison linéaire des autres.

Dans le système (1), le nombre de variables (n inconnues) est supérieur au nombre de restrictions m. On supposera que le rang de ce système est égal à m (le système est non redondant) et que le système (1) est cohérent. Alors m variables à partir de leur nombre total forment des variables de base, et les autres variables sont dites non fondamentales.Si un système d'équations a une solution, alors il a aussi une solution de base.Une solution au système d'équations (1) est dit admissible si toutes ses composantes sont non négatives. Si un système d'équations linéaires a une solution admissible, alors il a aussi une solution admissible de base. de toutes les solutions possibles du système (1) est un ensemble convexe, c'est-à-dire l'ensemble des solutions du problème de programmation linéaire est convexe. Puisque cet ensemble est formé de plans (hyperplans), il a la forme d'un polyèdre convexe. La solution réalisable de base correspond au point extrême du polyèdre convexe (ses faces ou sommet) S'il y a existe une solution optimale à un problème de programmation linéaire, alors il existe une base est la solution optimale.

La fonction objectif d'un problème de programmation linéaire est l'équation d'un plan (ou d'un hyperplan pour plus de trois variables). La fonction objectif d'un problème de programmation linéaire atteint sa valeur maximale ou minimale soit au sommet d'un polyèdre convexe, soit sur l'une de ses faces. Ainsi, la solution (les solutions) du problème de programmation linéaire se situe aux sommets du polyèdre convexe, et pour la trouver, il faut calculer les valeurs de la fonction objectif aux sommets du polyèdre convexe déterminées par les conditions -limitations du problème.

Résolution d'un problème de programmation linéaire par une méthode graphique.

La difficulté de construire un modèle mathématique réside dans l'identification des variables et la représentation ultérieure de l'objectif et des contraintes sous la forme de fonctions mathématiques de ces variables. Si le modèle ne contient que deux variables, le problème de programmation linéaire peut être résolu graphiquement. Dans le cas de trois variables, la solution graphique devient moins visuelle, et avec une plus grande valeur des variables, elle est même impossible. Cependant, la solution graphique permet de tirer des conclusions qui servent de base au développement d'une méthode générale de résolution d'un problème de programmation linéaire.

La première étape de l'utilisation de la méthode graphique consiste à représenter géométriquement les solutions réalisables, c'est-à-dire construction du domaine des solutions admissibles (ODD.), dans lequel toutes les contraintes du modèle sont simultanément satisfaites. Lorsqu'une solution graphique est obtenue, la variable est tracée le long de l'axe horizontal, et - le long de l'axe vertical. Lors de la formation du SDE, il est nécessaire d'empêcher la réception de solutions inacceptables associées à la nécessité de remplir la condition de non-négativité des variables. Avant la construction, il est nécessaire de déterminer les quadrants dans lesquels l'ODR sera situé. Les quadrants sont définis par les signes des variables et . Les conditions de non-négativité des variables et limitent la plage de leurs valeurs admissibles au premier quadrant. Si la variable n'est pas limitée en signe, alors la zone est limitée par les premier et deuxième quadrants, si , alors – par les premier et quatrième quadrants. Les autres frontières de l'espace des solutions sur le plan , sont matérialisées par des droites construites selon les équations de contraintes, à condition de remplacer le signe par le signe "=". Dans ce cas, les éléments suivants doivent être pris en compte : les membres droits de toutes les contraintes doivent être non négatifs . Si une restriction< 0, то необходимо коэффициенты соответствующего ограничения слева и справа до-множить на "-1" и изменить знак неравенства данного ограничения на противоположный. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных.

À la suite des constructions, un polygone est obtenu, qui détermine l'espace des solutions. Si l'une des restrictions a le signe "=", alors l'ODD dégénère en un segment.

En chaque point appartenant à l'aire ou aux limites du polygone de solution, toutes les contraintes sont satisfaites, donc toutes les solutions correspondant à ces points sont valides. L'espace des solutions contient un nombre infini de tels points, malgré cela, il est possible de trouver la solution optimale. Pour cela, il faut construire dans le plan des variables , le gradient de la fonction objectif. La détermination du point optimal dépend du problème à résoudre.

Si un problème de maximisation est défini dans la fonction objectif, alors le point optimal sera situé dans le sens de l'augmentation du gradient ; si le problème de minimisation est défini, alors dans le sens de la diminution du gradient de la fonction objectif. Pour déterminer le point optimal, nous allons déplacer la fonction objectif dans le sens d'augmentation (diminution) du gradient jusqu'à ce qu'elle se déplace vers la région des solutions inacceptables.

Après avoir trouvé le point optimal dans l'espace de solution, ses coordonnées et la valeur de la fonction objectif dans celui-ci sont déterminées. L'exactitude du choix du point optimal peut être vérifiée en calculant la fonction objectif aux sommets du polyèdre solution. Dans LLP, le domaine des solutions réalisables est toujours un ensemble convexe, c'est-à-dire un ensemble tel que, avec deux points quelconques appartenant à cet ensemble, le segment reliant ces deux points appartient également au même ensemble. Toute fonction croît de la manière la plus rapide dans le sens de son gradient.

Résolution d'un problème de programmation linéaire par la méthode du simplexe.

tâche directe.

Considérons un problème de programmation linéaire sous forme canonique :

Trouver le maximum (minimum) d'une fonction sous conditions

On suppose qu'il existe une solution à ce problème. Pour trouver la solution optimale, il est nécessaire de trouver des solutions de base admissibles et d'en choisir la solution de base optimale.

La méthode du simplexe est une méthode algébrique de résolution de problèmes de programmation linéaire. Au cours des calculs, les sommets du polyèdre solution (ODP) sont contournés séquentiellement avec une vérification des conditions d'optimalité à chaque sommet. De plus, chaque transition vers un sommet adjacent s'accompagne d'une amélioration de la fonction objectif.

Procédures de calcul de la méthode du simplexe.

Avec la méthode graphique de résolution du LLP, la solution optimale correspond toujours à l'un des points d'angle (extrêmes) de l'espace des solutions. Ce résultat sous-tend la construction de la méthode du simplexe. La méthode du simplexe n'a pas la visibilité d'une représentation géométrique de l'espace des solutions.

La méthode du simplexe met en œuvre un processus ordonné dans lequel, à partir d'un point d'angle admissible initial, des transitions successives sont effectuées d'un point extrême admissible à un autre jusqu'à ce qu'un point de solution optimale soit trouvé.

Notons : - le nombre total de variables du LLP, présenté sous forme canonique ; - nombre de variables initiales ; - le nombre de restrictions, - le nombre de variables supplémentaires, puis .

Chaque sommet du polyèdre solution a - des variables non nulles et () - des variables nulles.

Les variables non nulles sont dites basiques, les variables nulles sont dites non basiques.

Nous complétons le système d'égalités avec l'égalité de la fonction objectif, tout en supposant qu'il s'agit d'une variable de base toujours présente dans la base de tout sommet.

Pour obtenir une solution, une base admissible initiale est établie, dans laquelle les variables de base doivent être représentées sous forme de vecteurs unitaires. Cela signifie que les équations représentant un sommet donné doivent inclure chaque variable de base dans une seule ligne avec un facteur de 1.

Lors du choix d'une base initiale acceptable pour l'élaboration d'un tableau simplexe, à la première étape CT(0), les variables initiales sont égales à zéro et ne sont pas de base, parmi les variables supplémentaires introduites, les variables à coefficients égaux à un sont sélectionnées. Les variables en égalités (2) - (4) sont basiques et entrent dans la ligne - avec des coefficients égaux à 0. Pour remplir le tableau du simplexe, il faut convertir la fonction objectif sous la forme . Ainsi, on obtient finalement :

Lors de la compilation d'un tableau simplex, les règles suivantes sont suivies :

la colonne la plus à gauche contient les variables de base et ;

la colonne la plus à droite contient les bonnes parties des restrictions ;

La première ligne contient les variables dans un ordre spécifique :

d'abord, puis les variables non fondamentales, les variables de base sont situées dans les dernières colonnes avant le côté droit (IF). On écrit les coefficients dans CT(0) :

L'optimalité de l'un des sommets est déterminée par les coefficients des variables non fondamentales dans la ligne du tableau simplex actuel :

Pour le problème de maximisation, ce sommet est optimal si tous les coefficients des variables non fondamentales de la ligne – sont non négatifs (>0);

Pour le problème de minimisation, ce sommet est optimal si tous les coefficients des variables non fondamentales de la ligne - ne sont pas positifs (< 0).

Si dans le problème de maximisation (minimisation) une variable non fondamentale de la ligne - a un coefficient<0(>0), alors le point courant n'est pas optimal et il faut changer de base. Pour ce faire, choisissez une variable non fondamentale qui a le coefficient le plus négatif (positif) dans la ligne -. La variable non fondamentale sélectionnée sera incluse dans la nouvelle base, elle est donc appelée la variable incluse. La variable de base qui sera extraite de la base est appelée variable d'exclusion.

La variable exclue sera la variable de base qui passera d'abord à "0" lors du déplacement vers un sommet adjacent après avoir entré la variable incluse.

La colonne de la variable incluse sera appelée la colonne de résolution.

La chaîne de la variable exclue sera appelée la chaîne de résolution.

L'intersection d'une colonne permissive et d'une ligne définit un élément permissif (RE).

Pour définir une variable exclue :

divisez les parties droites de toutes les variables de base (à l'exception de la ligne) par les coefficients positifs correspondants de la colonne de résolution ;

choisir le plus petit des rapports obtenus.

La division par "0" et une valeur négative n'est pas autorisée, car cela conduit à l'absence d'un sommet d'intersection ou à un sommet en dehors de l'ODT.

Pour se déplacer vers un sommet adjacent, il est nécessaire de former une matrice de transition B(0), qui déterminera la relation entre ST(0) et ST(1) : ST(1) = B(0) ST(0).

Pour une matrice carrée arbitraire de dimension n, qui a des orts unitaires sous forme de (n - 1) colonnes, disposées conformément aux orts unitaires de la matrice d'identité, et une colonne arbitraire avec un élément non nul sur la diagonale principale, l'inverse matrice est trouvée par la règle suivante :

Chaque élément de la colonne j est divisé par RE et change de signe en l'opposé, à l'exception de l'élément de résolution.

Base initiale artificielle. M - méthode.

Si la contrainte initiale est écrite sous la forme d'égalité "=" ou a le signe "", alors il est impossible d'obtenir immédiatement une solution de base initiale acceptable, car lors de l'écriture du problème sous la forme standard, après avoir introduit des variables supplémentaires, un variante peut s'avérer lorsque les équations résultantes ne permettent pas de former une base initiale admissible sous forme de vecteurs unitaires.

Dans ce cas, pour trouver la base admissible initiale, des variables artificielles supplémentaires sont introduites. Les variables artificielles ne sont pas liées au contenu de la tâche, leur introduction n'est autorisée que si le schéma de calcul correspondant fournira une solution optimale dans laquelle toutes les variables artificielles seront égales à zéro.

Les variables R déterminent la base initiale admissible du point de vue d'une éventuelle transition ultérieure vers l'un des sommets de l'ODT. Pour l'utilisation de variables artificielles dans la fonction objectif, on introduit une pénalité M. Dans le problème de maximisation de M, négatif (M<<0), в задаче минимизации М положительное (М>>0).

Propriété M : Lors de l'addition (soustraction) avec n'importe quelle valeur finie qui détermine n'importe quelle valeur que chacune des variables de la LLP d'origine peut prendre, sa valeur (variable M) ne change pas, à savoir,

Formule (1.2), restrictions sur la non-négativité des variables (oui, non) - formule (1.3) (1.1) i = 1, ... m (1.2) (1.3) L'algorithme de résolution des problèmes de programmation linéaire nécessite de les amener sous forme canonique lorsque la fonction objectif ...

En pratique, les contraintes d'un problème de programmation linéaire sont souvent données non pas par des équations, mais par des inégalités.

Montrons comment on peut passer d'un problème avec contraintes d'inégalité au problème principal de la programmation linéaire.

Soit un problème de programmation linéaire à variables , dans lequel les contraintes imposées aux variables ont la forme d'inégalités linéaires. Dans certains d'entre eux, le signe d'inégalité peut être et d'autres (le second type est réduit au premier par un simple changement du signe des deux parties). Par conséquent, nous définissons toutes les contraintes d'inégalité sous la forme standard :

Il est nécessaire de trouver un tel ensemble de valeurs non négatives qui satisferait les inégalités (4.1), et, en plus, minimiserait la fonction linéaire :

Du problème ainsi posé, il est facile de passer au problème principal de la programmation linéaire. En effet, nous introduisons la notation :

où se trouvent de nouvelles variables, que nous appellerons "supplémentaires". Selon les conditions (4.1), ces variables supplémentaires, comme il se doit, doivent être non négatives.

Ainsi, nous sommes confrontés au problème de la programmation linéaire dans la formulation suivante : trouver des valeurs non négatives des variables telles qu'elles satisfassent le système d'équations (4.3) et en même temps minimiser la fonction linéaire de ces variables :

Comme vous pouvez le voir, nous avons devant nous dans sa forme pure le problème principal de la programmation linéaire (LPP). Les équations (4.3) sont données sous la forme déjà résolue par rapport aux variables de base, qui sont exprimées en termes de variables libres. La fonction L est exprimée uniquement en termes de variables "initiales" (les coefficients des variables "supplémentaires" qu'elle contient sont égaux à zéro).

Ainsi, nous avons réduit le problème de la programmation linéaire avec des contraintes d'inégalité au problème principal de la programmation linéaire, mais avec un plus grand nombre de variables que ce qui était initialement dans le problème.

Exemple 1 Il existe un problème de programmation linéaire avec des contraintes d'inégalité : trouver des valeurs non négatives de variables qui satisfont aux conditions

et en minimisant la fonction linéaire

Il est nécessaire de réduire ce problème à la forme de l'OLP.

Solution. Nous apportons les inégalités (4.4) à la forme standard ;

Nous introduisons des variables supplémentaires :

La tâche consiste à trouver des valeurs non négatives des variables

satisfaire les équations (4.6) et minimiser la fonction linéaire (4.5).

Nous avons montré comment il est possible de passer d'un problème de programmation linéaire avec contraintes d'inégalité à un problème avec contraintes d'égalité (ELP). La transition inverse est toujours possible - du LLP au problème avec contraintes d'inégalité. Si dans le premier cas nous avons augmenté le nombre de variables, dans le second cas nous le diminuerons en éliminant les variables de base et en ne laissant que les libres.

Exemple 2. Il existe un problème de programmation linéaire avec contraintes d'égalité (OLP) :

et la fonction à minimiser

Il est nécessaire de l'écrire comme un problème de programmation linéaire avec des contraintes d'inégalité.

Solution. Puisque , nous choisissons deux des variables comme libres. Notez que les variables ne peuvent pas être choisies comme libres, car elles sont liées par la première des équations (4 7) : la valeur de l'une d'entre elles est complètement déterminée par la valeur de l'autre, et les variables libres doivent être indépendantes

Pour la même raison, il est impossible de choisir des variables libres (elles sont reliées par la deuxième équation). Nous choisissons comme variables libres et exprimons tout le reste en fonction de celles-ci :

Puisque les conditions (4 9) peuvent être remplacées par des inégalités :

Passons dans l'expression de la fonction linéaire L aux variables libres Substituant dans L au lieu de et leurs expressions (4.9). avoir.

Les modèles mathématiques sont à la base de la résolution des problèmes économiques.

modèle mathématique problème est un ensemble de relations mathématiques qui décrivent l'essence du problème.

• sélection de variable de tâche
• l'élaboration d'un système de restrictions
• choix de la fonction objectif

Variables de tâche sont appelées grandeurs X1, X2, Xn, qui caractérisent pleinement le processus économique. Ils s'écrivent généralement sous la forme d'un vecteur : X=(X 1 , X 2 ,...,X n).

Le système des restrictions les tâches sont un ensemble d'équations et d'inégalités qui décrivent les ressources limitées dans le problème considéré.

fonction cible tâche est appelée une fonction de variables de tâche qui caractérise la qualité de la tâche et dont il faut trouver l'extremum.

En général, un problème de programmation linéaire peut être écrit comme suit :

Cette entrée signifie : trouver l'extremum de la fonction objectif (1) et les variables correspondantes X=(X 1 , X 2 ,...,X n) à condition que ces variables satisfassent le système de contraintes (2) et non -conditions de négativité (3) .

Solution acceptable(plan) d'un problème de programmation linéaire est tout vecteur à n dimensions X=(X 1 , X 2 ,...,X n) qui satisfait le système de contraintes et les conditions de non-négativité.

L'ensemble des solutions réalisables (plans) des formes du problème éventail de solutions réalisables(ODR).

La solution optimale(plan) d'un problème de programmation linéaire est une telle solution réalisable (plan) du problème, dans laquelle la fonction objectif atteint un extremum.

Un exemple de compilation d'un modèle mathématique

La tâche d'utiliser des ressources (matières premières)

État: Pour la fabrication de n types de produits, m types de ressources sont utilisées. Faire un modèle mathématique.

Connu:

• b i (i = 1,2,3,...,m) sont les réserves de chaque i-ième type de ressource ;
• a ij (i = 1,2,3,...,m; j=1,2,3,...,n) sont les coûts de chaque i-ème type de ressource pour la production d'un volume unitaire de le j-ième type de produit ;
• c j (j = 1,2,3,...,n) est le bénéfice de la vente d'un volume unitaire du j-ième type de produit.

Il est nécessaire d'élaborer un plan de production de produits qui offre un profit maximal avec des restrictions données sur les ressources (matières premières).

Solution:

On introduit un vecteur de variables X=(X 1 , X 2 ,...,X n), où xj (j = 1,2,...,n) est le volume de production du j-ème type de produit.

Les coûts du i-ème type de ressources pour la production d'un volume donné x j de produits sont égaux à a ij x j , par conséquent, la restriction à l'utilisation des ressources pour la production de tous les types de produits a la forme :
Le bénéfice de la vente du j-ième type de produit est égal à c j x j , donc la fonction objectif est égale à :

Réponse- Le modèle mathématique ressemble à :

Forme canonique d'un problème de programmation linéaire

Dans le cas général, un problème de programmation linéaire est écrit de telle manière que les équations et les inégalités sont des contraintes, et les variables peuvent être non négatives ou changer arbitrairement.

Dans le cas où toutes les contraintes sont des équations et toutes les variables satisfont la condition de non-négativité, le problème de programmation linéaire est appelé canonique.

Il peut être représenté en notation coordonnée, vectorielle et matricielle.

Le problème de programmation linéaire canonique en notation de coordonnées a la forme :

Le problème de programmation linéaire canonique en notation matricielle a la forme :

• A est la matrice des coefficients du système d'équations
• X est une matrice de colonnes de variables de tâche
• Ao est la matrice-colonne des parties droites du système de contraintes

On utilise souvent des problèmes de programmation linéaire, appelés symétriques, qui, en notation matricielle, ont la forme :

Réduction d'un problème général de programmation linéaire à une forme canonique

Dans la plupart des méthodes de résolution de problèmes de programmation linéaire, on suppose que le système de contraintes est constitué d'équations et de conditions naturelles pour la non-négativité des variables. Cependant, lors de la compilation de modèles de problèmes économiques, les contraintes sont principalement formées sous la forme d'un système d'inégalités, il est donc nécessaire de pouvoir passer d'un système d'inégalités à un système d'équations.

Prenez une inégalité linéaire a 1 x 1 +a 2 x 2 +...+anxn ≤b et ajoutez une valeur x n+1 à son côté gauche, de sorte que l'inégalité devienne l'égalité a 1 x 1 +a 2 x 2 + ...+anxn +x n+1 =b. De plus, cette valeur x n+1 est non négative.

Considérons tout avec un exemple.

Réduisez le problème de programmation linéaire à la forme canonique :

Solution:
Passons au problème de la recherche du maximum de la fonction objectif.
Pour ce faire, on change les signes des coefficients de la fonction objectif.
Pour convertir les deuxième et troisième inégalités du système de contraintes en équations, on introduit des variables supplémentaires non négatives x 4 x 5 (cette opération est repérée par la lettre D sur le modèle mathématique).
La variable x 4 est inscrite du côté gauche de la deuxième inégalité avec un signe "+", puisque l'inégalité a la forme "≤".
La variable x 5 est inscrite du côté gauche de la troisième inégalité avec le signe "-", puisque l'inégalité a la forme "≥".
Les variables x 4 x 5 sont entrées dans la fonction objectif avec un coefficient. égal à zéro.
Nous écrivons le problème sous forme canonique.

3.1. Problème général de programmation linéaire

Programmation linéaire- il s'agit de la section la plus développée de la programmation mathématique, à l'aide de laquelle l'analyse et la résolution de problèmes extrêmes avec des connexions linéaires et des restrictions sont effectuées.

La programmation linéaire comprend un certain nombre de méthodes de résolution heuristiques (approximatives) qui permettent, dans des conditions données, de choisir la meilleure solution optimale parmi toutes les solutions possibles aux problèmes de production. Ces méthodes comprennent les suivantes - graphique, simplexe, méthode potentielle (méthode de distribution modifiée - MOD), Khichkov, Kreko, méthode d'approximation de Vogel et autres.

Certaines de ces méthodes sont unies par un nom commun - la méthode de distribution ou de transport.

Le berceau de la programmation linéaire est la Russie. Les premiers travaux sur la programmation linéaire du futur académicien L.V. Kantorovich ont été publiés en 1939. En 1975, il a reçu le prix Nobel d'économie pour le développement de méthodes de programmation linéaire. Comme la plupart des travaux de l'académicien L.V. Kantorovich se consacre à la résolution des problèmes de transport, on peut considérer que le prix Nobel mentionné marque également les mérites de la science russe des transports.

Dans le transport routier, les méthodes de programmation linéaire sont utilisées depuis les années 1960 pour résoudre un grand nombre des problèmes de production les plus importants, à savoir : réduire la distance de transport des marchandises ; l'élaboration d'un schéma de transport optimal ; sélection des itinéraires de déplacement les plus courts ; tâches de transport de cargaisons différentes mais interchangeables ; planification quotidienne des quarts de travail ; planification du transport de cargaisons en petits lots ; répartition des bus le long des itinéraires et autres.

Les caractéristiques du modèle de programmation linéaire sont les suivantes :

La fonction objectif et les contraintes sont exprimées par des dépendances linéaires (égalités ou inégalités) ;

Le nombre de dépendances est toujours inférieur au nombre d'inconnues (condition d'incertitude) ;

Non-négativité des variables requises. La forme générale d'écriture d'un modèle de programmation linéaire sous forme abrégée est la suivante :

Trouver X ij ≥ 0 (j = 1, 2…n) sous le type de contraintes suivant :

Ces contraintes minimisent (ou maximisent) la fonction objectif

La forme standard d'écriture d'un modèle de programmation linéaire est un système d'équations linéaires écrites en canonique forme, c'est-à-dire sous forme d'égalités linéaires, en nombres non négatifs :

un 11 x 1 + un 12 x 2 + ... + un 1 n x n \u003d b 1;

une 21 x 1 + une 22 x 2 + ... + une 2 n x n \u003d b 2 ; (3.1)

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

une m x 1 + une m 2 x 2 + ...+ une mn x n = b m ..

Si le modèle est écrit sous la forme d'inégalités en nombres non négatifs, c'est-à-dire qu'il a la forme

une 11 x 1 + une 12 x 2 + ... + une 1 n x n ≤ b 1 ;

une 21 x 1 + une 22 x 2 + ... + une 2 n x n ≤ b 2 ; (3.2)

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

une m x 1 + une m 2 x 2 + …+ une mn x n ≤ b m ,..

alors cette entrée est réduite à canonique forme (3.1) en introduisant des variables supplémentaires x n +1> 0 (je=1,2…m) au côté gauche de l'inégalité (ou réduction du nombre de variables si le signe de l'inégalité est dirigé dans le sens opposé). Des variables supplémentaires constituent la base.

La forme standard de résolution d'un problème de programmation linéaire consiste à trouver des solutions à un système d'équations linéaires en nombres non négatifs qui minimisent la fonction objectif. La fonction objectif a alors la forme

L = c 1 x 1 + c 2 x 2 ... c n x n → minimum, (3.3)

où s 1 , s 2 … s n sont des coefficients de fonction objectifs L avec variables X j.

Des variables supplémentaires entrent dans la fonction objectif avec des coefficients nuls.

Dans le cas de la maximisation de la fonction objectif L les signes des variables de la fonction objectif doivent être inversés, et nous en reviendrons au problème de minimisation, c'est-à-dire une tâche est réduite à une autre substitution L sur le - L ou max L=min(- L).

Une solution de base d'un système d'équations linéaires (3.1) est une solution dans laquelle des valeurs nulles sont données aux variables non fondamentales.

Une solution de base est dite admissible dans laquelle les variables incluses dans la base sont non négatives.

Une solution admissible qui maximise (ou minimise) la fonction objectif (3.3) est dite optimale.

A chaque problème de programmation linéaire correspond un autre, appelé problème de programmation linéaire dual. Le problème original par rapport au dual s'appelle le problème direct. Les problèmes primal et dual forment une paire, appelée double paire en programmation linéaire. La paire primale et la paire duale forment une paire asymétrique lorsque le problème primal est écrit sous forme canonique, et une paire symétrique lorsque les conditions des problèmes sont écrites sous forme d'inégalités.

Les règles de compilation d'un modèle mathématique d'un problème dual sont basées sur les règles du calcul matriciel.

Le concept de dualité est largement utilisé dans l'analyse des problèmes de programmation linéaire. La propriété de dualité est examinée en détail dans chaque cas particulier.

3.2. Méthode d'analyse graphique

La méthode analytique des graphes est l'une des méthodes les plus simples de programmation linéaire. Il révèle clairement l'essence de la programmation linéaire, son interprétation géométrique. Son inconvénient est qu'il permet de résoudre des problèmes à 2 ou 3 inconnues, c'est-à-dire qu'il s'applique à un éventail restreint de problèmes. La méthode est basée sur les règles de la géométrie analytique.

Résoudre un problème à deux variables x1 et x2, qui, selon le sens du problème, ne devrait pas être négatif, est effectué dans le système de coordonnées cartésiennes. Équations x1=0 et x2= 0 sont les axes du système de coordonnées du premier quadrant

Considérons la méthode de résolution à l'aide d'un exemple spécifique.

Exemple 3.1. Il y a 300 tonnes de produits en béton cellulaire et 200 tonnes de produits en acier en stock. L'entreprise automobile doit livrer ces produits à l'installation en construction. Le constructeur automobile a des camions KAMAZ - 5320 et

ZIL-4314. Pour un voyage, KamAZ-5320 peut livrer 6 tonnes de béton cellulaire et 2 tonnes d'acier, et le bénéfice du voyage sera de 4 000 roubles. ZIL-4314 livre 2 tonnes de béton cellulaire et 4 tonnes d'acier en un seul voyage, le bénéfice du voyage est de 6 000 roubles. Il est nécessaire d'organiser le transport de manière à procurer le plus grand profit à l'entreprise automobile.

Construisons un modèle mathématique du problème. Dénotons par x 1 le nombre de voyages souhaités KamAZ-5320 et à travers X 2 nombre requis de coureurs ZIL-4314.

Le transport total en tonnes de produits en béton cellulaire est de 6 x1+ 2x2, et en acier 2 x1+ 4x2. La limite d'expédition, basée sur le nombre d'articles disponibles, est de 6 x1+ 2x2 ≤ 300 t pour le béton cellulaire et 2 x1+ 4x2 ≤ 200 t pour l'acier.

Bénéfice total en milliers de roubles. exprimé en 4 X 1 + 6X 2 , qui doit être maximisée et qui est le critère d'optimalité dans le problème considéré. Le modèle mathématique du problème ressemble donc à ce qui suit. Il faut maximiser la fonction objectif

L = 4x1+ 6x2 → max sous conditions : 6 x1+ 2x2 ≤ 300; 2x1+ 4x2 ≤ 200; x 1 ≥ 0;x2 ≥ 0.

Considérez l'équation 6 x1+ 2x 2 = 300. Pour construire une ligne décrite par cette équation, nous trouvons deux points situés sur cette ligne. À x1= 0 à partir de l'équation d'une droite on trouve 2 x 2 = 300, d'où x 2 \u003d 150. Par conséquent, le point A de coordonnées (0,150) se trouve sur la ligne souhaitée. À x2= 0 nous avons 6 x1\u003d 300, d'où x 1 \u003d 50, et le point ré de coordonnées (50,0) se trouve également sur la ligne souhaitée. Tracez une ligne passant par ces deux points UN D(Fig. 3.1).

Inégalité linéaire 6 x1+ 2x2 ≤ 300 est un demi-plan situé d'un côté de la ligne construite 6 x1+ 2x 2 = 300. Pour savoir de quel côté de cette droite se situent les points du demi-plan recherché, on substitue dans l'inégalité 6 x1+ 2x2 ≤ 300 coordonnées d'un point ne se trouvant pas sur la ligne de démarcation. Par exemple, l'origine est 0-(0,0). Elle satisfait l'inégalité 6∙0 + 2∙0 = 0< 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой UN D et sur la fig. 3.1 est grisé.

Équation 2 x1+ 4x2= 200 sera construit à partir de deux points. À x 1 = 0 4x 2 = 200 d'où x 2 = 50. Ensuite, pointez E a pour coordonnées (0,50) et appartient à la ligne désirée. À x2= 0, 2x 2 = 200 points Avec est sur la ligne donnée avec les coordonnées (100,0). En substituant dans l'inégalité les coordonnées du point Avec(0,0), on obtient 2∙0 + 4∙0 = 0< 200. Значит, начало координат находится в области допустимых значений от прямой 2x1+ 4x2= 200.

Le système de contraintes de tâches exige que les plans ( x 1 ; x2) satisfont les quatre inégalités, c'est-à-dire que les plans admissibles sont des points ( x 1 ; x2) doivent être simultanément dans les quatre demi-plans. Cette exigence n'est satisfaite que par les points situés à l'intérieur et sur la bordure du polygone. OEKD, qui est le polygone des solutions admissibles.

Les sommets du polygone des solutions réalisables sont les points O, E, K, D segments de ligne OE, EK, KD, OD- ses côtes. Tout point du polygone OEKD est le plan de la tâche, satisfaisant toutes ses conditions. Les sommets du polygone sont formés par l'intersection de deux droites et correspondent aux plans de base du problème, parmi lesquels se trouve le meilleur plan (optimal). Ainsi, il y aura autant de plans de référence qu'il y a de sommets dans le polygone des solutions réalisables.

Une représentation géométrique visuelle peut également être obtenue pour la fonction objectif L = 4x1+ 6x2. Nous fixons une valeur de la fonction objectif, par exemple L= 120. équation 4 x1+ 6x 2 = 120 définit une ligne passant par un point V avec des coordonnées (x 1 \u003d 0; x 2 \u003d 20) et un point L avec les coordonnées (( X 1 = 30; X 2 = 0). Section BL se trouve à l'intérieur du polygone OEKD. Par conséquent, pour tous les plans (points) de ce segment, la valeur de la fonction objectif est la même et égale à 120. En donnant d'autres valeurs de la fonction objectif, on obtient des lignes parallèles, appelées lignes de niveau fonction cible.

Faire bouger la ligne L parallèlement à lui-même dans une direction, nous obtenons une augmentation de la fonction objectif, et dans la direction opposée - sa diminution. Dans cet exemple, le mouvement d'une droite BLà droite détermine l'augmentation de la fonction objectif que nous maximisons. On fait ça jusqu'à la ligne BL aura au moins un point commun avec le polygone des solutions admissibles OEKD. De la fig. 3.1 il s'ensuit que le dernier point que la droite du niveau de la fonction objectif coupe sera le point À. Cela signifie que le point À détermine le plan de travail optimal.

La direction d'augmentation perpendiculaire à la ligne de niveau est appelée direction de la plus grande augmentation fonction objectif et détermine son gain maximal. Cette direction peut être définie sans tracer de lignes de niveau. Pour cela, il faut sur les axes x1 et x2 mettre de côté des segments égaux aux coefficients de la fonction objectif, et en les utilisant, comme dans les coordonnées, construire un vecteur de la plus grande augmentation de la fonction objectif. En mathématiques, cela s'appelle pente et désigné par le signe grad. Dégradé pour une fonctionnalité L = 4x 1 + 6x 2 va vectoriser n| 4 ; 6 | . Pour la commodité de sa construction, nous augmentons les coordonnées, par exemple, de 10 fois, c'est-à-dire n | 40 ; 60 | . Construisons le gradient de la fonction objectif L, dont on relie le point de coordonnées (40 ; 60) à l'origine. Les lignes de niveau de fonction objectif sont tracées perpendiculairement à la direction du gradient.

Ainsi, d'une manière ou d'une autre, il est établi que le point À détermine le plan de tâche optimal, dont les valeurs des variables correspondent aux coordonnées du point donné. Pour établir les coordonnées, il faut résoudre le système d'équations des droites qui forment ce sommet :

6x1+ 2x2= 300;

2x1+ 4x2= 200.

Nous égalisons les coefficients en x 1 en multipliant la deuxième équation par 3 et soustrayons le premier de la deuxième équation. Prenons 10 x2= 300,x 2 = 30. En remplaçant la valeur x 2 \u003d 30 dans l'une des équations, par exemple dans la première, nous déterminons la valeur X 1:

6x1+ 2X · 30 = 300,

d'où 6 x 1 = 300 - 60 = 240, donc, x 1 = 40.

Ainsi, pour tirer le meilleur parti d'un constructeur automobile, il est nécessaire d'effectuer 40 voyages vers KamAZ-5320 et 30 voyages vers ZIL-4314. Le profit maximum dans ce cas sera

L = 4x1+ 6x2\u003d 4 40 + 6 30 \u003d 340 mille roubles.

Sur la base de l'exemple considéré et de l'interprétation géométrique du problème d'optimisation à deux variables, nous pouvons tirer les conclusions suivantes :

1) dans un espace à deux dimensions, la zone des solutions réalisables est un polygone;

2) chaque côté du polygone correspond à la valeur d'une variable égale à zéro ;

3) chaque sommet du polygone des solutions admissibles correspond aux valeurs de deux variables égales à zéro ;

4) chaque valeur de la fonction objectif correspond à une droite ;

5) la solution optimale du problème correspond au sommet du polygone, dans lequel la fonction objectif acquiert la valeur optimale, tandis que les variables optimales sont les coordonnées de ce sommet.

Dans le cas général, les problèmes d'optimisation ont une interprétation géométrique similaire. L'ensemble des plans de tâches sera un polyèdre dont les sommets correspondent aux plans de référence. Lors de la résolution du problème, la transition d'un sommet du polyèdre à un autre avec une grande valeur de la fonction objectif est effectuée jusqu'à l'obtention de sa valeur optimale. Notons que l'efficacité des méthodes d'optimisation réside précisément dans le fait que l'énumération des sommets (itération) ne s'effectue que dans le sens de la plus grande augmentation de la fonction objectif. Par conséquent, tous les sommets ne sont pas pris en compte, dont il existe un grand nombre, mais uniquement ceux qui sont les plus proches de l'extrême.

Lors de la détermination d'une classe de problèmes d'optimisation et du choix d'une méthode pour la résoudre, il est nécessaire de savoir si l'ensemble des solutions réalisables est convexe ou non convexe, une fonction objectif linéaire ou non linéaire.

Par définition, un ensemble est appelé convexe si pour deux points quelconques le segment entier reliant ces points appartient à cet ensemble. Des exemples d'ensembles convexes sont, par exemple, un segment (Fig. 3.2, a), un plan en forme de cercle, un cube, un parallélépipède, ainsi que des polygones entièrement situés d'un côté de chacun de ses côtés , etc.

Sur la fig. 3.2b montre des ensembles non convexes. Dans les ensembles non convexes, on peut indiquer au moins deux points du segment AB qui n'appartiennent pas à l'ensemble considéré.

3.3. Méthode simplexe

Méthode simplexe est une méthode courante pour résoudre les problèmes de programmation linéaire. La méthode tire son nom du mot "simplex", désignant le polygone convexe le plus simple, dont le nombre de sommets est toujours un de plus que la dimension de l'espace. La méthode du simplexe a été développée aux États-Unis par le mathématicien J. Dantzig à la fin des années 1940.

La méthode du simplexe comprend l'obtention d'une solution de base non négative d'un système d'équations linéaires canoniques de type (3.1), la minimisation (maximisation) ultérieure de la fonction objectif (3.3) et, de cette manière, la recherche des valeurs optimales de la variables requises x 1, x 2… x n.

L'idée de la méthode du simplexe réside dans le fait qu'au cours du calcul on passe séquentiellement de la première solution de base à la deuxième, troisième, etc. par le soi-disant recto métamorphoses. Les transformations sont faites sous forme de tableaux simplex, ce qui simplifie et accélère grandement les calculs.

Pour obtenir des solutions de base non négatives d'un système d'équations linéaires, il est nécessaire de conduire le processus d'élimination des inconnues de manière à ce que les termes libres des équations restent non négatifs à toutes les étapes du processus. Dans ce cas, il faut se guider sur la règle suivante : toute variable libre pour laquelle il existe au moins un coefficient positif est prise comme nouvelle variable de base ; une variable est dérivée de la base, qui correspond au plus petit rapport des termes libres des équations aux coefficients positifs correspondants des équations avec la variable introduite dans la base. De telles transformations sont appelées convertisseurs simplex.

Ceci est très important, car pour trouver une solution non négative particulière qui correspond à la plus grande valeur possible d'une variable libre avec des valeurs nulles d'autres variables libres, au lieu de déterminer la plage de variation de la variable spécifiée et de la remplacer sa plus grande valeur possible dans la solution générale, il suffit de prendre cette variable comme variable de base et de soumettre le système à une transformation simplexe, passant à une nouvelle base, ce qui simplifie grandement les calculs.

Les calculs sont effectués de manière pratique à l'aide de tableaux simplex. Le passage d'un tableau à un autre correspond à une itération, c'est-à-dire le passage d'une base à une autre, tandis que la valeur de la fonction objectif diminue. Pour un certain nombre d'itérations, ils passent à la base pour laquelle la valeur optimale (minimale ou maximale) de la fonction objectif est obtenue. Considérons la méthode du simplexe sous sa forme générale.

La tâche générale de la programmation linéaire est de minimiser (maximiser) la fonction objectif, dont les variables sont interconnectées par un système d'équations linéaires, soumis à la condition de non-négativité.

Soit nécessaire de minimiser la forme linéaire

L = c 1 x 1 + c 2 x 2 + ... c n x n.

Dans les conditions suivantes (pour plus de clarté, les coefficients zéro et unité sont conservés dans les équations) :

1x1+ 0x2 + ... 0x m + une 1m+ 1x m+1 ... + une 1n x n \u003d b 1;

0x1+ 12+… 0x m + une 2m+ 1x m+1 ... + une 2n x n \u003d b 2;

……………………………………………

0x1+ 0x 2 + ... 1x m + un mm + 1x m +1 ... + un mn x n \u003d b m.

Ce système d'équations a déjà une base toute faite, puisque chaque équation de contrainte contient une inconnue avec un coefficient égal à un, qui n'est pas dans d'autres équations, c'est-à-dire parmi les coefficients des variables X 1 , X 2 …, xm vous pouvez créer une matrice d'identité.

Résolvons les équations pour les variables de base :

x 1 \u003d b 1 - (une 1m + 1 x m + 1 ... + une 1n x n);

x 2 \u003d b 2 - (un 2m + 1 x m + 1 ... + un 2n x n);

………………………………

x m \u003d b m - (un mm + 1x m + 1 ... + un mn x n),

et nous exprimerons la fonction objectif en termes de variables libres, en y substituant, à la place des variables de base, leurs expressions en termes de variables libres :

L=c 1 b 1 +c 2 b 2 +cmbm –(c 1 a 1m +c 2 a 2m+1 +…+cma mn+1)x m+1 -…-(c 1 a 1n +c 2 a 2n +…+cma mn)xn …+cnx n..

variables x 1, x 2 ..., x m, à l'aide desquels le premier plan de base est trouvé, sont basiques, et le reste x m +1 , x m +2 ,…x n – gratuit. Il devrait toujours y avoir autant de variables de base qu'il y a d'équations dans le système. Sur la base de la condition de non-négativité, la plus petite valeur des variables libres est égale à zéro. La solution de base résultante du système d'équations est sa solution réalisable initiale, c'est-à-dire x 1 \u003d b 1, x 2 \u003d b 2, ... x m \u003d b m, x m +1 \u003d 0,…, x n = 0.

Cette solution correspond à la valeur de la fonction objectif

L = c 1 b 1 + c 2 b 2 + ... c m b m.

L'optimalité de la solution initiale est vérifiée. Si elle n'est pas optimale, alors en introduisant des variables libres dans la base, les solutions réalisables suivantes sont trouvées avec une plus petite valeur de la fonction objectif. Pour cela, déterminez la variable libre qui doit être renseignée dans la base, ainsi que la variable qui doit être retirée de la base. Ensuite, ils passent du système précédent au système équivalent suivant. Cela se fait à l'aide de tableaux simplex. La résolution du problème se poursuit jusqu'à ce que la valeur optimale de la fonction objectif soit obtenue.

Les tableaux simplex sont compilés comme suit (voir tableau 3.1). Placer toutes les variables en haut du tableau X 1 , X 2 …, x n et coefficients cc, avec laquelle les variables correspondantes sont incluses dans la fonction objectif. Première colonne c je est constitué du coefficient de la fonction objectif pour les variables incluses dans la base. Ceci est suivi d'une colonne de variables de base et de termes libres des équations. Les éléments des colonnes restantes du tableau sont les coefficients des variables avec lesquelles ces dernières entrent dans le système d'équations. Ainsi, chaque ligne du tableau correspond à l'équation du système, résolue par rapport à la variable de base. Le tableau montre également une variante du plan qui correspond à la fonction objectif pour une base donnée.

La ligne du bas du tableau s'appelle indice. Chacun de ses éléments (estimation) ∆ j déterminer

∆j = z j – c j ,

où cc sont les coefficients des variables correspondantes dans la fonction objectif ; zj- la somme des produits des coefficients de la fonction objectif avec les variables de base et les variables correspondantes - éléments j-ème colonne du tableau.

tableau 3.1

Tableau simplex avec initiale valide

Cours 2

V Forme canonique

solution admissible du PLP(plan acceptable).

solution optimale du LLP.

Avoir besoin

Exemple.

Écrivons le problème en Forme canonique

Situations particulières de la solution graphique du ZLP

Sauf lorsque la tâche est la seule solution optimale pour et , peut être situation particulière:

1. la tâche a un nombre infini de solutions optimales – l'extremum de la fonction est atteint sur le segment ( optimum alternatif)- Figure 2;

2. tâche pas résoluble en raison de l'illimité de l'ODR, ou - Figure 3 ;

3. ODR - point unique Ah, alors ;

4. tâche pas résoluble si l'ODR a une zone vide.

UNE

Figure 2 Figure 3

Si la ligne de niveau est parallèle au côté de la zone des solutions réalisables, alors l'extremum est atteint en tous points du côté. Le problème a un nombre infini de solutions optimales - optimum alternatif . La solution optimale est trouvée par la formule

où est le paramètre. Pour toute valeur de 0 à 1, vous pouvez obtenir tous les points du segment, pour chacun desquels la fonction prend la même valeur. D'où le nom - optimum alternatif.

Exemple. Résoudre graphiquement le problème de programmation linéaire ( optimum alternatif):

Questions pour la maîtrise de soi

1. Écrivez le problème de programmation linéaire sous une forme générale.

2. Écrivez le problème de programmation linéaire sous des formes canoniques et standard.

3. Quelles transformations peut-on utiliser pour passer de la forme générale ou standard d'un problème de programmation linéaire à la forme canonique ?

4. Donner une définition des solutions réalisables et optimales au problème de programmation linéaire.

5. Laquelle des solutions est la « meilleure » ​​pour le problème de la minimisation de la fonction si ?

6. Laquelle des solutions est la « meilleure » ​​pour le problème de maximisation de la fonction si ?

7. Écrivez la forme standard du modèle mathématique d'un problème de programmation linéaire à deux variables.

8. Comment construire un demi-plan donné par une inégalité linéaire à deux variables ?

9. Qu'appelle-t-on la solution d'un système d'inégalités linéaires à deux variables ? Construire sur le plan le domaine des solutions réalisables d'un tel système d'inégalités linéaires, qui :

1) a une solution unique ;

2) a un ensemble infini de solutions ;

3) n'a pas de solution.

10. Ecrire pour une fonction linéaire gradient vectoriel, nommez le type de lignes de niveau. Comment les lignes de gradient et de niveau sont-elles situées les unes par rapport aux autres ?

11. Formulez un algorithme pour une méthode graphique de résolution d'un LLP standard à deux variables.

12. Comment trouver les coordonnées et les valeurs de la solution, ?

13. Construire l'aire des solutions réalisables, lignes de gradient et de niveau, pour des problèmes de programmation linéaire dans lesquels :

1) est atteint en un seul point, et - sur le segment ODR ;

2) est atteint en un seul point de l'ODS, et .

14. Donnez une illustration géométrique du LLP s'il :

1) possède des solutions optimales uniques pour et ;

2) a un ensemble de solutions optimales pour .

Cours 2

méthode graphique pour trouver la solution optimale

1. Formes de modèles mathématiques linéaires et leur transformation

2. Méthode graphique pour résoudre un problème de programmation linéaire

3. SITUATIONS PARTICULIERES DE LA SOLUTION GRAPHIQUE DE LLP

4. Solution graphique de problèmes économiques de programmation linéaire

Formes de modèles mathématiques linéaires et leur transformation

Un modèle mathématique d'un problème de programmation linéaire (LPP) peut être écrit sous l'une des trois formes suivantes.

V forme générale du modèle mathématique il faut trouver le maximum ou le minimum de la fonction objectif ; le système de contraintes contient des inégalités et des équations ; toutes les variables ne peuvent pas être non négatives.

V Forme canonique le modèle mathématique doit trouver le maximum de la fonction objectif ; le système de contraintes se compose uniquement d'équations ; toutes les variables sont non négatives.

Dans la forme standard d'un modèle mathématique, il est nécessaire de trouver le maximum ou le minimum d'une fonction ; toutes les contraintes sont des inégalités ; toutes les variables sont non négatives.

La solution du système de contraintes qui satisfait les conditions de non-négativité des variables est appelée solution admissible du PLP(plan acceptable).

L'ensemble des solutions réalisables est appelé le domaine des solutions réalisables du LLP.

Une solution réalisable, dans laquelle la fonction objectif atteint une valeur extrême, est appelée solution optimale du LLP.

Les trois formes du LLP sont équivalentes en ce sens que chacune d'elles peut être réduite à une forme différente à l'aide de transformations mathématiques.

Avoir besoin passage d'une forme de modèle mathématique à une autre associés aux méthodes de résolution de problèmes : par exemple, la méthode du simplexe, largement utilisée en programmation linéaire, est appliquée à un problème écrit sous forme canonique, et la méthode graphique est appliquée à la forme standard d'un modèle mathématique.

Passage à la notation canonique ZLP.

Exemple.

Écrivons le problème en Forme canonique, en introduisant une variable supplémentaire (solde) avec le signe "+" dans le côté gauche de la première inégalité du système de contraintes, et une variable supplémentaire avec le signe "moins" dans le côté gauche de la deuxième inégalité.

La signification économique des diverses variables supplémentaires peut ne pas être la même : elle dépend de la signification économique des restrictions dans lesquelles ces variables sont incluses.

Ainsi, dans le problème de l'utilisation des matières premières, ils montrent le reste des matières premières, et dans le problème du choix des technologies optimales, ils montrent le temps inutilisé de l'entreprise utilisant une certaine technologie ; dans le problème de la coupe - la libération de flans d'une longueur donnée dépassant le plan, etc.