Exemple 6.1.

Solution:

Tâche programmation linéaire est donné sous forme 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 cible 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 :

Le problème original peut alors s’écrire comme suit, équivalent à un problème de programmation linéaire standard :

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 est incohé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.

Les méthodes graphiques sont principalement associées à la représentation géométrique de la dépendance fonctionnelle à l'aide de lignes sur un plan. Les graphiques sont utilisés pour trouver rapidement la valeur des fonctions en fonction de la valeur correspondante de l'argument, pour afficher visuellement les dépendances fonctionnelles.
Presque tous les types de graphiques sont utilisés en analyse économique : graphiques de comparaison, graphiques de séries chronologiques, courbes de distribution, graphiques de champs de corrélation, cartogrammes statistiques. Les diagrammes de comparaison sont particulièrement répandus dans l'analyse - pour comparer les indicateurs de reporting avec ceux prévus, les périodes précédentes et les principales entreprises d'entreprises nationales ou étrangères. Pour représenter visuellement la dynamique des phénomènes économiques (et en analyse, il faut très souvent traiter des séries chronologiques), des diagrammes de séries chronologiques sont utilisés.
À l'aide d'une grille de coordonnées, des graphiques de la dépendance, par exemple, du niveau des coûts sur le volume de produits produits et vendus sont également construits. des graphiques sur lesquels vous pouvez représenter les corrélations entre les indicateurs. Dans le système d'axes de coordonnées, l'image montre l'influence divers facteurs pour l’un ou l’autre indicateur.
La méthode graphique est largement utilisée pour la recherche processus de production, structures organisationnelles, processus de programmation, etc. Par exemple, pour analyser l'efficacité de l'utilisation des équipements de production, des graphiques de calcul sont construits, comprenant des graphiques de plusieurs facteurs.

Notation : chaque cercle est considéré comme l'un des sommets du graphe ; le numéro dans le secteur supérieur de chaque sommet désigne son numéro de série ; Sur la base du nombre de deux sommets adjacents, le code de travail est formé ; le numéro dans le secteur inférieur de chaque sommet est le numéro de série du sommet précédent, et la ligne reliant ces deux sommets signifie un travail spécifique. En dessous de la ligne se trouve la durée prévue de ces travaux ; le chiffre dans le secteur gauche de chaque sommet signifie la durée totale de tous les travaux précédents, le chiffre dans le secteur droit diffère du chiffre à gauche par le montant de la réserve (réserve de temps). Ainsi, pour les sommets situés sur le chemin critique, les nombres dans les secteurs gauche et droit du sommet coïncident, puisque la marge temporelle est de 0.

Dans un système d'analyse, de planification et de gestion mathématiquement formalisé, les diagrammes de réseau occupent une place particulière. Ils ont un effet économique important dans la construction et l'installation d'entreprises industrielles et autres.
Le schéma de réseau (Fig. 6.1) permet d'identifier les plus importants de l'ensemble des travaux, ceux qui se trouvent sur le chemin critique, et de concentrer sur eux les principales ressources des organismes de construction, d'établir des relations entre les différents organismes spécialisés et de coordonner leurs travail. Les activités sur le chemin critique nécessitent l’attente la plus longue pour l’arrivée du prochain événement. Au stade de l'analyse et de la gestion opérationnelles, le planning du réseau permet de suivre efficacement l'avancement des travaux et de prendre des mesures en temps opportun pour éliminer d'éventuels retards dans les travaux.
Application graphiques de réseau l'analyse, la planification et la gestion permettent, comme le montrent de nombreux exemples, une réduction du temps de construction de 20 à 30 %, une augmentation de la productivité du travail de 15 à 20 %.
Dans les analyses réalisées directement sur les chantiers, l'utilisation de matériaux planification du réseau et la direction contribue à la bonne identification des raisons affectant l'avancement des travaux de construction et à l'identification des entreprises qui n'assurent pas l'achèvement des travaux qui leur sont confiés ou la livraison des équipements dans les délais fixés par le planning.
L'élaboration d'un planning de réseau en construction s'effectue en présence : de normes pour la durée de construction et la période de mise en service d'un objet ou d'un complexe d'objets, de devis de conception, d'un projet d'organisation de la construction et de la réalisation des ouvrages, de cartes technologiques standards , les normes en vigueur concernant les coûts de main-d'œuvre, les matériaux et le fonctionnement des machines. De plus, lors de l'élaboration d'un calendrier, l'expérience de l'exécution de travaux individuels, ainsi que les données sur la base de production des organismes de construction et d'installation, sont utilisées.
Sur la base de toutes ces données, un tableau des travaux et des ressources est établi, où dans la séquence technologique de production du travail leurs caractéristiques, volume, intensité de travail en jours-homme, exécutant (organisation et équipe), nombre de travailleurs, équipes, besoin de les mécanismes et les matériaux, les sources de leur approvisionnement sont indiqués. , la durée totale des travaux en jours, ainsi que la tâche précédente, après quoi vous pouvez commencer ce travail. Sur la base des indicateurs d'un tel tableau, un schéma de réseau est préparé, qui peut présenter différents degrés de détail en fonction du schéma de production adopté.
gestion du travail et niveau de gestion; En plus de l'horaire général, les interprètes élaborent un horaire pour le travail qu'ils exécutent.
Les principaux éléments d'un schéma de réseau : événement, travail, attente, dépendance.
Lors de l'analyse de l'avancement de la construction d'un objet, il convient d'établir si le planning du réseau a été établi correctement, si le chemin critique n'a pas été surestimé, si toutes les possibilités de le réduire ont été prises en compte lors de l'optimisation du planning, si tous les travaux peuvent être effectués en parallèle ou le temps qui y est consacré peut être réduit en augmentant les moyens de mécanisation, etc. Ceci est particulièrement important dans les cas où la durée des travaux selon le calendrier ne garantit pas l'achèvement de la construction à temps.
Le principal matériau de planification du réseau utilisé dans l'analyse est l'information sur l'avancement des travaux conformément au calendrier, qui est généralement établi au moins une fois par décennie. A titre d'exemple, une carte de la tâche et des informations sur l'avancement des travaux d'un projet de construction réalisés selon le planning du réseau sont données (tableau 6.1). D'après la carte, œuvres critiques ont été réalisés au début du mois plus tôt que prévu, mais l'installation des poutres de grue le long de la rangée B a ensuite été retardée et les travaux ultérieurs - l'installation des poutres de grue le long de la rangée A - ont été achevés avec un jour de retard.
L'optimisation des plannings du réseau s'effectue dès la phase de planification en réduisant le chemin critique, c'est-à-dire en minimisant les délais de réalisation les travaux de constructionà des niveaux de ressources donnés, en minimisant le niveau de consommation de ressources matérielles, de main-d'œuvre et financières avec des délais fixes pour l'achèvement des travaux de construction. Une approche mixte est également possible : pour une partie des travaux (plus chère) - minimiser le niveau de consommation de ressources avec un délai fixe pour réaliser les travaux, pour l'autre - minimiser le délai pour un niveau fixe de ressources.
La résolution des problèmes d'optimisation est grandement facilitée par la disponibilité des packages programmes d'application(PPP), adapté pour compiler des schémas de réseau optimaux sur un ordinateur.
Dans la pratique étrangère de l'analyse des systèmes, une méthode grapho-mathématique appelée « arbre de décision » est très répandue. L'essence de cette méthode est la suivante.
Par évaluation préliminaire besoins, une analyse préliminaire des conditions organisationnelles, techniques ou technologiques possibles, toutes les options possibles pour résoudre ce problème sont décrites. Développé pour la première fois

	Exercice					Information				Réserve de temps pour le travail		Nombre ty
