Exemples de théorème de Kuhn Tucker. Formulation et preuve du théorème de Kuhn-Tucker. b) Problème extrême conditionnel

Par segment appelez une partie d'une ligne droite composée de tous les points de cette ligne situés entre ces deux points - ils sont appelés les extrémités du segment.

Regardons le premier exemple. Supposons qu'un certain segment soit défini par deux points dans le plan de coordonnées. DANS dans ce cas on peut trouver sa longueur en appliquant le théorème de Pythagore.

Ainsi, dans le système de coordonnées, nous dessinons un segment avec les coordonnées données de ses extrémités(x1 ; y1) Et (x2; y2) . Sur l'axe X Et Oui Tracez des perpendiculaires à partir des extrémités du segment. Marquons en rouge les segments qui sont des projections du segment d'origine sur l'axe des coordonnées. Après cela, nous transférons les segments de projection parallèlement aux extrémités des segments. On obtient un triangle (rectangulaire). L'hypoténuse de ce triangle sera le segment AB lui-même, et ses jambes sont les projections transférées.

Calculons la longueur de ces projections. Donc sur l'axe Oui la longueur de projection est y2-y1 , et sur l'axe X la longueur de projection est x2-x1 . Appliquons le théorème de Pythagore : |AB|² = (y2 - y1)² + (x2 - x1)² . Dans ce cas |AB| est la longueur du segment.

Si vous utilisez ce diagramme pour calculer la longueur d’un segment, vous n’avez même pas besoin de construire un segment. Calculons maintenant la longueur du segment avec les coordonnées (1;3) Et (2;5) . En appliquant le théorème de Pythagore, on obtient : |AB|² = (2 - 1)² + (5 - 3)² = 1 + 4 = 5 . Cela signifie que la longueur de notre segment est égale à 5:1/2 .

Considérons la prochaine façon trouver la longueur d'un segment. Pour ce faire, nous devons connaître les coordonnées de deux points dans un système. Considérons cette possibilité, en utilisant un système de coordonnées cartésiennes bidimensionnelles.

Ainsi, dans un système de coordonnées bidimensionnel, les coordonnées des points extrêmes du segment sont données. Si nous traçons des lignes droites passant par ces points, elles doivent être perpendiculaires à l'axe des coordonnées, nous obtenons alors un triangle rectangle. Le segment d'origine sera l'hypoténuse du triangle résultant. Les jambes d'un triangle forment des segments, leur longueur est égale à la projection de l'hypoténuse sur les axes de coordonnées. Sur la base du théorème de Pythagore, nous concluons : pour trouver la longueur d'un segment donné, il faut trouver les longueurs des projections sur deux axes de coordonnées.

Trouvons les longueurs de projection (X et Y) le segment d'origine sur les axes de coordonnées. Nous les calculons en trouvant la différence entre les coordonnées des points le long d'un axe distinct : X = X2-X1, Y = Y2-Y1 .

Calculer la longueur du segment UN , pour cela on trouve la racine carrée :

A = √(X²+Y²) = √ ((X2-X1)²+(Y2-Y1)²) .

Si notre segment est situé entre des points dont les coordonnées 2;4 Et 4;1 , alors sa longueur est égale à √((4-2)²+(1-4)²) = √13 ≈ 3,61 .

Dans la section précédente, les conditions de Kuhn ont été construites-Tucker pour les tâches optimisation conditionnelle. En utilisant la méthode du multiplicateur de Lagrange, une idée intuitive a été obtenue selon laquelle les conditions de Kuhn-Tanker sont étroitement liées aux conditions d'optimalité nécessaires. DANS cette rubrique Des formulations rigoureuses de conditions nécessaires et suffisantes pour l'optimalité de la résolution d'un problème de programmation non linéaire sont considérées.

Théorème 1. Nécessité des conditions de Kuhn-Tucker

Considérons le problème de programmation non linéaire (0) - (2). Soit des fonctions différentiables, et x* une solution admissible à ce problème. Disons-le. De plus, qu’ils soient linéairement indépendants. Si x* - solution optimale problème de programmation non linéaire, alors il existe une paire de vecteurs qui est une solution au problème de Kuhn-Tucker (3) - (7).

La condition selon laquelle ils doivent être linéairement indépendants est connue sous le nom de condition indépendance linéaire et représente essentiellement une certaine condition de régularité de la région admissible, qui est presque toujours satisfaite pour les problèmes d'optimisation rencontrés en pratique. Cependant, en général, vérifier que la condition d’indépendance linéaire est remplie est très difficile, car il faut connaître à l’avance la solution optimale du problème. Dans le même temps, la condition d’indépendance linéaire est toujours satisfaite pour les problèmes de programmation non linéaire qui ont les propriétés suivantes.

