View Full Version : Maths problem!!


Mise
Jun 10, 2008, 11:55 AM
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?

uppi
Jun 10, 2008, 01:29 PM
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

ParadigmShifter
Jun 10, 2008, 02:10 PM
Man those sweets are expensive.

You can get all possible solutions with a bit of linear algebra, a quick search found this page

http://en.wikibooks.org/wiki/Linear_Algebra/Row_Reduction_and_Echelon_Forms

Reduced Echelon form is what you need to know about.

Erik Mesoy
Jun 10, 2008, 03:21 PM
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. ;)

Mise
Jun 10, 2008, 03:35 PM
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.

uppi
Jun 10, 2008, 03:35 PM
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.

Mise
Jun 10, 2008, 03:39 PM
That can be easily done by a computer (Calculating a linear equation system with more than three variables manually will usually fail anyway).

: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...

uppi
Jun 10, 2008, 03:42 PM
: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...

Octave should work. It's basically a Matlab clone, but I havent used it myself.

Mise
Jun 10, 2008, 03:58 PM
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...

ParadigmShifter
Jun 10, 2008, 04:25 PM
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

Perfection
Jun 10, 2008, 04:57 PM
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 overfitting and get junk results.

Decision tree learning might be the way to go.

ParadigmShifter
Jun 10, 2008, 05:03 PM
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 ;)

Perfection
Jun 10, 2008, 05:10 PM
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 cross-validation (preferably leave one out) to confirm the goodness of his model.

ParadigmShifter
Jun 10, 2008, 05:14 PM
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!

Perfection
Jun 10, 2008, 05:50 PM
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.