L'ensemble des solutions à un système d'inégalités linéaires. Collecte et utilisation des informations personnelles

On associe à chaque point (x 1 ,x 2 ,…x n) de l'espace à n dimensions R n un vecteur à n dimensions X=(x 1 ,x 2 ,…x n) avec le début à l'origine et la fin au point (x 1 ,x 2 ,…x n). Beaucoup de vecteurs X=(x 1,x 2,...x n) dans R n, dont les composantes satisfont m inégalités linéaires :

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

. . . . . . . . . . . . (2)

une m 1 x 1 +une m 2 x 2 +...+une m n x n ≤ b m

est appelé l’ensemble de solutions du système inégalités linéaires.

Dans la définition, toutes les inégalités s'écrivent avec le signe ≤. Multiplier par

(-1) n'importe laquelle des inégalités, vous pouvez changer son signe en l'opposé. Un ensemble de solutions est défini pour les systèmes d'inégalités linéaires de signe ³ et ≤.

Problèmes de modélisation

Sujet de théorie de la modélisation

La modélisation est le remplacement d'un objet (l'original) par un autre (le modèle) ainsi que la fixation et l'étude des propriétés du modèle. La substitution est effectuée dans le but simplification, réduire le coût, accélérer l'étude des propriétés de l'original.

DANS cas général l'objet original peut être un système naturel ou artificiel, réel ou imaginaire. Il possède de nombreux paramètres et se caractérise par certaines propriétés. Une mesure quantitative des propriétés d'un système est fournie par de nombreuses caractéristiques ; le système présente ses propriétés sous l'influence d'influences externes.

De nombreux paramètres et leurs valeurs reflètent son interne contenu - structure et principes de fonctionnement. Les caractéristiques sont fondamentalement elle signes extérieurs qui sont importants lors de l’interaction avec les autres.

La modélisation est conseillée lorsque le modèle ne présente pas les caractéristiques de l'original qui entravent son étude.

La théorie de la modélisation est un ensemble interconnecté de dispositions, de définitions, de méthodes et de moyens de création de modèles. Les modèles eux-mêmes font l'objet de la théorie de la modélisation.

La théorie de la modélisation est la composante principale théorie générale systèmes - systémologie, où les modèles réalisables sont postulés comme principe principal : un système peut être représenté par un ensemble fini de modèles, dont chacun reflète une certaine facette de son essence.

Le rôle et la place de la modélisation dans la recherche sur les systèmes.

La connaissance de tout système () se résume essentiellement à créer son modèle. Avant la fabrication de chaque appareil ou structure, son modèle-projet est élaboré. Toute œuvre d'art est un modèle qui capture la réalité.

Les progrès des mathématiques ont conduit à la diffusion de modèles mathématiques de divers objets et processus. On constate que la dynamique de fonctionnement de systèmes de nature physique différente présente le même type de dépendances, ce qui permet de les simuler sur PC.

Classement des modèles

Modèles physiques. La classification est basée sur le degré d'abstraction du modèle par rapport à l'original. Auparavant, tous les modèles pouvaient être divisés en 2 groupes : physiques et abstraits (mathématiques).

F.M. fait généralement référence à un système équivalent ou similaire à l’original, mais éventuellement de nature physique différente. Types de FM :

Naturel;

Quasi-naturel ;

Grande échelle;

Analogique;

Modèles naturels- ce sont des systèmes réels à l'étude (maquettes, prototypes). Ils sont parfaitement adaptés (correspondance) au système d'origine, mais sont coûteux.

Modèles quasi naturels- un ensemble de modèles naturels et mathématiques. Ce type est utilisé lorsque le modèle d'une partie du système ne peut être mathématique en raison de la complexité de sa description (modèle de l'opérateur humain) ou lorsqu'une partie du système doit être étudiée en interaction avec d'autres parties, mais qu'elles n'existent pas encore ou que leur l'inclusion est très coûteuse (polygones informatiques, ACS).

Un modèle réduit est un système de même nature physique que l’original, mais qui en diffère par son échelle. Base méthodologique la modélisation à l’échelle est la théorie de la similarité. Lors de la conception d'avions, des modèles réduits peuvent être utilisés pour analyser les options de solutions d'aménagement.

Modèles analogiques on appelle systèmes ceux qui ont une nature physique différente de l'original, mais qui fonctionnent comme des processus similaires à l'original. Pour créer un modèle analogique, une description mathématique du système étudié est nécessaire. Les systèmes mécaniques, hydrauliques, pneumatiques et électriques sont utilisés comme modèles analogiques. La modélisation analogique est utilisée lors de l'étude des équipements VT au niveau des éléments logiques et circuits électriques, ainsi qu'au niveau du système, lorsque le fonctionnement du système est décrit, par exemple, par des équations différentielles ou algébriques.

Modèles mathématiques. Les modèles mathématiques sont une représentation formalisée d'un système utilisant un langage abstrait, utilisant des relations mathématiques qui reflètent le processus de fonctionnement du système. Pour compiler un modèle mathématique, vous pouvez utiliser n'importe quel moyen mathématique - calcul algébrique, différentiel, intégral, théorie des ensembles, théorie des algorithmes, etc. Essentiellement, toutes les mathématiques ont été créées pour compiler et étudier des modèles d’objets et de processus.

Les moyens de description abstraite des systèmes incluent également les langages formules chimiques, diagrammes, dessins, cartes, diagrammes, etc. Le choix du type de modèle est déterminé par les caractéristiques du système étudié et les objectifs de la modélisation, car L'étude du modèle permet d'obtenir des réponses à un certain groupe de questions. Pour obtenir des informations différentes, des informations différentes peuvent nécessiter un type de modèle différent. Les modèles mathématiques peuvent être classés en déterministes et probabilistes, analytiques, numériques et simulation.

