Recherche Opérationnelle: PDF Recherche Opérationnelle: Programmation dynamique

Recherche opérationnelle

On admettra que ces résultats se généralisent `a un programme linéaire `a n variables. 1.3.6 Exercices. §. ¦. ¤. ¥. Exercice 1.

Cahier dexercices corrigés Eric LALLET Jean-Luc RAFFY

1.5 Programmation linéaire : la méthode géométrique . D'ailleurs pour toutes ces recherches et tout l'aspect logistique

1 Programmation linéaire

Document 4 : Corrigé des exercices d'optimisation linéaire On introduit 3 variables positives x1a

Exercice corrigé de recherche opérationnelle pdf

operationnelle exercices corriges pdf.recherche operationnelle programmation lineaire.exercice corrige methode simplexe pdf.recherche opérationnelle ...

RÉSOLUTION DE SYSTÈMES À DEUX INCONNUES

les cours de programmation linéaire et de recherche opérationnelle. Solution d'un système d'équations. Soit le système d'équations linéaires.

Programmation Linéaire en nombres entiers MOD 4.4: Recherche

Exercice: Vérifiez que probl`eme est celui du transversal minimum ! 20/23. Page 45. Dual d'un PL en nombre entier.

Untitled

1) Citer trois exemples d'application de la recherche opérationnelle. 2) Définir la programmation linéaire. 3) Formuler le programme linéaire correspondant au

1 Programmation Linéaire 2006·2007

Trouvez une solution optimale. (*) Exercice 4.2 Soit le programme linéaire `a résoudre par l'algorithme du simplexe. : ?. ???.

Programmation Linéaire Cours 1 : programmes linéaires

C. Prins et M. Sevaux - Programmation linéaire avec Excel : 55 probl`emes d'optimisation modélisés pas `a Le fabricant cherche `a maximiser son profit.

Recherche Opérationnelle:

Recherche Opérationnelle: Programmation dynamique chaînes de Markov

Introduction Au Cours Recherche Opérationnelle
La programmation linéaire est l’une des plus importantes techniques d’optimisation utilisées en recherche opérationnelle. Ceci est dû à la facilité de la modélisation, à l’efficacité des algorithmes développés et à l’existence sur le marché de nombreux logiciels. La généralisation de micro-informatique a mis la programmation linéaire à la portée de...
Exercices Corrigés Recherche Opérationnelle Pdf
Pour télécharger les QCM, exercices et examens de Recherche Opérationnelle, Cliquez sur le lien ci-dessous.

Quels sont les problèmes de la recherche opérationnelle ?

Par exemple, les problèmes d’ordonnancement et de circulation, les problèmes de gestion des stocks et des files d’attente, ou encore ceux que posent la théorie des jeux et la théorie des chaînes de Markov. Ce livre présente de manière claire et concise les principaux aspects de la Recherche opérationnelle.

Quel est l'objectif de la programmation linéaire ?

L'objectif de la programmation linéaire (P.L.) est de trouver la valeur optimale d'une fonction linéaire sous un système d'équations d'inégalités de contraintes linéaires.

Qu'est-ce que la programmation lin'eaire?

Introduction a la programmation lin´eaire Un outil qui permet de : •mod´eliser •r´esoudre toute une classe de probl`emes d’optimisation. Existence de solveurs e?cace pour la PL

Comment mettre en oeuvre un algorithme de programmation linéaire ?

Pour mettre en oeuvre cet algorithme, nous devons poser le problème sous une forme "standard" et introduire la notion de "programme de base" qui est l'expression algébrique correspondant à la notion de "point extrême du polyèdre des programmes admissibles" étudiée lors de la programmation linéaire (noté ci-après P.L.).

Recherche Opérationnelle:

Programmation dynamique, chaînes de Markov, files d"attente

Cours 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 . . . . . . . . . . . . . . . . . . 10

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) . . . . .

36
3

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 . . . . . . . . . .

100

4.3.9 Approvisionnement et gestion d"un stock . . . . . . . . . . . .

103

4.3.10 Un guichet avec des clients prioritaires . . . . . . . . . . . . .

104

Recherche 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àj d

0i;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;7

CHAPITRE 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 X t=0F(xt;at) Minimiser le profit global revient à résoudre l"équation de Bellman : min a

0;:::;aT(

TX 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èmequotesdbs_dbs13.pdfusesText_19

[PDF] exercices recherche operationnelle

[PDF] theme astral chinois complet gratuit interpretation

[PDF] cours recherche opérationnelle methode de simplexe

[PDF] recherche opérationnelle simplexe exercices corrigés

[PDF] livre recherche opérationnelle pdf

[PDF] cours et exercices corrigés de recherche opérationnelle+pdf

[PDF] inpes

[PDF] methode boscher pdf download

[PDF] méthode boscher cahier de lecture pdf

[PDF] methode boscher en ligne

[PDF] méthode boscher gratuit

[PDF] méthode boscher cahier des sons pdf

[PDF] adjectif pour acrostiche

[PDF] recherche qualitative définition

[PDF] méthode qualitative et quantitative

[PDF] Recherche Opérationnelle: Recherche Opérationnelle: Programmation dynamique

Introduction Au Cours Recherche Opérationnelle

Exercices Corrigés Recherche Opérationnelle Pdf

Quels sont les problèmes de la recherche opérationnelle ?

Quel est l'objectif de la programmation linéaire ?

Qu'est-ce que la programmation lin'eaire?

Comment mettre en oeuvre un algorithme de programmation linéaire ?

Recherche Opérationnelle:

Cours de Tronc Commun Scientifique

FICM 2A

Notes de cours et exercices corrigés

Frédéric SUR

École des Mines de Nancy

2013-2014

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-

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 . . . . . . . . . . . . . . . . . . . . . . .