Le problème

Julie a travaillé sur un très joli problème de mathématiques.

Comment l'auriez-vous résolu ? Selon vous, y'a-t-il une autre méthode que le 'tâtonnement' ? Y'a-t-il plusieurs solutions ?

Lorsque j'ai vu ce devoir, j'ai immédiatement identifié une variante (simple) du Knapsack (= problème du sac à dos) !

Il s'agit de :

  1. maximiser le chargement du camion,
  2. respecter la contrainte des 200 Kg.

La complexité du problème augmente considérablement si :

  1. on augmente le choix de caisses (poids différents, nombre)
  2. on ajoute une contrainte de volume (volume max du camion, volume des caisses).

Trouver une solution idéale

Qui trouvera la solution consistant en un chargement optimisé en poids et en respectant le volume disponible ?

Rien de tel qu'un petit tour dans Excel (et son extension 'Solver') pour proposer une ébauche de solution, en tous cas pour le premier voyage du camion.

La construction de mon tableau Excel consiste en :

  1. une liste des caisses à disposition (types et quantités)
  2. la multiplication du nombre de caisses par leur poids et volume
  3. lister les contraintes (poids max du camion, volume max)
  4. une colonne des variables (la quantité des caisses à prendre)
  5. une cellule de l'objectif à atteindre.

Le Solveur

Excel et son solveur sera donc en charge de maximiser le poids du chargement en jouant avec la quantité des caisses (variables), tout en respectant les contraintes imposées.

Des contraintes ont été ajoutées, notamment celle indiquant que le nombre de caisses doit être entier. Ou celles qui évitent au Solver d'embarquer davantage de caisses que celles à disposition.

Pour en savoir plus: Wikipedia donnera des informations intéressantes sur le Knapsack Problem ou la même page, en français.

Le site Microsoft détaille l'utilisation du Solver.