Dans les modèles de tâches de gestion évoqués ci-dessus, le temps n'était pas pris en compte. Il s'agit de modèles dits en une étape qui vous permettent d'analyser des processus statiques et indépendants du temps, par exemple lorsque les changements dans le processus étudié au fil du temps peuvent être négligés. Une décision de gestion sur une telle modélisation est logique soit dans des conditions de stabilité du système, soit pour une courte période dans le futur.

En réalité, tous les processus et phénomènes économiques fonctionnent et se développent dans le temps, c’est-à-dire qu’ils sont de nature dynamique. Cela oblige les gestionnaires à résoudre des problèmes pratiques dans lesquels il est nécessaire de prendre en compte les changements possibles des processus économiques au fil du temps, à condition que le processus puisse être contrôlé, c'est-à-dire influencer le cours de son développement.

La programmation dynamique est un appareil mathématique à l'aide duquel des problèmes de contrôle optimal en plusieurs étapes sont résolus. Dans une telle programmation, pour contrôler un processus, parmi l'ensemble de toutes les solutions réalisables, on recherche la solution optimale au sens d'un certain critère, c'est-à-dire une solution qui donne une valeur extrême (plus ou moins) de la fonction objectif - quelques caractéristiques numériques du processus. Le multi-degré fait référence soit à la structure en plusieurs étapes d'un processus, soit à la répartition du contrôle en un certain nombre d'étapes successives, correspondant, en règle générale, à différents moments dans le temps. Ainsi, le mot « programmation » signifie prendre des décisions de gestion, et le mot « dynamique » indique l'importance essentielle du temps et de l'ordre des opérations dans les processus et méthodes considérés.

Les tâches de programmation dynamique comprennent des tâches de planification, de répartition des investissements, de gestion des stocks, de réparations en cours et majeures, de sélection de méthodes publicitaires, etc.

Dans certains problèmes de programmation dynamique, le processus de gestion se décompose de manière naturelle en étapes, par exemple un mois, un trimestre, une année. Dans d'autres situations, la division en étapes peut être conditionnelle. La particularité de tous les problèmes de programmation dynamique est qu'à chaque étape il est possible de prendre en compte les changements antérieurs, de contrôler le cours des événements, tout en évaluant la qualité d'un tel contrôle. Ainsi, la programmation dynamique permet de prendre un certain nombre de décisions de gestion et assure le développement optimal du système dans son ensemble.

Considérons la formulation générale du problème de cette programmation. Étudions un processus économique comportant n étapes successives. Toutes les 7 étapes, le processus peut se trouver dans différents états, chacun étant caractérisé par un ensemble fini de paramètres. Chaque étape de la tâche est associée à l'adoption d'une certaine décision de gestion, qui transfère le système d'un état à un autre. On suppose que l'état si du système à la fin de la 7ème étape est déterminé uniquement par l'état précédent si_1 et le contrôle xi à la 7ème étape et ne dépend pas des états et commandes précédents. Alors l’état si du système s’écrit sous forme de dépendance

Si = f (in, _!, Xi), i = 1, P.

L'efficacité de l'ensemble du processus de gestion peut être présentée comme la somme de l'efficacité des décisions de gestion à différentes étapes, c'est-à-dire

Dans les conditions ci-dessus, le problème de programmation dynamique se formule comme suit : déterminer une telle séquence admissible de décisions de gestion X = (x1, x2, xn), qui transfère le système de l'état initial 50 à l'état final sn et à laquelle une efficacité de gestion maximale est atteinte.

Lors de la planification d'un processus de gestion à plusieurs étapes, dans les problèmes de programmation dynamique, il est nécessaire à chaque étape de sélectionner une décision de gestion, en tenant compte de ses conséquences sur les étapes à venir. Ce n'est qu'à la dernière étape qu'une décision de gestion pourra être prise qui donnera le maximum d'effet, car l'étape suivante n'existe pas pour elle. Par conséquent, les problèmes de programmation dynamique sont résolus dès la fin.

Le maximum de la fonction objectif à la nième étape finale est égal à

^ n-O = vérifier / n ^ n-i xn).

En conséquence, au stade (n - 1) nous avons

r * n-1 (5n-2) = ShaX ((fn-1 (sn-2, xn-1) + r * n ^ n-1)).

En tenant compte de ce modèle, pour un k-stade arbitraire, nous pouvons écrire la dépendance récurrente

g * (cinquième-1) = Shahi (L (ik-1, xk) + g * + 1)).

Cette dépendance récurrente est une représentation mathématique du principe d'optimalité de Bellman.

Après avoir déterminé l'effet conditionnellement optimal des dépendances récurrentes au stade initial, ils effectuent une optimisation inconditionnelle du contrôle dans le sens « inverse », à la suite de quoi une séquence de décisions de gestion est trouvée qui garantit une efficacité maximale du système dans son ensemble. .

Principales caractéristiques de la méthode de programmation dynamique

1. L’idée et la méthode de programmation dynamique sont plus adaptées aux problèmes discrets, qui sont dans la plupart des cas des problèmes de contrôle.

2. La méthode de programmation dynamique peut être utilisée avec n'importe quelle méthode de spécification de la fonction objectif et avec n'importe quel ensemble d'états et de commandes admissible. Les méthodes d’optimisation classiques et autres méthodes informatiques de programmation mathématique ne disposent pas de cet avantage.

