Problème de l'achat par lots

Problème de l'achat par lots

[alphablock]

Bonsoir à tous les chameliers,


J'ai défini un type "inventaire" qui est une liste de paires
(quantité,pièce) ainsi que 2 opérations de base. Les listes sont triées
selon le nom des pièces. La 1ère opération réalise l'union de deux
inventaires, la 2nd opération réalise la différence de deux inventaires et
renvoit une paire de listes (pièces restantes,pièces manquantes) :


type inventory = (int * string) list;;

let rec union_inventory (a:inventory) (b:inventory) =
  match a,b with
  | [],_ -> b
  | _,[] -> a
  | (qa,pa as ha)::ta,(qb,pb as hb)::tb ->
      if pa < pb then ha::(union_inventory ta b)
      else if pa > pb then hb::(union_inventory a tb)
      else (qa+qb,pa)::(union_inventory ta tb);;

let rec difference_inventory (a:inventory) (b:inventory) =
  match a,b with
  | [],_ -> [],b
  | _,[] -> a,[]
  | (qa,pa as ha)::ta,(qb,pb as hb)::tb ->
      if pa < pb then
        let r,m = difference_inventory ta b
        in  ha::r,m
      else if pa > pb then
        let r,m = difference_inventory a tb
        in  r,hb::m
      else
        let r,m = difference_inventory ta tb in
        if qa < qb then r,(qb-qa,pa)::m
        else if qa > qb then (qa-qb,pa)::r,m
        else r,m;;


Maintenant je voudrais implémenter une opération plus complexe. 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) ?

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 ?

merci de votre aide,

- damien

web page: http://perso.wanadoo.fr/alphablock/

Re: Problème_de_l'achat_par_lots

[Diego Olivier Fernandez Pons]

    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