ENSI                                                                                                                                                                2005/2006

Examen de rattrapage de Recherche Opérationnelle

 

Filiére 1.1.1

Documents: Documents non autorisés - Calculatrice autorisée

Durée: 2 heures

 

Exercice 1 (9pts)

Une société d'import export dispose, dans les ports de Veracruz, Sâo Paulo, Conakry et Abidjan, de stocks de café de respectivement 120t, 100t, 100t et 100t , pour lesquels elle a reçu des commandes d'importateurs de dunkerque (100t) , Bordeaux (80t), Saint-Nazaire et le Havre (150t). Divers bateaux se rendent des ports étrangers considérés vers les ports français de destination. Les disponibilités de transport (en tonnes) sont données par le tableau suivant:

 

 

		Dunkerque	Bordeaux	Saint-Nazaire	Le Havre
		D	B	SN	H
Veracruz	V	70	30	30
Sâo Paulo	SP	50	40	10
Conakry	C		20	40	80
Abidjan	A		20	40	80

 

On suppose que les commandes sont classées suivant l'ordre de priorité suivant: Bordeaux, Le Havre, Dunkerque et enfin Saint-Nazaire. On cherche à satisfaire les demandes au maximum.

1.     représenter le graphe correspondant à ce problème.

2.          Préciser le type de problème à résoudre et l'algorithme utilisé pour la résolution. Préciser aussi comment peut-on prendre en compte la priorité pour une destination?

3.          Résoudre le problème en précisant les étapes intermédiaires de la résolution.

4.          Donner la coupe de capacité minimum et calculer sa capacité.

5.   Quels bateaux embarqueront le maximum de leur tonnage et quels sont ceux qui n'embarqueront aucun sac de café. Donner les commandes non satisfaites.

On affecte à chaque arc du graphe de la question 1) un coût de transport égal au dixième de sa capacité . On cherche à présent, à satisfaire les demandes au mieux avec le minimum de dépenses.

6.   Préciser le type de problème à résoudre.

7.   Ecrire ce problème sous forme d'un programme linéaire en précisant les variables, la fonction objective ainsi que les contraintes.

8.   Proposer une méthode de résolution de ce programme.

Exercice 2 (5points)

1.   Donner la définition d'un graphe connexe.

2.   Donner la définition d'un graphe fortement connexe.

3.   Donner la définition d'une composante simplement connexe d'un sommet x du graphe.

4.   Donner la définition d'une composante fortement connexe d'un sommet x du graphe.

5.   Déterminer la composante fortement connexe du sommet 8 du graphe ci-dessous.

6.   Ce graphe est-il fortement connexe? justifier votre réponse.

Exercice 3 (3points)

Définition: Un arbre est un graphe connexe sans cycles.

Problème de l'arbre de poids minimum

Considérons un graphe G(X, U) connexe. A chaque arc u G U on associe un nombre w(u) appelé poids de l'arc u.

Etant donné un graphe partiel G' = (X, U') de G, on appelle poids de G' le nombre W(G) =Σw(u).

      UЄg’

Le problème de l'arbre de popids minimum est de rechercher un arbre A* de G, tel que W(A*) =Min (W(A)).

AЄG

Le minimum est pris sur l'ensemble de tous les arbres de G.

Algorithme de de Kruskal

Etant donné un graphe connexe valu d'ordre n.

Données: Le graphe est donné par la liste de ses arcs.

(i)       On lit la liste des arcs et on prend un premier arc qui est de poids minimum: soit Ai = {u1}

(ii)      à l'étape k on a A_{k_i} = {u₁ ,u₂,…u_k-1 }•

On choisit un arc parmi les arcs restant de plus faible poids telle que Ak _U {Uk} ne forme pas un cycle.

(iii) Si k =  n — 1 Fin: A_n-1 est par construction un graphe de (n — 1) arcs et sans cycles

c'est donc un arbre.

Sinon   k = k+ 1 et aller en (ii).

Application: L'installation d'un réseau télécoms dans une ville à n régions nécessite la connexion de ces régions par des câbles spécialisés. Minimiser le coût d'installetion (en terme de câbles) revient à trouver l'arbre de poids minimum dans ce réseau.

Questions:

1.  Appliquer l'algorithme de Kruskal pour déterminer l'arbre de poids minimum du graphe ci-dessous.

2.  Expliquer comment peut-on déterminer l'arbre de poids maximum par l'algorithme de Kruskal?

 

Exercice 4 (3points)

Chemins de longueurs extrémales

Considérons un graphe G = (X, U) d'ordre n. Les sommets sont notés x₀, x₁,…, x_n-1 L'arc (x„x_i) est value par un coût l_ji On recherche les chemins de longueur minimale de x_o à tous les autres sommets. Algorithme de Ford:

1-  Initialisation : ∏(x0) = 0  et ∏ (x_i) = +oo pour les autres sommets

2-  Examen des arcs : examiner l'ensemble des sommets x₀, x₁,…, x_n-1  dans cette ordre ;

pour chaque sommet examiné, parcourir l'ensemble des arcs (x_i,x_j) en calculant

∏ (x_j) = min(∏ (xj), ∏ (xi_j)+l ij).

3- Test d'arrêt : continuer tant que ∏ (x_j) aura été modifié dans (2).

Questions:

1.  Appliquer l'algorithme de Ford au graphe ci-dessous.

2.  Comment déterminer, à l'aide de l'algorithme de Ford, le plus court chemins entre x_o à x₄.