3. Schémas de calcul de la méthode de programmation dynamique dans le cas discret associé au tri des valeurs optimales de l'indicateur d'efficacité et de contrôle à la k-ème étape pour toutes les valeurs possibles de la variable d'état, mais le volume des calculs est nettement inférieur à celui du tri direct des options. Cela est dû au fait qu'au stade de l'optimisation conditionnelle, les options infructueuses sont immédiatement rejetées et seules celles qui sont conditionnellement optimales à ce stade sont conservées.

4. La méthode de programmation dynamique permet d'analyser la sensibilité aux changements des données initiales des états sk et de leur nombre n. En effet, ici à chaque étape non pas un problème est résolu, mais de nombreux problèmes similaires pour différents états sk et différents. k (1<к <п) . Поэтому с изменением исходных данных нельзя не решать задачу заново, а сделать только несложные добавление к уже выполненных расчетов, то есть продолжить уже решенную задачу за счет увеличения количества шагов п или количества значений sk.

Conclusions

1. L'émergence de modèles non linéaires est associée à la nécessité de prendre en compte et de démontrer des modèles non linéaires qui affectent la prise de décision optimale. De tels modèles sont inclus dans les contraintes du problème et la fonction objectif.

2. Selon la nature des fonctions et des contraintes qui décrivent les problèmes de programmation non linéaire, ils peuvent être classés comme suit : problèmes d'optimisation classiques ; problèmes avec la fonction objectif non linéaire et les contraintes linéaires ; problèmes de programmation convexe, quadratique, séparable.

3. Contrairement aux problèmes de programmation linéaire, il n’existe pas de méthode universelle pour résoudre les problèmes non linéaires. Dans chaque cas particulier, il faut choisir la meilleure méthode.

4. La programmation dynamique est un appareil mathématique à l'aide duquel des problèmes de contrôle optimal en plusieurs étapes sont résolus. Sous multi-degrés, on entend soit une structure en plusieurs étapes d'un processus, soit la répartition du contrôle en un certain nombre d'étapes successives, correspondant, en règle générale, à différents moments dans le temps.

5. Les tâches de programmation dynamique comprennent les tâches de planification, de répartition des investissements, de gestion des stocks, de réparations en cours et majeures, de sélection de méthodes publicitaires, etc. La particularité de tous les problèmes de programmation dynamique est qu'à chaque étape il est possible de prendre en compte les changements antérieurs et de contrôler le cours des événements, tout en évaluant la qualité d'un tel contrôle.

6. La solution des problèmes de programmation dynamique est basée sur le principe d'optimalité de Bellman. Dans le processus d'optimisation du contrôle de programmation dynamique, un processus en plusieurs étapes est effectué deux fois. La première fois, c'est de la fin au début, ce qui permet de trouver des contrôles conditionnellement optimaux. La seconde s'étend du début à la fin, permettant ainsi de trouver un contrôle optimal du processus dans son ensemble.

Programmation dynamique.

Lors de la modélisation des structures de réseau, outre les problèmes liés à l'existence de flux dans les réseaux de transport, électriques, téléphoniques, informatiques et autres, apparaît toute une classe de problèmes qui peuvent être réduits au problème du chemin le plus court. Par exemple, le problème du chemin le plus court est résolu à chaque fois par un programme de routeur lorsqu'un site est trouvé par son nom sur Internet.

Le problème du chemin le plus court dans un réseau dirigé est un problème de programmation dynamique typique. Par conséquent, bien que la programmation dynamique, ainsi que la planification du réseau, soient associées au développement de processus au fil du temps, dont la modélisation est discutée plus en détail dans la section suivante. , nous considérerons dans cette section la méthode de programmation dynamique sur exemple de recherche du chemin le plus court.

Le concept de programmation dynamique est étroitement lié à processus en plusieurs étapes prise de décision. Un processus décisionnel en plusieurs étapes peut être défini comme un processus de prise de décisions séquentielles visant à atteindre un objectif donné. Des processus décisionnels en plusieurs étapes sont constamment rencontrés dans diverses situations, de la réparation d'une voiture dans un atelier de réparation automobile au contrôle d'un vaisseau spatial.

La programmation dynamique peut être vaguement définie comme un ensemble de procédures mathématiques utilisées dans l'analyse de processus décisionnels en plusieurs étapes. Chaque processus de décision en plusieurs étapes est une évolution du problème suivant : trouver le chemin le plus court dans un réseau dirigé et acyclique.

La programmation dynamique peut être considérée comme une théorie unifiée en raison d'un ensemble unique d'idées et de techniques utilisées dans l'analyse mathématique de divers problèmes. Ces idées et techniques sont l'essence de la programmation dynamique. Bellman a été l'un des premiers à comprendre l'essence du principe d'optimalité et a commencé à l'appliquer à de nombreux problèmes d'optimisation découlant des mathématiques, de l'ingénierie, de la recherche opérationnelle et d'autres domaines.

Ainsi, le concept de programmation dynamique est associé à un processus décisionnel en plusieurs étapes pour atteindre un objectif spécifique. Par exemple, le transfert d'un avion d'une orbite à une autre est un problème typique de programmation dynamique, à condition que la correction d'orbite soit effectuée en appliquant une impulsion à des instants discrets et que le but soit d'économiser du carburant.

Caractérisant la programmation dynamique comme un ensemble de procédures mathématiques pour le contrôle optimal d'un système discret, en général, le problème de contrôle optimal peut être formulé comme suit. À des moments discrets dans le temps t= 1, 2,..., N le système est dans l'un des ensembles si d'états caractérisés par le vecteur d'état x (t) . La transition entre états successifs s'effectue à l'aide du vecteur de contrôle u (t) selon la loi :

