Donnons-nous un système d'inégalités de la forme

(4.3) et fonction

Z = f (x 1 , x 2 , …, x n), (4.4)

de plus, toutes les fonctions sont convexes sur un ensemble convexe M, et la fonction Z est soit convexe sur l'ensemble M, soit concave.

Le problème de la programmation convexe est de trouver une solution au système de contraintes (4.3) dans lequel la fonction objectif Z atteint une valeur minimale, ou la fonction concave Z atteint une valeur maximale. (Les conditions de non-négativité des variables peuvent être considérées comme incluses dans le système (4.3)).

En raison de la propriété 3 0, tout problème de programmation linéaire est un cas particulier de problème de programmation convexe. En général, les problèmes de programmation convexe sont des problèmes de programmation non linéaire. La séparation des problèmes de programmation convexe en une classe spéciale s'explique par les propriétés extrémales des fonctions convexes : tout minimum local d'une fonction convexe (maximum local d'une fonction concave) est également global ; de plus, compte tenu de la propriété 2 0, une fonction convexe (concave) définie sur un ensemble fermé borné atteint un maximum global et un minimum global sur cet ensemble. Il en résulte que si la fonction objectif Z est strictement convexe (strictement concave) et si le domaine de solution du système de contraintes n'est pas vide et limité, alors le problème de programmation convexe a toujours une solution unique.

La fonction F(X) = F(x 1, x 2, …, x n) est appelée séparable, s'il peut être représenté comme une somme de fonctions dont chacune dépend d'une seule variable, c'est-à-dire Si

(il est possible que F i (x i) = 0 pour certains i).

Supposons que le problème de programmation convexe soit donné par un système de contraintes (4.3) et une fonction objectif (4.4), et la fonction objectif Z et toutes les contraintes sont séparables. Le problème ressemble alors à :

Trouver le minimum d'une fonction convexe (maximum d'une concave)

sous restrictions

L'idée de la méthode d'approximation linéaire par morceaux est que tous les fi et all sont remplacés par des lignes brisées constituées de segments droits. Dans ce cas, le problème de programmation convexe original est remplacé par un nouveau problème approximatif, qui est un problème de programmation linéaire. Ce problème est généralement résolu à l'aide de la méthode du simplexe et sa solution est une solution approximative du problème de programmation convexe original.

Figure 12. Résolution du problème de programmation convexe à l'aide de la méthode d'approximation linéaire par morceaux

Pour construire un problème approximatif, considérons une approximation linéaire par morceaux d'une fonction d'une variable h(x) définie sur l'intervalle. Divisons ce segment en r parties par points x 0

L'équation de la section de la ligne brisée entre les points (x k ; h k) et (x k+1 ; h k+1) a la forme (équation d'une droite basée sur deux points). Si l’on note chacune des relations dans cette égalité par :

Notez que pour chacun il existe une valeur unique qui satisfait aux conditions (4.7). Ceci fait, nous pouvons réécrire (4.7) sous la forme :

