[PDF] exercices corrigés recherche opérationnelle pdf
[PDF] exercices corrigés recherche opérationnelle s5
[PDF] exercices corrigés repère dans le plan
[PDF] exercices corrigés repère dans le plan 3ème
[PDF] exercices corrigés repère dans le plan pdf
[PDF] exercices corrigés représentation de newman
[PDF] exercices corrigés sciences physiques premiere s
[PDF] exercices corrigés semi conducteurs pdf
[PDF] exercices corrigés statique des fluides pdf
[PDF] exercices corrigés statique pfs
[PDF] exercices corrigés statistique
[PDF] exercices corrigés statistique descriptive
[PDF] exercices corrigés statistique terminale pdf
[PDF] exercices corrigés sur acide faible/ base faible pdf
[PDF] exercices corrigés sur amplificateur d'instrumentation
UNIVERSITE DU LITTORAL
Maıtrise AES
Recherche op´erationnelle
Daniel DE WOLF
Dunkerque, Septembre 2003
Table des mati`eres
ILaprogrammation lin´eaire et en nombres entiers 7
1Laprogrammation lin´eaire. 9
1.1 Introduction............................9
1.2 Plan du cours............................10
1.3 Un simple exemple.........................10
1.4 R´esolution graphique.......................13
1.5 Formulation g´en´erale.......................17
1.6 Exercices..............................19
2Algorithme du Simplexe. 21
2.1 Principe de l"algorithme......................21
2.2 Formes canoniques d"un programme lin´eaire............22
2.3 Notion de solution de base.....................24
2.4 Initialisation de l"algorithme....................26
2.5 Une it´eration Simplexe.......................27
2.5.1 Choix de la direction....................27
2.5.2 Choix de la variable sortante................27
2.5.3 Calcul du nouveau sommet................28
2.5.4 Test d"optimalit´e......................30
2.5.5 Chemin suivi par l"algorithme du Simplexe........31
2.6 Algorithme du Simplexe......................32
3L"algorithme du Simplexe en Tableaux 33
3.1 Introduction............................33
3
4Table des mati`eres
3.2 Notion de tableau Simplexe....................34
3.3 Tableaux Simplexe et pivotage...................35
3.4 Algorithme du Simplexe en tableaux................40
3.5 Exercices..............................42
4Questions sur l"algorithme du Simplexe. 43
4.1 Introduction............................43
4.2 Initialisation de l"algorithme....................43
4.3 D´etermination de la variable entrante...............50
4.4 D´etermination de la variable sortante...............50
4.5 Arret apr`es un nombre fini d"it´erations...............53
4.6 Exercices..............................56
5Analyse postoptimale. 57
5.1 Introduction............................57
5.2 Variation par rapport au second membre..............58
5.3 Variation des coefficients objectifs.................62
5.4 Cout r´eduit des variables hors base.................64
5.5 Exercices..............................66
6Laprogrammation en nombres entiers. 69
6.1 Introduction............................69
6.2 Formulation des probl`emes mixtes.................70
6.2.1 Probl`emes avec couts fixes.................70
6.2.2 Probl`emes avec contrainte logique.............71
6.2.3 M´elange avec nombre limit´ed"ingr´edients........72
6.2.4 Choix parmi un nombre discret de valeurs.........73
6.3 M´ethode de branch and bound...................74
6.4 Exercices..............................79
Table des mati`eres5
II Les mod`eles sur r´eseau, dynamiques et non lin´eaires. 81
7Les mod`eles sur r´eseau 83
7.1 Le probl`eme de transport simple..................84
7.1.1 Repr´esentation au moyen d"un graphe...........84
7.1.2 Formulation du probl`eme.................85
7.2 Planification de la production...................87
7.3 Probl`eme d"affectation optimale..................89
7.4 Le probl`eme de transport g´en´eral.................90
7.4.1 Probl`eme du plus court chemin..............91
7.4.2 Probl`eme du flot maximum................92
7.5 Exercices..............................93
8R´esolution du probl`eme de transport simple 95
8.1 Introduction............................95
8.2 Notion de cout r´eduit........................95
8.3 Le probl`eme de transport simple..................99
8.4 R´esolution du probl`eme de transport simple............100
8.4.1 R´esolution par le Simplexe................100
8.4.2 R´esolution par la m´ethode du stepping stone.......102
8.5 Exercices..............................106
9R´esolution du probl`eme de transport g´en´eral 107
9.1 Introduction............................107
9.2 Notion de r´eseau r´esiduel.....................107
9.3 R´esolution du probl`eme de flot `acout minimum..........108
9.3.1 Algorithme de plus courts chemins successifs.......109
9.4 Application au probl`eme d"affectation...............112
9.5 Exercices..............................117
10 La programmation dynamique. 119
10.1 Le probl`eme du voyageur.....................119
6Table des mati`eres
10.2 R´esolution des probl`emes dynamiques...............123
10.3 Un probl`eme d"affectation de ressources rares...........124
10.4 Application `alaplanification de la production...........126
10.5 Exercices..............................130
11 Les mod`eles non lin´eaires 131
11.1 Introduction............................131
11.2 Difficult´eder´esolution des probl`emes non lin´eaires........132
11.3 Diff´erence avec la programmation lin´eaire.............133
11.4 Les probl`emes convexes......................136
11.5 Conditions de Kuhn et Tucker...................138
11.6 Exercices..............................142
12 R´esolution des probl`emes non lin´eaires 143
12.1 Introduction............................143
12.2 Programmation s´eparable.....................144
12.2.1 R´esolution par la notion d"´epigraphe...........146
12.2.2 R´esolution par la notion d"enveloppe convexe.......147
12.3 La m´ethode de Franck-Wolfe...................149
12.4 Exercices..............................154
Partie I
La programmation lin´eaire et en nombresentiers 7
Chapitre 1
La programmation lin´eaire.
1.1 Introduction
L"objectif de ce cours est double. Il s"agit, d"une part, de donner une introduction `alaformulation en mod`eles d"optimisation.Ils"agit, d"autre part, de pr´esenter lestechniques de r´esolutionde ces probl`emes. On parle deprobl`eme d"optimisationlorsqu"il fautmaximiser une fonction sous contraintes.Par exemple, maximiser le b´en´efice d"une entreprise sous les contraintes de satisfaire la demande et de respecter la capacit´edeproduction. Le cours est divis´eendeux parties correspondant `ades types diff´erents de mod`eles d"optimisation. Dans lapremi`ere partie du cours,nous nous concentrerons sur lesprobl`emes lin
´eaireset lesprobl`emes en nombres entiers.
meso`ulafonctionobjectifetlescontraintessontpurementlin´eaires. Lorsqu"iln"y aque deux variables de d´ecision, un probl`eme lin´eaire peut etre r´esolu de mani`ere purement graphique. C"est ce que nous verrons dans ce chapitre. Lorsqu"il y a un plus grand nombre de variables, un algorithme mis en uvre sous la forme d"un programme informatique s"av`ere n´ecessaire. Il s"agit de l"algorithme du Simplexe que nous verrons au chapitre 2. Au chapitre 5, nous examinerons une question tr`es importante : `asavoir la sensibilit´edelasolution `ades modifications de donn´ees.
On parle d"analyse post-optimale.
Lorsque les variables doivent prendre des valeurs enti`eres, on parle deprobl`e- mes en nombres entiers.On devrait `aproprement parler de probl`emes lin´eaires en nombres entiers car on impose, en plus, aux contraintes et `alafonction objectif d"etre lin´eaires. Nous verrons au chapitre 6 une technique de r´esolution de ces probl`emes : il s"agit de la m´ethode de branch and bound. Dans laseconde partie du cours,nous nous concentrerons sur lesprobl`emes 9
10Chapitre 1. La programmation lin´eaire.
dynamiqueset lesprobl`emes non lin´eaires. Le chapitre 10 est consacr´e`alaformulation et `alar´esolution desprobl`emes dynamiques,c"est-`a-dire ceux o`uune d´ecision strat´egique doit etre prise `achaque ´etape. Une application typique est la planification de production o`u`achaque p´eriode de l"horizon de planification, on doit d´ecider du niveau de production. Lorsque les contraintes et/ou la fonction objectif sont non lin´eaires, on parle deprobl`emes non lin´eaires.Nous verrons au chapitre 11 quelques m´ethodes de r´esolution de ces probl`emes. Il est `aremarquer que toutes ces m´ethodes de r´esolution ´etant mises en uvre dans des logiciels commerciaux, il ne viendrait plus `al"id´ee de les programmer soi-meme. Par exemple, le solveur d"Excel dispose d"une impl´ementation de ces algorithmes.
1.2 Plan du cours
Partie I : les probl`emes lin´eaires et en nombres entiers.
La programmation lin´eaire.
L"algorithme du Simplexe.
Questions sur l"algorithme du Simplexe.
L"analyse post-optimale.
Les mod`eles en nombres entiers.
R´esolution des mod`eles en nombres entiers. Partie II : les mod`eles sur r´eseau, dynamiques et non lin´eaires.
Les mod`eles sur r´eseau.
La programmation dynamique.
Application`alaplanification de production.
Les mod`eles non lin´eaires.
R´esolution des mod`eles non lin´eaires.
1.3 Un simple exemple
Nous prenons un exemple tir´edeHillier et Lieberman [10]. Il s"agit d"une ent- reprise de fabrication de chassis qui envisage la production de deux nouveaux
Section 1.3. Un simple exemple11
mod`eles au moyen des capacit´es r´esiduelles de ses trois ateliers. Il s"agit respec- tivement d"un chassis en aluminium et d"un chassis en bois. Le premier produit dans le troisi`eme atelier o`uleverre est mont´esur le chassis. Tandis que le second produit n´ecessite le passage dans le deuxi`eme atelier pour fabriquer le cadre en bois et dans le troisi`eme atelier o`uleverre est mont´esur le chassis. Les marges unitaires, les temps de fabrication de chacun des produits dans chacun des ateliers ainsi que les capacit´es hebdomadaires r´esiduelles de ces ateliers sont donn´es au tableau 1.1.
Produit 1 Produit 2Capacit´edisponible
(heures/produit) (heures/produit)(heures/semaine)
Atelier 1104
Atelier 20212
Atelier 33218
Marge3$ 5$
Tableau 1.1: Marges, temps d"usinage et capacit´es. Laquestionqui se pose est la suivante : "Combien faut-il produire de chassis de chaque type par semaine pour maximiser le profit net ?" Laformulationd"unprobl`emed"optimisationcomportetoujourslestrois ´etapes suivantes :
1. choix des variables du mod`ele;
2. formulation de l"objectif;
3. formulation des contraintes.
Lapremi`ere ´etapeconsiste `achoisir les variables du probl`eme. D´efinition 1.1Onappellevariabletoutequantit´eutile`alar´esolutionduprobl`eme dont le mod `ele doit d´eterminer la valeur. Cette d´efinition permet de diff´erencier les variables des param`etres, qui sont des donn´ees qui peuvent varier, par exemple d"une p´eriode `al"autre ou d"un sc´enario `al"autre. Ici les quantit´es que le mod`ele doit d´eterminer sont les productions de
12Chapitre 1. La programmation lin´eaire.
chassis par semaine. Notons donc : x 1 =nombre de chassis de type 1 produits par semaine, x 2 =nombre de chassis de type 2 produits par semaine. Ladeuxi`eme ´etapeconsiste `aformuler math´ematiquement l"objectif. D´efinition 1.2On appellefonction objectifd"un probl`eme d"optimisation le cri- t `ere de choix entre les diverses solutions possibles. Icil"entreprised´esiremaximisersonprofitnet. Lamarge ´etantde3pourlepremier type de chassis et de 5 pour le second, l"objectif s"exprime comme suit : maxz=3x 1 +5x 2 Latroisi`eme ´etapeest la formulation les contraintes du probl`eme. D´efinition 1.3On appellecontraintes du probl`emetoutes les relations limitant le choix des valeurs possibles des variables. Ces relations peuvent etre de simples bornes sur les variables. Par exemple, les quantit´eproduites ne peuvent etre n´egatives. Math´ematiquement : x 1 ,x 2 ≥0. Ellespeuvent etrepluscomplexescommelescontraintedecapacit´edeproduc- tion. Le temps pour assembler 1 chassis de type 1 dans l"atelier 1 est de 1 heure o`uilreste 4 heures disponibles. D"o`ulacontrainte de capacit´edel"atelier 1 : x 1 Semblablement, on peut construire les contraintes de capacit´es des deux autres ateliers : 2x 2 3x 1 +2x 2 Il est alors tr`es utile de reprendre sous une forme condens´ee la formulation compl`ete du probl`eme. Ici, on obtient la formulation suivante : maxz=3x 1 +5x 2 s.c.q. x 1 2x 2 3x 1 +2x 2 x 1 ≥0 x 2 ≥0(1.1)
Section 1.4. R´esolution graphique13
1.4 R´esolution graphique
Comme annonc´edans l"introduction, dans le cas de deux variables de d´ecision, un probl`eme lin´eaire peut etre r´esolu de mani`ere purement graphique en suivant le processus en trois ´etapes qui suit. Lapremi`ere ´etape de la r´esolutionconsiste `arepr´esenter graphiquement la r
´egion r´ealisable.
D´efinition 1.4On appeller´egion r´ealisable,l"ensemble des valeurs de variables de d
´ecision qui satisfont toutes les contraintes.
Dans le cas de l"exemple, c"est l"ensemble des points(x 1 ,x 2 )satisfaisant les in´egalit´es de (1.1).
Graphiquement une in´egalit´etelle que3x
1 +2x 2 1 +2x 2 =18). Lorsque l"on fait l"intersection des cinq demi-plans correspondant aux cinq in´ega- lit´es : x 1 2x 2 3x 1 +2x 2 x 1 ≥0(4) x 2 ≥0(5) onobtientlepolygonehachur´e`alafigure1.1. En ´economie,cetensembler´ealisable est encore appel´el"ensemble de production.
G´en´eralisation. La notion de poly`edre de
R n
Plus g
´en´eralement, si on anvariables, on ne parle plus de polygone, mais bien de poly `edre. En effet, la r´egion de R n correspondant aux solutions d"une in´egalit´e lin
´eaire du type suivant :
a k1 x 1 +a k2 x 2 +...+a kn x n k est un demi-espace ferm´esitu´ed"un cot´edel"hyperplan deR n d"´equation : a k1 x 1 +a k2 x 2 +...+a kn x n =b k
D´efinition 1.5On appellepoly`edrede
R n l"ensemble desx?R n v´erifiant un syst `eme d"in´equations lin´eaires : a k1 x 1 +a k2 x 2 +...+a kn x n k ,k=1,...p
14Chapitre 1. La programmation lin´eaire.
10 8 6 4 2
02468x
1 x 2 (1) (2) (3)(4) (5)
Figure 1.1: Ensemble de production.
Atitre d"illustration, le poly`edre de
R 3 d´efini par les in´egalit´es suivantes : x 1 +x 2 +x 3 x 1 ,x 2 ,x 3 ≥0 est repr ´esent´e`alafigure 1.2 par le prismeOABCo`uOnote l"origine des axes. x 1 x 3 x 2 AC Bquotesdbs_dbs19.pdfusesText_25
[PDF] Recherche opérationnelle - LMPA