Fonction cible. Si le revenu de la vente d'une table est égal à AVEC 1 roubles, puis de la vente de tables en volume X 1 pièce de revenu mensuel

sera AVEC 1 X 1 roubles. De même, le revenu mensuel provenant de la vente d'armoires sera AVEC 2 X 2 roubles. Désignant le revenu total (en roubles) via Z, on peut donner la formulation mathématique suivante de la fonction objectif : déterminer les valeurs (admissibles) X 1, et X 2 maximiser le montant du revenu total Z = AVEC 1 X 1 + AVEC 2 X 2 =

2

∑

j=1

C j X j.

Restrictions. Lors de la résolution du problème considéré, les restrictions sur la consommation des ressources doivent être prises en compte. Le bois est utilisé pour fabriquer des tables et des armoires. Va à une table UN 11 (m 3) de bois, puis pour les tables en quantité X 1 pièce requise UN 11 X 1 (m 3) bois. Pour fabriquer des armoires en quantité de x 2 pièces vous aurez besoin UN 12 X 2 (m 3) de bois. Bois total requis UN 11 X 1 + UN 12 X 2 (m3). Sa consommation ne doit pas dépasser le montant b 1 (m3). Ensuite, nous écrivons la contrainte sur le bois sous la forme de l'inégalité

Pour les tâches variables X 1 et X 2 il faut imposer les conditions de non-négativité et d'indivisibilité, c'est-à-dire introduisons des restrictions

X 1 ≥ 0, X 2 ≥ 0,

Où X 1 , X 2 sont des entiers.

Donc, modèle mathématique les tâches peuvent s'écrire comme suit : déterminer les volumes mensuels de production de tables X 1 et armoires X 2 auquel il est atteint

Il convient de noter que d'un point de vue formel ce modèle est linéaire car toutes les fonctions qu'il contient (contraintes et fonction objectif) sont linéaires. Mais la nature linéaire du modèle construit devrait présupposer la présence de deux propriétés : la proportionnalité et l'additivité. La proportionnalité implique une relation directement proportionnelle entre une variable et une fonction objective et le montant de la consommation de ressources limitées. Par exemple, la proportionnalité directe n’aura pas lieu si nous introduisons une dépendance du revenu des usines à l’égard de la taille du lot de produits vendus. L'additivité s'observe dans le fait que les composantes du revenu dans la fonction objectif sont indépendantes, le revenu total est égal au montant du revenu. Si une usine fabrique deux types spécifiques de produits, dont une augmentation des ventes de l'un affecte négativement le volume des ventes de l'autre, alors un tel modèle n'a pas la propriété d'additivité.

Pour déterminer les variables du modèle considéré, des méthodes peuvent être utilisées programmation linéaire. Méthode de base LP est une méthode simplexe développée par G. Danzig. Le problème LP peut également être résolu graphiquement. Une représentation graphique de la solution du problème aidera à comprendre l'idée de la méthode simplexe. Précisons le problème en présentant les données initiales sous forme de tableau. 3.1 (les données sont données sous condition).

Tableau 3.1

Ressources	Consommation de ressources par unité de production		Stock de ressources
	Tableau	Placard
Bois de sciage (m 3)	0,06	0,07	42
Vis (kg)	0,04	0,085	34
Peinture (kg)	0,035	0,12	42
Prix ​​unitaire (RUB)	500	750	-

Écrivons le modèle du problème avec les données données :

Dans ce qui suit, nous ne prendrons pas en compte la contrainte (3.5), et obtiendrons une solution au problème en arrondissant les variables trouvées du problème (3.0-3.4).

44 :: 45 :: 46 :: 47 :: Contenu

47 :: 48 :: 49 :: 50 :: 51 :: Contenu

3.2.2. Méthode graphique pour résoudre le problème

Pour déterminer la solution ZLP avec deux variables Faisons ce qui suit :

1. Construisons un ensemble de solutions réalisables au problème Ω. Cet ensembleΩ est formé à la suite de l’intersection de demi-plans (contraintes) (3.1-3.4). En figue. 3.2 l’ensemble des solutions réalisables est représenté par un pentagone. Les domaines dans lesquels les restrictions correspondantes sous forme d'inégalités sont satisfaites sont indiqués par des flèches dirigées vers les valeurs admissibles des variables. Le polyèdre résultant Ω est appelé un simplexe. D'où le nom de la méthode permettant de trouver la solution optimale.

2. Construisons un vecteur gradient C, composé de dérivées de la fonction objectif par rapport aux variables du problème, qui indique le sens d'augmentation de la fonction objectif par rapport à ces variables. C = ( AVEC 1 , AVEC 2) = (500,750). Le début de ce vecteur se situe au point de coordonnées (0, 0) et la fin au point (500, 750). Une série de lignes pointillées parallèles perpendiculaires au vecteur gradient forme un ensemble de cibles

Fonctions pour des valeurs arbitrairement choisies Z. À Z= 0 la droite (fonction objectif) passe par le point (0, 0), et la fonction objectif Z prend la valeur minimale.

Riz. 3 2 Interprétation géométrique du ZLP

3. Déplaçons la droite caractérisant les revenus Z, dans la direction du gradient vectoriel (pour le problème max Z) jusqu'à ce qu'il s'oriente vers des solutions inacceptables. En figue. 3.2 il est clair que la solution optimale correspond au point X* = ( X 1 *, X 2*). Puisque le point X* est le point d’intersection des droites (3.1) et (3.2), les valeurs X 1* et X 2* sont déterminés en résolvant un système de deux équations :

La résolution de ce système d'équations donne le résultat X 1 * = 517,4 et X 2 * =156,5. La solution résultante signifie que le volume de production mensuel des tables devrait être de 517 pièces et celui des armoires de 156 pièces. Les revenus perçus dans ce cas seront :

Z= 517 · 500 + 156 · 750 = 375 500 roubles

PLP avec de nombreuses variables peut être résolu graphiquement si dans sa notation canonique le nombre d'inconnues n et le nombre d'équations linéairement indépendantes m lié par la relation n-m≤ 2. Écrivons la forme canonique du ZLP considéré ci-dessus. Pour ce faire, nous introduisons de nouvelles variables X 3 , X 4 et X 5 .

Pour une PPA donnée, le nombre de variables n= 5, et le nombre d'équations linéairement indépendantes m= 3. Ceci et d'autres ZLP sous forme canonique peuvent être résolus graphiquement si n-m ≤ 2.

Choisissons-en n'importe lequel m inconnues et exprimer chacune d'elles à travers les autres ( n-m) variables. Dans notre cas, il est pratique de prendre des variables X 3 , X 4 et X 5 et les exprimer à travers X 1 et X 2 .

En tenant compte de la non-négativité de toutes les variables, y compris X 3 ≥ 0, X 4 ≥ 0 et X 5 ≥ 0, ainsi que la dépendance de ce dernier à deux variables X 1 et X 2, vous pouvez montrer graphiquement la solution au problème étendu avec projection sur des variables X 1 et X 2. Demi-plan X 3 ≥ 0 (voir Fig. 3.2) coïncide avec la contrainte (3.1), demi-plan X 4 ≥ 0 - avec contrainte (3.2), et le demi-plan X 5 ≥ 0 - avec restriction (3.3). Point optimal en coordonnées X 1 et X 2 est formé à la suite de l'intersection de demi-plans X 3 et X 4: X 1 * = 517,4; X 2 = 156,5. En conséquence, les valeurs des variables X 3Ä X 4 sera nul : X 3 * =0; X 4 * = 0. Alors de (3.9) il s'ensuit que X 5 * = 42 - 0,035 517,4 - 0,12 156,5 = 5,1. La solution du ZLP (3.6-3.10) sera le vecteur X* = (517,4 ; 156,5 ; 0 ; 0 ; 5,1).

La représentation géométrique du ZLP reflète les éléments suivants :

1) l'ensemble des solutions admissibles Ω est convexe ;

2) solution optimale n'existe pas si l'ensemble Ω est vide ou illimité dans le sens du déplacement de la famille d'hyperplans du niveau du but de recherche d'un extremum ;

3) la solution est située à l'un des points d'angle (sommets) de l'ensemble des solutions admissibles Ω, dites de base ;

