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 :
Each client receives the quantity of goods he ordered : $\sum M(i,y) = a_i$
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.