• 1. Toutes les restrictions sous forme d'égalités et d'inégalités contiennent des fonctions linéaires.
• 2. Toutes les contraintes d'inégalité contiennent des fonctions concaves, toutes les contraintes d'égalité contiennent des fonctions linéaires, et il y a aussi, selon au moins, un point réalisable x, qui est situé à l'intérieur de la région définie par les contraintes d'inégalité. Autrement dit, il existe un point x tel que

Si la condition d’indépendance linéaire au point optimal n’est pas satisfaite, alors le problème de Kuhn-Tucker n’a peut-être pas de solution.

Minimiser

sous restrictions

Sur la fig. 1 montre la région des solutions réalisables formulées ci-dessus problème non linéaire. Il est clair qu’il existe une solution optimale à ce problème. Montrons que la condition d'indépendance linéaire n'est pas satisfaite au point optimal.

Riz.

Il est facile de voir que les vecteurs sont linéairement dépendants, c'est-à-dire la condition d’indépendance linéaire au point n’est pas satisfaite.

Écrivons les conditions de Kuhn-Tucker et vérifions si elles sont satisfaites au point (1, 0). Les conditions (3), (6) et (7) prennent la forme suivante :

Il résulte de l'équation (11) que, alors que l'équation (14) donne, le point optimal n'est donc pas un point de Kuhn-Tucker.

Notez que la violation de la condition d’indépendance linéaire ne signifie pas nécessairement que le point de Kuhn-Tucker n’existe pas. Pour le confirmer, remplaçons la fonction objectif de cet exemple par la fonction. Dans ce cas, l’optimum est toujours atteint au point (1,0), auquel la condition d’indépendance linéaire n’est pas satisfaite. Les conditions de Kuhn-Tucker (12) - (16) restent inchangées et l'équation (11) prend la forme

Il est facile de vérifier que le point est un point de Kuhn-Tucker, c'est-à-dire satisfait aux conditions de Kuhn-Tucker.

Le théorème sur la nécessité des conditions de Kuhn-Tucker permet d'identifier les points non optimaux. En d’autres termes, le théorème 1 peut être utilisé pour prouver qu’un point réalisable donné qui satisfait à la condition d’indépendance linéaire n’est pas optimal s’il ne satisfait pas aux conditions de Kuhn-Tucker. D’un autre côté, si les conditions de Kuhn-Tucker sont satisfaites à ce stade, il n’y a aucune garantie que la solution optimale au problème non linéaire ait été trouvée. À titre d'exemple, considérons le problème de programmation non linéaire suivant.

Le théorème suivant établit les conditions dans lesquelles le point de Kuhn-Tucker correspond automatiquement à la solution optimale à un problème de programmation non linéaire.

Théorème 2. Suffisance des conditions de Kuhn-Tucker

Considérons le problème de programmation non linéaire (0) - (2). Laisser fonction objectif convexes, toutes les contraintes d’inégalité contiennent des fonctions concaves et les contraintes d’égalité contiennent des fonctions linéaires. Alors s'il existe une solution qui satisfait aux conditions de Kuhn-Tucker (3) - (7), alors x* est la solution optimale au problème de programmation non linéaire.

Si les conditions du théorème 2 sont remplies, alors trouver le point de Kuhn-Tucker fournit une solution optimale au problème de programmation non linéaire.

Le théorème 2 peut également être utilisé pour prouver l'optimalité cette décision problèmes de programmation non linéaire. Pour illustrer, considérons à nouveau l’exemple :

Minimiser

sous restrictions

En utilisant le théorème 2, nous prouvons que la solution est optimale. Nous avons

Puisque la matrice est semi-définie positive pour tout x, la fonction s'avère convexe. La première contrainte d'inégalité contient fonction linéaire, qui est à la fois convexe et concave. Pour ça

pour montrer que la fonction est concave, on calcule

Parce que la matrice est définie négative, la fonction est concave. La fonction est incluse dans la contrainte linéaire de l'équation d'égalité. Par conséquent, toutes les conditions du théorème 2 sont satisfaites ; si nous montrons que c'est le point de Kuhn-Tucker, nous établirons effectivement l'optimalité de la solution. Les conditions de Kuhn-Tucker par exemple 2 ont la forme

Le point satisfait aux contraintes (24) - (26) et est donc admissible. Les équations (22) et (23) prennent la forme suivante :

En le mettant, nous obtenons et. Ainsi, la solution x*=(1, 5) satisfait aux conditions de Kuhn-Tucker. Puisque les conditions du théorème 2 sont satisfaites, alors la solution optimale au problème de l'exemple 3. Notez qu'il existe également d'autres valeurs de et qui satisfont au système (22) - (29).