Modèle analytique Il s'agit d'une description formalisée d'un système qui vous permet de résoudre explicitement l'équation à l'aide d'un appareil mathématique bien connu.

Modèle numérique caractérisé par une dépendance d'un type qui ne permet que des solutions partielles pour des conditions initiales spécifiques et des paramètres quantitatifs des modèles.

Modèle de simulation- il s'agit d'un ensemble de descriptions du système et des influences externes, d'algorithmes de fonctionnement du système ou de règles de changement d'état du système sous l'influence de perturbations externes et internes. Ces algorithmes et règles ne permettent pas d'utiliser les méthodes mathématiques existantes à des fins analytiques et solution numérique, mais ils permettent de simuler le processus de fonctionnement du système et de calculer les caractéristiques d'intérêt. Des modèles de simulation peuvent être créés pour une classe d’objets et de processus beaucoup plus large que les modèles analytiques et numériques. Étant donné que les ordinateurs sont utilisés pour mettre en œuvre des modèles de simulation, des langages algorithmiques universels et spéciaux servent de moyen de description formalisée de ceux-ci. Ils sont les plus adaptés à l’étude des avions au niveau du système.

Considérons un certain nombre de problèmes dans lesquels il est nécessaire de trouver le domaine de solution d'un système d'inégalités linéaires.

Exemple 1:

X1 + 3x2 ≤ 6

x 1 - x 2 ≤ 2

L'ensemble de solutions requis correspond à la zone ombrée. Les sommets de l'ensemble de solutions sont trois points (0,2), (0,-2) et (3,1). Ce sont les points d’intersection des lignes qui limitent l’ensemble des solutions.

Dans cet exemple, l’ensemble solution est un ensemble convexe polyédrique.

Exemple 2 : Dessinez l’ensemble des solutions du système d’inégalités linéaires suivant dans R².

X 1 + 2x 2 ≤ 4

3x1 + 2x2 ≤ 6

Les sommets de l'ensemble souhaité sont deux points de coordonnées : (0,2) et (1/2, 9/4). Le point de coordonnée (0,3) n'est pas un sommet, puisqu'il ne satisfait pas la première inégalité. Cet ensemble de solutions est illimité.

Solution Exemple 3 : Dessinez l’ensemble des solutions du système d’inégalités linéaires suivant dans R².

X 1 - x 2 ³ 1

x1 + x2 ≤ 1

La solution aux première et deuxième inégalités sont les points du secteur inférieur ombré. La solution à la troisième inégalité réside dans les points du demi-plan supérieur ombré. Puisque ces deux domaines n’ont pas de points communs, alors l’ensemble du système d’inégalités n’a pas de solution, c’est-à-dire que la solution est Æ.

Le principal problème de la programmation linéaire.

DANS vue générale Le problème de programmation linéaire (LPP) est formulé comme suit.

Trouver un vecteur X=(x 1,x 2, ... x n) dans R n, qui maximise (ou minimise) la fonction objectif

F(x)=с 1 x 1 +с 2 x 2 +... +с n x n (3)

et satisfait m+n inégalités linéaires :

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

une 21 x 1 +une 22 x 2 +...+une 2n x n ≤ b 2

. . . . . . . . . . . . (4)

une m1 x 1 +une m2 x 2 +...+une mn x n ≤ b m

x 1 ³0, x 2 ³0, ... x n ³0

Dans la terminologie de programmation, la fonction linéaire F(x) est appelée fonction objectif du problème. L'ensemble des solutions du système d'inégalités linéaires (4) est appelé l'ensemble des solutions admissibles, et tout vecteur Xà partir de cet ensemble est appelée une solution réalisable. La solution optimale est le vecteur X*, à laquelle la fonction objectif prend sa valeur maximale (ou minimale) sur l'ensemble admissible de solutions.

Méthode graphique pour résoudre des problèmes de programmation linéaire. Montrons comment ce problème est résolu en utilisant la méthode graphique (géométrique). Pour ce faire, nous nous limitons à considérer un système d’inégalités linéaires à deux inconnues.

Soit la fonction objectif F=c 1 x 1 +c 2 x 2 +c 0. Trouvons parmi l'ensemble des points (x 1, x 2) de la région des solutions admissibles du système joint d'inégalités (4) (contenant uniquement les variables x 1 et x 2) ceux qui donnent fonction linéaire F est la plus petite (la plus grande) valeur. Pour chaque i –ème point du plan, la fonction F prend une valeur fixe F=F i . L'ensemble de tous ces points auxquels la fonction F prend la même valeur F i est une ligne droite avec 1 x 1 + c 2 x 2 + c 0 = F i = const, perpendiculaire à un vecteur appelé gradient F (grad F ). Ce vecteur sort de l'origine et a pour coordonnées grad F = (c 1,c 2). Selon la propriété du vecteur grad F, si la droite spécifiée est déplacée parallèlement à elle-même dans la direction positive du vecteur grad F, alors la valeur de la fonction objectif F=c 1 x 1 +c 2 x 2 +c 0 sur cette droite augmentera, et dans le sens opposé il diminuera.

