[PDF] [PDF] Cours de Recherche Opérationnelle IUT dOrsay Nicolas M THIÉRY

[PDF] Recherche opérationnelle et applications

2 Tour d'horizon des techniques de recherche opérationnelle 4 II Applications de la Moindre efficacité (actuellement) des solveurs gratuits 25 Exemples de problèmes “faciles” : programmation linéaire, affectation, plus courts chemins,

[PDF] Introduction `a la Recherche Opérationnelle

Recherche opérationnelle : comment organiser les operations (activités) Nous commençons ce cours par optimisation (programmation) linéaire (OL) – RMosek – l'interface R du moteur Mosek (logiciel commercial, disponible gratuitement

[PDF] cours recherche opperattionnelle - FPL

A U : 2017-2018 Cours de Programmation linéaire et Recherche Opérationnelle —E Pour pouvoir les éliminer en cours d'algorithme, ˜E Aboutir à une 

[PDF] COURS DE RECHERCHE OPERATIONNELLE - UFR SEG

U des Sciences Economues et de Gestion COURS DE RECHERCHE OPERATIONNELLE ECUE 1 : PROGRAMMATION LINEAIRE NOTES DE COURS PAR

[PDF] Cours de recherche opérationnelle I - Laboratoire G-SCOP

Ont participé `a la rédaction de ce cours (par ordre d'arrivée) Nadia Brauner Recherche Opérationnelle : approche scientifique pour la résolution de probl` emes Swedish ( pdf ) Press Release + outils pour le debuggage et aide en ligne 

[PDF] INTRODUCTION À LA RECHERCHE OPÉRATIONNELLE - Educnet

Ressources en ligne La recherche opérationnelle (RO) est la discipline des mathématiques appliquées qui traite des questions d'utilisation optimale des L' objectif de ce cours est de donner les bases de recherche opérationnelle :

[PDF] Cours de Recherche Opérationnelle IUT dOrsay Nicolas M THIÉRY

`A chaque solution elle associe une valeur Une solution est optimale si elle est faisable et maximize la fonction objective Exercice 1 Peut-on mettre sous forme  

[PDF] Modèles de Recherche Opérationnelle - Département d

Département d'Informatique et de Recherche Opérationnelle Université de visiter les campus de trois universités du Maine au cours d'un voyage unique, débutant et finissant à l'aéroport de Portland Une version gratuite de démonstra-

[PDF] Recherche opérationnelle - LMPA

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

[PDF] Programmation linéaire et recherche opérationnelle Recherche

Pourquoi un cours sur la programmation linéaire? Objectif : apprendre `a modéliser les probl`emes réels et `a résoudre les programmes linéaires

[PDF] programmation linéaire exercices corrigés simplex

[PDF] examen recherche opérationnelle corrigé

[PDF] exercice corrigé methode simplexe pdf

[PDF] multiples et sous multiples physique

[PDF] multiples et sous multiples physique exercices

[PDF] multiples et sous multiples du gramme

[PDF] multiple et sous multiple exercice

[PDF] multiples et sous multiples du litre

[PDF] multiplicateur fiscal formule

[PDF] multiplicateur fiscal macroéconomie

[PDF] cobb douglas explication

[PDF] revenu d'équilibre formule

[PDF] multiplicateur des dépenses publiques macroéconomie

[PDF] fonction de cobb douglas pdf

[PDF] revenu d'équilibre et revenu de plein emploi

Cours de Recherche Op´erationnelle

IUT d"Orsay

Nicolas M. THI

´ERY

E-mail address:Nicolas.Thiery@u-psud.fr

URL:http://Nicolas.Thiery.name/

CHAPTER 1

Introduction `a l"optimisation

1.1. TD: Ordonnancement par la m´ethode des potentiels

Exercice.On veut construire une maison, ce qui consiste en 9 tˆaches, le plus rapidement possible, avec les contraintes suivantes: •Certaines tˆaches d´ependent d"autres tˆaches •Toutes les tˆaches demandent une semaine de travail. •Chaque ouvrier ne peut travailler que sur une tˆache par jour •Il n"y a pas de gain de temps si plusieurs ouvriers travaillent sur la mˆeme tˆacheF: fondations

M: murs

E: électricitéT: toit

I: peinture intrieure

X: peinture extrieureP: plomberieT: fenêtres

N: nains de jardinExemple.Organisez un emploi du temps pour un ouvrier, de fa¸con `a construire la maison le plus rapidement.semaine 1semaine 2semaine 3semaine 4semaine 5semaine 6semaine 7 ouvrier 1

De mˆeme, s"il y a deux ouvriers:

semaine 1semaine 2semaine 3semaine 4semaine 5semaine 6semaine 7 ouvrier 1 ouvrier 2

De mˆeme, s"il y a trois ouvriers:

3

4 1. INTRODUCTION

`A L"OPTIMISATIONsemaine 1semaine 2semaine 3semaine 4semaine 5semaine 6semaine7 ouvrier 1 ouvrier 2 ouvrier 3

Et s"il y a plus d"ouvriers ?

G´en´eralisation avec des dur´ees.

1.2. Probl`emes d"optimisation

Problem1.2.1.Quelles sont les coordonn´ees du point culminant du massif de la

Chartreuse?

Mod´elisation:

D ´efinition1.2.2.Unprobl`eme d"optimisationest d´ecrit par: •UndomaineS Ici,Sest l"ensemble des pointspde la surface de la terre, d´ecrits par leur coordonn´ees (longitude, latitude).

Un ´el´ement deSest appell´esolution.

•Des contraintesCd´efinissant un sous-ensemble deS.

Ici,C(p) :=pest dans le massif de la Chartreuse.

Une solutionpv´erifiant les contraintesC(p) est ditesolution faisable. •Unefonction objectif:z:S?→R Ici la fonctionp?→z(p) qui associe `a un pointpde la surface de la terre sont altitudez(p). Il faut de plus pr´eciser s"il s"agit d"un probl`eme demaximisationou deminimisation.

1.2. PROBL

`EMES D"OPTIMISATION 5 Une solution faisablepest diteoptimalesiz(p)≥z(q) pour toute autre solution faisableq. But: d´eterminer l"ensemble des solutions optimales. Exemple1.2.3.Mod´eliser les probl`emes suivants, puis les r´esoudre ou proposer des m´ethodes de r´esolution: (1) Calcul du plus court chemin dans un graphe. (2) Recherche d"un ordonnancement optimal pour ... (3) D´eterminer le plus petits nombre de cartons n´ecessaires pour un d´em´e- nagement. (4) Chercher un mat en un minimum de coup (5) Recherche de l"´el´ement maximal d"un tableau denvaleurs al´eatoires. (6) Maximiserzpourzdans [0,1[. (7) MaximiserzpourzdansR+. (8) D´eterminer la valeur minimale de la fonctionx2+ 2x-4. plotfunc2d(x^2 + 2*x - 4) (9) D´eterminer la valeur minimale de la fonction 2x3-5x2-x+ 7. plotfunc2d(2*x^3 - 5*x - x + 7) (10) D´eterminer la valeur maximale de la fonction sin(x)sin(πx+2)+0.01x2. plotfunc2d(sin(x) * sin(PI*x+2)-0.01*x^2,x=-20..20) (11) Quelle est la profondeur maximale de l"oc´ean?

Bilan: un probl`eme d"optimisation peut avoir

•Aucune solution •Aucune solution optimale (non born´e) •Une unique solution optimale

Quelques m´ethodes d"optimisation:

(1) M´ethodes globales: •Monte-Carlo •Recherche exhaustive (toujours possible pour un probl`eme discret fini; parfois la seule m´ethode existante) •Recherche exhaustive structur´ee, avec coupures de branches. (2) M´ethodes locales, it´eratives: Lorsque le probl`eme a une propri´et´e deconvexit´e, l"optimisation locale am`ene `a une optimisation globale! •Algorithmes gloutons •M´ethodes analytiques (gradient) •M´ethode du simplexe (3) M´ethodes mixtes: •Monte-Carlo + gradient •Recuit simul´e, ...

CHAPTER 2

Programmation lin´eaire

2.1. Rappel d"alg`ebre lin´eaire

