Modèles linéaires pour la prise de décision commerciale. Modèles de programmation linéaire pour résoudre les problèmes de contrôle des processus de transport Vue générale du modèle de programmation linéaire

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 le problème graphiquement 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 peuvent être utilisées 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, méthode du simplexe, largement utilisé en programmation linéaire, est appliqué à un problème écrit sous forme canonique, tandis que 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.

T10. Énoncé du problème de programmation linéaire

modèle mathématique Un problème économique est un ensemble de relations mathématiques qui décrivent le processus économique.

Pour compiler un modèle mathématique, il faut :

1. sélectionner les variables de tâche ;

2. établir un système de restrictions ;

3. définir la fonction objectif.

Variables de tâche les quantités x 1 , x 2 ,…, x n sont appelées, qui caractérisent pleinement le processus économique. Ils sont généralement écrits sous la forme d'un vecteur X \u003d (x 1, x 2, ..., x n).

Système de contraintes de tâches est un ensemble d'équations et d'inégalités qui sont satisfaites par les variables du problème et qui découlent des ressources limitées et d'autres conditions économiques, par exemple, la positivité des variables. En général, ils ressemblent à :

La fonction objectif est appelée fonction F(X) = f(x 1 , x 2 ,…, x n) des variables de la tâche, qui caractérise la qualité de la tâche et dont il faut trouver l'extremum.

Problème général de programmation mathématique se formule comme suit : trouver les variables de tâche x 1 , x 2 ,…, x n qui fournissent l'extremum de la fonction objectif

F (X) \u003d f (x 1, x 2, ..., x n) ® max (min) (2)

et satisfaire le système de contraintes (1).

Si la fonction objectif (2) et le système de contraintes (1) sont linéaires, alors le problème de programmation mathématique est appelé problème de programmation linéaire (LPP).

Le vecteur X (un ensemble de variables de tâche) est appelé solution acceptable, ou le plan PLP, s'il satisfait au régime des restrictions (1). Un plan réalisable X qui fournit un extremum de la fonction objectif est appelé solution optimale ZLP.

2. Exemples de compilation de modèles mathématiques de problèmes économiques

L'étude de situations de production spécifiques conduit à des ZLP, qui sont interprétés comme des problèmes d'utilisation optimale de ressources limitées.

1.Le problème du plan de production optimal

Pour la fabrication de deux types de produits T 1 et T 2, trois types de ressources S 1 , S 2 , S 3 sont utilisées. Les stocks de ressources, le nombre d'unités de ressources dépensées pour la fabrication d'une unité de production, ainsi que le bénéfice de la vente d'une unité de production sont indiqués dans le tableau :

Il est nécessaire de trouver un tel plan pour la production de produits dans lequel le profit de sa vente sera maximal.

Solution.

Notons x 1, x 2 - le nombre d'unités de production, respectivement, T 1 et T 2, prévues pour la production. Pour leur fabrication, (x 1 + x 2) unités de ressource S 1, (x 1 + 4x 2) unités de ressource S 2, (x 1) unités de ressource S 3 seront nécessaires. La consommation des ressources S 1 , S 2 , S 3 ne doit pas dépasser leurs réserves, respectivement 8, 20 et 5 unités.

Alors le modèle économico-mathématique du problème peut être formulé comme suit :

Trouvez un plan de production X \u003d (x 1, x 2) qui satisfait le système de restrictions :

et l'état

sous lequel la fonction prend la valeur maximale.

Le problème peut être facilement généralisé au cas de la production de n types de produits utilisant m types de ressources.

2.Le problème de l'alimentation optimale

Il existe deux types d'aliments K 1 et K 2 contenant les nutriments S 1 , S 2 et S 3 . Le contenu du nombre d'unités nutritives dans 1 kg de chaque type d'aliment, le minimum requis d'éléments nutritifs, ainsi que le coût de 1 kg d'aliment sont indiqués dans le tableau:

Il est nécessaire d'établir une ration quotidienne qui a un coût minimum, dans laquelle la teneur de chaque type de nutriment ne serait pas inférieure à la limite établie.

Solution.

Notons x 1, x 2 - la quantité d'aliments K 1 et K 2 inclus dans l'alimentation quotidienne. Ensuite, ce régime comprendra (3x 1 + x 2) unités de nutriment S 1, (x 1 + 2x 2) unités de substance S 2, (x 1 + 6x 2) unités de nutriment S 3. Étant donné que la teneur en nutriments S 1 , S 2 et S 3 dans l'alimentation doit être de 9, 8 et 12 unités, respectivement, le modèle économico-mathématique du problème peut être formulé comme suit :

Composez un régime quotidien X \u003d (x 1, x 2), satisfaisant le système de restrictions:

et l'état

