[Solveur] Non respect des contraintes

[Amandine]

Bonjour,

Je suis étudiante et je cherche actuellement à résoudre un cas d'étude à l'aide du solveur d'Excel que je viens de commencer d'utiliser.
Voici le cas :
J'ai un camion qui doit faire plusieurs livraison en respectant des fréquences (1 par semaine, 3 par semaine, ...). Je me suis tout d'abord basée sur une semaine de collecte. J'ai donc mis une contrainte de fréquence à respecter. La présence d'une collecte est caractérisée par un "1", sinon "0". J'ai donc mis ces données en binaire.
Je sais aussi que la surface au sol dans ce camion est restreinte, j'ai donc mis une limite de chargement pour mon camion : il ne peut pas être rempli à plus de 100%.
Mon facteur à optimiser dans un premier temps est le remplissage moyen de mon camion que je veux au maximum possible.

Après avoir rentré ces différentes informations, je choisis une résolution "évolutionnaire" sinon de toute façon ça ne fonctionne pas.
J'ai essayer de mettre différents temps limites, très long parfois, mais le solveur n'arrive jamais à respecter toutes les conditions bien que je penses qu'elles ne soient pas contraignantes et laissent plusieurs réponses possibles.
J'ai l'impression qu'il cherche plus que tout à maximiser le remplissage moyen, et ce en faisant fis des contraintes.

Avez-vous aussi rencontré ce problème de non respect des contraintes? Avez-vous une solution?

Je vous joint mon petit fichier =)

Merci d'avance en tout cas

 

[ODVJ]

Re : [Solveur] Non respect des contraintes

Bonjour,

Où est le problème?
J'ai lancé ton modèle en évolutionnaire et j'obtiens un résultat cohérent (me semble-t-il) avec tes contraintes.
Le taux moyen ressort à 69.36%

Si tu modifies ton modèle, tu peux passer en simplexe avec ainsi un temps de réponse quasi immédiat.

En revanche, tu peux optimiser sur 4 jours au lieu de 5 et ainsi obtenir un taux de 86.69%

Cordialement

un complément :
les taux de 69.36% et 86.69% sont constants en fait. Ils correspondent au total livré dans la semaine divisé par (4 ou 5 * xSMaxCamion)

 

[Amandine]

Re : [Solveur] Non respect des contraintes

Pardon,

Oui c'était un premier fichier "simple"
C'est l'amélioration qui ne fonctionne pas en fait dsl.

Donc je joint le nouveau fichier. Dans ce cas, j'ai mis en place deux camions avec les mêmes contraintes que précédemment.
J'ai simplement ajouté qu'il n'est pas possible de collecter à deux endroits le même jour (et donc avec les deux camions).
J'ai cherché de même à optimiser.


Pour ce qui est que pour le premier fichier cela peut être fait un 4 jours au lieu de 5, c'était seulement un exemple qu'il faudra après que j'applique à un cas concret


Merci d'avance

 

[ODVJ]

Re : [Solveur] Non respect des contraintes

Bonsoir,

Tu vas rapidement arriver aux limites du solveur d'excel.

Dans le classeur joint, j'ai mis 3 onglets, tous en simplexe.

