Donnons une formulation mathématique du principe d'optimalité. Pour plus de simplicité, nous supposerons que les états initial x 0 et final x T du système sont donnés. Notons par z 1 (x 0 , u 1) la valeur de la fonction but à la première étape avec l'état initial du système x 0 et avec contrôle u 1 , par z 2 (x 1 , u 2) le correspondant valeur de la fonction but uniquement à la deuxième étape, . ..
z je (х je -1 ,u je) – sur ième étape, ..., via z N (x N -1, u N) - à la Nième étape. Il est évident que
Il faut trouver le contrôle optimal u*= (; ;...;), tel qu'il délivre l'extremum de la fonction objectif (1) sous restrictions.
Pour résoudre ce problème, nous le plongeons dans une famille de problèmes similaires. Introduisons quelques notations. Soient respectivement les zones
définitions de problèmes similaires à la dernière étape, aux deux dernières, etc. ;
– domaine de définition du problème initial. Notons F 1 (x N -1), F 2 (x N -2), ..., F k (x N -k), ..., F N (x 0), respectivement, le conditionnellement optimal valeurs de la fonction objectif à la dernière étape, deux les dernières, etc., aux k dernières, etc., à toutes les N étapes.
Commençons par la dernière étape. Soit x N-1 les états possibles du système au début de la Nième étape. Nous trouvons:
F 1 (x N -1) = z N (x N -1, u N). (2)
Pour les deux dernières étapes, nous obtenons
F 2 (x N -2) = (Z N -1 (x N -2, u N -1) + F 1 (x N -1)). (3)
De même:
F 3 (x N -3) = (Z N -2 (x N -3, u N -2) + F 2 (x N -2)). (4)
………………………………………………….
F k (x N -k) = (z N-k +1 (x N -k , u N-k +1) + F k- 1 (x N-k +1)). (5)
…………………………………………………..
F N (x 0) = (z 1 (x 0, u 1) + F N -1 (x 1)). (6)
L'expression (6) est une représentation mathématique du principe d'optimalité. L'expression (5) est la forme générale d'écriture de la valeur conditionnellement optimale de la fonction objectif pour les k étapes restantes. Les expressions (2) à (6) sont appelées équations fonctionnelles de Bellman. Leur nature récurrente (récurrente) est clairement visible, c'est-à-dire que pour trouver le contrôle optimal à N étapes, vous devez connaître le contrôle conditionnellement optimal aux N – 1 étapes précédentes, etc. Par conséquent, les équations fonctionnelles sont souvent appelées récurrentes (récurrentes) Relations Bellman.
- Caractéristiques des tâches programmation dynamique
Sur la base de ce qui précède, nous pouvons mettre en évidence les caractéristiques suivantes des problèmes de programmation dynamique.
- Nous considérons un système dont l'état à chaque étape est déterminé par le vecteur x t. Un changement supplémentaire dans son état dépend uniquement de l'état donné x t et ne dépend pas de la manière dont le système est arrivé à cet état. De tels processus sont appelés processus sans séquelles.
- A chaque étape, une solution u t est sélectionnée, sous l'influence de laquelle le système passe de l'état précédent x t -1 au nouvel état x t . Ce nouvel état est fonction de l'état au début de l'intervalle x t -1 et de la décision u t adoptée au début de l'intervalle, soit x t = x t (x t -1 ,u t).
- L'action à chaque étape est associée à un certain gain (revenu, profit) ou perte (coûts), qui dépend de l'état au début de l'étape (étape) et de la décision prise.
- Des restrictions peuvent être imposées aux vecteurs d'État et de contrôle, dont la combinaison constitue la région des solutions réalisables.
- Il est nécessaire de trouver un tel contrôle admissible u t pour chaque étape t afin d'obtenir la valeur extrême de la fonction objectif pour toutes les T étapes.
Toute séquence d'actions valide pour chaque étape qui transfère le système de l'état initial à l'état final est appelée stratégie de contrôle. Une stratégie de contrôle qui aboutit à une valeur extrême de la fonction objectif est dite optimale.
L'interprétation géométrique du problème de programmation dynamique est la suivante. Soit n la dimension de l'espace d'état. A chaque instant, les coordonnées du système ont une valeur bien précise. Avec un changement de temps t, les valeurs de coordonnées du vecteur d'état peuvent changer. Appelons la transition d'un système d'un état à un autre la trajectoire de son mouvement dans l'espace des états. Une telle transition s'effectue en influençant les coordonnées de l'état. L'espace dans lequel les états du système servent de coordonnées est appelé espace des phases. Le problème de programmation dynamique peut être interprété particulièrement clairement si l’espace d’états est bidimensionnel. La zone des états possibles dans ce cas sera représentée par un certain chiffre, les états initial et final du système - par les points x 0 (Fig. 1). Le contrôle est l’influence qui fait passer le système de l’état initial à l’état final. Pour de nombreux problèmes économiques, l'état initial ou final n'est pas connu, mais la région X 0 ou X T à laquelle appartiennent ces points est connue.
Image 1
Ensuite, les contrôles admissibles transfèrent les points de la région X 0 à X T . Le problème de programmation dynamique peut être formulé géométriquement comme suit : trouver une trajectoire de phase commençant dans la région X 0 et se terminant dans la région X T pour laquelle la fonction but atteint une valeur extrême. Si les états initial et final d’un problème de programmation dynamique sont connus, alors on parle d’un problème à extrémités fixes. Si les régions initiales et finales sont connues, alors on parle d’un problème avec les extrémités libres.
- PROBLÈME DE DISTRIBUTION DES RESSOURCES
2.1 Énoncé général du problème
Considérons l'application de la méthode de programmation dynamique en utilisant l'exemple de la répartition des fonds entre six objets de reconstruction d'une entreprise de distribution d'eau municipale :
1. Station centrale de pompage et de filtration ;
2. Station de pompage et de filtration Est ;
3. Station de pompage d’eau ;
4. Station d'aération centrale ;
5. Station d'aération Est ;
6. Station d'aération de campagne.
Le montant total des fonds prévus pour le développement ne dépasse pas 195 000 hryvnia. Sur la base de calculs techniques et économiques, il a été établi qu'à la suite de la reconstruction, en fonction du montant des fonds dépensés, les installations auront la productivité indiquée dans le tableau 1.1. Il est nécessaire de déterminer la répartition optimale des fonds entre les objets de reconstruction, qui assurera l'augmentation maximale de la productivité de ces objets. Ainsi, ce problème utilise un critère d'optimisation - la productivité totale des entreprises d'objets de reconstruction.
Tableau 1.1 Données d'entrée pour la productivité des objets de reconstruction
Numéro de série de l'objet |
Volume des ressources allouées au développement des installations (milliers UAH) |
|||||||||||||
Productivité des objets suite à l'aménagement (milliers m3) |
||||||||||||||
- Schéma fonctionnel du programme
Figure 1. Programme principal
QtObj – nombre d'objets
QtRes – nombre de ressources
effMatrix - matrice de performances des objets,
distVector – vecteur des ressources allouées
Étape 1. Optimisation conditionnelle
Étape 2. Optimisation inconditionnelle
I = QtObj-1.0 forme le résultat vectoriel
Figure 2. Saisie des données
distVector – vecteur de distance, effMatrix = matrice de performances
si tous les éléments de la matrice sont renseignés
si le vecteur de performance n'est pas
négatif
Figure 3. Optimisation conditionnelle,
on forme une matrice de sortie (maximum de la fonction objectif)
outMatrix – matrice cible maximale
QtObj – nombre d'objets
QtRes – nombre de ressources
Matrice – matrice de performances
distVect – vecteur de distance (vecteur de ressource)
non oui Si la première entreprise
Trouver le maximum
oui maxItem = temp; outMatrix[i][j] = maxItem
- Structure de l'algorithme du programme
- Saisie de données – classe DataDlg.
Membres de classe variables.
//vecteur pour stocker la quantité de ressources
std :: vecteur
//matrice de performances des objets
int** effMatrix ;
//fonction pour convertir une chaîne en nombre
int ChaîneVersInt(CString);
//fonction pour vérifier l'exactitude des données saisies
BOOL FillMatrix();
//fonction de nettoyage des ressources après fermeture de la fenêtre
virtuel BOOL DestroyWindow();
//fonction d'initialisation du dialogue
virtuel BOOL OnInitDialog();
- Calcul des résultats - la classe principale du programme courseWorkDlg
Membres de la classe variables
valeurint; //valeur de performance
int MaxIndex;// index maximum dans le vecteur de ressources
int Installation ;//entreprise
int Recource;//ressource dédiée
Article ** outMatrix ; //matrice cible maximale
std :: vecteur
void BuildOutMatrix(int **,std::vecteur
afx_msg void OnBnClickedButton1(); // gestionnaire pour cliquer sur le bouton « Calculer », qui démarre le processus de calcul.
virtual BOOL DestroyWindow();//effacement des ressources du programme
- Sortie du rapport de classe de résultats
Le but de cette classe est de générer le vecteur résultat sous forme de tableau.
2.4 Résultats du programme
Saisie initiale des données
- Saisie de données sur la productivité des objets de reconstruction
- Si tous les champs ne sont pas remplis
- Si un caractère incorrect est saisi
Saisie correcte des données
Afficher le résultat
- Entrée de données
Résultat du programme
Saisie initiale des données
Saisir la productivité des objets
Application.
Liste des programmes
int DataDlg :: StringToInt (CString str)
const wchar_t* s = T2CW(str);
int val = _wtoi(s);
// est-ce que tous les champs sont remplis ?
BOOL DataDlg::FillMatrix()
booléen indicateur = vrai ;
pour (int je = 0; je< Cells.GetSize(); i ++){
pour (int j = 0 ; j< Cells.GetAt(i)->Edits.GetSize(); j++)(
CEdit * temp = Cells.GetAt(i)->Edits.GetAt(j) ;
if (temp->m_hWnd != NULL)(
temp->GetWindowText(str);
si (str.IsEmpty())(
MessageBox(L"Vous devez remplir tous les champs", L"Erreur", MB_ICONERROR | MB_OK);
Description du travail
Le but de ce travail est de mettre en œuvre sur ordinateur une solution au problème de l'allocation optimale des fonds pour l'expansion de la production.
Objectifs du cours :
Considérer aspects théoriques résoudre des problèmes de programmation dynamique ; caractère récurrent des tâches de ce genre; Les principes d'optimalité de Bellman.
Développement d'algorithmes. Schémas fonctionnels. Structure de l'algorithme.
Implémentation informatique de l'algorithme développé dans le langage de programmation sélectionné.
Contenu
INTRODUCTION………………………………………………………2
Programmation dynamique
Notions de base…………………4
Principes de programmation dynamique. Équations fonctionnelles de Bellman…………………….5
Caractéristiques des problèmes de programmation dynamique……………….10
Problème d’allocation des ressources………………………12
Exposé général du problème………………………….13
Schéma fonctionnel du programme
Structure de l'algorithme du programme
Résultat du programme
Conclusion
Bibliographie
1. Notions de base
1.1. Modèle de programmation dynamique
1.2. Le principe d'optimalité. Équation de Bellman
2. Allocation optimale des ressources
2.1 Énoncé du problème
2.2 Modèle d'allocation des ressources bidimensionnel
2.3 Modèle dynamique discret d'allocation optimale des ressources
2.4 Prise en compte des séquelles dans les problèmes d’allocation optimale des ressources
Conclusion
Liste des sources utilisées
Annexe 1. Liste de programmes pour résoudre le problème de l'allocation optimale des ressources avec des paramètres donnés. Résultats du programme
Introduction
Tout au long de l’histoire, les gens ont eu recours à des rituels complexes lorsqu’ils étaient confrontés à des décisions. Ils organisaient des cérémonies solennelles, sacrifiaient des animaux, racontaient l'avenir grâce aux étoiles et observaient le vol des oiseaux. Ils s’appuyaient sur des superstitions populaires et essayaient de suivre des règles primitives qui leur facilitaient la tâche difficile de prendre des décisions. Actuellement, un nouveau « rituel » apparemment plus scientifique est utilisé pour prendre des décisions, basé sur l’utilisation d’un ordinateur électronique. Sans moderne moyens techniques L’esprit humain ne peut probablement pas prendre en compte les facteurs nombreux et variés rencontrés dans la gestion d’une entreprise, la conception d’une fusée ou la régulation du trafic. Il existe actuellement de nombreux méthodes mathématiques les optimisations sont déjà assez développées, ce qui permet d'utiliser efficacement les capacités du numérique et de l'hybride des ordinateurs. L'une de ces méthodes est la programmation mathématique, qui inclut la programmation dynamique comme cas particulier.
La plupart des problèmes pratiques en comportent plusieurs (et certains peut-être même nombre infini) solutions. Le but de l'optimisation est de trouver la meilleure solution parmi tant d’autres potentiellement possibles selon un certain critère d’efficacité ou de qualité. Un problème qui ne permet qu’une seule solution ne nécessite pas d’optimisation. L'optimisation peut être obtenue à l'aide de nombreuses stratégies, allant de procédures mathématiques analytiques et numériques très complexes à l'utilisation intelligente d'arithmétique simple.
La programmation dynamique est une méthode d'optimisation adaptée aux opérations dans laquelle le processus de prise de décision peut être décomposé en étapes (étapes) distinctes. De telles opérations sont appelées en plusieurs étapes.
En tant que branche de la programmation mathématique, la programmation dynamique (DP) a commencé à se développer dans les années 50 du 20e siècle. grâce au travail de R. Bellman et de ses associés. Pour la première fois, des problèmes de gestion optimale des stocks ont été résolus à l'aide de cette méthode, puis la classe de problèmes s'est considérablement élargie. Comment méthode pratique optimisation, la méthode de programmation dynamique n’est devenue possible qu’avec l’utilisation de la technologie informatique moderne.
La méthode de programmation dynamique repose sur le principe d'optimalité formulé par Bellman. Ce principe et cette idée d'inclusion tâche spécifique les optimisations dans une famille de problèmes similaires en plusieurs étapes conduisent à des relations récurrentes - des équations fonctionnelles - concernant la valeur optimale de la fonction objectif. Leur solution nous permet d’obtenir systématiquement un contrôle optimal pour le problème d’optimisation d’origine.
1. Notions de base
1.1 Modèle de programmation dynamique
Donne moi description générale modèles de programmation dynamique.
Nous considérons un système contrôlé qui, sous l'influence du contrôle, passe de l'état initial
à l'état final. Supposons que le processus de gestion du système puisse être divisé en P. pas. Soit , ,…, les états du système après le premier, le deuxième,..., P.-ème étape. Ceci est schématisé sur la Fig. 1.
Image 1
État
systèmes après kièmeétape ( k = 1,2 …,n) est caractérisé par les paramètres , ,…, appelés coordonnées de phase. L'état peut être représenté par un point dans l'espace de dimension s appelé espace des phases. Une transformation cohérente du système (étape par étape) est obtenue à l'aide de certaines activités , ,…, , qui constituent la gestion du système
, où est le contrôle sur k-étape, transférant le système d'un état à l'autre (Fig. 1). Gestion sur k La ème étape consiste à sélectionner les valeurs de certaines variables de contrôle. Nous supposons désormais que l'état du système à la fin kième l'étape dépend uniquement de l'état précédent du système
et la gestion sur cette étape(Fig. 1). Cette propriété est appelée aucune séquelle. Notons cette dépendance par
, (1.1)
Les égalités (1.1) sont appelées équations d'états. Les fonctions
nous supposons donné.Contrôle variable U , nous obtiendrons différentes « efficacités » du processus, que nous évaluerons quantitativement par la fonction objectif Z , en fonction de l'état initial du système
et à partir du contrôle sélectionné U : . (1.2)Indicateur de performance kièmeétape du processus de contrôle, qui dépend de l’état
au début de cette étape et le contrôle choisi à cette étape sera désigné par le problème d'optimisation étape par étape considéré fonction objectif(1.2) doit être additif, c'est-à-dire
. (1.3)
Si la propriété d'additivité de la fonction objectif Z n'est pas satisfaite, cela peut parfois être réalisé par certaines transformations de la fonction. Par exemple, si Z est une fonction multiplicative donnée par
, alors on peut considérer une fonction additive. Généralement, les conditions du processus sont contrôlées à chaque étape
certaines restrictions s'appliquent. Contrôles satisfaisant à ces restrictions sont dits recevables .Le problème d'optimisation étape par étape peut être formulé comme suit : déterminer l'ensemble des contrôles réalisables
Informatique, cybernétique et programmation
Fonds X alloués à quelle entreprise génère des bénéfices à la fin de l'année. Les fonctions sont données dans un tableau : X f1X f2X f3X f4X 1 8 6 3 4 2 10 9 4 6 3 11 11 7 8 4 12 13 11 13 5 18 15 18 16 Déterminer combien d'argent doit être alloué à chaque entreprise afin que le bénéfice total est égal à la somme des bénéfices reçus de chaque entreprise était le plus élevé. Laissez le montant des fonds alloués à quelle entreprise. Les équations à la mième étape satisfont à la condition : soit on n'attribue rien à quelle entreprise : soit pas plus...
Travaux de laboratoire 4_2. Résoudre le problème de l'allocation des ressources à l'aide de la méthode de programmation dynamique.
But du travail explorer les capacités du processeur de table MS Excel pour résoudre le problème de l'allocation de ressources limitées à l'aide de la méthode de programmation dynamique.
La construction d'un modèle de programmation dynamique (DP) et l'application de la méthode DP pour résoudre le problème se résument à ce qui suit :
- choisir une méthode de division du processus de gestion en étapes ;
- définir les paramètres d'état et les variables de contrôle X k à chaque étape ;
- écrire des équations d'état ;
- introduire des fonctions objectives k l'étape et la fonction objectif totale ;
- introduire en considération les maxima (minimums) conditionnels et le contrôle optimal conditionnel sur kème étape : .
- Notez le DP principal du circuit de calculÉquations de Bellmanpour et selon la règle :
- Les équations de Bellman sont résolues séquentiellement (optimisation conditionnelle) et deux séquences de fonctions et sont obtenues.
- Après avoir effectué une optimisation conditionnelle, la solution optimale pour un état spécifique est obtenue :
a) et
b) le long de la chaîne contrôle optimal (solution).
Énoncé du problème de programmation dynamique sous forme générale.
La tâche . Les activités de quatre entreprises industrielles sont prévues pour l'année prochaine. Fonds initiaux : USD L'investissement dans chaque entreprise est un multiple de 1 unité conventionnelle. Installations X, attribué k
|
f1 (X) |
f2(X) |
f3 (X) |
f4 (X) |
|
Déterminez combien d'argent doit être alloué à chaque entreprise pour que le profit total (égal à la somme des bénéfices reçus de chaque entreprise) soit le plus grand.
Solution. Soit le montant des fonds alloués k -ème entreprise. Le bénéfice total est égal. Variables X satisfaire aux restrictions : . Il est nécessaire de trouver des variables qui satisfont à ces restrictions et maximisent la fonction Z.
Diagramme de solutions le problème utilisant la méthode DP a la forme suivante : le processus de résolution de la répartition des fonds peut être considéré comme un processus en 4 étapes, le numéro de l'étape coïncide avec le numéro de l'entreprise ; choix des variables équations sur 1, 2, 3, 4 étapes en conséquence ; - l'état final du processus de distribution est égal à zéro, car tous les fonds doivent être investis dans la production,=0 .
Les équations d'état et le schéma de distribution peuvent être représentés comme suit :
Ici - paramètre d'état montant des fonds restants après k -ème étape, c'est-à-dire fonds qui restent à répartir entre les autres (4- k) les entreprises.
Introduisons en considération une fonction - le profit conditionnellement optimal reçu du ième, ( k +1 )ème, ..., 4ème entreprises, si les fonds étaient répartis de manière optimale entre elles). Les équations à la ième étape satisfont à la condition : (ou k Nous n’attribuons rien à la -ième entreprise : soit pas plus que ce que nous avons pourème étape :).
Les équations de Bellman ont la forme :
Les équations sont résolues par optimisation séquentielle de chaque étape.
Étape 4 Tous les fonds restant à la 4ème étape devraient être investis dans la 4ème entreprise, car, selon le tableau, les bénéfices augmentent de façon monotone. Dans ce cas, pour les valeurs possibles on obtient :
Étape 3 . On fait des hypothèses concernant le solde des fonds par la 3ème étape : elle peut prendre les valeurs 0,1,2,3,4,5 (=0, si tous les fonds sont donnés aux 1ère et 2ème entreprises, etc.). En fonction de cela, nous sélectionnons et comparons les valeurs de somme pour différentes valeurs à des valeurs fixes. Pour chacune, le maximum de ces valeurs est le profit optimal conditionnel obtenu avec la répartition optimale des fonds entre la 3ème et la 4ème entreprise. Les valeurs obtenues pour sont indiquées dans le tableau dans les colonnes 5 et 6, respectivement.
|
S k-1 |
k =3 |
k =2 |
k =1 |
||||||||
|
f 3 (X 3 )+ |
f 2 (X 2 )+ |
f 1 (X 1 )+ |
|||||||||
|
0+4=4 3+0=3 |
0+4=4 6+0=6 |
0+6=6 8+0=8 |
|||||||||
|
0+6=6 3+4=7 4+0=4 |
0+7=7 6+4=10 9+0=9 |
0+10=10 8+6=14 10+0=10 |
|||||||||
|
0+8=8 3+6=9 4+4=8 7+0=7 |
0+9=9 6+7=13 9+4=13 11+0=11 |
0+13=13 8+10=18 10+6=16 11+0=11 |
|||||||||
|
0+13=13 3+8=11 4+6=10 7+4=11 11+0=11 |
0+13=13 6+9=15 9+7=16 11+4=15 13+0=13 |
0+16=16 8+13=21 10+10=20 11+6=17 12+0=12 |
|||||||||
|
0+16=16 3+13=16 4+8=12 7+6=13 11+4=15 18+0=18 |
0+18=18 6+13=19 9+9=18 11+7=18 13+4=17 15+0=15 |
0+19=19 8+16=24 10+13=23 11+10=21 12+6=18 18+0=18 |
|||||||||
2 étapes k =2. Pour toutes les valeurs possibles, les valeurs de et se trouvent respectivement dans les colonnes 8 et 9 ; les premiers termes de la colonne 7 sont extraits de la condition, les seconds termes sont extraits de la colonne 5 lorsque.
1 étape . L'optimisation conditionnelle est effectuée dans le tableau à k =1 pour.
Si, alors=5 ; le bénéfice reçu de quatre entreprises, à condition que = 5 fonds entre les trois entreprises restantes soient répartis de manière optimale, est égal à.
Si, alors=4 ; le bénéfice total, à condition que = 4 fonds entre les trois entreprises restantes soient répartis de manière optimale, est égal à.
De même, quand, et ;
Quand, et ;
Quand, et ;
En comparant les valeurs obtenues, nous obtenons à.
En calculant, nous obtenons, et à partir du tableau de la colonne 9, nous trouvons. Ensuite, nous trouvons, et dans la colonne 6. Enfin, et. Solution optimale.
Répondre. Le bénéfice total maximum est de 24 USD. à condition qu'une entreprise reçoive 1 USD ; La 2ème entreprise a reçu 2 USD ; 3ème entreprise - 1 USD ; 4ème entreprise - 1 USD
Mise en œuvre de la tâche dans MS Excel
- La saisie des données initiales dans le tableau est illustrée à la Fig. 1.
Fig. 1. Saisie des données source dans les cellules de la feuille de calcul MS Excel
2. L'ordre de remplissage des cellules du tableau :
1). Vers la cellule E 15 entrez la formule INDEX($B$3:$F$8,MATCH($C15,$B$3:$B$8),G$12+1) et copiez la formule dans la plage de cellules avec E 15 à E 35.
2). Dans la cellule F 15, entrez la formule
INDEX($B$3:$F$8,MATCH($D15,$B$3:$B$8),5) et copiez la formule dans la plage de cellules avec F 15 à F 35.
3). Dans la cellule G 15, entrez la formule E 15+ F 15 et copiez la formule dans la plage : G15 - G35.
4). On retrouve la valeur maximale pour chaque état de 0 à 5, à cet effet dans la cellule H15 entrez la formule MAX(G15); après avoir entré une formule dans une cellule H16 il faut changer la plage de G 16 à G 16 : G 17, etc. le long de toute la colonne jusqu'à la cellule H 30 (Fig. 2a).
3. Rechercher la valeur de contrôle qui correspond à la valeur maximale de la fonction, prévue à cet effet dans la cellule je 15 entrons dans la formule INDEX($ C 15 : G 15 ; MATCH (H 15 ; G 15;0);1), copiez la formule dans la cellule je 16 et augmentez la portée, ce qui entraîne la cellule je 16 on obtient : INDICE($ C 16 : G 17 ;MATCH(H 16 ; G 16 : G 17;0);1). Ensuite, copiez la formule dans les cellules J'ai 18 ans, j'ai 21 ans, j'ai 25 ans, j'ai 30 ans , augmentant progressivement la portée (Fig. 2b)
Fig.2a. Type de feuille de calcul avec des formules, k =3.
Fig.2b ( partie droite feuille de calcul avec des formules, k =3
En conséquence nous obtenons :
Riz. 3 . Le résultat de la première étape ( k =3).
4. Sélectionnez une plage E 15:Je 35, exécutez la commande Copie J 15 et exécutez la commande Insérer .
5. Changeons la formule de la fonction. Aux cellules K 15, K 16, K 18, K 21, K 25, K 30 nous entrons respectivement les valeurs maximales de l'étape précédente situées dans les cellules H 15, H 16, H 18, H 21, H 25, H 30. Dans les cellules restantes on place les valeursdans la même colonne et correspondant aux précédentes S k . :
Vers la cellule K 17 copiez les valeurs de la cellule K15 ;
dans les cellules K19 et K20, les valeurs K16 et K17 ;
en K22:K24 valeurs K18:K20 ;
en K26:K29 valeurs K21:K24 ;
en K31:K35 valeurs K25:K29 ;
En conséquence nous obtenons :
Figure 4. Le résultat de la deuxième étape ( k =2).
6. Sélectionnez une plage de cellules J15:N 35, exécutez la commande Copie , placez le curseur dans la celluleÔ 15, exécutez la commande Insérer . En conséquence, nous obtenons un tableau complété avec une solution pour k =1 (Fig.5)
7. Expliquons les résultats obtenus : à. En calculant, nous obtenons, et à partir du tableau de la colonne 12, nous trouvons. Ensuite, nous déterminons, et à partir de la colonne 6. Enfin, et. Ainsi, la valeur optimale et la valeur de la fonction sont de 24 cu, ce qui correspond aux données obtenues manuellement.
Fig.6. Le résultat de la troisième étape ( k =1).
Exercices de contrôle. Possibilités.
1. Les activités de quatre entreprises industrielles sont prévues pour l'année prochaine. Fonds initiaux USD Le montant de l'investissement dans chaque entreprise est un multiple de 1 USD. Installations X, attribué k la ème entreprise (), génère des bénéfices à la fin de l'année. Les fonctions sont spécifiées dans un tableau :
|
f1 (X) |
f2(X) |
f3 (X) |
f4 (X) |
|
Déterminez combien d'argent doit être alloué à chaque entreprise pour que le profit total soit le plus élevé.
2. Les activités de trois entreprises industrielles sont prévues pour l'année prochaine. Fonds initiaux : USD Le montant de l'investissement dans chaque entreprise est un multiple de 1 USD. Installations X, attribué k la ème entreprise (), génère des bénéfices à la fin de l'année. Les fonctions sont spécifiées dans un tableau :
|
f1 (X) |
f2(X) |
f3 (X) |
|
Déterminez combien de fonds doivent être alloués à chaque entreprise pour que le profit total soit le plus élevé.
Ainsi que d'autres ouvrages qui pourraient vous intéresser |
|||
| 58796. | Perspectives géographiques | 977,5 Ko | |
| Par la fin de la leçon, vous devriez être capable de reconnaître et de comprendre de nouveaux mots et combinaisons de mots dans le texte, de lire et de comprendre l'essentiel et les détails malgré les difficultés naturelles. | |||
| 58797. | Informations et processus d'information. Système informatique | 128 Ko | |
| Zagalny caractéristique de ceux-là. Règles de sécurité dans le compte PEOM. L'informatique. Notions d'information. Informations et bruit. Processus d'information. Informations et notifications. | |||
| 58798. | Systèmes d'exploitation | 126 Ko | |
| Table de travail. Objets Windows de base. Vision de l'objet. Opérations, autorités et commandes de base pour travailler avec des objets. Menu contextuel de l'objet. Les étiquettes sont faites pour leur usage. | |||
| 58799. | Bases de la robotique avec disques | 144,5 Ko | |
| Zagalny caractéristique de ceux-là. Formatage du disque. Diagnostic et défragmentation des disques. Informations mises à jour sur le disque. Règles d'écriture et de lecture des informations à partir de disquettes. | |||
| 58800. | Éditeur de texte | 190 Ko | |
| Systèmes de traitement de texte et leurs principales fonctions. Zavantazhennya éditeur de texte. Interface de l'éditeur. Ligne d'informations. Modes d'écran, vikoristannya vikon. | |||
| 58801. | Editeur graphique | 708 Ko | |
| Zagalny caractéristique de ceux-là. Graphiques de machines. Écran graphique. Système de traitement de l'information graphique. Les inserts sont des dessins de primitives graphiques lorsque vous travaillez avec un éditeur. Types de fichiers graphiques. | |||
| 58802. | Tableaux électroniques | 280,5 Ko | |
| Navchalna. Décrire un nouveau sujet et souligner son rôle dans le cours d'informatique. Entrez dans le concept de table électronique. Familiarisez les étudiants avec les programmes de traitement ET, les règles de saisie et de modification des informations dans ET et les méthodes de formatage ET. | |||
| 58803. | Systèmes de gestion de bases de données (SGBD) | 156,5 Ko | |
| Hommages de base. Base de données documentaire factuelle. Modèle iєrarchique, merezheva, relationnel de la base de données. Les principaux éléments de la base de données : champ, enregistrement, fichier. SGBD. | |||
Brève théorie
La programmation dynamique (également connue sous le nom de planification dynamique) est une méthode permettant de trouver solutions optimales dans des problèmes avec une structure en plusieurs étapes (multi-étapes). De nombreux processus économiques sont naturellement divisés en étapes. Ce sont tous des processus de planification et de gestion développés au fil du temps. Une étape naturelle peut être une année, un trimestre, un mois, une décennie, une semaine, un jour, etc. Cependant, la méthode de programmation dynamique peut être utilisée pour résoudre des problèmes où le temps n'apparaît pas du tout ; La division en étapes dans de tels problèmes est introduite artificiellement. Par conséquent, la « dynamique » des problèmes de programmation dynamique réside dans la méthode de résolution.
Dans la pratique économique, il existe plusieurs types de problèmes qui, selon leur formulation ou leur mode de solution, appartiennent à des problèmes de programmation dynamique. Il s’agit de problèmes de planification optimale à long terme et actuelle dans le temps. Ils sont résolus soit en compilant un ensemble de modèles statiques interconnectés pour chaque période, soit en compilant un seul problème de programmation optimale dynamique en utilisant une procédure de prise de décision en plusieurs étapes. Les problèmes de programmation dynamique incluent les problèmes de recherche en plusieurs étapes de l'optimum dans le placement des forces productives, ainsi que des performances optimales.
Caractéristiques typiques des problèmes en plusieurs étapes.
1. Nous considérons un système dont l'état à chaque étape est déterminé par le vecteur . Un changement ultérieur de son état dépend uniquement de cet état et ne dépend pas de la manière dont le système y est parvenu. De tels processus sont appelés processus sans séquelles.
2. A chaque étape, une solution est sélectionnée, sous l'influence de laquelle le système passe de l'état précédent au nouveau. Ce nouvel état est fonction de l'état au début de l'intervalle et de la décision prise au début de l'intervalle, c'est-à-dire
3. L'action à chaque étape est associée à un certain gain (revenu, profit) ou perte (coût), qui dépend de l'état au début de l'étape (étape) et de la décision prise.
4. Des restrictions peuvent être imposées à l'État et aux vecteurs de contrôle, dont l'union constitue la région des solutions réalisables.
5. Il est nécessaire de trouver un tel contrôle admissible pour chaque étape afin d'obtenir la valeur extrême de la fonction objectif pour toutes les étapes.
Tout problème en plusieurs étapes peut être résolu de différentes manières. Premièrement, nous pouvons considérer les quantités inconnues u et trouver l’extremum de la fonction objectif en utilisant l’une des méthodes d’optimisation existantes, c’est-à-dire rechercher tous les éléments de la solution à toutes les étapes en même temps. A noter que ce chemin ne mène pas toujours au but, surtout lorsque la fonction objectif est donnée sous forme de tableaux ou que le nombre de variables est très important. La deuxième voie repose sur l’idée de réaliser une optimisation par étapes. Le phasage n'implique pas l'isolement dans l'optimisation des étapes. Au contraire, le contrôle à chaque étape est choisi en tenant compte de toutes ses conséquences. Habituellement, la deuxième méthode d'optimisation s'avère plus simple que la première, notamment avec un grand nombre d'étapes. L'idée d'une optimisation progressive, étape par étape, est l'essence même de la méthode de programmation dynamique. L'optimisation en une étape est généralement plus facile à optimiser l'ensemble du processus dans son ensemble. Il est préférable de résoudre plusieurs fois un problème relativement simple plutôt que de résoudre un problème complexe une seule fois.
À première vue, l’idée peut paraître triviale : s’il est difficile d’optimiser un problème complexe, il faut alors le décomposer en plusieurs problèmes plus simples. A chaque étape, un petit problème est optimisé, ce qui n'est pas difficile. En même temps, le principe de programmation dynamique n’implique pas du tout que chaque étape soit optimisée isolément, indépendamment des autres. Au contraire, le contrôle incrémental doit être choisi en tenant compte de toutes ses conséquences.
On peut formuler les principes suivants qui sous-tendent la programmation dynamique : le principe d'optimalité et le principe d'immersion.
Le contrôle optimal à chaque étape est déterminé par l'état du système au début de cette étape et l'objectif du contrôle. Ou sous forme développée : la stratégie optimale a la propriété que, quels que soient l'état initial et les décisions initiales, les décisions ultérieures doivent être prises sur la base de la stratégie optimale, en tenant compte de l'état résultant de la première décision. Ce principe a une interprétation mathématique assez simple, exprimée dans la compilation de certaines relations récurrentes (équations fonctionnelles de R. Bellman).
La nature du problème qui permet l'utilisation de la méthode de programmation dynamique ne change pas lorsque le nombre d'étapes change, c'est-à-dire la forme d'un tel problème est invariante par rapport à . En ce sens, tout processus spécifique comportant un nombre d'étapes donné s'avère pour ainsi dire immergé dans une famille de processus qui lui est similaire et peut être considéré du point de vue d'une classe plus large de problèmes.
La mise en œuvre de ces principes garantit que la décision prise à l'étape suivante sera la meilleure par rapport à l'ensemble du processus, et non à des intérêts étroits. cette étape. Sous-séquence solutions étape par étape conduit à la solution du problème de l’étape initiale.
Donnons une formulation mathématique du principe d'optimalité pour les problèmes avec un critère d'optimalité additif (fonction objectif séparable). Pour simplifier, nous supposerons que les états initial et final du système sont donnés. Notons par la valeur de la fonction but au premier étage à l'état initial du système et pendant le contrôle, par - la valeur correspondante de la fonction but uniquement au deuxième étage, ...., par - au stade , ..., par - à la -ème étape. Il est évident que
Il est nécessaire de trouver le contrôle optimal tel qu'il délivre l'extremum de la fonction objectif sous les contraintes.
Pour résoudre ce problème, nous le plongeons dans une famille de problèmes similaires. Introduisons quelques notations. Soient respectivement les domaines de définition de problèmes similaires à la dernière étape, aux deux dernières, etc. ; - domaine de définition du problème initial. Notons par
en conséquence, les valeurs conditionnellement optimales de la fonction objectif à la dernière étape, aux deux dernières, etc., à la dernière, etc., à toutes les étapes.
Commençons par la dernière étape. Soit les états possibles du système au début de la ème étape. Nous trouvons:
Pour les deux dernières étapes, nous obtenons :
De même:
…………………….
…………………….
L'expression (5) est une représentation mathématique du principe d'optimalité. L'expression (4) est la forme générale d'écriture de la valeur conditionnellement optimale de la fonction objectif pour les étapes restantes. Les expressions (1) à (5) sont appelées équations fonctionnelles de Bellman. Leur caractère récurrent (de retour) est clairement visible, c'est-à-dire pour trouver le contrôle optimal aux étapes, vous devez connaître le contrôle conditionnellement optimal aux étapes précédentes, etc. Par conséquent, les équations fonctionnelles sont souvent appelées relations de Bellman récurrentes.
Exemple de solution de problème
La tâche
L'association de production accorde à quatre de ses entreprises membres un prêt d'un montant de 100 millions d'unités monétaires. pour augmenter la production et augmenter la production de produits. Pour chaque entreprise, l'augmentation possible de la production (en termes monétaires) est connue, en fonction du montant qui lui est alloué. Pour simplifier les calculs, les montants alloués sont des multiples de 20 millions d'unités monétaires. Dans le même temps, nous supposons que l'augmentation de la production dans l'entreprise ne dépend pas du montant des fonds investis dans d'autres entreprises et que l'augmentation totale de la production dans l'association de production est égale à la somme des augmentations obtenues dans chaque entreprise. de l'association.
Il est nécessaire de trouver une solution optimale pour répartir le crédit entre les entreprises afin que l'augmentation globale de la production de l'association de production soit maximale.
| Fonds alloués, millions d'unités monétaires | Entreprise | №1 | №2 | №3 | №4 | Augmentation de la production dans les entreprises, en millions d'unités monétaires. | 20 | 10 | 12 | 11 | 16 | 40 | 31 | 24 | 36 | 37 | 60 | 42 | 36 | 45 | 46 | 80 | 62 | 52 | 60 | 63 | 100 | 76 | 74 | 77 | 80 |
La solution du problème
Si les délais de livraison travail d'essai Nous manquons de temps, vous pouvez toujours commander une solution urgente aux problèmes en utilisant des méthodes de solution optimales sur le site Web.
La programmation dynamique est une recherche en plusieurs étapes de la solution optimale. L'optimisation d'un processus en plusieurs étapes est basée sur le principe d'optimalité de R. Bellman.
Les calculs en programmation dynamique sont effectués de manière récursive - la solution optimale à un sous-problème est utilisée comme données d'entrée pour trouver la solution optimale au sous-problème suivant. Après avoir résolu le dernier sous-problème, nous obtenons la solution optimale au problème initial.
| Fonds alloués | 0 | 0 | 0 | 0 | 0 | 20 | 10 | 12 | 11 | 16 | 40 | 31 | 24 | 36 | 37 | 60 | 42 | 36 | 45 | 46 | 80 | 62 | 52 | 60 | 63 | 100 | 76 | 74 | 77 | 80 |
Étape 1
Conformément au schéma informatique de la programmation dynamique, considérons d'abord le cas, c'est-à-dire Supposons que tous les fonds disponibles soient alloués à la reconstruction et à la modernisation d'une entreprise. Désignons par le revenu supplémentaire maximum possible dans cette entreprise correspondant au montant alloué. Chaque valeur correspond à une valeur (unique) bien précise de revenu complémentaire, on peut donc écrire que :
Étape 2
Laissez maintenant, c'est-à-dire les fonds sont répartis entre deux entreprises. Si un montant est attribué à la deuxième entreprise, le revenu supplémentaire qui en découlera sera de . Les fonds restants pour une autre entreprise, selon la taille (et donc ) vous permettront d'augmenter les revenus supplémentaires jusqu'à la valeur maximale possible. Sous cette condition, le revenu supplémentaire total des deux entreprises est de :
Étape 3
Laissez maintenant, c'est-à-dire les fonds sont répartis entre trois entreprises. Si un montant est attribué à la troisième entreprise, le revenu supplémentaire qui en découlera sera de . Les fonds restants, selon la taille (et donc ) vous permettront d'augmenter les revenus complémentaires jusqu'à la valeur maximale possible. Sous cette condition, le revenu supplémentaire total dans trois entreprises est :
Étape 4
Laissez maintenant, c'est-à-dire les fonds sont répartis entre quatre entreprises. Si un montant est attribué à la quatrième entreprise, le revenu supplémentaire qui en découle sera de . Les fonds restants, selon la taille (et donc ) vous permettront d'augmenter les revenus complémentaires jusqu'à la valeur maximale possible. Sous cette condition, le revenu supplémentaire total de quatre entreprises est :
Répondre
Le plan de répartition optimal de 100 unités de ressource entre 4 entreprises :
| 0 | 20 | 40 | 40 |
Dans ce cas, l’augmentation totale de la production atteindra une valeur maximale de 85.
Moyenne le coût de résolution d'un test est de 700 à 1 200 roubles (mais pas moins de 300 roubles pour la totalité de la commande). Le prix est fortement influencé par l'urgence de la décision (d'une journée à plusieurs heures). Le coût de l'aide en ligne pour un examen/test est de 1 000 roubles. pour résoudre le ticket.
Vous pouvez poser toutes les questions sur le coût directement dans le chat, après avoir préalablement envoyé les conditions de la tâche et vous avoir informé du délai de solution dont vous avez besoin. Le temps de réponse est de quelques minutes.
Exemples de problèmes connexes
Modèle de base de gestion des stocks
À l'aide de l'exemple de résolution du problème, le modèle de base de gestion des stocks (modèle Wilson) est considéré. Des indicateurs de modèle tels que la taille optimale du lot de commande, les coûts de stockage annuels, l'intervalle entre les livraisons et le point de passation des commandes ont été calculés.
Problème de programmation quadratique
Un exemple de résolution d'un problème de programmation quadratique convexe à l'aide d'une méthode graphique est donné.
Jeux de stratégie mixtes
Contient des informations théoriques présentées sous une forme concise et accessible sur un jeu matriciel sans point de selle et une méthode pour réduire un tel problème au problème programmation linéaire, pour trouver sa solution dans des stratégies mixtes. Un exemple de résolution du problème est donné.