Corrigé de l'exercice 1 : Retour de monnaie
On définit le CSP (X,D,C) tel que
- X = {XE2, XE1, XC50, XC20, XC10}
où XE2 désigne le nombre de pièces de 2 Euros à retourner, XE1 désigne le nombre de pièces de 1 Euro à retourner, ...
- Les domaines spécifient que la quantité de pièces retournées, pour un type de pièce donné, est comprise entre 0 et le nombre de pièces de ce type que l'on a en réserve :
D(XE2) = {0,1,...,E2}
D(XE1) = {0,1,...,E1}
D(XC50) = {0,1,...,C50}
D(XC20) = {0,1,...,C20}
D(XC10) = {0,1,...,C10}
- Les contraintes spécifient que la somme à retourner doit être égale à la somme insérée moins le prix à payer :
C = { 200*XE2 + 100*XE1 + 50*XC50 + 20*XC20 + 10*XC10 = T-P }
Dans cette modélisation, nous avons utilisé une contrainte
arithmétique linéaire sur les entiers. Cette contrainte est globale dans le sens
où elle fait intervenir toutes les variables du problème. Une autre modélisation
possible consisterait à définir le domaine des variables par l'ensemble des entiers
positifs ou nuls, et d'ajouter en contraintes que la quantité de pièces retournées doit
être inférieure ou égale au nombre de pièces en réserve (pour chaque type de pièce différent).
Pour exprimer le fait que l'on souhaite que le distributeur rende le moins de
pièces possibles, on pourrait ajouter à ce CSP une fonction "objectif" à minimiser
f(X) = XE2 + XE1 + XC50 + XC20 + XC10
Dans ce cas, résoudre le CSP revient à chercher une affectation de X complète et consistante qui minimise f(X).