Remarques

• 1. Pour les problèmes rencontrés en pratique, la condition d’indépendance linéaire est généralement satisfaite. Si toutes les fonctions du problème sont différentiables, alors le point de Kuhn-Tucker doit être considéré comme point possible optimum. Ainsi, de nombreuses méthodes de programmation non linéaire convergent vers le point de Kuhn-Tucker. (Il convient ici de faire une analogie avec le cas optimisation inconditionnelle, lorsque les algorithmes correspondants permettent de déterminer un point stationnaire.)
• 2. Si les conditions du théorème 2 sont remplies, le point de Kuhn-Tucker s'avère en même temps être un point minimum global. Malheureusement, il est très difficile de vérifier des conditions suffisantes et, en outre, problèmes appliqués n’ont souvent pas les propriétés requises. Il est à noter que la présence d'au moins une contrainte non linéaire sous forme d'égalité conduit à une violation des hypothèses du théorème 2.
• 3. Les conditions suffisantes établies par le Théorème 2 peuvent être généralisées au cas de problèmes de fonctions non convexes incluses dans des contraintes sous forme d'inégalités, de fonctions objectives non convexes et de contraintes d'égalité non linéaires. Dans ce cas, des généralisations de fonctions convexes telles que les fonctions quasi-convexes et pseudo-convexes sont utilisées.

Le théorème de Kuhn-Tucker est une généralisation des méthodes de solution problèmes d'optimisation dans deux directions :

Programmation linéaire pour le cas non linéaire, qui a été obtenu par analogie pas très réputation« programmation non linéaire » ;

Contraintes d'égalité non linéaires sur les contraintes d'inégalité.

Méthode et conditions Karush-Kuhn-Tucker ( Conditions de Karush-Kuhn-Tucker, KKT) sont des conditions formellement nécessaires à l’optimalité d’un problème de programmation non linéaire. En plus, conditions nécessaires inclure les conditions dites de régularité pour les points stationnaires - non-dégénérescence de l'ensemble des gradients de contraintes. La méthode est une généralisation de la méthode du multiplicateur de Lagrange au cas des contraintes d'inégalité.

Kuhn et Tucker ont généralisé la méthode du multiplicateur de Lagrange (à utiliser dans la construction de critères d'optimalité pour les problèmes avec contraintes d'égalité) au cas d'un problème de programmation non linéaire général avec des contraintes d'égalité et d'inégalités.

La méthode principale en programmation non linéaire reste l'utilisation de la fonction de Lagrange obtenue en transférant des restrictions à la fonction objectif. Les conditions de Kuhn-Tucker dérivent également de ce principe.

William Karush, dans son travail de diplôme en 1931, a trouvé les conditions nécessaires dans cas général restrictions des égalités et des inégalités. Indépendamment, Harold Kuhn et Albert Tucker parvinrent aux mêmes conclusions plus tard en 1941. Leurs résultats étaient plus généraux.

Si, sous les restrictions imposées, il existe une solution au problème, alors il existe un vecteur de multiplicateurs de Lagrange tel que pour la fonction de Lagrange les conditions sont remplies :

- stationnarité: ;

- douceur complémentaire: ;

- non-négativité:.

Les conditions nécessaires énumérées pour le minimum d'une fonction ne sont pas suffisantes dans le cas général. Il existe plusieurs options conditions supplémentaires, ce qui les rend suffisants :

- état simple – 1) le point est stationnaire, 2) la condition de non-rigidité complémentaire est satisfaite, 3) les multiplicateurs de Lagrange ;

- L'état de Slater (plus faible) – 1) le point est stationnaire, 2) la condition de non-rigidité complémentaire est satisfaite, 3) .

Passons directement à la preuve du théorème de Kuhn-Tucker.

Si fonction continue n variables x = (x1,...,xn) F(x) a au point X opt maximum, alors il existe ε > 0 tel que pour tout x du ε-voisinage du point X de gros

F(x)≤F(x opt)

F(x)-F(x opt)≤0.

Choisissons deux types d'incrément xj le long de j les coordonnées

Δx j =x j -x jopt >0,

Δx j =x j -x jopt<0.

Passant dans ces relations à la limite en Δ xj→0, on obtient :

De ces relations il résulte que

(3.6.1)

