Algorithme vorace et minimisation des coûts

Version imprimable

12/04/2011, 03h30
cProg

Algorithme vorace et minimisation des coûts

Bonjour,

j'ai le problème suivant à résoudre;
Afin de commercialiser ses différents produits, une entreprise a besoin de n permis. A cause de certaines lois, elle ne peut obtenir plus d'un permis par mois. De plus, le coût des permis augmente
chaque mois. En effet, bien que le coût de chacun des permis soit de $100.00 actuellement, le coût du permis j (1 <= j <= n) augmente d'un facteur rj > 1 chaque mois (les rj sont des paramètres).
Autrement dit, acheter le permis 4 durant le premier mois coûte 100r4 alors que son acquisition durant le sixième mois, par exemple, coûterait 100(r4)^6 . Enfin, on suppose que ri ?=(différent) rj pour i ?=(différent) j.
La question est donc de savoir, pour un ensemble de rj donné (1 <= j <= n), dans quel ordre acheter les n permis afin de minimiser le coût total d'acquisition.
1. Elaborez un algorithme polynomial, utilisant l'approche vorace, permettant de résoudre ce problème. Analysez votre algorithme en pire cas.
2. Prouvez que votre algorithme retourne bien la solution optimale.
3. Illustrez votre algorithme sur l'instance suivante : n = 3, r1 = 3, r2 = 4, r3 = 2.
J'ai pu écrire seulement l'algorithme suivant, mais ne sait plus quoi écrire d'autre:

Algorithme minCout()

TantQue j<n (tant que tous les permis ne sont pas achetés)
j=prochain permis acheté
Si le permis du mois courant est disponible alors
acheter
Fsi
FTantQue

Pouvez vous m'aiguiller s'il vous plaît? Merci.
12/04/2011, 09h47
Acrim

Le principe d'un algorithme glouton est de construire une solution progressivement, en se basant sur ce qui semble le meilleur au fur et a mesure (c'est mieux formulé sur wikipedia :)).

L'algorithme que tu proposes (qui souffre de quelques défauts) permets de construire une solution mais la partie intéressante se trouve dans la ligne j=prochain permis acheté. Pour trouver ton algorithme glouton il faut que tu répondes à la question : Quel permis acheter ? Ou, autrement dit : Étant donné le mois n, quel permis est le plus intéressant ?

Vu ce que j'ai compris du problème je pense qu'il s'agit du permis dont le (rj) est le plus élevé. A toi de voir si cela convient et comment répondre aux autres questions...
12/04/2011, 14h11
cProg

Citation:

Envoyé par Acrim

Vu ce que j'ai compris du problème je pense qu'il s'agit du permis dont le (rj) est le plus élevé.

Bonjour Acrim. C'est exact; de façon intuitive, c'est la réponse à laquelle j'ai pensé. Mais le problème ici est de traduire cela sur le plan algorithmique.
12/04/2011, 14h43
Acrim

Citation:

Envoyé par cProg

Mais le problème ici est de traduire cela sur le plan algorithmique.

Je ne sais pas comment t'aiguiller plus sans te donner la solution. Si c'est l’écriture d'algorithme qui te pose problème. Essais, dans un premier temps, de décrire les étapes nécessaires de manière très générale. Une fois les étapes fixées tu pourras peut être plus facilement rentrer dans les détails (avec la notation etc).

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 Algorithme minCout(A[1, ..., n], B[]) //A[1, ..., n]: tableau stockant, dans le désordre, les rj valeurs des coûts des n licences //B[]: tableau vide pour stocker les licences retenues pour achat TriRapide(A[1, ..., n]) //A[1, ..., n] est maintenant trié en ordre décroissant while j < n (Tant qu’il reste encore des licences à acquérir) do <div style="margin-left:40px">for i ← 1 to n (Passer en revue les coûts des licences) do <div style="margin-left:40px">if ri < ri+1 (Il s’agit de choisir d’abord la licence de plus grand coût) then A[i ] = i + 1 (acheter maintenant la licence de plus grand coût) end</div>j = j + 1 (Recherche de la prochaine licence à acquérir) end end</div>Retourne A[i ]
Normalement le nombre de licences doit diminuer au fur et à mesure que je sélectionne les licences de plus haut coût et que les stocke dans le tableau B. De plus, lorsque je passe en revue les coûts des licences, je ne dois plus parcourir le tableau A dans son entièreté. Par conséquent comment puis je écrire une version récursive de cet algorithme, me permettant de tenir compte des 2 contraintes que je viens d'évoquer? Merci.

14/04/2011, 05h22
MABROUKI

algo vorace,choix min couttotal à etape i

bonjour

L'idee de base est minmiser le cout total en fin de periode.alors une implementation possible est :
variables de travail :
-N permis au total
-permis(J) J à N
-coutInitialPermis(J)
-R(J)*M Loi d'accroissement du cout en fonction du temps ou M est le ieme Mois.
-coutPermisMois(J,M)=coutInitialPermis(J)*R(J)*M, M annee d'acquisition
-dispPermis(J,M)=(0 si indisponible,1 disponible) indiquant à un mois donnee si le permis -J- est disponible au mois -M-
-AcquisPermis(J)=(1 deja acquis,0 non acquis) memorise les permis deja acquis.

