Méthodes dOptimisation PDF 3.2 Exercice synthétique

ORDONNANCEMENT Exercices avec solutions

13‏/04‏/2020 La méthode s'appuie sur une représentation graphique qui permet de bâtir un réseau constitué des nœuds et des tâches. Un réseau PERT est ...

2.1 Réseau de PERT

Exercice 1. Soient les contraintes d'antériorité: – A et B sont indépendantes. – C Représenter schématiquement ces contraintes en respectant la méthode PERT.

Mohammed DAOUDI Exercice et corrigé Diagramme GANTT/PERT

Exercice pédagogique TD : Préparer un repas. 1 Taches. ○ A : choisir le menu (30 min). ○ B : acheter les ingrédients (90 min).

RAPPORTS ANNUELS relatifs à lexercice 2012

14‏/11‏/2013 ii) Lorsque la correction financière est imposée par la Commis sion cette correction est nette et implique une perte financière pour la ...

Gestion de projet - réaliser le diagramme de PERT

Pour établir le diagramme Pert nous allons utiliser une méthode : la matrice des Réaliser le diagramme PERT. 41. Exercice. 41. Exercice. 42. Exercice. 42. A.

ASSISTANCE À LENSEIGNANT DANS LE CADRE DE LEIAH

structure de l'exercice puis les traits de surface et les valeurs qui y seront utilisés. pdf. [PECEGO 98] PECEGO G.

ÉTATS FINANCIERS POUR LEXERCICE BIENNAL 2008 2009

20‏/08‏/2010 À la quarante-troisième session des assemblées tenue du 24 septembre au. 3 octobre 2007

Exercice 2 :

Dresser le réseau de PERT de ce projet ? Solution b) Les deux chemins critiques : 1) E-J-A-I ;. 2) E-K-G-I. Page 4. Département d'informatique. Module : Gestion

InfoDalo

3 Exercice 1.2 5 CORRECTION FORMULES. VARIABLES

ORDONNANCEMENT Exercices avec solutions

13 avr. 2020 La méthode s'appuie sur une représentation graphique qui permet de bâtir un réseau constitué des nœuds et des tâches. Un réseau PERT est ...

Gestion de projet - réaliser le diagramme de PERT

Solution des exercices. 47. Objectifs. Université de lorraine Pour établir le diagramme Pert nous allons utiliser une méthode : la matrice des.

2.1 Réseau de PERT

2.1 Réseau de PERT. ? Exercice 1. Soient les contraintes d'antériorité: en respectant la méthode PERT. ... l'exercice 5 tracer le diagramme de GANTT :.

PLANIFICATION et Ordonnancement

PLANIFICATION et Ordonnancement. (Gestion de projet – Gestion des délais – Gestion des coûts). Méthodes : - PERT (USA) : potentiel - étapes. - MPM (Fr) :.

corrigé exercise TD GANTT & PERT

Exercice pédagogique TD : Préparer un repas. 1 Taches. ? A : choisir le menu (30 min). ? B : acheter les ingrédients (90 min).

Méthode PERT.pdf

La méthode commence par la construction d'un graphe appelé graphe PERT

Gestion de projet - calcul des dates et calcul des marges

V - Exercices Il existe deux grandes familles de diagramme Pertle Pert ... Créée en 1958 par M.B. Roy

Méthodes dOptimisation

3.2 Exercice synthétique corrigé : construction d'un pont . 4.3 Calcul de l'ordonnancement par la méthode PERT .

Méthodes dOptimisation

1.3 Exercices récapitulatifs . 3.2 Exercice synthétique corrigé : construction d'un pont . ... 4.3 Calcul de l'ordonnancement par la méthode PERT .

Recherche Opérationnelle-exercices-ordonnancement

21 avr. 2015 A précède C et D. B précède D. C et D précèdent E. Prof. Mohamed El Merouani. 8. Corrigé: Par la méthode PERT on a:.

METHODE P E R T La méthode PERT permet d' évaluer la durée de réalisation d'un projet complexe et de détecter les parties de ce projet ne supportant aucun retard Elle résout des problèmes appelés problèmes d'ordonnancement Le projet sera subdivisé en tâches

Searches related to methode pert exercice corrigé pdf PDF

Pour établir le diagramme Pert nous allons utiliser une méthode : la matrice des antériorités celle-ci n'est pas obligatoire mais bien utile car elle permet de répartir les tâches en niveaux

Quels sont les diagrammes de la méthode PERT?

Le diagramme le plus connu de la méthode PERT est le « réseau logique » ou diagramme d’enclenchement qui représente l’enchaînement logique de toutes les tâches du projet. Les outils informatiques de planification sont basés aujourd’hui sur les principes de calcul de durées de projets issus de la méthode PERT.