Une relation similaire peut être obtenue pour le cas d'une fonction minimale. Ainsi, la nécessité de conditions (3.6.1) à réaliser au point x vente en gros fonction maximum ou minimum f(x), c’est-à-dire s’il y a un extremum, alors les conditions (3.6.1) sont satisfaites. Mais l'égalité à zéro de toutes les dérivées au point x vente en gros ne garantit pas encore l'existence d'un extremum, c'est-à-dire que les conditions (3.6.1) ne sont pas suffisantes. Géométriquement, cela signifie que dans le cas d'une dérivée nulle d'une fonction d'une variable, il peut y avoir un point d'inflexion plutôt qu'un maximum (ou un minimum), et dans le cas d'une fonction de deux variables - point de selle, pas un extremum, etc. Par conséquent, les points x vente en gros, dans lesquels les relations (3.6.1) sont satisfaites sont dites stationnaires.

A noter que la condition (3.6.1) a été obtenue grâce à la possibilité d'attribuer une variable X incréments de deux signes, où sont les deux inégalités à et à . Si zone valide valeurs X limité aux valeurs non négatives X≥0, puis à l'intérieur de la région où X> 0, la condition (3.6.1) reste valable, puisque les incréments des deux signes y sont autorisés. A la frontière de la région X≥ 0, où X= 0, seul l'incrément positif Δ est autorisé X>0, on ne peut parler que d’une dérivée unilatérale, et de (3.6.1) découle la condition nécessaire suivante pour un maximum :

Dès lors, la condition nécessaire pour qu’il y ait un minimum à la limite de la région xj= 0 s'écrira comme

b) Problème sur conditionnel extrême

Lors de la détermination de l'extremum conditionnel d'une fonction, lorsqu'il est nécessaire de déterminer le maximum (ou le minimum) de la fonction F(x) dans des conditions limites :

g je (x) = b je , je = 1, ..., m,

f(x)=max;

g je (x)=b je ;

On utilise également la méthode des multiplicateurs de Lagrange qui, comme dans le cas du calcul classique des variations, consiste à introduire la fonction de Lagrange

(3.6.2)

où λ je - facteurs indéfinis Lagrange.

En supposant que la fonction est un cas particulier de la fonctionnelle, on obtient que les conditions nécessaires à l'extremum se trouvent par différenciation directe de la relation (3.6.2) et s'écrivent sous la forme

Si on introduit des vecteurs

les relations (17-8) et (17-9) seront réécrites comme

grade Φ = grade F - λ grade φ = 0 ; (3.6.6)

où l'égalité des vecteurs à zéro s'entend par composants.

Figure 3.6.1 - Explication du problème de l'extremum conditionnel

Au cas où n= 2 et m = 1 problème géométrique la recherche d'un extremum conditionnel revient (Fig. 17-6) à trouver le point de tangence A de la courbe φ = bà l'une des courbes de niveau constant f= const.

La place centrale dans la théorie de la programmation non linéaire est occupée par le théorème de Kuhn-Tucker. Soit un problème de programmation non linéaire :

trouver valeur maximale fonctions Z=f(x1, x2, ..., xn) avec restrictions

Composons la fonction de Lagrange pour ce problème :

(4.2)

Si la condition de régularité est satisfaite (il y a au moins un point X, pour lequel g je(X)>0 pour tout le monde je), alors le théorème suivant est valable.

Théorème. Vecteur X(0) si et seulement si est une solution optimale au problème (4.1) lorsqu’il existe un vecteur Λ (0) tel que lorsque pour tout le monde

Indiquer ( X (0),Λ (0)) est appelé selle point de fonction F(X,Λ), et le théorème s'appelle le théorème du point selle. Montrons la suffisance des conditions (4.3).

Preuve. Laisser X(0) >0 et Λ (0) >0 - point selle de la fonction F(X,Λ). Si en (4.3) à la place F(X,Λ) en substituant sa valeur (4.2), on obtient

à .

La bonne inégalité est valable pour tout, donc

Alors de l’inégalité de gauche on obtient

Puisque dans ce cas

Que f(X (0))>f(X).

Donc le point X (0) satisfait (4.1) et à tous les autres points satisfaisant (4.1), la fonction prend une valeur inférieure à X (0).

Cette affirmation conduit la solution du problème NLP à trouver les points selles de la fonction de Lagrange F(X,Λ).

La preuve de la nécessité des conditions (4.3) n’est pas considérée en raison de sa complexité.

Si f(X) Et g je(X)-différentiables, alors les conditions (4.3) sont équivalentes aux conditions locales de Kuhn-Tucker suivantes :

Expression

signifie que la valeur de la dérivée partielle de la fonction de Lagrange est prise au point ( X (0), Λ (0)), où

X (0)=(x1 (0) , x2 (0) , ..., xn(0)), Λ (0) =(λ 1 (0) , λ 2 (0) , ..., λ n (0)).

Ces conditions peuvent être écrites forme vectorielle:

