# Maths problem!!

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

1. ### Miseisle 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. ### uppiChieftain

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

Joined:
Apr 4, 2007
Messages:
21,810
Location:
Liverpool, home of Everton FC
4. ### Erik MesoyCore 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. ### Miseisle 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. ### uppiChieftain

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. ### Miseisle of lucy

Joined:
Apr 13, 2004
Messages:
28,503
Location:
London, UK
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. ### uppiChieftain

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

9. ### Miseisle 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...

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

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.

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

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.

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!

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.