Otpimization question (beyond multivariable calculus?)

[Dan34]

Hello,

 

Here is a problem that I think should be solvable but I am not sure how.

 

You need to have 450 subscriptions, each subscription gives a certain amount of cookies/year. You want to recieve 1,600,000 (+/- 10,000) cookies for the lowest cost.

 

Here are your subscription options:

0 cookies for $300

4000 cookies for $500

9000 cookies for $900

20000 cookies for $1800

 

Having a hard goal with some variance (1,600,000 +/-10,000) that is not a minimum or max, and a required amount of subscriptions adds complexity that I do not know how to deal with (outside of programming something to try them all).

 

 

If you are able to solve this mathmatically please let me know how.

[imatfaal]

Whilst it is not a real answer - however in this particular case can you not do the following

 

the solution using all 4000c/$500 subscriptions is 398 of 4000c @ $500 + 52 of 0c @ $300

 

to replace any of the cookies with the first 9000c/$900 sub the marginal saving is

 

[cost of 9000c] less [saved cost of 4000c] less [extra 0c to keep to 450 limit]

900 - (-2.25 * 500) - (1.25 x 300) = -150

 

to replace any of the cookies with the first 20000c/$1800 sub the marginal saving is

 

1800 - (5*500) - (4*300) = - 500

 

You can then start again the the same logic will apply and show that it is never worth replacing any of the cookies that you have purchased on a 4000c/$500 sub with a different subscription

 

I realise this is not gneralisable - but it does show that solutions are possible without longhaul checking - that is providing I havent screwed up

[Xittenn]

Wouldn't this simply be a case of using a Lagrange multiplier with a minimum price [math] P(a,b,c,d) [/math] restricted to the number of cookies [math] C(a,b,c,d) [/math] being equal to 1,600,000 and new formula [math] F(a,b,c,d,\lambda) [/math]?

[Dan34]

Thank you, that is a very good way to get a great answer.

 

I would be interested in a formula that can accomodate consumption, and subscription offering changes (although I can do this using the below formulas in excel).

 

I previously tryed to come up with it for fun and it has stumped me Now I want to know how/if other people solve it

 

 

Sorry, as you have already shown, I am making it more complicated than it needs to be.

 

 

 

 

 

 

 

[Xittenn]

Ah . . . . the subscriptions are restricted as well. Maybe modify the restriction to be the product of the number of cookies and total subscriptions?

[Dan34]

Wouldn't this simply be a case of using a Lagrange multiplier with a minimum price [math] P(a,b,c,d) [/math] restricted to the number of cookies [math] C(a,b,c,d) [/math] being equal to 1,600,000 and new formula [math] F(a,b,c,d,\lambda) [/math]?

 

 

This sounds interesting/fun... I am going to do some research and see if I can use the method you described above. I will let you know if I find a reason why that would not work.

[DrRocket]

Wouldn't this simply be a case of using a Lagrange multiplier with a minimum price [math] P(a,b,c,d) [/math] restricted to the number of cookies [math] C(a,b,c,d) [/math] being equal to 1,600,000 and new formula [math] F(a,b,c,d,\lambda) [/math]?

 

No. The problem posed is very discrete in nature. Only a finite number of potential solutions exist and calculus is useless.

 

This problem is a combinatorial nightmare, and totally impractical. You are not looking for a minimum cost to obtain 1,600,000 cookies (that solution is obvious) but a minimum cost with 450 subscriptions, which is quite a different thing.

 

You need to somehow consider all possible solutions. There may be a strategy to reduce the number of cases that must be evaluated in detail, but I don't see it at first blush.

Edited December 21, 2011 by DrRocket

[Xittenn]

No. The problem posed is very discrete in nature. Only a finite number of potential solutions exist and calculus is useless.

 

Could it not be solved using Calculus and assuming partial subscriptions as well as cookie pieces, followed by a rounding to whole numbers?

[insane_alien]

random walk search?

[Xittenn]

random walk search?

 

Why not a brute force algorithm, it's a fairly small data set for a computer?

 

Who is going to subscribe to 0 cookies for $300? I still don't see why the following won't work; given that cookies and subscriptions are treated as continuous and rounded after.

 

0 cookies for $300

4000 cookies for $500

9000 cookies for $900

20000 cookies for $1800

 

1) [math] P(a,b,c,d) = 300a + 500b + 900c + 1800d [/math]

 

2) [math] R(a,b,c,d) = ( 450 - ( a + b + c + d) )( 1,600,000 - ( 4000b + 9000c + 20000d ) ) = 0 [/math]

 

3) [math] F(a,b,c,d,\lambda) = P(a,b,c,d) - \lambda R(a,b,c,d) [/math]

[math]= ( 300a + 500b + 900c + 1800d ) - \lambda( ( 450 - ( a + b + c + d) )( 1,600,000 - ( 4000b + 9000c + 20000d ) ) ) [/math]

Edited December 21, 2011 by Xittenn

[DrRocket]

Could it not be solved using Calculus and assuming partial subscriptions as well as cookie pieces, followed by a rounding to whole numbers?

 

No.

 

If you assume partial subscriptions the 2000 cookie subscription, with the lowest per cookie cost provides the solution.

This problem as stated is not amenable to any application of calculus of several variables. It is very non-linear and totally discrete problem. Such problems are both very difficult to solve and completely uninteresting.

 

Why not a brute force algorithm, it's a fairly small data set for a computer?

 

Who is going to subscribe to 0 cookies for $300? I still don't see why the following won't work; given that cookies and subscriptions are treated as continuous and rounded after.

 

0 cookies for $300

4000 cookies for $500

9000 cookies for $900

20000 cookies for $1800

 

1) [math] P(a,b,c,d) = 300a + 500b + 900c + 1800d [/math]

 

2) [math] R(a,b,c,d) = ( 450 - ( a + b + c + d) )( 1,600,000 - ( 4000b + 9000c + 20000d ) ) = 0 [/math]

 

3) [math] F(a,b,c,d,\lambda) = P(a,b,c,d) - \lambda R(a,b,c,d) [/math]

[math]= ( 300a + 500b + 900c + 1800d ) - \lambda( ( 450 - ( a + b + c + d) )( 1,600,000 - ( 4000b + 9000c + 20000d ) ) ) [/math]

 

The reason for the 0 cookies for $300 possibilitb is that it lets you also take 80 subscriptions of 2000m cookies at $1800 each and then fill in the remaining 370 subscriptions to get to the required 450. As I said,this is a totally impractical and uninteresting problem.

[khaled]

This problem is just like what DrRocket said, it's a combinatorial problem

 

I'm not sure, but it seemed similar to knapsack problem, which can be solved using Dynamic Programming (Optimization over few variables)

 

But this one seem to more complex than a knapsack problem

Edited February 27, 2012 by khaled