Qu'est-ce que la méthode PERT?

La méthode PERT a permis d’estimer et surtout d’optimiser de manière scientifique un projet constitué de milliers de tâches de durées aléatoires. Le diagramme le plus connu de la méthode PERT est le « réseau logique » ou diagramme d’enclenchement qui représente l’enchaînement logique de toutes les tâches du projet.

Quels sont les exercices de PERT?

Pert et Gantt. Démonstrateurs : Marouane Kessentini. Hassen Grati. Exercice 1: Pert. La mise en exploitation d'un nouveau gisement minier demande la ... Exercices. Exercice 1. Calculer les marges. Exercice 2. Réaliser le PERT et le Gantt. S541 S851 LA GESTION DE PROJET.doc. 7 ... Exercice PERT. 01. 01. Exercice 1.

Quelle est la durée de réalisation de la méthode PERT ?

En plus , la méthode PERT date de 1958 et vient des États-Unis où elle a été développée sous l’impulsion de la marine américaine. Par contre , l’utilisation du PERT a permis de ramener la durée globale de réalisation du projet de sept à quatre ans. D’ailleurs , cette méthode s’est ensuite étendue à l’industrie américaine.

Methodes d'Optimisation

Licence Professionnelle Logistique

Universite du Littoral - C^ote d'Opale, P^ole Lamartine

Laurent SMOCH

(smoch@lmpa.univ-littoral.fr)

Septembre 2011

Laboratoire de Math´ematiques Pures et Appliqu´ees Joseph Liouville Universit´e du Littoral, zone universitaire de la Mi-Voix, bˆatiment H. Poincarr´e

50, rue F. Buisson, BP 699, F-62228 Calais cedex

Table des mati`eres

1 Quelques rappels sur les graphes1

1.1 Initiation `a la th´eorie des graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1.1 Vocabulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1.2 Niveaux des sommets d'un graphe sans circuit . . . . . . . . . . . . . . . . . . . . . .

1.1.3 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2 Graphes valu´es et chemins critiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.1 Valuations d'un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.2 Longueur d'un chemin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.3 Chemins minimaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.4 Chemins maximaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.5 Int´erˆet d'une telle recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3 Exercices r´ecapitulatifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Problemes d'ordonnancement25

2.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Notions de projet, tˆache et ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.1 Notion de projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.2 Notion de tˆache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3 M´ethode d'ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26
2.4

´Etablissement d'un ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5 D´etermination du chemin critique et ´enum´eration des tˆaches critiques . . . . . . . . . . . . .

2.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 La methode MPM29

3.1 Le graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.1 El´ements du graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.2 Contraintes potentielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.3 Exercice corrig´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.4 Tˆaches parall`eles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.5 Op´erations d´ependantes et ind´ependantes . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.6 Op´erations compos´ees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.7 Conditions limites de d´emarrage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2 Exercice synth´etique corrig´e : construction d'un pont . . . . . . . . . . . . . . . . . . . . . . .

3.3 Date au plus tˆot d'une tˆachei, ordonnancement minimum ou au plus tˆot . . . . . . . . . . .

3.3.1 D´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.2 D´etermination des dates au plus tˆot . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.3 Chemins critiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4 Date au plus tard de d´ebut d'une tˆachei, ordonnancement limite (ou au plus tard) . . . . . .

3.4.1 D´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.2 Recherche de l'ordonnancement au plus tard . . . . . . . . . . . . . . . . . . . . . . .

3.5 Marges d'une tˆachei. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5.1 Marge totalemT(i) de la tˆachei. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5.2 Marge libremL(i) d'une tˆachei. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39
I

IITABLE DES MATIERES

3.5.3 Marge certainemC(i) d'une tˆachei. . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5.4 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6 M´ethode MPM pr´esent´ee sous forme de tableaux . . . . . . . . . . . . . . . . . . . . . . . . .

3.6.1 Ordonnancement au plus tˆot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6.2 Ordonnancement au plus tard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 La methode PERT53

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2 Difficult´es de construction du graphe PERT . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3 Calcul de l'ordonnancement par la m´ethode PERT . . . . . . . . . . . . . . . . . . . . . . . .

4.3.1 Calcul de l'ordonnancement au plus tˆot . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3.2 Calcul de l'ordonnancement au plus tard . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3.3 Calcul du chemin critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Ordonnancement en ateliers specialises - Diagrammes de Gantt61

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2 Ordonnancement sur une machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2.1 Le diagramme de Gantt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2.2 La r`egle T.O.M. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.3 Ordonnancement avec deux centres de production . . . . . . . . . . . . . . . . . . . . . . . .