sous lequel la fonction accepte valeur minimum.

Formulaires d'enregistrement PLP

En LLP, il est nécessaire de trouver l'extremum de la fonction objectif linéaire :

avec restriction :

et la condition de non négativité

où a ij , b i , c j ( , ) sont des constantes données.

C'est ainsi que le ZLP est écrit en général former. Si le système de contraintes ne contient que des inégalités, alors le LLP est représenté dans la norme former. Canonique (principal) la forme de la notation ZLP est la notation lorsque le système de contraintes ne contient que des égalités. Ainsi, les LLP ci-dessus sont rédigés sous une forme standard.

Les formes générale, standard et canonique de la LLP sont équivalentes en ce sens que chacune d'elles, à l'aide de transformations simples, peut être réécrite sous une forme différente. Cela signifie que s'il existe un moyen de résoudre l'un de ces problèmes, le plan optimal pour l'un des problèmes peut être déterminé.

Pour passer d'une forme de notation LLP à une autre, il faut pouvoir passer de contraintes d'inégalité à des contraintes d'égalité et inversement.

Une contrainte d'inégalité (£) peut être convertie en une contrainte d'égalité en ajoutant une variable non négative supplémentaire à son côté gauche, et une contrainte d'inégalité (³) peut être convertie en une contrainte d'égalité en soustrayant une variable non négative supplémentaire de sa valeur. côté gauche. Le nombre de variables non négatives supplémentaires introduites est égal au nombre de contraintes d'inégalité transformées.

Introduit des variables supplémentaires ont un sens économique. Ainsi, si les contraintes du PLP d'origine reflètent la consommation et la disponibilité des ressources, alors la valeur de la variable supplémentaire PLP sous forme canonique est égale au volume de la ressource correspondante inutilisée.

Exemple 1. Ecrire sous la forme canonique ZLP :

avec restriction :

Solution.

La fonction objectif reste inchangée :

Le système d'inégalités se transforme en un système d'égalités :

Lors de la résolution du LLP par une méthode graphique, une transition de la forme canonique à la forme standard est requise.

Pour transformer le LLP en un formulaire standard, utilisez Méthode Jordan-Gauss Solutions SLAU. Contrairement à la méthode de Gauss, dans laquelle la matrice étendue du système est réduite à une forme en escalier, dans la méthode de Jordan-Gauss, une matrice d'identité est formée dans le cadre de la matrice étendue. Par conséquent, un mouvement inverse n'est pas nécessaire ici.

Pour convertir la LLP canonique d'origine en LLP standard équivalente :

a) un élément non nul a qp est choisi dans la matrice étendue du système de contraintes. Cet élément est appelé permissif, et q est la ligne et p-ème colonne appelé activer la ligne et activer la colonne.

b) la chaîne permissive est réécrite sans modification et tous les éléments de la colonne permissive, à l'exception de la colonne permissive, sont remplacés par des zéros. Les éléments restants de la matrice augmentée sont déterminés à l'aide de la "règle du rectangle":

Considérons quatre éléments de la matrice développée : l'élément a ij à transformer, l'élément de résolution a qp et les éléments a i p et a qj . Pour trouver l'élément a ij, il découle de l'élément a ij de soustraire le produit des éléments a i p et a qj situés aux sommets opposés du rectangle, divisé par l'élément résolvant a qp :

c) les inconnues autorisées sont simultanément exclues de la fonction objectif. Pour ce faire, les coefficients de la fonction objectif sont écrits dans la matrice développée dans la dernière ligne. Les calculs tiennent compte du fait que l'élément d'activation de la dernière ligne ne peut pas être sélectionné.

Exemple 2. Passer au formulaire standard :

Solution.

En utilisant la méthode de Jordan-Gauss, nous amenons le système d'équations de contraintes LLP à un système équivalent d'inégalités. Choisissons le troisième élément de la première ligne comme élément de résolution :

Le nombre -9 obtenu dans la dernière colonne de la dernière ligne doit être écrit dans la fonction objectif avec le signe opposé. Suite aux transformations, le LLP prend la forme :

Parce que les variables x 2 et x 3 sont non négatives, puis en les rejetant, on peut écrire le ZLP sous une forme symétrique :

Dans la forme canonique de la LLP, la fonction objectif peut être à la fois minimisée et maximisée. Pour passer de la recherche du maximum à la recherche du minimum ou inversement, il suffit de changer les signes des coefficients de la fonction objectif : F 1 = - F. Le problème résultant et le LLP original ont la même solution optimale, et les valeurs des fonctions objectifs sur cette solution ne diffèrent que par signe.

Propriétés ZLP

1. L'ensemble de toutes les solutions admissibles du système de contraintes d'un problème de programmation linéaire est convexe.

