Optimisation Combinatoire : Méthodes Approchées

Ecole Nationale des §ciences de l'Informatique **rf,

A.U.2013-2014

Optimisation C ombinatoire : Méthodes Approchées

TD NOl

Exercice I : Rendre la monnaie

On considère le problème consistant à rendre la monnaie avec le moins de pièces possible pour un commerçant. Son probième est d'arriver exactement à une somrne N donnée en choisissant dans sa caisse un ensemble de pièces dont chacune possède une valeur fixée. Nous considerons que le commerçênt dispose d'une inflrnité de pièces de : 10, 20, 50, 100, 1000 et 50Q0 millirnes.

1. Décrire un algorithme glouton permettant de résoudre ce problème. 2. Appliquer cet algorithme sur un exemple d'un client qui effectue un achat de 8dt200 et

quidonne 1Odt.

Exercice 2 : Probtème de Choix d'activités

Le problème consiste à répartir une ressource parmi plusieurs activités concurrentes. So,it un enscrnble S = {1, ...,T} de n activités concurrentes souhaitant utiliser une même ressource laquelle ne peut supporter qu'une activité à la fois. Chaque activité a un horaire de debut dl et un horaire de fin f; avec di 5 û. Si elle est choisie l'activité i a lieu pendant I'intervalle de temps [di, f;l. Les ae.tivités i et j sont compatibles lorsque di > t ou di 2 fi " Le problème consiste à choisir le plus grand nombre d'activités compatibles entre elles.

Proposer un algorithme glouton resolvant ce problème.

Exercice 3 : Problème de Voyageur de commerc

Un autocar ds ramassage scolaire doit, tous les matins, en partant de l'école située en A, charger des élèves et B;C;D;E; F: Ayant chronométré la durée de chacun des trajets entre les différents points d'arrêt, on cherche le trajet hamiltonien (le tour) de durée minimunr On donne la matrice D: (d,i ) des trajets.

!t

{,1

-tfi {''

llL} rL

7. J

_tu

-tu li

.{ts{"t}EF _x ,1 I :1 :]c 'j, i + -Ll +J-xl::1ü 1u;1r{.1+ Itii2:r:l lil li til J .J :{

I " .tlgorithme glouton

(a) Apphquer I'algorithle du PP\,'à la r-natnce D . (b) La solution clépend t-elle du soilmet de départ dans ie PP\/l 2" Soit ie tour: s : ABCDEF. on colrsidère la transftinnation élérnentaire 2- r;pt.

(a) Dorner toutes les solutrons voisines de s: (bl Peut-on an-réiiorer par ia méthode de descente.

3. On applique 1e recuit sirnulé

(a) Queile doit être 1a température pour que la translomatron oonsistant à remplacer 1es arêtes iE, Fl el ,iB:Cl par les arêtes lB,Ei et i/a', Fl ait une probabilrté c1e 0.,5? (b) On adopte la ten'rpérature calcu1ée à 1a question (a) cûm1re tençérature uritiale et on considère une décroissance géométrique de raison;z : Combien dort-on eflectuer de chansements" qu'on llote,\r. de ternpérature pour que 1a r:rôme trans{brn-iatiol que celle défmie à 1a question précédeirte ait ur-ie probabilité d'euviron 0.001 d'être acceptée.