alecail | Salut,
Si l'OP est encore interesse..
C'est un problème classique de recherche opérationnelle.
http://en.wikipedia.org/wiki/Assignment_problem
(la version en francais est un stub)
C'est soluble facilement avec glpsol de GLPK: il y a plein d'exemples sur:
http://www.ibm.com/developerworks/ [...] y/l-glpk1/
J'avais dans ma base de code un modèle semblable:
Code :
- set EMPLOYES;
- set RAYONS;
- /* parameters */
- param Pref {i in EMPLOYES, j in RAYONS};
- param Contrat {i in EMPLOYES};
- param BesoinRayon {j in RAYONS};
- #horaires = temps sur chaque poste dans chaque
- var Horaires {i in EMPLOYES, j in RAYONS} >= 0;
- # maximize HoraireOptimal: sum{i in EMPLOYES, j in RAYONS} Horaires[i,j];
- #### le minimum pour que ca marche
- maximize ConfortHoraireOptimal: sum{i in EMPLOYES, j in RAYONS} Horaires[i,j] * Pref[i,j];
- #### prend en compte les preferences des employes pour chaque poste
- # minimize ConfortHoraireOptimal: sum{i in EMPLOYES, j in RAYONS} Horaires[i,j] * Pref[i,j];
- #### favorise la decouverte de nouveaux horizons pour les employes! (emmerdement maximum...)
- #### noter le maximize --> minimize
- s.t. constrRayon {r in RAYONS} : sum{e in EMPLOYES} Horaires[e,r] >= BesoinRayon[r];
- s.t. constrEmploye{e in EMPLOYES} : sum{r in RAYONS} Horaires[e,r] <= Contrat[e];
- solve;
- display{i in EMPLOYES, j in RAYONS}: Horaires[i,j];
- data;
- set EMPLOYES := Kevin Sophie Fernand;
- set RAYONS := Telephone Maison Livres;
- #heures travaillees:
- param Contrat:=
- Kevin 35
- Sophie 15
- Fernand 35;
- # Heures necessaires:
- param BesoinRayon:=
- Telephone 35
- Maison 25
- Livres 25;
- param Pref (tr):
- Kevin Sophie Fernand :=
- Telephone 3 1 2
- Maison 2 2 1
- Livres 1 3 3;
- end;
|
Résolution: (besoin du programme glpsol fourni avec GLPK, The GNU Linear Programming Kit.)
Code :
- $ glpsol --math assignementProblem.mod
- GLPSOL: GLPK LP/MIP Solver, v4.43
- Parameter(s) specified in the command line:
- --math assignementProblem.mod
- Reading model section from assignementProblem.mod...
- Reading data section from assignementProblem.mod...
- 54 lines were read
- Generating ConfortHoraireOptimal...
- Generating constrRayon...
- Generating constrEmploye...
- Model has been successfully generated
- GLPK Simplex Optimizer, v4.43
- 7 rows, 9 columns, 27 non-zeros
- Preprocessing...
- 6 rows, 9 columns, 18 non-zeros
- Scaling...
- A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00
- Problem data seem to be well scaled
- Constructing initial basis...
- Size of triangular part = 6
- 0: obj = 0.000000000e+00 infeas = 8.500e+01 (0)
- * 5: obj = 2.200000000e+02 infeas = 0.000e+00 (0)
- * 6: obj = 2.200000000e+02 infeas = 0.000e+00 (0)
- OPTIMAL SOLUTION FOUND
- Time used: 0.0 secs
- Memory used: 0.1 Mb (134225 bytes)
- Display statement at line 29
- Horaires[Kevin,Telephone] = 35
- Horaires[Kevin,Maison] = 0
- Horaires[Kevin,Livres] = 0
- Horaires[Sophie,Telephone] = 0
- Horaires[Sophie,Maison] = 15
- Horaires[Sophie,Livres] = 0
- Horaires[Fernand,Telephone] = 0
- Horaires[Fernand,Maison] = 10
- Horaires[Fernand,Livres] = 25
- Model has been successfully processed
|
Et en variant la fonction objectif:
Code :
- Horaires[Kevin,Telephone] = 10
- Horaires[Kevin,Maison] = 0
- Horaires[Kevin,Livres] = 25
- Horaires[Sophie,Telephone] = 15
- Horaires[Sophie,Maison] = 0
- Horaires[Sophie,Livres] = 0
- Horaires[Fernand,Telephone] = 10
- Horaires[Fernand,Maison] = 25
- Horaires[Fernand,Livres] = 0
|
Excel possède sûrement un solver LP. Il te suffit de regarder comment créer des contraintes et fixer la fonction objectif et d'adapter ma méthode, mais ce n'est pas forcement trivial.
--
al
|