Nom travaux	chiffrer	date commencé	date après avoir fini	prévu a continué	Concernant réserve temps	% ceux-	temps requis pour	à rang	date réelle	découverte actuel	non localisé	réserver du temps avec
	travaux	travaux (plan)	nia travaux (plan)	habitant ness, jours	moi	oh prêt ness	après avoir fini nia travaux, jours	Zader femmes	après avoir fini nia travaux	sur le chemin critique	un chemin critique	début du mois, jours
1	2	3	4	5	6	7	8	9	10	11	12	13
Développement des sols	1-2	1/IV	6/IV	5	0	100	-	-	6/IV	¦-	-	-
Fondations en béton pour chaudières	2-3	7/IV	17/1V	9	0	100	14/IV	2	2
Bétonnage des fondations selon la rangée A	2-4	7/IV	14/1V	7	2	100	14/IV
Idem pour la ligne B	2-5	7/IV	14/IV	7	2	100	-	-	14/IV
Dispositif de distribution de tuyaux	6-18	18/IV	21/IV	4	19	100	-	-	29/IV	-7
Dispositif de remblayage	6-7	18/IV	19/IV	2	0	100	17/IV	2	2
Installation de structures préfabriquées en béton
Lonn : le long de la rangée B	7-8	20/IV	22/IV	3	1	100	-	-	22/IV	_	-	-
le long de la rangée A	7-9	20/IV	22/IV	3	1	100	-	-	22/IV	-	-	-

Construction de voies de grue et installation de grue à tour 7-10
Installation des cadres de support sur les fondations des équipements 7-16 Installation des poutres de grue :
le long du rang B 8-11
20/IV 24/IV 4
20/IV 24/IV 4
24/IV 25/IV 2

le long du rang A 10-12 25/IV 26/IV
Pose de la première partie des poutres et dalles de revêtement 12-13 27/IV 4/V
Installation de voies de grue pour pont lt;3 grues 12-14 27/IV 3/V

6	7	8	9	10	11	12	13
0	100	-	-	22/IV	1	-	1
14	100.	-	-	29/IV	-	-5	-
1	100	derrière-	27/IV	-2

27/IV-1
accompagnement avec fourniture de structures en béton armé

1. 100 -

options élargies. Ensuite, lorsque vous présentez conditions additionnelles chacun d'eux est divisé en un certain nombre d'options. Image graphique L'une de ces options vous permet d'exclure les moins rentables et de choisir la plus acceptable.
Cette méthode peut être utilisée pour déterminer l'ordre de traitement de certaines pièces sur plusieurs machines afin de minimiser le temps total de traitement ; lors de la définition de la taille des ressources pour minimiser les coûts de production globaux ; lors de la répartition des investissements en capital et d'autres ressources entre les installations industrielles ; lors de la résolution de problèmes de transport et autres.

La méthode graphique est assez simple et intuitive pour résoudre des problèmes LP à 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 LP est déterminée sur le plan de coordonnées (X 1 ,X 2 ) un certain demi-plan (Fig. 1), et le système d'inégalités dans son ensemble est l'intersection des plans correspondants. L’ensemble des points d’intersection de ces demi-plans est appelé zone d'acceptablesolutions(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. En cas d'incohérence du système de contraintes du problème, l'ODD est un ensemble vide.

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