Exemple. Trouver le maximum Z=-x 1 2 -x 2 2 avec restrictions

Montrons qu'il existe Λ (0) 0 pour lequel les conditions de Kuhn-Tucker (4.4), (4.5) pour la fonction sont satisfaites au point optimal F(X,Λ):

F(X,Λ)=- x 1 2 -x 2 2 +λ 1 (2 x 1 +x 2 -2)+λ 2 (8-2 x 1 -x 2)+λ 3 (6- x 1 -x 2).

D'après les conditions (4.5), λ 2 et λ 3 doivent prendre des valeurs nulles, car en substituant x 1 =0,8 et x 2 =0,4 dans l'expression

on a des valeurs supérieures à zéro, et par condition

D’après la condition, λ 1 peut prendre une valeur non nulle, puisque

Conformément à (2.16), la dérivée

doit prendre des valeurs nulles, puisque les coordonnées du vecteur X (0) sont différents de zéro. On trouve λ 1 =0,8. Par conséquent, au point ( X (0),Λ (0)) les conditions de Kuhn-Tucker sont satisfaites et c'est bien un point extremum.

Considérons les conditions de Kuhn-Tucker sous une forme légèrement différente.

Disons un problème d'optimisation avec des contraintes sous forme d'égalités :

z= f(x 1 , x 2 , …, xn) → minutes

sous conditions :

g 1 ( x 1 , x 2 , ... , xn) = 0,

g 2 ( x 1 , x 2 , ... , xn) = 0,

g n(x 1 , x 2 , . . . , xn) = 0.

Point minimum conditionnel de la fonction f coïncide avec le point selle de la fonction de Lagrange :

Dans ce cas, le point selle doit fournir un minimum dans ses variables x je et maximum sur les variables λ j.

Les conditions nécessaires pour un point stationnaire sont que les dérivées partielles du premier ordre par rapport à toutes les variables soient égales à zéro :

Notez que la deuxième équation implique que seuls les points valides satisferont aux conditions nécessaires.

Pour obtenir une condition suffisante pour l'existence d'un minimum, il faut ajouter l'exigence que le Hessien de la fonction objectif soit défini positif.

Considérons général tâche programmation mathématique:

Z= f(X) → minutes,

sous conditions :

Les contraintes d'inégalité peuvent être converties en contraintes d'égalité en ajoutant à chacune d'elles affaiblissement variables

Formons la fonction de Lagrange :

Les conditions minimales nécessaires prennent alors la forme :

La deuxième équation peut être transformée en supprimant les variables atténuantes et en passant aux contraintes d'inégalité. Obtenons les contraintes du problème initial. La troisième équation peut être multipliée par interface utilisateur/2 et remplacez les variables d'affaiblissement en les exprimant à partir de la deuxième équation du système.

Il y a une autre condition qui doit être remplie au point minimum. Cette condition : λ je= 0, ce qui est une conséquence de l'analyse signification physique coefficients de la fonction de Lagrange.

On peut montrer que

Coefficient de Lagrange au point minimum ;

f* - valeur optimale fonctions.

Évidemment, lorsque b augmente je la région autorisée s'agrandit, ce qui signifie que la valeur minimale ne peut que diminuer, c'est-à-dire que la dérivée doit être négative (non positive). Par conséquent, au point minimum conditionnel

On obtient finalement les conditions nécessaires au conditionnel minimum:

Les expressions de la deuxième ligne garantissent que le point optimal est valide.

La troisième ligne contient l'information suivante : si la contrainte est active (c'est-à-dire que l'expression entre parenthèses est égale à zéro), alors le coefficient de Lagrange correspondant est strictement positif. La positivité du coefficient de Lagrange signifie que la contrainte correspondante est active, c'est-à-dire le fait que cette limitation soit rare est précisément ce qui empêche amélioration supplémentaire fonction cible. Si la contrainte n'est pas active (c'est-à-dire que l'expression entre parenthèses n'est pas égale à zéro), alors le coefficient de Lagrange correspondant doit être égal à zéro, c'est-à-dire Cette limitation n'est pas déficiente ; elle n'affecte pas l'amélioration ultérieure de la fonction cible.

Pour le point maximum conditionnel, les coefficients de Lagrange changent de signe opposé (puisque la valeur optimale de la fonction objectif au point maximum conditionnel devrait augmenter).

Les conditions ci-dessus sont équivalentes Théorème de Kuhn-Tucker et sont souvent appelés de la même manière.

Une condition suffisante pour un minimum (maximum) est la convexité (concavité) de la fonction objectif en un point stationnaire. Cela signifie que le Hessian doit être défini positif (négatif).