4) pour ZLP canonique les solutions de base sont caractérisées par le vecteur X - (X 1 , X 2 ,..., X n), dans lequel les valeurs m les variables sont non nulles, où m- le nombre d'équations linéairement indépendantes du problème (le nombre de variables de base du point d'angle de l'ensemble Ω).

Pour la solution optimale X* de l’exemple considéré, les variables de base étaient les variables X 1 , X 2 et X 5 . Variables restantes ( n-m) sont dits non basiques ou gratuits. Leurs valeurs au point d'angle sont nulles.

Veuillez noter que toute variable de base peut être exprimée en termes de variables non fondamentales et que la variable de base dans le modèle (3.6) - (3.10) est écrite une fois avec un coefficient de un.

Le problème ci-dessus de l’utilisation des ressources a une formulation et une structure très simples. Il peut inclure des exigences relatives à la comptabilisation de la sortie des produits dans un certain rapport, en tenant compte de leur éventuelle sortie selon diverses technologies, comptabilité de charge d'équipement et autres. Toutes ces situations sont assez bien décrites par les modèles de programmation linéaire.

47 :: 48 :: 49 :: 50 :: 51 :: Contenu

50 :: 51 :: 52 :: 53 :: 54 :: 55 :: 56 :: 57 :: 58 :: 59 :: 60 :: 61 :: Contenu

3.2.3. Méthode algébrique (simplex) pour résoudre ZLP

Discuté ci-dessus méthode graphique résoudre le problème LP permet de comprendre l'idée des méthodes d'optimisation, y compris les méthodes de programmation linéaire. L'essence de toutes les méthodes de programmation mathématique est qu'au lieu d'une énumération « aveugle » des options du plan, une énumération sélective et organisée est effectuée, visant à l'amélioration la plus rapide et, dans certains cas, cohérente de la solution.

La solution extrême n’est pas obtenue à l’intérieur du domaine des solutions réalisables Ω, mais à sa frontière (voir Fig. 3.2) ; pour être encore plus précis, à l'un des sommets des points d'angle d'un polygone formé à la suite de l'intersection de lignes associées à certaines restrictions, ou sur un segment entre deux points d'angle adjacents. Puisque l'extremum est nécessairement atteint en un ou deux points d'angle des plans admissibles, il suffit de calculer les valeurs des fonctions objectifs en tous les points d'angle (dans notre exemple il y en a cinq) et

choisissez celui avec la valeur extrême. Avec un grand nombre de variables et un grand nombre de contraintes, le nombre de points d'angle du polyèdre devient si grand que calculer la valeur de la fonction objectif dans chacun d'eux, mémoriser ces valeurs et les comparer entre eux est très problématique même pour les ordinateurs puissants. Nous devons donc chercher une autre solution.

Vous pouvez vous approcher du point optimal de manière séquentielle, en passant d'un point d'angle au point voisin, par exemple, à chaque fois à partir du point initial (de référence) X 0 ( X 1 = 0, X 2 = 0) séquentiellement au voisin qui se rapproche de X* de plus en plus vite. La méthode du simplexe proposée par R. Dantzig permet l'énumération des points solutions selon ce schéma. Pour notre exemple, à la première étape (itération) à partir du point de référence X 0, nous nous déplacerons selon la méthode du simplexe jusqu'au point X 1 de coordonnées (700, 0) et à la deuxième étape nous nous déplacerons au point X*. Par l’autre chemin, le point X* peut être atteint en seulement trois étapes. D'un point de vue informatique, la méthode du simplexe est mise en œuvre à travers les tableaux dits simplexes, qui sont calculés pour chaque point d'angle, à partir du point de référence. Les tableaux simplex permettent de déterminer l'optimalité de la décision prise, les valeurs des variables, d'évaluer les paramètres des ressources (contraintes) pour leur rareté et, en cas de décision non optimale, d'indiquer comment passer à la suivante. point (le tableau suivant). En vertu de diverses fonctionnalités et les énoncés de problèmes, la méthode LP simplexe présente diverses modifications : directe, double, en deux étapes.

Pour implémenter l'une des méthodes simplexes, il est nécessaire construire le plan de référence initial .

Supposons que le système de restrictions soit le suivant :

En ajoutant des variables supplémentaires aux côtés gauches de l'inégalité Xn+je ≥ 0, je = 1, m, nous obtenons un problème canonique (étendu), stratégiquement équivalent à celui d'origine, avec un système de restrictions :

Alors le plan de référence initial sera le vecteur

Ce qui satisfait à la recevabilité de la solution (c'est basique, puisque le nombre d'éléments non nuls est égal à m, et soutenir, parce que Tous Xj≥0). Supposons que le système de restrictions soit le suivant :

Soustraire des variables supplémentaires des côtés gauches de l'inégalité Xn+je ≥ 0, je = 1, m, on obtient un problème étendu, stratégiquement équivalent à celui d'origine, avec un système de restrictions :

Cependant, des variables supplémentaires entrent désormais dans la partie gauche des contraintes avec des coefficients égaux à moins un. C'est pourquoi le plan

ne remplit pas les conditions de recevabilité d'une solution (elle est fondamentale, mais pas de référence).

Dans le premier comme dans le deuxième cas, lors de l'ajout de variables supplémentaires (elles deviennent également des variables de base) au système de contraintes, ces mêmes variables sont introduites dans la fonction objectif avec des coefficients égaux à zéro : Cn+je ≥ 0, je = 1, m, c'est à dire. dans la fonction objectif, il y a des coefficients nuls pour les variables de base et des coefficients pour les variables non fondamentales AVEC j, j = 1, n. Que la fonction objectif tende vers un minimum. Ensuite, la valeur de la fonction objectif peut être réduite si cette variable est introduite dans la base X j , auquel le coefficient AVEC j de la fonction objectif a un signe moins. Et si tous les coefficients de la fonction objectif ont un signe plus, alors il n'est pas possible de réduire sa valeur. Par conséquent, les coefficients (estimations) de la fonction objectif pour les variables non fondamentales servent de signe de l'optimalité de la solution ZLP.

En fonction du respect des conditions d'optimalité et d'admissibilité, l'un ou l'autre schéma de résolution du PLP est utilisé.

Les méthodes de résolution de problèmes sont divisées en deux groupes :

1) méthodes d'amélioration séquentielle de la solution. Ils sont basés sur le mouvement du point initial (toute solution admissible, mais non optimale au problème sous forme canonique) jusqu'à la solution optimale

Pointez en un nombre fini d’étapes (itérations). Ce groupe comprend la méthode du simplexe direct, la méthode du potentiel et d'autres ;

2) méthodes de réduction séquentielle des résidus. Ils sont basés sur le mouvement depuis le point initial conditionnellement optimal, qui se situe en dehors de la région des solutions admissibles, mais satisfait au critère d'optimalité de la solution, jusqu'au point optimal et admissible. Ce groupe comprend la méthode dual simplex, méthode hongroise et d'autres. Tous les algorithmes permettant de résoudre le problème sont basés sur la forme canonique du problème. Par conséquent, le nombre de variables requises problème canonique sera supérieur à celui d'origine.

Lors du choix d'un algorithme pour résoudre le problème LP, nous partons des données suivantes. Soit le ZLP réduit à la forme canonique, résolu pour les coefficients minimaux et libres bje ≥ 0, je = 1, m. Ensuite, si la fonction objectif du problème a des coefficients négatifs (la condition de solution optimale du problème n'est pas remplie), et que le plan initial du problème n'a pas de valeurs négatives des variables (la condition de recevabilité de résoudre le problème est satisfait), alors pour résoudre le problème proposé, vous devez utiliser l'algorithme de la méthode du simplexe direct (Tableau 3.2). La méthode dual simplex est utilisée si la condition d'optimalité pour résoudre le problème est satisfaite, mais que la condition d'admissibilité ne l'est pas. La méthode du simplexe en deux étapes est utilisée si les conditions d'optimalité et de faisabilité de la résolution du problème ne sont pas remplies.

Tableau 3.2

Considérons méthode du simplexe direct résoudre les problèmes LP à l’aide de l’exemple suivant.

Exemple 3.1

Fonction Réduire Z = -X 1 - X 2 avec restrictions : 0,5 X 1 + X 2 ≤ 1;