[Les équations (4.8) sont appelées équations paramétriques du segment.

Si h(x) = 0, alors la seconde de ces équations devient l'identité 0 = 0, et la première prend la forme (4.1) - l'équation du segment situé sur l'axe des x].

Ainsi, pour tout, l’équation de la ligne brisée peut s’écrire :

De plus, seules deux valeurs sont toujours différentes de zéro (si x est le point intérieur du k-ième segment de la partition) ou d'une (si x coïncide avec la fin du segment).

Revenant au problème de la programmation convexe avec fonctions séparables, notons qu'il faut tout d'abord (selon le système de restrictions) déterminer l'intervalle de changement de chaque variable x j. Ensuite, chacun de cet intervalle est divisé en parties par des points x jk et à l'aide des formules (4.9), une approximation linéaire par morceaux est construite pour les fonctions f j et. Après cela, nous pouvons écrire un problème approximatif pour le problème original (4.6) :

Trouver le maximum d'une fonction

sous restrictions (4.10)

Étant donné que le problème approximatif (4.10) est un problème de programmation linéaire, qui est généralement résolu à l'aide de la méthode du simplexe, les conditions de non-négativité des variables sont écrites séparément des autres restrictions.

La différence entre le problème résultant (4.10) et le problème de programmation linéaire habituel est que pour chaque x j il n'y a pas plus de deux uns voisins non nuls et, par conséquent, il est impossible d'en prendre deux avec le même j et k non voisin comme variables principales. Notez également que pour les conditions de non-négativité des termes variables f j (x j) et (s'il y en a) une approximation linéaire par morceaux, bien entendu, n'est pas nécessaire.

Ce chapitre n'a examiné que certaines des méthodes d'optimisation utilisées par les dirigeants pour prendre des décisions efficaces dans les entreprises. Cependant, les techniques décrites permettent de comprendre le principe de base de l'utilisation d'appareils mathématiques en économie, qui permet de choisir parmi de nombreuses options alternatives celle optimale pour un cas ou une situation spécifique donné.

PROGRAMMATION CONVEXE, une section de programmation mathématique qui étudie le problème de la maximisation de la fonction objectif concave f(x) de l'argument vectoriel x = (x 1, ..., x n), satisfaisant les contraintes g i (x) ≥ 0, x Є X, i = 1, ..., m, où g i sont des fonctions concaves, X est un ensemble convexe. Un point x qui satisfait à ces restrictions est dit admissible. Le résultat principal de la théorie de la programmation convexe est le théorème du point selle : pour que le point admissible x* d'un problème de programmation convexe soit optimal, il faut (sous des conditions assez larges) et suffisant l'existence du vecteur y * = (y* 1, ..., y m *) avec des composantes non négatives y* telles que le point (x*, y*) est un point selle pour la fonction de Lagrange

problèmes de programmation convexes, c'est-à-dire que pour tout x Є X et y avec des composantes non négatives, les inégalités sont satisfaites

Un certain nombre de méthodes de programmation convexes s'appuient sur le théorème du point selle, dans lequel la fonction φ(y 1 , ..., y m) = max x Є X L(x, y) est minimisée pour y i ≥ 0, i = 1, . . ., m, ou le point selle est directement trouvé, et à la place de la fonction de Lagrange, certaines de ses modifications sont parfois utilisées. Une autre approche pour résoudre le problème de programmation convexe est associée à la recherche de directions de mouvement possibles d'un point admissible x, qui ne dérivent pas de l'ensemble des points admissibles et lors du déplacement le long desquelles la fonction objectif augmente. Cette approche est mise en œuvre à travers une séquence d’itérations. A chaque itération, la direction possible émanant du point suivant est calculée, après quoi un décalage est effectué dans cette direction d'une certaine distance jusqu'au point suivant. Il existe des méthodes de résolution de problèmes de programmation convexe spécialement adaptées au cas où la fonction objectif est non linéaire et les contraintes sont linéaires. Généralement, les méthodes de programmation convexe nécessitent un nombre infini d’itérations pour déterminer avec précision le point optimal. Les exceptions sont les problèmes de programmation quadratique (la fonction objectif est la somme d'une fonction quadratique et linéaire concave, les contraintes sont linéaires) et de programmation linéaire (la fonction objectif et les contraintes sont linéaires), pour lesquelles des méthodes finies sont principalement utilisées. De nombreuses méthodes de programmation informatique convexe sont implémentées sous forme de programmes informatiques ; Il existe également des progiciels couvrant les problèmes de programmation linéaire et de programmation convexe. Voir également Recherche opérationnelle.

Lit. : Golshtein E. G. Programmation convexe. Éléments de théorie. M., 1970 ; Zangwill U. I. Programmation non linéaire. Approche unifiée. M., 1973.

L'examen de cette classe de problèmes commence généralement par une déclaration Méthode de Lagrange des multiplicateurs indéterminés. Pour ce faire, supposons que/(x b..., X") et g(x b ..., X")- les fonctions continues ainsi que leurs dérivées partielles, supprimons pour l'instant les conditions de non-négativité des variables et formulons le problème suivant pour un extremum conditionnel :

Pour trouver sa solution, nous introduisons Multiplicateurs de Lagrange / = 1, T et créer ce qu'on appelle Fonction de Lagrange:

trouvons et égalisons à zéro ses dérivées partielles par rapport à toutes les variables

avoir reçu le système p + téquations pour les inconnues x b xp,

Ui-,Up-

Si la fonction f(x h ..., X")à ce point a un extremum, alors il existe un tel vecteur Y (0> = (y, 0 ,..., y°) que le point (A r(0) , F (0)) est une solution du système (2.23). Par conséquent, en résolvant le système (2.23), nous obtenons des points auxquels la fonction (2.20) peut avoir un extremum. Ensuite, les points trouvés sont examinés de la même manière que lors de la résolution du problème d'un extremum inconditionnel.

Ainsi, la méthode du multiplicateur de Lagrange consiste à effectuer les étapes suivantes.

• 1. Composez la fonction de Lagrange.
• 2. Trouver les dérivées partielles par rapport à Xj Et oui,à partir de la fonction de Lagrange et assimilez-les à zéro.
• 3. Système de résolution (2.23), trouver les points auxquels la fonction objectif peut avoir un extremum.
• 4. Parmi les points candidats à l'extremum, trouvez ceux auxquels l'extremum est atteint et calculez les valeurs de la fonction f(x, ..., X")à ces points.

La méthode présentée est applicable aux problèmes de programmation convexe, c'est-à-dire à ceux dans lesquels la fonction objectif est convexe (ou concave) et la région des solutions réalisables, déterminée par les contraintes, est également convexe.

Définition 1. Fonction f(x,..., xn), défini sur un ensemble convexe X, est appelé convexe si pour n'importe quel point X, X2 depuis Hé pour n'importe quel numéro X, 0 X 1 l'inégalité est vraie

Définition 2. Fonction/(*, X„), défini sur un ensemble convexe X, est appelé concave si pour n'importe quel point X X, X2 depuis Hé pour n'importe quel numéro X, 0X

Définition 3. L'ensemble des solutions réalisables à un problème de programmation convexe satisfait la condition de régularité s'il y a au moins un point Xj, appartenant à la région des solutions réalisables pour lesquelles g^XJ) =b h je = 1, T.

Théorème 1. Tout extremum local d’un problème de programmation convexe est global.

Définition 4. La fonction de Lagrange d'un problème de programmation convexe est la fonction

où y est le multiplicateur de Lagrange.

Définition 5. Point (X(0) , T(0)) = (x,°,..., X (',oui, 0 ,..., ouais" ) appelé point selle de la fonction de Lagrange, Si

Présentons deux courts théorèmes de nature auxiliaire.

Théorème 2. Forfait optimal X (0) Tâches NP- Ce

où DA) est une fonction différentiable non linéaire qui satisfait aux conditions

où est le gradient de la fonction /

au point A" (0) .

Preuve.

Développons la fonction objectif en une série de Taylor au voisinage du point X (())

Où OH- vecteur de petits incréments X (0) ;

I - désignation de la norme (longueur) du vecteur.

De l'expression (2.26), il s'ensuit que si une valeur de la coordonnée vectorielle x| 0) > 0, alors la dérivée sera nécessairement égale à zéro

, car sinon le long de la coordonnée xk Peut,

avec des valeurs fixes des variables restantes, continuez à minimiser la fonction objectif, en diminuant la valeur de x[ 0) si la dérivée est supérieure à zéro, ou en augmentant xf si la dérivée est inférieure

zéro. Si x| 0) = 0, alors ça devrait être parce que le

sinon vous pourriez réduire la valeur f(Xm), augmentant 4 0) du montant Dx*, sans changer les valeurs des autres variables. Par conséquent, pour tout À l'égalité est valable :