x (t) = g (t) (x (t) , toi (t)) ; t= 1, 2,...,N

Les contrôles u (t) sont sélectionnés dans l'ensemble des contrôles admissibles et forment une séquence de contrôles admissibles u (0) ,u (1) ,…,u (N) . La séquence de contrôles admissibles pour un état initial donné x (0) détermine la trajectoire du système x (0), x (1), x (2),…, x (N).

Chaque trajectoire correspond à sa propre valeur du critère d'optimalité F, ou fonction de contrôle cible, qui est composée de contributions individuelles à chaque étape de contrôle :

Le problème du contrôle optimal est de trouver parmi un ensemble de séquences de contrôle celle qui atteint la valeur minimale de F. Une telle séquence est appelée séquence de contrôle optimale et détermine la trajectoire optimale.

La programmation dynamique est basée sur le principe d'optimalité de Bellman, qui peut être formulé comme suit. Une stratégie optimale a la propriété que quels que soient l’état initial et la décision du moment initial, les décisions ultérieures doivent formuler une stratégie optimale par rapport à l’état survenu après la décision initiale.

Le sens du principe d'optimalité devient plus clair si l'on considère que pour une trajectoire optimale, chaque tronçon entre le point final et tout point intermédiaire est également une trajectoire optimale. Le principe d'optimalité, ou autrement la méthode de programmation dynamique, vous permet de trouver la stratégie optimale en plusieurs étapes en résolvant un ensemble de problèmes d'optimisation en une étape plus simples.

La méthode de programmation dynamique est bien illustrée par l'exemple de la recherche du chemin le plus court entre les nœuds extrêmes d'un réseau orienté. Considérons un réseau dirigé avec 12 nœuds, qui doit être parcouru du nœud de départ (1) au nœud de fin (12) en quatre étapes, en se déplaçant de nœud en nœud à chaque étape.

Riz. 6.4.1. Traverser un réseau dirigé le long du chemin le plus court.

Les nombres indiqués aux arcs ( je,j) sont égales aux longueurs des arcs l ij entre les nœuds je Et j(en unités conventionnelles). Les états possibles du système s i dans ce cas sont associés au fait d'être dans je Au nœud, le contrôle u(t) est associé au choix de la direction du trajet à chaque étape de contrôle. Quatre étapes de contrôle u (1),...,u (4) transfèrent séquentiellement le système de l'état initial s 1 à l'état final s 12 et forment ainsi une certaine trajectoire qui doit être trouvée. Le critère d'optimalité F dans ce cas est la longueur de la trajectoire L, composé des longueurs d'arcs individuels :

Si la recherche du chemin le plus court, c'est-à-dire de la trajectoire optimale, ne commence pas depuis le début, mais depuis la fin du réseau et se déplace dans la direction opposée au début, alors nous avons dans ce cas un algorithme de « balayage arrière ». Dans ce cas, lors de la mise en œuvre de l'algorithme de balayage arrière, le déplacement s'effectue de l'état final s 12 à l'état initial s 1.

Au début de la recherche du chemin le plus court, une table de transition est constituée. Le nombre de lignes du tableau est égal au nombre d'étapes de contrôle, le nombre de colonnes est égal au nombre d'états moins un. Ce tableau stockera les étapes de contrôle et les valeurs correspondantes du critère d'optimalité L t pour tous les états possibles du système après chaque étape.

Tableau 6.4.1

il	s 1	s 2	art 3	art 4	art 5	S6	art 7	art 8	art 9	art. 10	art 11
									12	12 6
						10	11 10
			5
1

Les cellules remplies du tableau sont divisées en deux. Le contrôle u(t) est inscrit dans la partie supérieure de la cellule remplie, c'est-à-dire dans ce cas le numéro du nœud vers lequel s'effectue la transition. La valeur de la contribution Lt à la valeur totale du critère d'optimalité L, qui a été obtenue lors du passage du nœud correspondant à cette cellule au nœud final, est inscrite dans la partie inférieure de la cellule remplie.

Le remplissage du tableau commence par la première ligne, où sont stockées les informations sur la dernière étape du chemin. La dernière, dans ce cas, la quatrième étape du chemin est déterminée de manière unique lors de la transition depuis n'importe quel avant-dernier état, qui peut être l'un des trois possibles : s 9, s 10, s 11. Un contrôle optimal à la dernière étape est donc évident. Selon l'avant-dernier état, la contribution au critère d'optimalité est L 4 (9) = 12, L 4 (10) = 6, ou L 4 (11) = 7. Ces valeurs de contribution à L sont écrites en bas des cellules de la première ligne du tableau. 6.4.1.

Avant l'avant-dernière - dans ce cas, la troisième - étape, l'ensemble des états possibles du système est (s 5, s 6, s 7, s 8). Appliquons maintenant le principe de Bellman pour déterminer la trajectoire aux troisième et quatrième étapes. Cela réside dans le fait que, quelles que soient les deux premières étapes de contrôle, le segment de trajectoire dans les deux dernières étapes est lui-même une trajectoire optimale, c'est-à-dire donne la contribution minimale de L 3 au critère d'optimalité.

Si l'état du système avant l'avant-dernière étape est l'état s 8, alors aux dernières étapes la contribution à L est déterminée par la relation

