Tuesday, July 03, 2012

Operations Research

I've been feeling a small 'intellectual void' in the past few weeks: many things which have occupied my time seem to be winding down and I don't know how I'll be stimulating my brain in the coming months. In an attempt to jump-start the process, I found some texts on operations research, a subject which I thought might interest me. From the little that I've seen, this subject seems to be based on mathematics and appears somewhat heavy.

Here is a little puzzle from the first chapter of one of the books - Andrew, Brian, Charles and David (names changed to protect the guilty) are standing on the east bank of a river and wish to cross to the west side, using a canoe, which can hold at most two people at one time. Andrew, being the most athletic, can row across the river in one minute; Brian, Charles and David require 2, 5 and 10 minutes, respectively. If two people are in the canoe then the slower person dictates the crossing time. The objective is for all four people to be on the west bank of the river in the shortest possible time.

A naive and reasonable solution would be for Andrew and Brian to cross (2 minutes), Andrew to return (1), Andrew and Charles to cross (5), Andrew to return (1), Andrew and David to cross (10); this sequence would take 19 minutes. What would be a faster solution?

No comments: