Optimisation combinatoire

[Anonyme]

bonjour,

j'essaye de résoudre ce problème depuis quelques heures et là franchement je bloque, si quelqu'un aurait une idée ce serait sympa.
Merci.


On se donne une suite de n taches. On conna;)t pour chaque tache i sa
duree pi lorsqu’elle est effectuee par une machine de vitesse 1. Ces taches
doivent etre effectuees dans l’ordre 1, 2, . . . n par une machine qui peut etre
plus ou moins rapide selon la quantite d’energie qu’on depense.
On dispose de K vitesses differentes et entieres 1<=v1<=......<=vk. A chaque vitesse vj correspond deux coefficents bj (cout fixe) et cj (cout
variable), de sorte que chaque tache i, lorsqu’elle est effectuee a vitesse vj
dure pi/vj et coute en energie cjpi + bj .
On cherche a associer a chaque tache une vitesse de la machine, de sorte
que la duree totale de l’ensemble des taches ne depasse pas une valeur donnee D et la depense totale d’energie soit minimale.


1 Modeliser ce probleme a l’aide d’un programme mathematique.
2 Decrire le modele associe aux donnees num´eriques suivantes :
Taches :

i 1 2 3 4 5 6
pi 3 1 2 2 4 3

vitesses :
j 1 2 3
vj 1 2 4
bj 1 2 3
cj 1 3 5

D = 7