une il x 1 +une je 2 x 2 =b

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

Un je 2 x 2<Ь 1э +a i 2 x 2 >bj.

DF L(x)= c1x1 + c2x2 de valeur fixe L(x)=L définit une droite c1x1 sur le plan + c2x2 = L. En changeant les valeurs de L, on obtient une famille de droites parallèles appelée lignes de niveau.

Cela est dû au fait qu'une modification de la valeur de L entraînera une modification uniquement de la longueur du segment coupé par la ligne de niveau sur l'axe x2 (ordonnée initiale), et du coefficient angulaire de la droite tga = -- restera constant (Fig. 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 C = (c1; c2) avec les coordonnées des coefficients CF en x1 et x2 est perpendiculaire à chacune des lignes de niveau (voir Fig. 1). Directionle vecteur C coïncide avec direction en augmentant TF, qui est un point important pour résoudre les problèmes. Direction descendant FC opposédirection du vecteur C.

L'essence de la méthode graphique est la suivante. Dans la direction (contre la direction) du vecteur C dans l'ODR, le point optimal X = (x1 ; x2) est recherché ). Le point optimal est considéré comme le point par lequel passe la ligne de niveau L max (L min), correspondant à la plus grande (la plus petite) valeur de la fonction L(x). 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 solution optimale Pour les problèmes LP, les situations suivantes sont possibles : il existe une solution unique au problème ; il existe une infinité de solutions (option alternative); TF n'est pas limité ; la région des solutions réalisables est un point unique ; le problème n'a pas de solutions.

Zone valide- demi-plan

Image 1

1.2. Technique de résolution de problèmes LP à l'aide de la méthode graphique

I. Dans les contraintes du problème, 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. Pour ce faire, remplacez les coordonnées d'un point [par exemple, (0;0)] dans une inégalité spécifique et vérifiez 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é.

Depuis x1 et x2 doivent être non négatifs, alors leurs valeurs admissibles seront toujours au-dessus de l'axe des x 1 et à droite de l'axe x2, c'est-à-dire dans le 1er quadrant.

Les contraintes d'égalité autorisent uniquement les points qui se trouvent sur la ligne correspondante, mettez donc en évidence ces lignes sur le graphique.

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'ODR, la tâche Pas a des solutions, sur lesquels tirer la conclusion appropriée.

Si ODR n'est pas un ensemble vide, alors construisez la ligne cible, c'est-à-dire l'une des lignes de niveau c 1 x 1 + c 2 x 2 = L, où L est un nombre arbitraire, par exemple un multiple de 1 et avec 2, c'est-à-dire pratique pour faire des calculs. La méthode de construction est similaire à la construction de contraintes directes.

V. Construire un vecteur C = (c 1,c 2), qui commence au point (0;0), se termine au point (c 1,c 2). Si la ligne cible et le vecteur C sont construits correctement, alors ils seront perpendiculaire.

