OEF Ordonnancement
--- Introduction ---
Ce module regroupe pour l'instant 15 exercices sur les problèmes
d'ordonnancement et les graphes orientés sans circuit
(niveaux, chemin minimal, problèmes de modélisation).
Algorithme de calcul des niveaux
Voici un graphe orienté sans circuit
. On désire classer les sommets selon leur niveau en faisant toutes les étapes de l'algorithme. Etape : Chercher les sommets de niveau . Calculer le nombre de précédents de chaque sommet dans le graphe
obtenu à partir de
en enlevant les sommets dont le niveau a déjà été trouvé
puis donner la liste des sommets de niveau :
![]() | | Points |
|
| Nombre de précédents dans
|
|
|---|
|
| Sommet(s) de niveau : |
| Sommet(s) de niveau :
|
Entrée et sortie
Voici un graphe orienté sans circuit. On lui rajoute une entrée 
et une sortie 
. Quels sont les suivants de ? Quels sont les précédents de ? (il s'agit d'en prendre le moins possible).
Dictionnaire et niveau
Soit un graphe défini par le dictionnaire des .
Calculer la matrice booléenne des suivants du graphe (on séparera les éléments d'une ligne par des virgules).
| | |
La matrice booléenne des suivants est
. Sa matrice transposée est la matrice
. Calculer le niveau de chacun des sommets :
|
|
Placer les sommets
Soit un graphe sans circuit défini par le dictionnaire des . On lui rajoute une entrée et une sortie . Compléter le graphe par niveau tracé à côté :
Elimination
Voici la matrice booléenne des précédents d'un graphe orienté sans circuits.
Remplissez le tableau des précédents et des précédents des précédents (si un élément n'en a pas, mettre une étoile : *). | Sommets | Précédents | Précédents des précédents |
|---|
|
|
|
On obtient le tableau | Sommets | Précédents | Précédents des précédents |
|---|
| | |
Lorsqu'on étudie un problème d'ordonnancement, on peut éliminer une arête
si un chemin
existe. Donner le tableau des précédents obtenus en éliminant les informations inutiles détectées par ce calcul : Donner la matrice du nouveau graphe obtenu :
Liaisons
| |
|
|
h.
|
Donner une solution parmi les plus économiques en nommant le nom des villes par leur initiale et en commençant par
et en finissant par à
. Quel prix faut-il prévoir ?
Donner une solution parmi les plus rapides en nommant le nom des villes par leur initiale et en commençant par
et en finissant par à
. Quelle est la durée du trajet (sans compter les escales) ?
Longueur minimale et maximale
- Un chemin de longueur minimale :
- :
Plus grande distance
:
Classer les sommets par niveau I
Voici un graphe orienté sans circuit. Classer les sommets selon leur niveau : |
|
| Sommet(s) de niveau : |
| Sommet(s) de niveau :
| |
![]() |
Classer les sommets par niveau II
Voici un graphe orienté sans circuit. Classer les sommets selon leur niveau : ![]() |
| Sommet(s) de niveau : |
| Sommet(s) de niveau :
| |
Graphe sans circuits et niveau
Voici un graphe orienté sans circuit. Calculer le niveau de chacun des sommets
Niveaux sur le graphe
Voici un graphe orienté sans circuit. Remplir les cases avec le niveau de chacun des sommets :
Ordonnancement d'un projet
Etape 1 : Calculer la date au plus tôt de début de chaque tâche.
Etape 2 :
La durée minimale du projet est donc de
semaines
Etape 3 : Calculer la date au plus tard de début de chaque tâche.
Etape 4 : Donner la liste des tâches critiques (s'il n'y en a pas, écrire vide ):
| Sommet |
|
| Début au plus tôt |
|
| Début au plus tard |
|
Ordonnancement d'un projet, marges
Etape 1 : Calculer la date au plus tôt de début de chaque tâche.
Etape 2 :
La durée minimale du projet est donc de
semaines
Etape 3 : Calculer la date au plus tard de début de chaque tâche.
Etape 3 : Calculer la marge de chaque tâche.
Etape 4 : Donner la liste des tâches critiques (s'il n'y en a pas, écrire vide ):
| Sommet |
|
| Début au plus tôt |
|
| Début au plus tard |
|
| Marge |
|
Ordonnancement d'un projet modélisé
Etape 1 : Calculer la date au plus tôt de début de chaque tâche.
Etape 2 :
La durée minimale du projet est donc de
semaines
Etape 3 : Calculer la date au plus tard de début de chaque tâche.
Etape 4 : Donner la liste des tâches critiques (s'il n'y en a pas, écrire vide ):
| Sommet |
|
| Début au plus tôt |
|
| Début au plus tard |
|
The most recent version
Cette page n'est pas dans son apparence habituelle parce que
WIMS n'a pas pu reconnaître votre navigateur web.
Veuillez noter que les pages WIMS sont générées interactivement; elles ne
sont pas des fichiers
HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE.
Il est inutile pour vous de les ramasser par un programme robot.
- Description: collection d'exercices sur les graphes sans circuits et les méthodes d'ordonnancement. interactive exercises, online calculators and plotters, mathematical recreation and games
- Keywords: interactive mathematics, interactive math, server side interactivity, operational_research, graph, algorithmics, scheduling, potentiel, tache, pert