Le théorème a été prouvé.

Déterminons maintenant les conditions nécessaires et suffisantes à l'existence d'un point selle de la fonction de Lagrange.

Théorème 3. Pour que le point (A 10 *, I 0)) de coordonnées non négatives soit un point selle de la fonction différentiable L(X,Y), les conditions suivantes doivent être remplies :

Preuve.

1) Nécessité. Soit (X (0), Y" (0)) un point selle, c'est-à-dire :

La formule (2.29) est équivalente à l'expression

D’après (2.29) et (2.30), les conditions (2.27) et (2.28) sont satisfaites. La nécessité est donc avérée.

• 2) Adéquation. Supposons que les conditions (2.27) et (2.28) soient satisfaites. Développons la fonction L(X, Oui) dans une série de Taylor au voisinage d'un point

Du développement (2.31) et compte tenu des conditions (2.27) et (2.28) il résulte que

Les deux dernières expressions sont équivalentes à la formule (2.29). Le théorème a été prouvé.

Après les théorèmes ci-dessus, nous formulons le théorème de Kuhn-Tucker, désormais pratiquement évident.

Théorème 4 (Kuhn - Tucker). Pour le problème de programmation convexe (2.20) - (2.21), dont l'ensemble des solutions admissibles a la propriété de régularité, le point X (0) =(xj 0 *,..., x’ 0)), x,- 0> >0, / = 1, P. est un plan optimal si et seulement s'il existe un tel vecteur T = (y 1 (0),..., yi 0)), V/ 0) > 0, / = 1, T, que le point (T(0),H 0>) est un point selle de la fonction de Lagrange.

