Re: Problème_de_l'achat_par_lots

[Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@etu.upmc.fr>]

    Bonjour,

Damien a écrit :

> Soit un inventaire recherché par un achateur, et soit une liste de
> lots-inventaires en vente. L'acheteur veut maximiser son
> investissement, c'est-à-dire avoir le moins de pièces manquantes
> possible et le moins de pièces supperflues possible. Comment trouver
> la (les) combinaison(s) de lots la (les) plus avantageuse(s) ?

Désolé de ne répondre que maintenant, j'ai n'ai pas vu le message
initial passer, ce n'est qu'en fouillant dans les archives que je suis
tombé dessus.

> Je ne vois pas bien comment il faut aborder le problème:
> * est-ce un "backpack problem" ?
> * est-ce un "union-find problem" ?
> * est-ce un "genetic-oriented problem" ?
> * sinon qu'est-ce que c'est ?


Il y a deux problèmes dans votre question :

i) le permier est un problème d'optimisation (quel est le problème a
résoudre ? avec quel type de méthode ?)

ii) le second est un problème d'implantation (comment implémenter en
Caml la méthode choisie en i)


i. Le problème d'optimisation

Votre problème est en gros un problème de "covering". Dans un problème
de covering on cherche à minimiser le coût total d'achat sachant qu'on
veut satisfaire (couvrir) la demande.

Dans votre problème on ne cherche pas à satisfaire toute la demande,
mais une sorte de distance (somme de excédents et des déficits) et on
divise par le coût.

plusieurs méthodes :
- programmation linéaire en nombres entiers (PLNE)
- énumération implicite, programmation par contraintes (PPC)

Si vous n'êtes pas familier avec la PLNE, il vaut mieux ne pas choisir
cette méthode, surtout si vous voulez implémenter ensuite en Caml
(c'est compliqué et ça utilise plein de flottants).

ii. Implémentation en Caml d'une méthode d'énumération implicite

Il énumérer intelligement toutes les combinaisons possibles. Pour
cela, il faut un mécanisme de réversibilité qui s'obtient facilement
en Caml par
- des appels de fonctions récursives
- des structures de données persistantes (librairie standard)
- des exceptions

J'avais donné un exemple pour le subset sum (trouver un sous-ensemble
d'éléments ayant une somme fixe S) dans comp.lang.functional
(Backtracking in Haskell), code à la fin du message.

la procédure de base est simple :
- on prend le premier lot
- on essaye en l'ajoutant au panier (appel récursif fonction)
- on essaye en l'interdisant dans le panier (appel récursif fonction)

Dans chaque sous-cas on fait des calculs pour éliminer le plus de lots
dont l'ajout au panier ne sert à rien (par exemple touts les demandes
ont été satifaites) ou ajouter ceux qui sont nécessaires.

Quand on aboutit à une impasse, on lève une exception.

Le code risque d'être un peu plus complexe que pour le subset-sum mais
les principes sont les mêmes.


(* Code pour le subsetsum problem *)

exception Fail

let rec subsetsum = fun remaining candidates ->
  match remaining with
   | 0 -> []
   | _ ->
      match candidates with
        | v :: tail when v <= remaining ->
           (try
                v :: subsetsum (remaining - v) tail
            with Fail ->
                subsetsum remaining tail
           )
        | _ -> raise Fail

# subsetsum 40 [3;8;9;13;12;15;17;19];;
- : int list = [3; 8; 14; 15]

        Diego Olivier