Laissez la droite F=const se déplacer dans la direction positive du vecteur grad F pour la première fois lorsque cette droite rencontre le polygone des solutions admissibles à son sommet. Alors dans cette position F 1 la ligne F=const est appelée ligne support, et sur cette ligne la fonction F prend plus petite valeur. Avec un mouvement ultérieur dans la même direction (positive), la droite F=const passera par un autre sommet du polygone des solutions réalisables et, en quittant la zone de solution, deviendra également la droite de référence F 2 . Là-dessus, la fonction F prend valeur la plus élevée parmi toutes les valeurs acceptées sur le polygone des solutions réalisables. Ainsi, la minimisation et la maximisation de la fonction objectif F=c 1 x 1 +c 2 x 2 +c 0 sur le polygone des solutions réalisables sont réalisées aux points d'intersection de ce polygone avec les droites de référence F=c 1 x 1 + c 2 x 2 +c 0 = const, normal au vecteur grad F=(с 1 , с 2). Cette intersection de la ligne de référence avec l'ensemble des solutions réalisables peut se faire soit en un point (le sommet du polygone), soit en un ensemble infini de points (s'il s'agit de l'ensemble des côtés du polygone).

La tâche pour la première, la deuxième, la troisième tâche est sélectionnée par le nom, le prénom et le patronyme de l'élève, et pour la quatrième tâche est sélectionnée par le nom et le patronyme de l'élève.

Tâche n°1

Tableau 1

Première lettre

Nom de famille

Nom

Nom de famille

un 11

un 12

un 21

un 2 2

un 31

un 32

un 41

un 4 2

DANS

À PROPOS

AVEC

YuYa

Exemple 4 : Minimiser la forme linéaire F=14x 1 +4x 2 sous les contraintes :

7x 1 + 2x 2³ 14

4 x 1 –7x 2 ≤ 14

En remplaçant les signes d'inégalité par des signes d'égalité exacte, nous obtenons des équations pour les limites de la région des solutions réalisables. A l'aide des équations des droites obtenues, on construit l'aire souhaitée :

7x1 +2x2 =14

4 x 1 – 7 x 2 = 14

Le domaine des solutions admissibles au système d'inégalités est le polygone ABCDE.

Figure 5.

Pour trouver les points extremum, on construit une droite F=14x 1 +4x 2 =0 et un vecteur gradF = (14, 4). Nous allons déplacer la droite F=0 parallèlement à elle-même dans la direction du vecteur grad F. Cette droite rencontrera d'abord le polygone ABCDE aux points E(2,0) et A(10/9, 28/9), où la fonction objectif prend la même valeur minimale F(E) = F(A) =14·2+4∙0=28-min, (puisque le vecteur grad F est perpendiculaire à la droite AE). Ainsi, la fonction objectif prend sa valeur minimale en tout point du segment AE.

Du plan le principal problème de programmation linéaire est que le nombre de ses composantes positives ne dépasse pas .

Un plan de soutien est dit non dégénéré s’il contient exactement des composantes positives ; sinon le plan est dégénéré.

Toutes les variables système équations linéaires avec des variables (sous réserve de ) sont appelés basiques si le déterminant de la matrice de coefficients pour eux est différent de zéro. Ensuite, les variables restantes sont dites non primaires.

La solution de base d'un système de m équations linéaires avec variables est toute solution dans laquelle toutes les variables non fondamentales ont des valeurs nulles.

Théorème 1. L'ensemble de toutes les solutions réalisables au système de contraintes d'un problème de programmation linéaire est convexe.

Théorème 2. Si un problème de programmation linéaire a une solution optimale, alors elle coïncide avec le point central de l’ensemble des solutions réalisables.

Conséquence. Si la solution optimale n'est pas unique, alors il existera de nombreuses solutions de ce type (par exemple, tous les points du segment reliant les points d'angle correspondants).

Théorème 3. Chaque solution de base admissible d'un problème de programmation linéaire correspond à un point angulaire de la région des valeurs admissibles, et vice versa.

Le concept de la méthode simplexe.

La résolution du principal problème de programmation linéaire à l'aide de la méthode géométrique permet d'obtenir une grande clarté dans le cas de 2 et 3 variables. Pour le même cas plus variables, la méthode géométrique devient impossible. La méthode dite du simplexe est l'une des méthodes analytiques permettant de résoudre le problème de base de la programmation linéaire. Dans ce cas, les restrictions utilisées lors de la mise en œuvre de la méthode du simplexe sont généralement spécifiées par un système d'équations linéaires

UNE 11 x 1 +une 12 x 2 +...+une 1n x n = b 1

une 21 x 1 +une 22 x 2 +...+une 2n x n = b 2

. . . . . . . . . . . . (5)

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

parmi les solutions non négatives dont on recherche celles qui maximiseraient la fonction linéaire (objectif)

F=с 1 x 1 +с 2 x 2 +...+с n x n +с 0

La méthode du simplexe est basée sur les théorèmes :

Théorème 1. Si le ZLP a une solution optimale, alors la fonction objectif prend une valeur extrême à l'un des coins du polygone convexe des solutions réalisables.

Théorème 2. Chaque solution support de la ZLP correspond à un point d'angle du polygone des solutions réalisables et vice versa.

Sur la base de ces théorèmes, lors de la mise en œuvre de la méthode du simplexe, une recherche ciblée de tous les sommets est effectuée de sorte que dans chaque sommet suivant la valeur de la fonction objectif ne soit pas inférieure (pas plus) que dans le sommet précédent. En même temps, pour numéro finalétapes, la solution optimale souhaitée est obtenue, ou il est établi que le ZLP est insoluble.

Pour mettre en œuvre l'algorithme spécifié, on sélectionne dans le système (5) max un ensemble de variables linéairement indépendantes (celles pour lesquelles le déterminant composé de coefficients devant ces variables est différent de 0). Pour plus de précision, soit les variables x 1, x 2,... x r (r ≤ m). Exprimons ces variables en termes des variables restantes