2X 1 + X 2 ≤ 2;

X 1 , X 2 ≥ 0.

Une représentation graphique du problème (3.11-3.14) est présentée sur la Fig. 3.3.

Riz. 3.3. Représentation graphique du problème (3.11) - (3.14)

Le point de référence de base initial du problème sera le vecteur X 0 = (0 ; 0 ; 1 ; 2). La valeur de la fonction objectif à ce stade Z(X0) = 0.

Transférons la variable à la fonction objectif (3.11) Z pour le signe égal et cette tâcheÉcrivons-le sous forme de tableau. 3.3, appelée table simplexe (itération nulle).

Tableau 3.3

D'autres formes de notation de tableaux simplexes sont décrites dans la littérature. En utilisant le tableau simplexe, vous pouvez toujours savoir si la solution trouvée est optimale. Dans ce cas la solution X 1 = 0; X 2 = 0; X 3 = 1; X 4 = 2 n'est pas le meilleur, puisqu'une des variables peut être introduite dans la base X 1 ou X 2 (ces variables ont des coefficients avec un signe moins Avec 1 = -1 et Avec 2 = - 1), réduisant la valeur de la fonction objectif. Puis introduire dans la base une des variables non fondamentales X 1 ou X 2 (en augmentant sa valeur), la variable doit être dérivée de la base X 3 ou X 4 (ramenant sa valeur à zéro). Dans la méthode du simplexe direct, les questions suivantes sont considérées séquentiellement :

• 
  
• 
  
• 
  transition vers la nouvelle forme canonique du ZLP (vers la prochaine itération de la table simplex).

. Il est conseillé d'inclure dans la base la variable dont le coefficient a la plus petite valeur. Les coefficients des variables non fondamentales dans une solution non optimale ont des valeurs négatives. Que ce soit une variable Xs, Pour qui Cs= min j, Avec j< 0, j pas ∈ base. Dans notre exemple c 1 = c 2 = -1, incluons donc n'importe quelle variable dans la base X 1 ou X 2 (laissez X 1). Colonne dans un tableau simplex avec une variable Xs appelons cela la colonne principale, dans notre cas s= l.

. Si nous incluons une variable dans la base X 1, cela signifie que nous augmentons sa valeur de zéro jusqu'à certaines limites. Jusqu'à quoi? Passons à la Fig. 3.3. Valeur extrême pour une variable X 1 sera un, et la variable (directe) X 4 dans la contrainte (3.13) prendra une valeur égale à zéro, c'est-à-dire qu'elle sortira de la base X 4 , et sa place sera prise par la variable X 1 . À partir de l'équation (3.12), nous déterminons la valeur X 3 = 1 - 0,5 1 = 0,5. Ainsi, à la prochaine itération (étape), la solution réalisable sera le vecteur X 1 = (1 ; 0 ; 0,5 ; 0). La valeur de la fonction objectif à ce stade Z(1) = -1.

Sans recourir à une représentation graphique du problème, déterminer la valeur limite X l et définition des variables X 4, qui doit être dérivé de la base, peut être réalisé sur la distribution suivante. Si vous dérivez une variable de la base X 3, c'est-à-dire il doit y avoir X 3 = 0, alors de (3.12) il découle X je = b 1 /un 1 s= 1/0,5 = 2. Si vous dérivez une variable de la base X 4, c'est-à-dire faire X 4 = 0, donc de (3.13) X je = b 2 /un 2 s= 1/1 = 1. Il s'avère que la valeur X l = 1 ou X l = 2. Mais quand X l = 2 dans l'équation (3.13) variable X 4 = 1 - 2 - 0,5 · 0 = -1, ce qui contredit la condition de recevabilité de la solution (3.14). Nous incluons donc dans la base X l avec la plus petite valeur, qui est déterminée à partir de la deuxième contrainte. Cette contrainte contient la variable à exclure de la base X 4 . En général, la variable Xs, inclus dans la base, peut augmenter jusqu'à la valeur

Que le maximum soit atteint dans la ligne r, c'est à dire. Xs = br/unrs, alors dans cette ligne la variable de base devient nulle, c'est-à-dire est dérivé de la base. Chaîne r appelé ligne directrice, et l'élément UNrs - élément principal. S'il n'y a pas de positif dans la première colonne unest, cela signifie que le ZLP n'a pas de région de solutions réalisables.

Transition vers la nouvelle forme canonique du ZLP . Dans le tableau La figure 3.4 montre les transitions de l'itération zéro aux méthodes suivantes pour éliminer séquentiellement la variable de base nouvellement introduite des lignes non principales. Nouvelle ligne lors de l'itération suivante avec la variable de base nouvellement introduite, elle est obtenue en divisant les éléments de la ligne principale par l'élément principal ; par rapport à la ligne résultante, la nouvelle variable de base est alors exclue des autres lignes. Dans le tableau 3.4 à l'itération 1' sont indiqués les coefficients des variables de base, sous lesquels la transition correspondante est effectuée. Les principaux éléments du tableau sont marqués d'un astérisque.

Le calcul des coefficients à l'itération suivante peut être effectué selon la règle du quadrilatère.

Ce tableau à l'itération 2 correspond à la solution optimale X* = X 2 = (2/3 ; 2/3 ; 0 ; 0).

Valeur de la fonction objectif Z(X*) = -4/3.

Tableau 3.4

Considérons méthode double simplexe résoudre le problème LP en utilisant l’exemple suivant.

Exemple 3.2

Maximiser la fonction Z = -X 1 - X 2 avec restrictions :

0,5X 1 + X 2 ≤ 1;

2X 1 + X 2 ≥ 2;

X 1 , X 2 ≥ 0.

Sous la forme canonique, le ZLP prendra la forme

Une représentation graphique du problème est présentée sur la Fig. 3.4.

Riz. 3.4. Représentation graphique du problème (3.15) - (3.18)

Faisons un tableau simplexe 3.5.

Tableau 3.5

