1. We have added the ability to collapse/expand forum categories and widgets on forum home.
    Dismiss Notice
  2. Photobucket has changed its policy concerning hotlinking images and now requires an account with a $399.00 annual fee to allow hotlink. More information is available at: this link.
    Dismiss Notice
  3. All Civ avatars are brought back and available for selection in the Avatar Gallery! There are 945 avatars total.
    Dismiss Notice
  4. To make the site more secure, we have installed SSL certificates and enabled HTTPS for both the main site and forums.
    Dismiss Notice
  5. Civ6 is released! Order now! (Amazon US | Amazon UK | Amazon CA | Amazon DE | Amazon FR)
    Dismiss Notice
  6. Dismiss Notice
  7. Forum account upgrades are available for ad-free browsing.
    Dismiss Notice

Maths problem!!

Discussion in 'Science & Technology' started by Mise, Jun 10, 2008.

  1. Mise

    Mise isle of lucy

    Joined:
    Apr 13, 2004
    Messages:
    28,503
    Location:
    London, UK
    I sell different types of sweets. Sweets get put into a box, and sold. I know the cost of the box, but not the cost of each sweet. I know how many sweets go into each box. How do I calculate the cost of each sweet?

    For example, if there are three boxes (X, Y and Z), and four sweets (A, B, C and D), the contents of each box are as follows:

    Box X contains 4*A, 3*B, 7*D
    Box Y contains 5*A, 1*C, 2*D
    Box Z contains 2*B, 3*C

    Box X costs $204, box Y costs $96, and box Z costs $66.

    How much does A, B, C and D cost?

    I'm trying to use linear programming to "fit" the solution (i.e. finding the combination of sweet costs that minimise the absolute difference between the sum of the costs and the actual box cost), but I'm not sure that's the best way of doing it. It works in this small problem (kinda...) but in bigger problems it's somewhat lacking. Is there a more direct approach?
     
  2. uppi

    uppi Chieftain

    Joined:
    Feb 2, 2007
    Messages:
    3,504
    I'd solve the linear equation sytem for three variables with the forth variable as free parameter.

    for example:

    A= A,
    B = -165/16+(81/32)*A,
    C = -(27/16)*A+231/8,
    D = -(53/32)*A+537/16

    Now I am assuming that the variables are integer values, because else there are infinite solutions.

    I have no idea if there is a better way, but now I would simply try all values from 0 to 20 and filter for the results, where all values are integers, in this case this is only true for A=10
     
  3. ParadigmShifter

    ParadigmShifter Random Nonsense Generator

    Joined:
    Apr 4, 2007
    Messages:
    21,810
    Location:
    Liverpool, home of Everton FC
  4. Erik Mesoy

    Erik Mesoy Core Tester / Intern

    Joined:
    Mar 25, 2002
    Messages:
    10,949
    Location:
    Oslo, Norway
    Yeah, PS has it, pretty much. I'll try to help get you started some more:

    4A + 3B + 0C + 7D = 204
    5A + 0B + 1C + 2D = 96
    0A + 2B + 3C + 0D = 66

    Here are the next steps I would do:
    Multiply the first row by 10 so that the first term is divisible by 5 and the second term is divisible by 2

    40A + 30B + 0C + 70D = 2040
    5A + 0B + 1C + 2D = 96
    0A + 2B + 3C + 0D = 66

    Subtract eight of the second row from the first row

    0A + 30B + -8C + 54D = 1272
    5A + 0B + 1C + 2D = 96
    0A + 2B + 3C + 0D = 66

    Subtract fifteen of the third row from the first row

    0A + 0B + -23C + 54D = 282
    5A + 0B + 1C + 2D = 96
    0A + 2B + 3C + 0D = 66

    Etc. (Next multiply rows two and three by 23, so that you can get rid of the C term in them.) You usually need four boxes to be able to properly determine the value of four sweets, though.

    Edit: Gah, I think I got some numbers wrong. That's what I get for not using a calculator when handling too many numbers in my head at once. Use a calculator. ;)
     
  5. Mise

    Mise isle of lucy

    Joined:
    Apr 13, 2004
    Messages:
    28,503
    Location:
    London, UK
    Thanks guys! I assume there are programs and things that will convert my equations into Reduced Row Echelon Form... If not, it seems a fairly "programmable" set of procedures to do.

    They needn't be integers, but there are other constraints that will narrow down the options. At this stage, I just want some procedure that will tell me what a possible solution is, and I can take it from there. My problem actually involves ~350 variables and ~100 equations, so something programmable is ideal. There's a fair bit of leeway on what I can actually present as the value of each variable.
     
  6. uppi

    uppi Chieftain

    Joined:
    Feb 2, 2007
    Messages:
    3,504
    Err...I don't think his problem is solving the equation systems. That can be easily done by a computer (Calculating a linear equation system with more than three variables manually will usually fail anyway).

    The problem in this case is getting the solution(s) that fit your external restrictions (e.g. all variables must be postive integers) out of the infinite solutions for the equation system.

    edit because of crosspost:
    if you convert your problem into matrix form (assuming it is linear), every decent mathematics programm will tell you all the possible solutions. However as 100 equations will maximally determine 100 variables, you will still have 250 variables that you will have to somehow fit to external conditions.
     
  7. Mise

    Mise isle of lucy

    Joined:
    Apr 13, 2004
    Messages:
    28,503
    Location:
    London, UK
    :wow: What programs can I use?

    I'm guessing Matlab/Maple/Mathematica would work, but I don't have those at work, so it'll have to be something nice and freeware...
     
  8. uppi

    uppi Chieftain

    Joined:
    Feb 2, 2007
    Messages:
    3,504
    Octave should work. It's basically a Matlab clone, but I havent used it myself.
     
  9. Mise

    Mise isle of lucy

    Joined:
    Apr 13, 2004
    Messages:
    28,503
    Location:
    London, UK
    Octave looks good. And thanks for the edit. I think I might try and look at the constraints first, and see if I can reduce the number of variables that way...
     
  10. ParadigmShifter

    ParadigmShifter Random Nonsense Generator

    Joined:
    Apr 4, 2007
    Messages:
    21,810
    Location:
    Liverpool, home of Everton FC
    Yeah, the algorithm is easy but I'd use someone elses program [EDIT: lol I had problem here instead of program] to get the solution, if you roll your own you will probably encounter many issues with accuracy etc.

    As others have said, if you have ~250 free variables you are looking at a ~250 dimensional solution space ;)

    You are probably better off looking into linear regression in that case, get the best fit solution for the data.

    Starting point: http://en.wikipedia.org/wiki/Linear_regression
     
  11. Perfection

    Perfection The Great Head.

    Joined:
    Apr 9, 2002
    Messages:
    49,186
    Location:
    Salisbury Plain
    I don't think a linear fit would work so well with such a data analysis. With so many parameters to alter you'd probably run into [wiki]overfitting[/wiki] and get junk results.

    [wiki]Decision tree learning[/wiki] might be the way to go.
     
  12. ParadigmShifter

    ParadigmShifter Random Nonsense Generator

    Joined:
    Apr 4, 2007
    Messages:
    21,810
    Location:
    Liverpool, home of Everton FC
    Well, linear regression doesn't imply a linear fit... you can do a regression with squared terms etc.

    I think you are suggesting do some kind of correlation analysis on the parameters though... sounds like a good plan.

    I'm guessing now this isn't about prices of sweets in your Dad's sweetshop or a homework question ;)

    If you find out how to beat the stock market make sure you PM me and let me know how too ;)
     
  13. Perfection

    Perfection The Great Head.

    Joined:
    Apr 9, 2002
    Messages:
    49,186
    Location:
    Salisbury Plain
    well with so many parameters, I'd be suprised if it didn't fit exactly. Mise needs some serious dimensionality reduction.

    I know somewhere on the Internet you can get CART decision tree software for Matlab, but I can't seem to find it.

    Whatever Mise chooses, it would be wise of him to use [wiki]cross-validation[/wiki] (preferably leave one out) to confirm the goodness of his model.
     
  14. ParadigmShifter

    ParadigmShifter Random Nonsense Generator

    Joined:
    Apr 4, 2007
    Messages:
    21,810
    Location:
    Liverpool, home of Everton FC
    Yep he needs to check his variables are really independent... so long since I did stats at uni... [EDIT: I think Chi-squared maybe good for that, but as I said, too long ago]

    All this talk of sweets was a load of tosh though!
     
  15. Perfection

    Perfection The Great Head.

    Joined:
    Apr 9, 2002
    Messages:
    49,186
    Location:
    Salisbury Plain
    I think you're using statistical methods that work good for large sets of data where amount of data >> the number of variables. But since you can usually fit a 350-dimensional object (your linear regression) exactly through 100 points, and that's going to lead to junk results where the noise in the data overwhelms any real correlations.

    Mise needs to reduce the number of variables. CART decision trees can do it automatically. Mise also needs to control model complexity, cross-validation works best for that.

    Traditional statistical methods don't work here, Mise needs to get into learning theory stuff.
     

Share This Page