• Un pour la solution optimisée en nombre de jours. Le solveur déclare forfait..... "problème trop vaste" !!!!
• Un pour une solution sur 5 jours (alors qu'il y a des solutions en 3 jours)
• Le dernier, tronqué à 3 jours pour obtenir une solution optimisée en jours

Il suffit de charger les paramètres pour faire fonctionner le solveur sur chaque feuille.

Cordialement

PS : l'onglet du milieu met assez longtemps à répondre (1mn ou 2)

 

[Amandine]

Re : [Solveur] Non respect des contraintes

Bonjour,

J'ai regardé ton fichier et il fonctionne effectivement. Qu'as-tu changé exactement? Je ne comprend pas bien pourquoi mon fichier ne fonctionnait pas. Et moi si je cherche à le mettre en Simplex, il me dit "le solveur a rencontré une valeur d'erreur dans la cellule objectif ou dans une contrainte".
Qu'as-tu fait pour que cela fonctionne?

Cordialement,

Amandine

 

[ODVJ]

Re : [Solveur] Non respect des contraintes

Bonjour,

Cherche du côté des cellules fusionnées (O7:S18).
Met l'objectif en Max au lieu de valeur.
Tu peux choisir K38 ou K35 comme objectif.

cdlt

PS : et vérifie tes formules en E23:I34. De base, elles sont fausses mais en plus elles font intervenir des SI() qui rompent la linéarité.



Résultat :

Microsoft Excel 14.0 Rapport des réponses
Feuille : [Collecte camion - 2 camions-1.xlsx]Calcul (2)
Date du rapport : 7/13/2015 2:36:08 PM
Résultat : Le Solveur a trouvé une solution de nombre entier dans la plage de tolérance. Toutes les contraintes sont satisfaites.
Moteur du solveur
Moteur : Simplex PL ​
Heure de la solution : 1.67 secondes. ​
Itérations : 5 Sous-problèmes : 8 ​
Options du solveur
Temps max Illimité, Itérations Illimité, Precision 0.000001, Échelle automatique ​
Sous-problèmes max Illimité, Solutions de nombre entier max Illimité, Tolérance des nombres entiers 1%, Supposé non négatif ​
Cellule objectif (Max)
Cellule	Nom	Valeur initiale
$K$38	Moyenne	43.91%	43.91%
Cellules variables
Cellule	Nom	Valeur initiale	Valeur finale	Entier
$E$7	A Lundi	0	0	Binaire
$F$7	A Mardi	0	0	Binaire
$G$7	A Mercredi	0	0	Binaire
$H$7	A Jeudi	0	1	Binaire
$I$7	A Vendredi	0	0	Binaire
$E$8	Lundi	0	0	Binaire
$F$8	Mardi	0	0	Binaire

.................

 

[Amandine]

Re : [Solveur] Non respect des contraintes

Oui effectivement, maintenant cela fonctionne très bien!! Et la solution est quasiment instantanée dans certains cas.
Je suis cependant arrivée à saturation du nombre de cellules variables ^^

Je voudrais à présent mettre une condition qui traduirait ceci :
S'il faut collecter deux fois par semaine, alors il faut laisser deux jours entre les collectes. En gros, deux "1" doivent être séparés par deux "0".
Mais je ne sais pas comment faire, car il semble qu'il ne soit pas possible de mettre des "formules" dans les contraintes

 

[ODVJ]

Re : [Solveur] Non respect des contraintes

Bonjour,

tu étudies dans quel domaine et à quel niveau?
généralement on commence avec glpk puis on passe sur Cplex ou équivalent.

cordialement

 

[Amandine]

Re : [Solveur] Non respect des contraintes

Bon finalement je viens de trouver comment faire : une espèce de somme glissante sur 3 jours de la semaine qui doit constamment être égale à 1.

Cependant, la encore mon problème est trop "vaste", j'ai trop de cellules et de contraintes.
N'y as-t-il pas un moyen de passer outre et de dépasser cette limite (même si je pense bien que non...)

 

[Amandine]

Re : [Solveur] Non respect des contraintes

Je suis en école d'ingénieur
Que sont "glpk" et "cplex"??

 

[ODVJ]

Re : [Solveur] Non respect des contraintes

Ce sont des solveurs.
Le premier est gratuit et performant le second est commercial et trés performant et sur des domaines de résolution plus vastes que le premier.

Pour intégrer la nouvelle contrainte des 2 jours d'écart, il faut peut-être changer le modèle de données.

Es-tu tenue à l'utilisation d'excel et de son solveur?

 

[Amandine]

Re : [Solveur] Non respect des contraintes

Pour la contrainte de 2 jours d'écart, ce que j'ai fait fonctionne mais me rajoute des cellules à contraindre. Qu'entends tu par "changer le modèle de données"?

A quel autre logiciel penses tu pour optimiser ce cas d'étude?

 

[ODVJ]

Re : [Solveur] Non respect des contraintes

Bonjour,

Tu ne réponds pas à ma question : es-tu obligée d'utiliser le solveur d'excel?
Ensuite, je ne sais pas si ce qu'on te demande c'est de sortir une solution, de dénombrer les solutions.
Enfin, comme tu délivres les infos progressivement, je crains que tu ne sortes une contrainte supplémentaire qui oblige à revisiter le modèle.

Il faut savoir que dans l'état de ton problème, il n'y a pas encore d'explosion combinatoire.
Il est possible de trouver les solutions avec du code VBA et des données réarrangées pour limiter les boucles.
C'est pour cela que je te parlais de changer de modèle de données.
Symétries mises à part, j'ai trouvé 29 853 solutions à ton problème sur les 494 325 combinaisons testées (c'est mieux que 2^60 combinaisons).
J'ai simplement intégré les contraintes dans les données. C'est ce que j'appelais changer le modèle.
Je te laisse regarder le classeur xlsm en pièce jointe, onglet calcul(2)

Sinon, je n'ai pas testé, mais GLPK devrait faire l'affaire. Mais es-tu libre d'utiliser n'importe quel logiciel?

cordialement

 

[ODVJ]

Re : [Solveur] Non respect des contraintes

Bonjour,

Une solution avec GLPK.
Je te conseille de télécharger Gusek (GUSEK) et de le décompresser dans un dossier de ton choix.
Tu lances ensuite gusek.exe et tu arrives dans l'interface utilisateur.
Quelques paramétrages :

• Options\vertical Split
• Tools\use external data
• Tools\generate output file on go
• View\output

Tu crées 2 fichiers (menu fichier etc...),

l'un que tu nommeras collecte_2_camions.dat (ce sont les datas) et dans lequel tu colles les données suivantes :

data;
set Jours := Lundi Mardi Mercredi Jeudi Vendredi;
set triplet1:= Lundi Mardi Mercredi;
set triplet2:= Mardi Mercredi Jeudi;
set triplet3:= Mercredi Jeudi Vendredi;
set Sites := A B C D E F;
param collCible :=     A     2    B     1    C     1    D     2    E     2    F     3;
param surfHebdo := A 81092 B 19200 C 38400 D 19200 E 11511.5 F 24955.75;
param surfMaxCamion := 81092;
set Camions := Camion1 Camion2;