Initialisation Algorithme
----------------------
initialise les permis:
BoucleInitPermis
(faire J=1 à N)
AcquisPermis(J)=1
coutInitialPermis(J)
FinBoucleInitPermis

coutTotal=0
demarrrage algo:
----------------
BoucleMois
( faire K=1 à M)
temp=0
traqueChangeTemp=0
BouclePermis
(faire J=1 à N)
SI dispPermis(J,M)=1 ET AcquisPermis(J)=0 Alors
temp=Max[temp,coutPermisMois(J,M)]
FinSi
SI traqueChangeTemp<>temp Alors
AcquisPermis(J)=1
traqueChangeTemp=temp
FinSi
FinbouclePermis
coutTotal= coutTotal+temp
FinBoucleMois

On exemine à chaque -epoque(mois) -tous les permis pour selectionner parmi les Disponibles dans ce mois en ecartant les deja Acquis le -max coutTotal Pondere- en laissant au Plus Tard l'acquisition des permis dont le cout ponderee sera le plus faible(puisque l'on choisit au Plus Tot les permis dont le cout pondere est le plus grand) .
Evidemment ce raisonnment suppose que le cout pondere d'un permis croit avec le temps.
Dans le cas contraire il faut prendre Min .
bon code...

-

Citation:
Envoyé par cProg
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 Algorithme minCout(A[1, ..., n], B[]) //A[1, ..., n]: tableau stockant, dans le désordre, les rj valeurs des coûts des n licences //B[]: tableau vide pour stocker les licences retenues pour achat TriRapide(A[1, ..., n]) //A[1, ..., n] est maintenant trié en ordre décroissant while j < n (Tant qu’il reste encore des licences à acquérir) do <div style="margin-left:40px">for i ← 1 to n (Passer en revue les coûts des licences) do <div style="margin-left:40px">if ri < ri+1 (Il s’agit de choisir d’abord la licence de plus grand coût) then A[i ] = i + 1 (acheter maintenant la licence de plus grand coût) end</div>j = j + 1 (Recherche de la prochaine licence à acquérir) end end</div>Retourne A[i ]
Normalement le nombre de licences doit diminuer au fur et à mesure que je sélectionne les licences de plus haut coût et que les stocke dans le tableau B. De plus, lorsque je passe en revue les coûts des licences, je ne dois plus parcourir le tableau A dans son entièreté. Par conséquent comment puis je écrire une version récursive de cet algorithme, me permettant de tenir compte des 2 contraintes que je viens d'évoquer? Merci.
Effectivement, il faut que tu exploites le fait que tu ton tableau est trié pour limiter les recherches du permis de cout le plus élevé. D'ailleurs si tu pars du principe qu'il faut prendre en priorité le permis dont le r est le plus élevé, ton tableau trié te donne directement l'ordre dans lequel il va falloir les acheter, non ? Reste à faire le lien entre rj et le permis j.

Pour avoir les idées bien claires, tu peux aussi commenter le rôle de chacune des variables que tu introduis.

15/04/2011, 04h37
MABROUKI

algo vorace

rebonjour
Apparement tu n'as pas saisi une chose codeur de tableau trie "statique".
Le cout des permis depend du temps -t- il est donc dynamique ,cela implique simplement que ton tableau equivaut à -12 tableaux A(si on prends 1 annee).
La "diminution" que tu entrevois n'est pas dans les elements du tableau parbleu ,c'est le nombre des choix à chaque etape qui diminue.

C'est pour cela qu'il faut un tableau à 2 entrees coutPermisMois(J,t) ,a cause de -rj- (il y a 2 variables -j pour le cout initial et -r- pour le coeff de ponderation qui lui meme depend du temps)

Quand à la recursivite elle est "abstraite" c'est dans le critere de choix qu'elle se "cache".
C'est l' arbre de decision :
-on part d'une racine "zero"
-à l'etape k il y a (k) choix à exminer
-à l'etape k+1 il y a (k-1) choix à examiner
-à l'etape finale il y k=0 choix à examiner
Ce qui peut se representer graphiquement par un arbre inverse .

bon code....
15/04/2011, 08h43
Acrim

Citation:

Envoyé par MABROUKI

rebonjour
Le cout des permis depend du temps -t- il est donc dynamique ,cela implique simplement que ton tableau equivaut à -12 tableaux A(si on prends 1 annee).

Bonjour, étant donné que les permis ont le même prix de base : si 0 <= rj < ri alors prix_permis(j,t) < prix_permis(i,t) pour tout t, avec prix_permis(i,t) le prix du permis i la t-ieme année. On peut donc ne considérer que le tableau des rj lors du choix du permis à acheter.