VI. Lors de la recherche du CF maximum, déplacez la ligne cible dans la direction vecteur C, lors de la recherche de min CF - contre la direction vecteur C. Dernier dans le sens du mouvement, le sommet de l'ODR sera le point max ou min du CF. Si de tels points n’existent pas, alors tirez une conclusion sur TF illimité pour de nombreux projets par le haut (lors de la recherche d'un chèque) ou par le bas (lors de la recherche d'un min).

Déterminer les coordonnées du point max (min) TF X = (x1*; x2* ) et calculer la valeur du CF l(x *). Pour calculer les coordonnées du point optimal X*, résolvez le système d'équations de droites à l'intersection desquelles se trouve X*.

Problème 1

Trouvons la solution optimale au problème dont le modèle mathématique a la forme

L(X) = 3x 1 + 2x 2 → maximum

x1 + 2x2< 6, (1)

2x1 + x2< 8, (2)

X1 + X2<1, (3)

x2< 2, (4)

x1 >0, x2 >0.

Construisons des lignes de contrainte, pour lesquelles nous calculons les coordonnées des points d'intersection de ces lignes avec les axes de coordonnées (Fig. 2).

x1 + 2x2 = 6,(1)

2x1 + x2= 8,(2)

(1) x1=0, x1=6, x2=3, x2=0,

(2) x1=0, x1=4, x2=8, x2=0,

(3) x1=0, x1=-1, x2=1, x2=0,

La droite (4) passe par le point x 2 = 2 parallèle à l'axe L(X).

Riz. 2. Solution graphique au problème

Définissons l'ODR. Par exemple, on substitue le point (0;0) dans la contrainte d'origine (3), on obtient 0< 1, что является истинным неравенством, поэтому стрелкой (или штрихованием) обозначим полуплоскость, contenant point (0;0), c'est-à-dire situé à droite et en dessous de la ligne droite (3). De la même manière, nous définissons les demi-plans autorisés pour les restrictions restantes et les indiquons avec des flèches au niveau des restrictions directes correspondantes (Fig. 2). La zone générale autorisée par toutes les restrictions, c'est-à-dire ODR est un polygone ABCDEF.

La ligne cible peut être construite en utilisant l'équation

Nous construisons le vecteur C du point (0;0) au point (3;2). Le point E est le dernier sommet du polygone de solutions réalisables ABCDEF, par lequel passe la ligne cible, en se déplaçant vers vecteur C. Donc E est le point de CF maximum. Déterminons les coordonnées du point E à partir du système d'équations de contraintes directes (1) et (2)

X1 +2x 2 =6, (1) x1=10/3=3 1/3, x2=4/3=1 1/3

2 X1 + x 2 =8, (2) E 3 1/3 ; 1 1/3

La valeur CF maximale est L(E) = 3*10/3+2*4/3 = 12 2/3

La méthode la plus simple et la plus visuelle de programmation linéaire (LP) est la méthode graphique. Il est utilisé pour résoudre des problèmes LP à deux variables. Considérons le problème LP sous forme standard :

max f(x 1 , x 2 , ..., xn) = ,

, je = 1, 2, …, m,

x j 0, j = 1, 2, …, n.

Mettons n=2 et nous examinerons le problème dans l'avion. Que le système d'inégalités soit cohérent (avoir au moins une solution).

Chaque inégalité de ce système définit géométriquement un demi-plan avec la ligne limite a i 1 x 1 + a i 2 x 2 = b i, i = 1, 2, …, m. Les conditions de non-négativité définissent des demi-plans avec des lignes droites limites x 1 = 0, x 2 = 0, respectivement. Le système est cohérent, donc les demi-plans, comme des ensembles convexes, se coupant, forment une partie commune, qui est un ensemble convexe et est un ensemble de points, où les coordonnées de chaque point sont une solution de ce système. L’ensemble de ces points est appelé un polygone solution. Il peut s'agir d'un point, d'un segment, d'un rayon, d'un polygone borné ou non.

Ainsi, géométriquement, le ZLP est la recherche d'un point dans le polygone solution dont les coordonnées donnent fonction linéaire l'objectif est la valeur maximale (minimale) et tous les points du polygone de solution sont des solutions valides.

É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 est décrite par l'inégalité 2x 1 + 3x 2 12.

Tout d’abord, construisons une droite 2x 1 + 3x2= 12. Il passe par les points (6 ; 0) et (0 ; 4). Afin de déterminer quel demi-plan satisfait l'inégalité, il est nécessaire de sélectionner n'importe quel point du graphique qui n'appartient pas à la droite et de substituer ses coordonnées dans l'inégalité. Si l’inégalité est vraie, alors point donné est une solution réalisable et le demi-plan contenant le point satisfait l'inégalité. Pour remplacer l’inégalité, il est pratique d’utiliser le point d’origine. Remplacez x 1 = x 2 = 0 dans l'inégalité 2x 1 + 3x 2 12. Nous obtenons 2x0 + 3x0 12. Cette affirmation est vraie, donc l'inégalité 2x 1 + 3x 2 12 correspond au demi-plan inférieur contenant le point (0 ; 0). Cela se reflète dans le graphique présenté à la Fig. 1.1.

De même, toutes les contraintes du problème LP peuvent être représentées graphiquement.

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 la région des solutions admissibles, ou région 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, 2, …, n). 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 de problèmes LP, un vecteur gradient est utilisé, dont les coordonnées sont des dérivées partielles de la fonction objectif, c'est-à-dire

Ce vecteur montre la direction du changement le plus rapide de la fonction objectif. Ligne directe avec 1 x 1 + avec 2 x 2 = f(x0), perpendiculaire au vecteur gradient, est la ligne de niveau de la fonction objectif. En tout point de la ligne de niveau, la fonction objectif prend la même valeur. Assumons la fonction cible à une valeur constante "UN". En changeant la valeur de « a », on obtient une famille de droites parallèles dont chacune est une droite de niveau de la fonction objectif.

Une propriété importante de la ligne de niveau d'une fonction linéaire est que lorsque la ligne est décalée parallèlement dans un sens, le niveau ne fait qu'augmenter, et lorsqu'elle est décalée dans l'autre sens, il ne fait que diminuer.

D'un point de vue géométrique, dans un problème de programmation linéaire, nous recherchons un tel point d'angle ou un ensemble de points parmi un ensemble admissible de solutions auquel la ligne de niveau le plus haut (le plus bas) est atteinte, située plus loin (plus près) que les autres dans le sens de la croissance la plus rapide.

Méthode graphique la décision du PPP comprend les étapes suivantes.

1. Une région polygonale de solutions admissibles (ADS) du PLP est construite.

2. Le vecteur gradient de la fonction objectif (TF) est construit en un point x 0 appartenant à l'ODR :

3. La ligne de niveau c 1 x 1 + c 2 x 2 = a (a est une valeur constante) - une droite perpendiculaire au vecteur gradient - se déplace dans la direction de ce vecteur en cas de maximisation de f (x 1, x 2) jusqu'à ce qu'il quitte l'ODR. Le ou les points limites de la zone lors de ce mouvement sont le point maximum f(x 1, x 2).

4. Pour trouver les coordonnées du point maximum, il suffit de résoudre deux équations de droite obtenues à partir des restrictions correspondantes et donnant le point maximum à l'intersection. La valeur f(x 1, x 2) trouvée au point résultant est le maximum.

Lors de la minimisation (maximisation) de la fonction f(x 1, x 2), la ligne de niveau se déplace dans la direction opposée au vecteur gradient. 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 1, x 2) n'existe pas.

Si la ligne de niveau est parallèle à une contrainte fonctionnelle du problème, alors valeur optimale Le CF sera atteint 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. Situations possibles les solutions graphiques des problèmes LP sont présentées dans le tableau. 1.3.

Tableau 1.3

№	Type de RLL	Type de solution optimale	Remarques
	Polygonale fermée	Seule décision
	Seule décision
	Polygonal	La FC n'est pas limitée par le bas
	La FC n'est pas limitée d'en haut
	Polygonale ouverte	Seule décision
	Des solutions infinies
	Segment de ligne	Seule décision