Un résumé du matériel de ce chapitre peut être consulté dans deux présentations :

fichier « Programmation non linéaire » ;

fichier "Théorème de Kuhn-Tucker".

Les diapositives 10 à 14 de la présentation « Théorème de Kuhn-Tucker » montrent un exemple de résolution du problème de Kuhn-Tucker.

4.5. Questions de sécurité

(Développé par Afanasyev M.Yu. et Suvorov B.P.)

Question 1. Dana fonction réelle f(X S= . Laisser X 1 et X 2 - points de ce segment et 0 £ l £ 1.

Laquelle des inégalités suivantes est une condition de convexité d’une fonction ?

Réponses possibles :

Question 2.Étant donné une fonction réelle f(x), défini sur le segment nombres réels S=. Laisser x 1 et x 2 sont les points de ce segment et 0 £ l £ 1.

Laquelle des inégalités suivantes est une condition pour qu’une fonction soit strictement concavité ?

Réponses possibles :

Question 3. Fonction

1) convexe ;

2) strictement convexe ;

3) concave ;

4) strictement concave ;

5) convexe et concave.

Question 4. Fonction

3) concave ; 4) strictement concave ;

5) convexe et concave.

Question 5. Fonction

1) convexe ; 2) ni convexe ni concave ;

3) strictement convexe ; 4) concave :

5) convexe et concave.

Question 6. Nouveau modèle la moto à grande vitesse « Escargot » est vendue par l'entreprise au prix de (30 – 2 x) mille dollars par pièce, où X- nombre de motos vendues. Les coûts de fabrication variables sont de 6 000 $ par unité et les coûts fixes sont de 30 000 $. Maximisez les bénéfices de votre entreprise pour la semaine.

Disons que le changement du taux de taxe de vente a entraîné une taxe de vente supplémentaire de 4 000 $ pour chaque moto vendue.

Comment la production optimale de motos va-t-elle évoluer par rapport à la situation initiale ?

(Résolvez à l'aide de la fonction Lagrange.)

Réponses possibles :

1) augmentera de 2 ; 2) diminuera de 2 ;

3) ne changera pas ; 4) augmentera de 1 ;

5) diminuera de 1 .

Question 7. Supposons que vous ayez 2 semaines (14 jours) de vacances à passer aux îles Canaries et à Nice. Laissez votre fonction utilitaire être de la forme 2 KN – 3K2 – 4N 2, Où À Et N- le nombre de jours que vous passez respectivement aux îles Canaries et à Nice.

Combien de jours faut-il passer à Nice pour maximiser sa fonction d’utilité ?

(Pour résoudre, utilisez la fonction de Lagrange. Arrondissez le résultat à l'entier le plus proche. Vérifiez si les conditions d'optimalité de Kuhn-Tucker sont remplies.)

Réponses possibles :

1) 3 ; 2) 4 ; 3) 5 ; 4) 6 ; 5) 7 .

Question 8. Pour le problème de la question 7, trouvez la valeur de la double estimation de la contrainte.

(Arrondissez le résultat à l'entier le plus proche.)

Réponses possibles :

1) 41 ; 2) 34; 3) 29 ; 4) 39 ; 5) 44 .

Question 9. Le monopoleur planifie un programme de production et de vente pour la période suivante. Tarifs : r 1 = 14 – 0,25x 1 (par produit 1); r 2 = 14 – 0,5X 2 (par produit 2), où x 1 et X 2 - volumes de ventes de produits. Supposons que tous les produits fabriqués soient vendus. Le volume total maximum des ventes est de 57.

Quelle est la version optimale du produit 2 ?

Réponses possibles :

1) 36,4 ; 2) 30,7 ; 3) 26,3 ; 4) 20,6 ; 5) 41,8 .

Question 10. Le propriétaire d'une petite entreprise dispose de 100 000 roubles pour le mois prochain, qu'il peut dépenser pour augmenter les immobilisations À(achat d'équipement) au prix de 1 000 roubles par unité ou pour l'achat de main d'œuvre supplémentaire L au prix de 50 roubles/heure. Augmentation des produits finis pouvant être vendus pour 10 000 roubles. par unité, déterminé par la fonction de production F(K, L)= L 2/7 K 2/5.

Combien d’argent faut-il consacrer à l’augmentation des immobilisations ?

Réponses possibles :

1) 74,36 mille frotter.; 2) 58,33 mille roubles; 3) 63,44 mille roubles;

4) 45,66 mille roubles; 5) 39,77 mille roubles

Réponses aux questions :

1 -4,2 - 1,3 -4,4 - 5,

5 -2, 6 -5,7- 4,8- 2,9- 4,10- 2.

