Examens avec Solutions Recherche opérationnelle
Corrigé de l'examen de la session normale. Recherche opérationnelle. Semestre 6 Filière Economie et Gestion Ensembles : 2 et 3 M .ATMANI. Exercice 1. 1°) le
- Exercices de TD - 1 Modélisation.
Le but de cet exercice est la recherche d'une stratégie mixte optimale pour le jeu de Morra. 2. Page 3. FLIN606 Prog. linéaire 2011/2012. 1 MOD ÉLISATION. a
Livret dexercices Théorie des Graphes et Recherche Opérationnelle
29 août 2016 Donnez la modélisation par graphe. Quel est le problème formel ? Donnez la solution. 6.6 Publication des bancs. Soit M la matrice d'adjacence d' ...
Recherche opérationnelle
La recherche opérationnelle (aussi appelée “aide `a la décision”) peut être Modéliser cet exercice de façon `a pouvoir répondre aux questions suivantes :.
RECHERCHE OPERATIONNELLE
RECHERCHE OPERATIONNELLE – L3 GESTION – M. MEGHRAOUI – SEMESTRE 2. 26. Application numéro 8 : EXERCICES AUTO CORRIGES. Page 21. RECHERCHE OPERATIONNELLE – L3
Introduction à loptimisation et la recherche opérationnelle (2017
21 sept. 2018 Modélisation – corrigé (21 septembre 2018). Solution de la question 1 ... Note : Cette exercice est une version simplifiée du problème réel de ...
Modélisation mathématique en écologie : cours et exercices corrigés
d'images et du signal finance
MODÉLISATION MATHÉMATIQUE EN ÉCOLOGIE
Cours et exercices corrigés. Pierre Auger. Directeur de recherche à l'Institut d'images et du signal finance
GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir
Le but de cet exercice est de rechercher la limite de la suite (an) en utilisant deux méthodes différentes. Première méthode : graphe probabiliste. Pour
Recherche opérationnelle
Exercice d'application. Exercice d'application - corrigé : 1). Variables de décision : x1 : quantité de produits P1 fabriqués x2 : quantité de produits P2
- Exercices de TD - 1 Modélisation.
Modéliser le probl`eme sous forme d'un programme linéaire en nombres entiers. Le but de cet exercice est la recherche d'une stratégie mixte optimale ...
Recherche Opérationnelle:
Recherche Opérationnelle: Notes de cours et exercices corrigés ... permettent de modéliser des processus dans lesquels une réalisation dépend de la ...
Introduction `a la recherche opérationnelle
13 juil. 2017 La recherche opérationnelle (RO) est la discipline des ... parcours est impossible – en procédant `a une modélisation subtile par des mots.
Recherche opérationnelle
1.2 Modélisation d'un programme linéaire . 1.3.6 Exercices . ... La recherche opérationnelle trouve son origine au début du XXe si`ecle dans l'étude de ...
Processus stochastiques et modélisation (Cours et exercices
Processus stochastiques et modélisation Informations utiles (examens corrigés ...) : ... (d) Ici
GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir
Le but de cet exercice est de rechercher la limite de la suite (an) en utilisant deux méthodes différentes. Première méthode : graphe probabiliste. Pour tout
COURS DINITIATION A LA RECHERCHE OPERATIONNELLE
La modélisation en recherche opérationnelle sert à transformer un Exercice. Une entreprise prépare trois types de boites de fruits :.
Modelisation et resolution de problemes doptimisation combinatoire
11 mai 2005 pour m'avoir enseigné mes premiers cours de Recherche Opérationnelle à l'Institut Supérieur d'Informatique de Modélisation et leurs ...
MODÉLISATION MATHÉMATIQUE EN ÉCOLOGIE
Cours et exercices corrigés Directeur de recherche à l'Institut de Recherche ... d'images et du signal finance
Modèles de Recherche Opérationnelle
Département d'Informatique et de Recherche Opérationnelle 4.5 Exercices . ... Au-delà de la modélisation la résolution de problèmes de recherche ...
[PDF] Examens avec Solutions Recherche opérationnelle
Corrigé de l'examen de la session normale Recherche opérationnelle Semestre 6 Filière Economie et Gestion Ensembles : 2 et 3 M ATMANI Exercice 1
[PDF] - Exercices de TD - 1 Modélisation - LIRMM
Exercice 1 - Piles Une manufacture de piles désire ajouter deux nouveaux produits `a son catalogue : la Everlast III et la Xeros dry-cell
Recherche Opérationnelle: Cours et Exercices Corrigés PDF
Chapitre 1 : Modélisation et Résolution graphique des problèmes d'optimisation · Chapitre 2 : Méthode du Simplexe · Chapitre 3 : Variante du Simplexe: Méthode des
Modélisation méthode graphique et algorithme du Simplexe
Corrigés des exercices 5 page 18 + 4°) de l'exercice 10 page 22 + Exercice 1 Exercices corrigés 1 pdf Recherche Opérationnelle-exercices-ordon
3 séries corrigés Recherche Opérationnelle - Cours fsjes
19 déc 2016 · corrigé recherche pdf Exercices corrigés recherche opérationnelle Serie 1: Traduction des problèmes en langage mathématique
Exercices corrigés recherche opérationnelle par wwwcoursdefsjes
corrigé recherche opérationnelle simplexe pdf exercices corrigés modélisation recherche opérationnelle modélisation exercices corrigés pdf recherche
TD et Exercices Corrigés Recherche Opérationnelle S5 PDF
9 déc 2019 · Ce domaine fait largement appel au raisonnement mathématique (logique probabilités analyse des données) et à la modélisation des processus Il
[PDF] Recherche opérationnelle - LMPA
1 2 Modélisation d'un programme linéaire 1 3 6 Exercices La recherche opérationnelle trouve son origine au début du XXe si`ecle dans l'étude de
[PDF] RECHERCHE OPERATIONNELLE - FORPROS
Faure R Lemaire B Picouleau C Précis de Recherche Opérationnelle Dunod 2009 6e édi- Application numéro 8 : EXERCICES AUTO CORRIGES
Recherche Opérationnelle:
Programmation dynamique, chaînes de Markov, files d"attenteCours de Tronc Commun Scientifique
FICM 2A
Notes de cours et exercices corrigés
Frédéric SUR
sur@loria.fr http://www.loria.fr/sur/enseignement/RO/École des Mines de Nancy
2013-2014
(version du 27 février 2014) blablement des coquilles et erreurs. Merci de bien vouloir me les signaler.Il s"agit d"un résumé très condensé de notions dont l"étude approfondie nécessiterait
bien plus de temps. On essaie ici de donner les éléments simplifiés, mais autant que pos- sible rigoureux, de la théorie qui permettent d"aller au delà de l"application de formules. N"hésitez pas à consulter la littérature dédiée.Table des matières
1 La programmation dynamique 7
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1 Un problème de plus court chemin . . . . . . . . . . . . . . . .
1.1.2 Principe d"optimalité de Bellman . . . . . . . . . . . . . . . .
1.2 L"équation de Bellman . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.1 Un système dynamique . . . . . . . . . . . . . . . . . . . . . .
1.2.2 Équation de Bellman et principe d"optimalité . . . . . . . . . .
1.2.3 Un exemple de recherche de plus courts chemins . . . . . . . .
1.2.4 La résolution d"une équation de Bellman vue comme une re-
cherche de plus courts chemins . . . . . . . . . . . . . . . . . .1.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.1 La distance d"édition . . . . . . . . . . . . . . . . . . . . . . .
1.3.2 Problème de location de skis . . . . . . . . . . . . . . . . . . .
1.3.3 Équilibrage de charge sur deux machines en parallèle . . . . . .
1.3.4 Un problème d"économie mathématique . . . . . . . . . . . . .
1.3.5 Gestion de stock . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.6 Problème du sac à dos . . . . . . . . . . . . . . . . . . . . . .
2 Les chaînes de Markov 19
2.1 Exemple introductif . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Vocabulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Définitions et premières propriétés . . . . . . . . . . . . . . . .
2.2.2 Représentation graphique des chaînes de Markov . . . . . . . .
2.2.3 Chaînes réductibles et irréductibles . . . . . . . . . . . . . . .
2.2.4 Chaînes périodiques et apériodiques . . . . . . . . . . . . . . .
2.3 Comportement asymptotique des chaînes ergodiques . . . . . . . . . .
2.4 Le " théorème » des coupes . . . . . . . . . . . . . . . . . . . . . . . .
2.5 Comportement asymptotique des chaînes absorbantes . . . . . . . . . .
2.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6.1 L"anatomie d"un moteur de recherche (examen 2010-2011) . . .
2.6.2 Modèle économique de Leontief (examen 2011-2012) . . . . .
TABLE DES MATIÈRES 4
2.6.3 Problème de la ruine du joueur (examen 2013-2014) . . . . . .
3 Les files d"attentes 39
3.1 Rappels : loi de Poisson et loi exponentielle . . . . . . . . . . . . . . .
3.2 Caractéristiques d"un système d"attente . . . . . . . . . . . . . . . . .
3.3 La formule de Little . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Processus de Poisson . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.1 Processus de Poisson . . . . . . . . . . . . . . . . . . . . . . .
3.5 Modélisation dans le cadre Markovien . . . . . . . . . . . . . . . . . .
3.5.1 La propriété PASTA . . . . . . . . . . . . . . . . . . . . . . .
3.5.2 Les clients et les serveurs sont sans mémoire . . . . . . . . . .
3.5.3 Les files d"attente M/M/1 . . . . . . . . . . . . . . . . . . . . .
3.5.4 Processus de naissance et de mort . . . . . . . . . . . . . . . .
3.6 Formulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6.1 File M/M/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6.2 File M/M/1/K . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6.3 File M/M/m . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6.4 File M/M/m/m . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7 Les files M/G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7.1 Processus de Markov par lot . . . . . . . . . . . . . . . . . . .
3.7.2 File M/G/1 générale . . . . . . . . . . . . . . . . . . . . . . .
3.8 Réseaux de files d"attente . . . . . . . . . . . . . . . . . . . . . . . . .
3.9 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.9.1 Paradoxe de l"autobus . . . . . . . . . . . . . . . . . . . . . .
3.9.2 Dimensionnement d"un service-client . . . . . . . . . . . . . .
3.9.3 Vélos en libre service (rattrapage 2010-2011) . . . . . . . . . .
3.9.4 Chez le médecin (examen 2010-2011) . . . . . . . . . . . . . .
3.9.5 Un serveur informatique (rattrapage 2011-2012) . . . . . . . .
3.9.6 Problème de maintenance informatique (examen 2010-2011) . .
3.9.7 Étude d"une file M/G/1 (examen 2010-2011) . . . . . . . . . .
3.9.8 Maintenanced"unsystèmeindustrielcritique(examen2011-2012)
3.9.9 Approvisionnement et gestion d"un stock (examen 2013-2014) .
3.9.10 Un guichet avec des clients prioritaires (rattrapage 2013-2014) .
4 Correction des exercices 75
4.1 La programmation dynamique . . . . . . . . . . . . . . . . . . . . . .
4.1.1 La distance d"édition . . . . . . . . . . . . . . . . . . . . . . .
4.1.2 Problème de location de skis . . . . . . . . . . . . . . . . . . .
4.1.3 Équilibrage de charge sur deux machines en parallèle . . . . . .
4.1.4 Un problème d"économie mathématique . . . . . . . . . . . . .
4.1.5 Gestion de stock . . . . . . . . . . . . . . . . . . . . . . . . .
F. Sur 2013-2014
5 TABLE DES MATIÈRES
4.1.6 Problème du sac à dos . . . . . . . . . . . . . . . . . . . . . .
4.2 Les chaînes de Markov . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1 L"anatomie d"un moteur de recherche . . . . . . . . . . . . . .
4.2.2 Modèle économique de Leontief . . . . . . . . . . . . . . . . .
4.2.3 Problème de la ruine du joueur . . . . . . . . . . . . . . . . . .
4.3 Les files d"attente . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.1 Paradoxe de l"autobus . . . . . . . . . . . . . . . . . . . . . .
4.3.2 Dimensionnement d"un service-client . . . . . . . . . . . . . .
4.3.3 Vélos en libre service . . . . . . . . . . . . . . . . . . . . . . .
4.3.4 Chez le médecin . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.5 Un serveur informatique . . . . . . . . . . . . . . . . . . . . .
4.3.6 Problème de maintenance informatique . . . . . . . . . . . . .
4.3.7 Étude d"une file M/G/1 . . . . . . . . . . . . . . . . . . . . . .
4.3.8 Maintenance d"un système industriel critique . . . . . . . . . .
1004.3.9 Approvisionnement et gestion d"un stock . . . . . . . . . . . .
1034.3.10 Un guichet avec des clients prioritaires . . . . . . . . . . . . .
104Recherche Opérationnelle
TABLE DES MATIÈRES 6
F. Sur 2013-2014
Chapitre 1
La programmation dynamique
1.1 Introduction
1.1.1 Un problème de plus court chemin
On considère le problème du plus court chemin dans un graphe orienté et valué, défini sur un ensemble densommetsf1;2;:::ng. Si les valuations sont positives, l"al- gorithme de Dijkstra permet de trouver le plus court chemin (i.e. le chemin de valuation totale minimale) entre deux sommets. Dans le cas où les valuations peuvent être négatives et où le graphe ne présente pas de circuit de valuation totale négative, nous allons présenter l"algorithme de Floyd-Warshall qui répond à la question.
Notonsd(i;j)la valuation de l"arc(i;j), et (pourk>1)dki;jla longueur du plus court chemin du sommetiau sommetjparmi ceux parcourant uniquement les som- metsf1;2;:::kg. Par convention on suppose aussi : dki;j= +1s"il n"y a pas de chemin deiàj0i;j=d(i;j)
Le but est de construire un algorithme permettant de calculer lesdni;j.On remarque la propriété suivante.
Proposition 1.1Soitktel que06k6n1. Les(dk+1
i;j)i;jsont liés aux(dki;j)i;jpar la formule de récursion :8(i;j)2 f1;2;:::ng2; dk+1
i;j= mindki;j; dki;k+1+dkk+1;j Démonstration.En effet, si on considère deux sommetsietj: s oitle plus court chemin entre ietjparmi ceux visitantf1;:::;k+ 1gne passe pas par le sommetk+ 1, et alorsdk+1i;j=dki;j;7CHAPITRE 1. LA PROGRAMMATION DYNAMIQUE 8
soit ce plus court chemin passe par le sommet k+ 1. Dans ce cas il ne peut y passer qu"une seule fois (sinon il y a un circuit, de valuation totale positive par hypothèse sur le graphe, que l"on pourrait éliminer pour construire un chemin entreietjplus court, ce qui serait absurde). Ce plus court chemin est donc la concaténation du plus court chemin entreietk+ 1et du plus court chemin entrek+ 1etj, parmi ceux visitant les sommets intermédiairesf1;:::;kguniquement. On a alors :dk+1i;j=dki;k+1+dkk+1;j. L"algorithme de Floyd-Warshall (-Roy) (1962) consiste à calculer les(d1i;j)i;j(en O(n2)opérations, car il y an2paires de sommets(i;j)), puis les(d2i;j)i;j(O(n2) opérations), ..., et finalement les(dni;j)i;j(toujoursO(n2)opérations) qui donnent les longueurs de plus courts chemines cherchées. La complexité totale de l"algorithme est deO(n3).1.1.2 Principe d"optimalité de Bellman
Dans le problème précédent, pour trouver les chemins minimaux sur le graphe, on a résolu des problèmes " plus petits » : trouver les chemins minimaux sur des graphes à k < nsommets. Cette astuce est possible lorsque le problème d"optimisation vérifie le principe d"optimalité de Bellman: une solution optimale pour le problème contient les solutions optimales pour tous les sous-problèmes. Ici, le plus court chemin entre les sommetsietjest la concaténation, pour tout sommet intermédiaireksur ce chemin, du plus court chemin entreietket du plus court chemin entreketj. Laprogrammation dynamiqueconsiste à résoudre les problèmes d"optimisation sat- isfaisant le principe d"optimalité de Bellman en tirant partie d"une formule récursive. L"algorithme de Floyd-Warshall est donc de ce point de vue basé sur la programmation dynamique.1.2 L"équation de Bellman
Il se trouve qu"une classe générale de problèmes d"optimisation satisfait le principe d"optimalité de Bellman. Il s"agit de problèmes dont la fonctionnelle satisfait l"équation de Bellman.1.2.1 Un système dynamique
dont l"état à l"instantt(06t6T) est repéré parxt(valeur scalaire ou vecteur deRd).F. Sur 2013-2014
9 1.2. L"ÉQUATION DE BELLMAN
Soit(xt)l"ensemble des actions possibles lorsque le système est dans l"étatxt. Si l"actionat2(xt)est choisie, le système passe à l"étatxt+1=(xt;at). Notons égalementF(xt;at)le coût de l"actionatlorsque le système est dans l"é- tatxt. Partant de l"état initialx0, le coût global aprèsTpas de temps est alors : t=0F(xt;at) Minimiser le profit global revient à résoudre l"équation de Bellman : min0;:::;aT(
t=0F(xt;at);t.q.806t6T; at2(xt)et806t < T; xt+1=(xt;at)) NotonsPT(x)la valeur du coût minimal obtenu en arrivant à l"étatxaprèsTétapes, par-tant de l"étatx0. L"équation précédente donne la valeur dePT(xT+1)(après la dernière
décisionaTle système arrive à l"étatxT+1auquel aucun coût n"est associé). Résoudre l"équation de Bellman consiste à choisir les actionsatguidant le système à chaque pas de temps parmi celles possibles de manière à minimiser le coût global.1.2.2 Équation de Bellman et principe d"optimalité
Ce problème de minimisation peut aussi s"écrire pour tout état finalx:T(x) = mina2(y)t.q.x=(y;a)fPT1(y) +F(y;a)g
oùPT1(y)désigne le coût minimal réalisable enT1étapes menant à l"étaty. Autrement dit, l"équation de Bellman satisfait le principe d"optimalité de Bellman. La stratégie optimale enTétapes arrivant enxà l"instantTet passant paryà l"in- stantT1contient la stratégie optimale arrivant enyenT1étapes. On peut donc utiliser la programmation dynamique pour résoudre ce problème Pour ce faire, on suppose connaître lesP0(x)pour toutes les valeurs dexpossibles.On calcule alors pour tous lesxpossibles :
1(x) = mina2(y)t.q.x=(y;a)fP0(y) +F(y;a)g
(cette optimisation n"est pas forcément évidente en pratique, si par exemple(y)n"est qui sont les valeurs qui nous intéressent. La succession des choixa0;a1;:::;aTdonnela stratégie optimale.1. Il semble que certains auteurs réservent l"appellation " programmation dynamique » à la résolution
quotesdbs_dbs7.pdfusesText_5[PDF] formulation variationnelle exercices corrigés pdf
[PDF] pecheur d'islande film
[PDF] madame chrysanthème
[PDF] pecheur d'islande film 1996
[PDF] ramuntcho
[PDF] aziyadé
[PDF] cours modélisation et simulation des systèmes pdf
[PDF] différence entre modélisation et simulation
[PDF] modélisation et simulation cours
[PDF] modélisation et simulation cours informatique
[PDF] modélisation et simulation pdf
[PDF] pierre et jean résumé court
[PDF] pierre et jean personnages
[PDF] fonction affine activité
