Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Master-1 MIAGe – 2013/2014 Recherche Opérationnelle 2 (J1MG8003) Devoir à la ma

Master-1 MIAGe – 2013/2014 Recherche Opérationnelle 2 (J1MG8003) Devoir à la maison – Corrigé 20 mai 2014 ; rendre les copies avant la ﬁn mai 2014 Exercice 1. Les sept pays, les Pays-Bas, la Belgique, l’Allemagne, la Suisse, l’Italie, l’Espagne et la France, produisent, exportent, importent et consomment le beurre. Certains de ces pays surproduisent et sont obligé d’exporter, d’autres doivent importer. Le gouvernement de chaque pays décide de créer un organisme dont le rôle est d’aider les échanges. Pour cela, dans un premier temps, chaque pays passe un accord commercial avec chacun de ses voisins ﬁxans des aides pour l’exportation vers des pays déﬁcitaires et des taxes pour l’exportation vers des pays surproducteurs. Les données sont résumées dans le tableau 1. Les nombres dans chaque case du tableau représentent les taxes, les aides et les coût de transport sous forme taxe/aide/coût . PB B A S I F E PB 0/15/2 0/5/4 B 15/0/2 8/0/3 22/0/2 A 5/0/4 0/10/3 5/0/3 15/0/4 S 0/5/3 0/15/2 5/0/5 I 15/0/2 8/0/6 F 0/10/2 0/15/4 0/5/5 0/8/6 0/5/6 E 5/0/6 Table 1 – Taxes, aides et coûts de transport pour exportation du beurre. 1. Modéliser le problème sous forme d’un problème de plus court chemin dans un graphe orienté valué. Que remarque-t-on ? 2. La commission européenne propose de réduire de 15 à 10 l’aide à l’expor- tation de la France vers l’Allemagne. Quelle en est la raison ? 3. Résoudre le problème de l’exportation du beurre des Pays-Bas vers l’Es- pagne. Corrigé. Les dépenses pour acheminer le beurre d’un pays à un autre se cal- cule par la formule taxe −aide + coût . 1 PB B A F S E I −7 −8 17 −1 9 11 24 19 −2 14 1 11 17 −11 (−6) 10 0 −13 −13 8 −2 Figure 1 – Exportation du beurre. Nous obtenons donc le graphe de la ﬁgure 1. Les sigles signiﬁent PB = Pays- Bas, B = Belgique, A = Allemagne, F = France, S = Suisse, E = Espagne, I = Italie. 1. On remarque que ce graphe contient un circuit absorbant de valeur −2 : A 8 − →S −13 − →I 14 − →F −11 − →A . Ainsi, le problème d’un plus court chemin n’a pas de solution : en circulat par ce circuit on peut avoir du beurre et de l’argent du beurre. 2. En réduisant de 15 à 10 l’aide à l’exportation de la France vers l’Allemagne on rend le poids du traget F − →A égale à −6 au lieu de −11, ce qui détruit le circuit absorabant. 3. La table 2 montre le dérulement de l’algorithme de Ford–Bellmann. La 7ème étape est l’étape de contrôle : elle montre qu’il n’y a pas de circuits ab- sorbant. Finalement, le plus court chemin des Pays-Bas vers l’Espagne est le suivant : PB −13 − →B 11 − →A 8 − →S −13 − →I 14 − →F 1 − →E . La valeur de ce chemin est égale à 8. Aussi, ce chemin représente l’arborescence des plus courts chemins. 2 étape PB B A S I F E 0 0 ∞ ∞ ∞ ∞ ∞ ∞ 1 0 −13 −1 ∞ ∞ ∞ ∞ 2 0 −13 −2 7 ∞ 11 ∞ 3 0 −13 −2 6 −6 11 12 4 0 −13 −2 6 −7 8 12 5 0 −13 −2 6 −7 7 9 6 0 −13 −2 6 −7 7 8 7 0 −13 −2 6 −7 7 8 Table 2 – Algorithme de Ford–Bellmann. Exercice 2. La ﬁgure 2 représente un réseau. (a) Trouver le ﬂot maximum, en utilisant à chaque étape un chemin amélio- rant d’une capacité maximale. Vous n’êtes pas obligés d’expliciter tous les détails de l’application de l’algorithme : il suﬃt de donner la liste des chemins améliorants et des leurs valeurs, ainsi que le ﬂot optimal. (b) Exhiber une coupe minimum. (c) Le réseau subie des changements indiqués plus bas. Essayer de trou- ver, dans chaque cas, le ﬂot maximum sans beaucoup d’eﬀorts, et surtout sans recommencer l’algorithme dès le début. Indication : la connaissance de la coupe minimum peut être utile. 1. La capacité de l’arc ac diminue jusqu’à 8. 2. La capacité de l’arc cd augmente jusqu’à 10. 3. La capacité de l’arc ac augmente jusqu’à 12, celle de l’arc ad, jusqu’à 16, et l’arc de disparaît. 1 8 2 27 13 7 2 26 s a b c f d t 30 22 e 8 7 1 11 9 Figure 2 – Réseau. 3 Corrigé. Le ﬂot maximum ainsi que la coupe minimum sont montrés sur la ﬁgure 3. La valeur du ﬂot est égale à 32. Les chemins améliorants (en ordre décroissant de leurs valeurs) : 1 : s →a →c →f →t 11 2 : s →a →b →c →f →t 8 3 : s →a →d →t 7 4 : s →f →t 2 5 : s →a →d →b →c →e →t 2 6 : s →b →c →e →t 1 7 : s →a →d →e →t 1 La coupe minimum est S = {s, a, d}, T = {b, c, e, f, t}. Les arcs qui vont de S à T sont tous saturés : s →b (1/1), s →f (2/2), a →b (8/8), a →c (11/11), d →b (2/2), d →e (1/1), d →t (7/7). Leu seul arc qui va de T à S est vide : c →d (0/9). 1 2 27 13 2 s a b c f d t e 8 7 1 9 30 8 11 22 26 7 10/ 11/ 29/ 1/ 2/ 8/ 11/ 19/ 2/ 0/ 3/ 1/ 21/ 7/ 4/ Figure 3 – Réseau. Modiﬁcations du réseau : 1. La capacité de l’arc ac diminue jusqu’à 8. Par conséquent, la capacité de la même coupe (S, T ) devient égale à 29. Donc, on ne peut pas obtenir un ﬂot supérieur à 29. Le ﬂot égal à 29 peut être obtenu par la même ensemble de chemins (la valuer du premier chemin étant diminuée de 11 à 8). 4 2. La capacité de l’arc cd augmente jusqu’à 10. L’arc cd va de T vers S. Elle doit rester vide, et l’augmentation de sa capacité ne change pas la valeur du ﬂot. 3. – La capacité de l’arc ac augmente jusqu’à 12 : la valeur du premier chemin augmente jusqu’à 12 ; – celle de l’arc ad, jusqu’à 16 : cet arc se trouve à l’intérieur de l’ensemble S, et il n’est pas saturé ; pas d’inﬂuence donc sur la valeur du ﬂot ; – l’arc de disparaît : le dernier chemin de la liste (le chemin numéro 7) disparaît lui aussi, et la valeur du ﬂot diminue d’une unité. Au total, la valeur du ﬂot ne change pas. Exercice 3. Eﬀectuer un parcours en largeur et un parcours en profondeur du graphe de la ﬁgure 4, en prenant comme point de départ le sommet 13. Chaque fois quand il y a un choix à faire entre deux ou plusieurs sommets, il faut choisir le sommet ayant plus petit numéro. 9 17 1 2 3 4 6 7 8 10 11 12 14 15 16 18 19 20 21 13 5 Figure 4 – Graphe à parcourir. Corrigé. Les deux parcours sont montrés sur les ﬁgures 5 et 6. La ﬁle d’attente du parcours en largeur est comme suit : 13, 5, 8, 9, 18, 19, 1, 2, 3, 4, 7, 12, 6, 10, 14, 17, 20, 11, 15, 16, 21 5 9 17 1 2 3 4 6 7 8 10 11 12 14 15 16 18 19 20 21 13 5 Figure 5 – Parcours en largeur. 9 17 1 2 3 4 6 7 8 10 11 12 14 15 16 18 19 20 21 13 5 Figure 6 – Parcours en profondeur. 6 uploads/Geographie/ dm2bis-corrige-pdf.pdf