问题描述:

I have an assignment at work that involves finding the solution to this difficult problem.

Customers here can buy product allocations in either daily, monthly, quarterly or yearly amounts. Each step has a multiplier associated with it to incentivise people to book the longest allocation, so for example a day = 1.5 times the unit price, quarter = 1.3, month=1.2 etc.

This was fine, however, now they would like to see if having a different multiplier per step (i.e month 1 = 1.5, month 2 = 1.2, month 3 = 1.4 etc) down to monthly resolution.

In this case, the base case is year = 1, and daily = 1.5 with monthly and quarterly multipliers set inbetween.

My task is to get the perfect optimisation of each step to minimise the bill (we are simulating what a buyer will do) according to a demand profile.

So to sum up I need to find the minimum price a buyer could get while still meeting their demand profile.

Here's an example of the sort of demand chart I'm working with, with each yearly division shown where the multipliers are equal to 1 (the base case)

I'm working with either **VBA, Python, PHP, or C** for this. Preferably VBA (what work wants) or PHP (what I want) but in any case, it' the general case I don't get. Just how would I even start going about this price optimisation?? Will it be a case of literally simulating EVERY case? (of which there are 131,071 [year divides into 12 months, 4 seasons, 1 year + 12 months + 4 seasons + 1 daily multiplier = 18, 2^18=262144, divide by 2 because in every case they will buy days and minus 1 for the null case]).

Thanks to anyone who can help,even just a little bit!

Is this similar to the packaging problem and knapsack problems? http://en.wikipedia.org/wiki/Packing_problem and http://en.wikipedia.org/wiki/Knapsack_problem

If you consider each month as a package size, then you are after the best fit to a total demand. Just with the added twist of first package fitting for a year, then for 5months, then for 4 months etc. These algorithms are surprisingly quick even considering the brute force like nature, and they are also nice and decomposable to multiple processors if needed? (sorry this isn't just a comment, I'm not able to comment yet, or don't know how..) (thinking more, perhaps FFT might also be useable here, but I'm not an expert in that)