L 3 (s 5) = min ( }.

Puisque de s 5 des transitions vers s 9 et s 11 sont possibles, soit :

g(s 5,9) = s 9; ; L 4 (s 9) = 12,

g(s 5,11) = s 11; ; L 4 (s 11) = 7,

L 3 (s 5) = min(6+12, 4+7) = 11 et u (3) = 11.

Cela signifie que si le système est dans l’état s 5, alors le contrôle optimal consiste à passer d’abord à l’état s 11, puis à l’état s 12. La longueur de l'arc de s 5 à s 12 s'avère être égale à 11 unités.

En calculant la contribution à L de la même manière pour les transitions des états s 6, s 7, s 8, on obtient les contributions suivantes :

L 3 (s 6) = min (7 + 12, 6 + 6) = 12, u (3) = 10 ;

L 3 (s 7) = min (5 + 6, 3 + 7) = 10, u (3) = 11 ;

L 3 (s 8) = min (10 + 6, 12 + 7) = 16, u (3) = 10 ;

Les quatre paires de nombres résultantes sont écrites dans la deuxième ligne du tableau. 6.4.1.

A la deuxième étape de contrôle, la contribution au critère d'optimalité en fonction de l'état initial est

L 2 (s 2) = min( ) = min(11+11, 14+10) = 22, u (2) = 5;

L 2 (s 3) = min( ) = min(7+11, 9+12) = 18, u (2) = 5;

L 2 (s 4) = min( ) = min(2+16, 3+12, 6+10) = 15, u (2) = 6;

Les trois paires de nombres résultantes sont écrites dans la troisième ligne du tableau 6.4.1.

L'état initial s 1 est déterminé de manière unique, par conséquent, dans la dernière ligne du tableau, la seule cellule est remplie, où les valeurs 3 et 24 sont écrites car :

L 1 (s 1) = min( ) = min(5+22, 6+18, 11+15) = 24, u (1) = 3.

Nous pouvons maintenant enfin déterminer la séquence de contrôle optimal en plusieurs étapes. À la première étape u (1) = 3, c'est-à-dire du nœud 1 on passe au nœud 3, à la deuxième étape u (2) = 5, c'est-à-dire on passe au nœud 5, puis après contrôle u (3) = 11 - au nœud 11 et, enfin, au nœud 12. On obtient finalement que le chemin le plus court à travers le réseau représenté sur la Fig. 6.4.1, passe par la séquence d'états s 1 → s 2 → s 5 → s 11 → s 12, et sa longueur est de 24 unités conventionnelles.

La recherche du chemin le plus court peut également être effectuée dès le début du réseau, tout en mettant en œuvre un algorithme de balayage direct, qui effectue essentiellement les mêmes opérations d'addition et de comparaison, mais dans une séquence légèrement différente.

Les algorithmes de balayage avant et arrière, bien que essentiellement différents, fournissent une addition et une comparaison par arc. Les deux algorithmes ont donc les mêmes performances. Il existe cependant une différence importante. L'algorithme de balayage avant considère les arcs sortant de ces nœuds, les chemins les plus courts je je qui sont déjà connus.

L'algorithme de balayage arrière considère les arcs boîte de réception vers ces nœuds, les chemins les plus courts l j qui sont encore inconnus. En raison de cette dernière circonstance, la préférence est souvent donnée à l’algorithme de balayage direct. Cet algorithme peut être appliqué à n’importe quelle structure de l’ensemble des chemins les plus courts.

La résolution d'un problème simple du plus court chemin illustre un certain nombre de caractéristiques suivantes, inhérentes à des processus décisionnels en plusieurs étapes beaucoup plus complexes :

1. Le problème d'origine est immergé dans de nombreux problèmes d'optimisation ; dans ce cas, chaque nœud résout son propre problème.

2. L'ensemble des solutions aux problèmes d'optimisation est décrit par une équation fonctionnelle, qui est un système d'équations reliant plusieurs problèmes d'optimisation. Dans un tel système, chaque équation correspond à un nœud et contient généralement des opérateurs comme min, max ou minimax à droite du signe égal, et des variables comme g i et g j des deux côtés de celui-ci.

3. La solution à de nombreux problèmes d'optimisation peut être trouvée à l'aide d'un algorithme de balayage arrière, qui équivaut à une procédure ordonnée pour résoudre une séquence d'équations fonctionnelles.

La programmation dynamique est bien adaptée pour résoudre les problèmes liés à la modélisation de systèmes de réseau qui n'ont pas de structure particulière. Ainsi, les algorithmes de balayage avant et arrière conviennent pour effectuer des calculs dans des réseaux acycliques. L'algorithme de balayage arrière peut être généralisé et utilisé pour résoudre des problèmes dans lesquels il existe un élément de hasard. Cela ne peut pas être fait pour l’algorithme de balayage direct.

Le concept d'« état » joue un rôle central dans la programmation dynamique, et les états signifient ce qui suit. La transition s'effectue d'un état à un état contenant l'intégralité de l'historique du processus, c'est-à-dire que l'état est décrit avec un degré de détail permettant le calcul (l'évaluation) des solutions alternatives actuelles.

Pour le modèle de réseau, les états sont les nœuds et les arcs sortant d'un certain nœud représentent les différentes décisions qui peuvent être prises au niveau de ce nœud (état). Avec cette interprétation, nous pouvons dire que la transition se produit d’un État à l’autre et que les États représentent des points où les décisions sont prises. L'énoncé ci-dessus signifie que les arcs sortant d'un nœud n'ont aucun rapport avec le chemin par lequel tel ou tel nœud a été atteint, c'est-à-dire qu'ils ne dépendent pas des arcs entrants.