Problem2.1.1.Consid´erons le syst`eme suivant:

5 = s1 + 2*x1 + 3*x2 + x3

11 = s2 + 4*x1 + x2 + 2*x3

8 = s3 + 3*x1 + 4*x2 + 2*x3

Que peut-on dire dessus?

C"est un syst`emelin´eaire`a 6 inconnues et 3 ´equations. On peut d´ecrire l"ensemble des solutions en prenant comme param`etresx1,x2et x3. En effet, vu sa forme triangulaire, s1, s2 et s3 s"expriment en fonction dex1,x2et x3. Transformer le syst`eme pour prendre comme param`etress1,s2, etx1.

2.2. Qu"est-ce que la programmation lin´eaire

2.2.1. Exemple: le probl`eme du r´egime de Polly[1, p.3].

•Besoins journaliers:´Energie:2000 kcal

Prot´eines:55g

Calcium:800 mg

•Nourriture disponiblePortion´ Energie (kcal)Prot´eines (g)Calcium (mg)Prix/portion

C´er´eales28g110423

Poulet100g205321224

Oeufs2 gros160135413

Lait entier237cc16082859

Tarte170g42042220

Porc et haricots260g260148019

•Contraintes:

C´er´eales:au plus 4 portions par jour

Poulet:au plus 3 portions par jour

Oeufs:au plus 2 portions par jour

Lait:au plus 8 portions par jour

Tarte:au plus 2 portions par jour

Porc et haricots:au plus 2 portions par jour

7

8 2. PROGRAMMATION LIN

´EAIRE

Problem2.2.1.Polly peut-elle trouver une solution ? Comment formaliser le probl`eme ? (mod´elisation) Qu"est-ce qui fait la sp´ecificit´e du probl`eme ? Savez-vous r´esoudre des probl`emes similaires ?

2.2.2. Forme standard d"un probl`eme de programmation lin´eaire.

Problem2.2.2.[1, p. 5]

Maximiser: 5*x1 + 4*x2 + 3*x3

Sous les contraintes: 2*x1 + 3*x2 + x3 <= 5

4*x1 + x2 + 2*x3 <= 11

3*x1 + 4*x2 + 2*x3 <= 8

x1, x2, x3 >= 0

Minimiser: 3*x1 - x2

Sous les contraintes: - x1 + 6*x2 - x3 + x4 >= -

3

7*x2 + 2*x4 = 5

x1 + x2 + x3 = 1 x3 + x4 <= 2 x2, x3 >= 0 D ´efinition.Probl`eme de programmation lin´eaire sousforme standard:

Maximiser:

z:=n? j=1c jxj

Sous les contraintes:

nquotesdbs_dbs4.pdfusesText_7