[PDF] Programmation Linéaire - Recherche Opérationnelle
Programmation linéaire Formulation du probl`eme Méthode et interprétation graphique Algorithme du simplexe Détail de l'algorithme
[PDF] Modèles de Recherche Opérationnelle
MODÈLE GÉNÉRAL DE PROGRAMMATION LINÉAIRE 9 En résumé nous avons le problème d'optimisation suivant: max x z = 3x1 + 5x2 sous les contraintes
[PDF] Graphes et Recherche Opérationnelle - Jean-François SCHEID
expose l'algorithme du simplexe pour résoudre un programme linéaire En optimisation et plus généralement en Recherche Opérationnelle modéliser un
[PDF] programmes linéaires modélisation et résolution graphique
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
[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 Dr Yao Silvère KONAN
[PDF] LES ÉTAPES DE LALGORITHME DU SIMPLEXE
Un programme linéaire (PL) mis sous la forme particulière où toutes les contraintes sont des équations et toutes les variables sont non négatives est dit sous
[PDF] Recherche Opérationnelle 1A Programmation Linéaire Mod`eles
Recherche Opérationnelle 1A Programmation Linéaire Mod`eles classiques Zoltán Szigeti Laboratoire G-SCOP INP Grenoble France Z Szigeti (G-SCOP
Recherche opérationnelle et applications
2 Tour d’horizon des techniques de recherche opérationnelle Recherche opérationnelle La recherche opérationnelle est une technique d’aide à la décision Etapes pratiques 1 Dé?nition du problème 2 Construction d’un modèle 3 Solution du modèle 4 Validation du modèle 5 Implémentation de la solution Méthodologie
Searches related to programmation linéaire recherche opérationnelle PDF
La programmation linéaire est un outil très puissant de la recherche opérationnelle C’est un outil générique qui peut résoudre un grand nombre de problèmes
Quels sont les principes de la recherche opérationnelle ?
Dans les années 70-80, on applique même les principes de la recherche opérationnelle à la compréhension des phénomènes de trou noir. Aujourd’hui, elle représente une première approche des problèmes techniques et est devenue un outil d’aide à la décision. L’algorithme du simplexe est la méthode la plus utilisée en recherche opérationnelle.
Comment faire une recherche opérationnelle?
La recherche opérationnelle porte sur la gestion pratique de l’organisation. De ce fait, elle doit fournir des conclusions positives et compréhensibles aux décideurs lorsque cela est nécessaire pour la prise de décision. Elle nécessite de ce fait une approche pluridisciplinaire
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.
Qui a inventé la recherche opérationnelle?
La Recherche Opérationnelle 5 Commençons par citer Robert FAURE qui a été un des principaux initiateurs de la R.O. en France... a) Le caractère pratique de la Recherche Opérationnelle : Définition
![Recherche opérationnelle et applications Recherche opérationnelle et applications](https://pdfprof.com/Listes/18/5652-18Rechercheop__rationnelle.pdf.pdf.jpg)
Recherche opérationnelle et applications
Bernard Fortz
2012-2013
Table des matières
I Introduction à la recherche opérationnelle 31 Quelques exemples de modèles mathématiques 3
2 Tour d"horizon des techniques de recherche opérationnelle 4
II Applications de la programmation linéaire 6
3 Définition, exemples et méthode de résolution 6
3.1 Notions de bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63.2 Exemples de modèles linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63.3 Forme standard et forme canonique d"un programme linéaire . . . . . . . . . . . . . . . . . . . .
83.4 Résolution de programmes linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
103.4.1 Résolution graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
103.4.2 La méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
123.4.3 La méthode des deux phases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
163.4.4 Cas particuliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
174 Dualité19
4.1 Le problème dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
194.2 Relations primal/dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
204.3 Interprétation économique de la dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
215 Solveurs et langages de modélisation 23
III Programmation en nombres entiers et optimisation combinatoire 276 Définitions et exemples27
7 Complexité des problèmes et efficacité des algorithmes 30
8 Problèmes polynomiaux 31
8.1 Le problème d"affectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
318.2 Modèle de transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
329 Méthodes de Branch-and-Bound 39
9.1 Branch-and-Bound pour les problèmes en nombres entiers . . . . . . . . . . . . . . . . . . . . .
399.2 Branch-and-bound pour le voyageur de commerce . . . . . . . . . . . . . . . . . . . . . . . . . .
419.3 Branch-and-bound pour les contraintes disjonctives . . . . . . . . . . . . . . . . . . . . . . . . .
421
10 Méthodes heuristiques47
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4710.2 Heuristiques de construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4710.3 Recherche locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4910.4 Méta-heuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5010.5 Algorithmes génétiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52Références
Hamdy A. T aha,OperationsResearch,anintroduction, Prentice-HallMarc Pirlot, Métaheuristiquespourl"optimisationcombinatoire:unaperçugénéral, Chapitre 1, dans "Opti-
misation approchée en recherche opérationnelle", sous la direction de Jacques Teghem et Marc Pirlot, Hermes
Science.
2Première partie
Introduction à la recherche opérationnelle
1 Quelques exemples de modèles mathématiques
Un premier problème
Exemple1 (Achat de billets d"avion).
Un homme d"af fairesdoit ef fectuer5 v oyagesentre F ayetteville(FYV) à Den ver(DEN), en partant le lundi de
FYV et revenant le mercredi de DEN à FYV.
Billet aller -retour: $400.
Réduction de 20 % si un week endest inclus.
Aller simple : 75 % du prix aller -retour.
Question
Comment acheter les billets pour les 5 semaines (à prix minimum)?Aide à la décision
Problème d"aide à la décision
1.Quelles sont les alternati vespossibles ?
2. Quelles sont les restrictions à cette décision ? 3. Quel est l"objectif utilisé pour év aluerles alternati ves?Restrictions
FYV-DEN le lundi et DEN-FYV le mercredi de la même semaine.Evaluation des alternatives
Alternatives
Acheter 5 FYV -DEN-FYVnormaux. 5 x $400 = $2000
Acheter un FYV -DEN,4 DEN-FYV -DENcomprenant un week endet un DEN-FYV .0.75 x $400 + 4 x 0.8 x $400 + 0.75 x $400 = $1880Acheter un FYV -DEN-FYVpour le lundi de la première semaine et le mercredi de la dernière semaine, et 4
DEN-FYV-DEN comprenant un weekend pour les autres voyages.5 x 0.8 x400 =1600La troisième alternative est la meilleure.
Modèle de recherche opérationnelle
Ingrédients principaux
-Alternatives(variables, inconnues du problème). -Restrictions(contraintes). -Fonction objectifà optimiser (minimiser ou maximiser).Définition1 (Solution admissible).Unesolution admissibleest un ensemble de valeurs données aux variables qui
satisfait toutes les contraintes.Définition2 (Solution optimale).Unesolution optimaleest une solution admissible qui optimise la fonction
objectif. Variables :continues (réelles), entières, booléennes (0/1), ... Objectif :linéaire / non-linéaire, concave / convexe, ... 3Contraintes :linéaire / non-linéaire, concave / convexe, égalités / inégalités, ...
Paramètres :connus avec certitude (modèles déterministes) / incertains (modèles stochastiques)
Exemple2 (Maximisation de la surface d"un rectangle).Supposons que l"on veut plier un fil de fer de longueurL
en rectangle de manière à maximiser la surface du rectangle.l wFormulation maxA=lw s.t.l+w=L2Solution
-A=L2 ww=Lw2 w2 dAdw =L2 2w= 0Solution optimale : w=l=L4
Méthodes de résolution
Dans l"e xemple,solution analytiqueau problème.La plupart des problèmes pratiques sont trop grands ou trop comple xespour être résolus analytiquement.
Méthodes itératives
Déplacement de solution en solution pour atteindre l"optimum (méthodes exactes) ou une "bonne" solution
(heuristiques). Importance des algorithmes et des solutions informatiques.2 Tour d"horizon des techniques de recherche opérationnelle
Recherche opérationnelle
La recherche opérationnelle est une technique d"aide à la décision.Etapes pratiques
1.Définition du problème
2.Construction d"un modèle
3.Solution du modèle
4.V alidationdu modèle
5.Implémentation de la solution
Méthodologie
Les étapes les plus importantes sont la définition du problème (suppose un dialogueavec le décideur) et la
construction du modèle (prendre conscience deshypothèses simplificatriceset de leur impact). La phase de v alidationdoit permettre de remettre en cause la validité du modèle.Une approche globale nécessite donc un aller -retourconstant entre le modèle et les attentes du décideur .
Techniques principales
Programmation linéaire
Programmation en nombres entiers
Optimisation dans les réseaux
4 -Programmation non linéaire "Optimisation" multi-critèresProgrammation dynamique
Modèles stochastiques
Simulation
5Deuxième partie
Applications de la programmation linéaire
3 Définition, exemples et méthode de résolution
3.1 Notions de bases
Programmation linéaire
Définition4 (Programme linéaire).Modèle mathématique dans lequel la fonction objectif et les contraintes sont
linéaires en les variables.Applications
Optimisation de l"usage de ressources limitées dans les domaines militaire, industriel, agricole, économique, ...
Existence d"algorithmes très efficaces pour résoudre des problèmes de très grande taille (simplexe, points inté-
rieurs)3.2 Exemples de modèles linéaires
Exemple3 (Production de peinture).Une société produit de la peinture d"intérieur et d"extérieur à partir de deux
produits de base M1 et M2.Données
Quantité utilisée
par tonneQuantité disponible par jourExtérieure IntérieureM1 6 4 24
M2 1 2 6Profit par tonne 5 4
Contraintes supplémentaires
Demande maximum en peinture d"intérieur : 2 tonnes / jour . La production en peinture d"intérieur ne dépasser que d"une tonne celle d"e xtérieur.Formulation (Production de peinture)
Alternatives (variables, inconnues du problème) x1=tonnes de peinture d"extérieur
produites par jour x2=tonnes de peinture
d"intérieur produites par jourFonction objectifà optimiser
maxz= 5x1+ 4x2Restrictions (contraintes)
66x1+ 4x224
x1+ 2x26
x 22x 2x11 x 1;x20
Solutions et méthodes de résolution
-Solution admissible :satisfait toutes les contraintes. x1= 3; x2= 1 ()z= 19)
Nous v oulonstrouv erla solution (admissible) optimale.Infinité de solutions admissibles !
Méthodes pour trouver l"optimum
Méthode graphique
Simple xe
( Ellipsoide, points intérieurs )Exemple4 (Diet problem).-On désire déterminer la composition, à coût minimal, d"un aliment pour bétail qui
est obtenu en mélangeant au plus trois produits bruts : orge et arachide. La quantité nécessaire par portion est de 400g. L "alimentainsi f abriquéde vracomporter au moins 30% de protéines et au plus 5% de fibres.Données
Quantité par gramme d"aliment Coût
Aliment Protéines Fibres (EUR / kg)Orge 0.09 0.02 1.5Arachide 0.60 0.06 4.5
Formulation (Diet problem)
Variables
x1=grammes d"orge par portion
x2=grammes d"arachide par portion
Objectif
minz= 0:0015x1+ 0:0045x2Contraintes
Quantité totale :x1+x2400
Protéines :0:09x1+ 0:6x20:3(x1+x2)
Fibres :0:02x1+ 0:06x20:05(x1+x2)
Non-négativité :x1;x20
73.3 Forme standard et forme canonique d"un programme linéaire
Forme standard
Définition5 (Forme standard).Un programme linéaire est sousforme standardlorsque toutes ses contraintes sont
deségalitéset toutes ses variables sont non-négatives.Représentation matricielle
maxcTx s.c.Ax=b x0 nvariables,mcontraintes,m < n,c;x2Rn; b2Rm; A2Rmn.Forme canonique
Définition6 (Forme canonique).Un programme linéaire est sousforme canoniquelorsque toutes ses contraintes
sont desinégalitéset toutes ses variables sont non-négatives.Représentation matricielle
maxcTx s.t.Axb x0 nvariables,mcontraintes,c;x2Rn; b2Rm; A2Rmn.Théorème1 (Equivalence des formes standard et canonique).Tout programme linéaire peut s"écrire sous forme
standard et sous forme canonique.Démonstration.
Une containte d"inég alitéaTxbpeut être transformée en égalité par l"introduction d"unevariable d"écart:
aTx+s=b;
s0: Une contrainte d"ég alitéaTx=bpeut être remplacée par deux inégalités : a Txb aTx b -aTxb, aTx b. -mincTx=maxcTx. V ariablexnon restreinte : substitution par deux variables (partie positive et négative) x=x+x xquotesdbs_dbs33.pdfusesText_39[PDF] principe droite de henry
[PDF] exercice corrigé droite de henry
[PDF] courbe de henry excel
[PDF] droite de henry pdf
[PDF] programmation linéaire exercices corrigés pdf
[PDF] programmation linéaire exercices corrigés
[PDF] programmation linéaire simplexe
[PDF] recherche opérationnelle programmation linéaire exercices corrigés pdf
[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