Les éléments d'état sont souvent appelés variables d'état. Dans les modèles de programmation dynamique, les états sont parfois regroupés en étapes et la transition s'effectue d'une étape à l'autre. Par exemple, dans le problème du chemin le plus court, il y a des états, mais il n'y a pas d'étapes, car il est impossible de regrouper les états en ensembles de telle manière qu'il y ait une transition d'un ensemble à un autre.

Plonger dans une variété de problèmes d'optimisation revient à introduire le concept espace d'état qui représente un ensemble d’états. Dans l’équation fonctionnelle, la réponse optimale est considérée comme fonction de l’état de départ, et le principe d’optimalité établit la relation entre les réponses optimales pour différents états de départ.

Beaucoup S les états possibles (ou observables) sont appelés espace d'état, et élément s depuis S définit un spécifique État. Avec chaque condition s beaucoup connectés D(s) . Élément d de beaucoup D(s) s'appelle décision. La règle selon laquelle une solution réalisable est déterminée pour chaque état est appelée stratégie d.

En fait stratégie d correspond à chaque état s un élément d( s) de nombreux D(s). L'ensemble de toutes ces formes d espace stratégique D. Ce dernier signifie que le choix d’une solution dans un État ne contraint pas le choix dans tous les autres États. Essentiellement, D est un produit cartésien d'ensembles D(s) Par s.

L'une des idées de la programmation dynamique est que chaque stratégie d doit avoir une fonction dite de profit. Vd(s), qui peut être obtenu en fonction de l'état s et en utilisant la stratégie d. La notion de fonction de profit (ou de revenu) généralise la notion de contribution L t à la valeur globale du critère d'optimalité L considéré lors de la résolution du problème du plus court chemin.

L’expression « utiliser la stratégie d » signifie que vous êtes capable de s solution ré( s); le processus est alors supposé être entré dans l'état s", c'est-à-dire que l'État est réalisé s", dans laquelle la solution d( s"), etc. La fonction de profit a une structure assez complexe, puisqu'elle dépend de la séquence d'états et de décisions, des récompenses qui sont associées à ces états et décisions, ainsi que de la manière dont les récompenses sont agrégées.

Un état est une description de l’historique d’un processus avec un niveau de détail permettant une évaluation des solutions alternatives actuelles. La propriété principale des États est que l’État est un bref enregistrement de l’histoire du processus, et degré de détail permet de déterminer la fonction de revenu local En d’autres termes, la fonction de revenu local ne peut dépendre que de s, d Et v.

Le prochain chapitre examinera plus en détail les chaînes de Markov, qui sont d'une grande importance pour modéliser l'évolution temporelle des systèmes de production et techniques. Il existe également des modèles décisionnels markoviens dans lesquels l’État s déterminé par une paire de nombres (n, je), la solution est la fonction qui en dépend k, et la fonction de revenu local est déterminée par une expression telle que h[(n, je) , k, v] = R k je(n) + å j P k ij(n)v(m+ 1,j) (n ).

Les modèles de prise de décision markoviens sont généralisés dans différentes directions, notamment au cas Problèmes de reconstruction markovienne. La généralisation la plus utile est obtenue lorsque des temps de transition inégaux ou variables sont considérés. Dans les modèles simples, on suppose que la transition d'un état à l'autre et l'observation de l'état sont instantanées, et que la durée entre les transitions d'un état à l'autre peut être de durée variable ou aléatoire.

Chaque fois qu'un état est observé, une solution est sélectionnée et ne peut pas être modifiée jusqu'à ce que le processus passe à un nouvel état, où une nouvelle solution est sélectionnée, etc. Ce modèle est une combinaison de la théorie des chaînes de Markov et de la théorie de la restauration ; habituellement appelé Problème de reconstruction markovienne.

Questions du test pour le chapitre 6.

1. De quels composants se compose un réseau dirigé ?

1. Comment la matrice de capacité du réseau est-elle construite ?

1. Comment se forme la matrice de flux du réseau ?

1. Pourquoi les matrices de capacité et de débit sont-elles soustraites ?

1. Qu'est-ce qu'un schéma de réseau et à quoi sert-il ?

1. Comment sont déterminées les heures de début et de fin anticipées des travaux ?

1. Quel est le flottant total pour un événement sur le diagramme de réseau ?

1. Comment le chemin critique est-il déterminé ?

1. Qu'appelle-t-on le vecteur d'état d'un certain système ?

1. Quelle est la trajectoire d’un système dans l’espace d’états ?

1. Quel est le problème du contrôle optimal ?

1. Comment est formulé le critère d’optimalité ?

1. Qu'est-ce que la programmation dynamique ?

1. Formulez le principe d'optimalité de Bellman.

1. Quelle est l’essence des algorithmes de balayage avant et arrière lors de la recherche du chemin le plus court ?

Options pour les devoirs du chapitre 6.

Pour les réseaux dans chacune des options :

1) Trouver le débit maximum de la source (1) au nœud final du réseau - le puits, en supposant que l'un des nombres entre parenthèses pour chaque arc (i, j) détermine la capacité de l'arc ;

1) En supposant que les arcs (1)®(2), (1)®(3), etc. définissent des travaux dont la durée minimale et maximale sont précisées par les chiffres indiqués sous les arcs correspondants, trouver le chemin critique de l'événement initial (1) à la fin ;