Si dans le problème de programmation convexe (2.20) - (2.21) la fonction objectif et les contraintes sont continûment différentiables, alors le théorème de Kuhn-Tucker peut être complété par des expressions analytiques qui déterminent les conditions nécessaires et suffisantes pour le point (X (0), Y i(l), ) était le point selle de la fonction de Lagrange, c'est-à-dire était une solution au problème de programmation convexe. Ce sont les expressions (2.27) et (2.28). Ils se contentent du problème de programmation quadratique. Pour sa formulation finale, nous présentons plusieurs définitions et un théorème.

Définition 6. Forme quadratique par rapport aux variables X[, ..., X" est appelée une fonction numérique de ces variables, ayant la forme :

Définition 7. Forme quadratique F est appelé défini positif/négatif si F(X) > 0/F(X) 0 pour toutes les valeurs des variables qui composent le vecteur X.

Définition 8. Forme quadratique F est appelé semi-défini positif/négatif si F(X") > O / OUI") X, et, en plus, il existe un tel ensemble de variables - une composante du vecteur X", Quoi F(X") = 0.

Théorème 5. Une forme quadratique est une fonction convexe/concave si elle est semi-définie positive/négative.

Définition 9. La tâche de minimiser/maximiser la valeur d'une fonction

sous restrictions

où est une forme quadratique semi-définie positive/négative, appelée problème de programmation quadratique(ZKP).

Pour ce problème, la fonction de Lagrange a la forme :

Si la fonction de Lagrange a un point selle, alors les conditions (2.27), (2.28) sont satisfaites. En introduisant maintenant des variables supplémentaires qui transforment les inégalités en égalités (cette technique est également utilisée lors de la résolution de problèmes LP), nous écrivons ces conditions sous la forme :

Pour trouver une solution au ZKP, il est nécessaire de déterminer une solution non négative du système d’équations algébriques linéaires (2.32). Une telle solution peut être trouvée méthode de base artificielle, appliqué pour trouver la valeur minimale de la fonction objectif artificielle F = ^Pj, où sont des variables artificielles. Méthode, comment-

On sait qu’en un nombre fini d’étapes, il trouvera le plan optimal ou établira l’insolvabilité du problème.

Ainsi, le processus de recherche d’une solution à la demande de prix comprend les étapes suivantes.

• 1. Composez la fonction de Lagrange.
• 2. Sous forme d'expressions (2.27), (2.28) nous écrivons les conditions nécessaires et suffisantes pour l'existence d'un point selle de la fonction de Lagrange.
• 3. A l'aide de la méthode des bases artificielles, l'absence de point selle pour la fonction de Lagrange est établie ou ses coordonnées sont trouvées.
• 4. Notez la solution optimale au problème d'origine et trouvez la valeur de la fonction objectif.

Considérons l'élémentaire exemple numérique(No. 1) du livre de I. L. Akulich « Programmation mathématique dans les exemples et les problèmes ». Selon le plan de production, l'entreprise doit fabriquer 180 produits. Ils peuvent être fabriqués selon deux technologies. En production X des produits utilisant la 1ère méthode, les coûts étaient xf+4x, frotter., et pendant la production x2 produits de la 2ème manière, ils sont égaux x + 8x 2 frotter. Déterminez combien de produits doivent être fabriqués en utilisant chaque méthode pour minimiser le coût de la commande.

Solution. La fonction suivante doit être minimisée :

sous conditions:

La fonction de Lagrange dans ce cas ressemblera à ceci :

Calculons les dérivées partielles de cette fonction par rapport à X, x 2, y et mettez-les égaux à zéro :

Report dans les première et deuxième équations à du côté droit et en assimilant les côtés gauches, on obtient après des abréviations évidentes :

En résolvant cette équation avec la troisième équation du système, nous trouvons que Ce point est candidat à l’extrême.

En utilisant les dérivées partielles secondes, il est facile de montrer que le point trouvé est le minimum conditionnel de la fonction /