X 1 = une" 1, r +1 x r+1 + ... + une" 1 n x n + b 1 "

x 2 = a" 2, r +1 x r+1 + ... + a" 2 n x n + b 2 "(6)

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

x r = a" r, r +1 x r+1 + ... + a" r n x n + b r "

De plus, nous supposerons que tous b 1 "³0, b 2 "³0, b r "³0. Si les conditions restrictives initiales sont spécifiées par des inégalités, alors elles peuvent être transformées sous la forme (5) en introduisant de nouvelles variables non négatives, ceux dits d'équilibre (nivellement). Ainsi, par exemple, dans l'inégalitéa 1 x 1 +a 2 x 2 +...+a n x n ≤ b il suffit d'ajouter au côté gauche de l'inégalité une valeur x n + 1 ³ 0 égal à la différence entre les côtés droit et gauche de l'inégalité et on obtient l'égalité a 1 x 1 + a 2 x 2 +…+a n x n + x n +1 = b. Si les conditions restrictives sont spécifiées dans un mélange manière, c'est-à-dire par des inégalités et des équations, alors de la manière indiquée, elles peuvent également être réduites uniquement à des équations.

Dans le système résultant (6), les variables (inconnues) x 1, x 2 ... x z sont appelées de base, et l'ensemble entier (x 1, x 2 ... x z) est appelé une base, les variables restantes sont appelé gratuitement. Le système de restrictions (6) est appelé système réduit à l'unité. En substituant dans la fonction objectif F au lieu des variables de base leurs expressions par celles libres du système (6), on obtient

F = C 0 + C g+1 x g+1 + … + C n x n

Maintenant, en supposant que toutes les variables libres sont égales à zéro, on retrouve les valeurs des variables de base :

x 1 =b 1 ", x 2 = b 2" , ... x r =b r "

La solution admissible du système (6) ainsi obtenue