1) Recherchez le chemin le plus court du nœud de départ au nœud de fin du réseau. Considérons les distances entre les nœuds i, j données par l'un des nombres entre parenthèses.

X 4

La leçon examinera le concept de programmation dynamique et l'aspect historique de son apparition. Des problèmes de programmation dynamique et quelques exemples de leurs solutions sont considérés.

Le concept de « programmation dynamique » a été utilisé pour la première fois dans les années 1940 par Richard Bellman pour décrire le processus de recherche d'une solution à un problème dans lequel la réponse à un problème ne peut être obtenue qu'après avoir résolu un autre problème qui le « précède ».
Ainsi, le mathématicien américain et l'un des plus grands experts dans le domaine des mathématiques et de l'informatique - Richard Ernst Bellman- est devenu le père de la programmation dynamique.

Plus tard, la formulation du concept a été affinée et améliorée jusqu'à sa forme moderne par Bellman lui-même.

Le mot « programmation » dans le contexte de la « programmation dynamique », fait en fait référence à la compréhension classique de la programmation (écrire du code dans un langage de programmation) ça n'a pratiquement rien à voir avec ça. Le mot « Programmation » a la même signification que dans l’expression « programmation mathématique », qui est synonyme du mot « optimisation ».

C'est pourquoi programmes sera utilisé comme séquence d'actions optimale pour obtenir une solution au problème.

En général, pour commencer, définition informelle de la programmation dynamique pourrait ressembler à ceci :

Programmation dynamique est une technique ou une méthode qui permet de résoudre certains problèmes de combinatoire, d'optimisation et d'autres problèmes qui ont une certaine propriété (la propriété de co-optimalité pour les sous-tâches).

Problèmes d'optimisation, en règle générale, sont associés à la tâche de maximiser ou de minimiser l'une ou l'autre fonction objectif (par exemple, maximiser la probabilité que le système ne tombe pas en panne, maximiser le profit attendu, etc.).

Problèmes combinatoires, en règle générale, répondez à la question de savoir combien d'objets ont certaines propriétés, ou combien d'objets combinatoires ont des propriétés données.

Autrement dit, DP ne résout pas tous les problèmes, mais seulement certains, une certaine classe de sous-tâches. Mais cette classe de sous-tâches est utilisée dans de nombreux domaines de la connaissance : programmation, mathématiques, linguistique, statistiques, théorie des jeux, économie, informatique, etc.

Les problèmes résolus à l'aide de la programmation dynamique doivent avoir propriété de co-optimalité, qui sera discuté dans d’autres leçons.

Une explication informelle de la propriété d'optimalité des sous-problèmes peut être démontrée à l'aide d'un diagramme :
Il y a un problème que nous voulons résoudre en utilisant DP, c'est-à-dire trouvez un plan pour le résoudre. Disons que ce problème est complexe et que nous ne pouvons pas le résoudre tout de suite. Nous prenons un petit sous-problème et le résolvons d’abord (pour x1). Puis en utilisant cette petite solution x1, et sans changer la structure de cette solution, nous résolvons le problème suivant avec x1 et x2. Etc.

Riz. 1.1. Une explication informelle de la propriété d'optimalité des sous-problèmes

L’explication informelle est discutée plus en détail.

Exemples de problèmes résolus grâce à la programmation dynamique

Tout d’abord, considérons les problèmes d’optimisation (tâches 1 à 5) :

1. Itinéraire de longueur optimale

Exemple: Il existe une feuille de route présentée sous forme de graphique. Notre objectif : aller de l'avant UN pointer B. Cela doit être fait de manière à minimiser la distance ou le gaspillage de carburant.

Fonction objectif voici la distance de UNà B. Ceux. notre objectif est de minimiser la distance.

Et qu'est-ce que c'est variable de sélection? Afin de trouver le chemin le plus court, vous devez prendre des décisions à chaque fois. Ceux. A chaque point ou à chaque intersection, des décisions doivent être prises : où tourner ou aller tout droit.

Important: A partir de ce problème, vous pouvez déjà voir la structure générale des problèmes résolus à l'aide de la programmation dynamique : Chaque problème a une fonction objectif et une variable de choix.

2. Remplacement d'une machine (minimiser les coûts)

Exemple: Chaque année, nous décidons soit de conduire l'ancienne voiture pendant un an supplémentaire et d'assumer les frais d'entretien et d'entretien de l'ancienne voiture, soit de vendre la voiture et d'en acheter une nouvelle (et d'assumer les frais d'achat).

Fonction objectif : minimiser les coûts (soit les coûts d'entretien d'une vieille voiture, soit l'achat d'une nouvelle).

Variable de sélection : prendre la décision chaque année de vendre la voiture ou de la conserver.

3. Portefeuille d'échange

Exemple: Jouer en bourse, acheter des actions de toutes entreprises


Fonction objectif : maximisation moyenne revenu, parce que en bourse, les revenus sont obtenus de manière probabiliste, c'est-à-dire c'est un processus statistique, probabiliste.

Variable de sélection : quel type de portefeuille d'investissement il y aura : combien d'actions et quelle société nous devons acheter.

4. Élaboration d'un plan de production optimale (logistique)

Exemple: Il y a une usine qui fabrique des meubles. L'usine emploie un certain nombre d'ouvriers capables de produire la quantité correspondante de certains meubles (chaises, tables, armoires, etc.)