Des problèmes similaires à celui considéré sont mis en avant de diverses manières par la pratique économique. Certes, les problèmes réels contiennent généralement un grand nombre de variables et de restrictions, ce qui rend impossible leur résolution sans l'utilisation d'un ordinateur. Cependant, l’efficacité de l’utilisation d’un logiciel standardisé est déterminée par la connaissance du chercheur de l’essence des transformations effectuées par l’ordinateur. Cela l'aide à naviguer correctement dans la variété de méthodes, de procédures de calcul et de progiciels proposés pour résoudre les problèmes d'optimisation.

Pour consolider le sujet, considérons-en un de plus exemple numérique(N°2). Trouver la valeur maximale d'une fonction

sous conditions:

Solution. La fonction / est concave car c'est la somme d'une fonction linéaire f = 2х 2 + 4х ъ qui peut être considérée comme concave et de forme quadratique / 2 = -x -2x1, ce qui est défini négatif. Les contraintes contiennent uniquement des contraintes linéaires. Par conséquent, nous pouvons utiliser le théorème de Kuhn-Tucker et le schéma de solution ZKP.

1. Composons la fonction de Lagrange :

2. Écrivons les conditions nécessaires et suffisantes pour l'existence d'un point selle de la fonction L.

3. Introduisons des variables supplémentaires non négatives v b V2 dans le système d'inégalités linéaires, w, w2, transformer les inégalités en égalités. On obtient un système d'équations :

Dans ce cas, bien entendu, les conditions suivantes sont remplies :

Il est nécessaire de trouver une solution fondamentale au système d’équations (2.33) pour déterminer les coordonnées du point selle de la fonction de Lagrange. Pour cela, nous utiliserons la méthode des bases artificielles. Minimiser une fonction objective artificielle

Où Zi, Zi- variables artificielles, dans les conditions suivantes :

Ici, la solution de base évidente et réalisable ressemble à ceci :

Fonction cible F Exprimons-le en termes de variables non fondamentales :

En conclusion de notre raisonnement, nous notons qu'il tend vers zéro lorsque Xj (0) = 1, = 1 et que les autres variables ont des valeurs nulles. Ainsi, T (0) = (1, 1) est le plan optimal pour le problème initial,

(Document)

Projet de cours - Styles de programmation. Partie pratique - jeu de 100 matchs (Cours)

Travail de laboratoire n°4. Recherche multidimensionnelle. Programmation non linéaire. Méthodes de minimisation sans contrainte (Lab)

Veselov S.L. Programmation des PBX Samsung et Panasonic (Document)

Présentation - Programmation linéaire (Résumé)

Tikhomirova L.S. Méthodes de minimisation des fonctions booléennes (Document)

Kirsanova O.V., Semionova G.A. Programmation mathématique (calcul standard) (Document)

Kozyrev D.V. 1C : Entreprise 7.7 Configuration et programmation. Composant comptable. Cours à distance (Document)

Travail de laboratoire n°1. Optimisation unidimensionnelle inconditionnelle (laboratoire)

Moshchevikine A.P. Présentations des conférences "Théorie de la prise de décision" (Document)

n1.doc

1. 
   Programmation convexe. Théorème de Kuhn-Tucker. Conditions Kuhn-Tucker

Dans la théorie de la programmation convexe, le problème principal est la minimisation d'une fonction convexe.

Sous conditions

(1.3)

Où sont les fonctions
sont supposés convexes.

Si
et sont des fonctions concaves, alors nous avons un problème de maximisation
sous restrictions
Et

Composons la fonction de Lagrange pour ce problème :

Un point est appelé point selle de la fonction (1.4) si le point est le point minimum de la fonction
, et le point est le point maximum de la fonction. En d’autres termes, pour un point de selle pour tous
Et la relation est vraie

(1.5)

Théorème 1 (théorème de Kuhn-Tucker). Qu'il y ait au moins un point
, Pour qui
. Alors une condition nécessaire et suffisante pour l’optimalité du vecteur
, appartenant au domaine des solutions réalisables au problème (1.1)-(1.5), est l’existence d’un tel vecteur
c'est pour tout le monde et
les inégalités (1,5) sont vraies

Acceptons ce théorème sans preuve.

Le théorème de Kuhn-Tucker est également appelé théorème du point de selle.