Considérons solution graphique problèmes de programmation linéaire en utilisant l’exemple suivant.

Exemple 1.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 pour femme nécessite 1 m de laine, 2 m de lavsan et 1 personne/jour de travail. Pour un costume homme - 3,5 m de laine, 0,5 m de lavsan et 1 personne/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 unités monétaires et celui d'un costume pour homme de 20 unités monétaires. Il ne faut pas oublier qu'il est nécessaire de coudre au moins 60 costumes pour hommes.

Introduisons la notation suivante : x 1 - le nombre de costumes féminins ; x 2 – nombre de costumes pour hommes. Le bénéfice de la vente de costumes pour femmes est de 10x 1 et celui de la vente de costumes pour hommes de 20x 2, soit il faut maximiser la fonction objectif :

10x1 + 20x2

Les contraintes de tâches ont la forme :

x1 + x2 150,

2x1 + 0,5x2 240,

x 1 + 3,5x 2 350,

x2 60,

x1 0.

La première limitation de travail est x 1 + x 2 150. La droite x 1 + x 2 = 150 passe par les points (150 ; 0) et (0 ; 150) (Fig. 1.2).

La deuxième contrainte sur le lavsan est 2 x 1 + 0,5x 2 240. La droite 2 x 1 + 0,5x 2 = 240 passe par les points (120 ; 0) et (0 ; 480). Troisième limitation sur la laine x 1 + 3,5x 2 350. Ajoutons une quatrième limitation sur le nombre de costumes pour hommes x 2 60. La solution à cette inégalité est le demi-plan situé au-dessus de la droite x 2 = 60. Sur la Fig. 1.3 la région des solutions réalisables est ombrée. Pour déterminer la direction du mouvement vers l'optimum, nous construisons un vecteur gradient dont les coordonnées sont des dérivées partielles de la fonction objectif, c'est-à-dire

Pour construire un tel vecteur, vous devez connecter le point (10 ; 20) à l’origine. Lors de la maximisation de la fonction objectif, il est nécessaire de se déplacer dans la direction du vecteur gradient, et lors de la minimisation, dans la direction opposée. Pour plus de commodité, vous pouvez construire un vecteur proportionnel au vecteur . Ainsi, sur la Fig. 1.4 montre le vecteur gradient (30;60).

Pour déterminer la direction du mouvement vers l'optimum, nous construisons un vecteur gradient dont les coordonnées sont des dérivées partielles de la fonction objectif, c'est-à-dire

Dans notre cas, nous déplacerons la ligne de niveau jusqu’à ce qu’elle quitte la région des solutions réalisables. Au point extrême, au coin, le maximum de la fonction objectif est atteint. Pour trouver les coordonnées de ce point, il suffit de résoudre deux équations de droite obtenues à partir des restrictions correspondantes et donnant un point maximum à l'intersection :

x1 + 3,5x2 = 350,

x1 + x2 = 150.

À partir de là, il est facile d’écrire la solution au ZLP original : maximum f(x)= 2300 et est obtenu à x 1 = 70 et x 2 = 80 (voir Fig. 1.4).

1.3.TECHNOLOGIE POUR RÉSOUDRE LES PROBLÈMES DE PROGRAMMATION LINÉAIRE À L'AIDE DU COMPLÉMENT DE RECHERCHE DE SOLUTIONS DANS L'ENVIRONNEMENT EXCEL

1.3.1. informations généralesà propos de l'utilisation du processeur de feuille de calcul Excel

Considérons certains aspects du travail avec le tableur Excel, qui simplifieront les calculs nécessaires à la résolution des problèmes d'optimisation. Processeur de table- Ce logiciel, conçu pour automatiser le traitement des données tabulaires.

Éléments d’écran Excel. Après avoir lancé Excel, un tableau apparaît à l'écran dont l'apparence est illustrée à la figure 1.5.

Cette image s'appelle une feuille de calcul. Il s’agit d’une grille de lignes et de colonnes dont les intersections forment des rectangles appelés cellules. Les feuilles de calcul sont conçues pour saisir des données, effectuer des calculs, organiser une base d'informations, etc. La fenêtre Excel affiche les principaux éléments du programme : barre de titre, barre de menus, barre d'état, boutons de contrôle de la fenêtre.

Travailler avec des formules. Dans les programmes feuilles de calcul les formules sont utilisées pour effectuer de nombreux calculs différents. AVEC en utilisant Excel vous pouvez créer rapidement une formule. La formule se compose de trois parties principales :

1) signe égal ;

2) un ensemble de valeurs ou de références dans les cellules avec lesquelles les calculs sont effectués ;

3) opérateurs.

4) S'il n'y a pas de signe égal, Excel interprète les données non pas comme une formule, mais comme des données saisies dans une cellule. Les formules peuvent être saisies directement dans une cellule ou dans la barre de formule – soit du texte, soit des chiffres. Dans ce cas, vous devez effectuer les étapes suivantes :

· sélectionnez la cellule qui doit contenir la formule et entrez le signe (=) ;

· saisir un opérateur ou un signe d'action ;

· sélectionnez une autre cellule incluse dans la formule ;

· appuyez sur la touche Entrée.

La formule saisie apparaîtra dans la barre de formule et le résultat du calcul apparaîtra dans la cellule.

Utiliser des fonctions dans des formules. Pour faciliter la saisie des formules, vous pouvez utiliser les fonctions Excel. Les fonctions sont des formules intégrées à Excel. Excel contient de nombreuses formules. Ils sont regroupés par divers types: logique, mathématique, ingénierie, statistique, etc.

