CHAPITRE 15 (BONUS) Jeux et casse-tête 15.1 Introduction Les applications de la
CHAPITRE 15 (BONUS) Jeux et casse-tête 15.1 Introduction Les applications de la programmation linéaire n’échappent pas aux jeux et aux énigmes. Ce chapitre présente trois applications amusantes, dont une bien connue. Pour certains de ces problèmes, il n’y a pas de fonction-objectif, ou alors elle est sans objet. Le but de la résolution est de trouver une solution satisfaisant un ensemble de contraintes particulières correspondant à l’énoncé. Les problèmes 15.2 et 15.3 sont deux des nombreux problèmes de la page Web de Martin Chlond (http://www.chlond.demon.co.uk/academic/puzzles.html). Cette page web présente aussi les solutions formulées à l’aide du langage de modélisation Mosel de FICO (il s’agit du langage associé au solveur XPRESS). On trouvera dans ce chapitre un jeu de grille et de jetons que l’on peut résoudre à la main, un partage équitable et difficile de tonneaux de vins et, pour finir, le problème très connu des n reines. 15.2 Grille et jetons 15.2.1 Problème Partant de la grille carrée de taille 4 × 4 recouverte par seize jetons de la figure 15.1, comment enlever six jetons en laissant un nombre pair de jetons dans chaque ligne et chaque colonne de la grille ? 2 _____________________________________________ Programmation linéaire avec Excel Figure 15.1 – Grille de départ 15.2.2 Modélisation La constante n représente le nombre de jetons maximal que l’on peut placer en colonne ou en ligne. P désigne le nombre de jetons à laisser sur la grille. Une variable binaire xij est fixée à 1 si la case (i,j) est couverte par un jeton, 0 sinon. Sur la grille finale, P jetons doivent être positionnés, contrainte (1). ∑∑ = = = n i n j ij P x 1 1 ) 1 ( Pour vérifier qu’il y a un nombre pair de jeton par ligne ou par colonne, deux types de variables qui représentent la demi-somme des jetons sont nécessaires. NLi (resp. NCi) représente la moitié de la somme des jetons de la ligne i (resp. de la colonne i). Pour être sûr d’obtenir un nombre de jetons pair, il suffit que ces deux types de variables soient entiers. Les contraintes (2) et (3) permettent d’exprimer ces demi-sommes pour les lignes et les colonnes. Les contraintes (4), (5) et (6) définissent le domaine d’appartenance des variables. Comme il a été mentionné en introduction de ce chapitre, il n’y a pas de fonction- objectif pour ce problème, mais seulement un ensemble de contraintes à satisfaire. { } N I NC n j N I NL n i x n j n i NC x n j NL x n i P x j i ij n i j ij n j i ij n i n j ij ∈ = ∀ ∈ = ∀ ∈ = ∀ = ∀ = = ∀ = = ∀ = ∑ ∑ ∑∑ = = = = : 1 ) 6 ( : 1 ) 5 ( 1 , 0 : 1 , 1 ) 4 ( . 2 : 1 ) 3 ( . 2 : 1 ) 2 ( ) 1 ( 1 1 1 1 K K K K K K Chapitre 15 (bonus) – Jeux et casse-tête ________________________________________ 3 15.2.3 Traduction en Excel Le classeur C15-Jetons contient la feuille de calcul qui traduit le modèle mathématique en Excel. La feuille est organisée de la façon suivante. Le premier bloc va servir à vérifier le nombre de jetons à laisser sur la grille et le nombre de jetons actuellement présents sur la grille. Le tableau suivant présente la grille avec les cellules B7:E10 qui seront les variables xij. Pour chaque colonne et chaque ligne de cette grille, nous avons rajouté les informations sur le nombre de jetons présents, une variable correspondant à NLi ou NCj et une cellule qui sera le double de la variable précédente. Les formules de la feuille sont alors les suivantes : Nombre de jetons sur la grille. La cellule C4 reçoit la formule "=SOMME(B7:E10)". Nombre de jetons par ligne et par colonne. La cellule G7 reçoit la formule "=SOMME(B7:E7)" qui compte le nombre de jetons dans la ligne courante. Cette formule est recopiée dans les cellules G8:G10. La cellule B12 reçoit la formule "=SOMME(B7:B10)" qui compte le nombre de jetons par colonne. Cette formule est étendue aux cellules C12:E12. L’ensemble de ces formules correspond aux membres de gauche des contraintes (2) et (3). Nombre pair de jetons par ligne et colonne. La formule "=2*H7" est placée dans la cellule I7 et recopiée dans les cellules I8:I10. De même la formule "=2*B13"est placée en B14 et recopiée en C14:E14. Ces formules correspondent aux seconds membres des contraintes (2) et (3). Il reste maintenant à mettre en place les informations de la boite de dialogue du solveur. Pour ce problème, il n’y a pas de cellule cible puisqu’il n’y a pas d’objectif. Ceci est parfaitement autorisé par le solveur, qui va se contenter de trouver une solution vérifiant toutes les contraintes. Les cellules variables sont les cellules de la grille B7:E10 (variables xij), les cellules H7:H10 (variables NLi) et les cellules B13:E13 (variables NCj). 4 _____________________________________________ Programmation linéaire avec Excel La première ligne dans le bloc des contraintes correspond aux contraintes (3). La seconde ligne impose aux variables NCj d’être entières, contrainte (6), la troisième ligne aux variables xij d’être binaires, contrainte (4) et la quatrième ligne contraint le nombre de jetons qu’il devra rester sur la grille au final, contrainte (1). La cinquième ligne correspond aux contraintes (2) et la dernière ligne aux contraintes (5). Comme d’habitude, il ne faut pas oublier d’activer les options du solveur : Modèle supposé linéaire et Supposé non-négatif. 15.2.4 Résultats La résolution Excel est immédiate. La grille présentée dans la feuille Excel permet de visualiser le placement des jetons rapidement (une cellule avec 1 correspond à la présence d’un jeton et avec 0 à l’absence de jeton). Cette solution est représentée sur la figure 15.2, mais elle n’est pas unique : il en existe d’autres pouvant se déduire par symétrie ou permutations de lignes ou de colonnes. Figure 15.2 – Solution de l’énigme Chapitre 15 (bonus) – Jeux et casse-tête ________________________________________ 5 15.3 Les tonneaux de vins 15.3.1 Problème Un fermier décide de vider sa cave avant de vendre ses terres et prendre sa retraite. Sans enfants, il décide tout de même de partager ses 46 tonneaux de vin entre ses 5 neveux. Sur les 45 premiers tonneaux, 9 sont pleins, 9 aux trois-quarts pleins, 9 à moitié plein, 9 pleins au quart et 9 sont vides. D’où cinq taux de remplissage différents. Le dernier tonneau est rempli d’un très bon vin qu’il désire céder au plus intelligent de ses neveux. Il le cédera donc à celui qui saura partager le vin des 45 premiers tonneaux de façon que les neveux repartent chacun avec le même nombre de tonneaux et le même volume de vin. Il ajoute deux difficultés supplémentaires : les nombres de tonneaux alloués à chaque neveu et ayant le même taux de remplissage doivent être tous différents, et chaque neveu doit avoir au moins un tonneau de chaque taux ! 15.3.2 Modélisation Le nombre de neveux est noté n et le nombre de tonneaux de types différents noté T. Un ensemble de constantes rt représente les différents remplissages des tonneaux, r1 correspondra aux tonneaux pleins, r2 aux tonneaux pleins aux trois-quarts, etc. Les constantes auront donc les valeurs suivantes : r1 = 1, r2 = 0,75, r3 = 0,5, r4 = 0,25 et r5 = 0. Des variables xit préciseront le nombre de tonneaux de type t que recevra le neveu i. Chaque neveu va recevoir neuf tonneaux (contrainte (1)) et les neuf tonneaux de chaque type doivent trouver preneur (contrainte (2)). 9 : 1 ) 2 ( 9 : 1 ) 1 ( 1 1 = = ∀ = = ∀ ∑ ∑ = = n i it T t it x T t x n i K K Le partage doit être équilibré en termes de volume de vin. Chacun des neveux doit donc recevoir l’équivalent de quatre tonneaux et demi en vin. La contrainte (3) permet de vérifier cet équilibre dans la distribution. 5 , 4 : 1 ) 3 ( 1 = × = ∀ ∑ = T t it t x r n i K La dernière difficulté ajoutée par le fermier est exprimée par deux contraintes (4) et (5). Elle nécessite l’introduction de coefficients c1 à c5 qui ont les valeurs 10 000, 1 000, 100, 10 et 1. L’idée de la contrainte (4) est de réaliser le produit scalaire pi du vecteur des coefficients et du vecteur du nombre de tonneaux de différents types pour un neveu i. La contrainte (5) créé ensuite un ordre entre les différents produits scalaires, en imposant qu’il y ait au moins une unité de différence entre deux produits scalaires. La contrainte (6) impose aux variables xit d’être entières et comprises entre 1 et 5. 6 _____________________________________________ Programmation linéaire avec Excel { } 0 : uploads/Voyage/ chapitre-15-bonus-400dpi.pdf
Documents similaires
-
20
-
0
-
0
Licence et utilisation
Gratuit pour un usage personnel Attribution requise- Détails
- Publié le Jan 19, 2022
- Catégorie Travel / Voayage
- Langue French
- Taille du fichier 0.2372MB