Optimum pack size purchases: follow-up to minimum cost solution

I think the answer to 1 is MaxQuantity = LCM(Packsize) = 500

LCM: least common multiple

For 2, i think for example f_mincost(1300) = 2 * f_mincost(500) + f_mincost(300)

What would be the general expression?

I think:

f_mincost(QuantityNeeded) =
 Integer( QuantityNeeded/LCM ) * f_mincost( LCM ) + f_mincost( mod(QuantityNeeded,LCM) )

where LCM = LCM(PackSize)

Demo'd on this sheet: https://docs.google.com/spreadsheets/d/1TMiCPLrCq4pI-SjYUz_AhBY8g_duXlIKfDvOAZo0EC8/edit#gid=570105731

Your packet size and cost can be expressed as {  S_i, C_i } where the sizes are in increasing order; and I assume that, in general, the larger S is, the lower the unit cost. You refer to LCM. I don't believe that has any value. LCM just happens to be the largest size, 500, but for other lower values of size, the LCM may not be 500. But that largest size value of 500 is needed in your algorithm to compute the minimum cost.

f_mincost(6400) = ?

Step 1
Divide 6400 by the largest size , 500 , and get a quotient, Q, and remainder, R:
Q(6400/500) = 12
R = 6400 - (12 * 500) = 6400 - 6000 = 400

From this first step, you need to buy 12 orders of size 500g for a cost of 12 * $1 = $12
You still need to order 400g. (I would round up and just get 13 orders for a cost of $13 and store a away the extra 100g; but I'll assume you have no storage space.)

Step 2
Divide 400 by the next largest size, 250, and get a quotient, Q, and remainder, R:
Q(400/250) = 1
R = 400 - (1 * 250) = 400 - 250 = 150

 This second step, you need to buy one order of size 250g for cost of 1* $0.75 =  $0.75
 You still need to order 150g.

Step 3
Divide 150 by the next largest size, 100, and get a quotient, Q, and remainder, R:
Q(150/100) = 1
R = 150 - (1 * 100) = 150 - 100 = 50

Since there are no package sizes smaller than 100, you need to round up and purchase two orders of 100g for a cost of 2 * 0.40 = $0.80.

Your total cost is $12 + $0.75 + $0.80 = $13.55 and you have 50g left over to throw away.

Notice that the actual minimum cost is $13 by purchasing 13 orders of the largest packet size and then throwing away 100g. Of course you would not have known that the minimum cost is $13 unless you proceeded onto steps 2 and 3.

Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (mathematical optimization).

More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Its feasible region is a convex polytope, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued affine (linear) function defined on this polyhedron. A linear programming algorithm finds a point in the polyhedron where this function has the smallest (or largest) value if such a point exists.

https://en.m.wikipedia.org/wiki/Linear_programming

Here is a mathematics course covering linear programming. In their example in lecture 1, she talks about different foods and the vitamins minerals proteins associated with each food. There are constraints on what you eat everyday - known as minimum daily requirements or recommended daily allowances . So you have to get your protein , minerals, and vitamins. Maybe your objective is to eat healthy at minimum cost . This is what linear programming is about; namely to minimize or maximize some objective subject to constraints . In this case the constraint is to make sure that every day you get the required minimum amount of protein minerals and vitamins.

 Here is an entire course on linear programming . It consists of 27 lectures each is about 1 1/4 hours long.
https://m.youtube.com/watch?v=FdKgeeb4q3w      1.  Skip the first 9.5 minutes
https://m.youtube.com/watch?v=xY6AlnGZ1bw.       2
https://m.youtube.com/watch?v=N4GxD63lqLc.        3
https://m.youtube.com/watch?v=NYZ206ccuzY.          4
https://m.youtube.com/watch?v=cvRWORxDAY8.         5
https://m.youtube.com/watch?v=reswxUMC0iM.           6
https://m.youtube.com/watch?v=i4ig7Cpravo.                 7
https://m.youtube.com/watch?v=kh2qKN1jEAA.               8
https://m.youtube.com/watch?v=CiLG14fsPdc.                   9
https://m.youtube.com/watch?v=kvIp2CfFDUQ (ruined version)   10
https://m.youtube.com/watch?v=_uhTN6KvCC8.                               10

Here is a very short introduction to linear programming:
https://m.youtube.com/watch?v=gbL3vYq3cPk

Thank so much for this, and sorry for delay in responding, I have only just seen these updates. I will work through this and post again in a few days. Hopefully will make sense, it's been a couple of decades since i studied LP but hoping it'll come back !

Thanks again

I should have pointed out, that if you complete the order in Step 2, then you actually save a little by not doing Step 3; but not as much savings as just completing the order in Step 1 (as noted above). I got to lecture 4 before having to go back to work. To save time, I skipped a little every time the teacher writes on the board, and then pause a moment to read. Just hope i don't miss a pearl of wisdom as I go through these. The first two lectures give a very good rehash of your problem if you only had 2 variables instead of 3.

As you mention in your first comment, it's true that LCM(PackSize) is not necessarily MAX(PackSize), hence the use of the LCM function.

Your suggestion seems to be offering an alternative to the solution to my previous question.

However this current question is not asking for another algorithmic solution, rather it follows from the above previous question and asks:

Questions:
1. What MaxQuantity do we need to tabulate upto before the pattern is repeating
    ie MaxQuantity = some function of Packsize
2. How can we define f_mincost(QuantityNeeded) as a function of this repeating pattern
   eg what is f_mincost(6400) as a function of f_mincost(some value <= MaxQuantity)

Having written the question I posted what I think is the solution.

From tests done so far I believe this solution is complete. I will try to demonstrate this before closing this question.

You state

You refer to LCM. I don't believe that has any value

Can you demonstrate this?

It maybe your suggestion could be useful to verify this or otherwise.

Your suggestion to just round up may also be relevant in some instances of the problem, and I may look to parameterise the method used depending on the inputs. For example if LCM is very high (eg LCM (50, 250, 499) = 124750 it maybe that a lookup table solution is less efficient unless some approximation is done.

I will also have other related problems where it could well be that LP is required, so I will keep an eye on this info and refer back to it as and when I post those related problems.

Thanks again.

>> Your suggestion to just round up may also be relevant in some instances of the problem
Sorry I gave you that was my suggestion. I was just demonstrating that for this instance we have a solution using this approach. In general, the solution is solved using LP.

>> You refer to LCM. I don't believe that has any value
I was thinking in the more general cases of arbitrary numbers. For example, LCM( 25, 49, 81) = 99225. I don 't see how this number is going to help you. Granted in specific cases, there may be some optimizations when using the LCM that you notice to help, but not in a formulation.

I also believe that patterns may only be meaningful in very specific cases, but not in general.

My belief is that in the general case of an arbitrary number of variables (your OP shows 3, which is beyond the scope of the first couple of lectures) and a set of constraints, then this problem is already solved, and there are entire semesters to explain how to solve them.

>> From tests done so far I believe this solution is complete. I will try to demonstrate this before closing this question.
I look forward in seeing your demo for arbitrary number of variables and values.