Pour activer une formule particulière, cliquez sur les boutons Insérer, Fonctions. La fenêtre Assistant de fonction qui apparaît sur la gauche contient une liste de types de fonctions. Après avoir sélectionné un type, une liste des fonctions elles-mêmes sera placée à droite. Une fonction est sélectionnée en cliquant sur le nom correspondant.

Diverses fonctions exercées différents types calculs selon certaines règles. Lorsqu'une fonction est un objet unique dans une cellule de feuille de calcul, elle commence par un signe (=), suivi du nom de la fonction, puis des arguments de la fonction, entre parenthèses.

Find a Solution est un complément Excel qui vous permet de résoudre des problèmes d'optimisation. Si la commande Rechercher une solution n'est pas disponible dans le menu Outils, vous devez télécharger ce module complémentaire. Sélectionnez la commande Outils => Modules complémentaires et activez le module complémentaire Rechercher une solution. Si ce complément ne figure pas dans la boîte de dialogue Modules complémentaires, vous devez accéder au panneau Gestion des fenêtres, cliquez sur l'icône Ajout/Suppression de programmes et en utilisant le programme Installation Excel(ou Office) installez le complément Rechercher une solution.

Après avoir sélectionné les commandes Outils => Rechercher une solution, la boîte de dialogue Rechercher une solution apparaîtra.

Il existe trois options principales dans la boîte de dialogue Rechercher une solution ;

Définir la cellule cible.

Changer de cellule.

Restrictions.

Vous devez d’abord remplir le champ Définir la cellule cible. Dans toutes les tâches de l'outil Rechercher une solution, le résultat dans l'une des cellules de la feuille de calcul est optimisé. La cellule cible est liée aux autres cellules de cette feuille de calcul à l'aide de formules. L'outil Rechercher une solution utilise des formules qui produisent un résultat dans la cellule cible pour vérifier solutions possibles. Vous pouvez choisir de rechercher le plus petit ou valeur la plus élevée pour la cellule cible ou définissez une valeur spécifique.

Deuxième paramètre important L'outil Rechercher une solution est l'option Modification des cellules. Ici vous précisez les cellules dont les valeurs seront modifiées afin d'optimiser le résultat dans la cellule cible. Vous pouvez spécifier jusqu'à 200 cellules modifiables pour trouver une solution. Il y a deux exigences principales pour ces cellules : elles ne doivent pas contenir de formules et les modifications de leurs valeurs doivent se refléter dans une modification du résultat dans la cellule cible. En d’autres termes, la cellule cible dépend des cellules modifiées.

Le troisième paramètre qui doit être renseigné dans l'onglet Rechercher une solution est celui des restrictions.

Pour résoudre le problème, vous avez besoin de :

1) indiquer les adresses des cellules dans lesquelles sera placé le résultat de la décision (cellules modifiables) ;

2) saisir les données initiales ;

3) introduire une dépendance pour la fonction objectif ;

4) introduire des dépendances pour les restrictions,

5) exécutez la commande Rechercher des solutions ;

6) attribuer une cellule à la fonction cible (définir la cellule cible) ;

7) introduire des restrictions ;

8) entrez les paramètres pour résoudre le PLP.

Considérons la solution technologique en utilisant les conditions de l'exemple 1.1 (le problème de la combinaison).

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

Soit x 1 le nombre de costumes pour femmes ; x 2 - le nombre de costumes pour hommes,

10 x x 1 + 20 x x 2 maximum

Les contraintes de tâches ont la forme :

x 1 + x 2 150 - limitation du travail ;

2xx1 + 0,5x X 2 240 - limite sur le lavsan ;

x 1 + 3,5 x x 2 350 - limite de laine ;

x2 60 - limite sur les costumes pour hommes ;

x1 0 - restriction sur les costumes pour femmes.

1. Précisez les adresses des cellules dans lesquelles le résultat de la solution sera placé (cellules modifiables).

Notons x 1 , x 2 le nombre de combinaisons de chaque type. Dans notre problème, les valeurs optimales du vecteur = (x 1, x 2) seront placées dans les cellules A2:B2, la valeur optimale de la fonction objectif - dans la cellule S3.

2. Saisissez les données initiales.

Entrez les données de la tâche initiale comme indiqué sur la Fig. 1.6.

3. Introduisez une dépendance pour la fonction objectif.

· Placez le curseur dans la cellule « NW », la cellule sera sélectionnée.

· Placez le curseur sur le bouton Function Wizard situé dans la barre d'outils.

· Entrez Entrée. La boîte de dialogue Function Wizard étape 1 sur 2 apparaît à l'écran.

· Dans la fenêtre Fonctions, sélectionnez la ligne SUMPRODUCT (Fig. 1.7). Sur l'écran

· la boîte de dialogue SUMPRODUCT apparaît (Fig. 1.8).

· Entrez dans la ligne Array 1 A2:B2.

· Entrez AZ:VZ dans la ligne Array 2.

Le tableau 1 sera utilisé lors de la saisie des dépendances pour les contraintes, donc sur ce tableau vous devez faire lien absolu. En figue. La figure 1.9 montre qu'une fonction a été introduite dans la cellule SZ.

5. Entrez les dépendances pour les contraintes (Figure 1.10).

· Placez le curseur dans la cellule NW.

· Sur la barre d'outils se trouve un bouton Copier dans le Presse-papiers.

· Placez le curseur dans la cellule C4.

· Placez le curseur dans la cellule C5.

