Dan34 Posted December 21, 2011 Share Posted December 21, 2011 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. Link to comment Share on other sites More sharing options...
imatfaal Posted December 21, 2011 Share Posted December 21, 2011 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 Link to comment Share on other sites More sharing options...
Xittenn Posted December 21, 2011 Share Posted December 21, 2011 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]? Link to comment Share on other sites More sharing options...
Dan34 Posted December 21, 2011 Author Share Posted December 21, 2011 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. Link to comment Share on other sites More sharing options...
Xittenn Posted December 21, 2011 Share Posted December 21, 2011 Ah . . . . the subscriptions are restricted as well. Maybe modify the restriction to be the product of the number of cookies and total subscriptions? Link to comment Share on other sites More sharing options...
Dan34 Posted December 21, 2011 Author Share Posted December 21, 2011 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. Link to comment Share on other sites More sharing options...
DrRocket Posted December 21, 2011 Share Posted December 21, 2011 (edited) 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 Link to comment Share on other sites More sharing options...
Xittenn Posted December 21, 2011 Share Posted December 21, 2011 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? Link to comment Share on other sites More sharing options...
insane_alien Posted December 21, 2011 Share Posted December 21, 2011 random walk search? Link to comment Share on other sites More sharing options...
Xittenn Posted December 21, 2011 Share Posted December 21, 2011 (edited) 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 Link to comment Share on other sites More sharing options...
DrRocket Posted December 22, 2011 Share Posted December 22, 2011 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. 1 Link to comment Share on other sites More sharing options...
khaled Posted February 27, 2012 Share Posted February 27, 2012 (edited) 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 Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now