TP Contraintes sous prolog 2

lundi 13 mars 2023
par  Emmanuel Adam
popularité : 5%

Utilisez SWI Prolog, ou GNU Prolog, ou Prolog en ligne : https://swish.swi-prolog.org/

 Cartographie et couleurs

Contraintes sur domaine fini.

Un exercice fréquent en gestion de contraintes consiste à colorer une carte composée de plusieurs régions ; avec un minimum de couleurs ; de telle façon que deux régions adjacentes ne peuvent avoir la même couleur.

Vous testerez en prenant la carte 01

carte01

solution carte 1

couleurs(L, NB):-
   L=[A,B,C,D,E,F],
   L ins 1..NB,
   A #\= B, A #\= C, A #\= E, A #\= F,
   B #\= C, B #\= D, B #\= E, B #\= F,
   C #\= D, C #\= F,
   E #\= F,
   labeling([ff],L).

Question à poser : trouver un agencement avec 4 couleurs :
couleurs(L, 4)

Puis en prenant la carte 02.

carte02

Pour cela vous utiliserez la programmation par contraintes en prolog avec la librairie clpfd

 Ordonnancement de tâches

Contraintes sur rationnels. (inspiré de Fred Mesnard)

Il s’agit de déterminer un agenda des tâches de construction d’une maison de la société ViteFaitMalFait pour minimiser le temps de construction.
Il y a dix tâches à effectuer, chacune d’elle pouvant nécessiter l’achèvement d’une ou plusieurs autres tâches :

Code Nom Durée Nécessite
a maçonnerie 7 _
b charpente 3 a
c toit 1 b
d sanitaire 8 a
e façade 2 c,d
f fenêtres 1 c,d
g jardin 1 c,d
h plafond 3 f
j peinture 2 h
k finition 1 e,g,j

Les variables a, b, ...k, auront comme valeur la date de début de la phase correspondante (b=5, signifie que la charpente débutera au jour 5).

Calculer la fin au plus tôt de la maison (en cherchant à minimiser k )

solution travaux

travaux(L):-
   L = [A,B,C,D,E,F,G,H,I,J,K],
   L ins 0..100,
        A #>=0, B #>= A+7, C #>= B+3, D #>= A+7,
        E #>= C+1, E #>= D+8,
        F #>= C+1, F #>= D+8,  
        G #>= C+1, G #>= D+8,
        H #>= F         +1, I #>= H+3,
        J #>= E + 2, J #>= G+1, J #>= I+2,
   K #>= E+1, K #>= G+1, K #>= J+1,
   labeling([ff, min(K)],L).

Question à poser : trouver les dates de début des tâches :
travaux(Dates)

 Sportives

Un journaliste arrivé en retard de la finale du 100m des JO demande le classement aux cinq sprinteuses classées en tête :

  • Aline – « je n’étais pas dernière. »
  • Bea – « Chris était troisième. »
  • Chris – « Je suis arrivée avant Aline. »
  • Dorothée – « Je ne suis pas première. »
  • Emma – « Dorothée est arrivée après moi. »

On sait que les deux premières du classement ont menti pour se moquer du journaliste.

Donnez un exemple de classement.

Exemple de solution pour les sportives

%les 2 premières mentent
dire(X, Y) :- X#\=1, X#\=2, Y, !.
%les autres non
dire(_, Y) :- #\ Y.
       

%% fonction pricipale
%% retourne Sportives : le tableau de classement
solution(Sportives) :-
        Sportives = [S1, S2, S3, S4, S5],
        Sportives ins 1..5,
        all_different(Sportives),
        dire(S1, S1 #\= 5),
        dire(S2, S3 #= 3),
        dire(S3, S1 #> S3),
        dire(S4, S4 #\= 1),
        dire(S5, S5 #< S4),
        label(Sportives).

Question à poser :
sportives(S)

 Problème de transport

Contraintes sur rationnels. (inspiré de Fred Mesnard)

Suite au dérèglement climatique, les températures ont augmenté de
10°C dans certaines régions..... Il s’agit de déterminer l’approvisionnement, en ventilateurs, des points de vente à partir d’un ensemble d’usines en minimisant les coûts de transport.

  • Les usines se trouvent à Dunkerque (U1) et à Sars-Poterie (U2).
  • Les points de vente à approvisionner sont Valenciennes (V1), Avesnes (V2) et Gravelines (V3).

La matrice des coûts de transport est :

. V1 V2 V3
U1 1 5 1
U2 6 2 9

Les stocks et la demande sont :

  • stocks : U1=4 et U2=6
  • demande : V1=3, V2=5 et V3=2

Indications : introduire 6 variables Xij représentant la quantité à
transporter entre l’usine i et le point de vente j.

Exprimer alors les contraintes sur les offres et demandes

Résoudre dans les rationnels en minimisant le transport.

 Emploi du temps

Trois enseignants (e1, e2 et e3) doivent proposer chacun deux enseignements de deux heures, en présentiel, répartis sur deux jours (j1 et j2), à trois groupes d’étudiants (g1, g2, g3).
Les créneaux sont donc des créneaux de deux heures, s’étalant sur deux jours, de 8h à 18h, avec une pause de deux heures entre 12h et 14h.
Les enseignants possèdent des contraintes horaires, prioritaires (1) et secondaires (2) :
- e1 ne peut enseigner : (1) le jour j1 de 16h à 18h ; (2) le jour j2 de 14h à 16h.
- e2 ne peut enseigner : (1) le jour j2 de 10h à 12h ; (2) le jour j1 de 16h à 18h.
- e3 ne peut enseigner : (1) le jour j1 de 14h à 16h ; (2) le jour j2 de 8h à 10h.
Les trois salles s1, s2 et s3 sont disponibles pour ces enseignements, cependant elles sont soumises elles aussi à des contraintes classées par ordre d’importance :
- la salle s1 n’est pas disponible : (1) le jour j1 de 10h à 12h,
- la salle s2 n’est pas disponible : (1) le jour j2 de 16h à 18h et (2) de 8h à 10h,
- la salle s3 n’est pas disponible : (1) le jour j2 de 16h à 18h et (2) le jour j1 de 14h à 16h.
- Seules les salles s1 et s2 possèdent un vidéo-projecteur.

Les enseignants possèdent également des contraintes matérielles ; par exemple :
- tous les enseignants veulent utiliser un rétroprojecteur au moins une fois pour chaque groupe sur les deux jours.

Ainsi, chaque groupe d’étudiant assiste à 2 enseignements pour chaque enseignant, dont au moins 1 enseignement avec un vidéo-projecteur.

Il est toléré de ne pas respecter quelques contraintes secondaires si nécessaire, en privilégiant les contraintes des enseignants par rapport aux contraintes des salles si possible.

Proposez votre solution en Prolog utilisant la bibliothèque de contraintes...