· Sur la barre d'outils, le bouton Coller depuis le Presse-papiers.

· Placez le curseur dans la cellule Sat.

· Sur la barre d'outils, le bouton Coller depuis le Presse-papiers.

· Placez le curseur dans la cellule C7.

· Dans la barre d'outils, cliquez sur le bouton Coller à partir du Presse-papiers. (Le contenu des cellules C4-C7 doit être vérifié. Ils doivent contenir des informations, comme le montre par exemple la figure 1.11 ; le contenu de la cellule C5 est présenté à titre d'exemple.)

· Dans la ligne Menu, placez le pointeur de la souris sur Service. Dans le menu développé, sélectionnez la commande Rechercher une solution. La boîte de dialogue Rechercher une solution apparaît (Fig. 1.12).

5. Exécutez la commande Rechercher une solution.

6. Attribuez une cellule à la fonction cible (définissez la cellule cible), indiquez les adresses des cellules à modifier.

· Placez le curseur dans la ligne Définir la cellule cible.

· Entrez l'adresse de la cellule $С$3.

· Entrez le type de fonction objectif en fonction des conditions de votre problème. Pour ce faire, notez à quoi est égale la fonction objectif - Valeur maximale ou Valeur minimale.

· Placez le curseur dans une rangée en changeant de cellule.

· Entrez les adresses des variables requises A$2:B$2 (Fig. 1.13).

7. Introduire des restrictions.

· Placez le pointeur de la souris sur le bouton Ajouter. La boîte de dialogue Ajouter une contrainte apparaît.

· Entrez un signe de restriction.

· Dans la ligne Restriction, saisissez l'adresse $D$4 (Fig. 1.14).

· Placez le pointeur de la souris sur le bouton Ajouter. La boîte de dialogue Ajouter une restriction réapparaîtra.

· Entrez les contraintes restantes du problème en utilisant l'algorithme décrit ci-dessus.

· Après avoir saisi la dernière restriction, cliquez sur le bouton OK. La boîte de dialogue Rechercher une solution avec les conditions saisies apparaîtra à l'écran (Fig. 1.15).

8. Entrez les paramètres pour résoudre le problème de programmation linéaire.

· Dans la boîte de dialogue, placez le pointeur de la souris sur le bouton Options. La boîte de dialogue Options de recherche de solution apparaîtra à l'écran (Fig. 1.16).

· Définir des cases à cocher dans Windows Modèle linéaire(cela garantira l'utilisation de la méthode simplex) et des valeurs non négatives.

· Placez le pointeur de la souris sur le bouton OK. La boîte de dialogue Rechercher une solution apparaîtra à l'écran.

· Placez le pointeur de la souris sur le bouton Exécuter.

Après un court instant, la boîte de dialogue Résultats de la recherche de solution et le tableau initial avec les cellules remplies AZ:VZ pour les valeurs x i et la cellule SZ avec la valeur maximale de la fonction objectif apparaîtront (Fig. 1.17).

Si vous spécifiez le type de rapport Stabilité, vous pouvez obtenir des informations supplémentaires sur la solution optimale (Fig. 1.18).

Après avoir résolu le problème, la réponse a été reçue : il faut coudre 70 pièces. costumes pour femmes et 80 pcs. costumes pour hommes pour obtenir un profit maximum de 2300 USD.

1.4. DUALITÉ DANS LES PROBLÈMES DE PROGRAMMATION LINÉAIRE. ANALYSE DES SOLUTIONS OPTIMALES OBTENUES

En 1975, notre compatriote L.V. Kantorovitch a reçu le prix Nobel d'économie (avec l'économiste américain T. Koopmans) pour avoir développé la théorie utilisation optimale ressources (voir annexe 1).

Chaque problème de programmation linéaire est étroitement lié à un autre problème linéaire, appelé double ; le problème initial est appelé original ou direct. Le lien entre les problèmes originels et doubles réside notamment dans le fait que la solution de l’un d’eux peut être obtenue directement à partir de la solution de l’autre.

Variables double problème y i sont appelées estimations objectivement déterminées, ou estimations doubles, ou « prix » des ressources, ou prix fictifs.

Chacun des problèmes de double paire est en fait un problème de programmation linéaire indépendant et peut être résolu indépendamment de l’autre.

Le problème dual par rapport au problème original se compose selon les règles suivantes :

1) la fonction objectif du problème initial est formulée comme un maximum, et la fonction objectif du problème dual est formulée comme un minimum, tandis que dans le problème maximum toutes les inégalités dans les contraintes fonctionnelles ont la forme (), dans le problème minimum ils ont la forme ( );

2) la matrice A, composée de coefficients pour contraintes inconnues dans le système du problème d'origine, et une matrice similaire A T dans le problème dual sont obtenues l'une de l'autre par transposition ;

3) le nombre de variables dans le problème dual est égal au nombre de contraintes fonctionnelles dans le problème d'origine, et le nombre de restrictions dans le système du problème dual est égal au nombre de variables dans le problème d'origine ;

4) les coefficients des inconnues dans la fonction objectif du problème dual sont les termes libres du système de contraintes du problème d'origine, et les membres droits dans les restrictions du problème dual sont les coefficients des inconnues dans le fonction objective de l'original ; j 0.

Les deux problèmes présentés forment une paire de problèmes duaux symétriques. Les principales affirmations sur les problèmes mutuellement duaux sont contenues dans les deux théorèmes suivants.

Premier théorème de dualité. Pour des problèmes mutuellement doubles, l’un des cas mutuellement exclusifs se produit.