L'ensemble des points est appelé convexe, s'il contient le segment entier reliant deux points quelconques de cet ensemble.

Selon cette définition, le polygone de la Fig. 1a est un ensemble convexe, tandis que le polygone de la Fig. 1b ne l'est pas, car le segment MN entre ses deux points M et N n'appartient pas complètement à ce polygone.

Les ensembles convexes peuvent être non seulement des polygones. Des exemples d'ensembles convexes sont le cercle, le secteur, le segment, le cube, la pyramide, etc.

2. Si le LLP a une solution optimale, alors la fonction linéaire prend la valeur maximale (minimale) à l'un des points d'angle du polyèdre de décision. Si une fonction linéaire prend une valeur maximale (minimale) à plus d'un point d'angle, alors elle la prend à n'importe quel point qui est une combinaison linéaire convexe de ces points.

Le point X est appelé combinaison linéaire convexe points X 1 , X 2 ,…, X n si les conditions suivantes sont remplies :

X \u003d α 1 X 1 + α 2 X 2 + ... + α n X n,

αj ≥ 0, Σαj = 1.

Il est évident que dans le cas particulier pour n = 2 une combinaison linéaire convexe de deux points est un segment les reliant.

3. Chaque solution de base admissible du système de contraintes canonique LLP correspond à un point d'angle du polyèdre solution, et vice versa, à chaque point d'angle du polyèdre solution correspond une solution de base admissible.

Il découle des deux dernières propriétés que si une LLP a une solution optimale, alors elle coïncide avec au moins une de ses solutions de base admissibles.

Ainsi, l'extremum de la fonction linéaire LLP doit être recherché parmi un nombre fini de ses solutions de base admissibles.

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équations 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-ième type de produit.

Les coûts du i-ème type de ressource 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.

MODÈLE DE PROGRAMMATION LINÉAIRE

1 Description mathématique modèles de programmation linéaire

2 Méthodes de mise en œuvre des modèles de programmation linéaire

3 Problème de programmation linéaire double

Modèle de programmation linéaire(LP) a lieu si dans le système étudié (objet) les restrictions sur les variables et la fonction objectif linéaire.

Les modèles LP sont utilisés pour résoudre deux principaux types de problèmes appliqués :

1) une planification optimale dans toutes les sphères de l'activité humaine - sociale, économique, scientifique, technique et militaire. Par exemple, avec une planification optimale de la production : répartition des ressources financières, de main-d'œuvre et autres, approvisionnement en matières premières, gestion des stocks, etc.

2) le problème de transport (trouver le plan optimal pour divers types de transport, le plan optimal pour la répartition de divers moyens sur des objets à diverses fins, etc.)

DESCRIPTION MATHÉMATIQUE DU MODÈLE DE PROGRAMMATION LINÉAIRE

Il est nécessaire de trouver des valeurs non négatives de variables

satisfaisant des contraintes linéaires sous forme d'égalités et d'inégalités

,

où - numéros donnés,

et fournir un extremum de la fonction objectif linéaire

,

où sont donnés des nombres, qui s'écrivent comme

Solution acceptable tout ensemble est appelé , remplissant les conditions.

Domaine des solutions admissibles est l'ensemble de toutes les solutions admissibles.

Solution optimale
, Pour qui .

Remarques

1. Le modèle LP réduit est général. Il y a aussi la norme et canonique formes de modèles LP.

2. Conditions d'existence mise en œuvre du modèle LP :

– l'ensemble des solutions admissibles n'est pas vide ;

– fonction objectif limité par (au moins par le haut lors de la recherche d'un maximum et par le bas lors de la recherche d'un minimum).

3.LP est basé sur deux théorèmes