Fonction objectif: maximisation du profit.

Variable de sélection : choisir le nombre de chaises ou de tables à fabriquer pour avoir suffisamment de main d'œuvre.

5. Jeux (probabilistes ou non probabilistes)

Exemple: Participation à divers jeux


Fonction objectif : maximiser la probabilité de gagner ou maximiser le gain moyen, etc.

La variable de sélection dépend ici du jeu spécifique.

Les problèmes 1 à 5 sont des exemples de problèmes d'optimisation.

Combinatoire :

6. Graphiques et arbres

Exemple: La tâche consiste à décider combien d’arbres ont un certain nombre de feuilles ; ou combien de graphiques existent pour résoudre telle ou telle tâche, etc.

7. Problème d'échange de pièces ou nombre de façons de rendre la monnaie

Exemple: Il existe des pièces de différentes coupures, de quelles manières pouvez-vous restituer la monnaie.

Il s'agit d'une brève description des problèmes de programmation dynamique qui seront discutés en détail plus tard.

Le concept de programmation dynamique

Une explication informelle de l'optimalité des sous-problèmes DP.

Considérons informel Idée DP.

Prenons donc l’exemple d’une usine de fabrication de meubles.

Pour Pour atteindre l'objectif de maximisation du profit, il est nécessaire de résoudre de nombreuses sous-tâches :

• combien de chaises produire - variable X1,
• combien de tableaux produire - variable X2,
• combien de travailleurs embaucher - variable X3,
• ... Xn.

Avec un grand nombre de sous-problèmes, il est difficile de comprendre comment résoudre un tel problème. En règle générale, il est plus facile de résoudre un petit problème que de résoudre un gros problème composé de petits.

Par conséquent, le DP propose ce qui suit :

• Nous prenons une sous-tâche avec la variable X1 et oublions les sous-tâches restantes pour le moment.

Par exemple, une usine ne produit que des chaises. Le directeur a pour tâche de tirer le maximum de profit de la vente des chaises.

• Après avoir trouvé la solution optimale pour la première sous-tâche, nous prenons la sous-tâche pour deux variables X1 et X2 et la résolvons en utilisant la solution déjà trouvée pour la première sous-tâche.
• Nous obtenons une solution pour une sous-tâche plus grande, où apparaissent les variables X1 et X2. Ensuite, en utilisant la solution obtenue, nous prenons des sous-tâches couvrant X1, X2 et X3.
• Et ainsi nous continuons jusqu'à ce que nous obtenions une solution à l'ensemble du problème général.

Idée formelle de DP

Souvent, lorsqu’on pose un problème, la solution apparemment optimale est essayer toutes les options possibles. Cependant, en raison du très grand nombre de ces options et, par conséquent, de la surcharge de la mémoire de l'ordinateur, cette méthode n'est pas toujours acceptable.

De plus, la question suivante peut se poser : pour trouver, par exemple, le minimum ou le maximum, pourquoi ne trouve-t-on pas la dérivée ? ou ne pas utiliser les ensembles de La Grange, ou d'autres méthodes d'analyse mathématique ? Pourquoi avez-vous besoin de DP si vous disposez d’un large arsenal de moyens ?

Le fait est que :

La programmation dynamique est basée sur l'idée de résoudre un problème donné en le divisant en parties distinctes (sous-tâches, étapes), en résolvant ces sous-tâches puis en combinant ces solutions en une seule solution commune. Souvent, la plupart des sous-tâches sont exactement les mêmes.

Il est important que lors de la résolution d'un problème plus complexe, nous ne résolvions pas à nouveau un petit sous-problème, mais utilisions la réponse déjà résolue à ce sous-problème.
Sur un graphique, cela pourrait ressembler à ceci :

Important: Pour cette raison, diviser une tâche en sous-tâches et résoudre ces sous-problèmes une seule fois (!), réduisant ainsi le nombre de calculs globaux - une méthode plus optimale, inhérente à la programmation dynamique

Lorsque nous résolvons un problème avec des dérivées, des ensembles de La Grange, etc., nous travaillons avec des fonctions continues. Lors de la résolution de problèmes DP, nous travaillerons principalement avec des fonctions discrètes, il est donc inapproprié de parler ici de l'utilisation de fonctions continues.
Pour cette raison, dans de nombreux problèmes, mais pas dans tous, le recours à l’analyse mathématique sera inacceptable.

Un exemple simple de résolution de problèmes à l'aide de DP

Considérons la possibilité de résoudre le problème en utilisant la programmation dynamique.

Exemple: Il faut calculer la somme de n nombres : 1 + 2 + 3 + ... + n

Quelle est la prétendue « difficulté » de ce problème : il faut prendre un grand nombre de nombres à la fois et obtenir la réponse.

