Wednesday, December 17, 2008

Santa Knows Linear Programming!

Oh No! The economy has caught up with Santa too. With one week to go, with huge cost overruns and unable to obtain any credit, Santa is forced to now charge parents $10 for each toy for children over the age of 5 and $5 for each toy for children 5 and under. He has determined there are 560 elf-hours available for making the toys and 100 hours available for quality control ("checking them twice"). Each toy for the older children requires 1.5 hrs to produce and 15 minutes to check, while each toy for the younger children requires 1 hr to produce and 12 minutes to check.
How many of each should be produced to maximize Santa's revenue?
Why will the mathematical solution lead to unhappy children 5 and under? Will Santa follow his mathematical mind or his heart or Rudolph?

(BTW, my wife just read this and her suggestion is that Santa should consider outsourcing or visiting the local dollar store where one can buy $5 toys for a buck - she is definitely more practical than I am!).

Anyone (including us!) who hasn't worked with these recently or doesn't have much experience with these kinds of problems often struggle to get started: choosing variables, organizing all of the information, setting up the inequalities, etc. The issue of the best way to introduce this topic is a separate issue. The problem above does not represent an introductory problem to this topic! Furthermore, I threw in some complications (units, rounding issues, etc.). Again, there are pedagogical issues which I will not address for now (maybe in the comments). Have Fun!

Here's the setup:
x = the number of toys to be made for the older children
y = the number of toys to be made for the younger children

Objective Function: Revenue (R) = 10x + 5y

Constraints (defining the polygonal region):
x ≥ 0
y≥ 0
1.5x + 1y ≤ 560
0.25x + 0.2y ≤ 100


Sean Henderson said...

Well, since my trig class went over this exact thing earlier this semester, I put it in as an extra credit question. We'll se if they like it.

Dave Marain said...

Happy Holidays, Sean, to you and your students!
I would be interested in their reactions, how many will attempt this, never mind solve it.

They may need a calculator for some of the computation. Would you also give them graph paper for more accurate graphing (as opposed to a quick sketch)?

This 'extra credit' problem will be time consuming so you may also consider giving this as an extra credit problem outside of class (mention an honor system there but expect some collaboration!). Another possibility is, for that half day before the holidays (if you get one), have them compete against each in teams of 2,3, or 4.

Thanks for your support as always...

Anonymous said...

The important technique to get from this simple problem (remembering that practical LP problems are much worse) is that the answer must lie at a vertex of the problem domain. It's a fun thing to show, and doesn't require any calculation at all; just a simple argument on parametric equations for line segments.

Finding the vertices shouldn't be a difficult task either.

However, you may have problems explaining how LP problems occur in real life; the difference between a toy problem like this and the problem of supplying the Sixth Fleet with food and ammunition with the least transport cost is a few orders of magnitude.

Dave Marain said...

Thanks Eric and Happy Holidays!

I really think all hs math students who plan on continuing their study should see the parametric argument to which you're referring. It's instructive and elegant and I guess I should consider developing this as an investigation or a video.

As far as giving students a view of real-world applications of LP, I see it both ways. Show them an application, a video perhaps, showing professionals who utilize the technique. This provides some motivation and an overview. One needn't worry over the complexity of this professional application - it's just giving the 'big picture.' A careful incremental development can then follow. Many lessons often gloss over the practical application and focus only on the procedure.

By the way, I am willing to bet that Santa's problem will provide formidable to many students even if they have had an introduction to LP. Keeping track of even a small number of variables and setting up those constraints can be mind-boggling for many youngsters.