Théorème 1. Un tas de g, défini par le système de contraintes de la forme, est un fermé convexe ( polyèdre convexe avec des points d'angle - pics.)

Théorème 2. Forme linéaire , défini sur un polyèdre convexe

j=1,2,…,s

je=s+1,s+2,…, m,

atteint un extremum à l'un des sommets de ce polyèdre.

Ce théorème est appelé théorème extremum de la forme linéaire.

Conformément au théorème de Weierstrass, la solution optimale est unique et est un extremum global.

Il existe une approche analytique généraleà la mise en œuvre du modèle LP - la méthode du simplexe. Lors de la résolution de problèmes de programmation linéaire, il n'y a souvent pas de solution. Cela se produit pour les raisons suivantes.

Illustrons la première raison par un exemple.

À propos d'une telle raison, ils disent que les restrictions sont incohérentes. Le domaine des solutions admissibles est l'ensemble vide.

La seconde raison est commentée par l'exemple suivant :

Dans ce cas, la zone des solutions réalisables n'est pas délimitée par le haut. Le domaine des solutions admissibles n'est pas limité.

Suivant les traditions de la programmation linéaire, nous donnerons au problème LP une interprétation économique. Ayons m types de ressources. Nombre de ressources de type jéquivaut à . Ces ressources sont nécessaires pour produire n types de marchandises. Désignons la quantité de ces biens par les symboles respectivement. Type d'élément je frais . Type de fabrication de biens je devrait se limiter à respectivement. Pour la production d'une unité de bien du type je type de ressource consommée j. Il est nécessaire de déterminer un tel plan pour la production de biens ( ) afin que leur coût total soit minime.

Les problèmes de programmation linéaire utilisés pour optimiser le fonctionnement d'objets réels contiennent un nombre important de variables et de contraintes. Cela rend impossible leur résolution par des méthodes graphiques. Avec un grand nombre de variables et de restrictions, des méthodes algébriques sont utilisées, qui sont basées sur des procédures de calcul itératives. En programmation linéaire, de nombreuses méthodes algébriques ont été développées qui diffèrent dans les manières de construire une solution réalisable initiale et dans les conditions de passage d'une itération à l'autre. Cependant, toutes ces méthodes reposent sur des dispositions théoriques générales.

La généralité des principales dispositions théoriques conduit au fait que les méthodes algébriques de résolution de problèmes de programmation linéaire sont largement similaires les unes aux autres. En particulier, presque chacun d'entre eux nécessite une réduction préalable d'un problème de programmation linéaire à une forme standard (canonique).

Les méthodes algébriques pour résoudre le problème LP commencent par le réduire à forme standard (canonique):

,

,

je=1,..,n;j=1,..,m.

Tout problème de programmation linéaire peut être réduit à une forme standard. Comparaison modèle général avec le modèle canonique permet de conclure que pour ramener le problème PL à la forme standard, il faut, d'une part, passer du système d'inégalités aux égalités, et d'autre part, transformer toutes les variables pour qu'elles soient non- négatif.

Le passage aux égalités s'effectue en ajoutant une variable résiduelle non négative au côté gauche des contraintes pour les inégalités de type , et en soustrayant du côté gauche une variable en excès non négative pour les inégalités de type . Par exemple, l'inégalité lors du passage à la forme standard, elle se transforme en l'égalité , et l'inégalité - à l'égalité . Dans ce cas, la variable résiduelle et la variable excédentaire sont non négatives.

On suppose que le côté droit des inégalités est non négatif. Sinon, cela peut être réalisé en multipliant les deux côtés de l'inégalité par "-1" et en changeant son signe à l'opposé.

Si dans le problème de programmation linéaire d'origine, la variable n'est pas limitée en signe, elle peut être représentée comme la différence de deux variables non négatives , où .

Une caractéristique importante des variables est-ce que pour tout solution acceptable un seul d'entre eux peut prendre une valeur positive. Cela signifie que si , ensuite et vice versa. Par conséquent, il peut être considéré comme un résidu, mais - comme une variable redondante.

Exemple Soit un problème de programmation linéaire :

,

.

Vous devez l'amener à un formulaire standard. Notez que la première inégalité du problème d'origine a le signe , il est donc nécessaire d'y introduire la variable résiduelle. En conséquence, nous obtenons.

La deuxième inégalité a un signe et pour la transformation vers la forme standard elle nécessite l'introduction d'une variable redondante , après avoir effectué cette opération, on obtient .

De plus, la variable n'est pas bornée en signe. Par conséquent, à la fois dans la fonction objectif et dans les deux contraintes, il doit être remplacé par la différence . Après avoir effectué la substitution, nous obtenons un problème de programmation linéaire sous forme standard, équivalent au problème original :

.

Le problème de la programmation linéaire, écrit sous la forme standard, est le problème de trouver l'extremum de la fonction objectif sur l'ensemble des vecteurs solutions du système d'équations linéaires, en tenant compte des conditions de non-négativité. Comme on le sait, un système d'équations linéaires peut n'avoir aucune solution, avoir une solution unique ou avoir un nombre infini de solutions. L'optimisation de la fonction objectif n'est possible que si le système a l'infini de nombreuses solutions. Un système d'équations linéaires a un nombre infini de solutions s'il est cohérent (le rang de la matrice principale est égal au rang de la matrice étendue) et si le rang de la matrice principale est inférieur au nombre de inconnues.

Soit le rang de la matrice du système de contraintes égal à m. Cela signifie que la matrice a au moins un mineur mème ordre n'est pas égal à zéro. Sans perte de généralité, on peut supposer que le mineur est situé dans le coin supérieur gauche de la matrice. Ceci peut toujours être réalisé en modifiant la numérotation des variables. Ce mineur de rang non nul m s'appelle la base. Faisons un système dès le départ méquations du système, en l'écrivant comme suit :

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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 seconde é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.