Essayons d'appliquer les idées DP au problème et de le résoudre en le décomposant en sous-tâches simples.
(En DP, il faut toujours déterminer d'abord les conditions ou conditions initiales)

• Commençons par la somme du premier élément, c'est-à-dire prenons juste le premier élément :
  F(1) = 1
• Maintenant, en utilisant la solution du premier élément, nous résolvons
  F(2) = F(1) + 2 = 1 + 2 = 3, c'est-à-dire vous devez prendre la somme du premier élément et y ajouter le deuxième élément
• F(3) = F(2) + 3 = 6
• On continue par analogie et on obtient la fonction objectif :
  F(n) = F(n-1) + An

Alors, ce que nous avons fait : nous avons déterminé l'ordre et identifié les sous-tâches, puis nous avons résolu chacune d'elles, sur la base de la solution de la précédente.

Un exemple simple, où le DP est encore utilisé de manière injustifiée (artificiellement), démontre le principe des idées du DP.

Regardons un autre exemple.

Exemple: il y a un escalier de n marches, devant lequel il y a une personne qui est derrière 1 La marche peut soit monter à la marche suivante, soit sauter par-dessus une marche. Question : de combien de manières peut-il atteindre la dernière étape ?

Solution:

Considérons les options les plus simples (sous-tâches) :

Regardons un exemple de i étapes

Comment pouvons-nous arriver à l'étape i :

1. de l'étape i-1, et nous pourrions arriver à l'étape i-1 de différentes manières
2. de l'étape i-2, et nous pourrions accéder à l'étape i-2 de différentes manières

Par exemple, comment se rendre à 4ème étape:

Que., nombre total de façons passer à l'étape i :
f(une je) = f(une je-1) + f(une je-2)

Déterminons les valeurs initiales, à partir duquel commencer à résoudre le problème.
Si vous commencez par 1, alors la formule correspond à trouver la séquence de nombres de Fibonacci.

Nous voyons que le problème est essentiellement combinatoire (c'est-à-dire que le nombre de façons de faire quelque chose) a été réduit au calcul d'une séquence récurrente.

Tâche 1 : implémentez un exemple pour les dix premières étapes (essentiellement les 10 premiers nombres de la série de Fibonacci), en utilisant la récursion.

Complétez le code :

1 2 3 4 5 6 7 8 9 10 11 12 13

var c : entier ;

procédure getKolSposob(i, n: entier ) ;

commencer l'écriture (i+ n, " " ) ;
inc(c);

si ... alors getKolSposob(...,... ) end ;

1. commencer c: = 1 ;

getKolSposob(0 , 1 ) ;

fin.
var c:entier;

Considérons procédure getKolSposob(i,n : entier);.
Décomposons le processus décisionnel en plusieurs étapes en n mesures. Notons ε 0 l'état initial du système, par ε 1, ε 2, … ε n– état du système après le premier, le deuxième, n-ème étape. En général, l'État ε k– vecteur (ε k 1 , …, ε ks).
Gestion dans un processus en plusieurs étapes, un ensemble de solutions (variables de contrôle) est appelé Royaume-Uni = (Royaume-Uni 1 , ..., ok r) pris à chaque étape k et transférer le système de l'état ε k-1 = (ε k- 1 1 , …, ε k -1 s) pour énoncer ε k = (ε k 1 , …, ε ks).
Dans les processus économiques, la gestion consiste en la distribution et la redistribution des fonds à chaque étape. Par exemple, la production de produits par toute entreprise est un processus contrôlé, puisqu'il est déterminé par des changements dans la composition des équipements, le volume des approvisionnements en matières premières, le montant du financement, etc. Un ensemble de décisions prises au début de l'année, la période de planification, pour fournir à l'entreprise les matières premières, le remplacement des équipements, le montant du financement, etc. est la gestion. Il semblerait que pour obtenir le volume de production maximum, le moyen le plus simple est d'investir le maximum de fonds possible et d'utiliser l'équipement à pleine capacité. Mais cela entraînerait une usure rapide des équipements et, par conséquent, une diminution du rendement de la production. La libération du produit doit donc être planifiée de manière à éviter les effets indésirables. Il est nécessaire de prendre des mesures pour garantir que les équipements soient réapprovisionnés au fur et à mesure de leur usure, c'est-à-dire au fil du temps. Cette dernière, bien qu'elle entraîne une diminution du volume initial de production, offre la possibilité d'étendre la production à l'avenir. Ainsi, le processus économique de production peut être considéré comme composé de plusieurs étapes (étapes), dont chacune influence son développement.
Le début d'une étape (étape) d'un processus contrôlé est considéré comme le moment où une décision est prise (sur le montant de l'investissement en capital, sur le remplacement d'équipements d'un certain type, etc.). Une étape est généralement comprise comme une année commerciale.
Généralement sous contrôle à chaque étape Royaume-Uni certaines restrictions s'appliquent. Les contrôles qui satisfont à ces restrictions sont appelés acceptable.
En supposant que l'indicateur de performance k la ème étape du processus dépend de l'état initial à cette étape k-1 et du contrôle à cette étape Royaume-Uni, nous obtenons la fonction objectif de l'ensemble du processus en plusieurs étapes sous la forme :
.

Formulons maintenant le problème de programmation dynamique: « Déterminer l’ensemble des contrôles admissibles ( toi 1 , …, toi), transférant le système de l'état initial ε 0 à l'état final ε n et maximiser ou minimiser l'indicateur d'efficacité F».
Contrôle qui atteint le maximum (minimum) de la fonction F appelé contrôle optimal toi * = (toi 1* ,…, toi *).
Si les variables de contrôle Royaume-Uni prennent des valeurs discrètes, alors le modèle DP est appelé discret. Si les variables Royaume-Uni change continuellement, alors le modèle DP est appelé continu.
En fonction du nombre de paramètres d'état s et nombre de variables de contrôle r différencier unidimensionnel Et multidimensionnel Tâches DP.
Le nombre d'étapes dans une tâche peut être final ou sans fin.

Problèmes appliqués de programmation dynamique

1. problème de planification de la construction des installations.