Si
Et
sont des fonctions différentiables, alors les inégalités dans (1.5) sont équivalentes aux conditions locales de Kuhn-Tucker suivantes :

Ces expressions signifient que les valeurs des dérivées sont prises au point
.

1.2. Programmation quadratique. Méthode Barankin-Dorfman.

Un cas particulier de problème de programmation convexe est un problème de programmation quadratique. Le principal problème de la programmation quadratique est la minimisation de la fonction Z, qui est la somme d'une fonction linéaire et d'une fonction quadratique :

Sous contraintes linéaires

La matrice D est supposée symétrique et définie non négative. Dans ce cas, la fonction (2.1) sera convexe.

Pour le problème (2.1) - (2.3), composons des conditions locales de Kuhn-Tucker (1.6) - (1.7), qui sont des conditions nécessaires et suffisantes pour l'optimalité de la solution du problème (2.1) - (2.3).

La fonction de Lagrange dans ce cas a la forme :

Trouvons les dérivées partielles de cette fonction :

Notons

Compte tenu de ces notations et relations (2.4) et (2.5), les conditions de Kuhn-Tucker (1.6) – (1.7) prennent la forme suivante

Les égalités (2.6) et (2.7) forment un système de N=n+m équations linéaires à 2N=2(n+m) inconnues : .

Ainsi, conformément au théorème de Kuhn-Tucker, la solution
le problème (2.1) – (2.3) de programmation quadratique est optimal si et seulement si, avec la solution
il y a des solutions
Et
de telle sorte que c'est une solution du système (2.6) – (2.8) soumise à l'égalité (2.9).

La condition (2.9) pour le problème (2.1) – (2.3) équivaut à la réalisation de la condition

Il existe plusieurs méthodes pour résoudre un problème de programmation quadratique. Considérons l'une d'entre elles : la méthode Barankin-Dorfman.

Avec cette méthode, le système d’équations (2.6) – (2.7) est d’abord réduit à la forme :

Où (variables de base) et
(variables libres) sont différents éléments d'une certaine permutation de variables, et tous sont des nombres non négatifs (i=1,2,…,N).

Puis à partir du système (2.11) la solution de référence initiale est trouvée

Systèmes (2.6) – (2.8) et les composantes vectorielles disposés dans l'ordre.

Si pour solution la condition (2.10) est satisfaite, alors le problème (2.1) – (2.3) est résolu et sa solution optimale est
se trouve à partir des composantes correspondantes du vecteur .

Si la condition (2.10) n'est pas satisfaite, alors le tableau suivant est compilé pour passer à une autre solution de référence (tableau 2.1). La partie principale de ce tableau comprend des lignes pour toutes les variables, classées par ordre. Pour les variables de base, les éléments de ligne sont extraits du système (2.11) et pour les variables libres, des relations

Les paramètres de la partie complémentaire du tableau 2.1 sont les suivants :

UN) se trouvent à partir de la formule Où - un vecteur composé des éléments de la ième colonne de la partie principale du tableau ;

B) pour les s pour lesquels
, les paramètres restants sont calculés :

(éléments des colonnes correspondantes délivrant le minimum , marqué d'un astérisque),
.

La colonne qui correspond au plus petit négatif , est attribué comme colonne de résolution, la ligne avec l'élément marqué d'un astérisque dans cette colonne est une ligne de résolution, et cet élément lui-même est un élément de résolution, et avec leur aide une transformation simplexe du tableau 2.1 est effectuée.

Où:

En conséquence, une nouvelle solution de référence du système (2.6) – (2.8) est obtenue. Ce processus se poursuit jusqu'à ce que la condition (2.10) soit satisfaite. Si tout
, UN
, alors une autre solution est choisie comme solution initiale.

1.3 Un exemple de résolution d'un problème par la méthode Barankin-Dorfman
Fonction Réduire

Avec restrictions :

;
.

Solution

On retrouve la solution support initiale du système (2.12). Dans ce cas, la valeur de la fonction objectif est égale à .

Alors la condition (2.10) n’est pas satisfaite et, par conséquent, la solution n’est pas optimale.

Compilons le tableau 2.2 pour passer à une nouvelle solution de référence du système (2.12) - (2.13). Remplissons la partie principale de ce tableau en utilisant le système (2.12).

A) pour la partie supplémentaire du tableau on trouve :

B) pour positif Et Calculons les paramètres restants :