Ligne zéro dans le tableau. 3.5 indique que le critère de solution optimale du problème est satisfait (il n'y a pas de coefficients négatifs).

Cependant, la solution initiale X 0 = (0 ; 0 ; 1 ; -2) est négative.

Essayons de résoudre le problème (par opposition à la méthode du simplexe direct) par un mouvement séquentiel du point inacceptable initial X 0 à X *, en considérant les questions :

• 
  rechercher une variable à exclure de la base ;
• 
  rechercher une variable à inclure dans la base ;
• 
  transition vers une nouvelle forme du PLP (itération ultérieure de la solution).

Rechercher une variable à exclure de la base . La variable de la première ligne est exclue de la base r, qui a la plus petite valeur négative. Si toutes les variables situées dans la base sont positives, alors les calculs se terminent, puisque la solution

Ce sera à la fois optimal et acceptable. Dans notre exemple, nous excluons la variable X 4 = -2.

Rechercher une variable à inclure dans la base . Quelle variable non fondamentale doit être incluse dans la base ? X 1 ou X 2 ? En principe, n’importe qui peut être inclus dans la base dans le but d’avancer dans la région des solutions réalisables. D'après la représentation graphique du problème (voir Fig. 3.4), il est clair que lorsqu'une variable est incluse dans la base X 2, nous nous trouvons immédiatement au point X* admissible et optimal. La littérature montre que vous pouvez obtenir plus rapidement la solution optimale si vous choisissez une variable à inclure dans la base. Xs telle que pour elle l'attitude Cs/|unrs| pour tous les éléments unrs la ligne directrice sera minimale :

Si tous les éléments unrj· ≥ 0, cela signifiera que le problème n'a pas de solutions réalisables. Dans notre exemple, le rapport minimum (3,19) est atteint pour la variable X 1 est égal à 1/2. Résolvons le problème en utilisant une méthode tabulaire (tableau 3.6).

Tableau 3.6

Solution optimale: X* = (1; 0; 1/2; 0;); Z(X*) = -z" = -1.

Supposons qu’en résolvant l’exemple précédent (voir tableau 3.6), nous n’incluions pas dans la base X 1 et la variable X 2, alors nous obtiendrions le tableau suivant à l’itération 1. 3.7.

Tableau 3.7

Ligne zéro dans le tableau. 3.7 indique que le critère d'optimalité pour résoudre le problème n'est pas satisfait et que la solution intermédiaire X 1 = (0 ; 2 ; -1 ; 0) est inacceptable. De plus, le problème peut être résolu en utilisant la méthode du simplexe en deux étapes, la méthode des pénalités importantes, etc. Considérons méthode simplex en deux étapes .

1. Nous introduisons une variable supplémentaire, les rendant fondamentales, dans les équations dans lesquelles les conditions d'admissibilité n'étaient pas remplies. Dans notre cas, nous introduisons la variable X 5 à la ligne (1), en changeant d'abord les signes par les signes opposés (tableau 3.8), et la colonne sous X 5:

3/2 X 1 - X 3 - X 4 + X 5 = 1.

2. Nous introduisons une nouvelle fonction objectif (fictive) W comme la somme des variables supplémentaires nouvellement introduites, exprimées par des variables non fondamentales. Dans notre cas W = X 5 = 1 - 3/2 X 1 + X 3 + X 4 . Nous ajoutons une ligne supplémentaire (3) au tableau. 3.8 avec fonction objectif factice - W - 3/2 X 1 + X 3 + X 4 = -1.

3. Nous utilisons la méthode du simplexe direct pour minimiser la cible fictive W avec recalcul de tous les coefficients. La première étape se termine si la fonction objectif fictive W va à zéro W= 0, et donc les variables supplémentaires auront également des valeurs nulles. De plus, la ligne contenant la fonction objectif fictive et les colonnes contenant des variables supplémentaires ne sont pas prises en compte. Si, suite à la minimisation de la cible W on a valeur optimale W, différent de zéro W≠ 0, cela signifiera que le ZLP d'origine n'a aucune solution admissible.

Nous utilisons la méthode du simplexe direct pour optimiser le principal

fonction objectif Z. Nous incluons une variable dans la base X 3 au lieu d'une variable X 2. On recalcule les coefficients à l'itération 3 et obtenons la solution optimale : X* = (1 ; 0 ; 1/2 ; 0 ;) ; Z(X*) = - z" = -1.

Tableau 3.8

50 :: 51 :: 52 :: 53 :: 54 :: 55 :: 56 :: 57 :: 58 :: 59 :: 60 :: 61 :: Contenu

61 :: 62 :: 63 :: 64 :: 65 :: 66 :: 67 :: 68 :: 69 :: 70 :: Contenu

3.2.4. Analyse d'un modèle de problème de programmation linéaire

Les données du tableau simplex optimal permettent une analyse complète du modèle linéaire, notamment une analyse de la sensibilité de la solution optimale aux changements des réserves de ressources et aux variations des coefficients de la fonction objectif. Donnons d'abord la notion de dualité des problèmes de programmation linéaire.

Considérons le problème de programmation linéaire (3.20)-(3.22) en utilisant le problème d'utilisation des ressources comme exemple. Si pour cette ZLP initiale (appelons-la directe) on introduit des variables ouije pour estimer les contraintes de ressources (3.21) et faire la transition vers la formulation mathématique d'un autre problème (dual ou inverse) de la forme (3.23)-(3.25), alors les solutions aux problèmes directs et duaux seront mutuellement dépendantes, exprimées par les théorèmes de dualité correspondants.

Évidemment, le problème du dual au dual coïncide avec celui d’origine. Par conséquent, il n’y a aucune différence entre celui qui est accepté comme direct et celui qui est double. Ils parlent de deux problèmes mutuellement doubles.

27 août 2017 à 14h20

La solution est directe et double problème programmation linéaire en utilisant Python

Introduction

Il convient de noter que les méthodes de résolution des problèmes de programmation linéaire comprennent non pas à l’économie, mais aux mathématiques et à l’informatique. Dans le même temps, l'économiste doit offrir les conditions de dialogue les plus confortables avec le logiciel approprié. À leur tour, de telles conditions ne peuvent être assurées que par des environnements de développement dynamiques et interactifs qui disposent dans leur arsenal d'un ensemble de bibliothèques nécessaires à la résolution de tels problèmes. L'un des environnements de développement logiciel est définitivement Python.

Formulation du problème

Les publications envisageaient des solutions aux problèmes d'optimisation directe à l'aide de la méthode de programmation linéaire et suggéraient un choix raisonnable du solveur scipy. optimiser.

Or, on sait qu'à chaque problème de programmation linéaire correspond un problème dit distingué (dual). Dans celui-ci, par rapport au problème direct, les lignes se transforment en colonnes, les inégalités changent de signe, au lieu d'un maximum, un minimum est recherché (ou vice versa, au lieu d'un minimum, un maximum est recherché). La tâche duale au dual est la tâche originelle elle-même.

La résolution de ce double problème est très importante pour analyser l’utilisation des ressources. Dans cette publication, il sera prouvé que les valeurs optimales des fonctions objectives dans les problèmes original et dual coïncident (c'est-à-dire que le maximum dans le problème original coïncide avec le minimum dans le dual).

Les valeurs optimales des coûts de matériel et de main d'œuvre seront évaluées par leur contribution à la fonction objectif. Le résultat sera des « estimations objectivement déterminées » des matières premières et de la main-d’œuvre qui ne coïncident pas avec les prix du marché.

Solution du problème direct du programme de production optimal

Considérant haut niveau formation mathématique de la grande majorité des utilisateurs de cette ressource Je ne présenterai pas d'équations d'équilibre avec des restrictions supérieures et inférieures et l'introduction de variables supplémentaires pour le passage aux égalités. Je donnerai donc immédiatement les désignations des variables utilisées dans la solution :
N – nombre de types de produits fabriqués ;
m – nombre de types de matières premières utilisées ;
b_ub - vecteur de ressources disponibles de dimension m ;
A_ub est une matrice de dimension m×N dont chaque élément est la consommation d'une ressource de type i pour la production d'une unité de produit de type j ;
c est le vecteur de profit de la production d'une unité de chaque type de produit ;
x – les volumes requis de produits fabriqués de chaque type (plan de production optimal) garantissant un profit maximum.

Fonction d'objectif
maxF(x)=c×x

Restrictions
A×x≤b

Valeurs numériques des variables :
N=5 ; m = 4 ; b_ub = ; A_ub = [, , ,]; c = .

Tâches
1. Trouvez x pour assurer un profit maximum
2. Recherchez les ressources utilisées lors de l'exécution de l'étape 1
3. Recherchez les ressources restantes (le cas échéant) lors de l'exécution de l'étape 1

Pour déterminer le maximum (par défaut, le minimum est déterminé, les coefficients de la fonction objectif doivent être écrits avec un signe négatif c = [-25, -35,-25,-40,-30] et ignorer le signe moins devant le profit.

Notations utilisées pour afficher les résultats :
X– un tableau de valeurs variables qui fournissent le minimum (maximum) de la fonction cible ;
mou– valeurs de variables supplémentaires. Chaque variable correspond à une contrainte d'inégalité. Une valeur variable de zéro signifie que la contrainte correspondante est active ;
succès– Vrai, si la fonction a réussi à trouver la solution optimale ;
statut– statut de la décision :
0 – la recherche de la solution optimale s'est terminée avec succès ;
1 – la limite du nombre d'itérations a été atteinte ;
2 – le problème n’a pas de solution ;
3 – la fonction objectif n’est pas limitée.
lente– nombre d'itérations effectuées.

Listage de la solution au problème d'optimisation directe

#!/usr/bin/python # -*- codage : utf-8 -*- import scipy depuis scipy.optimize import linprog # chargement de la bibliothèque LP c = [-25, -35,-25,-40,-30] # liste des coefficients de la fonction objectif b_ub = # liste des volumes de ressources A_ub = [, # matrice de valeurs de ressources spécifiques, , ] d=linprog(c, A_ub, b_ub) # recherche d'une solution pour key,val in d.items(): print(key ,val) # sortie de la solution if key=="x": q=#ressources utilisées print("A_ub*x",q) q1= scipy.array(b_ub)-scipy.array (q) #ressources restantes print(" b_ub-A_ub*x", q1)

Résultats de la résolution du problème
lente 3
statut 0

succès Vrai
x [ 0. 0. 18.18181818 22.72727273 150. ]
A_ub*x
b_ub-A_ub*x [0.0.0.90.90909091]
amusant -5863.63636364
mou [0. 0. 0. 90.90909091]

conclusions

1. Le plan optimal pour les types de produits a été trouvé
2. Utilisation réelle des ressources trouvée
3. Le reste du quatrième type de ressource inutilisé a été trouvé [ 0. 0 0.0 0.0 90.909]
4. Il n'est pas nécessaire d'effectuer les calculs selon l'étape 3, puisque le même résultat est affiché dans la variable slack

Solution du double problème sur le programme de production optimal

Le quatrième type de ressource dans la tâche directe n'est pas entièrement utilisé. La valeur de cette ressource pour l'entreprise s'avère alors inférieure à celle des ressources qui limitent la production, et l'entreprise est prête à payer un prix plus élevé pour l'acquisition de ressources qui augmentent les profits.

Introduisons un nouvel objectif pour la variable souhaitée x en tant que prix « fictif » qui détermine la valeur d'une ressource donnée par rapport au profit de la vente de produits manufacturés.

C – vecteur de ressources disponibles ;
b_ub est le vecteur de profit de la production d'une unité de chaque type de produit ;
A_ub_T – matrice transposée A_ub.

Fonction d'objectif
minF(x)=c×x

Restrictions
A_ub_T ×x≥ b_ub

Valeurs numériques et relations pour les variables :
c = ; A_ub_T transpose(A_ub); b_ub = .

Tâche:
Trouvez x indiquant la valeur pour le producteur de chaque type de ressource.

Fonctionnalités de la solution avec la bibliothèque scipy. optimiser
Pour remplacer les restrictions d'en haut par des restrictions d'en bas, il faut multiplier les deux parties de la contrainte par moins un – A_ub_T ×x≥ b_ub... Pour ce faire, écrivez les données d'origine sous la forme : b_ub = [-25, -35,-25,-40,-30] ; A_ub_T =- scipy.transpose(A_ub).

Listing de la solution au problème de double optimisation

#!/usr/bin/python # -*- codage : utf-8 -*- importer scipy depuis scipy.optimize import linprog A_ub = [, , , ] c= b_ub = [-25, -35,-25,- 40,-30] A_ub_T =-scipy.transpose(A_ub) d=linprog(c, A_ub_T, b_ub) pour key,val dans d.items() : print(key,val)

Résultats de la résolution du problème
lenteur 7
message L'optimisation s'est terminée avec succès.
amusant 5863.63636364
x [ 2,27272727 1,81818182 6,36363636 0. ]
mou [5.45454545 2.27272727 0. 0. 0. ]
statut 0
succès Vrai

conclusions

Le troisième type de ressource a la plus grande valeur pour le fabricant, donc ce type les ressources doivent être achetées en premier, puis les premier et deuxième types. Le quatrième type de ressource a une valeur nulle pour le fabricant et est acheté en dernier.

Résultats de la comparaison des problèmes directs et duaux

1. Le double problème étend les capacités de planification de produits, mais en utilisant scipy. L'optimisation est résolue en deux fois plus d'itérations directes.
2. La variable slack affiche des informations sur l'activité des contraintes sous forme d'inégalités, qui peuvent être utilisées, par exemple, pour analyser les bilans de matières premières.
3. Le problème direct est un problème de maximisation, et le problème dual est un problème de minimisation, et vice versa.
4. Les coefficients de la fonction objectif dans le problème direct sont des contraintes dans le problème dual.
5. Les contraintes du problème direct deviennent des coefficients de la fonction objectif du problème dual.
6. Les signes d’inégalités en matière de restrictions s’inversent.
7. La matrice du système d’égalités est transposée.

Liens

Définition. Toute solution au système de contraintes est appelée solution admissible au PLP.
Définition. Une solution réalisable dans laquelle la fonction objectif atteint une valeur maximale ou minimale est appelée solution optimale.

Grâce à ces définitions, le problème LP peut être formulé comme suit : parmi tous les points d'une région convexe, qui est une solution à un système de contraintes, choisissez celui dont les coordonnées minimisent (maximisent) fonction linéaire F = Avec 1 X + Avec 2 oui.
Notez que les variables X, oui dans le ZLP, en règle générale, ils prennent des valeurs non négatives ( X≥ 0, oui≥ 0), donc la région est située dans le premier quart du plan de coordonnées.

Considérons la fonction linéaire F = Avec 1 X + Avec 2 oui et fixer une partie de sa valeur F. Laissez, par exemple, F= 0, c'est à dire Avec 1 X + Avec 2 oui= 0. Le graphique de cette équation sera une ligne droite passant par l'origine des coordonnées (0;0) (Fig.).
Dessin
Lors de la modification de cette valeur fixe F = d, droit Avec 1 X+ Avec 2 y = ré se déplacera parallèlement et « délimitera » l’ensemble du plan. Laisser D– polygone – domaine de solution du système de contraintes. Quand ça change d droit Avec 1 X + Avec 2 oui = d, à une certaine valeur d = d 1 atteindra le polygone D, appelons ce point UN"point d'entrée", puis, après avoir dépassé le polygone, à une certaine valeur d = d 2 on aura le dernier point commun avec lui DANS, appelons DANS"point de sortie".
Il est évident que la fonction objectif a ses valeurs les plus petites et les plus grandes. F=Avec 1 X + Avec 2 oui atteindra aux points d'entrée UN et "sortie" DANS.
Considérant que la valeur optimale sur l'ensemble des solutions réalisables, la fonction objectif prend les sommets de la région D, nous pouvons proposer le plan suivant pour résoudre le problème :

1. construire le domaine de solution du système de contraintes ;
2. construire une droite correspondant à la fonction objectif, et par translation parallèle de cette droite trouver le point « d'entrée » ou de « sortie » (selon la nécessité de minimiser ou de maximiser la fonction objectif) ;
3. déterminer les coordonnées de ce point et calculer la valeur de la fonction objectif qui s'y trouve.

Notez que le vecteur ( Avec 1 , Avec 2), perpendiculaire à la droite, montre le sens de croissance de la fonction objectif.

À solution graphique Il existe deux cas possibles de PAP qui nécessitent une discussion particulière.

Cas 1
Figure 6
Lors d'un déplacement en ligne droite Avec 1 X + Avec 2 oui= d« l'entrée » ou la « sortie » (comme dans la figure) se produira le long du côté du polygone. Cela se produira si le polygone a des côtés parallèles à la ligne Avec 1 X+ Avec 2 à = d .
Dans ce cas, il existe un nombre infini de points de « sortie » (« d'entrée »), à savoir n'importe quel point du segment. UN B. Cela signifie que la fonction objectif prend la valeur maximale (minimale) non pas en un point, mais en tous les points situés du côté correspondant du polygone. D.

Cas 2
Considérons le cas où la plage de valeurs admissibles est illimitée.
Dans le cas d'un domaine illimité, la fonction objectif peut être spécifiée de telle sorte que la droite correspondante n'ait pas de point de « sortie » (ou d'« entrée »). Ensuite, la valeur maximale de la fonction (minimum) n'est jamais atteinte - on dit que la fonction est illimitée.
Dessin
Il faut trouver la valeur maximale de la fonction objectif F = 4X + 6oui→ max , avec un système de 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étermine les demi-plans définis par les inégalités.
X + oui = 18

X	12	9
oui	6	9

0,5X + oui = 12

X	12	18
oui	6	3

X= 12 – parallèle à l'axe OY ;
oui= 9 – parallèle à l'axe BŒUF ;
X= 0 – axe OY ;
oui = 0 – axe BŒUF;
X≥ 0 – demi-plan à droite de l'axe OY;
oui≥ 0 – demi-plan au dessus de l'axe BŒUF;
oui≤ 9 – demi-plan ci-dessous oui = 9;
X ≤ 12 – demi-plan à gauche X = 12;
0,5X + oui≤ 12 – demi-plan en dessous de la droite 0,5 X + oui = 12;
X + oui≤ 18 – demi-plan en dessous de la droite X + oui = 18.
Dessin
L'intersection de tous ces demi-plans est évidemment un pentagone OAVSD, avec des sommets aux points À PROPOS(0; 0), UN(0; 9), DANS(6; 9), AVEC(12; 6), D(12 ; 0). Ce pentagone constitue la région des solutions réalisables au problème.

Considérez la fonction objective du problème F = 4X + 6oui→ maximum.

X	3	0
oui	–2	0

Construisons une droite correspondant à la valeur de la fonction F = 0: 4X + 6oui= 0. Nous déplacerons cette ligne de manière parallèle. De toute la famille des lignées 4 X+ 6oui= const le dernier sommet par lequel passera la ligne en quittant la limite du polygone sera le sommet AVEC(12 ; 6). C'est dedans F = 4X + 6oui atteindra sa valeur maximale.
Donc quand X = 12, oui= 6 fonctions F atteint sa valeur maximale F= 4 ∙ 12 + 6 ∙ 6 = 84, égal à 84. Le point de coordonnées (12 ; 6) satisfait toutes les inégalités du système de contraintes, et dans celui-ci la valeur de la fonction objectif est optimale F* = 84 (nous désignerons la valeur optimale par « * »).
Le problème est résolu. Il est donc nécessaire de fabriquer 12 produits de type I et 6 produits de type II, avec un bénéfice de 84 000 roubles.

La méthode graphique est utilisée pour résoudre des problèmes comportant seulement deux variables dans le système de contraintes. Cette méthode peut également être utilisée pour les systèmes d'inégalités à trois variables. Géométriquement, la situation sera différente, le rôle des lignes droites sera joué par les plans dans l'espace tridimensionnel, et la solution de l'inégalité à trois variables sera un demi-espace situé d'un côté du plan. Le rôle des aires sera joué par les polyèdres, qui sont l'intersection de demi-espaces.

Les paramètres de conception. Ce terme désigne des paramètres variables indépendants qui déterminent complètement et sans ambiguïté le problème de conception à résoudre. Les paramètres de conception sont des quantités inconnues dont les valeurs sont calculées lors du processus d'optimisation. Toutes les grandeurs de base ou dérivées servant à décrire quantitativement le système peuvent servir de paramètres de conception. Il peut donc s'agir de valeurs inconnues de longueur, de masse, de temps, de température. Le nombre de paramètres de conception caractérise le degré de complexité d'un problème de conception donné. Habituellement, le nombre de paramètres de conception est noté n et les paramètres de conception eux-mêmes par x avec les indices correspondants. Ainsi, n paramètres de conception de ce problème seront notés

X1, X2, X3,...Xp.

Il convient de noter que les paramètres de conception peuvent être appelés paramètres internes contrôlables dans certaines sources.

Fonction cible. C'est une expression dont l'ingénieur s'efforce de rendre maximale ou minimale la valeur. La fonction objectif vous permet de comparer quantitativement deux Solutions alternatives. D'un point de vue mathématique, la fonction objectif décrit une surface à (n+1) dimensions. Sa valeur est déterminée par les paramètres de conception

M = M (x1,x2,…,xn).

Des exemples de fonctions objectives souvent rencontrées dans la pratique de l'ingénierie sont le coût, le poids, la résistance, les dimensions et l'efficacité. S'il n'y a qu'un seul paramètre de conception, alors la fonction objectif peut être représentée par une courbe sur le plan (Fig. 1). S'il existe deux paramètres de conception, alors la fonction objectif sera représentée comme une surface dans un espace tridimensionnel (Fig. 2). Avec trois paramètres de conception ou plus, les surfaces spécifiées par la fonction objectif sont appelées hypersurfaces et ne peuvent pas être représentées par des moyens conventionnels. Les propriétés topologiques de la surface de la fonction objectif jouent un rôle important dans le processus d'optimisation, puisque le choix de l'algorithme le plus efficace en dépend.

Figure 1. Fonction objectif unidimensionnelle.

Figure 2. Fonction objectif bidimensionnelle.

La fonction objectif peut dans certains cas prendre les formes les plus inattendues. Par exemple, il ne peut pas toujours être exprimé sous une forme mathématique fermée ; dans d'autres cas, il peut s'agir d'une fonction linéaire par morceaux. La spécification d'une fonction objectif peut parfois nécessiter un tableau de données techniques (par exemple, un tableau de l'état de la vapeur d'eau) ou nécessiter une expérience. Dans certains cas, les paramètres de conception prennent uniquement des valeurs entières. Un exemple serait le nombre de dents dans un train d’engrenages ou le nombre de boulons dans une bride. Parfois, les paramètres de conception n’ont que deux significations : oui ou non. Les paramètres qualitatifs, tels que la satisfaction ressentie par l'acheteur qui a acheté le produit, la fiabilité, l'esthétique, sont difficiles à prendre en compte dans le processus d'optimisation, car ils sont quasiment impossibles à caractériser quantitativement. Cependant, quelle que soit la forme sous laquelle la fonction objectif est présentée, elle doit être une fonction sans ambiguïté des paramètres de conception.

Un certain nombre de problèmes d'optimisation nécessitent l'introduction de plus d'une fonction objectif. Parfois, l’un d’eux peut être incompatible avec l’autre. Un exemple est la conception d’avions, où une résistance maximale, un poids minimum et un coût minimum sont simultanément requis. Dans de tels cas, le concepteur doit introduire un système de priorités et attribuer un certain facteur sans dimension à chaque fonction objectif. En conséquence, une « fonction de compromis » apparaît, qui permet l'utilisation d'une fonction objectif composite pendant le processus d'optimisation.

Recherchez le minimum et le maximum. Certains algorithmes d'optimisation sont conçus pour trouver le maximum, d'autres pour trouver le minimum. Cependant, quel que soit le type de problème extremum résolu, vous pouvez utiliser le même algorithme, car le problème de minimisation peut facilement être transformé en problème de recherche maximale en inversant le signe de la fonction objectif. Cette technique est illustrée sur la figure 3.

Figure 3. Lorsque le signe de la fonction objectif change à l'opposé dans un problème minimum, cela le transforme en problème maximum.

Espace de conception. Il s'agit du nom de la zone définie par les n paramètres de conception. L’espace de conception n’est pas aussi vaste qu’il y paraît, car il est généralement limité par un certain nombre de conditions liées à la nature physique du problème. Les restrictions peuvent être si fortes que le problème ne trouvera pas une seule solution satisfaisante. Les contraintes sont divisées en deux groupes : contraintes - égalité et contraintes - inégalité.

Les contraintes d'égalité sont des dépendances entre les paramètres de conception qui doivent être prises en compte lors de la recherche d'une solution. Ils reflètent les lois de la nature, de l'économie, du droit, des goûts dominants et de la disponibilité. matériel nécessaire. Le nombre de contraintes - les égalités peuvent être quelconques. Ils ressemblent à

C1 (X1, X2, X3, . . ., Xn) = 0,

C2 (X1, X2, X3, . . ., Xn) = 0,

..……………………………..

Cj(X1, X2, X3,..., Xn) = 0.

Les contraintes d'inégalité sont un type particulier de contrainte exprimée par les inégalités. Dans le cas général, il peut y en avoir autant que l'on veut, et ils ont tous la forme

z1 ?r1(X1, X2, X3, . . ., Xn) ?Z1

z2 ?r2(X1, X2, X3, . . ., Xn) ?Z2

………………………………………

zk ?rk(X1, X2, X3, . . ., Xn) ?Zk

Il convient de noter que très souvent, en raison de restrictions, la valeur optimale de la fonction objectif n'est pas atteinte là où sa surface présente un gradient nul. Souvent La meilleure décision correspond à l’une des limites de la zone de conception.

Restrictions directes et fonctionnelles. Les restrictions directes ont la forme

xni ? XI ? xвi à je? ,

où xнi, xвi - minimum et maximum valeurs valides i-ième paramètre contrôlé ; n est la dimension de l'espace des paramètres contrôlés. Par exemple, pour de nombreux objets, les paramètres des éléments ne peuvent pas être négatifs : xнi ? 0 (dimensions géométriques, résistance électrique, masse, etc.).

En règle générale, les restrictions fonctionnelles représentent les conditions d'exécution des paramètres de sortie qui ne sont pas inclus dans la fonction cible. Les restrictions fonctionnelles peuvent être :

• 1) type d'égalités
• w(X) = 0 ; (2.1)
• 2) type d'inégalités

tz (X) › 0, (2.2)

où w(X) et q(X) sont des fonctions vectorielles.

Les restrictions directes et fonctionnelles forment la zone de recherche autorisée :

ХД = (Х | w(Х) = 0, ц (Х)›0, xi › xнi ,

xi ‹ xвi pour je ? ).

Si les restrictions (2.1) et (2.2) coïncident avec les conditions de performance, alors la zone autorisée est également appelée zone de performance XP.

N'importe lequel des points X appartenant au CD est une solution réalisable au problème. La synthèse paramétrique est souvent posée comme le problème de la détermination de l'une des solutions réalisables. Cependant, il est bien plus important de résoudre le problème d'optimisation - de trouver la solution optimale parmi celles réalisables.

Optimale locale. C'est le nom du point de l'espace de conception auquel la fonction objectif a valeur la plus élevée par rapport à ses valeurs en tous autres points de son voisinage immédiat. La figure 4 montre une fonction objectif unidimensionnelle qui a deux optima locaux. Souvent, l’espace de conception contient de nombreux optima locaux et il faut veiller à ne pas confondre le premier avec la solution optimale au problème.

Figure 4. Une fonction objectif arbitraire peut avoir plusieurs optima locaux.

L'optimum global est la solution optimale pour l'ensemble de l'espace de conception. C'est mieux que toutes les autres solutions correspondant aux optima locaux, et c'est ce que recherche le concepteur. Il est possible qu’il existe plusieurs optima globaux égaux situés dans différentes parties de l’espace de conception. Cela vous permet de sélectionner Meilleure option d'égaux options optimales par fonction objectif. Dans ce cas, le concepteur peut choisir une option de manière intuitive ou sur la base d'une comparaison des options résultantes.

Sélection de critères. Le principal problème dans la formulation de problèmes extrêmes est la formulation de la fonction objectif. La difficulté du choix d'une fonction objectif réside dans le fait que tout objet technique présente initialement un caractère vectoriel de critères d'optimalité (multi-critères). De plus, une amélioration de l'un des paramètres de sortie entraîne généralement une détérioration de l'autre, puisque tous les paramètres de sortie sont des fonctions des mêmes paramètres contrôlés et ne peuvent pas changer indépendamment les uns des autres. Ces paramètres de sortie sont appelés paramètres de conflit.

Il doit y avoir une fonction cible (principe d'unicité). La réduction d'un problème multicritère à un problème monocritère est appelée convolution d'un critère vectoriel. La tâche de trouver son extremum se réduit à un problème de programmation mathématique. Selon la manière dont les paramètres de sortie sont sélectionnés et combinés dans la fonction de qualité scalaire, on distingue les critères partiels, additifs, multiplicatifs, minimax, statistiques et autres. DANS Termes de référence pour la conception d'un objet technique, les exigences relatives aux principaux paramètres de sortie sont indiquées. Ces exigences sont exprimées sous forme de données numériques spécifiques, de l'étendue de leurs variations, des conditions de fonctionnement et de valeurs minimales ou maximales acceptables. Les relations requises entre les paramètres de sortie et les exigences techniques (TR) sont appelées conditions de performance et s'écrivent sous la forme :

ouais< TTi , i О ; yi >TTj,jO;

année = TTr ± ?année ; rO.

où yi, yj, an - ensemble de paramètres de sortie ;

TTi, TTj, TTr - valeurs quantitatives requises des paramètres de sortie correspondants selon les spécifications techniques ;

Yr est l'écart admissible du r-ième paramètre de sortie par rapport à la valeur TTr spécifiée dans les spécifications techniques.

Les conditions d’exploitation sont d’une importance décisive dans le développement appareils techniques, puisque la tâche de conception consiste à sélectionner une solution de conception dans laquelle la meilleure façon toutes les conditions de fonctionnement sont remplies dans toute la gamme de modifications des paramètres externes et lorsque toutes les exigences des spécifications techniques sont remplies.

Des critères particuliers peuvent être utilisés dans les cas où parmi les paramètres de sortie, un paramètre principal yi(X) peut être identifié, qui reflète le plus pleinement l'efficacité de l'objet conçu. Ce paramètre est pris comme fonction objectif. Des exemples de tels paramètres sont : pour une installation énergétique - la puissance, pour une machine technologique - la productivité, pour véhicule- capacité de chargement. Pour de nombreux objets techniques, ce paramètre est le coût. Les conditions de fonctionnement de tous les autres paramètres de sortie de l'objet sont appelées restrictions fonctionnelles. L'optimisation basée sur une telle formulation est appelée optimisation selon un critère particulier.

L'avantage de cette approche est sa simplicité ; un inconvénient majeur est qu'une grande marge d'efficacité ne peut être obtenue que pour le paramètre principal, qui est accepté comme fonction objectif, et les autres paramètres de sortie n'auront aucune marge du tout.

Le critère additif pondéré est utilisé lorsque les conditions de performance permettent de distinguer deux groupes de paramètres de sortie. Le premier groupe comprend les paramètres de sortie dont les valeurs doivent être augmentées au cours du processus d'optimisation y+i(X) (performances, immunité au bruit, probabilité de fonctionnement sans panne, etc.), le deuxième groupe comprend les paramètres de sortie, dont les valeurs doivent être diminuées y-i (X) ( consommation de carburant, durée du processus transitoire, dépassement, déplacement, etc.). La combinaison de plusieurs paramètres de sortie, qui ont généralement des dimensions physiques différentes, en une seule fonction objectif scalaire nécessite une normalisation préalable de ces paramètres. Les méthodes de normalisation des paramètres seront discutées ci-dessous. Pour l’instant, nous supposerons que tous les y(X) sont sans dimension et parmi eux aucun ne correspond à des conditions de performance de type égalité. Alors, dans le cas de la minimisation de la fonction objectif, la convolution du critère vectoriel aura la forme

où aj>0 est un coefficient de pondération qui détermine le degré d'importance du j-ème paramètre de sortie (généralement, aj est sélectionné par le concepteur et reste constant pendant le processus d'optimisation).

La fonction objectif sous la forme (2.1), exprimant le critère additif, peut également s'écrire dans le cas où toutes ou les principales conditions de performance ont la forme d'égalités. Alors la fonction objectif

détermine l'approximation quadratique moyenne de yj(X) par rapport aux exigences techniques données TTj.

Le critère multiplicatif peut être utilisé dans les cas où il n'y a pas de conditions de performance de type égalité et où les paramètres de sortie ne peuvent pas accepter valeurs nulles. Alors la fonction objectif multiplicative à minimiser a la forme

Un des plus des lacunes importantes Le critère à la fois additif et multiplicatif est la non-prise en compte des exigences techniques pour les paramètres de sortie dans la formulation du problème.

Le critère de forme de fonction est utilisé lorsque la tâche est définie sur la meilleure correspondance d'une caractéristique (de référence) donnée yCT(X, y) avec la caractéristique de sortie correspondante y(X, y) de l'objet conçu, où y est une variable, par exemple, fréquence, temps, variable de phase sélectionnée. Ces tâches comprennent : concevoir un système de contrôle automatique qui fournit le type de processus transitoire requis pour le paramètre contrôlé ; déterminer les paramètres du modèle de transistor qui fournissent un accord maximal entre ses caractéristiques courant-tension théoriques et celles expérimentales ; recherche de paramètres de sections de poutre dont les valeurs conduisent à la meilleure coïncidence du diagramme de contraintes donné avec celui calculé, etc.

L'utilisation d'un critère d'optimisation particulier revient dans ces cas à remplacer les caractéristiques continues par un ensemble fini de points nodaux et à choisir l'une des fonctions objectifs suivantes à minimiser :

où p est le nombre de points nodaux uj sur l'axe de la variable u ; aj - coefficients de pondération dont les valeurs sont plus grandes, plus l'écart y(X, φj) - yTT(X, φj) doit être obtenu au j-ème point.

Les critères Maximin (minimax) permettent d'atteindre l'un des objectifs de la conception optimale : la meilleure satisfaction des conditions de performance.

Introduisons une évaluation quantitative du degré de réalisation de la j-ième condition de performance, notons-la par zj et appelons-la la réserve de performance du paramètre yj. Le calcul de la marge pour le jième paramètre de sortie peut être effectué de différentes manières, par exemple :

où aj est le coefficient de pondération ; yjnom - valeur nominale du j-ième paramètre de sortie ; dj est une valeur caractérisant l'étalement du jème paramètre de sortie.

Ici, on suppose que toutes les relations sont réduites à la forme yi< TТj. Если yi >TTj, alors -yj< -TТj . Следует принимать аj >1 (valeurs recommandées 5 ? aj ? 20), s'il est souhaitable d'atteindre le j-ème les pré-requis techniques avec une tolérance donnée, soit yj = TTj ± ?yj ; aj=l, s'il faut obtenir l'estimation maximale possible zj.

Qualité des performances système technique caractérisé par un vecteur de paramètres de sortie et donc un vecteur Z=(zm,zm,…,zm). Par conséquent, la fonction cible doit être formée comme une fonction µ(Z) du vecteur d’évaluation. Par exemple, si la fonction cible considère la réserve uniquement pour le paramètre de sortie qui, à un point donné X, est le pire du point de vue de la satisfaction des exigences des spécifications techniques, alors

où m est le nombre de réserves de capacité de travail.

Il est naturel maintenant de se poser le problème du choix d'une stratégie de recherche X qui maximiserait le minimum des réserves, c'est-à-dire

où HD est la zone de recherche.

Le critère d’optimisation avec fonction objectif (2.6) est appelé critère maximin.

Critères statistiques. L'optimisation par critères statistiques vise à obtenir la probabilité maximale P de performance. Cette probabilité est prise comme fonction objectif. Ensuite, nous avons le problème

Normalisation des paramètres contrôlés et de sortie. L'espace des paramètres contrôlés est métrique. Par conséquent, lors du choix des directions et des valeurs des étapes de recherche, il est nécessaire d'introduire l'une ou l'autre norme, identifiée par la distance entre deux points. Ce dernier suppose que tous les paramètres contrôlés ont la même dimension ou sont sans dimension.

Possible différentes manières rationnement. A titre d'exemple, considérons la méthode de normalisation logarithmique, dont l'avantage est le passage des incréments absolus de paramètres aux incréments relatifs. Dans ce cas je-et contrôlé le paramètre ui est converti en xi sans dimension comme suit :

où oi est le coefficient, numériquement égal à un paramètre ui.

La normalisation des paramètres de sortie peut être effectuée à l'aide de coefficients de pondération, comme dans le critère additif, ou en passant de уj aux réserves de performance zj selon (2.5).

Programmation linéaire.

Bref informations théoriques

Fixer des objectifs

La résolution d'un problème de programmation linéaire directe répond à la question suivante :

à quelles intensités n processus lucratifs (fournissant diverses prestations, processus de production), dans lequel ils sont utilisés m types de ressources (facteurs de production) avec une intensité maximale connue d'utilisation de ces ressources, le chiffre d'affaires (bénéfice) sera maximum dans le cas où l'intensité de consommation de chaque ressource et l'intensité du profit (revenu) dans chacun des processus dépendent linéairement de l’intensité de ce processus.

La solution à son double problème répond à la question suivante :

à quoi prix les plus bas par unité de ressource, il ne sera pas rentable pour un agent économique d'étendre davantage le processus de profit par l'acquisition de nouveaux volumes de ressources rares dans les conditions actuelles de l'activité économique.

Un problème de programmation linéaire directe peut être lié à la situation suivante. Disponible n moyens de réaliser un profit (en fournissant n types de services) avec des volumes x je (nombre de pièces je services rendus). Dans ce cas, ils sont utilisés m types de ressources, stock j -ième dont est égal à bj . Dans le même temps, la consommation de chaque ressource j et le montant du profit dans chacun des processus je dépendent linéairement du nombre de services fournis je -ième type avec coefficients un ji Et c je , respectivement. Matrice UN=(un ji )m'n la signification est similaire à celle de la première partie et est également appelée matrice des coefficients technologiques ou structurels. Ensuite, le plan optimal selon le critère du profit maximum peut être obtenu en résolvant le problème de programmation linéaire directe suivant :

Ce problème peut être associé à une matrice étendue de la forme suivante :

(4.1)

Le problème dual du problème (4) a la forme suivante ( zj – prix limites requis) :

Avec cette formulation du double problème, (5.1) et (5.3) découlent de la condition de minimisation des prix, et de la condition de non-rentabilité de la poursuite de l'activité, la condition d'excédent ou d'égalité des coûts sur le chiffre d'affaires surgit directement.

Concepts de base du modèle

Décision (plan, programme) - ensemble, vecteur de valeurs spécifiques de tous paramètres variables contrôle du modèle - ces quantités qui peuvent être modifiées à la volonté du gestionnaire de l'objet de modélisation. Les solutions peuvent être acceptables (mises en pratique), inacceptables (non réalisables en raison des limitations existant dans le modèle) et optimales (la meilleure des solutions acceptables).

Fonction objectif L(x) – une expression mathématique reliant les facteurs (paramètres) du modèle. La signification économique de la fonction objectif reflète critère d'optimalité– un indicateur qui a un contenu économique et sert de formalisation d'un objectif de gestion spécifique, par exemple : maximiser le profit (ligne 1 en (4)), maximiser la qualité du produit ou minimiser les coûts (5.1).

Système de restrictions modèles - limites qui limitent plage acceptable(acceptable, réalisable) solutions, enregistrant les principales propriétés internes et externes de l'objet associées à l'objectif d'optimisation. Équations de communication(taper fj(x) ) – formalisation mathématique du système de restrictions (lignes 2 et 3 de (4), (5.2, 5.3)). Le système de restrictions reflète la signification économique des équations de communication.

Un système composé d'une fonction objectif et d'équations de communication - problème de modélisation économique et mathématique (EMM). Dans le cas où la fonction objectif et les équations de couplage sont linéaires et les variables de contrôle changent continuellement, le problème EMM est appelé problème de programmation linéaire (LP). La propriété principale de l’ensemble des plans admissibles (SAP) du problème LP est qu’il s’agit d’un polyèdre convexe. Un ensemble est dit convexe s’il contient tous les segments reliant deux points quelconques de cet ensemble. Si le problème LP a une solution, alors elle est située au sommet du MDP. Les plans situés aux sommets du MDP sont dits basiques. Les problèmes de programmation linéaire sont divisés en problèmes avec contraintes sous forme d'inégalités (problème LP général) et sous forme d'égalités (problème LP canonique). Lors de la formalisation mathématique de problèmes économiques à l'aide d'un modèle linéaire, des problèmes généraux LP sont obtenus - par exemple (4), (5). Tout problème général peut être associé à un problème canonique en introduisant des variables supplémentaires. Ainsi, au problème (4) en introduisant dans chaque inégalité du type « consommation de ressources £ réserve de ressources » (ligne 2 dans (4)) une variable supplémentaire xn+j (solde non dépensé j ème ressource), la canonique suivante est comparée :

Dans le même temps, la dimension du problème (6) - le nombre de variables de conception - par rapport à (4) a augmenté avec n avant n+m .

Lors de la résolution du problème (4), les coefficients d'efficacité des ressources sont importants, parmi lesquels les coefficients différentiels et incrémentaux seront utilisés ici. Coefficient différentiel d’efficacité des ressources k ji montre le coût du rendu lors de l'utilisation d'une unité j la ressource je -s services. Ces types de services pour lesquels tout k ji s'avèrent être les plus petits pour tous les types de services et les moins rentables. Ils ne devraient pas être présents dans le plan optimal. Cela permet, en réduisant à zéro le volume de fourniture de tels services, de réduire l'ampleur du problème et, ainsi, de simplifier sa solution. Ils sont calculés comme suit - k ji =c je /a ji .

coefficient d'efficacité incrémental des ressources K j est le coefficient de proportionnalité entre l'incrément de la valeur de la fonction objectif du plan optimal et la variation de stock qui a provoqué cet incrément j -ème ressource. On peut considérer que À j montrer de combien la valeur de la fonction objectif du problème d'origine dans le plan optimal augmentera avec une augmentation de la marge j -ème ressource par unité. D'un point de vue mathématique, c'est la dérivée complète de la valeur optimale de la fonction objectif en termes de valeur de marge j -ième ressource : À j =dL opt/dbj .