1. Définition du problème

Un marchand achète des pommes le matin et les vend sur le marché l'après-midi. Comme il achète à différents producteurs, il se retrouve avec des prix différents. Il range donc ses pommes par origine, dans des caisses différentes. Ainsi, s'il a acheté 7 pommes à Alain au prix unitaire de 14 cents et 12 à Bernard à 11 cents, il met sur son étalage une caisse avec les pommes provenant d'Alain et une avec achetée à Bernard.
Il se pose alors la question de comment attribuer ces pommes à ses clients. Doit il laisser le premier client arrivé acheter les pommes les moins chères ou doit-il répartir équitablement les pommes entre tous ses clients du jour ? Et comment doit-il faire s'il y a plus de pommes que ce que demande les clients, ou l'inverse ?
Il met donc au point différents algorithmes pour les étudier avant de faire son choix.
Une banque doit distribuer à intervalles réguliers des pièces d'or à ses clients. A chaque échéance, elle possède un certain nombre de caisses contenant des pièces d'or. Les caisses n'ont pas forcément la même contenance. D'un autre côté, plusieurs clients viennent réclamer des sommes différentes.
L'attribution consiste à définir l'ensemble des transactions qui permet satisfaire les clients. Chaque transaction consiste à prendre des pièces dans une caisse et de les donner à un client. Le but de la banque est double :

2. Le cas trivial

Supposons que l'on ait n clients réclamant respectivement q_1, q_2, \ldots, q_n pièces d'or. D'autre part, la banque possède n caisses contenant respectivement q_1, q_2, \ldots, q_n pièces.
On aura alors seulement n transactions :

3. Montants différents

Il peut arriver que la somme de ce qui est réclamé par les clients soit différente de la somme des pièces contenues dans les caisses. Dans ce cas, avant d'effectuer l'attribution, il faut réduire les quantités de la partie excédentaire au prorata des quantités initiales.
L'algorithme suivant permet de réaliser cette répartition au plus juste : 
# -*- coding: utf-8 -*-
import math

def reduce(E, q):
    Q = 0
    n = len(E)
    parts = [0]*n
    for i in range(n):
        Q += E[i]
    for i in range(n - 1):
        part = math.floor(0.5 + q*E[i]/Q)
        parts[i] = part
        q -= part
        Q -= E[i]
    parts[n - 1] = q
    return parts
Pages : 1 2
Attribution
22 mai 2013
Sommaire général