(b 1", b 2 ", ... b r ", 0, ... 0) est dit basique. Pour cette solution basique, la valeur de la fonction objectif sera égale à F B = C 0.

La résolution du problème par la méthode du simplexe se divise en un certain nombre d'étapes, consistant dans le fait que d'une base donnée B on passe à une autre base B" de telle sorte que la valeur de F B sur la nouvelle base augmente ou, au moins , ne diminue pas, alors est rempli F B "≥ F B. De plus, si tout b 1 ">0, b 2 ">0,…., b r ">0, alors cette solution est appelée référence et correspond à certains coin domaine de solutions réalisables déterminé par le système de contraintes d'origine. Alors le passage d'une solution de base (de référence) à une autre correspond au passage d'un sommet du polygone des solutions réalisables à un autre sommet.

TÂCHE N°2

Pour vendre trois groupes de biens, une entreprise commerciale dispose de trois types de matières organiques et de ressources monétaires d'un montant de , , unités. Dans le même temps, pour la vente d'un groupe de marchandises pour 1 000 roubles. la consommation du chiffre d'affaires des marchandises a été perdue en nombre d'unités, la ressource du deuxième type en nombre d'unités, la ressource du troisième type en nombre d'unités. Pour la vente de 2 et 3 groupes de marchandises pour 1 000 roubles. le chiffre d'affaires des marchandises est dépensé en fonction de la ressource du premier type d'un montant de , unités, des ressources du deuxième type d'un montant de , unités, des ressources du troisième type d'un montant de , unités. Bénéficiez de trois groupes de produits pour 1 000 roubles. le chiffre d'affaires est respectivement de , , (milliers de roubles).

Déterminez le volume et la structure prévus du chiffre d'affaires commercial afin que le profit de l'entreprise commerciale soit maximisé.

Première lettre

Nom de famille

Nom

Nom de famille

DANS

1 0

À PROPOS

AVEC

ELLE

Yu Ya

Exemple 5 : Maximisez la fonction objectif F=-x 4 +x 5 sous les restrictions :

Ce système d'équations est cohérent, puisque les rangs de la matrice système

et matrice étendue

coïncident et sont égaux à 3. En exprimant les variables de base (en colonnes unitaires) x 1, x 2, x 3, à travers les variables libres x 4 et x 5, on arrive au système

(7)

En plus du système (7), on peut exprimer les variables de base à travers des variables libres et dans la fonction objectif (dans notre exemple, F = -x 4 + x 5 est déjà exprimé à travers les variables libres x 4 et x 5). En supposant maintenant x 4 = 0, x 5 =0, nous trouvons les variables de base : x 1 =1, x 2 =2, x 3 =3. Ainsi, la première solution de base réalisable du système d’équations est (1, 2, 3, 0, 0) . Lorsqu'une solution admissible est trouvée, la fonction objectif F a la valeur 0, c'est-à-dire F 1 =0.

Essayons maintenant d'augmenter la valeur de F 1. Une augmentation de x 4 diminuera F 1, car avant x 4 dans l'expression F = -x 4 + x 5 il y a un coefficient négatif, et une augmentation de x 5 donne une augmentation de F 1. Par conséquent, nous augmentons x 5 pour que x 1, x 2, x 3 ne deviennent pas négatifs, laissant x 4 = 0. À partir de la deuxième équation (7), nous voyons que x 5 peut être augmenté jusqu'à 2 (de sorte que x 2 reste 0, avec x 4 = 0). La valeur des variables sera alors (5, 0, 1, 0, 2) et la valeur de F 2 = 2. Comme vous pouvez le voir, la valeur de F a augmenté dans la deuxième étape.

Puisque x 2 et x 4 se sont avérés égaux à 0, alors nous prendrons en outre x 2 et x 4 comme inconnues libres, alors x 5 = 2x 2 + 2x 4

et du système (7) on passe à son système équivalent (8)

(8)

De plus, F dans ce cas sera égal

F = 2x2 +x4

Pour augmenter F, nous augmenterons x 4 (puisque x 2 est précédé d'un coefficient négatif). D'après la deuxième équation du système (8), il est clair que, à condition que x 3 soit non négatif, la valeur de x 4 peut être ramené à x 4 = 1/5, alors on a (28/5 , 0, 0, 1/5, 12/5), F 3 =11/5.

Puisque la solution obtenue x 2 = x 3 = 0, on prend x 2 et x 3 comme variables libres et on exprime x 1, x 4, x 5, par x 2 et x 3. On obtient

X1 = 28/5 - 7/5x2 - 3/5x3

x 4 = 1/5 + 1/5 x 2 – 1/5 x 3

x 5 = 12/5 – 3/5 x 2 – 2/5 x 3

avec F = 11/5 – 4/5 x 2 – 1/5 x 3

Puisque les coefficients de x 2 et x 3 dans l'expression de F sont négatifs, il n'est plus possible d'augmenter la valeur de F. Par conséquent, en mettant x 2 = x 3 = 0, nous obtenons la plus grande valeur F = 11/5 lors de la résolution de (28/5, 0, 0, 1/5, 12/5)

Répondre: F max = 11/5 à X* = (28/5, 0, 0, 1/5, 12/5)

Tableaux simplexes.

Étant donné que la résolution du ZLP à l'aide d'un tel raisonnement, comme cela a été fait dans l'exemple précédent, est clairement peu pratique pour un enregistrement compact de la solution, et des tables dites simplex sont utilisées pour pouvoir programmer l'algorithme de solution sur un ordinateur. Pour ce faire, nous réduisons le système de restrictions à l'unité.

x 1 + une 1, r +1 x r+1 + ... + une 1 n x n = b 1

x je + une je,r+1 x r+1 + .... + une je n x n = b je (9)

x r + a r,r+1 x r+1 + ... + a r n x n = b r

et la fonction objectif F - sous la forme :

F = C g+1 x r +1 + ... + C j x j +…+ C n x n + C 0 (10)

Nous appellerons égalité (10) une expression réduite (aux variables libres) pour la fonction F et les coefficients C j – estimations (indices) des variables libres correspondantes x j.

Les coefficients du système de restrictions ci-dessus (9), ainsi que diverses variables auxiliaires sont saisis dans un tableau simplex (tableau 1)

Tableau 1

Variables de base

Membres gratuits

...

x je

...

xg+1

...

une 1,r+1

...

un 1j

...

un 1n

...

x je

b je

...

et je,r+1

...

un ij

...

un dans

...

b r

...

et r,r+1

...

un RJ

...

arn

C 0

...

- Cg+1

...

-Cj

...

-Cn

Les r premières colonnes avec des inconnues x i sont des colonnes unitaires avec des variables de base x 1 ,…,x r . Suivant n-r les colonnes sont des colonnes avec des variables libres x r +1 ,…,x n . En supposant des variables libres x r +1 = …=

X n = 0, on retrouve les variables de base x 1 = b 1,…, x r = b r. Dans ce cas, la valeur de la fonction objectif est F = C 0 .

Le plan vectoriel trouvé X 1 = et la valeur de la fonction objectif F = C 0 correspondent à un sommet du polygone des solutions réalisables. Le passage à un autre sommet et, par conséquent, à un autre plan vectoriel et à une autre valeur de la fonction objectif s'effectue en recalculant cette table simplexe.

ÉQUATIONS LINÉAIRES ET INÉGALITÉS I

§ 23 Systèmes d'inégalités linéaires

Un système d’inégalités linéaires est tout ensemble de deux ou plusieurs inégalités linéaires contenant la même quantité inconnue.

Des exemples de tels systèmes incluent les systèmes suivants :

Résoudre un système d'inégalités signifie trouver toutes les valeurs de la quantité inconnue pour lesquelles chaque inégalité du système est satisfaite.

Résolvons les systèmes ci-dessus.

Plaçons deux droites numériques l'une en dessous de l'autre (Fig. 31) ; en haut, nous marquons ces valeurs X , pour lequel la première inégalité est satisfaite ( X > 1), et en bas ces valeurs X , pour lequel la deuxième inégalité est satisfaite ( X > 4).

En comparant les résultats sur les droites numériques, nous remarquons que les deux inégalités seront simultanément satisfaites lorsque X > 4. Répondez, X > 4.

La première inégalité donne -3 X < -б, или X > 2, et le deuxième - X > -8, ou X < 8. Далее поступаем так же, как и в первом примере. На одной числовой прямой отмечаем все те значения X , pour lequel la première inégalité du système est satisfaite, et sur la deuxième droite numérique, située sous la première, toutes ces valeurs X , pour lequel la deuxième inégalité du système est satisfaite (Fig. 32).

Une comparaison de ces deux résultats montre que les deux inégalités seront valables simultanément pour toutes les valeurs X , compris entre 2 et 8. L'ensemble de ces valeurs X écrit comme double inégalité 2< X < 8.

Exemple 3. Résoudre le système d'inégalités

La première inégalité du système donne 5 X < 10, или X < 2, второе X > 4. Ainsi, tout nombre qui satisfait simultanément les deux inégalités ne doit pas être supérieur à 2 et supérieur à 4 (Fig. 33).

Mais de tels chiffres n’existent pas. Par conséquent, ce système d’inégalités ne s’applique à aucune valeur X . De tels systèmes d'inégalités sont appelés incohérents.

Des exercices

Résolvez ces systèmes d'inégalités (n° 179-184) :

Résoudre les inégalités (No. 185, 186) :

185. (2X + 3) (2 - 2X ) > 0. 186. (2 - π ) (2X - 15) (X + 4) > 0.

Trouver valeurs valides lettres incluses dans les données sur l'égalité (n ° 187, 188):

Résoudre les inégalités (No. 189, 190) :

189. 1 < 2X - 5 < 2. 190. -2 < 1 - Oh < 5.

191. Quelle doit être la température de 10 litres d'eau pour les mélanger avec 6 litres d'eau à une température de 15° pour obtenir une eau à une température d'au moins 30° et pas plus de 40° ?

192. Un côté du triangle mesure 4 cm et la somme des deux autres est 10 cm. Trouvez ces côtés s'ils sont exprimés en nombres entiers.

193. On sait que le système de deux inégalités linéaires n'est satisfait pour aucune valeur de la quantité inconnue. Pouvons-nous dire que les inégalités individuelles de ce système ne sont satisfaites pour aucune valeur de la quantité inconnue ?

Méthode graphique.. 3

Méthode simplexe.. 6

Méthode de base artificielle... 8

Le principe de dualité.. 10

Liste de la littérature utilisée... 12

Introduction

Certaines propriétés des systèmes d'inégalités linéaires ont été considérées dès la première moitié du XIXe siècle en relation avec certains problèmes de mécanique analytique. L'étude systématique des systèmes d'inégalités linéaires a commencé à la toute fin du XIXe siècle, mais il n'est devenu possible de parler de théorie des inégalités linéaires qu'à la fin des années vingt du XXe siècle, lorsqu'un nombre suffisant de résultats les concernant ont eu déjà accumulé.

Or, la théorie des systèmes finis d'inégalités linéaires peut être considérée comme une branche de l'algèbre linéaire, qui en est issue avec l'exigence supplémentaire d'ordonner le champ des coefficients.

Les inégalités linéaires sont particulièrement important pour les économistes, car c'est à l'aide d'inégalités linéaires que l'on peut modéliser les processus de production et trouver les plans de production, de transport, d'allocation des ressources les plus rentables, etc.

Cet article présentera les méthodes de base pour résoudre les inégalités linéaires appliquées à des problèmes spécifiques.

Méthode graphique

La méthode graphique consiste à construire un ensemble de solutions admissibles au PLP, et à trouver dans cet ensemble le point correspondant à la fonction objectif max/min.

En raison de handicapées pour une représentation graphique visuelle, cette méthode n'est utilisée que pour les systèmes d'inégalités linéaires à deux inconnues et les systèmes pouvant être réduits à cette forme.

Afin de démontrer clairement méthode graphique, résolvons le problème suivant :

Dans un premier temps, il est nécessaire de construire une région de solutions réalisables. Pour cet exemple, il est plus pratique de sélectionner X2 comme abscisse et X1 comme ordonnée, et d'écrire les inégalités sous la forme suivante :

les graphiques et la zone de solutions réalisables se situent au premier trimestre.

Afin de trouver les points limites, nous résolvons les équations (1)=(2), (1)=(3) et (2)=(3).

Comme le montre l’illustration, le polyèdre ABCDE forme une région de solutions réalisables.

Si la région des solutions réalisables n'est pas fermée, alors soit max(f)=+ ∞ soit min(f)= -∞.

Nous pouvons maintenant procéder à la recherche directe du maximum de la fonction f.

En substituant alternativement les coordonnées des sommets du polyèdre dans la fonction f et en comparant les valeurs, on constate que

f(C)=f(4;1)=19 – maximum de la fonction.

Cette approche est très bénéfique avec un petit nombre de sommets. Mais cette procédure peut prendre beaucoup de temps s'il y a beaucoup de sommets.

Dans ce cas, il est plus pratique de considérer une ligne de niveau de la forme f=a. Avec une augmentation monotone du nombre a de -∞ à +∞, les droites f=a se déplacent le long du vecteur normal. Si, avec un tel mouvement de la ligne de niveau, il existe un certain point X - le premier point commun de la région des solutions réalisables (polyèdre ABCDE) et de la ligne de niveau, alors f(X) est le minimum de f sur l'ensemble ABCDE. Si X est le dernier point d'intersection de la ligne de niveau et de l'ensemble ABCDE, alors f(X) est le maximum sur l'ensemble des solutions réalisables. Si, comme a→-∞, la droite f=a coupe l'ensemble des solutions réalisables, alors min(f)= -∞. Si cela se produit sous la forme a→+∞, alors

Dans notre exemple, la droite f=a coupe la zone ABCDE au point C(4;1). Puisqu'il s'agit du dernier point d'intersection, max(f)=f(C)=f(4;1)=19.

Méthode simplexe

Les vrais problèmes de programmation linéaire impliquent très grand nombre restrictions et inconnues et sont exécutés sur un ordinateur. La méthode du simplexe est l’algorithme le plus général utilisé pour résoudre de tels problèmes. L'essence de la méthode est qu'après un certain nombre de transformations simplesx spéciales, le ZLP est réduit à type spécial, autorisé. Afin de démontrer la méthode du simplexe en action, résolvons le problème suivant accompagné de commentaires :

Afin de commencer à résoudre le problème par la méthode simplex, vous devez présenter le problème sous un formulaire spécial et remplir le tableau simplex.

Le système (4) constitue une limitation naturelle et ne rentre pas dans le tableau. Les équations (1), (2), (3) forment la région des solutions réalisables. L'expression (5) est la fonction objectif. Les termes libres dans le système de restrictions et la zone de solutions admissibles doivent être non négatifs.

Dans cet exemple, X3, X4, X5 sont les inconnues de base. Ils doivent être exprimés en termes d'inconnues libres et remplacés dans la fonction objectif.

Vous pouvez maintenant commencer à remplir le tableau simplex :

B.	X1	X2	X3	X4	X5	C
X3	0	-1	1	1	0	1
X4	0	1	-1	0	1	1
X5	1	1	1	0	0	2
F	0	-6	7	0	0	3

La première colonne de ce tableau indique les inconnues de base, la dernière - les valeurs des inconnues libres et le reste - les coefficients des inconnues.

Afin de trouver le maximum de la fonction f, à l'aide des transformations gaussiennes, vous devez vous assurer que tous les coefficients des inconnues de la dernière ligne sont non négatifs (pour trouver le minimum, assurez-vous que tous les coefficients sont inférieurs ou égaux à zéro).

B	X1	X2	X3	X4	X5	C
X3	-1	1	1	0	0	1
X4	1	-1	0	1	0	1
X5	1	1	0	0	1	2
F	-6	7	0	0	0	3

Pour cela, sélectionnez la colonne à coefficient négatif dans la dernière ligne (colonne 3) et composez la relation terme libre/coefficient (1/1 ; 2/1) pour les éléments positifs de cette colonne. Parmi ces ratios, sélectionnez le plus petit et marquez la ligne correspondante.

Nous avons sélectionné l'élément dans la cellule (3;3). Maintenant, en utilisant la méthode gaussienne, nous réinitialisons les autres coefficients de cette colonne, cela conduit à un changement de base et nous nous rapprochons de la solution optimale.

B	X1	X2	X3	X4	X5	C
X3	0	0	1	1	0	2
X1	1	-1	0	1	0	1
X5	0	2	0	-1	1	1
F	0	1	0	6	0	9

Comme le montre le tableau, tous les coefficients de la dernière ligne sont désormais supérieurs ou égaux à zéro. Cela signifie que nous avons trouvé la valeur optimale. Les inconnues libres sont égales à zéro, la valeur des inconnues de base et le maximum de la fonction f correspondent aux valeurs des inconnues libres.

Définition 1 . Ensemble de points dans l'espace R. n , dont les coordonnées satisfont à l'équation UN 1 X 1 + un 2 X 2 +…+ un n X n = b, appelé ( n - 1 )-hyperplan dimensionnel dans n-espace dimensionnel.

Théorème 1. Un hyperplan divise tout l'espace en deux demi-espaces. Un demi-espace est un ensemble convexe.

L'intersection d'un nombre fini de demi-espaces est un ensemble convexe.

Théorème 2 . Résoudre une inégalité linéaire avec n inconnu

UN 1 X 1 + un 2 X 2 +…+ un n X n b

est l'un des demi-espaces dans lesquels l'espace entier est divisé par un hyperplan

UN 1 X 1 + UN 2 X 2 +…+un n X m= b.

Considérons un système de m inégalités linéaires avec n inconnu.

La solution à chaque inégalité du système est un certain demi-espace. La solution du système sera l'intersection de tous les demi-espaces. Cet ensemble sera fermé et convexe.

Résolution de systèmes d'inégalités linéaires

avec deux variables

Laissez un système de m inégalités linéaires à deux variables.

La solution de chaque inégalité sera l’un des demi-plans dans lesquels le plan entier est divisé par la droite correspondante. La solution du système sera l’intersection de ces demi-plans. Ce problème peut être résolu graphiquement sur un plan X 1 0 X 2 .

37. Représentation d'un polyèdre convexe

Définition 1. Fermé convexe ensemble limité dans R. n ayant un nombre fini points d'angle, est appelé convexe n-polyèdre dimensionnel.

Définition 2 . Fermé convexe illimité mis en place R. n ayant un nombre fini de points d’angle est appelé une région polyédrique convexe.

Définition 3 . Un tas de UNR. n est dit borné s’il existe n-boule dimensionnelle contenant cet ensemble.

Définition 4. Une combinaison linéaire convexe de points est l'expression où t i , .

Théorème (un théorème sur la représentation d'un polyèdre convexe). Tout point d'un polyèdre convexe peut être représenté comme une combinaison linéaire convexe de ses points d'angle.

38. Région des solutions admissibles d'un système d'équations et d'inégalités.

Laissez un système de méquations linéaires et inégalités avec n inconnu.

Définition 1 . Point R. n est appelé une solution possible du système si ses coordonnées satisfont aux équations et inégalités du système. L’ensemble de toutes les solutions possibles est appelé zone de solutions possibles (PSA) du système.

Définition 2. Une solution possible dont les coordonnées sont non négatives est appelée solution réalisable du système. L’ensemble de toutes les solutions réalisables est appelé le domaine de solutions réalisables (ADA) du système.

Théorème 1 . Un ODR est un sous-ensemble fermé, convexe, délimité (ou non limité) dans R. n.

Théorème 2. Une solution admissible du système est une solution de référence si et seulement si ce point est un point angulaire de l'ODS.

Théorème 3 (le théorème sur la représentation de l'ODR). Si l'ODD est un ensemble borné, alors toute solution réalisable peut être représentée comme une combinaison linéaire convexe des points d'angle de l'ODD (sous la forme d'une combinaison linéaire convexe solutions de support systèmes).

Théorème 4 (le théorème sur l'existence d'une solution support du système). Si le système a au moins une solution admissible (ADS), alors parmi les solutions admissibles il y a au moins une solution de référence.

voir aussi Résolution graphique d'un problème de programmation linéaire, Forme canonique des problèmes de programmation linéaire

Le système de contraintes pour un tel problème est constitué d'inégalités en deux variables :
et la fonction objectif a la forme F = C 1 X + C 2 oui qui doit être maximisé.

Répondons à la question : quelles paires de nombres ( X; oui) les solutions au système d'inégalités, c'est-à-dire satisfont-elles simultanément chacune des inégalités ? En d’autres termes, que signifie résoudre graphiquement un système ?
Vous devez d’abord comprendre quelle est la solution d’une inégalité linéaire à deux inconnues.
Résoudre une inégalité linéaire à deux inconnues signifie déterminer toutes les paires de valeurs inconnues pour lesquelles l'inégalité est vraie.
Par exemple, l'inégalité 3 X – 5oui≥ 42 satisfont les paires ( X , oui) : (100, 2); (3, –10), etc. La tâche est de trouver toutes ces paires.
Considérons deux inégalités : hache + par≤ c, hache + par≥ c. Droit hache + par = c divise le plan en deux demi-plans pour que les coordonnées des points de l'un d'eux satisfassent à l'inégalité hache + par >c, et l'autre inégalité hache + +par <c.
En effet, prenons un point de coordonnée X = X 0 ; puis un point situé sur une droite et ayant une abscisse X 0, a une ordonnée

Laissez pour certitude un< 0, b>0, c>0. Tous les points en abscisse X 0 situé au-dessus P.(par exemple, point M), avoir et M>oui 0 , et tous les points en dessous du point P., en abscisse X 0 , avoir oui N<oui 0 . Parce que le X 0 est un point arbitraire, alors il y aura toujours des points d'un côté de la ligne pour lesquels hache+ par > c, formant un demi-plan, et de l'autre côté - les points pour lesquels hache + par< c.

Image 1

Le signe de l'inégalité dans le demi-plan dépend des nombres un, b , c.
Cela conduit à la méthode suivante solution graphique systèmes d'inégalités linéaires à deux variables. Pour résoudre le système, vous avez besoin de :

Pour chaque inégalité, écrivez l'équation correspondant à cette inégalité.
Construisez des lignes droites qui sont des graphiques de fonctions spécifiées par des équations.
Pour chaque droite, déterminez le demi-plan donné par l’inégalité. Pour ce faire, prenez un point arbitraire qui ne se trouve pas sur une droite et remplacez ses coordonnées dans l'inégalité. si l'inégalité est vraie, alors le demi-plan contenant le point choisi est la solution de l'inégalité d'origine. Si l’inégalité est fausse, alors le demi-plan de l’autre côté de la ligne est l’ensemble des solutions à cette inégalité.
Pour résoudre un système d'inégalités, il faut trouver l'aire d'intersection de tous les demi-plans qui sont la solution de chaque inégalité du système.

Cet espace peut s'avérer vide, alors le système d'inégalités n'a pas de solutions et est incohérent. Autrement, le système est dit cohérent.
Il peut y avoir un nombre fini de solutions et ensemble infini. La zone peut être un polygone fermé ou illimité.

Regardons trois exemples pertinents.

Exemple 1. Résolvez le système graphiquement :
X + oui – 1 ≤ 0;
–2X - 2oui + 5 ≤ 0.

considérons les équations x+y–1=0 et –2x–2y+5=0 correspondant aux inégalités ;
Construisons des droites données par ces équations.

Figure 2

Définissons les demi-plans définis par les inégalités. Prenons un point arbitraire, soit (0 ; 0). Considérons X+ oui– 1 0, remplacez le point (0 ; 0) : 0 + 0 – 1 ≤ 0. Cela signifie que dans le demi-plan où se trouve le point (0 ; 0), X + oui – 1 ≤ 0, c'est-à-dire le demi-plan situé en dessous de la droite est une solution à la première inégalité. En remplaçant ce point (0 ; 0) par le second, on obtient : –2 ∙ 0 – 2 ∙ 0 + 5 ≤ 0, c'est-à-dire dans le demi-plan où se trouve le point (0 ; 0), –2 X – 2oui+ 5≥ 0, et on nous a demandé où –2 X – 2oui+ 5 ≤ 0 donc dans l'autre demi-plan - dans celui au-dessus de la droite.
Trouvons l'intersection de ces deux demi-plans. Les lignes sont parallèles, donc les plans ne se coupent nulle part, ce qui signifie que le système de ces inégalités n'a pas de solutions et est incohérent.

Exemple 2. Trouver graphiquement des solutions au système d'inégalités :

figure 3
1. Écrivons les équations correspondant aux inégalités et construisons des droites.
X + 2oui– 2 = 0

X	2	0
oui	0	1

oui – X – 1 = 0

X	0	2
oui	1	3

oui + 2 = 0;
oui = –2.
2. Après avoir choisi le point (0 ; 0), on détermine les signes des inégalités dans les demi-plans :
0 + 2 ∙ 0 – 2 ≤ 0, c'est-à-dire X + 2oui– 2 ≤ 0 dans le demi-plan situé au-dessous de la droite ;
0 – 0 – 1 ≤ 0, c'est-à-dire oui –X– 1 ≤ 0 dans le demi-plan situé au-dessous de la droite ;
0 + 2 =2 ≥ 0, c'est-à-dire oui+ 2 ≥ 0 dans le demi-plan au-dessus de la droite.
3. L’intersection de ces trois demi-plans sera une aire qui est un triangle. Il n'est pas difficile de trouver les sommets de la région comme points d'intersection des lignes correspondantes

Ainsi, UN(–3; –2), DANS(0; 1), AVEC(6; –2).

Considérons un autre exemple dans lequel le domaine de solution résultant du système n'est pas limité.