La quatrième colonne, qui correspond au plus petit négatif , nous attribuons une colonne de résolution, une ligne avec l'élément 3 de cette colonne comme ligne de résolution et l'élément 3 lui-même comme élément de résolution, et avec leur aide nous effectuons une transformation simplexe du tableau 2.2.

En conséquence, nous obtenons le tableau 2.3 contenant une nouvelle solution de référence.

Pour cette solution

Par conséquent, nous remplissons la partie supplémentaire du tableau 2.3 de la même manière que cela a été fait dans le cas précédent, pour passer à une nouvelle solution de référence du système (2.12) - (2.13).

En soumettant le tableau 2.3 à une transformation simplexe avec un élément de résolution de 13,30, on obtient un autre tableau avec une solution de référence pour laquelle
.

Ainsi, la solution optimale a été trouvée
, auquel la fonction objectif Z de ce problème est minimisée. Où

1.4 Tâche individuelle : résoudre le problème selon la méthode Barankin-Dorfman

;

Solution

A partir des relations (2.6) - (2.7) on obtient le système d'équations suivant :

Après des transformations simples, on amène ce système sous la forme :

(2.14)

D'où, en tenant compte de la non-négativité

Trouver la solution de base initiale
systèmes (2.14). Dans ce cas, la valeur de la fonction objectif est égale à
.

Puisque , alors la condition (2.10) n’est pas satisfaite et, par conséquent, la solution n’est pas optimale.

Compilons le tableau 2.4 pour passer à une nouvelle solution de base du système (2.14) - (2.15).
Tableau 2.4

, et , il faut alors refaire le choix de la solution de référence initiale.

	1	-	-	-
	0	-1	0	0
	0	0	-1	0
	4	1	-2	0
	0	0	0	-1
	2	4 *	-6	-2
	4	2	0	-1
	32
		12	-10	-4
		4
		1/2		Tableau 2.5	0	0	-1
	0	-1	0	0
	3	-1/2	3 *	0
	110,25
		-2,5	9	-2
			-3

Conférence 11.Programmation convexe

Définition 1. Z problème de programmation convexe est appelé un problème de programmation non linéaire où toutes les fonctions sont convexes.

Ainsi, le problème de programmation convexe est un problème de minimisation sous contrainte, où la fonction objectif est convexe et la région réalisable est un ensemble convexe formé par un système d’inégalités convexes. Par conséquent, les affirmations obtenues plus tôt dans la section 6 sont valables pour le problème de programmation convexe. Dans cette section, nous allons préciser ces résultats généraux et les mettre sous une forme plus pratique pour étudier et résoudre le problème de programmation convexe suivant :

(1)

, (2)

. (3)

Nous aurons besoin de constructions auxiliaires dans l'espace
vecteurs
. Vecteur du premier
composant ponctuel nous désignerons par . Donc,
.

Pour le problème (1) – (3) nous définissons l’ensemble

Où
.

Lemme . Pour le problème de programmation convexe (1) – (3) un tas de de manière convexe.

Preuve. Choisissons des vecteurs arbitraires
de beaucoup et numéro
. Ensuite, il y a des points Et depuis tel que . Multiplions ces inégalités par Et
, respectivement, et additionnez-les. En raison de la convexité de toutes les fonctions, on obtient

Des inégalités obtenues il résulte que l'ensemble est convexe .

