DM Recherche Opérationnelle
ING2 Génie Civil - IPSL
Exercice 1 : Méthode du Simplexe
1. Trouver le maximum de
Z = 60x1 + 60x2 + 90x3 + 90x4
soumis aux contraintes :
x1 + x2 + x3 + x4 ≤ 15,
7x1 + 5x2 + 3x3 + 2x4 ≤ 1,
3x1 + 5x2 + 10x3 + 15x4 ≤ 1.
2. Donner le programme dual.
3. Quelle est la solution optimale du programme dual considéré dans la question 2 ?
4. On remplace la dernière inéquation par :
3x1 + 5x2 + 10x3 + 15x4 = 1.
Quel est alors le maximum de Z ?
Exercice 2 : Chemin optimal
Trouver le(s) chemin(s) de valeur minimale (resp. maximale) entre les sommets x1
et x14 dans le graphe suivant et donner à chaque fois la longueur optimale.
Exercice 3 : Applications de la RO
1. Enoncez une situation-problème relative au Génie Civil mais dont la résolu-
tion nécessite une formalisation en termes de programmation linéaire. Fournir
des valeurs réalistes aux contraintes, puis résoudre le problème à l’aide de la
méthode du Simplexe.
2. Proposez une deuxième situation-problème utilisant cette fois l’algorithme de
Ford-Fulkerson.
1
Problème : Flot de valeur maximale
Deux usines à gaz, g1 et g2 alimentent trois villes v1 , v2 et v3 par l’intermédiaire du
réseau de distribution ci-dessous ; les nombres associés aux arcs et aux sommets de
ce réseau représentent des capacités journalières.
Déterminer à l’aide de l’algorithme de Ford-Fulkerson la production journalière
maximale que peuvent écouler ces deux usines. Si cette production est atteinte,
à quelle consommation journalière chacune des villes peut-elle prétendre ?
Indication : Associer au problème le réseau suivant :