1. Il existe des solutions optimales aux problèmes directs et doubles,
dans ce cas, les valeurs des fonctions objectifs sur les solutions optimales
correspondre

2. Dans le problème direct, l'ensemble admissible n'est pas vide et la fonction objectif sur cet ensemble n'est pas bornée par le haut. Dans ce cas, le problème dual aura un ensemble admissible vide.

3. Dans un problème dual, l'ensemble admissible n'est pas vide et la fonction objectif sur cet ensemble n'est pas bornée par le bas. Dans ce cas, l’ensemble admissible du problème direct s’avère vide.

4. Les deux problèmes considérés ont des ensembles admissibles vides.

Deuxième théorème de dualité (théorème complémentaire de non-rigidité). Soit = ​​( x1 , x2,..., x n) est une solution admissible au problème direct, a = (y 1,y 2,...,y t) est une solution admissible au problème dual. Pour qu’ils constituent des solutions optimales aux problèmes directs et doubles, respectivement, il est nécessaire et suffisant que les relations suivantes soient vérifiées :

(1.4)

(1.5)

Les conditions (1.4) et (1.5) permettent, connaissant la solution optimale d'un des problèmes mutuellement duaux, de trouver la solution optimale d'un autre problème.

Considérons un autre théorème dont les conclusions seront utilisées plus loin.

Théorème d'estimation. Les valeurs des variables y i dans la solution optimale du problème dual représentent des estimations de l'influence des termes libres b i du système de contraintes (inégalités) du problème direct sur la valeur

Décider ZLP utilisant la méthode simplex, nous résolvons simultanément le double ZLP. Les variables du problème dual y i sont appelées estimations objectivement déterminées.

Considérons l'interprétation économique du double problème en prenant comme exemple le problème du tapis.

Exemple 1 .2. À l’aide de l’énoncé du problème du tapis, effectuez les tâches suivantes.

1. Formuler le contexte économique modèle mathématique problèmes sur les tapis pour maximiser le coût total de production, en utilisant les données du tableau. 1.1.

2. À l'aide de Rechercher une solution, trouvez un plan de production tel que coût total la production sera maximale.

3. Formuler un modèle économico-mathématique du double problème du problème du tapis.

4. Trouver plan optimal problème dual, à l'aide de théorèmes de dualité, expliquer l'égalité à zéro de X 1 et X 4.

5. À l'aide des protocoles de recherche de solutions, effectuez une analyse de la solution optimale obtenue au problème d'origine.

6. Déterminez comment le coût total et le plan de production changeront lorsque la durée de vie des tuyaux augmentera de 12 unités.

1. Formulons un modèle économique et mathématique du problème.

Notons X 1, X 2, X 3, X 4 le nombre de tapis de chaque type. La fonction objectif a la forme

F(X) = 3X 1 + 4X 2 + 3X 3 + X 4 maximum,

et les limites des ressources

7Х 1 + 2Х 2 + 2Х 3 + 6X4 80,

5Х 1 + 8Х 2 + 4 X3 + ZH4 480,

2X1 + 4 X2 + X3 + 8X4 130,

X1, X2, X3, X4 0.

2. Recherchez le plan de publication optimal.

Nous allons résoudre le problème à l'aide du complément Excel Rechercher une solution. La technologie permettant de résoudre le problème a été discutée en détail dans le problème du costume. Dans notre problème, les valeurs optimales du vecteur X = (X 1, X 2, X 3, X 4) seront placées dans les cellules VZ:EZ, la valeur optimale de la fonction objectif - dans la cellule F4.

Entrons les données initiales. Tout d'abord, nous décrivons la fonction cible à l'aide de la fonction - SUMPRODUCT (Fig. 1.19). Et puis nous saisirons les données pour les parties gauches des restrictions. Dans la recherche d'une solution, nous saisirons le sens de la fonction objectif, les adresses des variables recherchées et ajouterons des restrictions. La boîte de dialogue Rechercher une solution avec les conditions saisies apparaîtra à l'écran (Fig. 1.20).

Après avoir entré les paramètres pour résoudre le problème, cliquez sur le bouton Exécuter. Un message apparaîtra à l'écran indiquant qu'une solution a été trouvée (Fig. 1.21).

La solution résultante signifie que revenu maximum 150 mille roubles. une usine peut recevoir 30 tapis du deuxième type et 10 tapis du troisième type lors de sa production. Dans ce cas, les ressources « main d'œuvre » et « équipement » seront pleinement utilisées, et sur 480 kg de fil (ressource « matières premières »), 280 kg seront utilisés.

Création d'un rapport basé sur les résultats de la recherche d'une solution. Excel permet de présenter les résultats de la recherche d'une solution sous forme de rapport (tableau 1.4). Il existe trois types de tels rapports :

· Résultats (Réponse). Le rapport comprend les valeurs initiales et finales des cellules cibles et modifiées, ainsi que des informations supplémentaires sur les restrictions.

· Stabilité (sensibilité). Un rapport contenant des informations sur la sensibilité d'une solution à de petits changements dans les cellules en cours de modification ou dans les formules de contraintes.

· Limites. En plus des valeurs source et destination des cellules affectées et cibles, le rapport inclut des limites supérieure et inférieure sur les valeurs que les cellules d'influence peuvent accepter si les contraintes sont respectées.

La programmation linéaire utilise une méthode graphique pour déterminer des ensembles convexes (polyèdre solution). Si le problème principal de programmation linéaire a un 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 un modèle mathématique d'un problème 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