end;

l'autre que tu nommeras collecte_2_camions.mod (c'est le modèle) et dans lequel tu colles les données suivantes :

#Fichier collecte_2_camions.mod  

#Jours dans la semaine     
    set Jours;
    set triplet1;
    set triplet2;
    set triplet3;
#display nbJours,Jours,triplet1,triplet2,triplet3;

#Sites
    set Sites;

#tableau des collectes cibles hebdo par Site
    param collCible{i in Sites};
#display collCible;

#tableau des surfaces camion équivalentes à une semaine de livraisons par Site
    param surfHebdo{i in Sites};
#display surfHebdo;

#surface maxi d'un camion     
    param surfMaxCamion;
#display surfMaxCamion;

#camions     
    set Camions;
#display Camions;

#matrice de collecte
    var Collecte{i in Sites, j in Jours, k in Camions} binary;

#************* objectif ********************
#la somme sur tous les sites des (1 pour un site multipliée par la surface hebo du site) doit être maximal
    maximize surfaceTotaleHebdo:    sum{i in Sites, j in Jours, k in Camions} Collecte[i,j,k]*surfHebdo[i];
#************* fin objectif ********************

#************* contraintes ********************
# 1) une seule livraison pour un jour et un site
    s.t.    uniciteCamionSiteJour{i in Sites, j in Jours}:
            sum{k in Camions}Collecte[i,j,k],<=1;

# 2) la capacité d'un camion ne peut etre dépassee dans une tournee
    s.t.    capaciteCamionJour{j in Jours, k in Camions}:
            sum{i in Sites} Collecte[i,j,k]*surfHebdo[i],<=surfMaxCamion;

# 3) 2 jours de repos entre 2 livraisons
    s.t.    JoursdeRepos1{i in Sites, k in Camions}:
            sum{j in triplet1} Collecte[i,j,k],<=1;
    s.t.    JoursdeRepos2{i in Sites, k in Camions}:
            sum{j in triplet2} Collecte[i,j,k],<=1;
    s.t.    JoursdeRepos3{i in Sites, k in Camions}:
            sum{j in triplet3} Collecte[i,j,k],<=1;

# 4) le nombre de livraisons pour un site i doit correspondre à la cible collCible[i]
    s.t.    livraisonSite{i in Sites}:
            sum{j in Jours, k in Camions} Collecte[i,j,k],=collCible[i];

solve;

end;

sur le fichier modèle, tu vas dans tools\Compile pour vérifier que tout va bien (fenêtre de droite) et ensuite tu fais tools\go pour générer le fichier résultat collecte_2_camions.out dans lequel tu trouves le tableau :

No. Column name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 Collecte[A,Lundi,Camion1]
* ____________________________ 0 ____0 _____1
2 Collecte[A,Lundi,Camion2]
* _____________________________1 ____0 _____1
3 Collecte[A,Mardi,Camion1]
* ____________________________ 0 ____0 ____ 1
4 Collecte[A,Mardi,Camion2]
* ____________________________ 0 ____0 _____1
5 Collecte[A,Mercredi,Camion1]
* ____________________________ 0 ____0 _____1
6 Collecte[A,Mercredi,Camion2]
* _____________________________0 ____0 _____1
7 Collecte[A,Jeudi,Camion1]
* _____________________________1 ____0 _____1
8 Collecte[A,Jeudi,Camion2]
* ____________________________ 0 ____0 _____1
9 Collecte[A,Vendredi,Camion1]
* _____________________________0 ___ 0 _____1
10 Collecte[A,Vendredi,Camion2]
* ____________________________ 0 ____0 _____1
11 Collecte[B,Lundi,Camion1]
* ____________________________ 0 ___ 0 ____ 1
12 Collecte[B,Lundi,Camion2] ...................
.........................................................

que tu remets en forme sur excel

__L M M J V
A 0 0 0 1 0 camion1
__1 0 0 0 0 camion2
B 0 0 0 0 0 camion1
__0 0 0 0 1 camion2
C 1 0 0 0 0 camion1
__0 0 0 0 0 camion2
D 1 0 0 0 0 camion1
__0 0 0 0 1 camion2
E 0 1 0 0 0 camion1
__0 0 0 0 1 camion2
F 0 0 1 0 0 camion1
__0 1 0 0 1 camion2

pour le tester dans l'onglet Calcul (2) avec un copier/coller valeur dans la zone E7:I18 et vérifier le respect des contraintes.

Cordialement

 

[Amandine]

Re : [Solveur] Non respect des contraintes

Bonjour,

En fait j'ai utilisé Excel parce que c'est le premier logiciel auquel j'ai pensé pour son solveur et que par la suite je peux extraire les résultats au format pdf facilement par exemple ou retraiter les données obtenus dans Excel même.

Je vais cependant me pencher sur le cas de glpk pour voir si c'est plus simple.

Merci pour tout ton détail! Je penses que ca va m'aider à le prendre en main

Cordialement