How to calculate optimal suppliers and order quantity?

Question

Algorithms

There is a conditional array of data with prices of suppliers and quantities in stock, the first element in the prices array is priceBreak where the key is the minimum order quantity, and the value is the price per joke.
We need an algorithm or a hint on how best to implement it to find the best suppliers and the optimal quantity for ordering from a single person according to the requested quantity

$priceLists = [
        [
            'id' => 3,
            'stock' => 10000,
            'prices' => [
                10 => 40,
                25 => 30,
                50 => 20
            ]
        ],
        [
            'id' => 4,
            'stock' => 12000,
            'prices' => [
                1 => 51,
                10 => 41,
                25 => 31,
                50 => 19
            ]
        ],
        [
            'id' => 6,
            'stock' => 2000,
            'prices' => [
                1 => 51,
                10 => 39,
                25 => 29,
                50 => 18
            ]
        ],
        [
            'id' => 9,
            'stock' => 70,
            'prices' => [
                5 => 50,
                10 => 38,
                25 => 28,
                50 => 16
            ]
        ]
    ];


$requestedQuantity = 40;


/** 
 * @return array
*/
function getBestPricesQuantity($priceLists,  $requestedQuantity) {

}

Expect to get a truncated, modified array with a new quantity key in each element

Answer 1

I came up with a solution through dynamic programming.
Assumption - prices for each supplier do not increase with an increase in the number of orders. Otherwise, this is some kind of nonsense, not suppliers.
The key observation is that if there is some answer (distribution of orders by suppliers), then among all active suppliers there is always one, whose current price is minimal. You can throw off goods to him from the rest, until we hit the limit of switching prices for them. At the same time, the price of this supplier may also improve. The total will only improve from this. If we run into the stocks of this supplier, then we can exclude him from consideration and repeat the operation. Thus, only by improving the answer, we will come to the conclusion that some suppliers sell their entire stock, some one sells some (and its price is less than all the remaining ones). All the rest sell exactly the minimum quantity for some price (key from the input). You can add the option => <last price> to the array of prices for each supplier, if there is no such entry. And also write 0 => 0 in the beginning there (buy 0 for 0). Then everything is still simplified - all suppliers, except for one, sell exactly some of their priceBreak pieces.
This simple reasoning tells us that it is possible to search for the optimal answer only among those described above. Because any option can be reduced to this, perhaps even improving it.
This can already be reduced to something like the knapsack problem. Iterate over one special supplier (who will sell a non-fixed number of items). Eliminate him from the supplier array (but remember his prices so you can calculate how much he'll have to pay for the rest).
Now, as in the knapsack problem, consider dynamic programming DP(i,j) - what is the minimum price to get exactly i pieces from the first j customers (and each sells exactly some priceBreak).
The base is trivial: DP(0,0) = 0, DP(i>0, 0) = infinity(in practice - a large number, or -1, and this value must be checked separately when passing).
Transition:

DP(i,j) = min_{k : priceBreak[j][k]<=i} DP(i-priceBreak[j][k], j-1) + priceBreak[j][k]*cost[j][k]

Here we just iterate over how much the last supplier sells. We take the remaining ones from the previous (DP(...,j-1) and add how much we will pay the last one.
Here, you calculated the DP. Now the answer is min_{i <= n, i <= stock} DP(n-i,m) + (i)*cost(i). Iterate over how much you will buy from a special supplier. Take the rest from dynamic programming.
If the suppliers are M , you need to buy N pieces, from each supplier at K prices, but this solution will be O(M*(M*N*K + N)) in time and O(M*N) in memory.(Actually, you can refine time estimate - O(M*(M*N+N*L+N)), where L is the total number of entries in the price arrays for all suppliers)
To restore the answer, along with DP(), remember which value of k produced the best result.Then it will be possible to unwind the optimal answer from the end, giving a known value to the last supplier.
If the prices of suppliers can increase with an increase in quantity, then the solution remains valid, only it is necessary to add elements with a quantity 1 less than each priceBreak to each "quantity => price" array. Because now, in any answer, it will still be possible to transfer from one customer to another, until it is stubborn either in priceBreak from above, or in the last quantity with an unchanged price. And again it turns out that only one supplier will sell a value that is not fixed in the array.
You can use the simplex method instead of DP, as Philipp already wrote (it will be faster if there are few suppliers, and the number of pieces is very large).
Perhaps, it is possible to speed up the solution by M times, if instead of M different DPs, we drive one with all suppliers. Then iterate over i<=n, distribute i pieces among suppliers taking only priceBreak, and then add the rest to the supplier with the minimum price (without going beyond the next priceBreak!). But I'm not sure that this will work (I haven't been able to prove yet that if someone's supplier's tail sticking out from priceBreak is cut off for the optimal answer, then the answer will remain optimal for the new quantity).

Answer 2

You have a typical problem for the simplex method .
In this case, to find the minimum of the function.
https://github.com/westla/Simplex-Calculator

Answer 3

the implementation depends on the language, in general terms we bypass the goods in a loop, in the nested loop we find the min. cost