Théorème 7.2. Pour un problème de programmation convexe (7.4)–(7.6), dont l’ensemble des solutions admissibles possède la propriété de régularité, le plan est plan optimal si et seulement s'il existe un vecteur tel que
– point selle de la fonction de Lagrange.

En supposant que la fonction objectif
et fonctions sont continus et différentiables, alors le théorème de Kuhn-Tucker peut être complété par des expressions analytiques qui déterminent la condition nécessaire et suffisante pour le point
était le point de selle de la fonction de Lagrange, c'est-à-dire était une solution au problème de programmation convexe. Ces expressions ont la forme suivante :

Où Et sont les valeurs des dérivées partielles correspondantes de la fonction de Lagrange calculées au point selle.

Le théorème de Kuhn-Tucker occupe une place centrale dans la théorie de la programmation non linéaire. Cela est également valable pour les problèmes de programmation dits quadratiques, c'est-à-dire où est la fonction objectif
avec restrictions :

.

Dans le cas général de la résolution de problèmes de programmation non linéaire pour déterminer l’extremum global du problème, il n’existe pas de méthode de calcul efficace si l’on ne sait pas extrême local est également mondial en même temps. Ainsi, dans un problème de programmation convexe et quadratique, l’ensemble des solutions réalisables est convexe, donc si la fonction objectif est concave, tout maximum local est également global.

Exemple 7.3. En utilisant le théorème de Kuhn-Tucker, nous trouvons
sous restrictions

Nous résolvons graphiquement (Fig. 7.2) et trouvons :
;
;
(voir la solution ci-dessous pour plus de détails). Montrons qu'il existe un vecteur Oui 0 0, auquel les conditions de Kuhn-Tucker sont satisfaites au point optimal. Composons la fonction de Lagrange :

Solution
on trouve du système :
. De la deuxième équation
remplacer dans la première équation du système. Se différencier par :
. Dans les expressions Et remplacer les valeurs
Et
. On a des valeurs de dérivées partielles supérieures à zéro, et selon la condition elles doivent être égales à zéro, alors =0 Et =0. De l'autre côté, peut prendre des valeurs non nulles, car
d'ici
; Tous
ceux. les conditions de Kuhn-Tucker sont satisfaites, ce point est donc un point extrême.

Figure 7.2. Solution graphique au problème non linéaire

exemple de programmation 7.3

Condition nécessaire à l’optimalité pour un problème de programmation non linéaire peut être formulé comme suit. Laisser
est la solution optimale au problème (7.4)–(7.6), et les fonctions
,
,
différenciable à ce stade. Si
est un point non singulier de l’ensemble admissible du problème (7.4) – (7.6), alors c’est un point de Kuhn-Tucker de ce problème.

Ainsi, si un ensemble admissible
le problème (7.4)-(7.6) n’a pas de points singuliers, et les fonctions F(M),g je (M), (
) différenciable en tous points
, alors la solution optimale à ce problème doit être recherchée parmi les points de Kuhn-Tucker.

Comme le montre l’analyse mathématique, point spécial ensembles de solutions admissibles à un système d'équations linéaires et d'inégalités de la forme

c'est-à-dire des ensembles de solutions réalisables

si au point
les gradients de ces fonctions dépendent linéairement
, qui se transforme en . Par exemple,
– point singulier de l’ensemble

Vraiment,

Il s’agit donc d’un système linéairement dépendant.

Fonction dégradé
est un vecteur dont les coordonnées sont respectivement égales aux valeurs des dérivées partielles de la fonction
au point M. 0 . Ce vecteur montre la direction de croissance la plus rapide de la fonction.

La condition d’optimalité nécessaire est peu utile pour résoudre la plupart des problèmes de programmation non linéaire, car Ce n'est que dans de rares cas qu'il est possible de trouver tous les points de Kuhn-Tucker d'un problème de programmation non linéaire.

Condition suffisante pour l'optimalité pour un problème de programmation non linéaire : si
est le point selle de la fonction de Lagrange pour le problème (7.4)–(7.6), alors
est la solution optimale à ce problème.

Cette condition n'est pas nécessaire dans le cas général : la fonction de Lagrange peut ne pas avoir de points selle, alors qu'en même temps le problème de programmation non linéaire original a une solution optimale.

On connaît diverses méthodes permettant de trouver approximativement la solution optimale à un problème de programmation non linéaire. Cependant, ces méthodes fournissent une assez bonne approximation uniquement pour le problème de programmation convexe, où chaque extremum local est également global. En général, sous pente les méthodes comprennent les méthodes dans lesquelles le mouvement vers le point optimal d'une fonction coïncide avec la direction du gradient de cette fonction, c'est-à-dire à partir d'un certain point
une transition séquentielle est effectuée vers d'autres points jusqu'à ce qu'une solution acceptable au problème d'origine soit identifiée. Dans ce cas, les méthodes de gradient peuvent être divisées en 2 groupes.

