La programmation linéaire utilise une méthode graphique pour déterminer des ensembles convexes (polyèdre solution). Si la tâche principale programmation linéaire Il a plan optimal, alors la fonction objectif prend une valeur à l'un des sommets du polyèdre solution (voir figure).

Objet de la prestation. En utilisant de ce service possible dans mode en ligne résoudre le problème de programmation linéaire à l'aide de la méthode géométrique, et également obtenir une solution au problème double (évaluer l'utilisation optimale des ressources). De plus, un modèle de solution est créé dans Excel.

Instructions. Sélectionnez le nombre de lignes (nombre de restrictions).

Nombre de restrictions 1 2 3 4 5 6 7 8 9 10

Si le nombre de variables est supérieur à deux, il faut amener le système au SZLP (voir exemple et exemple n°2). Si la contrainte est double, par exemple 1 ≤ x 1 ≤ 4, alors elle est divisée en deux : x 1 ≥ 1, x 1 ≤ 4 (c'est-à-dire que le nombre de lignes augmente de 1).
Vous pouvez également créer une zone de solutions réalisables (ADA) en utilisant ce service.

Les éléments suivants sont également utilisés avec cette calculatrice :
Méthode simplexe pour résoudre ZLP

Solution au problème des transports
Résoudre un jeu matriciel
Grâce au service en ligne, vous pouvez déterminer le prix d'un jeu matriciel (bornes inférieure et supérieure), vérifier la présence d'un point selle, trouver une solution à une stratégie mixte en utilisant les méthodes suivantes : minimax, méthode simplex, graphique (géométrique ), méthode de Brown.
Extremum d'une fonction de deux variables
Calcul des limites

La résolution d'un problème de programmation linéaire par méthode graphique comprend les étapes suivantes:

1. Les lignes sont construites sur le plan X 1 0X 2.
2. Des demi-plans sont déterminés.
3. Définir un polygone de solution ;
4. Un vecteur N(c 1 ,c 2) est construit, qui indique la direction de la fonction objectif ;
5. Fonction objectif Avancer c 1 x 2 + c 2 x 2= 0 dans la direction du vecteur N jusqu'au point extrême du polygone solution.
6. Les coordonnées du point et la valeur de la fonction objectif en ce point sont calculées.

Les situations suivantes peuvent se présenter :

Exemple. L'entreprise fabrique deux types de produits : P1 et P2. Pour la fabrication de produits, deux types de matières premières sont utilisées - C1 et C2. Prix ​​de gros l'unité de production est égale à : 5 unités. pour unités P1 et 4 pour P2. La consommation de matières premières par unité de produit de type P1 et de type P2 est donnée dans le tableau.
Tableau - Consommation de matières premières pour la production

Des restrictions sur la demande de produits ont été établies : le volume de production quotidien des produits P2 ne doit pas dépasser le volume de production quotidien des produits P1 d'au plus 1 tonne ; Le volume de production quotidien maximum de P2 ne doit pas dépasser 2 tonnes.
Vous devez déterminer :
Combien de produits de chaque type l'entreprise doit-elle produire afin de maximiser les revenus provenant des ventes de produits ?

1. Formuler modèle mathématique problèmes de programmation linéaire.
2. Résoudre un problème de programmation linéaire graphiquement(pour deux variables).

Solution.
Formulons un modèle mathématique du problème de programmation linéaire.
x 1 - production de produits P1, unités.
x 2 - production de produits P2, unités.
x 1 , x 2 ≥ 0

Limites des ressources
6x1 + 4x2 ≤ 24
x 1 + 2 x 2 ≤ 6

Restrictions de demande
x 1 +1 ≥ x 2
x 2 ≤ 2

Fonction objectif
5x 1 + 4x 2 → maximum

On obtient alors le PLP suivant :
6x1 + 4x2 ≤ 24
x 1 + 2 x 2 ≤ 6
x 2 - x 1 ≤ 1
x 2 ≤ 2
x 1 , x 2 ≥ 0
5x 1 + 4x 2 → maximum

Tâche. Résolvez graphiquement le problème de programmation linéaire en déterminant la valeur extrême de la fonction objectif :

sous restrictions

Construisons une région de solutions réalisables, c'est-à-dire Résolvons graphiquement le système d'inégalités. Pour ce faire, on construit chaque droite et on définit les demi-plans définis par les inégalités (les demi-plans sont indiqués par un nombre premier).

Construisons l'équation 3x 1 +x 2 = 9 en deux points.
Pour trouver le premier point, nous assimilons x 1 = 0. Nous trouvons x 2 = 9. Pour trouver le deuxième point, nous assimilons x 2 = 0. Nous trouvons x 1 = 3. Nous connectons le point (0;9) avec (3;0) avec une ligne droite. Définissons le demi-plan défini par l'inégalité. Après avoir choisi le point (0 ; 0), on définit le signe de l'inégalité dans le demi-plan : 3. 0 + 1 . 0 - 9 ≤ 0, c'est-à-dire 3x 1 +x 2 - 9≥ 0 dans le demi-plan au-dessus de la droite.
Construisons l'équation x 1 +2x 2 = 8 en deux points.
Pour trouver le premier point, nous assimilons x 1 = 0. Nous trouvons x 2 = 4. Pour trouver le deuxième point, nous assimilons x 2 = 0. Nous trouvons x 1 = 8. Nous connectons le point (0;4) avec (8;0) avec une ligne droite. Définissons le demi-plan défini par l'inégalité. Après avoir choisi le point (0 ; 0), on définit le signe de l'inégalité dans le demi-plan : 1. 0 + 2 . 0 - 8 ≤ 0, c'est-à-dire x 1 +2x 2 - 8≥ 0 dans le demi-plan au-dessus de la droite.
Construisons l'équation x 1 + x 2 = 8 en deux points.
Pour trouver le premier point, nous assimilons x 1 = 0. Nous trouvons x 2 = 8. Pour trouver le deuxième point, nous assimilons x 2 = 0. Nous trouvons x 1 = 8. Nous connectons le point (0;8) avec (8;0) avec une ligne droite. Définissons le demi-plan défini par l'inégalité. Après avoir choisi le point (0 ; 0), on définit le signe de l'inégalité dans le demi-plan : 1. 0 + 1 . 0 - 8 ≤ 0, c'est-à-dire x 1 +x 2 - 8≤ 0 dans le demi-plan situé sous la droite.

L'intersection des demi-plans sera une région dont les coordonnées des points satisfont aux inégalités du système de contraintes du problème.
Notons les limites de l'aire du polygone de solution.

Vous pouvez vérifier l'exactitude de la construction des graphiques de fonctions à l'aide d'une calculatrice

Considérons la fonction objectif du problème F = 4x 1 +6x 2 → min.
Construisons une droite correspondant à la valeur de la fonction F = 0 : F = 4x 1 +6x 2 = 0. Le vecteur gradient, composé des coefficients de la fonction objectif, indique la direction de minimisation de F(X). Le début du vecteur est le point (0 ; 0), la fin est le point (4 ; 6). Nous déplacerons cette ligne droite de manière parallèle. Puisque nous nous intéressons à la solution minimale, nous déplaçons donc la ligne droite jusqu’à ce qu’elle touche d’abord la zone désignée. Sur le graphique, cette droite est indiquée par une ligne pointillée.

Droit F(x) = 4x 1 +6x 2 coupe la région au point B. Puisque le point B est obtenu à la suite de l'intersection de lignes (1) Et (2) , alors ses coordonnées satisfont les équations de ces droites :
3x1 +x2 =9
x1 +2x2 =8

Après avoir résolu le système d'équations, on obtient : x 1 = 2, x 2 = 3
Comment trouver la valeur minimale de la fonction objectif :
F(X) = 4*2 + 6*3 = 26

La méthode la plus simple et la plus visuelle pour résoudre un problème de programmation linéaire (LPP) est la méthode graphique. Elle est basée sur l'interprétation géométrique du problème de programmation linéaire et permet de résoudre le ZLP à deux inconnues :

Nous examinerons la solution de ce problème dans un avion. Chaque inégalité du système de contraintes fonctionnelles définit géométriquement un demi-plan avec une ligne frontière un p x, + + une j2 x 2 = b n je = 1, T. Les conditions de non-négativité définissent des demi-plans avec des lignes de démarcation X (= 0, x2= 0 en conséquence. Si le système est cohérent, alors les demi-plans, se coupant, forment une partie commune, qui est un ensemble convexe et représente un ensemble de points ; les coordonnées de chacun de ces points sont une solution à ce système. L’ensemble de ces points est appelé polygone de solution. Il peut s'agir d'un point, d'un segment, d'un rayon, d'un polygone borné ou non.

Géométriquement, le ZLP est trouver un point d'angle du polygone de solution dont les coordonnées fournissent la valeur maximale (minimale) de la fonction objectif linéaire, De plus, tous les points du polygone de solution sont des solutions admissibles.

Une équation linéaire décrit un ensemble de points situés sur la même ligne. Une inégalité linéaire décrit une région du plan.

Déterminons quelle partie du plan décrit l'inégalité 2x ( + 3x2 12.

Tout d'abord, construisons une droite 2x, + Zx2 = 12. Il passe par les points (6 ; 0) et (0 ; 4). Deuxièmement, nous déterminons quel demi-plan satisfait l’inégalité. Pour ce faire, sélectionnez n'importe quel point du graphique qui n'appartient pas à la droite et remplacez ses coordonnées dans l'inégalité. Si l’inégalité est vraie, alors point donné est une solution admissible et le demi-plan contenant le point satisfait l'inégalité. Il est pratique d’utiliser l’origine des coordonnées pour substituer l’inégalité. Remplaçons x ( = x 2 = 0 à l'inégalité 2x, + 3x 2 12. On obtient 2 0 + 3 0

De même, vous pouvez représenter graphiquement toutes les contraintes d'un problème de programmation linéaire.

La solution à chaque inégalité du système de contraintes ZLP est un demi-plan contenant la ligne frontière et situé d’un côté de celle-ci. L'intersection des demi-plans, dont chacun est déterminé par l'inégalité correspondante du système, est appelée domaine des solutions réalisables(ODR) ou domaine de définition.

Il faut se rappeler que la région des solutions réalisables satisfait aux conditions de non-négativité (Xj > 0, j = 1, P). Les coordonnées de tout point appartenant au domaine de définition sont une solution valable au problème.

Pour trouver la valeur extrême de la fonction objectif lors de la résolution graphique du ZLP, utilisez vecteur dégradé, dont les coordonnées sont des dérivées partielles de la fonction objectif :

Ce vecteur montre la direction du changement le plus rapide de la fonction objectif. Droit c [ x l + c 2 x 2 = f(x 0), perpendiculaire au vecteur gradient est ligne de niveau fonction cible (Fig. 2.2.2). En tout point de la ligne de niveau, la fonction objectif prend la même valeur. Assumons la fonction cible à une valeur constante UN. Changer le sens UN, on obtient une famille de droites parallèles dont chacune est une droite de niveau de la fonction objectif.

Riz. 2.2.2.

Une propriété importante d'une ligne de niveau fonction linéaire est que lorsque la ligne est parallèlement décalée d'un côté, le niveau n'est que augmente et lorsqu'il est déplacé de l'autre côté - seulement diminue.

Méthode graphique la décision du PPP comprend quatre étapes :

• 1. La région des solutions admissibles (ADA) du PLP est construite.
• 2. Le vecteur gradient de la fonction objectif (TF) est construit avec le début au point x0(0 ; 0) : V = (s, à partir de 2).
• 3. Ligne de niveau CjXj + c 2 x 2 = une (une - valeur constante) - une droite perpendiculaire au vecteur gradient V, - se déplace dans la direction du vecteur gradient dans le cas de la maximisation de la fonction objectif f(xvx2) jusqu'à ce qu'il quitte l'ODR. Lors de la réduction de /(*, x2) la ligne de niveau se déplace dans la direction opposée au vecteur dégradé. Le ou les points extrêmes de l'ODR lors de ce mouvement sont le point maximum (minimum) f(x p jc 2).

Si la droite correspondant à la ligne de niveau ne quitte pas l'ODR lors de son déplacement, alors le minimum (maximum) de la fonction f(x p x 2) n’existe pas.

Si la ligne du niveau de fonction cible est parallèle à la contrainte fonctionnelle de la tâche à laquelle valeur optimale CF, alors la valeur CF optimale sera atteinte en tout point de cette contrainte situé entre deux points d'angle optimaux et, par conséquent, n'importe lequel de ces points est la solution optimale du ZLP.

4. Les coordonnées du point maximum (minimum) sont déterminées. Pour ce faire, il suffit de résoudre un système d'équations de droites qui donnent un point maximum (minimum) à l'intersection. Signification f(x ( , x 2), trouvée au point résultant est la valeur maximale (minimale) de la fonction objectif.

Situations possibles solution graphique Les PAP sont présentées sous forme de tableau. 2.2.1.

Tableau 2.2.1

Type de RLL	Voir solution optimale
Limité	Seule décision
	Des solutions infinies
Illimité	La FC n'est pas limitée par le bas
	La FC n'est pas limitée d'en haut
	Seule décision
	Des solutions infinies
	Seule décision
	Des solutions infinies

Exemple 2.2.1. Planification de la production d'une entreprise de couture (problème concernant les costumes).

Il est prévu de sortir deux types de costumes : pour hommes et pour femmes. Un costume de femme nécessite 1 m de laine, 2 m de lavsan et 1 jour-homme de travail ; pour les hommes - 3,5 m de laine, 0,5 m de lavsan et 1 homme-jour de travail. Au total, il y a 350 m de laine, 240 m de lavsan et 150 jours-homme de travail.

Il est nécessaire de déterminer combien de costumes de chaque type doivent être confectionnés pour assurer un profit maximum si le bénéfice de la vente d'un costume pour femme est de 10 deniers. unités, et chez les hommes - 20 deniers. unités Il ne faut pas oublier qu'il est nécessaire de coudre au moins 60 costumes pour hommes.

Modèle économique et mathématique du problème

Variables: X, - nombre de costumes pour femmes ; x2 - nombre de costumes pour hommes.

Fonction objectif:

Restrictions:

La première contrainte (sur la laine) a la forme x( + 3,5x 2 x ( + 3,5x 2 = 350 passe par les points (350 ; 0) et (0 ; 100). La deuxième contrainte (selon lavsan) a la forme 2x (+ 0,5x 2 2x x + 0,5x 2 = 240 passe par les points (120 ; 0) et (0 ; 480). La troisième restriction (sur le travail) a la forme x y + x 2 150. Direct x ( + x 2 = 150 passe par les points (150 ; 0) et (0 ; 150). La quatrième contrainte (sur le nombre de costumes masculins) a la forme x2> 60. La solution de cette inégalité est le demi-plan situé au dessus de la droite x2 = 60.

À la suite de l’intersection des quatre demi-plans construits, nous obtenons un polygone, qui est la région des solutions réalisables à notre problème. Tout point de ce polygone satisfait les quatre inégalités fonctionnelles, et pour tout point en dehors de ce polygone, au moins une inégalité sera violée.

En figue. 2.2.3 la région des solutions réalisables (ADA) est ombrée. Pour déterminer la direction du mouvement vers l'optimum, on construit un vecteur gradient V dont les coordonnées sont des dérivées partielles de la fonction objectif :

Pour construire un tel vecteur, vous devez relier le point (10 ; 20) à l'origine. Pour plus de commodité, vous pouvez construire un vecteur proportionnel au vecteur V. Ainsi, sur la Fig. 2.2.3 montre le vecteur (30 ; 60).

Ensuite nous construirons une ligne de niveau 10xj + 20x 2 = UN. Assumons la fonction cible à une valeur constante UN. Changer le sens UN, on obtient une famille de droites parallèles dont chacune est une droite de niveau de la fonction objectif.

La méthode graphique de résolution du ZLP est basée sur les affirmations données au paragraphe 2.1. D'après le théorème 2, la solution optimale est située au sommet du domaine des solutions réalisables et donc résoudre le ZLP revient à trouver le sommet du domaine des solutions réalisables dont les coordonnées donnent la valeur optimale de la fonction objectif.

La méthode graphique est utilisée pour résoudre une classe limitée de problèmes à deux variables, parfois à trois variables. Il convient de noter que pour trois variables, ce domaine n'est pas assez clair.

Algorithme pour la méthode graphique de résolution de problèmes

Nous considérerons la mise en œuvre de la méthode graphique de résolution du ZLP à l'aide d'exemples.

Exemple 2.2.1. Résolvez graphiquement le ZLP :

(2.2.1)

maximum z=X 1 + 4X 2 (2.2.2)

Solution. Pour construire une région de solutions réalisables, qui est constituée de l'intersection de demi-plans correspondant à chaque inégalité du système de contraintes (2.2.1), on écrit les équations des droites frontières :

je 1: X 1 + 5X 2 = 5; je 2: X 1 + X 2 = 6; je 3: 7X 1 + X 2 = 7.

je 1 à la forme (2.2.3.) on divise ses deux parties par 5 :
. Ainsi, directement je 1 coupe sur axe Oh 1 5 unités, sur axe Oh 2 1 unité. De même nous avons pour je 2:
Et je 3:
.

Pour déterminer les demi-plans qui répondent aux contraintes du système (2.2.1), vous devez substituer les coordonnées de tout point qui ne se trouve pas sur la ligne de démarcation dans les contraintes. Si nous obtenons une vraie inégalité, alors tous les points de ce demi-plan sont des solutions à cette inégalité. DANS sinon choisissez un autre demi-plan.

Ainsi, les premier et deuxième demi-plans souhaités sont situés dans la direction opposée à l'origine des coordonnées (0 – 5 0 - 5 ; 7 0 + 0 7), et le second – vers l’origine des coordonnées (0 + 0 6). La région des solutions réalisables sur la figure 2.2.1 est ombrée.

Figure 2.2.1 – Domaine de solutions réalisables

Pour trouver le plan optimal, qui sera situé au sommet du polygone de solution, vous devez construire un vecteur de directions
=(Avec 1 ,Avec 2), qui indique la direction de la plus grande augmentation de la fonction objectif z=Avec 1 X 1 +Avec 2 X 2 .

Dans ce problème, le vecteur directeur
= (1, 4) : cela commence au point À PROPOS(0,0) et se termine au point N(1, 4).

Ensuite, nous construisons une ligne droite qui passe par la région des solutions réalisables, perpendiculaire au vecteur, et est appelée ligne de niveau cible les fonctions. Nous déplaçons la ligne de niveau dans la direction du vecteur en cas de maximisation de la fonction objectif z et dans le sens inverse, dans le cas de minimisation z, jusqu'à la dernière intersection avec la région des solutions réalisables. En conséquence, le ou les points sont déterminés là où la fonction objectif atteint une valeur extrême, ou le caractère illimité de la fonction objectif est établi. z sur l'ensemble des solutions au problème.

Ainsi, le point maximum de la fonction objectif z est le point UN intersections de lignes je 2 et je 3 .

Pour calculer la valeur optimale de la fonction objectif z trouver les coordonnées du point UN . Depuis le point UN est le point d'intersection des lignes je 2 et je 3, alors ses coordonnées satisfont un système d'équations composé des équations des lignes frontières correspondantes :

Donc le point UN a des coordonnées X 1 =1/6, X 2 = 35/6.

Pour calculer la valeur optimale de la fonction objectif, vous devez y substituer les coordonnées du point UN .

Remplacement des coordonnées du point UN dans la fonction objectif (2.4), on obtient

maximum z = 1/6 + 4·(35/6) = 47/2.

Exemple 2.2.2. Construire sur le plan la région des solutions réalisables du système d'inégalités linéaires (2.2.4) et trouver les plus grandes et les plus petites valeurs de la fonction objectif (2.2.5) :

(2.2.4)

z= –2X 1 –X 2 (2.2.5)

Solution. Pour construire une région de solutions réalisables, qui est constituée de l'intersection de demi-plans correspondant à chaque inégalité du système de contraintes (2.2.4), on écrit les équations des droites frontières :

je 1: 4X 1 – X 2 = 0; je 2: X 1 + 3X 2 = 6; je 3: X 1 – 3X 2 = 6; je 4: X 2 = 1.

Droit je 1 passe par le point de coordonnées (0;0). Pour le construire, on exprime X 2 à travers X 1: X 2 = 4X 1 . Trouvons un autre point par lequel passe la ligne je 1, par exemple (1;4). Passant par le point de coordonnées (0;0) et le point de coordonnées (1;4) on trace une ligne droite je 1 .

Réduire l’équation d’une droite je 2 à la forme en segments sur les axes (2.2.3), on divise ses deux parties par 6 :
. Ainsi, directement je 2 coupes sur axe Oh 1 6 unités, sur axe Oh 2 à 2 unités. De même nous avons pour je 3:
et Direct je 4 parallèles à l'axe Oh 1 et passe par le point de coordonnées (0;1) .

Pour déterminer les demi-plans qui répondent aux contraintes du système (2.2.4), il est nécessaire de substituer dans les contraintes les coordonnées de tout point qui ne se trouve pas sur la ligne frontière. En raison des restrictionsX 1 0, X 2 0, plage acceptable décisions du PPP se situe dans le premier quart du plan de coordonnées.

À PROPOS
la zone des solutions réalisables sur la figure 2.2.2 est ombrée.

Figure 2.2.2 – Domaine de solutions réalisables

Construisons un vecteur de directions
= (–2,–1). Ensuite, nous construisons une ligne de niveau perpendiculaire au vecteur .

Pour trouver la plus grande valeur de la fonction objectif, on déplace la ligne de niveau dans la direction du vecteur jusqu'à la dernière intersection avec la région des solutions réalisables. Ainsi, le point maximum de la fonction objectif z est le point UN(intersection des lignes je 1 et je 2).

Pour calculer la valeur optimale de la fonction objectif z trouver les coordonnées du point UN. Depuis le point UN est le point d'intersection des lignes je 1 et je 2, alors ses coordonnées satisfont un système d'équations composé des équations des lignes frontières correspondantes :

Donc le point UN a des coordonnées X 1 =6/13, X 2 = 24/13.

Remplacement des coordonnées du point UN dans la fonction objectif (2.2.5), on obtient la valeur optimale de la fonction objectif

maximum z= – 2·(6/13) – (24/13) = – 36/13.

Pour trouver la plus petite valeur de la fonction objectif, on déplace la ligne de niveau dans la direction opposée au vecteur jusqu'à la dernière intersection avec la région des solutions réalisables. Dans ce cas, la fonction objectif est illimitée dans la région des solutions réalisables, c'est-à-dire ZLP n’a pas de minimum.

À la suite de la décision du PPP, les cas suivants sont possibles :

La fonction objectif atteint sa valeur optimale à un seul sommet du polygone de solution ;

La fonction objectif atteint sa valeur optimale en tout point du bord du polygone de solution (la ZLP dispose de plans de référence alternatifs avec les mêmes valeurs z );

Le PAP n'a pas de plans optimaux ;

ZLP dispose d'un plan optimal dans le cas d'une gamme illimitée de solutions réalisables.

La méthode graphique est assez simple et intuitive pour résoudre des problèmes de programmation linéaire à deux variables. C'est basé sur géométrique présentation des solutions réalisables et des TF du problème.

Chacune des inégalités du problème de programmation linéaire (1.2) définit un certain demi-plan sur le plan de coordonnées (Fig. 2.1), et le système d'inégalités dans son ensemble définit l'intersection des plans correspondants. L’ensemble des points d’intersection de ces demi-plans est appelé domaine des solutions réalisables(ODR). ODR représente toujours convexe chiffre, c'est-à-dire ayant la propriété suivante : si deux points A et B appartiennent à cette figure, alors tout le segment AB lui appartient. L'ODR peut être représenté graphiquement par un polygone convexe, une zone polygonale convexe illimitée, un segment, un rayon ou un point. Si le système de contraintes du problème (1.2) est incohérent, l’ODS est un ensemble vide.

Tout ce qui précède s'applique également au cas où le système de restrictions (1.2) inclut des égalités, puisque toute égalité

peut être représenté comme un système de deux inégalités (voir Fig. 2.1)

Le filtre numérique à valeur fixe définit une droite sur le plan. En changeant les valeurs de L, on obtient une famille de droites parallèles appelée lignes de niveau.

Cela est dû au fait que changer la valeur de L entraînera une modification uniquement de la longueur du segment coupé par la ligne de niveau sur l'axe (ordonnée initiale), et le coefficient angulaire de la droite restera constant (voir Figure 2.1). Par conséquent, pour le résoudre, il suffira de construire l’une des lignes de niveau, en choisissant arbitrairement la valeur de L.

Le vecteur avec les coordonnées des coefficients CF à et est perpendiculaire à chacune des lignes de niveau (voir Fig. 2.1). La direction du vecteur coïncide avec la direction en augmentant CF, qui est point important Résoudre des problèmes. Direction descendant Le CF est opposé à la direction du vecteur.

L'essence de la méthode graphique est la suivante. Dans la direction (contre la direction) du vecteur dans l'ODR, le point optimal est recherché. Le point optimal est le point par lequel passe la ligne de niveau, correspondant à la plus grande (la plus petite) valeur de la fonction. La solution optimale est toujours située sur la limite de l'ODD, par exemple, au dernier sommet du polygone ODD par lequel passera la ligne cible, ou sur tout son côté.

Lors de la recherche d'une solution optimale à des problèmes de programmation linéaire, les situations suivantes sont possibles : il existe une solution unique au problème ; il existe un nombre infini de solutions (alternatives) ; TF n'est pas limité ; la région des solutions réalisables est un point unique ; le problème n'a pas de solutions.

Figure 2.1 Interprétation géométrique des contraintes et CF du problème.

Méthodologie de résolution de problèmes LP par la méthode graphique.

I. Dans les contraintes du problème (1.2), remplacer les signes d'inégalité par des signes d'égalité exacte et construire les droites correspondantes.

II. Trouvez et ombrez les demi-plans autorisés par chacune des contraintes d'inégalité du problème (1.2). Pour ce faire, vous devez remplacer les coordonnées d'un point [par exemple, (0;0)] dans une inégalité spécifique et vérifier la véracité de l'inégalité résultante.

Si l'inégalité est vraie,

Que il faut ombrer le demi-plan contenant ce point ;

sinon(l'inégalité est fausse) il faut ombrer le demi-plan qui ne contient pas le point donné.

Puisque et doit être non négatif, alors leur valeurs valides sera toujours au-dessus de l'axe et à droite de l'axe, c'est-à-dire dans le premier quadrant.

Les contraintes d'égalité autorisent uniquement les points situés sur la ligne correspondante. Par conséquent, il est nécessaire de mettre en évidence ces lignes droites sur le graphique.

III. Définissez l'ODR comme une partie du plan qui appartient simultanément à toutes les zones autorisées et sélectionnez-la. En l’absence d’ODD, le problème n’a pas de solution.

IV. Si l'ODR n'est pas un ensemble vide, alors vous devez construire la ligne cible, c'est-à-dire n'importe laquelle des lignes de niveau (où L est un nombre arbitraire, par exemple un multiple et, c'est-à-dire pratique pour les calculs). La méthode de construction est similaire à la construction de contraintes directes.

V. Construisez un vecteur qui commence au point (0;0) et se termine au point. Si la ligne cible et le vecteur sont construits correctement, alors ils perpendiculaire.

VI. Lors de la recherche du CF maximum, vous devez déplacer la ligne cible dans la direction vecteur, lors de la recherche du CF minimum - contre la direction vecteur. Le dernier sommet de l'ODR dans le sens du mouvement sera le point de maximum ou de minimum du CF. Si de tels points n’existent pas, alors nous pouvons conclure que TF illimité sur de nombreux forfaits par le haut (lors de la recherche d'un maximum) ou par le bas (lors de la recherche d'un minimum).

VII. Déterminez les coordonnées du point max (min) du filtre numérique et calculez la valeur du filtre numérique. Pour calculer les coordonnées du point optimal, il faut résoudre un système d'équations des droites à l'intersection desquelles il se trouve.