The Price of Beer - Linear Algebra Problem

[pbuk]

In an ill-conditioned problem, I would hate to guess how many reasonable solutions there might be, and what the standard of "reasonable" is.

I often find that by not worrying about how hard and unreasonable something might be and instead just doing it, it turns out not to be so hard or unreasonable after all. You can see from the timings in #14 that it took me less than 10 minutes to find the solution once I had found a decent version of the question (which took about half an hour).

 

[FactChecker]

I often find that by not worrying about how hard and unreasonable something might be and instead just doing it, it turns out not to be so hard or unreasonable after all. You can see from the timings in #14 that it took me less than 10 minutes to find the solution once I had found a decent version of the question (which took about half an hour).

You found A solution. How many more are there? There are a lot of combinations of full and half pints that might be other solutions. In a simple, small, academic example, you might be able to handle it well, but nobody really needed this problem to be solved anyway; it's just a practice exercise. There are a lot of real-world problems that have hundreds, even thousands of variables.

IMHO, this is just a bad example. It is ill-conditioned, with no hint of how to handle that aspect. It is less well-defined than it needs to be. The solution is "ad-hoc".

 

[diegogarcia]

Anyway the question is available on the interweb: it is the bonus question in Part 1 of worksheet 3 from http://www.staff.city.ac.uk/o.s.kerr/CompMaths/.

Thanks for providing that link. I could not find the original site.

Yes, ill-conditioning is the issue here. For a very brief, although very comprehensive, discussion see this blog post:

Condition Number of a Matrix

Most CA software include functions to determine the condition number. For the FOSS Maxima software, one can use the functions described here:

https://def.fe.up.pt/pipermail/maxima-discuss/2007/018137.html

mat_norm2j(M) := sqrt(lmax(eigens_by_jacobi(transpose(conjugate(M)).M)[1]));

Using this function, the condition number of the matrix in this problem is 3923.4, which is large enough to cause considerable error.

I always thought that the issue of this problem was theoretical in nature, but the issue is actually numerical in nature.

 

[scottdave]

Since the person doesn't have all of the information (pricing of a half pint vs pint) then this is an estimation problem, rather than an algebra problem.

They are all friends. He could just find the average spent per pint for all of the beer. Then he knows how many pints each person consumed.

 

[pbuk]

Since the person doesn't have all of the information (pricing of a half pint vs pint)

I am not sure how many times it needs to be said that a half pint is priced at half of the price of a pint, rounded up to a £0.01 if necessary.

then this is an estimation problem, rather than an algebra problem.

No it isn't, it is a problem demonstrating the magnification of errors in ill-conditioned problems in computational linear algebra.

 

[FactChecker]

I am not sure how many times it needs to be said that a half pint is priced at half of the price of a pint, rounded up to a £0.01 if necessary.

Should we assume there are only marginal costs and no fixed cost? I think that is unusual. The per unit price is usually noticeably higher for the smaller quantity, and not just due to rounding up.

 

[pbuk]

Should we assume there are only marginal costs and no fixed cost? I think that is unusual. The per unit price is usually noticeably higher for the smaller quantity, and not just due to rounding up.

You should assume exactly as much as needs to be assumed to answer the question and no more. For the avoidance of doubt this means that instead of the first equation being $1.5b + 2l +2.5c + 0.5s = 8.99$, the correct sum could also be $8.985, 8.98 \text{ or } 8.975$ depending on how many of $b, c \text{ and } s$ have prices for a pint that are an odd number of pence. There are 16 combinations to try in all (including the one that leads to $b = -£3.86$) and only one gives a sensible answer. Remember this is a question in computational mathematics: iterating over a potential solution space is part of the standard toolbox (and each iteration is just 1 matrix multiplication).

 

[scottdave]

,... it is a problem demonstrating the magnification of errors in ill-conditioned problems in computational linear algebra.

For some reason it "clicked" for me, this time.

 

[FactChecker]

No it isn't, it is a problem demonstrating the magnification of errors in ill-conditioned problems in computational linear algebra.

It certainly illustrates that. I'm just not sure that was intended. I would have to see the text.
(I have seen an optimization example where the matrix was actually singular in a text where the code testing for a zero determinant was commented out.)

 

[Mark44]

The thread seems to have run its course, so I'm closing it. If anyone feels the need to add anything more of substance, please let me know and I'll reopen the thread.