Td2 recherche operationnelle et optimisation 2eme annee ing
Télécharger PDFTD 2 : Recherche Opérationnelle et Optimisation
Ce document d'étude s'adresse aux étudiants en 2ème année d'ingénierie mécatronique. Il traite des problématiques fondamentales de la théorie des graphes et de la recherche de chemins optimaux dans des réseaux complexes.
Exercice 1
On considère le projet de construction d’un réseau routier entre les villes A et G. Coût de chaque tronçon : A -- B = 8 ; A -- C = 5 ; C -- B = 4 ; B -- D = 9 ; B -- F = 7 ; C -- E = 10 ; C -- F = 2 ; E -- B = 1 ; E -- D = 6 ; D -- G = 7 ; E -- G = 11 ; F -- G = 8 ; F -- E = 3. Le problème consiste à déterminer l’autoroute dont le coût total de construction est minimal.
Pour résoudre ce problème, il est conseillé de modéliser le réseau sous forme de graphe valué où chaque ville est un sommet et chaque coût une pondération sur l'arc correspondant. L'utilisation d'un algorithme de recherche de chemin minimal permettra d'identifier la route la plus économique entre A et G.
Exercice 2
On considère le graphe représenté ci-dessous : Déterminer le plus court chemin entre le sommet (1) et tout autre sommet du graphe.
Dans cet exercice, l'application de l'algorithme de Dijkstra est idéale pour trouver les distances minimales depuis un point source unique vers l'ensemble des destinations possibles dans un graphe à poids positifs.
Exercice 3
On considère le réseau routier décrit ci-dessous : Dans ce graphe, -Les arcs représentent des tronçons de route à sens unique et les nombres qui leur font face représentent le temps nécessaire pour parcourir le trajet associé; -Les arêtes représentent des tronçons de route à double sens et les nombres qui leur font face représentent le temps nécessaire pour parcourir le trajet associé (dans les deux sens); -Les sommets représentent les carrefours du réseau routier et les nombres en regards de ceux-ci représentent le temps nécessaire pour traverser le carrefour associé. On désire aller le plus rapidement possible de A vers H. Modifiez l'algorithme de Dijkstra de façon à résoudre ce problème.
La modification consiste à intégrer le coût de traversée des sommets dans la fonction de mise à jour des distances. Une approche consiste à créer un graphe fictif où chaque sommet est dédoublé pour représenter le délai de passage.
Foire Aux Questions (FAQ)
Quelle est la différence entre un arc et une arête ?
Un arc est une liaison orientée (un sens unique), tandis qu'une arête est une liaison bidirectionnelle (double sens). Dans une modélisation mathématique, une arête peut être vue comme deux arcs de sens opposés ayant le même poids.
Comment adapter l'algorithme de Dijkstra pour les coûts aux sommets ?
Pour prendre en compte le temps d'attente à un carrefour, on peut ajouter la valeur du sommet au poids de tous les arcs qui en sortent lors de l'étape de relâchement des distances dans l'algorithme.
Pourquoi Dijkstra est-il utilisé en mécatronique ?
En ingénierie mécatronique, ces algorithmes servent à optimiser les trajectoires de robots mobiles, à planifier les mouvements de bras articulés ou à gérer les flux logistiques dans des systèmes de production automatisés.