À d'abord Ce groupe comprend des méthodes dans lesquelles les points étudiés ne dépassent pas l'éventail des solutions réalisables au problème. La plus courante de ces méthodes est la méthode Frank-Loup (Loup). De telles méthodes incluent la méthode dégradés de Rosen projetés, méthode directions valides de Zeutendijk.

Co. deuxième Ce groupe comprend des méthodes dans lesquelles les points étudiés peuvent ou non appartenir à la région des solutions réalisables. Cependant, suite à la mise en œuvre du processus itératif, un point dans la région des solutions réalisables est trouvé, ce qui détermine une solution acceptable.

Parmi ces méthodes, la méthode la plus couramment utilisée est fonctions de pénalité ou méthode Flèche-Hurwitz.

Lors de la recherche de solutions à des problèmes utilisant des méthodes de gradient, y compris celles mentionnées ci-dessus, le processus itératif est effectué jusqu'à ce que ce moment, tandis que le gradient de la fonction
au point suivant
ne le fera pas égal à zéro ou pour l'instant
, Où – un nombre positif assez petit caractérisant la précision de la solution résultante.

La résolution de problèmes de programmation non linéaire complexes à l’aide de méthodes de gradient implique une grande quantité de calculs et n’est conseillée qu’à l’aide d’un ordinateur.

À l'aide d'un exemple, nous montrerons la signification générale des méthodes de gradient pour résoudre des problèmes de programmation non linéaire.

Soit une fonction de deux variables
. Soit les valeurs initiales des variables
, et la valeur de la fonction
. Si
n'est pas un extremum, alors ces nouvelles valeurs des variables sont déterminées
Et
, à valeur suivante fonctions
s'est avéré plus proche de l'optimum que le précédent.

Comment est déterminée la taille des incréments ? Et ? Pour ce faire, aux points Et La direction de changement de fonction vers l'extremum est déterminée à l'aide du gradient. Plus la valeur de la dérivée partielle est grande, plus la fonction évolue rapidement vers l'extremum. Donc les incréments Et sont choisis proportionnellement à la valeur des dérivées partielles Et aux points
Et
. Ainsi,
Et
, Où – une valeur appelée step, qui définit l’échelle du changement Et .

Exemple 7.4.

Qu'il soit nécessaire de maximiser la fonction

(maximum au point (3;2))

.

Au point
,
à
nous avons

;
,

Faisons encore une itération. Au point
,
à
nous avons

;
,

Figure 7.3. Interprétation géométrique de deux étapes

méthode du gradient par exemple 7.4

Sur la fig. 7.3 montre le mouvement le long de la pente, qui a été effectué en dans cet exemple. Attitude indique le sens de changement de la fonction vers le maximum. Si on prend le dégradé avec un signe moins, alors on se dirigera vers le minimum.

Un problème spécifique avec les méthodes de gradient est le choix de la taille du pas t. Si nous faisons de petits pas, nous chercherons l’optimum pendant très longtemps. Si vous choisissez une valeur trop grande, alors l'optimum peut être « dépassé ». Le problème intermédiaire du choix de la taille de pas optimale est résolu à l’aide de méthodes appropriées. Si l'étape t est déterminé approximativement, alors, en règle générale, ils ne tombent pas dans l'optimum, mais dans sa zone. Les méthodes de gradient permettent de déterminer les optima locaux. Lors de la recherche d'un optimal global à l'aide d'un gradient, on doute souvent que l'optimum trouvé soit global. C'est l'inconvénient de cette méthode lors de la résolution de problèmes de programmation non convexes.

Questions d'auto-test

Énoncé du problème de programmation non linéaire.

Processus consistant à trouver une solution à un problème de programmation non linéaire en utilisant son interprétation géométrique.

Algorithme de la méthode Lagrange pour résoudre un problème de programmation non linéaire.

Application de la méthode de Lagrange à la résolution d'un problème de programmation non linéaire dans le cas où les conditions de connexion sont des inégalités.

Définitions auxiliaires et théorèmes nécessaires à l'examen théorème central programmation non linéaire – Théorème de Kuhn-Tucker.

Théorème de Kuhn-Tucker.

Condition d'optimalité nécessaire et suffisante pour un problème de programmation non linéaire.

La signification générale des méthodes de gradient pour la solution approximative de problèmes de programmation non linéaire.

Groupes de méthodes de gradient pour la solution approximative de problèmes de programmation non linéaire.