5.4 Ordonnancement sur trois machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 Reduction de la duree d'un projet71

6.1 Pr´esentation de la m´ethode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 Optimisation des

ux77

7.1 G´en´eralit´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.1.1 R´eseau de circulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.1.2 Graphe associ´e `a un r´eseau de circulation . . . . . . . . . . . . . . . . . . . . . . . . .

7.1.3 Graphe canonique associ´e `a un r´eseau de circulation . . . . . . . . . . . . . . . . . . .

7.1.4 Flot sur un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.2 Recherche d'un flot maximal dans un r´eseau avec capacit´es . . . . . . . . . . . . . . . . . . .

7.2.1 La coupe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.2.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

83
7.2.3

´Etude th´eorique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.2.4 Flot complet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.3 Algorithme de Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.3.2 Enonc´e de l'algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.3.3 Suite de l'algorithme : Marquage des sommets . . . . . . . . . . . . . . . . . . . . . .

7.3.4 Suite de l'algorithme : Modification des flux . . . . . . . . . . . . . . . . . . . . . . . .

7.3.5 Recherche `a partir du marquage d'une coupe de capacit´e minimale . . . . . . . . . . .

7.4 Exercices r´ecapitulatifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

101

8 La programmation lineaire109

8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

109

8.2 Mod´elisation d'un programme lin´eaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

109

8.2.1 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

110

8.2.2 Formule g´en´erale d'un programme lin´eaire . . . . . . . . . . . . . . . . . . . . . . . . .

113

8.3 M´ethode graphique : probl`eme `a deux inconnues . . . . . . . . . . . . . . . . . . . . . . . . .

114

8.3.1 R´egionnement du plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

114

TABLE DES MATI

ERESIII

8.3.2 Les ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

115

8.3.3 R´esolution de syst`emes d'in´equations - Exemples . . . . . . . . . . . . . . . . . . . . .

116

8.3.4 R´esolution de programmes lin´eaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

120

8.3.5 Cas g´en´eral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

126

8.3.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

126

8.4 La m´ethode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

130

8.4.1 Programme lin´eaire standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

131

8.4.2 L'algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

132

8.4.3 D´etermination d'une solution de base admissible . . . . . . . . . . . . . . . . . . . . .

157

8.4.4 Utilisation de la m´ethode du simplexe lorsque la solution optimale n'existe pas . . . .

159

8.4.5 Utilisation de la m´ethode du simplexe dans un probl`eme de minimisation . . . . . . .

160

8.4.6 Exercices r´ecapitulatifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

161

IVTABLE DES MATIERES

Chapitre 1

Quelques rappels sur les graphes

1.1 Initiation `a la th´eorie des graphes

1.1.1 Vocabulaire

(a) Produit cartesien. Carre cartesien On appelleproduit cart´esiendeEparF, l'ensemble not´e

E×F={(x,y)/x∈E, y∈F}

On appellecarr´e cart´esiendeE, l'ensemble not´e

E×E=E2={(x,y)/x∈E, y∈E}

(b) Relation deEdansF On appellerelationRdeEdansFtoute correspondance qui `a certains ´el´ements deEassocie certains ´el´ements deF. "xest en relation avecy" (x∈E,y∈F) est not´e xRy L'ensemble des couples (x,y) deE×Ftels quexRyest appel´egraphede la relation. On note

G={(x,y)∈E×F/xRy}

On remarque queG⊂E×F.

SoitRune relation deEdansF, larelation r´eciproqueR-1est une relation deFdansEd´efinie par xRy⇔yR-1x (c) Relation binaire

Denition 1.1.1

Une relation binaired´efinie surEest une relation deEdansEqui est dite : r´eflexivesi : ∀x∈E,xRx sym´etriquesi : ∀x∈E,∀y∈E, xRy⇒yRx transitivesi : ∀x∈E,∀y∈E,∀z∈E,(xRyetyRz)⇒xRz 1

2CHAPITRE 1. QUELQUES RAPPELS SUR LES GRAPHES

(d) Caracterisation de la relation binaire

Une relation binaire est caract´eris´ee

1. par songraphe

Exemple 1.1.1

SoitE={x1,x2,x3,x4,x5}. On se donne

G={(x1,x1),(x1,x2),(x1,x5),(x2,x1),(x2,x3),(x4,x3),(x4,x5),(x5,x3)} 2. par sarepr´esentation sagittale Figure1.1 - Repr´esentation sagittale du graphe 3. par sarepr´esentation cart´esienne X

XXXXXXXXXXd´epartarriv´ee

x 1 x 2 x 3 x 4 x 5 x 1 x 2 x 3 x 4 x 5 4. par samatrice bool´eenne X