Applications et livres

Méthode graphique pour résoudre des équations de programmation linéaire.

Méthode graphique pour résoudre des problèmes Brève théorie Programmation linéaire - section programmation mathématique, utilisé dans le développement de méthodes pour trouver l'extremum des fonctions linéaires de plusieurs variables pour linéaire restrictions supplémentaires, imposé aux variables. Selon le type de problèmes résolus, ses méthodes sont divisées en universelles et spéciales. En utilisant méthodes universelles tout problème peut être résolu programmation linéaire(ZLP). Méthodes spéciales prendre en compte les caractéristiques du modèle de problème, son

fonction objectif et des systèmes de restrictions. Une caractéristique des problèmes de programmation linéaire est que la fonction objectif atteint un extremum à la limite de la région des solutions réalisables. Méthode graphique la résolution de problèmes de programmation linéaire permet de visualiser leur structure, d'identifier des caractéristiques et ouvre la voie à l'étude de propriétés plus complexes. Un problème de programmation linéaire à deux variables peut toujours être résolu graphiquement. Cependant, déjà dans un espace tridimensionnel, une telle solution devient plus compliquée, et dans des espaces de dimensions supérieures à trois, une solution graphique est généralement impossible. Le cas de deux variables n’a pas de particularité

signification pratique , cependant, sa considération clarifie les propriétés des limites du LLP, conduit à l'idée de sa solution, clarifie géométriquement les méthodes de solution et les modalités de leur mise en œuvre pratique. Si les contraintes et la fonction objectif contiennent plus de deux variables, alors c'est nécessaire (ou par la méthode d'amélioration séquentielle de la solution) - c'est universel et peut être utilisé pour résoudre n'importe quel problème. Pour certains

problèmes appliqués

programmation linéaire, telle que , des méthodes de résolution spéciales ont été développées.

Exemple de solution de problème Condition problématique L'entreprise fabrique deux types de produits : Produit 1 et Produit 2. Pour fabriquer une unité du Produit 1, des kg de matières premières sont nécessaires

premier type

• , kg de matières premières du deuxième type, kg de matières premières du troisième type. Pour fabriquer une unité du Produit 2, il faut dépenser des kg du premier type, des matières premières du deuxième type et des matières premières du troisième type. La production est assurée avec des matières premières de chaque type en quantités de kg, kg, kg, respectivement. Le prix du marché d'une unité du Produit 1 est de mille roubles et celui d'une unité du Produit 2 est de mille roubles.
• Élaborer un plan de production de produits garantissant un revenu maximal de leur vente en utilisant une méthode graphique pour résoudre un problème de programmation linéaire.

Pour garantir que la solution à un problème de programmation linéaire soit aussi précise et correcte que possible, beaucoup commandent à moindre coût travail d'essai sur ce site. Vous pouvez lire plus de détails (comment soumettre une demande, tarifs, délais, modes de paiement) sur la page Acheter un test de programmation linéaire...

Solution du problème

Construction de maquettes

Notons et désignons le nombre de produits manufacturés des 1er et 2e types.

Puis les restrictions de ressources :

De plus, selon le sens de la tâche

La fonction cible du modèle économico-mathématique, exprimant les revenus tirés des ventes :

On obtient le modèle économique et mathématique suivant :

Construction du domaine des solutions réalisables

Résolvons graphiquement le problème de programmation linéaire résultant :

Pour construire une région de solutions réalisables, nous construisons des lignes limites correspondant à ces inégalités dans le système de coordonnées :

Trouvons les points par lesquels passent les lignes :

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.

Pour définir un demi-plan, prenez n'importe quel point, par exemple, n'appartenant pas à la droite (1), et remplacez les coordonnées (0;0) dans l'inégalité correspondante. Parce que l'inégalité est vraie :

La région de solution de la 1ère inégalité correspondante correspond au demi-plan gauche

Prenons par exemple n'importe quel point qui n'appartient pas à la droite (2) et substituons les coordonnées (0;0) dans l'inégalité correspondante. Parce que l'inégalité est vraie :

Prenons par exemple n'importe quel point qui n'appartient pas à la droite (3) et substituons les coordonnées (0;0) dans l'inégalité correspondante. Parce que l'inégalité est vraie :

La région de solution de la 2ème inégalité correspondante correspond au demi-plan gauche

La région des solutions réalisables est la figure.

Trouver une solution au problème LP

On construit un vecteur dont les coordonnées sont proportionnelles aux coefficients de la fonction objectif. Voici le coefficient de proportionnalité.

Tracez une ligne de niveau perpendiculaire au vecteur construit.

Nous déplaçons la ligne de niveau dans la direction du vecteur afin qu'elle touche la région des solutions réalisables au point extrême. La solution au maximum est le point dont les coordonnées se trouvent comme point d'intersection des droites (2) et (1).

Répondre

Ainsi, il faut fabriquer 56 produits du 1er type et 64 produits du 2ème type. Dans ce cas, les revenus de la vente des produits seront maximaux et s'élèveront à 5 104 unités monétaires.

Méthode solution graphique, si un problème avec deux variables a des contraintes linéaires et que la fonction objectif est quadratique, discuté en détail ici
La page discute en détail de la solution au problème de programmation linéaire méthode simplexe, de plus, la construction est montrée double problème programmation linéaire et trouver sa solution en résolvant un problème direct.

Problème de transport et méthode potentielle
Le problème du transport, son modèle mathématique et ses méthodes de solution sont examinés en détail - trouver le plan de référence par la méthode des éléments minimaux et rechercher la solution optimale par la méthode du potentiel.

Programmation convexe - méthode graphique
Un exemple de résolution d'un problème de programmation quadratique convexe à l'aide d'une méthode graphique est donné.

Exemple 6.1.

Solution:

Le problème de programmation linéaire est donné dans formulaire standard et a deux paramètres de conception, donc

Il est possible de le résoudre par la méthode géométrique.

Étape 1 : ( ODR ).

Considérons la première contrainte, remplacez le signe d'inégalité par un signe égal et exprimez la variable x2à travers x1:

.

De même, nous déterminons les points pour les contraintes restantes du système et construisons à partir d'eux des lignes droites correspondant à chaque inégalité (Fig. 1). Nous numérotons les lignes selon le schéma précédemment adopté.

Étape 2 : .

Définissons des demi-plans - solutions à chacune des inégalités.

Considérons la première inégalité du système de contraintes du problème. Prenons un point (point de contrôle) qui n'appartient pas à la droite correspondant à cette inégalité, par exemple le point (0 ; 0). Remplaçons-le dans l'inégalité considérée :

Lors du remplacement des coordonnées point de contrôle les inégalités restent justes. Par conséquent, l'ensemble des points appartenant à cette droite (puisque l'inégalité n'est pas stricte), ainsi que ceux situés en dessous, seront des solutions à l'inégalité considérée (marquons sur le graphique (Fig. 1) la moitié trouvée -avion avec deux flèches pointant vers le bas à côté de la ligne je ) .

De la même manière, nous déterminons les solutions à d’autres inégalités et les marquons sur le graphique en conséquence. En conséquence, le graphique ressemblera à ceci :

Étape 3 : .

Les demi-plans trouvés (solutions à chacune des inégalités du système de contraintes) forment un polygone à leur intersection ABCDÉO, qui est l'ODD du problème considéré.

Riz. 1. Région de solutions réalisables au problème

Étape 4 :
Le vecteur gradient montre la direction de maximisation de la fonction objectif. Déterminons ses coordonnées : les coordonnées de son point initial (point d'application) – (0 ; 0), les coordonnées du deuxième point :

Traçons ce vecteur sur le graphique (Fig. 2).

Étape 5 : .

Considérons la fonction objective de ce problème :

.

Donnons-lui une valeur, par exemple . Exprimons la variable x2à travers x1:

.

Pour construire une droite à l'aide de cette équation, nous spécifierons deux points arbitraires, par exemple :

Construisons une droite correspondant à la fonction objectif (Fig. 2).

Riz. 2. Construction de la fonction cible F(X) et du vecteur gradient C

Étape 6 : déterminer le maximum de la fonction cible.

Déplacer une ligne droite F(X) parallèlement à lui-même dans la direction du vecteur gradient, on détermine le ou les points extrêmes de l'ODR. D'après le graphique (Fig. 3), un tel point est le point C - le point d'intersection des lignes je Et II .

Riz. 3. Détermination du point maximum de la fonction objectif F(X)

Déterminons les coordonnées du point C, pour cela résolvons le système d'équations linéaires suivant :

Remplaçons les coordonnées trouvées dans la fonction objectif et trouvons sa valeur optimale (maximale) :

Répondre: sous des restrictions données, la valeur maximale de la fonction objectif F(X)=24, qui est atteint au point C dont les coordonnées x1=6, x2=4.

Exemple 6.2. Résolvez le problème de programmation linéaire en utilisant la méthode géométrique :

Solution:

Les étapes 1 à 3 sont similaires aux étapes correspondantes de la tâche précédente.
Étape 4 : construction d'un vecteur gradient.
La construction du vecteur gradient s'effectue de la même manière que dans le problème précédent. Traçons ce vecteur sur le graphique (Fig. 4). On note également sur ce tableau la flèche est la direction opposée au vecteur gradient – ​​la direction de minimisation de la fonction objectif F (X).

Étape 5 : construction d'une fonction cible directe.

Construction d'une fonction objectif directe F(X) est réalisé de la même manière que dans le problème précédent (le résultat de la construction est présenté sur la Fig. 4).

Riz. 4. Construction de la fonction objectif F(x) et du vecteur gradient C

Étape 6 : déterminer l'optimum de la fonction cible.

Déplacer une ligne droite F(x) parallèlement à lui-même dans la direction opposée au vecteur gradient, on détermine le ou les points extrêmes de l'ODR. D'après le graphique (Fig. 5), un tel point est le point O de coordonnées (0 ; 0).

Riz. 5. Détermination du point minimum de la fonction objectif

En substituant les coordonnées du point minimum dans la fonction cible, nous déterminons sa valeur optimale (minimale), qui est égale à 0.
Répondre: sous des restrictions données, la valeur minimale de la fonction objectif F(X)=0, qui est atteint au point O (0 ; 0).

Exemple 6.3. Résolvez le problème de programmation linéaire suivant en utilisant la méthode géométrique :

Solution:

Le problème de programmation linéaire considéré est donné dans forme canonique, on sélectionne comme variables de base x 1 Et x2 .

Créons une matrice étendue et sélectionnons-la à l'aide de la méthode Jordanie-Gauss variables de base x1 Et x 2 .

Multipliez (élément par élément) la première ligne par –3 et ajoutez-la à la seconde :
.

Multipliez la deuxième ligne par :

.

Ajoutons la deuxième ligne à la première ligne :

.

En conséquence, le système de restrictions prendra la forme suivante :

Exprimons les variables de base en termes de variables gratuites :

Exprimons également la fonction cible en termes de variables libres ; pour ce faire, nous substituons les valeurs obtenues des variables de base dans la fonction cible :

Écrivons le problème de programmation linéaire résultant :

Puisque les variables x1 Et x2 non négatif, alors le système de restrictions résultant peut s'écrire sous la forme suivante :

Alors le problème original peut s’écrire sous la forme équivalente suivante tâche standard programmation linéaire :

Ce problème comporte deux paramètres de conception et peut donc être résolu en utilisant la méthode géométrique.

Étape 1 : construction de lignes droites limitant le domaine des solutions réalisables ( ODR ).

Considérons le système de contraintes du problème de programmation linéaire (pour plus de commodité, nous numérotons les inégalités) :

Construisons des droites correspondant à chaque inégalité (Fig. 6). Nous numérotons les droites selon le schéma précédemment adopté.

Étape 2 : détermination de la solution à chacune des inégalités du système de contraintes.

À l'aide de points de contrôle, nous déterminons des demi-plans - des solutions à chacune des inégalités, et les marquons sur le graphique (Fig. 6) à l'aide de flèches.

Étape 3 : détermination de l'ODD d'un problème de programmation linéaire.

Les demi-plans trouvés (c'est-à-dire les solutions à chacune des inégalités du système de contraintes) n'ont pas d'intersection commune (donc les solutions aux inégalités I contredisent généralement les inégalités restantes du système de contraintes), donc le système de contraintes n'est pas cohérent et le problème de programmation linéaire n’a donc pas de solution.

Riz. 6. Fragment d'un document MathCAD :

construire une région de solutions réalisables à un problème

Répondre: Le problème de programmation linéaire considéré n’a pas de solution en raison de l’incohérence du système de contraintes.

Si, après avoir substitué les coordonnées du point de contrôle dans l'inégalité, sa signification est violée, alors la solution de cette inégalité est un demi-plan qui ne contient pas ce point (c'est-à-dire situé de l'autre côté de la ligne).

La direction opposée au vecteur gradient correspond à la direction de minimisation de la fonction objectif.

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 de 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. Inégalité linéaire décrit une région de l'avion.

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 de 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.

La méthode graphique de résolution du PLP 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, l'un de ces points est solution optimale 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.

Les situations possibles d'une solution graphique du ZLP sont présentées dans le tableau. 2.2.1.

Tableau 2.2.1

Type de RLL	Type de solution optimale
Limité	La seule solution
	Des solutions infinies
Illimité	La FC n'est pas limitée par le bas
	La FC n'est pas limitée d'en haut
	La seule solution
	Des solutions infinies
	La seule solution
	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.

Économique modèle mathématique tâches

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.

Sur la fig. 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.

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 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 aux é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

Résoudre un problème de programmation linéaire (LPP) à l'aide d'une méthode graphique

Formulation générale de l'intrigue

Trouver les valeurs de n variables x 1 , x 2 , …, x n qui fournissent l'extremum (minimum ou maximum) de la fonction linéaire Z=C 1 x 1 ,+ C 2 x 2+…+ C n x n

et satisfaisant simultanément m restrictions de la forme

une 1,1 x 1 +une 1,2 x 2 +…+une 1.n x n£ =≥b 1 ,

une 2,1 x 1 +une 2,2 x 2 +…+une 2.n x n£ = ≥b 2 ,

. . . . . . . . . . . . . . . . . . . . . . .,

une m,1 x 1 +une m,2 x 2 +…+une m,n x n£ = ≥b m ,

pour donné a i,j , b i, C j (i=1,2,…,m; j=1,2,…,n). Le signe de la relation peut prendre n'importe laquelle des trois valeurs données.

Exemple de problème de programmation linéaire

Considérons le problème suivant. Le directeur d'une entreprise produisant deux types de peintures a décrit à un chercheur opérationnel la situation de la production et de la commercialisation des peintures. Il s'est avéré que l'usine produit deux types de peintures : pour l'intérieur et travaux extérieurs. Les deux couleurs entrent en jeu de gros. Pour la production de peintures deux produit original– A et B. Les réserves journalières maximales possibles de ces produits sont respectivement de 6 et 8 tonnes. L'expérience a montré que la demande quotidienne de peinture extérieure ne dépasse jamais la demande de peinture intérieure de plus d'une tonne. De plus, on constate que la demande en peinture extérieure ne dépasse jamais 2 tonnes par jour. Les prix de gros pour une tonne de peinture sont les suivants : 3 000 roubles pour la peinture extérieure et 2 000 roubles pour la peinture intérieure. Quelle quantité de chaque type de peinture l’usine doit-elle produire pour maximiser ses revenus de vente ?

Pour résoudre le problème posé au chercheur, il faut d’abord élaborer un modèle mathématique de la situation décrite.

Lors de la construction d’un modèle mathématique, le chercheur opérationnel se pose trois questions.

• Pour quelles quantités le modèle doit-il être construit ? En d’autres termes, vous devez identifier les variables de la tâche.
• Quelles restrictions doivent être imposées aux variables pour que les conditions caractéristiques du système modélisé soient remplies ?
• Quel est le but, pour atteindre lequel, parmi toutes les valeurs possibles (admissibles) des variables, il faut sélectionner celles qui correspondront à la (meilleure) solution optimale au problème ?

Introduisons les variables :

x 1 – volume de production quotidien de peinture extérieure (en tonnes),

x 2 – volume de production quotidien de peinture intérieure (en tonnes).

Considérant prix de gros par tonne de chaque type de peinture, le revenu journalier provenant de la vente de produits manufacturés est donné par la fonction objectif linéaire Z = 3x 1 + 2x 2.

Le but de la production est d'obtenir un profit maximum, ce qui signifie qu'il faut trouver les valeurs de x 1 et x 2 qui maximisent la fonction objectif Z.

Étant donné que le fabricant de peinture ne peut pas disposer arbitrairement des valeurs des variables, il est nécessaire d'identifier un ensemble de valeurs possibles de ces variables, qui est déterminé par les conditions spécifiques de production et de vente. Cet ensemble est appelé une région valeurs acceptables.

Le premier type de contrainte est déterminé par les stocks de produits A et B à partir desquels les peintures sont fabriquées. D'après la technologie de production, on sait que deux parties du produit A sont utilisées pour produire une tonne de peinture externe et qu'une partie est utilisée pour produire une tonne de peinture interne. Pour le produit B, la relation est inversée. Ces conditions technologiques sont décrites par les inégalités

2x 1 + x 2 6 £ (6 tonnes de produit A en stock),

x 1 + 2x 2 8 £ (il y a 8 tonnes de produit B en stock).

Les deux dernières restrictions impliquent une circonstance évidente : vous ne pouvez pas utiliser plus de produits A et B pour la production de peintures qu'il n'y en a réellement en stock.

La situation de la vente de peintures sur le marché entraîne les restrictions suivantes : x 1 – x 2 £ 1 (la peinture externe n'est pas vendue plus d'une tonne de plus que la peinture interne), x 1 £ 2 (la peinture externe n'est pas vendue plus plus de deux tonnes par jour).

En résumant tout ce qui a été dit, un modèle mathématique décrivant la situation actuelle de la production peut être spécifié sous la forme suivante :

trouver® max( Z=2× x 1 + 3× x 2 ) avec les restrictions suivantes sur les valeurs des variables x 1 et x 2

2 × x 1 + x 2 € 6 limitation (1),

X 1 + 2 × x 2 € 8 limitation (2),

X 1 - x 2 € 1 limitation (3),

X 1 £ 2 contrainte (4)

et l'exigence que les variables x 1 ³ 0 (5), x 2 ³ 0 (6) soient non négatives.

Le modèle mathématique résultant est un problème de programmation linéaire.

Méthode graphique pour résoudre des problèmes

La méthode graphique de résolution du problème ne peut être mise en œuvre que dans le cas bidimensionnel.

Modèle mathématique obtenu pour la formule tâche typique, nécessite des recherches, car on ne sait pas à l’avance si elle a (comment problème de mathématiques) solution. Nous mènerons l’étude en utilisant constructions graphiques. Simultanément à ces recherches, nous trouverons (s’il y en a une) une solution.

Étape 1. Construction du domaine des solutions réalisables

Le but est de construire une région dans laquelle chaque point satisfait à toutes les contraintes.

Chacune des six contraintes définit géométriquement un demi-plan. Pour le construire, il vous faut :

• · remplacer le signe d'inégalité dans la contrainte par l'égalité (on obtient l'équation d'une droite) ;

• · construire une droite à l'aide de deux points ;

• · déterminer quel demi-plan est spécifié par le signe d'inégalité. Pour ce faire, remplacez un point dans l'inégalité (par exemple, l'origine des coordonnées). S'il satisfait l'inégalité, on peint le demi-plan qui le contient.

Nous effectuons ces actions pour toutes les restrictions. On note chacune des lignes par les numéros adoptés lors de la numérotation des restrictions (voir figure).

Domaine de solutions réalisables (satisfaisant toutes les restrictions) est l'ensemble des points du premier quadrant du plan de coordonnées (x 1, x 2), qui est l'intersection de tous les demi-plans définis par les inégalités des restrictions.

L'ensemble des points qui satisfont aux six contraintes du problème est le polygone AFEDCB.

Étape 2 : Construction des lignes de niveau de fonction cible et détermination du point maximum

Le but est de trouver dans le polygone construit AFEDCB est le point auquel la fonction objectif Z=2x 1 + 3x 2 prend sa valeur maximale.

Traçons une ligne droite 2x 1 + 3x 2 = Const (ligne de niveau) afin qu'elle coupe le polygone AFEDCB (par exemple, Const = 10). Cette ligne de niveau est représentée sous forme de ligne pointillée sur la figure.

Si l'on considère les valeurs de la fonction objectif linéaire Z sur un ensemble de points (x 1 , x 2) appartenant à un segment de la ligne pointillée situé à l'intérieur de l'hexagone, alors elles sont toutes égales à la même valeur (Const = 10).

Déterminons le sens d'augmentation de la fonction. Pour ce faire, nous allons construire une ligne de niveau avec une valeur plus grande. Ce sera une ligne droite, parallèle à celle construite, mais située à droite. Alors, dans direction donnée la valeur de la fonction objectif augmente, et nous avons intérêt à la pousser le plus loin possible dans cette direction.

Le déplacement peut se poursuivre tant que la droite mobile coupe le polygone des solutions réalisables. La dernière position de la ligne, lorsqu'elle a un point commun avec le polygone AFEDCB (point C), correspond à valeur maximale fonction objectif Z et est atteint au point C de coordonnées x 1 = 4/3 (» 1,333), x 2 = 10/3 (» 3,333). Dans ce cas, Z = 38/3 (» 12,667).

La tâche a été complètement résolue. Du raisonnement géométrique effectué, il ressort clairement que la solution est unique. Faisons quelques généralisations découlant de l’interprétation géométrique du problème.

D'abord. La région des solutions réalisables est un polygone convexe ( Pourquoi convexe ? La région des solutions réalisables peut-elle être un ensemble vide ? Période? Une tranche ? Faisceau? Directement? Si oui, donnez un exemple de système de restriction).

Deuxième. Le maximum de la fonction objectif est atteint au sommet du polygone des solutions réalisables ( mais peut-être pas la seule solution? N'y aurait-il pas de solution ?)

Tâche 1 (à réaliser en classe, à montrer à l'enseignant)

Résoudre graphiquement

A) F =2 x 1 +3 x 2 et max Avec restrictions x 1 +3 x 2 ≤ 18 2 x 1 + x 2 ≤ 16 x2 ≤ 5 3 x 1 ≤ 21 x 1 ≥ 0 x 2 ≥ 0	B ) F =4 x 1 +6 x 2 et min Avec restrictions 3 x 1 + x 2 ≥ 9 x 1 +2 x 2 ≥ 8 x1 +6x2 ≥ 12 x 1 ≥ 0 x 2 ≥ 0
C ) F =3 x 1 +3 x 2 et max Avec restrictions x1 + x2 ≤ 8 2x 1 -x 2 ≥ 1 x 1 -2x 2 ≤ 2 x 1 ≥ 0 x 2 ≥ 0	D ) F =2 x 1 -3 x 2 и min Avec restrictions x 1 + x 2 ≥ 4 2x 1 -x 2 ≥ 1 x 1 -2x 2 ≤ 1 x 1 ≥ 0 x 2 ≥ 0

A) x1=6 x2=4 F=24

B) x1=2 x2=3 F=26

C) x1О x2=8-x1 F=24

Tâche 2 (à réaliser en classe, à montrer à l'enseignant)

Répondez aux questions en italique.

Tâche 3 (devoirs)

Écrivez un programme.

Dan fichier texte gentil

2 3 (coefficients de fonction objectif)

4 (nombre de restrictions)

2 2 12 (restrictions)

1 2 8

4 0 16

0 4 12

Construisez des lignes droites de manière à ce que le polygone des solutions réalisables soit entièrement à l'écran (pour la définition de l'échelle, voir le livre de Onegov). Les lignes droites peuvent être parallèles aux axes !

Construire plusieurs lignes au niveau de la fonction objectif (appuyer sur la touche - la droite se déplace, la valeur de la fonction objectif s'affiche). Afficher l'échelle.