User Tools

Site Tools


Sidebar

* [[http://www.labri.fr/perso/melancon|Me as a researcher]] --- * [[start|Home]] * [[proj_techno:start|Projets technologiques - Licence 3 Informatique]] 4TIN601U * [[proj_CMI_L2:start|Projet de programmation - CMI ISI]] 4TCM401U * [[MIAGE:processus_stoch_simulation|Processus stochastiques et simulation - MIAGE et e-MIAGE]] 4TYE814U / 4TYE808U ---- * **Fête de la Science** - [[mathc2+:analyse|"Analyse de réseau appliquée aux réseau sociaux"]] ---- * Master U de Bx * [[http://www.labri.fr/perso/melancon/Visual_Analytics_Course/|Visual Analytics]] * [[e-miage_ubx_i|e-MIAGE U de Bx]] * [[estia:estia|ESTIA DataViz / Data Science]] * [[Enseignements passés]] ---- * [[http://www.labri.fr/perso/melancon|Research]] ---- * [[admin:Site admin]]

A PCRE internal error occured. This might be caused by a faulty plugin
miage_solution:solution_allocation

====== Master 4TYE814U/4TYE808U MIAGE & e-MIAGE -- Processus stochastiques et simulation ====== ===== Séance de travaux dirigé ===== ==== Allocation budgétaire -- Solution ==== On dispose d'un budget global de $L$ euros et de $N$ demandes de financement de $L_i$ euros chacune ($i = 1, \ldots, N$). Comme $L < L_1 + \cdots + L_N,$ il faudra choisir les demandes à satisfaire. On considère les sous-ensembles $A \subset \{1, \ldots, N\}$ tels que $\sum_{i \in A} L_i \leq L$ et on considère l'objectif $U(A) = L - \sum_{i \in A} L_i$ qu'il s'agit de minimiser (on veut utiliser une masse budgétaire maximale). On considère une chaîne de Markov dont les états sont les sous-ensembles de $\{1, \ldots, N\}$. --- **Combien d'états cette chaîne compte t-elle ?** * Une affectation budgétaire consiste des demandes $L_i$ qui seront accordées, qui correspond à un sous-ensemble de $\{1, \ldots, N\}$. Le nombre maximum d'états est donc de $2^N$. En effet, certains sous-ensembles $A$ ne donnent pas lieu à des affectations budgétaires précisément lorsque $U(A) < 0$). ---- On définit la fonction de transition suivante. Soit $A$ un sous-ensemble. * On choisit au hasard uniformément un entier $i$ parmi $\{1, \ldots, N\}$; * On modifie $A$: * (a) Si $i \in A$, on passe à $A' = A \setminus \{i\}$ * (b) Si $i \not \in A$, on passe à $A' = A \cup \{i\}$ quand c'est possible (si $U(A') \geq 0$); sinon, on reste en $A$. **Expliciter cette fonction de transition (quelles sont les probabilités de transition ?). Montrer que cette fonction de transition est irréductible et symétrique.** On peut rassembler les entiers $i \in \{1, \ldots, N\}$ en trois cas: - Soit $i \in A$ - Soit $i \not \in A$ et $U(A) + L_i \leq L$ - Soit $i \not \in A$ et $U(A) + L_i > L$ Un entier $i$ peut être choisi aléatoirement parmi $\{1, \ldots, N\}$ avec probabilité $1/N$. - Dans le premier cas, l'entier $i$ induit une transition $A \to A' = A \setminus \{i\}$ avec probabilité $1/N$ - Dans le second cas, l'entier $i$ induit une transition $A \to A' = A \cup \{i\}$ avec probabilité $1/N$ - Dans le troisième cas, l'entier $i$ induit une transition $A \to A$ avec probabilité $1/N$ Cette dernière transition se fait donc avec une probabilité $k/n$ où $k$ est le nombre d'entiers qui entre dans ce cas. On a bien la symétrie puisque: * La transition $A \to A' = A \setminus \{i\}$ (cas 1) peut être suivie de la transition $A' \to A' \cup \{i\} = A$ (cas 2) avec probabilité $1/N$ aussi. * La transition $A \to A' = A \cup \{i\}$ (cas 2) peut être suivie de la transition $A' \to A' \setminus \{i\} = A$ avec probabilité $1/N$ aussi. Cette chaîne est irréductible. Pour s'en convaincre, il faut exhiber un chemin allant de tout ensemble $A$ (avec $U(A) \geq 0$) à tout autre ensemble $A'$ (avec $U(A') \geq 0$). * On considère le sous-ensemble vide $\emptyset$ pour lequel on a bien $U(\emptyset) \geq 0$; c'est donc bien un état de notre chaîne de Markov. * On peut aller de $\emptyset$ à $A = \{i_1, \ldots, i_p\}$ par une suite de transitions (cas 2): $\emptyset \to \{i_1\} \to \{i_1, i_2\} \to \cdots \to \{i_1, i_2, \ldots, i_p\} = A$. Comme la chaîne est symétrique on a aussi une suite de transitions (cas 1) $A \to \cdots \to \{i_1\} \to \emptyset $. * De la même manière, on peut aller de $\emptyset$ à $A' = \{j_1, \ldots, j_q\}$ par une suite de transitions (cas 2): $\emptyset \to \{j_1\} \to \{j_1, j_2\} \to \cdots \to \{j_1, j_2, \ldots, j_q\} = A'$. * En conjuguant toutes ces transitions on trouve bien un chemin allant de $A$ à $A'$. Notre chaîne est donc bien irréductible et symétrique. ---- On peut maintenant se servir de cette chaîne de Markov, et la modifier à l'aide de l'algorithme de Metropolis pour tenter de trouver une solution qui optimise l'affectation budgétaire, c'est-à-dire une affectation $A$ pour laquelle $U(A)$ est minimale. **Donner une distribution cible pour laquelle la probabilité va croissante en fonction de l'utilisation du budget disponible $L$.** * On peut prendre, //par exemple//, n'importe quelle fonction décroissante définie sur $[0, L]$ (à gauche) * $\pi'(A) = e^{-U(A)}$ * On peut aussi prendre une fonction dont la décroissance ets "moins prononcée" (attention toutefois au budget nul $\emptyset$ qu'il faut traiter isolément) (à droite) * $\pi'(A) = \frac{1}{U(A)}$ ^ Fonction ^ Courbe ^ | $e^{-U(A)}$ | {{miage:exponentielle.jpeg?direct&150|}} | | $\frac{1}{U(A)}$ | {{miage:un_sur_x.jpeg?direct&150|}} | --- **Donnez la fonction de transition de l'algorithme de Metropolis permettant de calculer une solution approchée de l'optimum (en effectuant une marche aléatoire sur le graphe des états de la chaîne de Markov précédente).** * La transition depuis un état $A$ se fait en choisissant au départ un état $A'$ selon la fonction de transition de la chaîne de Markov de départ. * On calcule le ratio $p = \min \{\frac{\pi'(A')}{\pi'(A)}, 1\}$ * On effectue la transition $A \to A'$ avec probabilité $p$ --- [[miage:metropolis_suite|Retourner au TD]]

miage_solution/solution_allocation.txt · Last modified: 2017/02/26 12:43 by melancon