How can I fairly distribute identical goods bought at different prices amongst customers so that they all pay the same price?

I'm trying to allocate a product bought at different prices to different clients in a fair way. Initially, each of the $n$ client asked for a specific quantity of the product $a_1\ldots a_n$

The goods were bought in $m$ batches, every batch having a different quantity of goods $q$ which was paid a different price $p$ : $(q_1,p_1)\cdots(q_m,p_m)$

Obviously, the total quantity of items bought matches what was initially ordered $\sum a = \sum e$

I'm trying to find a matrix M(x,y) for which :

1. Each client receives the quantity of goods he ordered : $\sum M(i,y) = a_i$

2. The average price paid par each client is as close as possible to the "fair price", which is the average price of the global order $|\frac {\sum M(i,y) p_i )}{ a_i} - \frac { \sum q_m,p_m }{ \sum a_n } |= \epsilon$

What would be an efficient way of doing that? I've looked into the simplex algorithm, but I'm not sure it would be adapted in that case.

• Thank you so much for asking this question! Did you also discover this problem as part of financial order execution (filling brokerage orders for multiple accounts)? – Prashant Kumar Mar 6 '13 at 2:48

• The trick here is that you have to be accountable for each individual and indivisible unit allocated. Thus, we are still solving for the integer values of the matrix $M(x,y)$ – Prashant Kumar Mar 6 '13 at 2:52