Théorème 1. (Le théorème de Kuhn-Tucker sous la forme du point selle de la fonction de Lagrange d'un problème de programmation convexe ) Supposons que le problème de programmation convexe (1) – (3) du système (2) satisfasse la condition de Slater par rapport à était une solution au problème (1) – (3), il est nécessaire et suffisant qu'il y ait un vecteur non négatif tel que
– point selle de la fonction de Lagrange.

Preuve. Puisque la suffisance de cette condition a déjà été prouvée pour un problème de programmation arbitraire non linéaire (voir Théorème 2.6 en introduction), il ne reste plus qu'à prouver la nécessité.

Nécessité. Laisser – solution au problème (1) – (3). Mettons
. Il est évident que
, parce que
,
Et
.

Assurons-nous que
. Supposons le contraire. Cela signifie qu'il y a un point
tel que
. Ainsi, – un tel point admissible, dont la valeur de la fonction objectif est inférieure au minimum. Nous obtenons une contradiction avec le fait que – solution d'un problème de programmation convexe.

Donc,
. D’après le lemme, l’ensemble convexe. Par conséquent, toutes les exigences du théorème 8.2 sont satisfaites. Il existe donc un non nul

vecteur
référence au point trop :

Vérifions en outre que toutes les coordonnées du vecteur ne sont pas positifs. Supposons le contraire. Qu'il y ait une coordonnée
. Fixons le vecteur tous les composants sauf -Aie. Ensuite, étant donné que le produit
peut prendre des valeurs arbitrairement grandes (en raison du caractère illimité d'en haut de la coordonnée ), on obtient une contradiction avec l'inégalité (4).

Il est facile de voir que pour n'importe quel
vecteurs
inclus dans l'ensemble . Alors de (4) on a :

Montrons que
. Qu’il n’en soit pas ainsi. Alors
. Ainsi,
. D’après la condition de Slater, il existe un vecteur
tel que
. C'est pourquoi
. La contradiction qui en résulte signifie que
.

Notons
. Montrons que le vecteur construit représente le vecteur souhaité des multiplicateurs de Lagrange. Il est évident que
et de (5) on obtient

Par conséquent, à
devrait

. (7)

En revanche, puisque
(parce que le
) Et
, on obtient l'inégalité

. D’ici et de (7) il s’ensuit qu’au point
la condition de non-rigidité complémentaire est satisfaite :

. (8)

De (6) et (8) on a

ou, ce qui est pareil,

Ensuite, laissez
. Alors
. De là et de (8) on obtient l'inégalité

Les inégalités (9), (10) signifient que
est le point selle de la fonction de Lagrange du problème convexe.

logo de programmation. C'est ce qu'il fallait.

Avant de nous familiariser avec une autre version du théorème de Kuhn-Tucker, nous présentons le théorème suivant, qui est un critère minimum conditionnel en termes de cônes vectoriels supports.

Théorème 2. Laisser – convexe et différentiable sur
fonction, définir
convexe. Ensuite, pour faire valoir un point
était le minimum conditionnel de la fonction sur un plateau
, il est nécessaire et suffisant que l'inclusion ait lieu

. (11)

La preuve découle directement du théorème 6.5 et de la définition du cône
vecteurs de support en un point trop
.

Théorème 3. (Théorème de Kuhn-Tucker sous forme différentielle pour un problème de programmation convexe ) Soit un problème de programmation convexe sous la forme (1), (2), où toutes les fonctions
sont continuellement différentiables, le système (2) satisfait à la condition de Slater. Alors pour que le vecteur
était une solution au problème (1), (2), il est nécessaire et suffisant qu'il y ait un vecteur non négatif de telle sorte que les conditions soient remplies

, (12)

.

Preuve. Montrons que les conditions (12) et (13) sont équivalentes à l'inclusion (11). Laissons le point
est-ce
. Alors
Et
.

Laisse-le maintenant
. Ensuite, des théorèmes 2 et 10.5, il s'ensuit qu'une condition nécessaire et suffisante pour un extremum est l'existence de tels facteurs
,
, Pour qui
. Mettons
pour tous
et de la dernière égalité on obtient les conditions (12) et (13). C'est ce qu'il fallait.

Pour conclure cette section, nous présentons les formulations de deux théorèmes de Kuhn-Tucker pour le problème du calcul

programmation convexe avec contraintes linéaires.

Théorème 4. Supposons que dans le problème de programmation convexe (1) – (3) le système de contraintes (2) ait la forme

, b – vecteur dimensionnel
. Alors pour qu'un vecteur non négatif était une solution au problème, il est nécessaire et suffisant pour que

il y avait un vecteur non négatif tel que
est le point selle de la fonction de Lagrange de ce problème.

Notez que dans ce cas la fonction de Lagrange a la forme .

Théorème 5. Soit le problème de programmation convexe (1), (2) la fonction objectif est continûment différentiable, le système de restrictions (2) a la forme
, où A est la matrice des dimensions
, b – vecteur dimensionnel
. Alors pour que le vecteur
était une solution au problème, il est nécessaire et suffisant qu'il y ait un vecteur non négatif de telle sorte que les conditions soient remplies
,
.

Notez que les théorèmes 4 et 5 n'exigent pas la réalisation de la condition de Slater, ce ne sont donc pas des cas particuliers des théorèmes 1 et 3 et nécessitent une preuve indépendante.